Non-strongly-convex smooth stochastic approximation with convergence rate O(1/n)

Abstract

We consider the stochastic approximation problem where a convex function has to be minimized, given only the knowledge of unbiased estimates of its gradients at certain points, a framework which includes machine learning methods based on the minimization of the empirical risk. We focus on problems without strong convexity, for which all previously known algorithms achieve a convergence rate for function values of O(1/n^{1/2}). We consider and analyze two algorithms that achieve a rate of O(1/n) for classical supervised learning problems. For least-squares regression, we show that averaged stochastic gradient descent with constant step-size achieves the desired rate. For logistic regression, this is achieved by a simple novel stochastic gradient algorithm that (a) constructs successive local quadratic approximations of the loss functions, while (b) preserving the same running time complexity as stochastic gradient descent. For these algorithms, we provide a non-asymptotic analysis of the generalization error (in expectation, and also in high probability for least-squares), and run extensive experiments on standard machine learning benchmarks showing that they often outperform existing approaches.

References in corpus (1)

• Non-strongly-convex smooth stochastic approximation with convergence rate O(1/n)

Cited by in corpus (93)

• Robust Aggregation for Federated Learning
• Extended dynamic mode decomposition with dictionary learning: a data-driven adaptive spectral decomposition of the Koopman operator
• Convex Optimization for Big Data
• Non-strongly-convex smooth stochastic approximation with convergence rate O(1/n)
• Neural networks-based variationally enhanced sampling
• Using the Maximum Entropy Principle to Combine Simulations and Solution Experiments
• Ensemble Kalman Inversion: A Derivative-Free Technique For Machine Learning Tasks
• Why gradient clipping accelerates training: A theoretical justification for adaptivity
• Riemannian SVRG: Fast Stochastic Optimization on Riemannian Manifolds
• Fast large-scale optimization by unifying stochastic gradient and quasi-Newton methods
• The Step Decay Schedule: A Near Optimal, Geometrically Decaying Learning Rate Procedure For Least Squares
• From Averaging to Acceleration, There is Only a Step-size
• Strong error analysis for stochastic gradient descent optimization algorithms
• Making the best of a bad situation: a multiscale approach to free energy calculation
• Full error analysis for the training of deep neural networks
• The Implicit Regularization of Stochastic Gradient Flow for Least Squares
• Logistic Regression: Tight Bounds for Stochastic and Online Optimization
• Lower error bounds for the stochastic gradient descent optimization algorithm: Sharp convergence rates for slowly and fast decaying learning rates
• Online Stochastic Linear Optimization under One-bit Feedback
• HiGrad: Uncertainty Quantification for Online Learning and Stochastic Approximation
• Enhanced sampling of transition states
• Simultaneous Model Selection and Optimization through Parameter-free Stochastic Learning
• Phase equilibrium of liquid water and hexagonal ice from enhanced sampling molecular dynamics simulations
• On the Adaptivity of Stochastic Gradient-Based Optimization
• A proof of convergence for gradient descent in the training of artificial neural networks for constant target functions
• A Selective Review on Statistical Methods for Massive Data Computation: Distributed Computing, Subsampling, and Minibatch Techniques
• Fast and Robust Online Inference with Stochastic Gradient Descent via Random Scaling
• Communication trade-offs for synchronized distributed SGD with large step size
• A variational approach to nucleation simulation
• Optimal Rates for Averaged Stochastic Gradient Descent under Neural Tangent Kernel Regime
• Robust, Accurate Stochastic Optimization for Variational Inference
• A generalization of regularized dual averaging and its dynamics
• Bandit Structured Prediction for Learning from Partial Feedback in Statistical Machine Translation
• On the existence of global minima and convergence analyses for gradient descent methods in the training of deep neural networks
• Which Algorithmic Choices Matter at Which Batch Sizes? Insights From a Noisy Quadratic Model
• A proof of convergence for stochastic gradient descent in the training of artificial neural networks with ReLU activation for constant target functions
• Learning to Predict Independent of Span
• Reducing the variance in online optimization by transporting past gradients
• A Unified Analysis of First-Order Methods for Smooth Games via Integral Quadratic Constraints
• Online Robust Regression via SGD on the l1 loss
• Benign Overfitting of Constant-Stepsize SGD for Linear Regression
• On the fast convergence of random perturbations of the gradient flow
• Quasi-potential as an implicit regularizer for the loss function in the stochastic gradient descent
• Stochastic gradient descent methods for estimation with large data sets
• Self-Learning Camera: Autonomous Adaptation of Object Detectors to Unlabeled Video Streams
• On the interplay between noise and curvature and its effect on optimization and generalization
• Constant Step Size Least-Mean-Square: Bias-Variance Trade-offs and Optimal Sampling Distributions
• True Asymptotic Natural Gradient Optimization
• Non-asymptotic Error Bounds For Constant Stepsize Stochastic Approximation For Tracking Mobile Agents
• Last iterate convergence of SGD for Least-Squares in the Interpolation regime
• Stochastic Iterative Hard Thresholding for Graph-structured Sparsity Optimization
• Uniform-in-Time Weak Error Analysis for Stochastic Gradient Descent Algorithms via Diffusion Approximation
• Existence, uniqueness, and convergence rates for gradient flows in the training of artificial neural networks with ReLU activation
• Optimal Matrix Momentum Stochastic Approximation and Applications to Q-learning
• The Benefits of Implicit Regularization from SGD in Least Squares Problems
• Convergence of stochastic gradient descent schemes for Lojasiewicz-landscapes
• Differentially Private SGD with Non-Smooth Losses
• Stochastic Online Optimization using Kalman Recursion
• Improved Learning Rates for Stochastic Optimization
• Efficient and Robust Algorithms for Adversarial Linear Contextual Bandits
• On the Double Descent of Random Features Models Trained with SGD
• Low Complexity Approximate Bayesian Logistic Regression for Sparse Online Learning
• Convergence rates for gradient descent in the training of overparameterized artificial neural networks with piecewise affine activation
• Stochastic Proximal AUC Maximization
• On the asymptotic rate of convergence of Stochastic Newton algorithms and their Weighted Averaged versions
• Understanding and Detecting Convergence for Stochastic Gradient Descent with Momentum
• 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
• Eigencurve: Optimal Learning Rate Schedule for SGD on Quadratic Objectives with Skewed Hessian Spectrums
• A Study of Condition Numbers for First-Order Optimization
• Stochastic Gradient Descent in Hilbert Scales: Smoothness, Preconditioning and Earlier Stopping
• Computational Convergence Analysis of Distributed Gradient Tracking for Smooth Convex Optimization Using Dissipativity Theory
• Anytime Tail Averaging
• On Data Preconditioning for Regularized Loss Minimization
• Naive imputation implicitly regularizes high-dimensional linear models
• Self-Concordant Analysis of Generalized Linear Bandits with Forgetting
• Dimension Independent Generalization Error by Stochastic Gradient Descent
• Stochastic Approximation of Smooth and Strongly Convex Functions: Beyond the $O(1/T)$ Convergence Rate
• Improved scalability under heavy tails, without strong convexity
• How Data Augmentation affects Optimization for Linear Regression
• Strong overall error analysis for the training of artificial neural networks via random initializations
• Small errors in random zeroth-order optimization are imaginary
• Non asymptotic analysis of Adaptive stochastic gradient algorithms and applications
• Coupling-based Convergence Diagnostic and Stepsize Scheme for Stochastic Gradient Descent
• Last Iterate Risk Bounds of SGD with Decaying Stepsize for Overparameterized Linear Regression
• Debiasing Stochastic Gradient Descent to handle missing values
• Stochastic Gradient Descent with Exponential Convergence Rates of Expected Classification Errors
• Convergence guarantees for forward gradient descent in the linear regression model
• Logarithmic Regret for parameter-free Online Logistic Regression
• Convergence and Stability of the Stochastic Proximal Point Algorithm with Momentum
• SGD with Variance Reduction beyond Empirical Risk Minimization
• Some Limit Properties of Markov Chains Induced by Stochastic Recursive Algorithms
• COCO Denoiser: Using Co-Coercivity for Variance Reduction in Stochastic Convex Optimization
• Better scalability under potentially heavy-tailed feedback