Session: Interplay between Online Convex Optimization and Statistics
Chair: Jun-Kun Wang
Cluster: Optimization For Data Science
Talk 1: On the near-optimality of betting confidence sets for bounded means
Speaker: Shubhanshu Shekhar
Abstract: Constructing nonasymptotic confidence intervals (CIs) for the mean of a univariate distribution from independent and identically distributed (i.i.d.) observations is a fundamental task in statistics. For bounded observations, a classical nonparametric approach proceeds by inverting standard concentration bounds, such as Hoeffding's or Bernstein's inequalities. Recently, an alternative betting-based approach for defining CIs and their time-uniform variants called confidence sequences (CSs), has been shown to be empirically superior to the classical methods. In this paper, we provide theoretical justification for this improved empirical performance of betting CIs and CSs. Our main contributions are as follows: (i) We first compare CIs using the values of their first-order asymptotic widths (scaled by ), and show that the betting CI of Waudby-Smith and Ramdas (2023) has a smaller limiting width than existing empirical Bernstein (EB)-CIs. (ii) Next, we establish two lower bounds that characterize the minimum width achievable by any method for constructing CIs/CSs in terms of certain inverse information projections. (iii) Finally, we show that the betting CI and CS match the fundamental limits, modulo an additive logarithmic term and a multiplicative constant. Overall these results imply that the betting CI~(and CS) admit stronger theoretical guarantees than the existing state-of-the-art EB-CI~(and CS); both in the asymptotic and finite-sample regimes.
Talk 2: Confidence sequences via online learning
Speaker: Kwang-Sung Jun
Abstract: Confidence sequence provides ways to characterize uncertainty in stochastic environments, which is a widely-used tool for interactive machine learning algorithms and statistical problems including A/B testing, Bayesian optimization, reinforcement learning, and offline evaluation/learning. In these problems, constructing confidence sequences that are tight without losing correctness is crucial since it has a dramatic impact on the performance of downstream tasks. In this talk, I will present how to leverage results from online learning to derive confidence sequences that are provably and numerically tight. First, I will present an implicitly-defined confidence sequence for bounded random variables, which induces an empirical Bernstein-style confidence bound (thus adapts to the variance) and is provably better than the KL divergence-based confidence bound simultaneously, unlike the standard empirical Bernstein bound. Our confidence bound is never vacuous, can be efficiently computed, and provides state-of-the-art numerical performance. Second, I will turn to generalized linear models and how leveraging online learning helps develop (i) improved confidence sets for logistic linear models and (ii) noise-adaptive confidence sets for linear models with sub-Gaussian and bounded noise respectively. These lead to improved regret bounds in (generalized) linear bandit problems. I will conclude with open problems in confidence sequences and the role that online learning plays for them.
Talk 3: Sequential Hypothesis Testing via Online Learning and Optimization
Speaker: Jun-Kun Wang
Abstract: Online convex optimization (a.k.a. no-regret learning) concerns a scenario where an online learner commits to a point at each round before receiving the loss function. The learner's goal is to minimize the regret, defined as the gap between the cumulative losses and that of a clairvoyant who knows the sequence of the loss functions in advance. In this talk, I will first review a very neat known result in the literature that casts non-parametric sequential hypothesis testing as an online convex optimization problem, where an online learner tries to bet whether the null hypothesis is true or false, and a tighter regret bound suggests a faster stopping time to reject the null when the alternative is true. Then, I will show the relevant techniques can be used to design algorithms with strong statistical guarantees with applications such as online detecting LLM-generated texts, auditing fairness, and detecting distribution shifts. After that, I will introduce a new algorithm that overcomes the limitations of the existing methods and potentially leads to a faster rejection time under the alternative while controlling the false positive rate.
