April 11, 2022

Two Birds with One Coin: Convex Optimization and Confidence Sequences with Coin-Betting

Francesco Orabona, Boston University

Abstract: Consider the following two problems. The first one is calculating valid and numerically sharp confidence sequences for the unknown expectation of a bounded random variable. The second problem is optimizing an arbitrary convex function with the smallest number of accesses to its stochastic gradients. Surprisingly, we will show that both problems can be solved through a reduction to a simple gambling game: betting money on the outcomes of a coin.

First, we will explain that the problem of betting money on a coin can be solved with optimal algorithms from the universal compression/gambling literature. These algorithms guarantee an exponential growth rate of the wealth of the gambler, even without stochastic assumptions on the coin. In turn, this exponential wealth will allow us to design a reduction to obtain state-of-the-art valid confidence sequences for the expectation of bounded random variables. In particular, our confidence sequences are never vacuous, even with a single sample. Moreover, another reduction will allow us to convert the same betting algorithm into an optimal online convex optimization algorithm.

Emphasis will be given to the history of these ideas in the fields of information theory, game-theoretic probability, and online learning.