From low probability to high confidence in stochastic convex optimization
This provides improved reliability guarantees for stochastic optimization algorithms, addressing a known bottleneck in the field, though it is incremental as it builds on existing methods like robust distance estimation and the proximal point method.
The paper tackles the problem of obtaining high-confidence guarantees in stochastic convex optimization, showing that a wide class of algorithms can be augmented to achieve such bounds with only logarithmic overhead in confidence level and polylogarithmic overhead in condition number.
Standard results in stochastic convex optimization bound the number of samples that an algorithm needs to generate a point with small function value in expectation. More nuanced high probability guarantees are rare, and typically either rely on "light-tail" noise assumptions or exhibit worse sample complexity. In this work, we show that a wide class of stochastic optimization algorithms for strongly convex problems can be augmented with high confidence bounds at an overhead cost that is only logarithmic in the confidence level and polylogarithmic in the condition number. The procedure we propose, called proxBoost, is elementary and builds on two well-known ingredients: robust distance estimation and the proximal point method. We discuss consequences for both streaming (online) algorithms and offline algorithms based on empirical risk minimization.