Research map / Learning theory and algorithms / Prediction and decision losses

On the Tightness and Computational Tractability of Higher-Dimensional Confidence Sequences

NeurIPS 2026 · Learning theory and algorithms › Prediction and decision losses · approach: Distributionally robust optimization · 0 citations (OpenAlex)

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Proposes tractable outer approximations (bounding box, lp-ellipsoid, and their intersection) of the intractable portfolio confidence sequence for bounded vector means, built from 1D betting-based wealth processes, preserving anytime validity.

Problem

Multivariate confidence sequences for bounded vector means are either tight but computationally intractable (portfolio/ mixture-type regions with O(t^D) membership) or tractable but conservative (Bonferroni, spheres), limiting multi-metric sequential monitoring.

Approach

Lift 1D betting-based CSs to vectors via a weighted Bonferroni rectangle, a max-wealth form (shown equivalent to Bonferroni), and a weighted portfolio sum of wealths; then derive a bounding-box outer approximation and an lp-ellipsoid fitted per coordinate with two touch points, and intersect them, with certified validity after numerical implementation.

Key results

• At D=10 the portfolio volume is up to 50% smaller than the Bonferroni rectangle on synthetic data.
• In the simulated A/B test with effect, the proposed CSs (bonf, bbox, ellipsoid) stop at batch 178 versus 5,018 for Banach Sphere and never for Conf Sphere.
• In the Adult model comparison the CSs detect an overall accuracy improvement after about 356 batches while existing tractable baselines remain inconclusive over all 509 batches.

Surprising findings

• The max-wealth form is exactly equivalent to the weighted Bonferroni rectangle, so the bounding box is the only lift that tightens Bonferroni at the same cost.

Limitations

• The lp-ellipsoid is only a valid CS in its safe variant; the grid-based version is approximate.
• Intersection volume requires Monte Carlo estimation, which degrades as dimension grows.
• Per-dimension ellipsoid fitting relies on a discretization grid that can be costly.

Experimental setup

Datasets: Adult simulated web-shop A/B metrics synthetic bounded vector distributions (unit ball, Bernoulli mixture)

Benchmarks: synthetic unit-ball and Bernoulli-mixture distributions simulated A/B web metrics Adult multi-metric model comparison

Metrics: region volume coverage number of k evaluations stopping time relative volume to Bonferroni

Baselines: Banach Sphere Conf Sphere Sub-psi ellipsoids Bounded UP Bonferroni rectangle

Builds on: Bonferroni correction Ville's inequality betting-based confidence sequences (Waudby-Smith & Ramdas) Banach sphere CS Sub-psi ellipsoids

Closest papers by meaning

• Gambling-Based Confidence Sequences for Bounded Random Vectors (ICML 2024 · similarity 0.89)
• STAR-Bets: Sequential TArget-Recalculating Bets for Tighter Confidence Intervals (NeurIPS 2025 · similarity 0.86)
• Peeking with PEAK: Sequential, Nonparametric Composite Hypothesis Tests for Means of Multiple Data Streams (ICML 2024 · similarity 0.84)
• Asymptotically Log-Optimal Bayes-Assisted Confidence Sequences for Bounded Means (NeurIPS 2026 · similarity 0.83)
• A Set-Sequence Model for Time Series (NeurIPS 2026 · similarity 0.83)
• DCC: Differentiable Cardinality Constraints for Partial Index Tracking (AAAI 2025 · similarity 0.83)