# Stochastic Methods for Composite and Weakly Convex Optimization Problems

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

## Key facts

- Cited by 48 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 24 Mar 2017.

## Built on by (most cited first, 30 of 48)

- [Same Pre-training Loss, Better Downstream: Implicit Bias Matters for Language Models](https://mlsanity.com/paper/2210.14199/) (2022)
- [Gradient-Free Methods for Deterministic and Stochastic Nonsmooth Nonconvex Optimization](https://mlsanity.com/paper/2209.05045/) (2022)
- [Oracle Complexity in Nonsmooth Nonconvex Optimization](https://mlsanity.com/paper/2104.06763/) (2021)
- [Stability and Convergence of Stochastic Gradient Clipping: Beyond Lipschitz Continuity and Smoothness](https://mlsanity.com/paper/2102.06489/) (2021)
- [Convergence of gradient descent for deep neural networks](https://mlsanity.com/paper/2203.16462/) (2022)
- [Explicit Eigenvalue Regularization Improves Sharpness-Aware Minimization](https://mlsanity.com/paper/2501.12666/) (2025)
- [Accelerated, Optimal, and Parallel: Some Results on Model-Based Stochastic Optimization](https://mlsanity.com/paper/2101.02696/) (2021)
- [When is the Convergence Time of Langevin Algorithms Dimension Independent? A Composite Optimization Viewpoint](https://mlsanity.com/paper/2110.01827/) (2021)
- [A Unified Convergence Theorem for Stochastic Optimization Methods](https://mlsanity.com/paper/2206.03907/) (2022)
- [Minibatch and Momentum Model-based Methods for Stochastic Weakly Convex Optimization](https://mlsanity.com/paper/2106.03034/) (2021)
- [Non-Smooth Weakly-Convex Finite-sum Coupled Compositional Optimization](https://mlsanity.com/paper/2310.03234/) (2023)
- [Stochastic Subgradient Descent Escapes Active Strict Saddles on Weakly Convex Functions](https://mlsanity.com/paper/2108.02072/) (2021)
- [A Projection-free Algorithm for Constrained Stochastic Multi-level Composition Optimization](https://mlsanity.com/paper/2202.04296/) (2022)
- [A Normal Map-Based Proximal Stochastic Gradient Method: Convergence and Identification Properties](https://mlsanity.com/paper/2305.05828/) (2023)
- [A Model-Based Method for Minimizing CVaR and Beyond](https://mlsanity.com/paper/2305.17498/) (2023)
- [Adam-family Methods with Decoupled Weight Decay in Deep Learning](https://mlsanity.com/paper/2310.08858/) (2023)
- [Lower Bounds and Proximally Anchored SGD for Non-Convex Minimization Under Unbounded Variance](https://mlsanity.com/paper/2604.16620/) (2026)
- [First-Order Methods for Convex Optimization](https://mlsanity.com/paper/2101.00935/) (2021)
- [On the Self-Penalization Phenomenon in Feature Selection](https://mlsanity.com/paper/2110.05852/) (2021)
- [Sharper Analysis for Minibatch Stochastic Proximal Point Methods: Stability, Smoothness, and Deviation](https://mlsanity.com/paper/2301.03125/) (2023)
- [A New Random Reshuffling Method for Nonsmooth Nonconvex Finite-sum Optimization](https://mlsanity.com/paper/2312.01047/) (2023)
- [A Functional Model Method for Nonconvex Nonsmooth Conditional Stochastic Optimization](https://mlsanity.com/paper/2405.10815/) (2024)
- [Second-order step-size tuning of SGD for non-convex optimization](https://mlsanity.com/paper/2103.03570/) (2021)
- [Convergence of stochastic gradient descent under a local Lojasiewicz condition for deep neural networks](https://mlsanity.com/paper/2304.09221/) (2023)
- [Stochastic Subgradient Methods with Guaranteed Global Stability in Nonsmooth Nonconvex Optimization](https://mlsanity.com/paper/2307.10053/) (2023)
- [On the Uniform Convergence of Subdifferentials in Stochastic Optimization and Learning](https://mlsanity.com/paper/2405.10289/) (2024)
- [On exploration of an interior mirror descent flow for stochastic nonconvex constrained problem](https://mlsanity.com/paper/2507.15264/) (2025)
- [Deep Learning as the Disciplined Construction of Tame Objects](https://mlsanity.com/paper/2509.18025/) (2025)
- [Efficient algorithms for implementing incremental proximal-point methods](https://mlsanity.com/paper/2205.01457/) (2022)
- [Developing Lagrangian-based Methods for Nonsmooth Nonconvex Optimization](https://mlsanity.com/paper/2404.09438/) (2024)

## Abstract (arXiv)

We consider minimization of stochastic functionals that are compositions of a (potentially) non-smooth convex function h and smooth function c and, more generally, stochastic weakly-convex functionals. We develop a family of stochastic methods---including a stochastic prox-linear algorithm and a stochastic (generalized) sub-gradient procedure---and prove that, under mild technical conditions, each converges to first-order stationary points of the stochastic objective. We provide experiments further investigating our methods on non-smooth phase retrieval problems; the experiments indicate the practical effectiveness of the procedures.