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

Abstract

In this paper, we propose a new technique named \textit{Stochastic 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-SFO\textsuperscript{+}, 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-SFO\textsuperscript{+} algorithms achieve a record-breaking gradient computation cost of $\mathcal{O}\left(\min (n^{1/2}{\epsilon }^{-2},{\epsilon }^{-3})\right)$ for finding an $\epsilon$-approximate first-order and $\tilde{\mathcal{O}}\left(\min (n^{1/2}{\epsilon }^{-2}+{\epsilon }^{-2.5},{\epsilon }^{-3})\right)$ for finding an $(\epsilon ,\mathcal{O}({\epsilon }^{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 $\mathcal{O}(d\min (n^{1/2}{\epsilon }^{-2},{\epsilon }^{-3}))$ which outperforms all existing results.

References in corpus (21)

• SAGA: A Fast Incremental Gradient Method With Support for Non-Strongly Convex Composite Objectives
• Identifying and attacking the saddle point problem in high-dimensional non-convex optimization
• Non-convex Optimization for Machine Learning
• Stochastic Variance Reduction for Nonconvex Optimization
• An Optimal Algorithm for Bandit and Zero-Order Convex Optimization with Two-Point Feedback
• Variance Reduction for Faster Non-Convex Optimization
• SARAH: A Novel Method for Machine Learning Problems Using Stochastic Recursive Gradient
• The Power of Normalization: Faster Evasion of Saddle Points
• Stochastic Recursive Gradient Algorithm for Nonconvex Optimization
• Stochastic Nested Variance Reduction for Nonconvex Optimization
• Neon2: Finding Local Minima via First-Order Oracles
• Accelerated Methods for Non-Convex Optimization
• Accelerated Gradient Descent Escapes Saddle Points Faster than Gradient Descent
• Tight Complexity Bounds for Optimizing Composite Objectives
• Near-Optimal Stochastic Approximation for Online Principal Component Estimation
• Beyond Convexity: Stochastic Quasi-Convex Optimization
• "Convex Until Proven Guilty": Dimension-Free Acceleration of Gradient Descent on Non-Convex Functions
• A Generic Approach for Escaping Saddle points
• First-order Stochastic Algorithms for Escaping From Saddle Points in Almost Linear Time
• Lower Bound for Randomized First Order Convex Optimization
• Finding Local Minima via Stochastic Nested Variance Reduction

Cited by in corpus (79)

• SCAFFOLD: Stochastic Controlled Averaging for Federated Learning
• Why gradient clipping accelerates training: A theoretical justification for adaptivity
• On Nonconvex Optimization for Machine Learning: Gradients, Stochasticity, and Saddle Points
• Solving Stochastic Compositional Optimization is Nearly as Easy as Solving Stochastic Optimization
• Sample Efficient Policy Gradient Methods with Recursive Variance Reduction
• Momentum-Based Variance Reduction in Non-Convex SGD
• SpiderBoost and Momentum: Faster Stochastic Variance Reduction Algorithms
• Mathematical Models of Overparameterized Neural Networks
• Convergence of Distributed Stochastic Variance Reduced Methods without Sampling Extra Data
• Estimate Sequences for Stochastic Composite Optimization: Variance Reduction, Acceleration, and Robustness to Noise
• Hessian-Aware Zeroth-Order Optimization for Black-Box Adversarial Attack
• PAGE: A Simple and Optimal Probabilistic Gradient Estimator for Nonconvex Optimization
• Universal gradient descent
• On the Convergence and Sample Efficiency of Variance-Reduced Policy Gradient Method
• MARINA: Faster Non-Convex Distributed Learning with Compression
• Complexity of Finding Stationary Points of Nonsmooth Nonconvex Functions
• Stochastic Recursive Momentum for Policy Gradient Methods
• Stochastic Recursive Variance-Reduced Cubic Regularization Methods
• Stochastic Conditional Gradient++
• On Quantum Speedups for Nonconvex Optimization via Quantum Tunneling Walks
• Bias-Variance Reduced Local SGD for Less Heterogeneous Federated Learning
• Parallel Restarted SPIDER -- Communication Efficient Distributed Nonconvex Optimization with Optimal Computation Complexity
• Improving the Sample and Communication Complexity for Decentralized Non-Convex Optimization: A Joint Gradient Estimation and Tracking Approach
• ZeroSARAH: Efficient Nonconvex Finite-Sum Optimization with Zero Full Gradient Computation
• Efficient Privacy-Preserving Stochastic Nonconvex Optimization
• Fast decentralized non-convex finite-sum optimization with recursive variance reduction
• SPRING: A fast stochastic proximal alternating method for non-smooth non-convex optimization
• Faster Non-Convex Federated Learning via Global and Local Momentum
• Compositional ADAM: An Adaptive Compositional Solver
• History-Gradient Aided Batch Size Adaptation for Variance Reduced Algorithms
• Provably Faster Algorithms for Bilevel Optimization
• A Hybrid Stochastic Optimization Framework for Stochastic Composite Nonconvex Optimization
• A general sample complexity analysis of vanilla policy gradient
• On Biased Stochastic Gradient Estimation
• A Hybrid Variance-Reduced Method for Decentralized Stochastic Non-Convex Optimization
• Riemannian Stochastic Proximal Gradient Methods for Nonsmooth Optimization over the Stiefel Manifold
• A Hybrid Stochastic Policy Gradient Algorithm for Reinforcement Learning
• Random batch methods (RBM) for interacting particle systems
• Regret minimization in stochastic non-convex learning via a proximal-gradient approach
• ANITA: An Optimal Loopless Accelerated Variance-Reduced Gradient Method
• Almost Tune-Free Variance Reduction
• Fast Distributionally Robust Learning with Variance Reduced Min-Max Optimization
• Momentum-based variance-reduced proximal stochastic gradient method for composite nonconvex stochastic optimization
• Stochastic Variance-Reduced Prox-Linear Algorithms for Nonconvex Composite Optimization
• Gradient Free Minimax Optimization: Variance Reduction and Faster Convergence
• Projection-Free Adaptive Gradients for Large-Scale Optimization
• Nonconvex Zeroth-Order Stochastic ADMM Methods with Lower Function Query Complexity
• AdaGDA: Faster Adaptive Gradient Descent Ascent Methods for Minimax Optimization
• Implicit Regularization Properties of Variance Reduced Stochastic Mirror Descent
• Katalyst: Boosting Convex Katayusha for Non-Convex Problems with a Large Condition Number
• Enhanced Bilevel Optimization via Bregman Distance
• Deep Neural Network Training with Frank-Wolfe
• On the Convergence of SARAH and Beyond
• Escaping Saddle Points for Nonsmooth Weakly Convex Functions via Perturbed Proximal Algorithms
• Near Optimal Stochastic Algorithms for Finite-Sum Unbalanced Convex-Concave Minimax Optimization
• Half-Space Proximal Stochastic Gradient Method for Group-Sparsity Regularized Problem
• Variance Reduction on General Adaptive Stochastic Mirror Descent
• Multi-Level Composite Stochastic Optimization via Nested Variance Reduction
• Practical Schemes for Finding Near-Stationary Points of Convex Finite-Sums
• Proxy Convexity: A Unified Framework for the Analysis of Neural Networks Trained by Gradient Descent
• Variance-Reduced Stochastic Optimization for Efficient Inference of Hidden Markov Models
• Optimal Complexity in Decentralized Training
• Sample complexity of variance-reduced policy gradient: weaker assumptions and lower bounds
• Efficient preconditioned stochastic gradient descent for estimation in latent variable models
• Faster Stochastic Quasi-Newton Methods
• Random-reshuffled SARAH does not need a full gradient computations
• Three Operator Splitting with a Nonconvex Loss Function
• On the Oracle Complexity of Higher-Order Smooth Non-Convex Finite-Sum Optimization
• A Fast Anderson-Chebyshev Acceleration for Nonlinear Optimization
• Statistical Inference for Polyak-Ruppert Averaged Zeroth-order Stochastic Gradient Algorithm
• On the Importance of Sampling in Training GCNs: Tighter Analysis and Variance Reduction
• Bregman Gradient Policy Optimization
• Characterization of Excess Risk for Locally Strongly Convex Population Risk
• Scalable Projection-Free Optimization
• Momentum Improves Normalized SGD
• Faster Perturbed Stochastic Gradient Methods for Finding Local Minima
• Tight Lower Complexity Bounds for Strongly Convex Finite-Sum Optimization
• Fast Incremental Expectation Maximization for finite-sum optimization: nonasymptotic convergence
• Stochastic Approximation for Online Tensorial Independent Component Analysis