# A proximal subgradient method for nonconvex stochastic optimization under the Kurdyka-Lojasiewicz condition

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 38 of its 89 references that are in the map.
- First posted on arXiv 5 Aug 2026.

## Builds on (most cited first, 30 of 38)

- [Optimization Methods for Large-Scale Machine Learning](https://mlsanity.com/paper/1606.04838/) (2016)
- [Stochastic First- and Zeroth-order Methods for Nonconvex Stochastic Programming](https://mlsanity.com/paper/1309.5549/) (2013)
- [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)
- [Accelerated Gradient Methods for Nonconvex Nonlinear and Stochastic Programming](https://mlsanity.com/paper/1310.3787/) (2013)
- [Regularized M-estimators with nonconvexity: Statistical and algorithmic theory for local optima](https://mlsanity.com/paper/1305.2436/) (2013)
- [Stochastic Methods for Composite and Weakly Convex Optimization Problems](https://mlsanity.com/paper/1703.08570/) (2017)
- [ProxSARAH: An Efficient Algorithmic Framework for Stochastic Composite Nonconvex Optimization](https://mlsanity.com/paper/1902.05679/) (2019)
- [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)
- [Extragradient method with variance reduction for stochastic variational inequalities](https://mlsanity.com/paper/1703.00260/) (2017)
- [Proximally Guided Stochastic Subgradient Method for Nonsmooth, Nonconvex Problems](https://mlsanity.com/paper/1707.03505/) (2017)
- [Learning from Ambiguously Labeled Face Images](https://mlsanity.com/paper/1702.04455/) (2017)
- [A Hybrid Stochastic Optimization Framework for Stochastic Composite Nonconvex Optimization](https://mlsanity.com/paper/1907.03793/) (2019)
- [Splitting methods with variable metric for KL functions](https://mlsanity.com/paper/1405.1357/) (2014)
- [First-Order Methods for Nonsmooth Nonconvex Functional Constrained Optimization with or without Slater Points](https://mlsanity.com/paper/2212.00927/) (2022)
- [Fundamental Convergence Analysis of Sharpness-Aware Minimization](https://mlsanity.com/paper/2401.08060/) (2024)
- [Variable Smoothing for Weakly Convex Composite Functions](https://mlsanity.com/paper/2003.07612/) (2020)
- [Stochastic Optimization under Hidden Convexity](https://mlsanity.com/paper/2401.00108/) (2023)
- [Accelerating the DC algorithm for smooth functions](https://mlsanity.com/paper/1507.07375/) (2015)
- [On the Convergence of the Iterative Shrinkage/Thresholding Algorithm With a Weakly Convex Penalty](https://mlsanity.com/paper/1510.07821/) (2015)
- [A Method for Finding Structured Sparse Solutions to Non-negative Least Squares Problems with Applications](https://mlsanity.com/paper/1301.0413/) (2013)
- [A Zeroth-order Proximal Stochastic Gradient Method for Weakly Convex Stochastic Optimization](https://mlsanity.com/paper/2205.01633/) (2022)
- [Simple and Optimal Stochastic Gradient Methods for Nonsmooth Nonconvex Optimization](https://mlsanity.com/paper/2208.10025/) (2022)
- [Stochastic Proximal Methods for Non-Smooth Non-Convex Constrained Sparse Optimization](https://mlsanity.com/paper/1905.10188/) (2019)
- [Incremental constraint projection methods for monotone stochastic variational inequalities](https://mlsanity.com/paper/1703.00272/) (2017)
- [Asynchronous Variance-reduced Block Schemes for Composite Nonconvex Stochastic Optimization: Block-specific Steplengths and Adapted Batch-sizes](https://mlsanity.com/paper/1808.02543/) (2018)
- [Partial-Label Regression](https://mlsanity.com/paper/2306.08968/) (2023)
- [On variance reduction for stochastic smooth convex optimization with multiplicative noise](https://mlsanity.com/paper/1705.02969/) (2017)
- [Stochastic Proximal Gradient Methods for Nonconvex Problems in Hilbert Spaces](https://mlsanity.com/paper/2001.01329/) (2020)
- [The Boosted Double-Proximal Subgradient Algorithm for Nonconvex Optimization](https://mlsanity.com/paper/2306.17144/) (2023)

## Abstract (arXiv)

This work introduces a proximal stochastic subgradient method for minimizing the sum of an expected cost, whose integrand is potentially nonsmooth and nonconvex, and a lower semicontinuous, prox-bounded function. We target a broad class of integrands obeying a nonsmooth, localized variant of the descent lemma in the decision variable, a structural assumption that simultaneously covers smooth losses with Lipschitz gradient and differences of such losses with convex functions. At each iteration the expected cost is replaced by a sample average that is progressively refined, and the proximal-subgradient stepsize is selected by an Armijo-type line search enforcing a sufficient-decrease property up to stochastic errors induced by the sample-based approximation. This framework accommodates substantially more general problem formulations than existing methods, in particular, it requires neither (weak) convexity of the regularizer nor a uniform bound on the variance of the stochastic oracle, and our analysis yields convergence guarantees that are new even in the smooth setting. Specifically, we establish almost sure convergence of the sequence of function values and stationarity of every accumulation point of the trajectories under the relaxed requirement that the sample-size sequence be merely nondecreasing and unbounded, with no prescribed growth rate. Leveraging the Kurdyka-Lojasiewicz (KL) property, we further upgrade this subsequential guarantee to convergence of the whole trajectory to a single stationary point. Finally, for exponential-type KL desingularizing functions and polynomially growing sample sizes, we derive explicit polynomial convergence rates, up to a logarithmic factor, for both the function values and the iterates.