# SPIRAL: A superlinearly convergent incremental proximal algorithm for nonconvex finite sum minimization

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 41 of its 89 references that are in the map.
- First posted on arXiv 17 Jul 2022.

## Builds on (most cited first, 30 of 41)

- [Stochastic First- and Zeroth-order Methods for Nonconvex Stochastic Programming](https://mlsanity.com/paper/1309.5549/) (2013)
- [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)
- [Minimizing Finite Sums with the Stochastic Average Gradient](https://mlsanity.com/paper/1309.2388/) (2013)
- [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)
- [Phase Retrieval via Wirtinger Flow: Theory and Algorithms](https://mlsanity.com/paper/1407.1065/) (2014)
- [Random Reshuffling: Simple Analysis with Vast Improvements](https://mlsanity.com/paper/2006.05988/) (2020)
- [Relatively-Smooth Convex Optimization by First-Order Methods, and Applications](https://mlsanity.com/paper/1610.05708/) (2016)
- [A Geometric Analysis of Phase Retrieval](https://mlsanity.com/paper/1602.06664/) (2016)
- [Why Random Reshuffling Beats Stochastic Gradient Descent](https://mlsanity.com/paper/1510.08560/) (2015)
- [Random Shuffling Beats SGD after Finite Epochs](https://mlsanity.com/paper/1806.10077/) (2018)
- [A Linearly-Convergent Stochastic L-BFGS Algorithm](https://mlsanity.com/paper/1508.02087/) (2015)
- [First Order Methods beyond Convexity and Lipschitz Gradient Continuity with Applications to Quadratic Inverse Problems](https://mlsanity.com/paper/1706.06461/) (2017)
- [ProxSARAH: An Efficient Algorithmic Framework for Stochastic Composite Nonconvex Optimization](https://mlsanity.com/paper/1902.05679/) (2019)
- [Incremental Majorization-Minimization Optimization with Application to Large-Scale Machine Learning](https://mlsanity.com/paper/1402.4419/) (2014)
- [ZeroSARAH: Efficient Nonconvex Finite-Sum Optimization with Zero Full Gradient Computation](https://mlsanity.com/paper/2103.01447/) (2021)
- [Solving (most) of a set of quadratic equalities: Composite optimization for robust phase retrieval](https://mlsanity.com/paper/1705.02356/) (2017)
- [Fast Stochastic Bregman Gradient Methods: Sharp Analysis and Variance Reduction](https://mlsanity.com/paper/2104.09813/) (2021)
- [Stabilized SVRG: Simple Variance Reduction for Nonconvex Optimization](https://mlsanity.com/paper/1905.00529/) (2019)
- [Fastest Rates for Stochastic Mirror Descent Methods](https://mlsanity.com/paper/1803.07374/) (2018)
- [Surpassing Gradient Descent Provably: A Cyclic Incremental Method with Linear Convergence Rate](https://mlsanity.com/paper/1611.00347/) (2016)
- [Global Convergence Rate of Proximal Incremental Aggregated Gradient Methods](https://mlsanity.com/paper/1608.01713/) (2016)
- [IQN: An Incremental Quasi-Newton Method with Local Superlinear Convergence Rate](https://mlsanity.com/paper/1702.00709/) (2017)
- [Finito: A Faster, Permutable Incremental Gradient Method for Big Data Problems](https://mlsanity.com/paper/1407.2710/) (2014)
- [Forward-backward quasi-Newton methods for nonsmooth optimization problems](https://mlsanity.com/paper/1604.08096/) (2016)
- [Forward-backward envelope for the sum of two nonconvex functions: Further properties and nonmonotone line-search algorithms](https://mlsanity.com/paper/1606.06256/) (2016)
- [Stochastic model-based minimization under high-order growth](https://mlsanity.com/paper/1807.00255/) (2018)
- [A Stochastic Extra-Step Quasi-Newton Method for Nonsmooth Nonconvex Optimization](https://mlsanity.com/paper/1910.09373/) (2019)

## Abstract (arXiv)

We introduce SPIRAL, a SuPerlinearly convergent Incremental pRoximal ALgorithm, for solving nonconvex regularized finite sum problems under a relative smoothness assumption. Each iteration of SPIRAL consists of an inner and an outer loop. It combines incremental gradient updates with a linesearch that has the remarkable property of never being triggered asymptotically, leading to superlinear convergence under mild assumptions at the limit point. Simulation results with L-BFGS directions on different convex, nonconvex, and non-Lipschitz differentiable problems show that our algorithm, as well as its adaptive variant, are competitive to the state of the art.