Huber-Robust Confidence Sequences
- URL: http://arxiv.org/abs/2301.09573v1
- Date: Mon, 23 Jan 2023 17:29:26 GMT
- Title: Huber-Robust Confidence Sequences
- Authors: Hongjian Wang, Aaditya Ramdas
- Abstract summary: 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.
- Score: 37.16361789841549
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Confidence sequences are confidence intervals that can be sequentially
tracked, and are valid at arbitrary data-dependent stopping times. This paper
presents confidence sequences for a univariate mean of an unknown distribution
with a known upper bound on the p-th central moment (p > 1), but allowing for
(at most) {\epsilon} fraction of arbitrary distribution corruption, as in
Huber's contamination model. We do this by designing new robust exponential
supermartingales, and show that the resulting confidence sequences attain the
optimal width achieved in the nonsequential setting. Perhaps surprisingly, the
constant margin between our sequential result and the lower bound is smaller
than even fixed-time robust confidence intervals based on the trimmed mean, for
example. 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.
Related papers
- Revisiting Confidence Estimation: Towards Reliable Failure Prediction [53.79160907725975]
We find a general, widely existing but actually-neglected phenomenon that most confidence estimation methods are harmful for detecting misclassification errors.
We propose to enlarge the confidence gap by finding flat minima, which yields state-of-the-art failure prediction performance.
arXiv Detail & Related papers (2024-03-05T11:44:14Z) - 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) - Binary Classification with Confidence Difference [100.08818204756093]
This paper delves into a novel weakly supervised binary classification problem called confidence-difference (ConfDiff) classification.
We propose a risk-consistent approach to tackle this problem and show that the estimation error bound the optimal convergence rate.
We also introduce a risk correction approach to mitigate overfitting problems, whose consistency and convergence rate are also proven.
arXiv Detail & Related papers (2023-10-09T11:44:50Z) - 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) - Simple Buehler-optimal confidence intervals on the average success
probability of independent Bernoulli trials [0.0]
One-sided confidence intervals are presented for the average of non-identical Bernoulli parameters.
A simple interval valid for all confidence levels is also provided with a tightness guarantee.
arXiv Detail & Related papers (2022-12-23T19:22:51Z) - Catoni-style Confidence Sequences under Infinite Variance [19.61346221428679]
We provide an extension of confidence sequences for settings where the variance of the data-generating distribution does not exist or is infinite.
Confidence sequences furnish confidence intervals that are valid at arbitrary data-dependent stopping times.
The derived results are shown to better than confidence sequences obtained using Dubins-Savage inequality.
arXiv Detail & Related papers (2022-08-05T14:11:06Z) - 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) - Off-policy Confidence Sequences [33.749904615295485]
We develop confidence bounds that hold uniformly over time for off-policy evaluation in the contextual bandit setting.
We provide algorithms for computing these confidence sequences that strike a good balance between computational and statistical efficiency.
arXiv Detail & Related papers (2021-02-18T18:40:30Z) - Distribution-free binary classification: prediction sets, confidence
intervals and calibration [106.50279469344937]
We study three notions of uncertainty quantification -- calibration, confidence intervals and prediction sets -- for binary classification in the distribution-free setting.
We derive confidence intervals for binned probabilities for both fixed-width and uniform-mass binning.
As a consequence of our 'tripod' theorems, these confidence intervals for binned probabilities lead to distribution-free calibration.
arXiv Detail & Related papers (2020-06-18T14:17:29Z) - 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.