How To Make the Gradients Small Stochastically: Even Faster Convex and Nonconvex SGD

Abstract

Stochastic gradient descent (SGD) gives an optimal convergence rate when minimizing convex stochastic objectives $f(x)$. However, in terms of making the gradients small, the original SGD does not give an optimal rate, even when $f(x)$ is convex. If $f(x)$ is convex, to find a point with gradient norm $\epsilon$, we design an algorithm SGD3 with a near-optimal rate $\tilde{O}({\epsilon }^{-2})$, improving the best known rate $O({\epsilon }^{-8/3})$ of [18]. If $f(x)$ is nonconvex, to find its $\epsilon$-approximate local minimum, we design an algorithm SGD5 with rate $\tilde{O}({\epsilon }^{-3.5})$, where previously SGD variants only achieve $\tilde{O}({\epsilon }^{-4})$ [6, 15, 33]. This is no slower than the best known stochastic version of Newton's method in all parameter regimes [30].

V2 added two applications to nonconvex stochastic optimization, and V3 corrects a citation. arXiv admin note: text overlap with arXiv:1708.08694

Cited by in corpus (22)

• Federated Optimization in Heterogeneous Networks
• On the Convergence of Adaptive Gradient Methods for Nonconvex Optimization
• Universal gradient descent
• Sharp Analysis for Nonconvex SGD Escaping from Saddle Points
• Optimizing the Efficiency of First-Order Methods for Decreasing the Gradient of Smooth Convex Functions
• The Complexity of Making the Gradient Small in Stochastic Convex Optimization
• Complexity of Finding Stationary Points of Nonsmooth Nonconvex Functions
• A Second look at Exponential and Cosine Step Sizes: Simplicity, Adaptivity, and Performance
• The Complexity of Finding Stationary Points with Stochastic Gradient Descent
• The Complexity of Nonconvex-Strongly-Concave Minimax Optimization
• Distributed Stochastic Algorithms for High-rate Streaming Principal Component Analysis
• On the Convergence of Stochastic Gradient Descent with Bandwidth-based Step Size
• Adaptive Step Sizes in Variance Reduction via Regularization
• Stagewise Enlargement of Batch Size for SGD-based Learning
• Second-Order Information in Non-Convex Stochastic Optimization: Power and Limitations
• Machine Unlearning via Algorithmic Stability
• Optimal Complexity in Decentralized Training
• Dual Averaging is Surprisingly Effective for Deep Learning Optimization
• Practical Schemes for Finding Near-Stationary Points of Convex Finite-Sums
• Multiplicative Weights Update as a Distributed Constrained Optimization Algorithm: Convergence to Second-order Stationary Points Almost Always
• On the Convergence of Memory-Based Distributed SGD
• On The Convergence of First Order Methods for Quasar-Convex Optimization