Francesco Orabona, Stony Brook University

Abstract

Stochastic subgradient descent has become the method of choice for large-scale optimization of nonsmooth convex functions. However, in order to achieve the best theoretical and practical performance, it requires to tune its parameters: the stepsizes. These stepsizes are particularly critical in the unconstrained setting, where the distance between the initial point and the optimal solution can be arbitrary large. In this talk, I will show that stochastic optimization with Lipschitz convex losses can be reduced to a game of betting on a non-stochastic coin. Betting on a non-stochastic coin is a well-known problem that can be solved using tools from information theory. Moreover, optimal parameter-free coin betting algorithms are known, giving rise to novel parameter-free stochastic optimization algorithms. This approach is very general, i.e. it works for any norm, and it gives optimal rates in a number of settings, i.e. stochastic optimization in reproducing kernel Hilbert spaces, without any parameter/stepsize to tune. Empirical results will be shown as well.