mlsanityData to 14 Oct 2026

A Normal Map-Based Proximal Stochastic Gradient Method: Convergence and Identification Properties

arXiv 2305.05828 ↗First posted 10 May 2023math.OC cs.LGcited by 5

Not on the map. Why?

Abstract (arXiv)

The proximal stochastic gradient method (PSGD) is one of the state-of-the-art approaches for stochastic composite-type problems. In contrast to its deterministic counterpart, PSGD has been found to have difficulties with the correct identification of underlying substructures (such as supports, low rank patterns, or active constraints) and it does not possess a finite-time manifold identification property. Existing solutions rely on convexity assumptions or on the additional usage of variance reduction techniques. In this paper, we address these limitations and present a simple variant of PSGD based on Robinson's normal map. The proposed normal map-based proximal stochastic gradient method (NSGD) is shown to converge globally, i.e., accumulation points of the generated iterates correspond to stationary points almost surely. In addition, we establish complexity bounds for NSGD that match the known results for PSGD and we prove that NSGD can almost surely identify active manifolds in finite-time in a general nonconvex setting. Our derivations are built on almost sure iterate convergence guarantees and utilize analysis techniques based on the Kurdyka-Lojasiewicz inequality.

Key facts. Cited by 5 papers in the map (data through 14 Oct 2026). Builds on 28 of its 90 references that are in the map. First posted on arXiv 10 May 2023.

Builds on

28 of 90 references.

References · 28

  1. 2016Optimization Methods for Large-Scale Machine Learningcited by 1,150
  2. 2019Momentum-Based Variance Reduction in Non-Convex SGDcited by 306
  3. 2018Stochastic model-based minimization of weakly convex functionscited by 159
  4. 2013Mini-batch Stochastic Approximation Methods for Nonconvex Stochastic Composite Optimizationcited by 143
  5. 2018Stochastic subgradient method converges on tame functionscited by 124
  6. 2014A Proximal Stochastic Gradient Method with Progressive Variance Reductioncited by 78
  7. 2016Error bounds, quadratic growth, and linear convergence of proximal methodscited by 60
  8. 2016Efficiency of minimizing compositions of convex functions and smooth mapscited by 59
  9. 2017Stochastic Methods for Composite and Weakly Convex Optimization Problemscited by 48
  10. 2016Asymptotic Optimality in Stochastic Optimizationcited by 38
  11. 2016Stochastic Quasi-Newton Methods for Nonconvex Stochastic Optimizationcited by 37
  12. 2016Calculus of the exponent of Kurdyka-Lojasiewicz inequality and its applications to linear convergence of first-order methodscited by 35
16 more
  1. 2021Convergence of stochastic gradient descent schemes for Lojasiewicz-landscapescited by 28
  2. 2014Splitting methods with variable metric for KL functionscited by 26
  3. 2020Alternating proximal-gradient steps for (stochastic) nonconvex-concave minimax problemscited by 26
  4. 2022Stochastic fixed-point iterations for nonexpansive maps: Convergence and error boundscited by 24
  5. 2018Analysis of nonsmooth stochastic approximation: the differential inclusion approachcited by 23
  6. 2014Convergence of Stochastic Proximal Gradient Algorithmcited by 17
  7. 2022A Unified Convergence Theorem for Stochastic Optimization Methodscited by 12
  8. 2018Local Convergence Properties of SAGA/Prox-SVRG and Accelerationcited by 10
  9. 2021Bregman Finito/MISO for nonconvex regularized finite sum minimization without Lipschitz gradient continuitycited by 7
  10. 2021Training Structured Neural Networks Through Manifold Identification and Variance Reductioncited by 7
  11. 2014Model Consistency of Partly Smooth Regularizerscited by 6
  12. 2019Block-coordinate and incremental aggregated proximal gradient methods for nonsmooth nonconvex problemscited by 5
  13. 2020Accelerating Inexact Successive Quadratic Approximation for Regularized Optimization Through Manifold Identificationcited by 4
  14. 2021A trust region-type normal map-based semismooth Newton method for nonsmooth nonconvex composite optimizationcited by 4
  15. 2018A Stochastic Semismooth Newton Method for Nonsmooth Nonconvex Optimizationcited by 3
  16. 2023A Variance-Reduced and Stabilized Proximal Stochastic Gradient Method with Support Identification Guarantees for Structured Optimizationcited by 1

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2024: 1; 2025: 1; 2026: 3.

5 papers.

  1. 2024A KL-based Analysis Framework with Applications to Non-Descent Optimization Methodscited by 1
  2. 2026Shuffling the Stochastic Mirror Descent via Dual Lipschitz Continuity and Kernel Conditioningcited by 1
  3. 2025Quantization through Piecewise-Affine Regularization: Optimization and Statistical Guaranteescited by 0
  4. 2026Achieving Linear Speedup for Composite Federated Learningcited by 0
  5. 2026Stochastic Saddle Avoidance Beyond Unit Excitation and Smoothness: A Pathwise Lyapunov-Perron Frameworkcited by 0