mlsanityData to 14 Oct 2026

Projected gradient methods for nonconvex and stochastic smooth optimization: new complexities and auto-conditioned stepsizes

arXiv 2412.14291 ↗First posted 18 Dec 2024math.OC cs.LG stat.MLcited by 6

Not on the map. Why?

Abstract (arXiv)

We present a novel class of projected gradient (PG) methods for minimizing a smooth but not necessarily convex function over a convex compact set. We first provide a novel analysis of the constant-stepsize PG method, achieving the best-known iteration complexity for finding an approximate stationary point of the problem. We then develop an "auto-conditioned" projected gradient (AC-PG) variant that achieves the same iteration complexity without requiring the input of the Lipschitz constant of the gradient or any line search procedure. The key idea is to estimate the Lipschitz constant using first-order information gathered from the previous iterations, and to show that the error caused by underestimating the Lipschitz constant can be properly controlled. We then generalize the PG methods to the stochastic setting, by proposing a stochastic projected gradient (SPG) method and a variance-reduced stochastic gradient (VR-SPG) method, achieving new complexity bounds in different oracle settings. We also present auto-conditioned stepsize policies for both stochastic PG methods and establish comparable convergence guarantees.

Key facts. Cited by 6 papers in the map (data through 14 Oct 2026). Builds on 25 of its 43 references that are in the map. First posted on arXiv 18 Dec 2024.

Builds on

25 of 43 references.

References · 25

  1. 2016Optimization Methods for Large-Scale Machine Learningcited by 1,150
  2. 2019Lower Bounds for Non-Convex Stochastic Optimizationcited by 307
  3. 2019Momentum-Based Variance Reduction in Non-Convex SGDcited by 306
  4. 2018SPIDER: Near-Optimal Non-Convex Optimization via Stochastic Path Integrated Differential Estimatorcited by 287
  5. 2018Stochastic model-based minimization of weakly convex functionscited by 159
  6. 2013Mini-batch Stochastic Approximation Methods for Nonconvex Stochastic Composite Optimizationcited by 143
  7. 2016Coin Betting and Parameter-Free Online Learningcited by 133
  8. 2023DoG is SGD's Best Friend: A Parameter-Free Dynamic Step Size Schedulecited by 85
  9. 2019Adaptive Gradient Descent without Descentcited by 79
  10. 2013Accelerated Gradient Methods for Nonconvex Nonlinear and Stochastic Programmingcited by 75
  11. 2022Making SGD Parameter-Freecited by 50
  12. 2017Proximally Guided Stochastic Subgradient Method for Nonsmooth, Nonconvex Problemscited by 30
13 more
  1. 2019A Hybrid Stochastic Optimization Framework for Stochastic Composite Nonconvex Optimizationcited by 27
  2. 2023Adaptive proximal algorithms for convex optimization under local Lipschitz continuity of the gradientcited by 19
  3. 2023A simple uniformly optimal method without line search for convex optimizationcited by 18
  4. 2018Optimizing the Efficiency of First-Order Methods for Decreasing the Gradient of Smooth Convex Functionscited by 14
  5. 2020Momentum-based variance-reduced proximal stochastic gradient method for composite nonconvex stochastic optimizationcited by 14
  6. 2024Accelerated Objective Gap and Gradient Norm Convergence for Gradient Descent via Long Stepscited by 11
  7. 2023Optimal and parameter-free gradient minimization methods for convex and nonconvex optimizationcited by 8
  8. 2024AdaBB: Adaptive Barzilai-Borwein Method for Convex Optimizationcited by 8
  9. 2014Sparse Bilinear Logistic Regressioncited by 7
  10. 2024Accelerating Proximal Gradient Descent via Silver Stepsizescited by 4
  11. 2019An Average Curvature Accelerated Composite Gradient Method for Nonconvex Smooth Composite Optimization Problemscited by 2
  12. 2024Auto-conditioned primal-dual hybrid gradient method and alternating direction method of multiplierscited by 2
  13. 2021Average Curvature FISTA for Nonconvex Smooth Composite Optimization Problemscited by 1

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2025: 2; 2026: 4.

6 papers.

  1. 2025Can SGD Handle Heavy-Tailed Noise?cited by 17
  2. 2026Adaptive Lipschitz-Free Conditional Gradient Methods for Stochastic Composite Nonconvex Optimizationcited by 1
  3. 2025Quantitative Convergence Analysis of Projected Stochastic Gradient Descent for Non-Convex Losses via the Goldstein Subdifferentialcited by 0
  4. 2026Adaptive Delayed-Update Cyclic Algorithm for Variational Inequalitiescited by 0
  5. 2026Stochastic Auto-conditioned Fast Gradient Methods with Optimal Ratescited by 0
  6. 2026First-order Constrained Trilevel Optimization Over Distributed Networks for Robust Coreset Selectioncited by 0