mlsanityData to 14 Oct 2026

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

arXiv 2207.08195 ↗First posted 17 Jul 2022math.OC cs.LGcited by 0

Not on the map. Why?

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.

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

41 of 89 references.

References · 41

  1. 2013Stochastic First- and Zeroth-order Methods for Nonconvex Stochastic Programmingcited by 724
  2. 2014SAGA: A Fast Incremental Gradient Method With Support for Non-Strongly Convex Composite Objectivescited by 402
  3. 2018SPIDER: Near-Optimal Non-Convex Optimization via Stochastic Path Integrated Differential Estimatorcited by 287
  4. 2017SARAH: A Novel Method for Machine Learning Problems Using Stochastic Recursive Gradientcited by 220
  5. 2013Minimizing Finite Sums with the Stochastic Average Gradientcited by 164
  6. 2016Stochastic Variance Reduction for Nonconvex Optimizationcited by 145
  7. 2013Mini-batch Stochastic Approximation Methods for Nonconvex Stochastic Composite Optimizationcited by 143
  8. 2014Phase Retrieval via Wirtinger Flow: Theory and Algorithmscited by 125
  9. 2020Random Reshuffling: Simple Analysis with Vast Improvementscited by 115
  10. 2016Relatively-Smooth Convex Optimization by First-Order Methods, and Applicationscited by 108
  11. 2016A Geometric Analysis of Phase Retrievalcited by 92
  12. 2015Why Random Reshuffling Beats Stochastic Gradient Descentcited by 79
29 more
  1. 2018Random Shuffling Beats SGD after Finite Epochscited by 67
  2. 2015A Linearly-Convergent Stochastic L-BFGS Algorithmcited by 39
  3. 2017First Order Methods beyond Convexity and Lipschitz Gradient Continuity with Applications to Quadratic Inverse Problemscited by 37
  4. 2019ProxSARAH: An Efficient Algorithmic Framework for Stochastic Composite Nonconvex Optimizationcited by 37
  5. 2014Incremental Majorization-Minimization Optimization with Application to Large-Scale Machine Learningcited by 35
  6. 2021ZeroSARAH: Efficient Nonconvex Finite-Sum Optimization with Zero Full Gradient Computationcited by 29
  7. 2017Solving (most) of a set of quadratic equalities: Composite optimization for robust phase retrievalcited by 24
  8. 2021Fast Stochastic Bregman Gradient Methods: Sharp Analysis and Variance Reductioncited by 19
  9. 2019Stabilized SVRG: Simple Variance Reduction for Nonconvex Optimizationcited by 15
  10. 2018Fastest Rates for Stochastic Mirror Descent Methodscited by 14
  11. 2016Surpassing Gradient Descent Provably: A Cyclic Incremental Method with Linear Convergence Ratecited by 12
  12. 2016Global Convergence Rate of Proximal Incremental Aggregated Gradient Methodscited by 11
  13. 2017IQN: An Incremental Quasi-Newton Method with Local Superlinear Convergence Ratecited by 11
  14. 2014Finito: A Faster, Permutable Incremental Gradient Method for Big Data Problemscited by 10
  15. 2016Forward-backward quasi-Newton methods for nonsmooth optimization problemscited by 9
  16. 2016Forward-backward envelope for the sum of two nonconvex functions: Further properties and nonmonotone line-search algorithmscited by 8
  17. 2018Stochastic model-based minimization under high-order growthcited by 7
  18. 2019A Stochastic Extra-Step Quasi-Newton Method for Nonsmooth Nonconvex Optimizationcited by 7
  19. 2021Bregman Finito/MISO for nonconvex regularized finite sum minimization without Lipschitz gradient continuitycited by 7
  20. 2019A Bregman forward-backward linesearch algorithm for nonconvex composite optimization: superlinear convergence to nonisolated local minimacited by 6
  21. 2013On Stochastic Subgradient Mirror-Descent Algorithm with Weighted Averagingcited by 5
  22. 2017Proximal-Like Incremental Aggregated Gradient Method with Linear Convergence under Bregman Distance Growth Conditionscited by 5
  23. 2019Block-coordinate and incremental aggregated proximal gradient methods for nonsmooth nonconvex problemscited by 5
  24. 2016SuperMann: a superlinearly convergent algorithm for finding fixed points of nonexpansive operatorscited by 4
  25. 2021Alpaqa: A matrix-free solver for nonlinear MPC and large-scale nonconvex optimizationcited by 4
  26. 2021Proximal Gradient Algorithms under Local Lipschitz Gradient Continuity: A Convergence and Robustness Analysis of PANOCcited by 4
  27. 2022Variance-Reduced Stochastic Quasi-Newton Methods for Decentralized Learning: Part Icited by 4
  28. 2018On the acceleration of forward-backward splitting via an inexact Newton methodcited by 1
  29. 2021Hybrid Acceleration Scheme for Variance Reduced Stochastic Optimization Algorithmscited by 1

Built on by

Not cited yet.