Making Gradient Descent Optimal for Strongly Convex Stochastic Optimization

Abstract

Stochastic gradient descent (SGD) is a simple and popular method to solve stochastic optimization problems which arise in machine learning. For strongly convex problems, its convergence rate was known to be O(\log(T)/T), by running SGD for T iterations and returning the average point. However, recent results showed that using a different algorithm, one can get an optimal O(1/T) rate. This might lead one to believe that standard SGD is suboptimal, and maybe should even be replaced as a method of choice. In this paper, we investigate the optimality of SGD in a stochastic setting. We show that for smooth problems, the algorithm attains the optimal O(1/T) rate. However, for non-smooth problems, the convergence rate with averaging might really be Ω(\log(T)/T), and this is not just an artifact of the analysis. On the flip side, we show that a simple modification of the averaging step suffices to recover the O(1/T) rate, and no other change of the algorithm is necessary. We also present experimental results which support our findings, and point out open problems.

Updated version which fixes a bug in the proof of lemma 1 and modifies the step size choice. As a result, constants are changed throughout the paper

References in corpus (1)

• Primal-dual subgradient methods for minimizing uniformly convex functions

Cited by in corpus (203)

• Federated Learning with Non-IID Data
• Communication Efficient Distributed Optimization using an Approximate Newton-type Method
• Train faster, generalize better: Stability of stochastic gradient descent
• Local SGD Converges Fast and Communicates Little
• Escaping From Saddle Points --- Online Stochastic Gradient for Tensor Decomposition
• Byzantine Stochastic Gradient Descent
• A Unified Theory of Decentralized SGD with Changing Topology and Local Updates
• Block-Coordinate Frank-Wolfe Optimization for Structural SVMs
• Taming the Wild: A Unified Analysis of Hogwild!-Style Algorithms
• Why Random Reshuffling Beats Stochastic Gradient Descent
• The Non-IID Data Quagmire of Decentralized Machine Learning
• Mini-Batch Primal and Dual Methods for SVMs
• On the Complexity of Bandit and Derivative-Free Stochastic Convex Optimization
• Accelerating Minibatch Stochastic Gradient Descent using Stratified Sampling
• Scalable Kernel Methods via Doubly Stochastic Gradients
• The Step Decay Schedule: A Near Optimal, Geometrically Decaying Learning Rate Procedure For Least Squares
• Stochastic Optimization with Importance Sampling
• Better Theory for SGD in the Nonconvex World
• Semi-Supervised AUC Optimization based on Positive-Unlabeled Learning
• On Graduated Optimization for Stochastic Non-Convex Problems
• Strong error analysis for stochastic gradient descent optimization algorithms
• Unified Optimal Analysis of the (Stochastic) Gradient Method
• Communication Efficient Federated Learning over Multiple Access Channels
• Adam revisited: a weighted past gradients perspective
• Near-Optimal Stochastic Approximation for Online Principal Component Estimation
• Where to Go Next: A Spatio-temporal LSTM model for Next POI Recommendation
• Model Pruning Enables Localized and Efficient Federated Learning for Yield Forecasting and Data Sharing
• Stochastic subgradient method converges at the rate $O(k^{-1/4})$ on weakly convex functions
• Big Batch SGD: Automated Inference using Adaptive Batch Sizes
• Stochastic Polyak Step-size for SGD: An Adaptive Learning Rate for Fast Convergence
• Asymmetric Valleys: Beyond Sharp and Flat Local Minima
• SGD: General Analysis and Improved Rates
• A Sharp Estimate on the Transient Time of Distributed Stochastic Gradient Descent
• The proximal point method revisited
• Random Reshuffling: Simple Analysis with Vast Improvements
• Lower error bounds for the stochastic gradient descent optimization algorithm: Sharp convergence rates for slowly and fast decaying learning rates
• Competing with the Empirical Risk Minimizer in a Single Pass
• Statistical Inference for Model Parameters in Stochastic Gradient Descent
• HiGrad: Uncertainty Quantification for Online Learning and Stochastic Approximation
• A Variance Reduced Stochastic Newton Method
• On Distributed Online Classification in the Midst of Concept Drifts
• On the Adaptivity of Stochastic Gradient-Based Optimization
• Linear Convergence of Variance-Reduced Stochastic Gradient without Strong Convexity
• Stochastic Optimization for Performative Prediction
• Wireless Federated Learning with Local Differential Privacy
• Accelerating Stochastic Composition Optimization
• Universal gradient descent
• Tight Analyses for Non-Smooth Stochastic Gradient Descent
• On Linear Stochastic Approximation: Fine-grained Polyak-Ruppert and Non-Asymptotic Concentration
• MetaGrad: Multiple Learning Rates in Online Learning
• Fast Stochastic Variance Reduced Gradient Method with Momentum Acceleration for Machine Learning
• Random Multi-Constraint Projection: Stochastic Gradient Methods for Convex Optimization with Many Constraints
• Rivalry of Two Families of Algorithms for Memory-Restricted Streaming PCA
• On the Outsized Importance of Learning Rates in Local Update Methods
• Scaling Limit: Exact and Tractable Analysis of Online Learning Algorithms with Applications to Regularized Regression and PCA
• Fast and Robust Online Inference with Stochastic Gradient Descent via Random Scaling
• Without-Replacement Sampling for Stochastic Gradient Methods: Convergence Results and Application to Distributed Optimization
• Communication trade-offs for synchronized distributed SGD with large step size
• Exploiting Higher Order Smoothness in Derivative-free Optimization and Continuous Bandits
• Generalization of ERM in Stochastic Convex Optimization: The Dimension Strikes Back
• Sharp Analysis for Nonconvex SGD Escaping from Saddle Points
• The Strength of Nesterov's Extrapolation in the Individual Convergence of Nonsmooth Optimization
• Optimal Rates for Averaged Stochastic Gradient Descent under Neural Tangent Kernel Regime
• Communication-efficient distributed SGD with Sketching
• Less than a Single Pass: Stochastically Controlled Stochastic Gradient Method
• CAFE: Catastrophic Data Leakage in Vertical Federated Learning
• Splash: User-friendly Programming Interface for Parallelizing Stochastic Algorithms
• LoAdaBoost: loss-based AdaBoost federated machine learning with reduced computational complexity on IID and non-IID intensive care data
• LASG: Lazily Aggregated Stochastic Gradients for Communication-Efficient Distributed Learning
• On the existence of global minima and convergence analyses for gradient descent methods in the training of deep neural networks
• Stochastic gradient methods with inexact oracle
• SPARQ-SGD: Event-Triggered and Compressed Communication in Decentralized Stochastic Optimization
• A proof of convergence for stochastic gradient descent in the training of artificial neural networks with ReLU activation for constant target functions
• Distributed Stochastic Gradient Tracking Methods
• Fine-Grained Analysis of Stability and Generalization for Stochastic Gradient Descent
• The Complexity of Finding Stationary Points with Stochastic Gradient Descent
• The Gap Between Model-Based and Model-Free Methods on the Linear Quadratic Regulator: An Asymptotic Viewpoint
• Learning by Minimizing the Sum of Ranked Range
• Minimax Estimation for Personalized Federated Learning: An Alternative between FedAvg and Local Training?
• New Convergence Aspects of Stochastic Gradient Algorithms
• Convergence of Adam for Non-convex Objectives: Relaxed Hyperparameters and Non-ergodic Case
• MixedGrad: An O(1/T) Convergence Rate Algorithm for Stochastic Smooth Optimization
• Stochastic Optimization with Heavy-Tailed Noise via Accelerated Gradient Clipping
• Simple and optimal high-probability bounds for strongly-convex stochastic gradient descent
• Convergence and Margin of Adversarial Training on Separable Data
• Stochastic Gradient Descent for Nonconvex Learning without Bounded Gradient Assumptions
• Customized Local Differential Privacy for Multi-Agent Distributed Optimization
• O(logT) Projections for Stochastic Optimization of Smooth and Strongly Convex Functions
• Learning Rates as a Function of Batch Size: A Random Matrix Theory Approach to Neural Network Training
• Accelerate Stochastic Subgradient Method by Leveraging Local Growth Condition
• Dynamic of Stochastic Gradient Descent with State-Dependent Noise
• On Data Dependence in Distributed Stochastic Optimization
• Online Stochastic Optimization with Multiple Objectives
• Bidirectional compression in heterogeneous settings for distributed or federated learning with partial participation: tight convergence guarantees
• Improved OOD Generalization via Adversarial Training and Pre-training
• Asymptotic Analysis via Stochastic Differential Equations of Gradient Descent Algorithms in Statistical and Computational Paradigms
• Layered SGD: A Decentralized and Synchronous SGD Algorithm for Scalable Deep Neural Network Training
• Complexity of finding near-stationary points of convex functions stochastically
• Outlier Robust Online Learning
• Stochastic Gradient Descent with Polyak's Learning Rate
• Guaranteed Sufficient Decrease for Stochastic Variance Reduced Gradient Optimization
• Convergence of Stochastic Gradient Descent for PCA
• About accelerated randomized methods
• The Role of Momentum Parameters in the Optimal Convergence of Adaptive Polyak's Heavy-ball Methods
• Uniform-in-Time Weak Error Analysis for Stochastic Gradient Descent Algorithms via Diffusion Approximation
• Stochastic Compositional Gradient Descent: Algorithms for Minimizing Compositions of Expected-Value Functions
• SGD for Structured Nonconvex Functions: Learning Rates, Minibatching and Interpolation
• Stochastic Iterative Hard Thresholding for Graph-structured Sparsity Optimization
• Existence, uniqueness, and convergence rates for gradient flows in the training of artificial neural networks with ReLU activation
• Optimal quantization of the mean measure and applications to statistical learning
• Nesterov's method with decreasing learning rate leads to accelerated stochastic gradient descent
• Robust Optimization over Multiple Domains
• Generalized Linear Bandits with Local Differential Privacy
• Beating SGD Saturation with Tail-Averaging and Minibatching
• Randomized Block Subgradient Methods for Convex Nonsmooth and Stochastic Optimization
• Maximum likelihood estimation of regularisation parameters in high-dimensional inverse problems: an empirical Bayesian approach. Part I: Methodology and Experiments
• Differentially Private SGD with Non-Smooth Losses
• Convergence of Unregularized Online Learning Algorithms
• Provable Smoothness Guarantees for Black-Box Variational Inference
• How Good is SGD with Random Shuffling?
• Fast Rates of ERM and Stochastic Approximation: Adaptive to Error Bound Conditions
• On the Convergence of Stochastic Gradient Descent with Bandwidth-based Step Size
• Optimal Distributed Stochastic Mirror Descent for Strongly Convex Optimization
• Asymptotic Network Independence in Distributed Stochastic Optimization for Machine Learning
• On Projected Stochastic Gradient Descent Algorithm with Weighted Averaging for Least Squares Regression
• Generalization of Model-Agnostic Meta-Learning Algorithms: Recurring and Unseen Tasks
• Improved Learning Rates for Stochastic Optimization
• Online Covariance Matrix Estimation in Stochastic Gradient Descent
• Stability of SGD: Tightness Analysis and Improved Bounds
• On the Convergence of Step Decay Step-Size for Stochastic Optimization
• Maximum likelihood estimation of regularisation parameters in high-dimensional inverse problems: an empirical Bayesian approach. Part II: Theoretical Analysis
• Approximation Vector Machines for Large-scale Online Learning
• On Stochastic Subgradient Mirror-Descent Algorithm with Weighted Averaging
• Passive Learning with Target Risk
• A Fully Stochastic Second-Order Trust Region Method
• Exploiting Smoothness in Statistical Learning, Sequential Prediction, and Stochastic Optimization
• Stochastic Proximal AUC Maximization
• Query-based Interactive Recommendation by Meta-Path and Adapted Attention-GRU
• Decentralized Differentially Private Without-Replacement Stochastic Gradient Descent
• Random Shuffling Beats SGD Only After Many Epochs on Ill-Conditioned Problems
• Large-scale Distance Metric Learning with Uncertainty
• Stochastic Gradient Descent in Hilbert Scales: Smoothness, Preconditioning and Earlier Stopping
• Error Lower Bounds of Constant Step-size Stochastic Gradient Descent
• Sentiment Analysis by Joint Learning of Word Embeddings and Classifier
• Time-Delay Momentum: A Regularization Perspective on the Convergence and Generalization of Stochastic Momentum for Deep Learning
• Searching equillibriums in large transport networks
• A Hybrid-Order Distributed SGD Method for Non-Convex Optimization to Balance Communication Overhead, Computational Complexity, and Convergence Rate
• Stability and Optimization Error of Stochastic Gradient Descent for Pairwise Learning
• A proof of convergence for the gradient descent optimization method with random initializations in the training of neural networks with ReLU activation for piecewise linear target functions
• Reducing Runtime by Recycling Samples
• Convergence rate of stochastic k-means
• On Faster Convergence of Scaled Sign Gradient Descent
• Stochastic Gradient Descent-Ascent and Consensus Optimization for Smooth Games: Convergence Analysis under Expected Co-coercivity
• Stochastic Gradient Descent on a Tree: an Adaptive and Robust Approach to Stochastic Convex Optimization
• Stochastic Variance Reduction Gradient for a Non-convex Problem Using Graduated Optimization
• Minibatch vs Local SGD with Shuffling: Tight Convergence Bounds and Beyond
• Anytime Online-to-Batch Conversions, Optimism, and Acceleration
• Revisiting SGD with Increasingly Weighted Averaging: Optimization and Generalization Perspectives
• Adversarial Delays in Online Strongly-Convex Optimization
• Hierarchical Context enabled Recurrent Neural Network for Recommendation
• An Approximation Algorithm for Optimal Subarchitecture Extraction
• Convergence Analysis of Accelerated Stochastic Gradient Descent under the Growth Condition
• Convergence rates and approximation results for SGD and its continuous-time counterpart
• Stochastic Proximal Gradient Descent for Nuclear Norm Regularization
• On the Convergence of Memory-Based Distributed SGD
• Stochastic Optimization under Distributional Drift
• Heavy-tailed Streaming Statistical Estimation
• Risk-Averse Approximate Dynamic Programming with Quantile-Based Risk Measures
• Quantum Algorithm for Online Convex Optimization
• When is the Convergence Time of Langevin Algorithms Dimension Independent? A Composite Optimization Viewpoint
• Random Reshuffling with Variance Reduction: New Analysis and Better Rates
• Stochastic Gradient Descent for Stochastic Doubly-Nonconvex Composite Optimization
• Nearly Optimal Robust Method for Convex Compositional Problems with Heavy-Tailed Noise
• Stochastic Subgradient Algorithms for Strongly Convex Optimization over Distributed Networks
• Efficient First-Order Algorithms for Adaptive Signal Denoising
• Gaussian Process Inference Using Mini-batch Stochastic Gradient Descent: Convergence Guarantees and Empirical Benefits
• Last Iterate Risk Bounds of SGD with Decaying Stepsize for Overparameterized Linear Regression
• Stochastic Approximation of Smooth and Strongly Convex Functions: Beyond the $O(1/T)$ Convergence Rate
• A Rule for Gradient Estimator Selection, with an Application to Variational Inference
• On the Convergence of Stochastic Gradient Descent with Low-Rank Projections for Convex Low-Rank Matrix Problems
• A nonasymptotic law of iterated logarithm for general M-estimators
• Parallel Stochastic Optimization Framework for Large-Scale Non-Convex Stochastic Problems
• Mixing of Stochastic Accelerated Gradient Descent
• Compositional Stochastic Average Gradient for Machine Learning and Related Applications
• Stability and Generalization for Randomized Coordinate Descent
• The Convergence Rate of SGD's Final Iterate: Analysis on Dimension Dependence
• Multistep stochastic mirror descent for risk-averse convex stochastic programs based on extended polyhedral risk measures
• One-dimensional System Arising in Stochastic Gradient Descent
• Staggered Time Average Algorithm for Stochastic Non-smooth Optimization with O(1/T) Convergence
• Data Dependent Convergence for Distributed Stochastic Optimization
• A General Framework for Analyzing Stochastic Dynamics in Learning Algorithms
• Asymptotic Properties of $\mathcal{S}$-$\mathcal{A}\mathcal{B}$ Method with Diminishing Stepsize
• On Structured Filtering-Clustering: Global Error Bound and Optimal First-Order Algorithms
• Stochastic Bias-Reduced Gradient Methods
• Toward Efficient Federated Learning in Multi-Channeled Mobile Edge Network with Layerd Gradient Compression
• Greedy Step Averaging: A parameter-free stochastic optimization method
• Better scalability under potentially heavy-tailed feedback
• Sum of Ranked Range Loss for Supervised Learning
• Stochastic gradient descent algorithms for strongly convex functions at O(1/T) convergence rates
• Practical Newton-Type Distributed Learning using Gradient Based Approximations
• Comparison-Based Algorithms for One-Dimensional Stochastic Convex Optimization
• New nonasymptotic convergence rates of stochastic proximal pointalgorithm for convex optimization problems
• Fast Nonsmooth Regularized Risk Minimization with Continuation