Near-Optimal Confidence Sequences for Bounded Random Variables
- URL: http://arxiv.org/abs/2006.05022v3
- Date: Thu, 3 Jun 2021 20:43:21 GMT
- Title: Near-Optimal Confidence Sequences for Bounded Random Variables
- Authors: Arun Kumar Kuchibhotla and Qinqing Zheng
- Abstract summary: 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.
- Score: 5.901337162013615
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Many inference problems, such as sequential decision problems like A/B
testing, adaptive sampling schemes like bandit selection, are often online in
nature. The fundamental problem for online inference is to provide a sequence
of confidence intervals that are valid uniformly over the growing-into-infinity
sample sizes. To address this question, we provide a near-optimal confidence
sequence for bounded random variables by utilizing Bentkus' concentration
results. We show that it improves on the existing approaches that use the
Cram{\'e}r-Chernoff technique such as the Hoeffding, Bernstein, and Bennett
inequalities. The resulting confidence sequence is confirmed to be favorable in
both synthetic coverage problems and an application to adaptive stopping
algorithms.
Related papers
- Simultaneous Inference for Local Structural Parameters with Random Forests [19.014535120129338]
We construct simultaneous confidence intervals for solutions to conditional moment equations.
We obtain several new order-explicit results on the concentration and normal approximation of high-dimensional U.S.
As a by-product, we obtain several new order-explicit results on the concentration and normal approximation of high-dimensional U.S.
arXiv Detail & Related papers (2024-05-13T15:46:11Z) - Best Arm Identification with Fixed Budget: A Large Deviation Perspective [54.305323903582845]
We present sred, a truly adaptive algorithm that can reject arms in it any round based on the observed empirical gaps between the rewards of various arms.
In particular, we present sred, a truly adaptive algorithm that can reject arms in it any round based on the observed empirical gaps between the rewards of various arms.
arXiv Detail & Related papers (2023-12-19T13:17:43Z) - Likelihood Ratio Confidence Sets for Sequential Decision Making [51.66638486226482]
We revisit the likelihood-based inference principle and propose to use likelihood ratios to construct valid confidence sequences.
Our method is especially suitable for problems with well-specified likelihoods.
We show how to provably choose the best sequence of estimators and shed light on connections to online convex optimization.
arXiv Detail & Related papers (2023-11-08T00:10:21Z) - Improved Algorithms for Stochastic Linear Bandits Using Tail Bounds for
Martingale Mixtures [26.683757807252675]
We present improved algorithms with worst-case regret guarantees for the linear bandit problem.
We show that our confidence sequences are tighter than competitors, both empirically and theoretically.
arXiv Detail & Related papers (2023-09-25T17:13:46Z) - Margin theory for the scenario-based approach to robust optimization in
high dimension [0.0]
This paper deals with the scenario approach to robust optimization.
This relies on a random sampling of the possibly infinite number of constraints induced by uncertainties in a problem.
arXiv Detail & Related papers (2023-03-07T13:33:46Z) - 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) - Optimal Clustering with Bandit Feedback [57.672609011609886]
This paper considers the problem of online clustering with bandit feedback.
It includes a novel stopping rule for sequential testing that circumvents the need to solve any NP-hard weighted clustering problem as its subroutines.
We show through extensive simulations on synthetic and real-world datasets that BOC's performance matches the lower boundally, and significantly outperforms a non-adaptive baseline algorithm.
arXiv Detail & Related papers (2022-02-09T06:05:05Z) - Open Problem: Tight Online Confidence Intervals for RKHS Elements [57.363123214464764]
We formalize the question of online confidence intervals in the RKHS setting and overview the existing results.
It is unclear whether the suboptimal regret bound is a fundamental shortcoming of these algorithms or an artifact of the proof.
arXiv Detail & Related papers (2021-10-28T22:36:20Z) - Stochastic Gradient Descent-Ascent and Consensus Optimization for Smooth
Games: Convergence Analysis under Expected Co-coercivity [49.66890309455787]
We introduce the expected co-coercivity condition, explain its benefits, and provide the first last-iterate convergence guarantees of SGDA and SCO.
We prove linear convergence of both methods to a neighborhood of the solution when they use constant step-size.
Our convergence guarantees hold under the arbitrary sampling paradigm, and we give insights into the complexity of minibatching.
arXiv Detail & Related papers (2021-06-30T18:32:46Z) - Post-Contextual-Bandit Inference [57.88785630755165]
Contextual bandit algorithms are increasingly replacing non-adaptive A/B tests in e-commerce, healthcare, and policymaking.
They can both improve outcomes for study participants and increase the chance of identifying good or even best policies.
To support credible inference on novel interventions at the end of the study, we still want to construct valid confidence intervals on average treatment effects, subgroup effects, or value of new policies.
arXiv Detail & Related papers (2021-06-01T12:01:51Z)
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.