Stochastic Gradient Descent for Non-smooth Optimization: Convergence Results and Optimal Averaging Schemes

Abstract

Stochastic Gradient Descent (SGD) is one of the simplest and most popular stochastic optimization methods. While it has already been theoretically studied for decades, the classical analysis usually required non-trivial smoothness assumptions, which do not apply to many modern applications of SGD with non-smooth objective functions such as support vector machines. In this paper, we investigate the performance of SGD without such smoothness assumptions, as well as a running average scheme to convert the SGD iterates to a solution with optimal optimization accuracy. In this framework, we prove that after T rounds, the suboptimality of the last SGD iterate scales as O(log(T)/\sqrt{T}) for non-smooth convex objective functions, and O(log(T)/T) in the non-smooth strongly convex case. To the best of our knowledge, these are the first bounds of this kind, and almost match the minimax-optimal rates obtainable by appropriate averaging schemes. We also propose a new and simple averaging scheme, which not only attains optimal rates, but can also be easily computed on-the-fly (in contrast, the suffix averaging scheme proposed in Rakhlin et al. (2011) is not as simple to implement). Finally, we provide some experimental illustrations.

To appear in ICML 2013

Cited by in corpus (156)

• Deeply-Supervised Nets
• Differentially Private Distributed Constrained Optimization
• Local SGD Converges Fast and Communicates Little
• Block-Coordinate Frank-Wolfe Optimization for Structural SVMs
• An Asynchronous Parallel Stochastic Coordinate Descent Algorithm
• Stochastic Primal-Dual Coordinate Method for Regularized Empirical Risk Minimization
• Accelerating Minibatch Stochastic Gradient Descent using Stratified Sampling
• Stochastic Optimization with Importance Sampling
• Better Theory for SGD in the Nonconvex World
• WNGrad: Learn the Learning Rate in Gradient Descent
• Unified Optimal Analysis of the (Stochastic) Gradient Method
• Adam revisited: a weighted past gradients perspective
• Near-Optimal Stochastic Approximation for Online Principal Component Estimation
• An Optimal Control Approach to Deep Learning and Applications to Discrete-Weight Neural Networks
• Generalization Properties and Implicit Regularization for Multiple Passes SGM
• Large-Scale Methods for Distributionally Robust Optimization
• Stochastic Polyak Step-size for SGD: An Adaptive Learning Rate for Fast Convergence
• Encode, Shuffle, Analyze Privacy Revisited: Formalizations and Empirical Evaluation
• SGD: General Analysis and Improved Rates
• Bridging the Gap between Constant Step Size Stochastic Gradient Descent and Markov Chains
• Stochastic Gradient Descent, Weighted Sampling, and the Randomized Kaczmarz algorithm
• The Impact of Neural Network Overparameterization on Gradient Confusion and Stochastic Gradient Descent
• Laplacian Smoothing Gradient Descent
• To Drop or Not to Drop: Robustness, Consistency and Differential Privacy Properties of Dropout
• Linear Convergence of Variance-Reduced Stochastic Gradient without Strong Convexity
• Smoothed Variable Sample-size Accelerated Proximal Methods for Nonsmooth Stochastic Convex Programs
• Accelerating Stochastic Composition Optimization
• Optimal Transport Based Distributionally Robust Optimization: Structural Properties and Iterative Schemes
• On Linear Stochastic Approximation: Fine-grained Polyak-Ruppert and Non-Asymptotic Concentration
• Tight Analyses for Non-Smooth Stochastic Gradient Descent
• MetaGrad: Multiple Learning Rates in Online Learning
• Random Multi-Constraint Projection: Stochastic Gradient Methods for Convex Optimization with Many Constraints
• Fast Stochastic Variance Reduced Gradient Method with Momentum Acceleration for Machine Learning
• Online Learning to Sample
• Generalization of ERM in Stochastic Convex Optimization: The Dimension Strikes Back
• Communication trade-offs for synchronized distributed SGD with large step size
• Differentially Private Federated Learning for Resource-Constrained Internet of Things
• Without-Replacement Sampling for Stochastic Gradient Methods: Convergence Results and Application to Distributed Optimization
• DPIS: An Enhanced Mechanism for Differentially Private SGD with Importance Sampling
• The Strength of Nesterov's Extrapolation in the Individual Convergence of Nonsmooth Optimization
• How degenerate is the parametrization of neural networks with the ReLU activation function?
• Conservative Stochastic Optimization with Expectation Constraints
• Stochastic Quasi-Newton Methods for Nonconvex Stochastic Optimization
• Last Iterate is Slower than Averaged Iterate in Smooth Convex-Concave Saddle Point Problems
• Optimal Margin Distribution Machine
• Iterative Regularization for Learning with Convex Loss Functions
• Biased Stochastic First-Order Methods for Conditional Stochastic Optimization and Applications in Meta Learning
• Fine-Grained Analysis of Stability and Generalization for Stochastic Gradient Descent
• Generalized Conditional Gradient for Sparse Estimation
• A neural network based policy iteration algorithm with global $H^2$-superlinear convergence for stochastic games on domains
• Parallelization does not Accelerate Convex Optimization: Adaptivity Lower Bounds for Non-smooth Convex Minimization
• Online Robust Regression via SGD on the l1 loss
• Network Support for High-performance Distributed Machine Learning
• Shuffled Model of Federated Learning: Privacy, Communication and Accuracy Trade-offs
• Langevin Monte Carlo without smoothness
• Minimax Estimation for Personalized Federated Learning: An Alternative between FedAvg and Local Training?
• MixedGrad: An O(1/T) Convergence Rate Algorithm for Stochastic Smooth Optimization
• Customized Local Differential Privacy for Multi-Agent Distributed Optimization
• Towards stability and optimality in stochastic gradient descent
• Stochastic Optimization for Regularized Wasserstein Estimators
• Learning Rates as a Function of Batch Size: A Random Matrix Theory Approach to Neural Network Training
• Stochastic gradient descent methods for estimation with large data sets
• Evading Curse of Dimensionality in Unconstrained Private GLMs via Private Gradient Descent
• Asynchronous Stochastic Coordinate Descent: Parallelism and Convergence Properties
• Classification Logit Two-sample Testing by Neural Networks
• Guaranteed Sufficient Decrease for Stochastic Variance Reduced Gradient Optimization
• Gradient Perturbation is Underrated for Differentially Private Convex Optimization
• Generalization Properties of Doubly Stochastic Learning Algorithms
• Stochastic subGradient Methods with Linear Convergence for Polyhedral Convex Optimization
• Projection Efficient Subgradient Method and Optimal Nonsmooth Frank-Wolfe Method
• Can Implicit Bias Explain Generalization? Stochastic Convex Optimization as a Case Study
• Convergence of Stochastic Gradient Descent for PCA
• Deep Learning with Label Differential Privacy
• Random feature neural networks learn Black-Scholes type PDEs without curse of dimensionality
• The Statistics of Streaming Sparse Regression
• Stochastic Compositional Gradient Descent: Algorithms for Minimizing Compositions of Expected-Value Functions
• Last iterate convergence of SGD for Least-Squares in the Interpolation regime
• Stochastic Iterative Hard Thresholding for Graph-structured Sparsity Optimization
• Nesterov's method with decreasing learning rate leads to accelerated stochastic gradient descent
• The Value of Collaboration in Convex Machine Learning with Differential Privacy
• Uniform-in-Time Weak Error Analysis for Stochastic Gradient Descent Algorithms via Diffusion Approximation
• Dimensionality Reduction for Stationary Time Series via Stochastic Nonconvex Optimization
• Online Pairwise Learning Algorithms with Kernels
• On the Convergence of Stochastic Gradient Descent with Bandwidth-based Step Size
• Renyi Differential Privacy of the Subsampled Shuffle Model in Distributed Learning
• Fast Rates of ERM and Stochastic Approximation: Adaptive to Error Bound Conditions
• Convergence of Unregularized Online Learning Algorithms
• Beating SGD Saturation with Tail-Averaging and Minibatching
• Guarantees for Tuning the Step Size using a Learning-to-Learn Approach
• Differentially Private SGD with Non-Smooth Losses
• Scalable Nonlinear Learning with Adaptive Polynomial Expansions
• Maximum likelihood estimation of regularisation parameters in high-dimensional inverse problems: an empirical Bayesian approach. Part II: Theoretical Analysis
• Stigmergic Independent Reinforcement Learning for Multi-Agent Collaboration
• Learning with risks based on M-location
• Stochastic Gradient Descent for Linear Systems with Missing Data
• Improved Learning Rates for Stochastic Optimization
• On the Convergence of Step Decay Step-Size for Stochastic Optimization
• Stability of SGD: Tightness Analysis and Improved Bounds
• Randomized Iterative Methods for Linear Systems: Momentum, Inexactness and Gossip
• Online Covariance Matrix Estimation in Stochastic Gradient Descent
• Accelerated Dual-Averaging Primal-Dual Method for Composite Convex Minimization
• Swing contract pricing: with and without Neural Networks
• ECC: Platform-Independent Energy-Constrained Deep Neural Network Compression via a Bilinear Regression Model
• On the convergence of mirror descent beyond stochastic convex programming
• Exploiting Smoothness in Statistical Learning, Sequential Prediction, and Stochastic Optimization
• Optimal Rates for Learning with Nyström Stochastic Gradient Methods
• Stochastic Gradient Descent Meets Distribution Regression
• Lsh-sampling Breaks the Computation Chicken-and-egg Loop in Adaptive Stochastic Gradient Estimation
• An Efficient Algorithm for High-Dimensional Log-Concave Maximum Likelihood
• Learning Risk-aware Costmaps for Traversability in Challenging Environments
• Deep-learning inversion: a next generation seismic velocity-model building method
• Quantized Epoch-SGD for Communication-Efficient Distributed Learning
• SecureGBM: Secure Multi-Party Gradient Boosting
• Parameter-free Stochastic Optimization of Variationally Coherent Functions
• Eigencurve: Optimal Learning Rate Schedule for SGD on Quadratic Objectives with Skewed Hessian Spectrums
• Random Shuffling Beats SGD Only After Many Epochs on Ill-Conditioned Problems
• Private Stochastic Convex Optimization: Efficient Algorithms for Non-smooth Objectives
• Stochastic Gradient Descent on a Tree: an Adaptive and Robust Approach to Stochastic Convex Optimization
• Personalized Advertisement Recommendation: A Ranking Approach to Address the Ubiquitous Click Sparsity Problem
• Coupling-based Convergence Diagnostic and Stepsize Scheme for Stochastic Gradient Descent
• Debiasing Stochastic Gradient Descent to handle missing values
• When is the Convergence Time of Langevin Algorithms Dimension Independent? A Composite Optimization Viewpoint
• Revisiting SGD with Increasingly Weighted Averaging: Optimization and Generalization Perspectives
• Efficient active learning of sparse halfspaces
• The Cost of a Reductions Approach to Private Fair Optimization
• Stochastic Approximation of Smooth and Strongly Convex Functions: Beyond the $O(1/T)$ Convergence Rate
• Accelerating Stochastic Gradient Descent Using Antithetic Sampling
• Blockwise Adaptivity: Faster Training and Better Generalization in Deep Learning
• Larger is Better: The Effect of Learning Rates Enjoyed by Stochastic Optimization with Progressive Variance Reduction
• Large Margin Distribution Machine
• A Rule for Gradient Estimator Selection, with an Application to Variational Inference
• Adversarial Delays in Online Strongly-Convex Optimization
• Stochastic Gradient Descent for Stochastic Doubly-Nonconvex Composite Optimization
• Stationary Behavior of Constant Stepsize SGD Type Algorithms: An Asymptotic Characterization
• The Convergence Rate of SGD's Final Iterate: Analysis on Dimension Dependence
• Variance Regularization for Accelerating Stochastic Optimization
• Parallel Stochastic Optimization Framework for Large-Scale Non-Convex Stochastic Problems
• Large-scale Kernel Methods and Applications to Lifelong Robot Learning
• Network Parameter Learning Using Nonlinear Transforms, Local Representation Goals and Local Propagation Constraints
• Concavifiability and convergence: necessary and sufficient conditions for gradient descent analysis
• Structure-Adaptive, Variance-Reduced, and Accelerated Stochastic Optimization
• Staggered Time Average Algorithm for Stochastic Non-smooth Optimization with O(1/T) Convergence
• The Power of Factorial Powers: New Parameter settings for (Stochastic) Optimization
• Network Learning with Local Propagation
• Comparison-Based Algorithms for One-Dimensional Stochastic Convex Optimization
• Data-driven Algorithm Selection and Parameter Tuning: Two Case studies in Optimization and Signal Processing
• Comprehensive Personalized Ranking Using One-Bit Comparison Data
• Training L1-Regularized Models with Orthant-Wise Passive Descent Algorithms
• Bound on Peak-to-Average Power Ratio with Moment and Reduction Method
• Projected Semi-Stochastic Gradient Descent Method with Mini-Batch Scheme under Weak Strong Convexity Assumption
• Carpe Diem, Seize the Samples Uncertain "At the Moment" for Adaptive Batch Selection
• Greedy Step Averaging: A parameter-free stochastic optimization method
• Randomized Smoothing SVRG for Large-scale Nonsmooth Convex Optimization
• Characterization of Excess Risk for Locally Strongly Convex Population Risk
• Fast Nonsmooth Regularized Risk Minimization with Continuation
• A FAIR and AI-ready Higgs boson decay dataset