We analyze a variant of stochastic gradient descent with initial regularization (SGDIR) and derive dimension-free upper bounds on its expected excess risk for the squared loss. In the noiseless case, we obtain new bounds for both averaged and non-averaged SGDIR under moment, source, and capacity assumptions. For a particular value of the source parameter, these bounds are of order m−2log2m, where the number of training samples is of order m. For another value of the source parameter, we obtain, for any ε>0, bounds of order m−3+ε, provided that the capacity parameter exceeds ε−1. We also establish a lower bound that matches our upper bounds in certain regimes up to a polylogarithmic factor. In the noisy case, we provide an instance-based comparison between SGDIR and ridge regression. Under general assumptions and a mild lower bound on the regularization parameter, we show that the expected excess risk of SGDIR is no larger than that of ridge regression, up to a polylogarithmic factor. Numerical experiments on synthetic and real data are consistent with our theoretical findings.
Figures & tables
Figure 1: Test error versus n for in a noiseless setting.
n
house_8L ( d′=8 )
elevators ( d′=18 )
MSD ( d′=90 )
SGD
KRR
λn
SGD
KRR
λn
SGD
KRR
λn
150
0.0016
0.00086
0.09
0.0014
0.00079
3.5×10−5
0.0019
0.00081
2.1
300
0.0039
0.0042
0.12
0.0034
0.0034
1×10−6
0.0044
0.0034
0.12
600
0.015
0.019
0.16
0.014
0.018
1×10−6
0.016
0.019
0.11
1200
0.048
0.084
0.19
0.046
0.092
1×10−6
0.053
0.083
0.17
2400
0.19
0.42
0.23
0.20
0.42
1×10−6
0.17
0.41
0.23
Table 1: Running time (in seconds) of a single run of tail-averaged SGD (representative of both SGD-like methods) and KRR, together with the corresponding values of λn . The reported running times exclude cross-validation and test error evaluation.
Figure 2: Average test error versus n for the house_8L, elevators and MSD datasets, from left to right.
Figure 3: Upper bound on E[R(θˉn/2:n+1)]/E[R(θ^λ,n)] , with n~=14000 .
Variance reduction (VR) methods employ stochastic gradients with decreasing variance, and they have been widely applied to solve large-scale optimization problems in machine learning because of their efficiency. Existing theoretical studies of VR methods are mainly focused on the convergence analysis, leaving the generalization behavior largely unexplored. In this paper, we bridge this gap by developing the first non-vacuous generalization analysis of the representative VR method: Stochastic Variance Reduced Gradient (SVRG), through the lens of algorithmic stability. In particular, we establish sharp stability bounds of the SVRG in both convex and strongly convex settings by exploiting its algorithmic structure. The obtained bounds are data-dependent, because the training errors are incorporated along the trajectory. Our analysis clarifies the interplay between optimization and generalization, leading to optimal excess population risk bounds in both settings. Our approach differs substantially from existing analyses of stochastic algorithms in the sense that we decompose the SVRG update as an SGD-like step plus a zero-mean correction term and then introduce novel Lyapunov functions to absorb the additional gradient terms induced by the reference points. Our analytical framework can be generalized to other VR methods, and we demonstrate the generalization by the well-known Stochastic Average Gradient Accelerated (SAGA) method.
Yunwen Lei, Zimeng Wang, Xiaoming Yuan
Department of Mathematics, The University of Hong Kong, Hong Kong, China · Department of Mathematics and Mathematical Statistics, Ume˚a University, Sweden
We consider L2-regularized linear (ridge) regression over a finite data sample X with bounded covariance and linear prediction targets y with additive isotropic noise of finite variance. We present an iterative procedure to compute the optimal regularization strength numerically from the generative parameters in the fixed-X setting and prove its convergence at limited noise levels. Our experimental evaluation over synthetic data shows that the proposed procedure combined with sample-based parameter estimates attains near-optimal random-X generalization across a wide range of sample sizes, aspect ratios, and noise levels, at an added computational cost equivalent to one preliminary ridge regression in the underparameterized regime and two in the overparameterized case.
Jack Timmermans, Sergio A. Alvarez
Department of Computer Science, Boston College, Chestnut Hill, MA 02467 USA
A fundamental problem in machine learning is understanding the effect of early stopping on the parameters obtained and the generalization capabilities of the model. Even for linear models, the effect is not fully understood for arbitrary learning rates and data. In this paper, we analyze the dynamics of discrete full batch gradient descent for linear regression. With minimal distributional assumptions, we characterize the trajectory of the parameters and the expected excess risk. Using this characterization, we show that when training with any learning rate schedule and finite time horizon, the early stopped solution is equivalent to the minimum norm solution for a generalized ridge regression problem. We also prove that early stopping is beneficial for generic data with arbitrary spectrum and for a wide variety of learning rate schedules. We provide an estimate for the optimal stopping time and empirically demonstrate the accuracy of our estimate.
Rishi Sonthalia, Jackie Lok, Elizaveta Rebrova
Department of Mathematics, Boston College · ORFE Department, Princeton University