# SPIDER: Near-Optimal Non-Convex Optimization via Stochastic Path Integrated Differential Estimator

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

## Key facts

- Cited by 287 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 4 Jul 2018.

## Built on by (most cited first, 30 of 287)

- [Exploring Deep Neural Networks via Layer-Peeled Model: Minority Collapse in Imbalanced Training](https://mlsanity.com/paper/2101.12699/) (2021)
- [A Near-Optimal Algorithm for Stochastic Bilevel Optimization via Double-Momentum](https://mlsanity.com/paper/2102.07367/) (2021)
- [Provably Faster Algorithms for Bilevel Optimization](https://mlsanity.com/paper/2106.04692/) (2021)
- [AUC Maximization in the Era of Big Data and AI: A Survey](https://mlsanity.com/paper/2203.15046/) (2022)
- [A framework for bilevel optimization that enables stochastic and global variance reduction algorithms](https://mlsanity.com/paper/2201.13409/) (2022)
- [Convergence of Adam Under Relaxed Assumptions](https://mlsanity.com/paper/2304.13972/) (2023)
- [Private Stochastic Convex Optimization: Optimal Rates in ℓ1 Geometry](https://mlsanity.com/paper/2103.01516/) (2021)
- [MARINA: Faster Non-Convex Distributed Learning with Compression](https://mlsanity.com/paper/2102.07845/) (2021)
- [A general sample complexity analysis of vanilla policy gradient](https://mlsanity.com/paper/2107.11433/) (2021)
- [On the Convergence and Sample Efficiency of Variance-Reduced Policy Gradient Method](https://mlsanity.com/paper/2102.08607/) (2021)
- [Only Train Once: A One-Shot Neural Network Training And Pruning Framework](https://mlsanity.com/paper/2107.07467/) (2021)
- [An Improved Analysis of (Variance-Reduced) Policy Gradient and Natural Policy Gradient Methods](https://mlsanity.com/paper/2211.07937/) (2022)
- [FedVARP: Tackling the Variance Due to Partial Client Participation in Federated Learning](https://mlsanity.com/paper/2207.14130/) (2022)
- [MARS: Unleashing the Power of Variance Reduction for Training Large Models](https://mlsanity.com/paper/2411.10438/) (2024)
- [Stochastic Policy Gradient Methods: Improved Sample Complexity for Fisher-non-degenerate Policies](https://mlsanity.com/paper/2302.01734/) (2023)
- [Non-Euclidean Differentially Private Stochastic Convex Optimization: Optimal Rates in Linear Time](https://mlsanity.com/paper/2103.01278/) (2021)
- [A Novel Convergence Analysis for Algorithms of the Adam Family](https://mlsanity.com/paper/2112.03459/) (2021)
- [The Complexity of Nonconvex-Strongly-Concave Minimax Optimization](https://mlsanity.com/paper/2103.15888/) (2021)
- [Differentially Private Stochastic Optimization: New Results in Convex and Non-Convex Settings](https://mlsanity.com/paper/2107.05585/) (2021)
- [Optimal Stochastic Non-smooth Non-convex Optimization through Online-to-Non-convex Conversion](https://mlsanity.com/paper/2302.03775/) (2023)
- [STEM: A Stochastic Two-Sided Momentum Algorithm Achieving Near-Optimal Sample and Communication Complexities for Federated Learning](https://mlsanity.com/paper/2106.10435/) (2021)
- [An Introduction to Bi-level Optimization: Foundations and Applications in Signal Processing and Machine Learning](https://mlsanity.com/paper/2308.00788/) (2023)
- [Lions and Muons: Optimization via Stochastic Frank-Wolfe under Heavy-Tailed Noise](https://mlsanity.com/paper/2506.04192/) (2025)
- [SUPER-ADAM: Faster and Universal Framework of Adaptive Gradients](https://mlsanity.com/paper/2106.08208/) (2021)
- [Momentum Benefits Non-IID Federated Learning Simply and Provably](https://mlsanity.com/paper/2306.16504/) (2023)
- [Complexity Lower Bounds for Nonconvex-Strongly-Concave Min-Max Optimization](https://mlsanity.com/paper/2104.08708/) (2021)
- [On Improving Model-Free Algorithms for Decentralized Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/2110.05707/) (2021)
- [Faster Adaptive Federated Learning](https://mlsanity.com/paper/2212.00974/) (2022)
- [Randomized Stochastic Variance-Reduced Methods for Multi-Task Stochastic Bilevel Optimization](https://mlsanity.com/paper/2105.02266/) (2021)
- [Lower Bounds and Nearly Optimal Algorithms in Distributed Learning with Communication Compression](https://mlsanity.com/paper/2206.03665/) (2022)

## Abstract (arXiv)

In this paper, we propose a new technique named textitStochastic Path-Integrated Differential EstimatoR (SPIDER), which can be used to track many deterministic quantities of interest with significantly reduced computational cost. We apply SPIDER to two tasks, namely the stochastic first-order and zeroth-order methods. For stochastic first-order method, combining SPIDER with normalized gradient descent, we propose two new algorithms, namely SPIDER-SFO and SPIDER-SFOtextsuperscript+, that solve non-convex stochastic optimization problems using stochastic gradients only. We provide sharp error-bound results on their convergence rates. In special, we prove that the SPIDER-SFO and SPIDER-SFOtextsuperscript+ algorithms achieve a record-breaking gradient computation cost of Oleft( min( n1/2 ε-2, ε-3 ) right) for finding an ε-approximate first-order and tildeOleft( min( n1/2 ε-2+ε-2.5, ε-3 ) right) for finding an (ε, O(ε0.5))-approximate second-order stationary point, respectively. In addition, we prove that SPIDER-SFO nearly matches the algorithmic lower bound for finding approximate first-order stationary points under the gradient Lipschitz assumption in the finite-sum setting. For stochastic zeroth-order method, we prove a cost of O( d min( n1/2 ε-2, ε-3) ) which outperforms all existing results.