# Non-asymptotic Analysis of Stochastic Methods for Non-Smooth Non-Convex Regularized Problems

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

## Key facts

- Cited by 14 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 20 Feb 2019.

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

- [Finite-Sum Coupled Compositional Stochastic Optimization: Theory and Applications](https://mlsanity.com/paper/2202.12396/) (2022)
- [Not All Semantics are Created Equal: Contrastive Self-supervised Learning with Automatic Temperature Individualization](https://mlsanity.com/paper/2305.11965/) (2023)
- [Structured Sparsity Inducing Adaptive Optimizers for Deep Learning](https://mlsanity.com/paper/2102.03869/) (2021)
- [Stochastic Constrained DRO with a Complexity Independent of Sample Size](https://mlsanity.com/paper/2210.05740/) (2022)
- [An Experimental Comparison Between Temporal Difference and Residual Gradient with Neural Network Approximation](https://mlsanity.com/paper/2205.12770/) (2022)
- [Demystifying the Myths and Legends of Nonconvex Convergence of SGD](https://mlsanity.com/paper/2310.12969/) (2023)
- [FedOne: Query-Efficient Federated Learning for Black-box Discrete Prompt Learning](https://mlsanity.com/paper/2506.14929/) (2025)
- [A Theoretical Analysis of Learning with Noisily Labeled Data](https://mlsanity.com/paper/2104.04114/) (2021)
- [Adaptive Lipschitz-Free Proximal Gradient Methods for Stochastic Composite Nonconvex Optimization](https://mlsanity.com/paper/2502.21099/) (2025)
- [Differentially Private Non-convex Distributionally Robust Optimization](https://mlsanity.com/paper/2602.16155/) (2026)
- [A Stochastic Proximal Method for Nonsmooth Regularized Finite Sum Optimization](https://mlsanity.com/paper/2206.06531/) (2022)
- [Outlier-robust neural network training: variation regularization meets trimmed loss to prevent functional breakdown](https://mlsanity.com/paper/2308.02293/) (2023)
- [Hard-Thresholding Meets Evolution Strategies in Reinforcement Learning](https://mlsanity.com/paper/2405.01615/) (2024)
- [DualHash: A Stochastic Primal-Dual Algorithm with Theoretical Guarantee for Deep Hashing](https://mlsanity.com/paper/2510.18218/) (2025)

## Abstract (arXiv)

Stochastic Proximal Gradient (SPG) methods have been widely used for solving optimization problems with a simple (possibly non-smooth) regularizer in machine learning and statistics. However, to the best of our knowledge no non-asymptotic convergence analysis of SPG exists for non-convex optimization with a non-smooth and non-convex regularizer. All existing non-asymptotic analysis of SPG for solving non-smooth non-convex problems require the non-smooth regularizer to be a convex function, and hence are not applicable to a non-smooth non-convex regularized problem. This work initiates the analysis to bridge this gap and opens the door to non-asymptotic convergence analysis of non-smooth non-convex regularized problems. We analyze several variants of mini-batch SPG methods for minimizing a non-convex objective that consists of a smooth non-convex loss and a non-smooth non-convex regularizer. Our contributions are two-fold: (i) we show that they enjoy the same complexities as their counterparts for solving convex regularized non-convex problems in terms of finding an approximate stationary point; (ii) we develop more practical variants using dynamic mini-batch size instead of a fixed mini-batch size without requiring the target accuracy level of solution. The significance of our results is that they improve upon the-state-of-art results for solving non-smooth non-convex regularized problems. We also empirically demonstrate the effectiveness of the considered SPG methods in comparison with other peer stochastic methods.