Quantitative Convergence Analysis of Projected Stochastic Gradient Descent for Non-Convex Losses via the Goldstein Subdifferential
Not on the map. Why?
Abstract (arXiv)
Stochastic gradient descent (SGD) is the main algorithm behind a large body of work in machine learning. In many cases, constraints are enforced via projections, leading to projected stochastic gradient algorithms. In recent years, a large body of work has examined the convergence properties of projected SGD for non-convex losses in asymptotic and non-asymptotic settings. Strong quantitative guarantees are available for convergence measured via Moreau envelopes. However, these results cannot be compared directly with work on unconstrained SGD, since the Moreau envelope construction changes the gradient. Other common measures based on gradient mappings have the limitation that convergence can only be guaranteed if variance reduction methods, such as mini-batching, are employed. This paper presents an analysis of projected SGD for non-convex losses over compact convex sets. Convergence is measured via the distance of the gradient to the Goldstein subdifferential generated by the constraints. Our proposed convergence criterion directly reduces to commonly used criteria in the unconstrained case, and we obtain convergence without requiring variance reduction. We obtain results for data that are independent, identically distributed (IID) or satisfy mixing conditions (L-mixing). In these cases, we derive asymptotic convergence and O(N-1/3) non-asymptotic bounds in expectation, where N is the number of steps. In the case of IID sub-Gaussian data, we obtain almost-sure asymptotic convergence and high-probability non-asymptotic O(N-1/5) bounds. In particular, these are the first non-asymptotic high-probability bounds for projected SGD with non-convex losses.
Key facts. No citing papers in the map yet (data through 14 Oct 2026). Builds on 42 of its 75 references that are in the map. First posted on arXiv 3 Oct 2025.
Builds on
42 of 75 references.
References · 42
- 2021Convex optimizationcited by 2,515
- 2016Optimization Methods for Large-Scale Machine Learningcited by 1,150
- 2019Introduction to Online Convex Optimizationcited by 803
- 2014Convex Optimization: Algorithms and Complexitycited by 575
- 2023Handbook of Convergence Theorems for (Stochastic) Gradient Methodscited by 163
- 2018Stochastic model-based minimization of weakly convex functionscited by 159
- 2020Better Theory for SGD in the Nonconvex Worldcited by 158
- 2013Mini-batch Stochastic Approximation Methods for Nonconvex Stochastic Composite Optimizationcited by 143
- 2018Stochastic subgradient method converges on tame functionscited by 124
- 2019Global Convergence of Policy Gradient Methods to (Almost) Locally Optimal Policiescited by 124
- 2020A Finite Time Analysis of Two Time-Scale Actor Critic Methodscited by 122
- 2021A general sample complexity analysis of vanilla policy gradientcited by 76
30 more
- 2020SGD for Structured Nonconvex Functions: Learning Rates, Minibatching and Interpolationcited by 67
- 2016Convergence Rate of Frank-Wolfe for Non-Convex Objectivescited by 63
- 2018Stochastic (Approximate) Proximal Point Methods: Convergence, Optimality, and Adaptivitycited by 61
- 2017Stochastic Methods for Composite and Weakly Convex Optimization Problemscited by 48
- 2019Stochastic Gradient Descent for Nonconvex Learning without Bounded Gradient Assumptionscited by 48
- 2016Stochastic Frank-Wolfe Methods for Nonconvex Optimizationcited by 41
- 2021A gradient sampling method with complexity guarantees for Lipschitz functions in high and low dimensionscited by 39
- 2020Projected Stochastic Gradient Langevin Algorithms for Constrained Sampling and Non-Convex Learningcited by 33
- 2019The importance of better models in stochastic optimizationcited by 32
- 2022Finite-time analysis of single-timescale actor-criticcited by 32
- 2020Convergence of constant step stochastic gradient descent for non-smooth non-convex functionscited by 27
- 2018Analysis of nonsmooth stochastic approximation: the differential inclusion approachcited by 23
- 2018On stochastic gradient Langevin dynamics with dependent data streams in the logconcave casecited by 20
- 2025Can SGD Handle Heavy-Tailed Noise?cited by 17
- 2023Complexity of Single Loop Algorithms for Nonlinear Programming with Stochastic Objective and Constraintscited by 16
- 2022A Unified Convergence Theorem for Stochastic Optimization Methodscited by 12
- 2021Minibatch and Momentum Model-based Methods for Stochastic Weakly Convex Optimizationcited by 10
- 2022Convergence of First-Order Methods for Constrained Nonconvex Optimization with Dependent Datacited by 7
- 2020Convergence of adaptive algorithms for weakly convex constrained optimizationcited by 6
- 2022Constrained Langevin Algorithms with L-mixing External Random Variablescited by 6
- 2024Projected gradient methods for nonconvex and stochastic smooth optimization: new complexities and auto-conditioned stepsizescited by 6
- 2020Stochastic optimization over proximally smooth setscited by 4
- 2024Proximal random reshuffling under local Lipschitz continuitycited by 4
- 2019Error bound conditions and convergence of optimization methods on smooth and proximally smooth manifoldscited by 3
- 2024Stochastic Weakly Convex Optimization Beyond Lipschitz Continuitycited by 3
- 2024Projected gradient descent accumulates at Bouligand stationary pointscited by 3
- 2023A Unified Analysis on the Subgradient Upper Bounds for the Subgradient Methods Minimizing Composite Nonconvex, Nonsmooth and Non-Lipschitz Functionscited by 2
- 2025Convergence of projected stochastic approximation algorithmcited by 2
- 2023Full-Low Evaluation Methods For Bound and Linearly Constrained Derivative-Free Optimizationcited by 1
- 2025On Tackling High-Dimensional Nonconvex Stochastic Optimization via Stochastic First-Order Methods with Non-smooth Proximal Terms and Variance Reductioncited by 1
Built on by
Not cited yet.