# A Stochastic Subgradient Method for Nonsmooth Nonconvex Multi-Level Composition Optimization

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

## Key facts

- Cited by 16 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 29 Jan 2020.

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

- [Non-convex Distributionally Robust Optimization: Non-asymptotic Analysis](https://mlsanity.com/paper/2110.12459/) (2021)
- [Decentralized Gossip-Based Stochastic Bilevel Optimization over Communication Networks](https://mlsanity.com/paper/2206.10870/) (2022)
- [Tighter Analysis of Alternating Stochastic Gradient Method for Stochastic Nested Problems](https://mlsanity.com/paper/2106.13781/) (2021)
- [A Single-Timescale Analysis For Stochastic Approximation With Multiple Coupled Sequences](https://mlsanity.com/paper/2206.10414/) (2022)
- [A Projection-free Algorithm for Constrained Stochastic Multi-level Composition Optimization](https://mlsanity.com/paper/2202.04296/) (2022)
- [Zeroth-order Riemannian Averaging Stochastic Approximation Algorithms](https://mlsanity.com/paper/2309.14506/) (2023)
- [Adam-family Methods with Decoupled Weight Decay in Deep Learning](https://mlsanity.com/paper/2310.08858/) (2023)
- [Stochastic Compositional Optimization with Compositional Constraints](https://mlsanity.com/paper/2209.04086/) (2022)
- [A Functional Model Method for Nonconvex Nonsmooth Conditional Stochastic Optimization](https://mlsanity.com/paper/2405.10815/) (2024)
- [Stochastic Optimization Algorithms for Instrumental Variable Regression with Streaming Data](https://mlsanity.com/paper/2405.19463/) (2024)
- [Stability and Generalization of Stochastic Compositional Gradient Descent Algorithms](https://mlsanity.com/paper/2307.03357/) (2023)
- [Stochastic Subgradient Methods with Guaranteed Global Stability in Nonsmooth Nonconvex Optimization](https://mlsanity.com/paper/2307.10053/) (2023)
- [Batched Stochastic Bandit for Nondegenerate Functions](https://mlsanity.com/paper/2405.05733/) (2024)
- [Stochastic Nested Compositional Bi-level Optimization for Robust Feature Learning](https://mlsanity.com/paper/2307.05384/) (2023)
- [Lipschitzian SLLNs for random functions](https://mlsanity.com/paper/2607.20411/) (2026)
- [Optimal Momentum Methods for Stochastic Multilevel Compositional Optimization](https://mlsanity.com/paper/2610.01572/) (2026)

## Abstract (arXiv)

We propose a single time-scale stochastic subgradient method for constrained optimization of a composition of several nonsmooth and nonconvex functions. The functions are assumed to be locally Lipschitz and differentiable in a generalized sense. Only stochastic estimates of the values and generalized derivatives of the functions are used. The method is parameter-free. We prove convergence with probability one of the method, by associating with it a system of differential inclusions and devising a nondifferentiable Lyapunov function for this system. For problems with functions having Lipschitz continuous derivatives, the method finds a point satisfying an optimality measure with error of order 1/√N, after executing N iterations with constant stepsize.