# Stochastic Variance-Reduced Prox-Linear Algorithms for Nonconvex Composite Optimization

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

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 9 Apr 2020.

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

- [Minibatch and Momentum Model-based Methods for Stochastic Weakly Convex Optimization](https://mlsanity.com/paper/2106.03034/) (2021)
- [Modified Gauss-Newton Algorithms under Noise](https://mlsanity.com/paper/2305.10634/) (2023)
- [Stochastic Primal-Dual Double Block-Coordinate for Two-way Partial AUC Maximization](https://mlsanity.com/paper/2505.21944/) (2025)
- [Dual Gauss-Newton Directions for Deep Learning](https://mlsanity.com/paper/2308.08886/) (2023)
- [Shuffling Gradient-Based Methods for Nonconvex-Concave Minimax Optimization](https://mlsanity.com/paper/2410.22297/) (2024)
- [DualHash: A Stochastic Primal-Dual Algorithm with Theoretical Guarantee for Deep Hashing](https://mlsanity.com/paper/2510.18218/) (2025)
- [Variance-Reduced Conditional Gradient Methods under Markovian Sampling for Nonconvex Composite Optimization](https://mlsanity.com/paper/2607.25785/) (2026)

## Abstract (arXiv)

We consider minimization of composite functions of the form f(g(x))+h(x), where f and h are convex functions (which can be nonsmooth) and g is a smooth vector mapping. In addition, we assume that g is the average of finite number of component mappings or the expectation over a family of random component mappings. We propose a class of stochastic variance-reduced prox-linear algorithms for solving such problems and bound their sample complexities for finding an ε-stationary point in terms of the total number of evaluations of the component mappings and their Jacobians. When g is a finite average of N components, we obtain sample complexity O(N+ N4/5ε-1) for both mapping and Jacobian evaluations. When g is a general expectation, we obtain sample complexities of O(ε-5/2) and O(ε-3/2) for component mappings and their Jacobians respectively. If in addition f is smooth, then improved sample complexities of O(N+N1/2ε-1) and O(ε-3/2) are derived for g being a finite average and a general expectation respectively, for both component mapping and Jacobian evaluations.