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 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.
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 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.
Bio:
Kwang-Sung Jun is an assistant professor in the Department of Computer Science at the University of Arizona, starting in 2019. His research interest is interactive machine learning, especially bandit problems, online learning, and confidence bounds. Before joining UA, he was a postdoc at Boston University with Dr. Francesco Orabona. Before that, he was at the University of Wisconsin-Madison for a PhD degree with Dr. Xiaojin (Jerry) Zhu and a postdoc with Drs. Robert Nowak, Rebecca Willett, and Stephen Wright.
October 23, 2024
12:30 pm (1h)
Discovery Building, Orchard View Room
Kwang-Sung Jun, University of Arizona