A Stochastic Gradient Method with an Exponential Convergence Rate for Finite Training Sets
arXiv:1202.6258
Abstract
We propose a new stochastic gradient method for optimizing the sum of a finite set of smooth functions, where the sum is strongly convex. While standard stochastic gradient methods converge at sublinear rates for this problem, the proposed method incorporates a memory of previous gradient values in order to achieve a linear convergence rate. In a machine learning context, numerical experiments indicate that the new algorithm can dramatically outperform standard algorithms, both in terms of optimizing the training error and reducing the test error quickly.
The notable changes over the current version: - worked example of convergence rates showing SAG can be faster than first-order methods - pointing out that the storage cost is O(n) for linear models - the more-stable line-search - comparison to additional optimal SG methods - comparison to rates of coordinate descent methods in quadratic case
References in corpus (2)
Cited by in corpus (199)
- Convex Optimization for Big Data
- Mini-Batch Semi-Stochastic Gradient Descent in the Proximal Setting
- A Linearly-Convergent Stochastic L-BFGS Algorithm
- DSA: Decentralized Double Stochastic Averaging Gradient Algorithm
- Barzilai-Borwein Step Size for Stochastic Gradient Descent
- Optimization with First-Order Surrogate Functions
- Why Random Reshuffling Beats Stochastic Gradient Descent
- Stochastic Majorization-Minimization Algorithms for Large-Scale Optimization
- Stochastic Primal-Dual Coordinate Method for Regularized Empirical Risk Minimization
- Stochastic Conjugate Gradient Algorithm with Variance Reduction
- Stochastic Distributed Learning with Gradient Quantization and Variance Reduction
- SARAH: A Novel Method for Machine Learning Problems Using Stochastic Recursive Gradient
- Fast large-scale optimization by unifying stochastic gradient and quasi-Newton methods
- Riemannian stochastic variance reduced gradient algorithm with retraction and vector transport
- High-Accuracy Low-Precision Training
- Stochastic Optimization with Importance Sampling
- A Simple Stochastic Variance Reduced Algorithm with Fast Convergence Rates
- A Tight Bound of Hard Thresholding
- Sub-Sampled Newton Methods II: Local Convergence Rates
- Fast and Simple PCA via Convex Optimization
- Strong error analysis for stochastic gradient descent optimization algorithms
- Stochastic Averaging for Constrained Optimization with Application to Online Resource Allocation
- Steps Toward Deep Kernel Methods from Infinite Neural Networks
- A Lower Bound for the Optimization of Finite Sums
- A Survey of Optimization Methods from a Machine Learning Perspective
- Distributed Stochastic Variance Reduced Gradient Methods and A Lower Bound for Communication Complexity
- Large-Scale Approximate Kernel Canonical Correlation Analysis
- A globally convergent incremental Newton method
- An Accelerated Proximal Coordinate Gradient Method and its Application to Regularized Empirical Risk Minimization
- Kalman-based Stochastic Gradient Method with Stop Condition and Insensitivity to Conditioning
- SDCA without Duality
- SDCA without Duality, Regularization, and Individual Convexity
- Nonconvex Sparse Learning via Stochastic Optimization with Progressive Variance Reduction
- SpiderBoost and Momentum: Faster Stochastic Variance Reduction Algorithms
- The Impact of the Mini-batch Size on the Variance of Gradients in Stochastic Gradient Descent
- A Variance Reduced Stochastic Newton Method
- Randomized Block Coordinate Descent for Online and Stochastic Optimization
- On the Adaptivity of Stochastic Gradient-Based Optimization
- A Proximal Stochastic Gradient Method with Progressive Variance Reduction
- Enhancing the Transferability of Adversarial Attacks through Variance Tuning
- A Unified Convergence Analysis for Shuffling-Type Gradient Methods
- Linear Convergence of Variance-Reduced Stochastic Gradient without Strong Convexity
- Decentralized Stochastic Gradient Tracking for Non-convex Empirical Risk Minimization
- Accelerated Variance Reduced Stochastic ADMM
- Solving Empirical Risk Minimization in the Current Matrix Multiplication Time
- A Selective Review on Statistical Methods for Massive Data Computation: Distributed Computing, Subsampling, and Minibatch Techniques
- Stochastic Variance Reduction Methods for Saddle-Point Problems
- Asynchronous Stochastic Gradient Descent with Variance Reduction for Non-Convex Optimization
- On Linear Stochastic Approximation: Fine-grained Polyak-Ruppert and Non-Asymptotic Concentration
- Linear Convergence of the Primal-Dual Gradient Method for Convex-Concave Saddle Point Problems without Strong Convexity
- Least Squares Revisited: Scalable Approaches for Multi-class Prediction
- KKT Conditions, First-Order and Second-Order Optimization, and Distributed Optimization: Tutorial and Survey
- Scaling Limit: Exact and Tractable Analysis of Online Learning Algorithms with Applications to Regularized Regression and PCA
- Without-Replacement Sampling for Stochastic Gradient Methods: Convergence Results and Application to Distributed Optimization
- Active Importance Sampling for Variational Objectives Dominated by Rare Events: Consequences for Optimization and Generalization
- Statistical Inference for the Population Landscape via Moment Adjusted Stochastic Gradients
- A Unified Theory of SGD: Variance Reduction, Sampling, Quantization and Coordinate Descent
- Scalable Stochastic Alternating Direction Method of Multipliers
- Incremental Majorization-Minimization Optimization with Application to Large-Scale Machine Learning
- Less than a Single Pass: Stochastically Controlled Stochastic Gradient Method
- Tight Dimension Independent Lower Bound on the Expected Convergence Rate for Diminishing Step Sizes in SGD
- Stochastic Newton and Cubic Newton Methods with Simple Local Linear-Quadratic Rates
- Breaking the Nonsmooth Barrier: A Scalable Parallel Method for Composite Optimization
- Robust, Accurate Stochastic Optimization for Variational Inference
- Never look back - A modified EnKF method and its application to the training of neural networks without back propagation
- On Fast Leverage Score Sampling and Optimal Learning
- Stochastic Recursive Variance-Reduced Cubic Regularization Methods
- DAve-QN: A Distributed Averaged Quasi-Newton Method with Local Superlinear Convergence Rate
- Convergence Rates of Accelerated Markov Gradient Descent with Applications in Reinforcement Learning
- VR-SGD: A Simple Stochastic Variance Reduction Method for Machine Learning
- A Study of Gradient Variance in Deep Learning
- Starting Small -- Learning with Adaptive Sample Sizes
- Reducing the variance in online optimization by transporting past gradients
- Federated Optimization of Smooth Loss Functions
- Efficient Distributed Hessian Free Algorithm for Large-scale Empirical Risk Minimization via Accumulating Sample Strategy
- Variance-Reduced Stochastic Learning under Random Reshuffling
- A stochastic variational framework for fitting and diagnosing generalized linear mixed models
- MixedGrad: An O(1/T) Convergence Rate Algorithm for Stochastic Smooth Optimization
- New Convergence Aspects of Stochastic Gradient Algorithms
- Don't Jump Through Hoops and Remove Those Loops: SVRG and Katyusha are Better Without the Outer Loop
- One Method to Rule Them All: Variance Reduction for Data, Parameters and Many New Methods
- Riemannian stochastic variance reduced gradient on Grassmann manifold
- Stabilized SVRG: Simple Variance Reduction for Nonconvex Optimization
- Accelerate Stochastic Subgradient Method by Leveraging Local Growth Condition
- An ODE Method to Prove the Geometric Convergence of Adaptive Stochastic Algorithms
- Mini-Batch Stochastic ADMMs for Nonconvex Nonsmooth Optimization
- History-Gradient Aided Batch Size Adaptation for Variance Reduced Algorithms
- Towards closing the gap between the theory and practice of SVRG
- TAdam: A Robust Stochastic Gradient Optimizer
- A Survey of Latent Factor Models in Recommender Systems
- Stochastic Subspace Descent
- Advances in Asynchronous Parallel and Distributed Optimization
- Lower Bounds for Smooth Nonconvex Finite-Sum Optimization
- Analysis of regularized federated learning
- Distributed Inexact Damped Newton Method: Data Partitioning and Load-Balancing
- Guaranteed Sufficient Decrease for Stochastic Variance Reduced Gradient Optimization
- A Stochastic Decoupling Method for Minimizing the Sum of Smooth and Non-Smooth Functions
- ANITA: An Optimal Loopless Accelerated Variance-Reduced Gradient Method
- Accelerating Minibatch Stochastic Gradient Descent using Typicality Sampling
- Linear Convergence of Adaptive Stochastic Gradient Descent
- When Naïve Bayes Nearest Neighbours Meet Convolutional Neural Networks
- Anarchic Federated Learning
- Almost Tune-Free Variance Reduction
- Stochastic Variance-Reduced ADMM
- Topology Optimization under Uncertainty using a Stochastic Gradient-based Approach
- Stochastic Variance-Reduced Hamilton Monte Carlo Methods
- Adaptive Step Sizes in Variance Reduction via Regularization
- Online Nonnegative Matrix Factorization with General Divergences
- On Projected Stochastic Gradient Descent Algorithm with Weighted Averaging for Least Squares Regression
- Fast Asynchronous Parallel Stochastic Gradient Decent
- D-SPIDER-SFO: A Decentralized Optimization Algorithm with Faster Convergence Rate for Nonconvex Problems
- A variable metric mini-batch proximal stochastic recursive gradient algorithm with diagonal Barzilai-Borwein stepsize
- Large Scale Empirical Risk Minimization via Truncated Adaptive Newton Method
- Distributed Inexact Successive Convex Approximation ADMM: Analysis-Part I
- Adaptive Sampling Distributed Stochastic Variance Reduced Gradient for Heterogeneous Distributed Datasets
- Learning with risks based on M-location
- On the Convergence of SARAH and Beyond
- A Proximal Stochastic Quasi-Newton Algorithm
- Hot Swapping for Online Adaptation of Optimization Hyperparameters
- Spatial-Spectral Boosting Analysis for Stroke Patients' Motor Imagery EEG in Rehabilitation Training
- Katalyst: Boosting Convex Katayusha for Non-Convex Problems with a Large Condition Number
- Variance Reduction for Deep Q-Learning using Stochastic Recursive Gradient
- Momentum with Variance Reduction for Nonconvex Composition Optimization
- Linearly Convergent Algorithm with Variance Reduction for Distributed Stochastic Optimization
- Variance Reduction with Sparse Gradients
- Exploiting Smoothness in Statistical Learning, Sequential Prediction, and Stochastic Optimization
- Stochasticity of Deterministic Gradient Descent: Large Learning Rate for Multiscale Objective Function
- Stochastic Reweighted Gradient Descent
- Bi-fidelity Stochastic Gradient Descent for Structural Optimization under Uncertainty
- Adaptive Newton Method for Empirical Risk Minimization to Statistical Accuracy
- Curvature-aided Incremental Aggregated Gradient Method
- Understanding and Detecting Convergence for Stochastic Gradient Descent with Momentum
- Condition Number Analysis of Logistic Regression, and its Implications for Standard First-Order Solution Methods
- Stochastic inertial primal-dual algorithms
- Revisiting Sub-sampled Newton Methods
- Stochastic Bound Majorization
- Variance Reduction via Primal-Dual Accelerated Dual Averaging for Nonsmooth Convex Finite-Sums
- Stable deep reinforcement learning method by predicting uncertainty in rewards as a subtask
- Half-Space Proximal Stochastic Gradient Method for Group-Sparsity Regularized Problem
- A Stochastic Variance Reduced Nesterov's Accelerated Quasi-Newton Method
- Drill the Cork of Information Bottleneck by Inputting the Most Important Data
- Multi-Level Composite Stochastic Optimization via Nested Variance Reduction
- A Unifying Framework for Variance Reduction Algorithms for Finding Zeroes of Monotone Operators
- Asynchronous Distributed Optimization with Redundancy in Cost Functions
- Characterization of Convex Objective Functions and Optimal Expected Convergence Rates for SGD
- Variance Reduced Coordinate Descent with Acceleration: New Method With a Surprising Application to Finite-Sum Problems
- Reducing Runtime by Recycling Samples
- Accelerating Mini-batch SARAH by Step Size Rules
- ADINE: An Adaptive Momentum Method for Stochastic Gradient Descent
- Sample complexity of variance-reduced policy gradient: weaker assumptions and lower bounds
- Stochastic First-Order Minimization Techniques Using Jensen Surrogates for X-Ray Transmission Tomography
- On the Generalization of Models Trained with SGD: Information-Theoretic Bounds and Implications
- Asynchronous Distributed Optimization with Stochastic Delays
- Stochastic Variance Reduction Gradient for a Non-convex Problem Using Graduated Optimization
- Stochastic Approximation of Smooth and Strongly Convex Functions: Beyond the Convergence Rate
- Dual Free Adaptive Mini-batch SDCA for Empirical Risk Minimization
- Stochastic Dykstra Algorithms for Metric Learning on Positive Semi-Definite Cone
- HAMSI: A Parallel Incremental Optimization Algorithm Using Quadratic Approximations for Solving Partially Separable Problems
- Three Operator Splitting with a Nonconvex Loss Function
- Accelerated Randomized Coordinate Descent Algorithms for Stochastic Optimization and Online Learning
- Hybrid Acceleration Scheme for Variance Reduced Stochastic Optimization Algorithms
- Carathéodory Sampling for Stochastic Gradient Descent
- Random Reshuffling with Variance Reduction: New Analysis and Better Rates
- AutoDrop: Training Deep Learning Models with Automatic Learning Rate Drop
- Stochastic variance reduced multiplicative update for nonnegative matrix factorization
- Constant Time EXPected Similarity Estimation using Stochastic Optimization
- Memory Augmented Optimizers for Deep Learning
- Stochastic Gradient Descent for Stochastic Doubly-Nonconvex Composite Optimization
- Boosting First-Order Methods by Shifting Objective: New Schemes with Faster Worst-Case Rates
- Acceleration of SVRG and Katyusha X by Inexact Preconditioning
- Exploiting Uncertainty of Loss Landscape for Stochastic Optimization
- Learning Sign-Constrained Support Vector Machines
- Improved SVRG for quadratic functions
- Practical Newton-Type Distributed Learning using Gradient Based Approximations
- Variance Reduction in Deep Learning: More Momentum is All You Need
- Block-Cyclic Stochastic Coordinate Descent for Deep Neural Networks
- Tracking Moving Agents via Inexact Online Gradient Descent Algorithm
- Structure-Adaptive, Variance-Reduced, and Accelerated Stochastic Optimization
- Rapid Aerodynamic Shape Optimization Under Parametric and Turbulence Model Uncertainty: A Stochastic Gradient Approach
- Projected Semi-Stochastic Gradient Descent Method with Mini-Batch Scheme under Weak Strong Convexity Assumption
- Optimization for Supervised Machine Learning: Randomized Algorithms for Data and Parameters
- Accelerated Kaczmarz Algorithms using History Information
- Variance reduction for dependent sequences with applications to Stochastic Gradient MCMC
- Learn-and-Adapt Stochastic Dual Gradients for Network Resource Allocation
- Lightweight Stochastic Optimization for Minimizing Finite Sums with Infinite Data
- Compositional Stochastic Average Gradient for Machine Learning and Related Applications
- Accelerated Randomized Mirror Descent Algorithms For Composite Non-strongly Convex Optimization
- Homeomorphic-Invariance of EM: Non-Asymptotic Convergence in KL Divergence for Exponential Families via Mirror Descent
- Discriminative Bayesian filtering lends momentum to the stochastic Newton method for minimizing log-convex functions
- :An Unbiased Stratified Statistic and a Fast Gradient Optimization Algorithm Based on It
- Accelerating Perturbed Stochastic Iterates in Asynchronous Lock-Free Optimization
- Continuous-time Models for Stochastic Optimization Algorithms
- Stochastic dual averaging methods using variance reduction techniques for regularized empirical risk minimization problems
- Stochastic Doubly Robust Gradient
- L-DQN: An Asynchronous Limited-Memory Distributed Quasi-Newton Method
- Characterization of Excess Risk for Locally Strongly Convex Population Risk
- Exploiting Local Convergence of Quasi-Newton Methods Globally: Adaptive Sample Size Approach
- Adaptive Weight Decay for Deep Neural Networks
- Training Efficiency and Robustness in Deep Learning