Early Stopping in Deep Networks: Double Descent and How to Eliminate it

Reinhard Heckel; Fatih Furkan Yilmaz

Source-linked AI summary

Early Stopping in Deep Networks: Double Descent and How to Eliminate it

Reinhard Heckel, Fatih Furkan Yilmaz

arXiv:2007.10099v2Jul 20, 2020cs.LGstat.ML

TL;DR

Epoch-wise test error can decrease, increase, and then decrease during training, prompting the question of what explains this behavior. The paper analyzes early-stopped least squares and two-layer networks, finding that superposed bias–variance tradeoffs explain the pattern, which can occur in both under- and overparameterized models.

Problem
Epoch-wise test error can decrease, increase, and then decrease during training, and the paper investigates what explains this behavior.
Source: §1 · p. 1, §1.1 · p. 2
Method
The paper theoretically characterizes early-stopped least-squares and two-layer-network risk, examining how feature scales, layer initializations, and step sizes shape bias–variance tradeoffs.
Source: §1.1 · p. 3
Results
Epoch-wise double descent arises from superposed bias–variance tradeoffs and can occur in both under- and overparameterized models.
Source: §1 · p. 2
Takeaways & Limitations
In the two-layer network, a smaller second-layer step size eliminates double descent and gives better overall risk.
Source: §3.1 · p. 11
Optimal step sizes may be unavailable when feature variances are unknown, though treating step sizes as hyperparameters can mitigate double descent suboptimally.
Source: §2.3 · p. 7

Abstract

from arXiv · show

Over-parameterized models, such as large deep networks, often exhibit a double descent phenomenon, whereas a function of model size, error first decreases, increases, and decreases at last. This intriguing double descent behavior also occurs as a function of training epochs and has been conjectured to arise because training epochs control the model complexity. In this paper, we show that such epoch-wise double descent arises for a different reason: It is caused by a superposition of two or more bias-variance tradeoffs that arise because different parts of the network are learned at different epochs, and eliminating this by proper scaling of stepsizes can significantly improve the early stopping performance. We show this analytically for i) linear regression, where differently scaled features give rise to a superposition of bias-variance tradeoffs, and for ii) a two-layer neural network, where the first and second layer each govern a bias-variance tradeoff. Inspired by this theory, we study two standard convolutional networks empirically and show that eliminating epoch-wise double descent through adjusting stepsizes of different layers improves the early stopping performance significantly.

1 Introduction

Epoch-wise double descent is explained not by training-time control of model complexity, but by superposed bias-variance tradeoffs learned at different times. The paper analyzes this mechanism in linear regression and two-layer networks, then studies its mitigation in convolutional networks.

1 Introduction

Epoch-wise double descent arises from a superposition of bias-variance tradeoffs, rather than from early stopping controlling model complexity.When the tradeoffs have minima at different training times, their sum can produce a double-descent curve.Source: §1 · p. 2, §1.1 · p. 2
Unlike model-wise double descent, epoch-wise double descent can occur in both under- and overparameterized models.The paper therefore distinguishes the phenomenon from one tied to model over-parameterization.Source: §1 · pp. 1–2

1.1 Contributions

In linear regression, differently scaled features make early-stopped least squares risk a superposition of bias-variance tradeoffs, yielding a double-descent-like curve.The paper theoretically characterizes the risk as a function of early-stopping time.Source: §1.1 · p. 3
For a two-layer neural network, the layers’ initialization scales and stepsizes govern overlapping bias-variance tradeoffs and whether epoch-wise double descent occurs.The paper’s theoretical risk bound motivates scaling layer stepsizes to eliminate the pattern.Source: §1.1 · p. 3
Experiments on a 5-layer CNN and ResNet-18 associate double descent with layers learned at different speeds and report that adjusting layer stepsizes can eliminate it.In the 5-layer CNN, representation layers are learned faster than the final fully connected layer; in ResNet-18, later layers are learned faster than early layers.Source: §1.1 · p. 3

1.2 Related works

Prior early-stopping analyses formalized bias-variance balancing without predicting double descent [Ras+14], while this paper’s two-layer analysis optimizes both layers.Earlier neural-network analyses optimized only the first layer; model-wise double-descent work instead studies bias and variance as functions of model size [Jac+20; Yan+20; d’A+20].Source: §1.2 · pp. 3–4

2 Early-stopped gradient descent for linear least squares

This section analyzes early-stopped gradient descent for linear least squares, showing how differently scaled features produce a superposition of bias-variance tradeoffs and epoch-wise double descent. Aligning those tradeoffs through feature-specific stepsizes can improve early-stopping risk.

2.1 Data model and risk

The data model uses zero-mean Gaussian features with diagonal covariance and independent zero-mean Gaussian noise; the linear estimator's risk is evaluated on an independent example.The feature variances and true coefficients determine the risk expression.Source: §2.1 · pp. 4–5

2.2 Early-stopped least squares estimate

The estimator is obtained by applying gradient descent to empirical risk from θ_0 = 0, with a potentially different positive stepsize for each feature, then stopping after t iterations.The section studies the resulting estimator's risk as a function of the stopping time.Source: §2.2 · p. 5

2 Early-stopped gradient descent for linear least squares

In the underparameterized regime, the section's main result states that the early-stopped gradient-descent risk is very close to a tractable risk expression.The analysis focuses on fitting a linear model to data generated by a Gaussian linear model.Source: §2 · p. 4, §2.3 · p. 5

2.3 Risk of early stopped least squares

The linear-regression analysis finds that differently scaled features can produce epoch-wise double descent by adding U-shaped, per-feature bias-variance tradeoffs with minima at different iterations.Each curve's minimum depends on the product of its feature variance and stepsize, η_iσ_i^2.Source: §2.3 · p. 6
Choosing feature-specific stepsizes to align the tradeoff minima at a selected stopping time eliminates double descent and achieves the lowest overall risk there.The figure illustrates overlapping tradeoffs and a lower minimum risk after elimination; in practice, unknown feature variances may limit optimal scaling, though hyperparameter tuning can mitigate the effect.Source: §2.3 · pp. 6–7

3 Early stopping in two layer neural networks

The two-layer network’s early-stopped risk can be bounded by a superposition of bias-variance tradeoffs governed by kernels for its two layers. The analysis and numerical example show how layer initialization and stepsizes affect epoch-wise double descent.

3 Early stopping in two layer neural networks

The section studies a randomly initialized two-layer ReLU network trained by gradient descent on quadratic loss, with normalized inputs and bounded labels.The network has k hidden neurons; its first-layer weights are W and its output-layer weights are v.Source: §3 · pp. 8–9

3.1 Risk of early stopped neural network training

The risk bound depends on a Gram matrix built from kernels associated with the first and second layers, and whether double descent occurs depends on its singular values.Those singular values depend on the kernels, initialization, and example distribution.Source: §3.1 · pp. 9–10
The theorem bounds the test risk for a sufficiently wide network under its stated initialization and Gram-matrix conditions.The bound is interpreted as a superposition of n U-shaped bias-variance tradeoffs.Source: §3.1 · p. 10
In the example, large singular values associated mainly with second-layer weights accompany double descent, which can be mitigated by reducing that layer’s stepsize.The figure’s bottom row measures the singular-value association with each layer’s weights.Source: §3.1 · p. 11, Figure 4 · p. 12
A smaller second-layer stepsize eliminates double descent and improves overall risk in the example; a smaller first-layer initialization also eliminates the descent pattern.With equal initialization scales and equal stepsizes, the empirical test risk shows double descent.Source: §3.1 · p. 11, Figure 4 · p. 12

4 Early stopping in convolutional neural networks

On noisy CIFAR-10, smaller stepsizes for selected layers eliminate epoch-wise double descent in a 5-layer CNN and ResNet-18. The CNN’s Jacobian structure suggests why layer-specific scaling helps.

4 Early stopping in convolutional neural networks

The study evaluates a standard 5-layer CNN and ResNet-18 on CIFAR-10 with 20% random label noise, and reports no theoretical results for these complex networks.The authors use their theory to motivate adjusting layer stepsizes.Source: §4 · p. 12
Smaller stepsizes for the fully connected layer eliminate double descent in the 5-layer CNN, while scaling the latter half of ResNet-18’s layers mitigates it.The experiments use CIFAR-10 with 20% random label noise.Source: §4 · pp. 12–14
In the CNN, large Jacobian singular values are associated mostly with fully connected weights, so equal stepsizes make that layer learn faster than the convolutional layers.Reducing the fully connected layer’s stepsize brings its learning speed closer to that of the convolutional layers and improves the best early-stopped performance.Source: §4 · p. 13, Figure 5 · p. 13

A Numerical results for linear least squares

Numerical simulations of Gaussian linear least squares compare early-stopped risk with the paper’s risk expression. The expression slightly underestimates simulated risk, with better estimates at larger sample size.

A Numerical results for linear least squares

The n = 6d simulation uses d = 700 features, n = 6d examples, and two feature groups with singular values 1 and 0.1.The groups comprise 6/7 and 1/7 of the features, with associated model coefficients 1 and 10, respectively.Source: A Numerical results for linear least… · p. 16
The risk expression slightly underestimates the simulated early-stopped risk but otherwise describes its behavior well.Figure 7 compares the risk from Gaussian-model simulations with the expression given in equation (2); simulations average 100 gradient-descent runs.Source: A Numerical results for linear least… · p. 16, Figure 7 · p. 17
The estimate’s quality improves as the sample size increases from n = 6d to n = 10d.The n = 10d simulation uses the same configuration as the n = 6d simulation.Source: A Numerical results for linear least… · pp. 16–17

B Numerical bias-variance decomposition for the 5-layer CNN

The CNN decomposition supports an account of epoch-wise double descent as a temporal superposition of bias–variance tradeoffs, distinct from model-wise double descent. The accompanying proof passages describe separate bounds and residual comparisons.

B Numerical bias-variance decomposition for the 5-layer CNN

The paper attributes epoch-wise double descent to a temporal superposition of multiple bias–variance tradeoff curves rather than a unimodal variance curve.This differs from model-wise double descent as characterized in the passage.Source: B Numerical bias-variance… · p. 17
The CNN’s numerically computed overall bias increases while overall variance has a double-descent-like shape, supporting the paper’s temporal-superposition account.The paper distinguishes this explanation from model-wise double descent, which it describes as involving a unimodal variance curve.Source: B Numerical bias-variance… · p. 17

C Proof of Theorem 1

Theorem 1’s proof bounds two right-hand-side terms separately, then applies bounds (12) and (13) to bound (10).Source: C Proof of Theorem 1 · pp. 18–19

C.1 Proof of Lemma 1

The proof of Lemma 1 compares residuals of the original and related iterates after writing X = ˜XΣ.The passage states that ˜X has iid Gaussian entries N(0, 1/n).Source: §C.1 · p. 19

C.2 Proof of Lemma 2

The Lemma 2 proof uses a probability bound over all i, obtained by a union bound.

C.2 Proof of Lemma 2

The proof combines two bounds before applying the union bound over all i.Source: §C.2 · p. 20
A union bound over all i gives the stated probability bound 1 − 2d(e^−β²/2 + e^−n/8).Source: §C.2 · p. 20
The stated probability bound is 1 − 2d(e^−β²/2 + e^−n/8).Source: §C.2 · p. 20

C.3 Proof of Lemma 3

The proof uses concentration bounds for conditioned random variables, combines the resulting events, and concludes the lemma.

Conditioned on z, Zi is treated as a squared Gaussian with a variance upper bound.Source: §C.3 · p. 21
A standard sub-exponential concentration inequality is used to obtain events conditioned on z.Source: §C.3 · p. 21
A union bound combines the events, and the resulting bounds complete the lemma proof.Source: §C.3 · p. 21

D Proof of Proposition 1

The risk expression is a sum of U-shaped curves, and the proof minimizes one curve to characterize its minimum.

The risk expression is a sum of U-shaped curves, R(θ̃_t) = σ² + Σ_i U_i(t).Source: D Proof of Proposition 1 · p. 22
The proof finds the minimum of one curve by setting its derivative to zero and solving for the iteration condition.Source: D Proof of Proposition 1 · p. 22
Under the relation specified in equation (18), the minimum is independent of iteration t and stepsize.Source: D Proof of Proposition 1 · p. 22

E Proof and statements for neural networks

The neural-network result specifies data and initialization conditions, then bounds the risk with high probability; Theorem 2 follows by selecting the error parameter as O(α).

Theorem 3 assumes iid data with unit-norm inputs and bounded labels, along with stated conditions on the network and initialization.Source: E Proof and statements for neural… · p. 22
Under these conditions, the risk after t gradient-descent iterations obeys a bound with probability at least 1 − δ.Source: E Proof and statements for neural… · p. 22
Theorem 2 follows from Theorem 3 by choosing the error parameter ξ = O(α).Source: E Proof and statements for neural… · p. 22

E.1 Proof of Theorem 3

The proof controls training and generalization risk using linearized network dynamics and Rademacher complexity, with preliminaries connecting the network's expected initialization Jacobian to its layer kernels.

E.3 Proof of Theorem 4 (bound on the training error)

Theorem 4 controls training error and shows that the network coefficients deviate little from their initialization.Source: §E.1 · p. 23

E.1 Proof of Theorem 3

The risk proof combines a training-risk bound with Rademacher-complexity control of generalization; sufficiently wide networks' training loss follows linear least-squares dynamics governed by the Gram matrix.Source: §E.1 · pp. 23–25

E.2 Preliminaries

The expected Jacobian at initialization and its singular values underpin the analysis, with separate kernels associated with the first and second layers.Source: §E.2 · p. 26

E.3.1 The dynamics of linear and nonlinear least-squares

Within the stated assumptions, nonlinear and linearized residuals remain close; the nonlinear problem therefore behaves similarly to its linearized counterpart near initialization.Source: §E.3.1 · pp. 28–29

E.3.2 Proving Theorem 4 by applying Theorem 6

The proof applies Theorem 6 to the network predictions and verifies its conditions with high probability. It then bounds training error, distance from initialization, and changes in individual layer coefficients.

E.3.2 Proving Theorem 4 by applying Theorem 6

A reference Jacobian is chosen close to the initialization Jacobian, and the proof verifies the required Jacobian conditions with high probability.The construction uses Lemma 7; the bound on the initialization radius supports verification of the Jacobian conditions.Source: §E.3.2 · pp. 29, 31, 32
Gaussian concentration bounds the network output and initial residual, using unit-norm inputs and the assumption |y_i| ≤ 1.The proof then uses these bounds when checking the theorem’s conditions.Source: §E.3.2 · pp. 29–30

E.3.3 Proof of lemma 8

Lemma 8 controls Jacobian variation near initialization by bounding changes in activation signs under a parameter perturbation.Its proof bounds the number of sign flips between XW and XW′.Source: §E.3.2 · p. 32, §E.3.3 · p. 35

E.3.2 Proving Theorem 4 by applying Theorem 6

Theorem 4’s conditions hold with probability at least 1 − O(δ), after which the proof bounds training error and deviations from initialization.The subsequent bounds cover parameter distance and changes in individual coefficients.Source: §E.3.2 · pp. 32–33

E.4 Proof of Lemma 4 (bound on the Rademacher complexity)

The proof bounds empirical Rademacher complexity for the constrained network by separating the initialization linearization from deviations caused by activation changes.

E.4 Proof of Lemma 4 (bound on the Rademacher complexity)

For small parameter movement, Gaussian anticoncentration makes the ReLU derivative constant for most coefficients, motivating a bound on the nonlinear deviation.The proof treats coefficients with changing activation separately from those whose ReLU derivative remains constant.Source: §E.4 · p. 36
The complexity bound combines a term for the initialization Jacobian with a term accounting for the difference between the network and its linearization.The derivation bounds these two terms and combines them to obtain the stated Rademacher-complexity bound.Source: §E.4 · p. 37