From low probability to high confidence in stochastic convex optimization
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.
Code (0)
등록된 구현이 없습니다.
Tasks
Stochastic OptimizationVocal Bursts Intensity PredictionSimilar Papers 제목 키워드 기반
High Probability Complexity Bounds for Non-Smooth Stochastic Optimization with Heavy-Tailed Noise
Stochastic first-order methods are standard for training large-scale machine learning models. Random behavior may cause a particular run of an algorithm to result in a highly suboptimal objective value, whereas theoretic…
Stochastic OptimizationNoise-Adaptive High-Probability Regret Bounds for Online Convex Optimization
We study high-probability regret bounds for online convex optimization (OCO) with strongly convex losses and establish three results that resolve open questions at the intersection of noise adaptivity, feedback structure…
Nearly Optimal Robust Method for Convex Compositional Problems with Heavy-Tailed Noise
In this paper, we propose robust stochastic algorithms for solving convex compositional problems of the form $f(\E_\xi g(\cdot; \xi)) + r(\cdot)$ by establishing {\bf sub-Gaussian confidence bounds} under weak assumption…
Gradient Clipping Helps in Non-Smooth Stochastic Optimization with Heavy-Tailed Noise
Thanks to their practical efficiency and random nature of the data, stochastic first-order methods are standard for training large-scale machine learning models. Random behavior may cause a particular run of an algorithm…
Stochastic OptimizationStochastic Non-convex Optimization with Strong High Probability Second-order Convergence
In this paper, we study stochastic non-convex optimization with non-convex random functions. Recent studies on non-convex optimization revolve around establishing second-order convergence, i.e., converging to a nearly se…
Vocal Bursts Intensity Prediction