Non-convex Finite-Sum Optimization Via SCSG Methods

Abstract

We develop a class of algorithms, as variants of the stochastically controlled stochastic gradient (SCSG) methods (Lei and Jordan, 2016), for the smooth non-convex finite-sum optimization problem. Assuming the smoothness of each component, the complexity of SCSG to reach a stationary point with $\mathbb{E}\Vert \nabla f(x){\Vert }^2\le \epsilon$ is $O\left(\min \{{\epsilon }^{-5/3},{\epsilon }^{-1}{n}^{2/3}\}\right)$, which strictly outperforms the stochastic gradient descent. Moreover, SCSG is never worse than the state-of-the-art methods based on variance reduction and it significantly outperforms them when the target accuracy is low. A similar acceleration is also achieved when the functions satisfy the Polyak-Lojasiewicz condition. Empirical experiments demonstrate that SCSG outperforms stochastic gradient methods on training multi-layers neural networks in terms of both training and validation loss.

Add Lemma B.1

References in corpus (3)

• Accelerated Methods for Non-Convex Optimization
• Natasha: Faster Non-Convex Stochastic Optimization Via Strongly Non-Convex Parameter
• "Convex Until Proven Guilty": Dimension-Free Acceleration of Gradient Descent on Non-Convex Functions

Cited by in corpus (52)

• An Energy Approach to the Solution of Partial Differential Equations in Computational Mechanics via Machine Learning: Concepts, Implementation and Applications
• Not All Samples Are Created Equal: Deep Learning with Importance Sampling
• On the Convergence of A Class of Adam-Type Algorithms for Non-Convex Optimization
• On the Convergence of Adaptive Gradient Methods for Nonconvex Optimization
• A Simple Proximal Stochastic Gradient Method for Nonsmooth Nonconvex Optimization
• Stochastic Recursive Gradient Descent Ascent for Stochastic Nonconvex-Strongly-Concave Minimax Problems
• Stochastic AUC Maximization with Deep Neural Networks
• Sample Efficient Policy Gradient Methods with Recursive Variance Reduction
• Natasha: Faster Non-Convex Stochastic Optimization Via Strongly Non-Convex Parameter
• SpiderBoost and Momentum: Faster Stochastic Variance Reduction Algorithms
• Laplacian Smoothing Gradient Descent
• On the Adaptivity of Stochastic Gradient-Based Optimization
• Estimate Sequences for Stochastic Composite Optimization: Variance Reduction, Acceleration, and Robustness to Noise
• Catalyst Acceleration for Gradient-Based Non-Convex Optimization
• Katyusha X: Practical Momentum Method for Stochastic Sum-of-Nonconvex Optimization
• First-order Stochastic Algorithms for Escaping From Saddle Points in Almost Linear Time
• Global Convergence of Arbitrary-Block Gradient Methods for Generalized Polyak-Łojasiewicz Functions
• Stochastic Zeroth-order Optimization via Variance Reduction method
• On the Ineffectiveness of Variance Reduced Optimization for Deep Learning
• Stochastic Conditional Gradient++
• Bias-Variance Reduced Local SGD for Less Heterogeneous Federated Learning
• Stagewise Training Accelerates Convergence of Testing Error Over SGD
• A Second look at Exponential and Cosine Step Sizes: Simplicity, Adaptivity, and Performance
• Improving the Sample and Communication Complexity for Decentralized Non-Convex Optimization: A Joint Gradient Estimation and Tracking Approach
• Finding Local Minima via Stochastic Nested Variance Reduction
• ZeroSARAH: Efficient Nonconvex Finite-Sum Optimization with Zero Full Gradient Computation
• Efficient Privacy-Preserving Stochastic Nonconvex Optimization
• An Adaptive Gradient Method with Energy and Momentum
• GENO -- GENeric Optimization for Classical Machine Learning
• Stochastically Controlled Stochastic Gradient for the Convex and Non-convex Composition problem
• A Hybrid Stochastic Optimization Framework for Stochastic Composite Nonconvex Optimization
• Escaping Saddle Points Faster with Stochastic Momentum
• A Stochastic Decoupling Method for Minimizing the Sum of Smooth and Non-Smooth Functions
• ANITA: An Optimal Loopless Accelerated Variance-Reduced Gradient Method
• Momentum-based variance-reduced proximal stochastic gradient method for composite nonconvex stochastic optimization
• Almost Tune-Free Variance Reduction
• Stochastic Variance-Reduced Hamilton Monte Carlo Methods
• Uniform Convergence of Gradients for Non-Convex Learning and Optimization
• On the Convergence of SARAH and Beyond
• Third-order Smoothness Helps: Even Faster Stochastic Optimization Algorithms for Finding Local Minima
• A Fast Anderson-Chebyshev Acceleration for Nonlinear Optimization
• Stochastic Gradient Descent for Stochastic Doubly-Nonconvex Composite Optimization
• Faster Stochastic Quasi-Newton Methods
• Data Sampling Strategies in Stochastic Algorithms for Empirical Risk Minimization
• Revisiting SGD with Increasingly Weighted Averaging: Optimization and Generalization Perspectives
• Fault-Tolerant Federated Reinforcement Learning with Theoretical Guarantee
• Bounding the expected run-time of nonconvex optimization with early stopping
• Effective Proximal Methods for Non-convex Non-smooth Regularized Learning
• Stochastic Approximation for Online Tensorial Independent Component Analysis
• Faster Perturbed Stochastic Gradient Methods for Finding Local Minima
• Towards Better Generalization: BP-SVRG in Training Deep Neural Networks
• Continuous-time Models for Stochastic Optimization Algorithms