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

arXiv: https://arxiv.org/abs/2305.05828 · HTML: https://mlsanity.com/paper/2305.05828/

## 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 (most cited first, 28 of 28)

- [Optimization Methods for Large-Scale Machine Learning](https://mlsanity.com/paper/1606.04838/) (2016)
- [Momentum-Based Variance Reduction in Non-Convex SGD](https://mlsanity.com/paper/1905.10018/) (2019)
- [Stochastic model-based minimization of weakly convex functions](https://mlsanity.com/paper/1803.06523/) (2018)
- [Mini-batch Stochastic Approximation Methods for Nonconvex Stochastic Composite Optimization](https://mlsanity.com/paper/1308.6594/) (2013)
- [Stochastic subgradient method converges on tame functions](https://mlsanity.com/paper/1804.07795/) (2018)
- [A Proximal Stochastic Gradient Method with Progressive Variance Reduction](https://mlsanity.com/paper/1403.4699/) (2014)
- [Error bounds, quadratic growth, and linear convergence of proximal methods](https://mlsanity.com/paper/1602.06661/) (2016)
- [Efficiency of minimizing compositions of convex functions and smooth maps](https://mlsanity.com/paper/1605.00125/) (2016)
- [Stochastic Methods for Composite and Weakly Convex Optimization Problems](https://mlsanity.com/paper/1703.08570/) (2017)
- [Asymptotic Optimality in Stochastic Optimization](https://mlsanity.com/paper/1612.05612/) (2016)
- [Stochastic Quasi-Newton Methods for Nonconvex Stochastic Optimization](https://mlsanity.com/paper/1607.01231/) (2016)
- [Calculus of the exponent of Kurdyka-Lojasiewicz inequality and its applications to linear convergence of first-order methods](https://mlsanity.com/paper/1602.02915/) (2016)
- [Convergence of stochastic gradient descent schemes for Lojasiewicz-landscapes](https://mlsanity.com/paper/2102.09385/) (2021)
- [Splitting methods with variable metric for KL functions](https://mlsanity.com/paper/1405.1357/) (2014)
- [Alternating proximal-gradient steps for (stochastic) nonconvex-concave minimax problems](https://mlsanity.com/paper/2007.13605/) (2020)
- [Stochastic fixed-point iterations for nonexpansive maps: Convergence and error bounds](https://mlsanity.com/paper/2208.04193/) (2022)
- [Analysis of nonsmooth stochastic approximation: the differential inclusion approach](https://mlsanity.com/paper/1805.01916/) (2018)
- [Convergence of Stochastic Proximal Gradient Algorithm](https://mlsanity.com/paper/1403.5074/) (2014)
- [A Unified Convergence Theorem for Stochastic Optimization Methods](https://mlsanity.com/paper/2206.03907/) (2022)
- [Local Convergence Properties of SAGA/Prox-SVRG and Acceleration](https://mlsanity.com/paper/1802.02554/) (2018)
- [Bregman Finito/MISO for nonconvex regularized finite sum minimization without Lipschitz gradient continuity](https://mlsanity.com/paper/2102.10312/) (2021)
- [Training Structured Neural Networks Through Manifold Identification and Variance Reduction](https://mlsanity.com/paper/2112.02612/) (2021)
- [Model Consistency of Partly Smooth Regularizers](https://mlsanity.com/paper/1405.1004/) (2014)
- [Block-coordinate and incremental aggregated proximal gradient methods for nonsmooth nonconvex problems](https://mlsanity.com/paper/1906.10053/) (2019)
- [Accelerating Inexact Successive Quadratic Approximation for Regularized Optimization Through Manifold Identification](https://mlsanity.com/paper/2012.02522/) (2020)
- [A trust region-type normal map-based semismooth Newton method for nonsmooth nonconvex composite optimization](https://mlsanity.com/paper/2106.09340/) (2021)
- [A Stochastic Semismooth Newton Method for Nonsmooth Nonconvex Optimization](https://mlsanity.com/paper/1803.03466/) (2018)
- [A Variance-Reduced and Stabilized Proximal Stochastic Gradient Method with Support Identification Guarantees for Structured Optimization](https://mlsanity.com/paper/2302.06790/) (2023)

## Built on by (most cited first, 5 of 5)

- [A KL-based Analysis Framework with Applications to Non-Descent Optimization Methods](https://mlsanity.com/paper/2406.02273/) (2024)
- [Shuffling the Stochastic Mirror Descent via Dual Lipschitz Continuity and Kernel Conditioning](https://mlsanity.com/paper/2603.16042/) (2026)
- [Quantization through Piecewise-Affine Regularization: Optimization and Statistical Guarantees](https://mlsanity.com/paper/2508.11112/) (2025)
- [Achieving Linear Speedup for Composite Federated Learning](https://mlsanity.com/paper/2602.03357/) (2026)
- [Stochastic Saddle Avoidance Beyond Unit Excitation and Smoothness: A Pathwise Lyapunov-Perron Framework](https://mlsanity.com/paper/2608.03001/) (2026)

## 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.