STaR-Bets: Sequential Target-Recalculating Bets for Tighter Confidence Intervals

• URL: http://arxiv.org/abs/2505.22422v1
• Date: Wed, 28 May 2025 14:48:07 GMT
• Title: STaR-Bets: Sequential Target-Recalculating Bets for Tighter Confidence Intervals
• Authors: Václav Voráček, Francesco Orabona,
• Abstract summary: We propose a betting-based algorithm to compute confidence intervals that empirically outperforms the competitors.<n>Our strategy uses the optimal strategy in every step, whereas the standard betting methods choose a constant strategy in advance.<n>We also prove that the width of our confidence intervals is optimal up to an $1+o(1)$ factor diminishing with $n$.
• Score: 9.319818839579137
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: The construction of confidence intervals for the mean of a bounded random variable is a classical problem in statistics with numerous applications in machine learning and virtually all scientific fields. In particular, obtaining the tightest possible confidence intervals is vital every time the sampling of the random variables is expensive. The current state-of-the-art method to construct confidence intervals is by using betting algorithms. This is a very successful approach for deriving optimal confidence sequences, even matching the rate of law of iterated logarithms. However, in the fixed horizon setting, these approaches are either sub-optimal or based on heuristic solutions with strong empirical performance but without a finite-time guarantee. Hence, no betting-based algorithm guaranteeing the optimal $\mathcal{O}(\sqrt{\frac{\sigma^2\log\frac1\delta}{n}})$ width of the confidence intervals are known. This work bridges this gap. We propose a betting-based algorithm to compute confidence intervals that empirically outperforms the competitors. Our betting strategy uses the optimal strategy in every step (in a certain sense), whereas the standard betting methods choose a constant strategy in advance. Leveraging this fact results in strict improvements even for classical concentration inequalities, such as the ones of Hoeffding or Bernstein. Moreover, we also prove that the width of our confidence intervals is optimal up to an $1+o(1)$ factor diminishing with $n$. The code is available on~https://github.com/vvoracek/STaR-bets-confidence-interval.

Related papers

• Asymptotically Optimal Linear Best Feasible Arm Identification with Fixed Budget [55.938644481736446]
  We introduce a novel algorithm for best feasible arm identification that guarantees an exponential decay in the error probability.<n>We validate our algorithm through comprehensive empirical evaluations across various problem instances with different levels of complexity.
  arXiv  Detail & Related papers  (2025-06-03T02:56:26Z)
• Learning the Optimal Stopping for Early Classification within Finite Horizons via Sequential Probability Ratio Test [11.199585259018459]
  Time-sensitive machine learning benefits from Sequential Probability Ratio Test (SPRT), which provides an optimal stopping time for early classification of time series.<n>In finite horizon scenarios, where input lengths are finite, determining the optimal stopping rule becomes computationally intensive due to the need for backward induction.<n>We introduce FIRMBOUND, an SPRT-based framework that efficiently estimates the solution to backward induction from training data.
  arXiv  Detail & Related papers  (2025-01-29T23:54:46Z)
• Tighter Confidence Bounds for Sequential Kernel Regression [3.683202928838613]
  We use martingale tail inequalities to establish new confidence bounds for sequential kernel regression. Our confidence bounds can be computed by solving a conic program, although this bare version quickly becomes impractical. We find that when our confidence bounds replace existing ones, the KernelUCB algorithm has better empirical performance, a matching worst-case performance guarantee and comparable computational cost.
  arXiv  Detail & Related papers  (2024-03-19T13:47:35Z)
• High Confidence Level Inference is Almost Free using Parallel Stochastic Optimization [16.38026811561888]
  This paper introduces a novel inference method focused on constructing confidence intervals with efficient computation and fast convergence to the nominal level. Our method requires minimal additional computation and memory beyond the standard updating of estimates, making the inference process almost cost-free.
  arXiv  Detail & Related papers  (2024-01-17T17:11:45Z)
• Show Your Work with Confidence: Confidence Bands for Tuning Curves [51.12106543561089]
  tuning curves plot validation performance as a function of tuning effort. We present the first method to construct valid confidence bands for tuning curves. We validate our design with ablations, analyze the effect of sample size, and provide guidance on comparing models with our method.
  arXiv  Detail & Related papers  (2023-11-16T00:50:37Z)
• Huber-Robust Confidence Sequences [37.16361789841549]
  Confidence sequences are confidence intervals that can be sequentially tracked, and are valid at arbitrary data-dependent stopping times. We show that the resulting confidence sequences attain the optimal width achieved in the nonsequential setting. Since confidence sequences are a common tool used within A/B/n testing and bandits, these results open the door to sequential experimentation that is robust to outliers and adversarial corruptions.
  arXiv  Detail & Related papers  (2023-01-23T17:29:26Z)
• Mean-based Best Arm Identification in Stochastic Bandits under Reward Contamination [80.53485617514707]
  This paper proposes two algorithms, a gap-based algorithm and one based on the successive elimination, for best arm identification in sub-Gaussian bandits. Specifically, for the gap-based algorithm, the sample complexity is optimal up to constant factors, while for the successive elimination, it is optimal up to logarithmic factors.
  arXiv  Detail & Related papers  (2021-11-14T21:49:58Z)
• Tight Concentrations and Confidence Sequences from the Regret of Universal Portfolio [30.750408480772027]
  Jun and Orabona [COLT'19] have shown how to easily convert the regret guarantee of an online betting algorithm into a time-uniform concentration inequality. We show that we can go even further: We show that the regret of a minimax betting algorithm gives rise to a new implicit empirical time-uniform concentration.
  arXiv  Detail & Related papers  (2021-10-27T00:44:32Z)
• High Probability Complexity Bounds for Non-Smooth Stochastic Optimization with Heavy-Tailed Noise [51.31435087414348]
  It is essential to theoretically guarantee that algorithms provide small objective residual with high probability. Existing methods for non-smooth convex optimization have complexity bounds with dependence on confidence level. We propose novel stepsize rules for two methods with gradient clipping.
  arXiv  Detail & Related papers  (2021-06-10T17:54:21Z)
• Byzantine-Resilient Non-Convex Stochastic Gradient Descent [61.6382287971982]
  adversary-resilient distributed optimization, in which. machines can independently compute gradients, and cooperate. Our algorithm is based on a new concentration technique, and its sample complexity. It is very practical: it improves upon the performance of all prior methods when no. setting machines are present.
  arXiv  Detail & Related papers  (2020-12-28T17:19:32Z)
• CoinDICE: Off-Policy Confidence Interval Estimation [107.86876722777535]
  We study high-confidence behavior-agnostic off-policy evaluation in reinforcement learning. We show in a variety of benchmarks that the confidence interval estimates are tighter and more accurate than existing methods.
  arXiv  Detail & Related papers  (2020-10-22T12:39:11Z)
• Near-Optimal Confidence Sequences for Bounded Random Variables [5.901337162013615]
  A fundamental problem for online inference is to provide a sequence of confidence intervals that are valid uniformly over the growing-into-infinity sample sizes. We provide a near-optimal confidence sequence for bounded random variables by utilizing Bentkus' concentration results. The resulting confidence sequence is confirmed to be favorable in both synthetic coverage problems and an application to adaptive stopping algorithms.
  arXiv  Detail & Related papers  (2020-06-09T02:50:01Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.