mlsanityData to 7 Oct 2026

Non-convex Finite-Sum Optimization Via SCSG Methods

arXiv 1706.09156 ↗First posted 28 Jun 2017math.OC cs.CCcited by 61

Not on the map. Why?

Abstract (arXiv)

We develop a class of algorithms, as variants of the stochastically controlled stochastic gradient (SCSG) methods (Lei and Jordan, 2016), for the smooth non-convex finite-sum optimization problem. Assuming the smoothness of each component, the complexity of SCSG to reach a stationary point with mathbbE |nabla f(x)|2≤ ε is Oleft (minε-5/3, ε-1n2/3right), which strictly outperforms the stochastic gradient descent. Moreover, SCSG is never worse than the state-of-the-art methods based on variance reduction and it significantly outperforms them when the target accuracy is low. A similar acceleration is also achieved when the functions satisfy the Polyak-Lojasiewicz condition. Empirical experiments demonstrate that SCSG outperforms stochastic gradient methods on training multi-layers neural networks in terms of both training and validation loss.

Key facts. Cited by 61 papers in the map (data through 7 Oct 2026). First posted on arXiv 28 Jun 2017.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 17; 2022: 18; 2023: 10; 2024: 11; 2025: 3; 2026: 2.

61 papers.

Sort:

By area:

  1. 2023Convergence of Adam Under Relaxed Assumptionscited by 97
  2. 2022FedVARP: Tackling the Variance Due to Partial Client Participation in Federated Learningcited by 62
  3. 2021Fault-Tolerant Federated Reinforcement Learning with Theoretical Guaranteecited by 52
  4. 2021Bias-Variance Reduced Local SGD for Less Heterogeneous Federated Learningcited by 30
  5. 2021Private Federated Learning Without a Trusted Server: Optimal Algorithms for Convex Lossescited by 30
  6. 2021ZeroSARAH: Efficient Nonconvex Finite-Sum Optimization with Zero Full Gradient Computationcited by 28
  7. 2022Private Non-Convex Federated Learning Without a Trusted Servercited by 26
  8. 2023Variance-reduced Clipping for Non-convex Optimizationcited by 22
  9. 2021FedPAGE: A Fast Local Stochastic Gradient Method for Communication-Efficient Federated Learningcited by 19
  10. 2022Stochastic Halpern Iteration with Variance Reduction for Stochastic Monotone Inclusionscited by 17
  11. 2021DESTRESS: Computation-Optimal and Communication-Efficient Decentralized Nonconvex Finite-Sum Optimizationcited by 16
  12. 2022Stochastic Differentially Private and Fair Learningcited by 16
38 more
  1. 2022Anchor Sampling for Federated Learning with Partial Client Participationcited by 14
  2. 2021Variance Reduced Training with Stratified Sampling for Forecasting Modelscited by 13
  3. 2024Efficient Sign-Based Optimization: Accelerating Convergence via Variance Reductioncited by 13
  4. 2022Optimization with Access to Auxiliary Informationcited by 12
  5. 2023Knowledge Distillation Performs Partial Variance Reductioncited by 11
  6. 2025Complexity of normalized stochastic first-order methods with momentum under heavy-tailed noisecited by 11
  7. 2023Stochastic Approximation Beyond Gradient for Signal Processing and Machine Learningcited by 10
  8. 2021ANITA: An Optimal Loopless Accelerated Variance-Reduced Gradient Methodcited by 9
  9. 2022Sharper Rates and Flexible Framework for Nonconvex SGD with Client and Data Samplingcited by 9
  10. 2022Cyclic Block Coordinate Descent With Variance Reduction for Composite Nonconvex Optimizationcited by 9
  11. 2021GT-STORM: Taming Sample, Communication, and Memory Complexities in Decentralized Non-Convex Learningcited by 8
  12. 2021Escaping Saddle Points Faster with Stochastic Momentumcited by 8
  13. 2023A Coefficient Makes SVRG Effectivecited by 7
  14. 2024On the Convergence of Continual Learning with Adaptive Methodscited by 7
  15. 2021The Minimax Complexity of Distributed Optimizationcited by 6
  16. 2022Zeroth-Order Negative Curvature Finding: Escaping Saddle Points without Gradientscited by 6
  17. 2022Stochastic Gradient Methods with Preconditioned Updatescited by 5
  18. 2022Simple and Optimal Stochastic Gradient Methods for Nonsmooth Nonconvex Optimizationcited by 5
  19. 2022META-STORM: Generalized Fully-Adaptive Variance Reduced SGD for Unbounded Functionscited by 5
  20. 2024FedStale: leveraging stale client updates in federated learningcited by 5
  21. 2024Freya PAGE: First Optimal Time Complexity for Large-Scale Nonconvex Finite-Sum Optimization with Heterogeneous Asynchronous Computationscited by 5
  22. 2021STORM+: Fully Adaptive SGD with Momentum for Nonconvex Optimizationcited by 4
  23. 2022Differentially Private Deep Learning with ModelMixcited by 4
  24. 2024Faster Algorithms for User-Level Private Stochastic Convex Optimizationcited by 4
  25. 2022An Adaptive Gradient Method with Energy and Momentumcited by 3
  26. 2023Accelerated Cyclic Coordinate Dual Averaging with Extrapolation for Composite Convex Optimizationcited by 3
  27. 2023Convergence of stochastic gradient descent under a local Lojasiewicz condition for deep neural networkscited by 3
  28. 2021A Variance Controlled Stochastic Method with Biased Estimation for Faster Non-convex Optimizationcited by 2
  29. 2022Tackling benign nonconvexity with smoothing and stochastic gradientscited by 2
  30. 2023Stochastic Optimization for Non-convex Problem with Inexact Hessian Matrix, Gradient, and Functioncited by 2
  31. 2023Convergence of Sign-based Random Reshuffling Algorithms for Nonconvex Optimizationcited by 2
  32. 2024Probabilistic Guarantees of Stochastic Recursive Gradient in Non-Convex Finite Sum Problemscited by 2
  33. 2024On the Complexity of Finite-Sum Smooth Optimization under the Polyak-Lojasiewicz Conditioncited by 2
  34. 2024An Effective Dynamic Gradient Calibration Method for Continual Learningcited by 2
  35. 2026Lower Bounds and Proximally Anchored SGD for Non-Convex Minimization Under Unbounded Variancecited by 2
  36. 2021On the Oracle Complexity of Higher-Order Smooth Non-Convex Finite-Sum Optimizationcited by 1
  37. 2021Faster Perturbed Stochastic Gradient Methods for Finding Local Minimacited by 1
  38. 2022A PDE-based Explanation of Extreme Numerical Sensitivities and Edge of Stability in Training Neural Networkscited by 1

50 most cited of 61 All 61 (JSON)