Simple and optimal high-probability bounds for strongly-convex stochastic gradient descent

Abstract

We consider stochastic gradient descent algorithms for minimizing a non-smooth, strongly-convex function. Several forms of this algorithm, including suffix averaging, are known to achieve the optimal $O(1/T)$ convergence rate in expectation. We consider a simple, non-uniform averaging strategy of Lacoste-Julien et al. (2011) and prove that it achieves the optimal $O(1/T)$ convergence rate with high probability. Our proof uses a recently developed generalization of Freedman's inequality. Finally, we compare several of these algorithms experimentally and show that this non-uniform averaging strategy outperforms many standard techniques, and with smaller variance.

References in corpus (1)

• Making Gradient Descent Optimal for Strongly Convex Stochastic Optimization

Cited by in corpus (6)

• On the Convergence of Adaptive Gradient Methods for Nonconvex Optimization
• A High Probability Analysis of Adaptive SGD with Momentum
• Convergence and Sample Complexity of SGD in GANs
• Minimax Optimization with Smooth Algorithmic Adversaries
• Heavy-tailed Streaming Statistical Estimation
• Analyzing and Improving the Optimization Landscape of Noise-Contrastive Estimation