# Stochastic Variable Metric Proximal Gradient with variance reduction for non-convex composite optimization

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 28 of its 79 references that are in the map.
- First posted on arXiv 2 Jan 2023.

## Builds on (most cited first, 28 of 28)

- [Stochastic First- and Zeroth-order Methods for Nonconvex Stochastic Programming](https://mlsanity.com/paper/1309.5549/) (2013)
- [Linear Convergence of Gradient and Proximal-Gradient Methods Under the Polyak-Lojasiewicz Condition](https://mlsanity.com/paper/1608.04636/) (2016)
- [SAGA: A Fast Incremental Gradient Method With Support for Non-Strongly Convex Composite Objectives](https://mlsanity.com/paper/1407.0202/) (2014)
- [SPIDER: Near-Optimal Non-Convex Optimization via Stochastic Path Integrated Differential Estimator](https://mlsanity.com/paper/1807.01695/) (2018)
- [SARAH: A Novel Method for Machine Learning Problems Using Stochastic Recursive Gradient](https://mlsanity.com/paper/1703.00102/) (2017)
- [On the Convergence of A Class of Adam-Type Algorithms for Non-Convex Optimization](https://mlsanity.com/paper/1808.02941/) (2018)
- [Stochastic Variance Reduction for Nonconvex Optimization](https://mlsanity.com/paper/1603.06160/) (2016)
- [Mini-batch Stochastic Approximation Methods for Nonconvex Stochastic Composite Optimization](https://mlsanity.com/paper/1308.6594/) (2013)
- [PAGE: A Simple and Optimal Probabilistic Gradient Estimator for Nonconvex Optimization](https://mlsanity.com/paper/2008.10898/) (2020)
- [Variance Reduction for Faster Non-Convex Optimization](https://mlsanity.com/paper/1603.05643/) (2016)
- [Stochastic Nested Variance Reduction for Nonconvex Optimization](https://mlsanity.com/paper/1806.07811/) (2018)
- [Natasha 2: Faster Non-Convex Optimization Than SGD](https://mlsanity.com/paper/1708.08694/) (2017)
- [A Linearly-Convergent Stochastic L-BFGS Algorithm](https://mlsanity.com/paper/1508.02087/) (2015)
- [ProxSARAH: An Efficient Algorithmic Framework for Stochastic Composite Nonconvex Optimization](https://mlsanity.com/paper/1902.05679/) (2019)
- [A Simple Proximal Stochastic Gradient Method for Nonsmooth Nonconvex Optimization](https://mlsanity.com/paper/1802.04477/) (2018)
- [A Stochastic Composite Gradient Method with Incremental Variance Reduction](https://mlsanity.com/paper/1906.10186/) (2019)
- [Stochastic Block BFGS: Squeezing More Curvature out of Data](https://mlsanity.com/paper/1603.09649/) (2016)
- [Adaptivity of Stochastic Gradient Methods for Nonconvex Optimization](https://mlsanity.com/paper/2002.05359/) (2020)
- [On the Global Convergence of (Fast) Incremental Expectation Maximization Methods](https://mlsanity.com/paper/1910.12521/) (2019)
- [Faster Stochastic Quasi-Newton Methods](https://mlsanity.com/paper/2004.06479/) (2020)
- [On Quasi-Newton Forward--Backward Splitting: Proximal Calculus and Convergence](https://mlsanity.com/paper/1801.08691/) (2018)
- [Geom-SPIDER-EM: Faster Variance Reduced Stochastic Expectation Maximization for Nonconvex Finite-Sum Optimization](https://mlsanity.com/paper/2011.12392/) (2020)
- [Fast Incremental Expectation Maximization for finite-sum optimization: nonasymptotic convergence](https://mlsanity.com/paper/2012.14670/) (2020)
- [Stochastic Proximal Methods for Non-Smooth Non-Convex Constrained Sparse Optimization](https://mlsanity.com/paper/1905.10188/) (2019)
- [Variable Metric Proximal Gradient Method with Diagonal Barzilai-Borwein Stepsize](https://mlsanity.com/paper/1910.07056/) (2019)
- [The perturbed prox-preconditioned spider algorithm: non-asymptotic convergence bounds](https://mlsanity.com/paper/2105.11733/) (2021)
- [Variable Metric Forward-Backward Algorithm for Composite Minimization Problems](https://mlsanity.com/paper/1907.11486/) (2019)
- [A Stochastic Path-Integrated Differential EstimatoR Expectation Maximization Algorithm](https://mlsanity.com/paper/2012.01929/) (2020)

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

- [Stochastic Approximation Beyond Gradient for Signal Processing and Machine Learning](https://mlsanity.com/paper/2302.11147/) (2023)
- [Revisiting Incremental Stochastic Majorization-Minimization Algorithms with Applications to Mixture of Experts](https://mlsanity.com/paper/2601.19811/) (2026)
- [Fast Model Selection and Stable Optimization for Softmax-Gated Multinomial-Logistic Mixture of Experts Models](https://mlsanity.com/paper/2602.07997/) (2026)

## Abstract (arXiv)

This paper introduces a novel algorithm, the Perturbed Proximal Preconditioned SPIDER algorithm (3P-SPIDER), designed to solve finite sum non-convex composite optimization. It is a stochastic Variable Metric Forward-Backward algorithm, which allows approximate preconditioned forward operator and uses a variable metric proximity operator as the backward operator; it also proposes a mini-batch strategy with variance reduction to address the finite sum setting. We show that 3P-SPIDER extends some Stochastic preconditioned Gradient Descent-based algorithms and some Incremental Expectation Maximization algorithms to composite optimization and to the case the forward operator can not be computed in closed form. We also provide an explicit control of convergence in expectation of 3P-SPIDER, and study its complexity in order to satisfy the epsilon-approximate stationary condition. Our results are the first to combine the composite non-convex optimization setting, a variance reduction technique to tackle the finite sum setting by using a minibatch strategy and, to allow deterministic or random approximations of the preconditioned forward operator. Finally, through an application to inference in a logistic regression model with random effects, we numerically compare 3P-SPIDER to other stochastic forward-backward algorithms and discuss the role of some design parameters of 3P-SPIDER.