Statistical Optimality of Stochastic Gradient Descent on Hard Learning Problems through Multiple Passes

Abstract

We consider stochastic gradient descent (SGD) for least-squares regression with potentially several passes over the data. While several passes have been widely reported to perform practically better in terms of predictive performance on unseen data, the existing theoretical analysis of SGD suggests that a single pass is statistically optimal. While this is true for low-dimensional easy problems, we show that for hard problems, multiple passes lead to statistically optimal predictions while single pass does not; we also show that in these hard models, the optimal number of passes over the data increases with sample size. In order to define the notion of hardness and show that our predictive performances are optimal, we consider potentially infinite-dimensional models and notions typically associated to kernel methods, namely, the decay of eigenvalues of the covariance matrix of the features and the complexity of the optimal predictor as measured through the covariance matrix. We illustrate our results on synthetic experiments with non-linear kernel methods and on a classical benchmark with a linear model.

Cited by in corpus (20)

• High probability generalization bounds for uniformly stable algorithms with nearly optimal rate
• The Implicit Regularization of Stochastic Gradient Flow for Least Squares
• Sobolev Norm Learning Rates for Regularized Least-Squares Algorithm
• Optimal Rates for Averaged Stochastic Gradient Descent under Neural Tangent Kernel Regime
• Fine-Grained Analysis of Stability and Generalization for Stochastic Gradient Descent
• When Does Preconditioning Help or Hurt Generalization?
• Optimal Statistical Rates for Decentralised Non-Parametric Regression with Linear Speed-Up
• Kernel Truncated Randomized Ridge Regression: Optimal Rates and Low Noise Acceleration
• Beating SGD Saturation with Tail-Averaging and Minibatching
• Improved Learning Rates for Stochastic Optimization
• Learning with Gradient Descent and Weakly Convex Losses
• Gradient Descent in RKHS with Importance Labeling
• Stochastic Gradient Descent Meets Distribution Regression
• Stochastic Gradient Descent in Hilbert Scales: Smoothness, Preconditioning and Earlier Stopping
• Fast rates in structured prediction
• The Directional Bias Helps Stochastic Gradient Descent to Generalize in Kernel Regression Models
• Learning Curves for SGD on Structured Features
• How isotropic kernels perform on simple invariants
• Online nonparametric regression with Sobolev kernels
• On the Saturation Phenomenon of Stochastic Gradient Descent for Linear Inverse Problems