Escaping Saddle Points with Compressed SGD
Not on the map. Why?
Abstract (arXiv)
Stochastic gradient descent (SGD) is a prevalent optimization technique for large-scale distributed machine learning. While SGD computation can be efficiently divided between multiple machines, communication typically becomes a bottleneck in the distributed setting. Gradient compression methods can be used to alleviate this problem, and a recent line of work shows that SGD augmented with gradient compression converges to an varepsilon-first-order stationary point. In this paper we extend these results to convergence to an varepsilon-second-order stationary point (varepsilon-SOSP), which is to the best of our knowledge the first result of this type. In addition, we show that, when the stochastic gradient is not Lipschitz, compressed SGD with RandomK compressor converges to an varepsilon-SOSP with the same number of iterations as uncompressed SGD [Jin et al.,2021] (JACM), while improving the total communication by a factor of tilde Theta(√d varepsilon-3/4), where d is the dimension of the optimization problem. We present additional results for the cases when the compressor is arbitrary and when the stochastic gradient is Lipschitz.
Key facts. Cited by 1 paper in the map (data through 7 Oct 2026). Builds on 31 of its 45 references that are in the map. First posted on arXiv 21 May 2021.
Builds on
31 of 45 references.
References · 31
- 2016Communication-Efficient Learning of Deep Networks from Decentralized Datacited by 7,592
- 2018Local SGD Converges Fast and Communicates Littlecited by 595
- 2018signSGD: Compressed Optimisation for Non-Convex Problemscited by 561
- 2018Sparsified SGD with Memorycited by 373
- 2019Error Feedback Fixes SignSGD and other Gradient Compression Schemescited by 306
- 2014Identifying and attacking the saddle point problem in high-dimensional non-convex optimizationcited by 286
- 2017How to Escape Saddle Points Efficientlycited by 284
- 2018SPIDER: Near-Optimal Non-Convex Optimization via Stochastic Path Integrated Differential Estimatorcited by 283
- 2014The Loss Surfaces of Multilayer Networkscited by 278
- 2015Escaping From Saddle Points --- Online Stochastic Gradient for Tensor Decompositioncited by 241
- 2018The Convergence of Sparsified Gradient Methodscited by 228
- 2016QSGD: Communication-Efficient SGD via Gradient Quantization and Encodingcited by 147
19 more
- 2016Matrix Completion has No Spurious Local Minimumcited by 124
- 2016A Geometric Analysis of Phase Retrievalcited by 92
- 2016Global Optimality of Local Search for Low Rank Matrix Recoverycited by 81
- 2019Communication-efficient distributed SGD with Sketchingcited by 81
- 2017Gradient Descent Can Take Exponential Time to Escape Saddle Pointscited by 74
- 2017Accelerated Gradient Descent Escapes Saddle Points Faster than Gradient Descentcited by 66
- 2017Stochastic Cubic Regularization for Fast Nonconvex Optimizationcited by 55
- 2017Natasha 2: Faster Non-Convex Optimization Than SGDcited by 49
- 2017"Convex Until Proven Guilty": Dimension-Free Acceleration of Gradient Descent on Non-Convex Functionscited by 46
- 2019Sharp Analysis for Nonconvex SGD Escaping from Saddle Pointscited by 40
- 2017Neon2: Finding Local Minima via First-Order Oraclescited by 36
- 2019Escaping from saddle points on Riemannian manifoldscited by 33
- 2017First-order Stochastic Algorithms for Escaping From Saddle Points in Almost Linear Timecited by 29
- 2018SEGA: Variance Reduction via Gradient Sketchingcited by 29
- 2016Efficient approaches for escaping higher order saddle points in non-convex optimizationcited by 23
- 2016Accelerated Methods for Non-Convex Optimizationcited by 20
- 2017A Generic Approach for Escaping Saddle pointscited by 13
- 2019Stochastic Recursive Variance-Reduced Cubic Regularization Methodscited by 12
- 2018Finding Local Minima via Stochastic Nested Variance Reductioncited by 9
Built on by
Citing papers per year: 2023: 1.
1 paper.