PaperlayerView exact revision on arXiv

Source-linked AI summary

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

Fabian Denoodt, Sibylle Hess, Joaquin Vanschoren, Christian A. Naesseth

arXiv:2610.03727v1stat.MLstat.ME

TL;DR

For bounded vector means, existing multivariate confidence sequences can be tight but computationally intractable, or tractable but conservative. This paper lifts betting-based sequences to vectors and develops valid tractable outer approximations of a tighter portfolio region. The approximations yield smaller regions than existing tractable alternatives and support earlier significance detection in case studies.

  • Problem

    For sequential monitoring of multiple metrics, existing multivariate confidence sequences for bounded vector means can be tight but intractable or tractable but conservative.

    Source: §1 · pp. 1–2, §3.2 · p. 4

  • Method

    The paper lifts one-dimensional betting-based confidence sequences to vectors, studies Bonferroni, max-wealth, and portfolio constructions, and derives valid tractable outer approximations of the portfolio.

    Source: §1 · p. 2, §7 · p. 10

  • Results

    The approximations produce substantially smaller regions than existing tractable alternatives, and model-comparison sequences detect an overall-accuracy improvement after about 356 batches while tractable baselines remain inconclusive after 509.

    Source: §6 · p. 9, §7 · p. 10

  • Takeaways & Limitations

    The A/B-testing and model-comparison case studies detect significance with substantially fewer observations, supporting reliable earlier decisions and reduced data-collection costs.

    Source: §7 · p. 10

    The ℓp-ellipsoid can require costly dense per-dimension grids, while intersection-volume Monte Carlo estimates become less accurate as dimension increases.

    Source: §7 · p. 10

Abstract

from arXiv · show

Modern sequential monitoring problems often involve multiple metrics, where we monitor several data streams simultaneously and may act once the evidence is strong enough. Confidence sequences (CSs) are a natural tool for such continuous monitoring. However, for bounded vector means, existing multivariate CSs are either tight but computationally intractable, or fast to compute but conservative. To address this, we study three lifts of one-dimensional betting-based CSs to higher dimensions: a weighted Bonferroni region, an equivalent max-wealth form, and a portfolio region. The portfolio is typically much tighter, especially in higher dimensions, but its boundary and properties such as volume are not available in closed form. To make this tighter construction usable, we propose tractable outer approximations of the portfolio region that preserve statistical validity: a bounding box, an $\ell_p$-ellipsoid, and their intersection. We prove set relations among all constructions and show empirically that these approximations (i) achieve regions close to the intractable portfolio, (ii) substantially outperform existing tractable multivariate CSs, and (iii) enable practical use cases such as multi-metric A/B testing and model comparison.

1 Introduction

Confidence sequences support decisions during continuous monitoring, but multivariate applications need regions that are both tight and computationally tractable. The paper lifts betting-based confidence sequences to bounded vectors and develops valid, tractable approximations of a tighter but intractable portfolio region.

1 Introduction

  • Multivariate confidence sequences must shrink rapidly enough to support early decisions while remaining tractable for real-time monitoring in moderate to high dimensions.Applications include simultaneous monitoring of website metrics and subgroup accuracies when comparing machine-learning models.Source: §1 · p. 1
  • Existing tight multivariate regions can lack closed-form solutions and incur O(tD) membership checks, while confidence spheres are easy to compute but expand and shrink all coordinates together.Whitehouse et al. [6] adapt to per-axis variance but target more general vector processes; this paper specializes to bounded observations.Source: §1 · p. 2
  • The portfolio construction averages coordinate-wise wealth processes and can be substantially tighter, but its boundary and properties such as volume are not readily available in closed form.The weighted Bonferroni hyperrectangle is easy to compute but becomes increasingly conservative as dimension grows.Source: §1 · p. 2
  • The paper derives a bounding box, an ℓp-ellipsoid, and their intersection as tractable outer approximations of the portfolio, with experiments showing smaller regions than existing tractable alternatives, especially as dimension grows.The approximations are designed to scale linearly with dimension and preserve statistical validity; case studies detect significance with substantially fewer observations.Source: §1 · p. 2
  • The paper formalizes three multivariate lifts, proves their relations, and develops practical computations for the three valid outer approximations.The lifts are a weighted Bonferroni rectangle, an equivalent max-form, and a portfolio construction.Source: §1 · p. 2

2 Background: One-Dimensional Confidence Sequences by Betting

The background sets up bounded sequential observations and defines confidence sequences through time-uniform coverage. It then uses betting-based test supermartingales and Ville’s inequality to construct valid sequences that can shrink as evidence accumulates.

2 Background: One-Dimensional Confidence Sequences by Betting

  • Observations lie in [0, 1] and have conditional mean µ at every time, a setup that also includes the classical i.i.d. case.The target mean is likewise in [0, 1].Source: §2 · p. 2
  • A confidence sequence is a sequence of sets that contains the true mean at all times with prescribed probability, and is called a (1 − α)-CS at error level α.The construction uses Ville’s inequality for supermartingales.Source: §2 · pp. 2–3
  • For a candidate mean m, a process that is a test supermartingale when m = µ yields a valid (1 − α)-CS through its sublevel set.Ville’s inequality supplies the time-uniform validity guarantee.Source: §2 · p. 3
  • The Hedged Capital Process of Waudby-Smith and Ramdas builds a test martingale at the true mean from two functions that are respectively non-increasing and non-decreasing in m.Its data-dependent stakes are described as λ+ and λ−.Source: §2 · p. 3
  • Because the wealth process is nonnegative and quasiconvex, its sublevel set is an interval computable by root finding; a conservative outer wealth process remains valid as well.The process crosses the rejection threshold 1/α to exclude incorrect candidate values from the confidence sequence.Source: §2 · p. 3

3 From One-Dimensional Confidence Intervals to Higher-Dimensional Sets

For bounded vector observations, the section formalizes three multivariate lifts: a weighted Bonferroni rectangle, its equivalent max form, and a portfolio. The portfolio is the tightest construction in the family but computationally intractable.

3.1 Bonferroni Hyperrectangle

  • Weighted Bonferroni assigns each coordinate an error level αw_d; equal weights recover the classical Bonferroni correction.This provides a straightforward multivariate confidence set from coordinate-wise wealth processes.Source: §3.1 · p. 4

3.2 Maximum of Wealth Processes

  • The equivalent max-wealth form represents the Bonferroni region and confirms its validity, but coordinate-wise screening ignores dependence and is typically conservative as D grows.The max-wealth formulation is easy to compute and defines a D-dimensional hyperrectangle.Source: §3.2 · p. 4

3.3 Portfolio Process

  • The portfolio aggregates coordinate-wise wealth and can be substantially smaller than Bonferroni, but its weighted sum does not generally preserve quasiconvexity.Its sublevel set is therefore not necessarily convex.Source: §3.3 · p. 4
  • Evaluating portfolio wealth on a grid requires N^D evaluations, motivating explicit, efficient outer approximations.The proposed approximations are designed to retain statistical validity.Source: §3.3 · p. 5

4 Approximating the Portfolio Process

The paper constructs three statistically valid outer approximations of the portfolio region: a bounding box, an ℓp-ellipsoid, and their intersection. They trade shape and computational convenience while retaining containment of the portfolio region.

4 Approximating the Portfolio Process

  • The three proposed supersets of C_port are C_bbox, C_ℓp, and C_bbox∩ℓp, allowing computation of volume and maximum width while preserving confidence-sequence validity.Each contains C_port.Source: §4 · p. 5

4.1 Bounding Box

  • The bounding box contains C_port and is contained in the max-wealth/Bonferroni region by using each other coordinate’s global minimum contribution.Its coordinate-wise intervals are tighter than the max/Bonferroni threshold.Source: §4.1 · p. 5

4.2 ℓp-Ellipsoid

  • The ℓp-ellipsoid replaces each k_d with a simpler ˜k_d to form a hyper-ellipsoid with closed-form volume; containment follows when ˜k_d≤k_d on the relevant interval.The required lower-bound condition need not hold outside the interval relevant to portfolio membership.Source: §4.2 · pp. 5–6

4.3 Intersection: Bounding Box ∩ℓp-Ellipsoid

  • C_bbox∩ℓp is the smallest proposed superset, but its volume lacks a closed form and must be estimated by hit-or-miss Monte Carlo.Using C_bbox as the sampling region rather than [0,1]^D increases the fraction of sampled points inside the target region.Source: §4.3 · p. 6
  • The intersection’s maximum width is no greater than the smaller of the bounding box’s and ℓp-ellipsoid’s maximum widths.Source: §4.3 · p. 6

5 Computing the Regions in Practice

The implementation procedures are designed to enlarge the proposed regions conservatively so they remain valid confidence sequences. Root-finding and fitted ellipsoid approximations provide tractable constructions, with a safe option for the ellipsoid.

5 Computing the Regions in Practice

  • Numerical procedures for constructing C_bbox and C_ℓp should only enlarge the proposed regions, preserving their validity as confidence sequences.Source: §5 · p. 6

5.1 A Lower Bound on the Global Minimum of k(·)

  • A small number of root-finding calls bounds the global minimum of k using roots of h(x), with the gap controlled by a preset tolerance.The procedure establishes that minimizers exist and returns explicit upper and lower bounds together with a minimizer estimate.Source: §5.1 · p. 6

5.2 Computing the Bounding Box

  • The bounding-box endpoints are computed by bisection around each estimated minimizer; three bisections per dimension yield O(D C_eval log(1/ε)) time, matching Bonferroni complexity.A positive ϵ ensures enclosure in case of flat regions, and the implemented box remains a valid outer approximation of C_port.Source: §5.2 · pp. 6–7

5.3 Computing the ℓp-Ellipsoid

  • For each candidate degree p, the ellipsoid fits per-dimension functions at two touch points, then selects the minimum-volume fit over the candidate grid.The fit is largely analytic, with a single pass over the grid after choosing the touch points and parameters.Source: §5.3 · p. 7
  • The safe ellipsoid modifies grid points to ensure ˜k_d≤k_d across the interval, guaranteeing C_port⊆C_ℓp^safe; construction costs O(D N_p N (log(L/tol)+C_eval)).The approximate variant enforces the inequality only on the grid; the safe variant provides the superset guarantee.Source: §5.3 · p. 7

6 Empirical Results

The synthetic experiments show that tractable outer approximations recover much of the portfolio’s tightness at substantially lower computational cost. In two case studies, the methods support earlier stopping for A/B testing and model comparison.

Tightness and Coverage

  • Across the synthetic settings, proposed regions have substantially smaller volumes than sphere-based baselines and per-time-step coverage closer to the 1 − α target.The comparison is shown in Figure 4.Source: §6 · p. 8, Figure 4 · p. 8

Approximation Quality

  • At D = 10, Cport’s volume is up to 50% smaller than Cbonf, while the ℓp-ellipsoid and its intersection with Cbbox approximate Cport well at lower computational cost.Cbbox is slightly smaller than Cbonf at the same computational complexity.Source: §6 · p. 8, Figure 4 · p. 8

Computational Cost

  • The outer approximations require orders of magnitude fewer evaluations than direct Cport gridding to compute volume at t = 100.Table 2 reports kd_t(·) evaluation counts; the supplied passage does not give specific counts.Source: §6 · p. 8, Table 2 · p. 9

Paired A/B-Testing Experiment of Simulated Web Metrics

  • In the simulated ten-metric A/B experiment, proposed methods stop substantially earlier than existing tractable CSs when an effect is present; ℓp-based variants stop fastest with no effect.Table 3 defines stopping for significance by an interval excluding 0 and stopping as unsubstantial when volume falls below a preset threshold.Source: §6 · p. 9, Table 3 · p. 9

Multi-metric Model Comparison Experiment

  • On the Adult dataset, Cbbox certifies an overall-accuracy improvement of 0.6%-3.7% after 356 batches, while baselines remain inconclusive through 509 batches.The six monitored metrics include overall accuracy, Brier score, and four subgroup accuracies.Source: §6 · p. 9, Figure 5 · p. 10

7 Conclusion

The paper develops tractable outer approximations to the tight but computationally intractable portfolio confidence sequence and proves relations that preserve validity. Its conclusion reports smaller, practical regions and earlier significance detection in two case studies, while noting computational and volume-estimation limitations.

7 Conclusion

  • The three portfolio outer approximations are a bounding box, an ℓp-ellipsoid, and their intersection.The portfolio is the tightest of the studied lifts but is computationally intractable.Source: §7 · p. 10
  • Cmax is equivalent to Cbonf, and Cbbox is contained in the corresponding Bonferroni region, so it can replace Cbonf at the same computational cost with an at least as tight valid sequence.Cℓp tracks Cport closely in practice and has a closed-form volume; the proposed approximations remain statistically valid after implementation.Source: §7 · p. 10
  • The proposed sequences and outer approximations yield substantially smaller regions than existing tractable alternatives while remaining practical in higher dimensions.In both A/B testing and model-comparison case studies, significance was detected after substantially fewer observations.Source: §7 · p. 10
  • The ℓp-ellipsoid can be costly with dense per-dimension discretization, and its general bound may require a dense grid to compensate for conservatism.The intersection of Cbbox and Cℓp lacks a closed-form volume, which must be estimated by Monte Carlo sampling; accuracy declines with dimension unless more samples are used.Source: §7 · p. 10

Appendix

  • The appendix presents core validity and set-relation proofs, develops both outer-approximation constructions and certified between-grid control, and provides experiments, ablations, and additional case studies.Source: Appendix · p. 13

A Proof of Prop. 3.1

The proof combines coordinate-wise test martingales into a weighted sum and uses Ville’s inequality to establish validity of a conservative outer confidence sequence.

A Proof of Prop. 3.1

B Set Relations

This section establishes set relations among confidence regions and develops tractable bounding-box and ℓ_p-ellipsoid approximations, including procedures for bounding minima and fitting the ellipsoid. It also describes ellipsoid-fitting algorithms and their handling of missing touch points and constraints near k(x) = γ.

B Set Relations

  • Under the stated assumptions, the max-wealth and weighted Bonferroni regions are equal: Cmax = Cbonf.The theorem assumes α ∈ (0, 1], fixed w ∈ ∆D, and wd > 0 for every coordinate.Source: B Set Relations · p. 14
  • Every point in Cport satisfies the coordinatewise betting-wealth bounds used to place it within the corresponding Bonferroni intervals.The passage states that for x ∈ Cport, each coordinate must satisfy kd(xd) ≤ 1/(αwd).Source: B Set Relations · pp. 15–16

C.1 Quasiconvexity of ˜k

  • For p ≥ 1 and b > 0, the stated function has convex sublevel sets and is therefore quasiconvex.The sublevel sets are empty, a singleton, or an interval depending on the threshold.Source: §C.1 · p. 16

C.2 Continuity of k(x)

  • The constructed component functions and their maximum k are continuous on [0, 1].The continuity argument extends the component definitions to the endpoints and uses finite products and the maximum of continuous functions.Source: §C.2 · pp. 16–17

D Bounding the Global Minimum of k(x)

E Bounding box

  • Coordinate projections of Cport yield intervals whose product forms an axis-aligned bounding box containing Cport.Because quasiconvex functions may have flat segments, the passage recommends using a small positive ε when finding outer solutions.Source: E Bounding box · pp. 19–20

F.1 ℓp-Ellipsoid Derivation

  • The derivation rewrites the construction as an axis-aligned ℓ_p-ellipsoid and identifies its semi-axis lengths.The set is also expressible in matrix form.Source: §F.1 · p. 20

F.2 Fitting ˜k(x) from Two Touch Points

  • Given a threshold above the minimum and two touch points flanking the optimizer, the fitting procedure determines a, b, and c, then selects p to minimize ellipsoid volume.The passage describes searching a small fixed grid of integer p candidates.Source: §F.2 · p. 21

Deriving (a, b c)

  • When k lacks a second touch point at γ + ϵ, mirroring a segment extends its domain while preserving quasiconvexity and leaving k unchanged on [0, 1].The extension is applied symmetrically for a missing left touch point; if k is monotone, the domain is mirrored left or right according to its direction.Source: Deriving (a, b c) · p. 23

F.3 Algorithms

  • FINDELLIPSOID grid-searches candidate p values, fitting one function per coordinate via touch-point search and parameter fitting; FITPARAMSATTOUCH takes O(N) time.If touch constraints are infeasible, the construction widens touch points by bisection on δ until feasible or the tolerance is reached.Source: Deriving (a, b c) · p. 22, §F.3 · pp. 23–24

F.4 Analysis of R(x) when dividing by zero

  • Near D(x) = k(x) − γ = 0, the implementation treats |D(x)| < ϵ as zero, and the analysis asks whether this can remove critical bounds on b_p and violate k(x_i) ≥ ˜k(x_i).For D(x) > 0, points impose a lower bound on b_p; for D(x) < 0, they impose an upper bound.Source: §F.4 · p. 25

F.4.1 Analytical analysis

The analysis explains how points on either side of D(x)=0 contribute feasibility bounds and argues that near-zero points can be treated as the zero case without removing finite critical bounds.

F.4.1 Analytical analysis

  • The divergent one-sided limits near the right-side root do not produce finite or active constraints.Source: §F.4.1 · p. 26
  • Points with D(x)<0 provide upper bounds on bp, whereas points with D(x)>0 provide lower bounds.Source: §F.4.1 · p. 26
  • For sufficiently small ϵ, treating points with |D(x)|<ϵ as the D(x)=0 case does not eliminate finite critical bounds on bp, and this is also validated empirically.Source: §F.4.1 · p. 26

F.4.2 Empirical analysis

The empirical analysis examines boundary behavior in the function approximation. The following sections extend the construction to distinct touch levels and establish assumptions for bounding between-grid violations.

F.4.2 Empirical analysis

  • As p increases, crucial boundary points move away from D(x) = 0, where R(x) diverges and the upper or lower bound on b_p becomes meaningless.The subregions containing these boundary points appear somewhat convex, suggesting a possible alternative to uniform-grid evaluation.Source: §F.4.2 · p. 27

F.5 Side Note - Function Approximation with Two Distinct Touch Levels

  • The extended construction kext addresses cases where the touch level γ is not attained on both sides of k’s global minimizer.For distinct touch levels, the derivation gives a quadratic construction; the parameter equations become more involved for p > 2, with no known closed-form solution.Source: §F.5 · pp. 27, 29

F.6 A bound on the Between-Grid Violation of ˜k

  • The between-grid analysis seeks a guaranteed outer approximation by bounding violations of the fitted function between grid points.Its setup assumes k and the fitted function are quasiconvex, k is continuous, and the fit lies below k at every grid point.Source: §F.6 · p. 29, §F.6.1 · p. 30

F.6.2 Error Bound when a Global Minimizer Lies on the Grid

The section derives between-grid bounds for a fitted function, first when the minimizer is on the grid and then when only a global lower bound is known. A conservative grid-value adjustment yields zero between-grid violation under the stated assumptions.

F.6.2 Error Bound when a Global Minimizer Lies on the Grid

  • When a global minimizer lies on the grid, the bound on each interval uses the endpoint nearer the minimizer: k(x_i) to its right and k(x_i+1) to its left.This follows from the monotonicity of a quasiconvex k on either side of its minimizer.Source: §F.6.2 · p. 30

F.6.3 When the Minimizer is Not a Grid Point

  • When the minimizer is not on the grid, a known global lower bound ϕ lets the method bound intervals around the grid minimum where monotonicity cannot be assumed.The other intervals use the local bound; the resulting bound is computable from grid evaluations and can guide adaptive grid refinement.Source: §F.6.3 · pp. 30–31

F.6.4 A Conservative Construction with Zero Between-Grid Violation

  • Under the stated quasiconvexity assumptions, shifting the grid values conservatively makes the bound on the maximum between-grid violation zero or less.The construction accounts for worst-case between-grid behavior by shrinking the feasible set of the fitted function.Source: §F.6.4 · pp. 31–32

G.1.1 Data and various experiment parameters.

The experiments compare the proposed regions with tractable baselines across distributions, dimensions, and significance levels. The approximations remain close to the portfolio while cumulative false exclusion stays below the nominal level in the tested settings.

G.1.1 Data and various experiment parameters.

  • The experiments include uniform-on-sphere, Bernoulli-mixture, and highly correlated data, with settings that favor different methods’ assumptions.The sphere baselines assume a global norm bound, while the proposed methods and Bounded UP require coordinate-wise bounds.Source: §G.1.1 · p. 32

G.1.2 Hedged Capital Process and Capital Stakes

  • In the reported experiments, c is set to 3/4 and the parameter θ in Eq. (3) to 1/2; all portfolio and Bonferroni weights are chosen uniformly as wd = 1/D.Source: §G.1.1 · p. 32, §G.1.2 · p. 33

G.1.3 Ellipsoid construction.

  • The ℓp-ellipsoid uses a fixed grid of N = 2001 per coordinate and selects p from {6, ..., 16}; Monte Carlo volume estimates use five runs of 25,000 samples.Sampling is restricted to a tight bounding box when possible.Source: §G.1.3 · p. 33, §G.1.4 · p. 33

G.1.6 Evaluation time.

  • At t = 100, volume evaluation excludes Cport and Bounded UP because of their exponential computational cost.The experiments use a single laptop without GPU acceleration or specialized hardware.Source: §G.1.6 · p. 33, §G.1.5 · p. 33

G.2 Small-Scale Experiments

  • The small-scale comparison includes Bounded UP because its membership-checking cost makes larger evaluations too costly.The main experiments generally use 1,000 observations, dimension D = 5 for volume-versus-time comparisons, and α = 0.05.Source: §G.1.1 · p. 32, §G.2 · p. 34, Figure 9 · p. 34

G.3 Cℓp vs Cℓpsafe

  • The safe and non-safe ellipsoid variants produce remarkably similar volumes, while the safe variant’s additional computational cost is measured in kd(·) calls.The parameter analyses vary the ellipsoid exponent and touch level, and the safe ellipsoid’s grid size.Source: §G.3 · p. 34, §G.4.1 · p. 34, Figure 11 · p. 35

G.4.2 Accuracy of Monte Carlo Volume Estimation

  • At D = 20, bounding-box sampling remains effective in the tested examples, but its accuracy deteriorates substantially by D = 50, particularly for uniform-on-sphere data.Accuracy can worsen as dimension grows because the method has no dimension-free bound on the acceptance probability; bounding-box sampling nevertheless outperforms sampling from [0, 1]^D.Source: §G.4.2 · p. 37

G.4.3 Influence on Significance Level α

  • Across α = 0.01, 0.05, and 0.10, cumulative false exclusion by t = 1000 stays below α, and the approximations remain close to the portfolio while improving substantially over tractable baselines.Relative-volume rankings are stable across significance levels.Source: §G.4.3 · p. 38, Figure 14 · p. 39, Figure 15 · p. 39

G.5 A/B-Testing Experiment: Synthetic Web Metrics

The paper tests sequential confidence sequences in simulated multi-metric A/B testing and classifier comparison. In the Adult-data experiment, hedged-capital regions detect a positive overall-accuracy gain while several baselines remain inconclusive.

G.5 A/B-Testing Experiment: Synthetic Web Metrics

  • The simulation shifts only time, clicks, scroll, and add-to-cart in the with-effect condition, while the other metrics are approximately unchanged.The ten bounded metrics are correlated through a latent engagement variable.Source: §G.5 · pp. 40–41
  • In the batch-size ablation (n ∈ {50, 100, 200, 400, 800}), relative method performance remains consistent; stopping takes 170–181 batches with an effect and 355–428 without one.Smaller batches reach the same decisions with substantially fewer users in this experiment.Source: §G.5 · p. 41

G.6 Model Comparison on Adult

  • For classifier comparison, subgroup accuracy gains are represented as ratios of joint-accuracy gains to subgroup proportions, preserving anytime validity through a deterministic transformation of a jointly valid confidence sequence.The Adult experiment also tracks overall accuracy, Brier-score improvement, and subgroup quantities.Source: §G.6 · pp. 42–44
  • On the Adult dataset, hedged-capital regions detect a positive overall-accuracy gain after roughly 356 batches, while ConfSphere, BanachSphere, and Sub-ψ remain inconclusive after all 509 batches.The figure reports intervals by method and metric; positive values favor the histogram-gradient-boosting challenger over logistic-regression baseline.Source: §G.6 · p. 44, Figure 18 · p. 45

H Additional Related Work

  • Cho et al. [14] combine wealth processes for bandit tests, whereas this paper focuses on tractable outer approximations for describing confidence-region quantities.The paper states its constructions apply to any legal stake choice.Source: H Additional Related Work · p. 45

I Broader Impacts

  • The paper presents the methods as tools that can support trustworthy decisions in online experimentation and model evaluation, while noting a risk of misuse or misinterpretation.The authors foresee no direct negative societal impacts from the methods themselves.Source: I Broader Impacts · pp. 45–46
Loading 2610.03727v1…