The Power of Interpolation: Understanding the Effectiveness of SGD in Modern Over-parametrized Learning

Siyuan Ma; Raef Bassily; Mikhail Belkin

Source-linked AI summary

The Power of Interpolation: Understanding the Effectiveness of SGD in Modern Over-parametrized Learning

Siyuan Ma, Raef Bassily, Mikhail Belkin

arXiv:1712.06559v3Dec 18, 2017cs.LGstat.ML

TL;DR

Modern over-parameterized models often interpolate training data, yet the computational reason for SGD’s fast practical convergence is not fully explained by standard analyses. This paper analyzes interpolated convex optimization across mini-batch sizes, derives quadratic-loss optima, and finds exponential convergence with linear-scaling and saturation regimes that closely match real-data experiments.

Problem
Standard analyses note SGD’s lower per-iteration cost but often require adaptive step sizes and predict convergence much slower than GD, complicating efficiency comparisons.
Method
The paper analyzes convex mini-batch SGD in the interpolated regime as a function of batch size, then derives explicit optimal batch-size and step-size results for quadratic loss.
Results
The analysis gives exponential convergence, with linear scaling for m ≤ m* and saturation for m > m*, while m* is nearly independent of n and experiments corroborate these regimes.
Takeaways & Limitations
The critical batch size marks the limit of effective mini-batch parallelization, while small-batch SGD can match GD’s convergence per iteration and offer O(n) computational acceleration.
Takeaways & Limitations
The reported analysis focuses on training error; test error is reported separately, with test error decreasing alongside training error in the stated over-parameterized settings.

Abstract

from arXiv · show

In this paper we aim to formally explain the phenomenon of fast convergence of SGD observed in modern machine learning. The key observation is that most modern learning architectures are over-parametrized and are trained to interpolate the data by driving the empirical loss (classification and regression) close to zero. While it is still unclear why these interpolated solutions perform well on test data, we show that these regimes allow for fast convergence of SGD, comparable in number of iterations to full gradient descent. For convex loss functions we obtain an exponential convergence bound for {\it mini-batch} SGD parallel to that for full gradient descent. We show that there is a critical batch size $m^*$ such that: (a) SGD iteration with mini-batch size $m\leq m^*$ is nearly equivalent to $m$ iterations of mini-batch size $1$ (\emph{linear scaling regime}). (b) SGD iteration with mini-batch $m> m^*$ is nearly equivalent to a full gradient descent iteration (\emph{saturation regime}). Moreover, for the quadratic loss, we derive explicit expressions for the optimal mini-batch and step size and explicitly characterize the two regimes above. The critical mini-batch size can be viewed as the limit for effective mini-batch parallelization. It is also nearly independent of the data size, implying $O(n)$ acceleration over GD per unit of computation. We give experimental evidence on real data which closely follows our theoretical analyses. Finally, we show how our results fit in the recent developments in training deep neural networks and discuss connections to adaptive rates for SGD and variance reduction.

1 Introduction

The paper explains fast SGD convergence by analyzing over-parameterized, interpolated learning and how mini-batch size controls convergence and computational efficiency. It identifies linear-scaling and saturation regimes, derives sharper quadratic-loss results, and supports them experimentally.

Motivation: Over-parameterization enables near-zero training loss, motivating an analysis of interpolation’s computational implications for SGD.The paper distinguishes this convergence question from the still unresolved question of why interpolated classifiers generalize well.
Convergence: Fixed-step SGD converges exponentially fast for convex losses in the interpolated regime.The paper connects this regime to modern over-parameterized learning and analyzes its dependence on mini-batch size.
Mini-batch regimes: For m ≤ m*, one mini-batch SGD iteration is equivalent up to a near-one constant to m iterations with batch size one.This is the linear-scaling regime.
Mini-batch regimes: For m > m*, one mini-batch SGD iteration is nearly as effective as one full gradient descent iteration.Beyond the critical batch size, additional parallel computation has limited added value.
Quadratic loss: For quadratic loss, the paper derives an explicit optimal step size and characterizes the critical batch size using the Hessian spectrum.The stated characterization gives m* in terms of the Hessian’s spectral norm and related quantities.
Computational efficiency: m* is nearly independent of data size n, while mini-batch size one is optimal for computation per target error.The resulting analysis implies O(n) acceleration over GD per unit of computation and is supported by experiments on real data.
Related context: Prior non-interpolated analyses found it harder to reconcile full GD’s exponential convergence with slower mini-batch SGD rates without additional components.The paper contrasts this difficulty with its interpolated-regime analysis.

2 Preliminaries

The preliminaries formulate unconstrained empirical risk minimization and define the convexity, smoothness, and strong-convexity conditions used in the analysis.

Convex analysis: A differentiable function is convex when it lies above every tangent-plane lower bound.The definition is expressed through the inequality involving ℓ(v), ℓ(w), and ∇ℓ(w).
Convex analysis: β-smoothness bounds the function above by its first-order Taylor approximation plus a quadratic term.This condition controls how rapidly the gradient can change.
Empirical risk minimization: Empirical risk minimization minimizes the average of n individual loss functions over a parameter space.Each loss corresponds to fitting one data point in the supervised-learning formulation.

3 Interpolation and Fast SGD: Convex Loss

Under interpolation, where each individual loss is minimized at a common solution, constant-step-size mini-batch SGD achieves exponential convergence for convex losses. Its speedup follows two batch-size regimes: linear scaling up to a critical size, then saturation at full-gradient effectiveness.

Setting: Interpolation assumes a common minimizer w* with zero loss for every data point, alongside nonnegative, smooth, convex individual losses.The setting includes a λ-smooth, α-strongly convex empirical loss, with β ≥ λ; least-squares regression with full-rank sample covariance is one example.
Method: SGD samples m data points uniformly with replacement at each iteration and updates from their mini-batch empirical loss using a constant step size.The analysis rewrites the update around the optimum and bounds the expected squared error from one iteration by the preceding error.
Convergence result: Exponential convergence holds for mini-batch SGD in the interpolated regime, with optimal step size η*(m) = m/(β + λ(m−1)).The selected step size minimizes the contraction factor among the analyzed choices.
Batch-size regimes: For m ≤ m*, one mini-batch iteration is nearly equivalent to m iterations with batch size 1, up to a multiplicative constant close to 1.The speedup analysis derives this linear-scaling regime from the batch-dependent convergence rate.
Batch-size regimes: For m > m*, one mini-batch iteration is nearly equivalent to one full-gradient iteration, so additional parallel computation has limited value.The quadratic-loss analysis provides a sharper characterization of these regimes.
Variance reduction: In general convex optimization, sampling variance prevents ordinary SGD from using a constant step size and attaining exponential convergence, whereas interpolation supplies these benefits without modifications or extra information.The paper contrasts this with variance-reduction methods, reporting that interpolated SGD uses the largest step size and achieves the fastest convergence rate among the compared methods except Katyusha.

4 How Fast is Fast SGD: Analysis of Step, Mini-batch Sizes and Computational Efficiency for Quadratic Loss

For quadratic losses in the interpolation regime, the paper derives optimal step sizes and convergence rates as functions of mini-batch size, then characterizes computational efficiency and the transition from linear scaling to saturation.

The quadratic analysis covers over-parametrized linear or kernel regression and approximates smooth convex functions near a minimum.
The effective SGD update evolves only in the covariance range because the null-space component does not affect the target loss.
Theorem 2 provides an upper bound on expected empirical loss, and a constructed quadratic instance shows this bound is tight.
Optimal step size: The optimal step size η∗(m) minimizes the convergence factor for each batch size, while a near-optimal approximation can avoid dependence on the least non-zero eigenvalue λk.
Computational efficiency: m = 1 minimizes total gradient computations for a fixed accuracy under the stated computational model, although batch sizes up to a critical m∗ are nearly optimal.
Batch-size regimes: In the linear scaling regime, doubling m roughly halves iterations with η scaling approximately linearly, whereas beyond m∗ additional batching yields sharply smaller benefits and at most a factor-4 iteration reduction.

5 Experimental Results

Experiments on real data support the predicted linear-scaling and saturation regimes for mini-batch SGD, while training-error efficiency favors very small batches. The observed critical batch size is much smaller than the dataset size, and interpolation experiments show similar relative batch-size behavior across kernels.

Step-size behavior: Increasing the step size from η̂ to 2η̂ consistently causes divergence, indicating η̂ is within a factor of 2 of the optimal step size.
Comparison with full gradient descent: SGD with batch size m∗ reaches the same error as GD using at most 4 times as many iterations.This result is reported as consistent with experiments on MNIST, HINT-S, and TIMIT.
Comparison with full gradient descent: Batch sizes larger than m∗ but still much smaller than n converge nearly identically to full gradient descent.
Train-test reporting: The analysis reports training error because it focuses on training error; test error is reported separately, where it decreases with training error in these over-parametrized settings.
Linear scaling and saturation: m = 1 achieves the lowest error for any fixed number of epochs, while m = 1 and m = m∗ show only a small difference in the linear-scaling regime.The epoch count is proportional to computation measured in gradient evaluations.
Kernel experiments: Laplace kernels converge to interpolation faster than Gaussian kernels, but their relative computational efficiencies across batch sizes are remarkably similar.The absolute error scales differ between the settings, while the curve profiles remain similar.

A Proof of Claim 1

The proof decomposes data vectors in the Hessian eigenbasis and shows that mini-batch Hessians preserve the positive-eigenspace while annihilating its orthogonal complement. This establishes the stated structural claim for every sampled mini-batch.

Eigenbasis decomposition: Each data vector is expanded in the eigenbasis of H, whose nonzero eigenvalues are λ1 through λk.
Eigenbasis decomposition: Coefficients αi,ℓ vanish for every zero-eigenvalue direction ℓ ∈ {k + 1, …, d}.
Mini-batch Hessian: For a mini-batch Hessian Hm, its action on an eigenvector er is determined by the mini-batch coefficients and is zero when r > k.
Projection argument: Writing any u as Pu + Qu shows HmPu remains in Span{e1, …, ek}, while HmQu = 0.Pu and Qu are the projections onto the positive-eigenspace and its orthogonal complement.

B Proof of Theorem 6

The proof establishes that batch size one minimizes computational cost for reaching a fixed target accuracy. It does so by analyzing the two piecewise extensions of the convergence factor and proving the resulting cost is monotone.

Cost objective: The cost function g∗(m)^(1/m) measures total computation required to reach a fixed target accuracy without parallel computation.
Monotonicity strategy: The proof reduces optimality to showing g∗(m)^(1/m) is increasing for all m ≥ 1.
Piecewise analysis: The first piece g1(m) extends the small-batch expression of Theorem 4 beyond its original interval.
Piecewise analysis: The second piece is g2(m) = 1 − 4m(m − 1)λ1λk / (β + (m − 1)(λ1 + λk))^2 for m ≥ 1.
Monotonicity proof: The monotonicity proof uses T(m) = 1/[m ln(1/g1(m))] and τ = β − λk, together with a decreasing-function argument.
Monotonicity proof: A key inequality follows because its left-hand side is the complete square ((m − 1)(λ1 − λk) − β)^2.
Conclusion: Combining the two piecewise bounds yields g∗(1) ≤ g∗(m) for every m ≥ 1.

C Experiments: Comparison of Train and Test losses

Figure 8 compares training and testing error across mini-batch sizes as a function of epochs, with epochs scaled to represent computation. The figure is intended to assess train-test behavior under different batching choices.

Train-test comparison: Training and testing error are compared for different mini-batch sizes as a function of number of epochs.The dataset has n = 10^4 data points.