From low probability to high confidence in stochastic convex optimization

Abstract

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.

37 pages

References in corpus (13)

• Byzantine-Robust Distributed Learning: Towards Optimal Statistical Rates
• Geometric median and robust estimation in Banach spaces
• A Universal Catalyst for First-Order Optimization
• Loss minimization and parameter estimation with heavy tails
• Stochastic (Approximate) Proximal Point Methods: Convergence, Optimality, and Adaptivity
• The Step Decay Schedule: A Near Optimal, Geometrically Decaying Learning Rate Procedure For Least Squares
• The importance of better models in stochastic optimization
• Estimate Sequences for Stochastic Composite Optimization: Variance Reduction, Acceleration, and Robustness to Noise
• A Universally Optimal Multistage Accelerated Stochastic Gradient Method
• A Generic Acceleration Framework for Stochastic Composite Optimization
• Stagewise Training Accelerates Convergence of Testing Error Over SGD
• Accelerate Stochastic Subgradient Method by Leveraging Local Growth Condition
• Algorithms of Robust Stochastic Optimization Based on Mirror Descent Method

Cited by in corpus (5)

• Stochastic Optimization with Heavy-Tailed Noise via Accelerated Gradient Clipping
• Convergence Rates of Stochastic Gradient Descent under Infinite Noise Variance
• On the Convergence of Step Decay Step-Size for Stochastic Optimization
• Nearly Optimal Robust Method for Convex Compositional Problems with Heavy-Tailed Noise
• A termination criterion for stochastic gradient descent for binary classification