PaperlayerView exact revision on arXiv

Source-linked AI summary

Reconciling modern machine learning practice and the bias-variance trade-off

Mikhail Belkin, Daniel Hsu, Siyuan Ma, Soumik Mandal

arXiv:1812.11118v2stat.MLcs.LG

TL;DR

The paper addresses the tension between the classical bias-variance trade-off and accurate interpolation by modern high-capacity models. It unifies these behaviors through a double descent risk curve and proposes an inductive-bias-based mechanism for its emergence. The authors report that increasing capacity beyond interpolation typically lowers risk below the classical sweet spot, while noting that optimization and regularization can obscure the pattern.

  • Problem

    Modern high-capacity models can interpolate training data yet generalize accurately, challenging the classical bias-variance account of how capacity affects prediction.

  • Method

    The paper studies how performance changes with function-class capacity across model classes and datasets, interpreting double descent through inductive biases favoring smooth, low-norm interpolants.

  • Results

    Increasing function-class capacity beyond the interpolation threshold typically decreases risk, often below the risk at the classical sweet spot.

  • Takeaways & Limitations

    The double descent curve reconciles the classical U-shaped trade-off with rich-model behavior and is argued to be ubiquitous in machine learning applications.

  • Takeaways & Limitations

    Non-convex optimization, narrow interpolation peaks, initialization sensitivity, and regularization or early stopping can mask double descent in neural-network experiments.

Abstract

from arXiv · show

Breakthroughs in machine learning are rapidly changing science and society, yet our fundamental understanding of this technology has lagged far behind. Indeed, one of the central tenets of the field, the bias-variance trade-off, appears to be at odds with the observed behavior of methods used in the modern machine learning practice. The bias-variance trade-off implies that a model should balance under-fitting and over-fitting: rich enough to express underlying structure in data, simple enough to avoid fitting spurious patterns. However, in the modern practice, very rich models such as neural networks are trained to exactly fit (i.e., interpolate) the data. Classically, such models would be considered over-fit, and yet they often obtain high accuracy on test data. This apparent contradiction has raised questions about the mathematical foundations of machine learning and their relevance to practitioners. In this paper, we reconcile the classical understanding and the modern practice within a unified performance curve. This "double descent" curve subsumes the textbook U-shaped bias-variance trade-off curve by showing how increasing model capacity beyond the point of interpolation results in improved performance. We provide evidence for the existence and ubiquity of double descent for a wide spectrum of models and datasets, and we posit a mechanism for its emergence. This connection between the performance and the structure of machine learning models delineates the limits of classical analyses, and has implications for both the theory and practice of machine learning.

1 Introduction

Machine learning traditionally balances under-fitting and over-fitting through a U-shaped risk curve, yet modern high-capacity models can interpolate training data while generalizing accurately. The paper introduces double descent, extending the classical curve beyond interpolation and explaining improved test performance in richer function classes.

  • Machine learning seeks predictors that perform well on unseen data, creating a gap between minimizing training risk and minimizing true test risk.
  • Classical bias-variance reasoning recommends controlling function-class capacity to balance under-fitting from overly small classes against over-fitting from overly large classes.
  • Modern large neural networks often achieve near-perfect training fits while still making accurate predictions on new data, challenging the classical trade-off.
  • Double descent extends the classical U-shaped risk curve beyond the interpolation threshold, where increasing capacity can reduce risk after an interpolation-associated peak.The pattern has been observed across important model classes and datasets.
  • The proposed mechanism favors smooth, low-norm interpolating functions: larger classes contain more perfectly fitting candidates, including simpler ones under the relevant inductive bias.This provides an Occam’s-razor interpretation of why richer classes can improve performance.
  • Margins theory addresses some larger-margin classifiers but does not apply to regression or predict the second descent beyond interpolation.

2 Neural networks

Neural-network and related feature models exhibit double descent: test risk rises near interpolation, then improves as capacity increases further, consistent with increasingly smooth or small-norm predictors.

  • Random Fourier features: RFF models show a classical U-shaped test-risk curve below interpolation, peaking at the threshold N = n.Training risk approaches test risk when N ≪ n, while fitting becomes exact near interpolation.
  • Random Fourier features: Beyond interpolation, increasing RFF features sharply improves accuracy, eventually outperforming the classical sweet-spot predictor.The kernel-machine predictor from H∞ outperforms every finite-N RFF predictor in the reported experiment.
  • Inductive bias: Richer RFF classes can approximate the smallest-norm interpolating function more closely, so predictor norms are expected to decrease after interpolation.The norm is expected to be largest at the interpolation threshold and decrease monotonically as N increases.
  • Inductive bias: Random ReLU fits become smoother as feature count increases, with coefficient norm falling from approximately 695 at N = 40 to approximately 159 at N = 4000.Both fits remain piecewise linear, but the larger feature class produces the smoother-looking function.
  • Neural networks: Fully connected neural networks display a qualitatively similar double-descent curve as the number of parameters increases beyond interpolation.The observed improvement beyond interpolation is compatible with small-norm inductive biases associated with common neural-network training algorithms.
  • Neural networks: Neural-network experiments can obscure double descent because non-convex optimization and initialization-sensitive local search may produce variable, suboptimal risks.This difficulty is especially relevant in the under-parameterized regime, where increasing architecture size need not reduce training risk consistently.

3 Decision trees and ensemble methods

Double descent also appears in decision-tree ensembles when capacity is indexed by tree size before interpolation and by ensemble size afterward, extending the phenomenon beyond neural networks.

  • Evidence across ensemble methods: Boosting with decision trees and Random Forests show generalization behavior similar to neural networks on both sides of the interpolation threshold.The evidence covers prediction methods beyond neural networks and includes behavior before and after interpolation.
  • Decision-tree capacity: Decision-tree capacity is parameterized by the number of leaves, with trees of n leaves able to interpolate n training examples.The interpolation threshold may occur earlier, but n leaves provide an upper bound.
  • Random Forests: Beyond interpolation, the number of interpolating trees indexes ensemble capacity, revealing a double-descent curve for Random Forests.The corresponding Random Forest complexity is controlled by the number of trees and the maximum leaves per tree.
  • Boosting: The same ensemble-capacity perspective is also reported to produce similar behavior for L2-boosting.Those results are reported in the paper’s appendix.

4 Concluding thoughts

The paper presents double descent as a framework reconciling classical U-shaped risk with modern rich models, while linking its emergence to inductive bias and practical optimization.

  • The double descent curve reconciles the classical bias-variance prediction with the behavior of rich models in modern machine learning.
  • Historical absence: The double descent curve was historically difficult to observe because classical linear settings used fixed feature sets, while practical RFF models were usually restricted to N ≪ n.
  • General multilayer neural-network curves are harder to characterize because interpolation peaks can be narrow, initialization-sensitive, and obscured by early stopping.
  • Minimum-norm interpolation provides a common solution across explicit norm minimization, stochastic gradient descent, and Gaussian-process posterior averaging for kernel machines.
  • Optimization and practical considerations: Over-parameterized models can combine low test risk with easier optimization because local methods such as SGD often converge to global training-risk minima.
  • Outlook: The framework delineates limits of classical analyses and motivates comparing computational, statistical, and mathematical properties across classical and modern regimes.

A Approximation theorem

The approximation theorem analyzes interpolating hypotheses for noiseless samples from a smooth target class and bounds their approximation error through sample coverage and function norms.

  • The theorem considers noiseless iid samples from a target h* on a compact cube and any hypothesis h that interpolates all observed labels.
  • The proof bounds approximation error by applying a smoothness-based theorem to f(x) = h(x) − h*(x), which vanishes on the training points.
  • The argument also extends to more general domains and probability distributions, according to the accompanying remark.
  • With high probability, the fill distance of n uniformly sampled points satisfies κ_n = O((n/log n)^−1/d).
  • The minimum-norm interpolant has norm no larger than the target and therefore achieves the smallest bound supplied by the theorem.These bounds apply only in the noiseless setting.

B Experimental setup

The experiments train representative models on subsampled image, speech, and text classification datasets, measuring training and test risks across capacity through interpolation.

  • The study evaluates neural networks, kernel machines, and ensemble methods on widely used image, speech, and text datasets.
  • Datasets: The datasets use one-versus-rest classification, with preprocessing tailored to image, speech, and text inputs.
  • Datasets: Training sets are uniformly subsampled without replacement, while 20-Newsgroups uses a randomly selected 1/8 test subset.
  • Model training: Models minimize squared loss and can interpolate once capacity exceeds an interpolation threshold; experiments report zero-one and squared train/test risks.
  • Model training: Neural-network and ensemble results average five runs, whereas RFF and Random ReLU results use a single empirically consistent run.
  • Figure 8 studies Random ReLU predictors on MNIST and SVHN at n = 104, adding 4 · 10−6 regularization for SVHN near interpolation.

C Additional experimental results for neural networks

Additional experiments show double descent for Random Fourier and Random ReLU features across several real-world datasets, with similar risk and norm behavior between the feature families.

  • Additional RFF experiments show double descent on CIFAR-10 and 20-Newsgroups, with similar curves reported for TIMIT and SVHN.
  • The random feature vectors are sampled independently, with bandwidth values set separately for MNIST, SVHN, CIFAR-10, 20-Newsgroups, and TIMIT.
  • Random ReLU feature networks use ReLU-transformed random features with learned coefficients, and their risk curves also exhibit double descent.
  • Random ReLU experiments on MNIST and SVHN produce risk and norm curves very similar to those observed for RFF models.SVHN uses ridge regularization λ := 4 · 10−6 for numerical stability near interpolation; MNIST uses none.

C.3 Fully connected neural networks

The experiments vary fully connected neural-network capacity through hidden-unit count and train with SGD. Double descent remains visible across MNIST and CIFAR-10, including without weight reuse despite greater variance and nonmonotonic training loss.

  • Neural-network capacity is controlled by varying the number of hidden units in single-hidden-layer networks trained with SGD.
  • Weight reuse initializes larger under-parametrized networks from smaller trained networks to reduce SGD sensitivity to initialization.
  • Double descent is observed on MNIST and CIFAR-10 experiments using weight reuse.
  • Without weight reuse, double descent remains discernible despite significantly larger variance and nonmonotonic training loss.
  • Training uses momentum 0.95, different initialization schedules across the interpolation threshold, and stopping rules based on classification error or 6000 epochs.

C.4 Synthetic model

The synthetic model constructs random Fourier-like function classes whose capacity is the number of sampled basis functions, then fits them by empirical risk minimization. Simulations show a double-descent curve whose peak occurs at interpolation and whose high-capacity endpoint improves beyond the classical U-curve minimum.

  • The synthetic model uses periodic complex-valued functions on [0, 2π], viewed as a one-dimensional-circle version of random Fourier features.
  • For each N, the model samples N distinct indices and spans their basis functions, making N both the parameter count and capacity.
  • The data model uses uniformly sampled inputs on a finite grid, independent Gaussian noise, and signal-to-noise ratio defined as E[h*(x_i)^2]/σ^2.
  • Empirical risk minimization is ordinary least squares in an N-dimensional space, with interpolation achieved when N ≥ n.
  • For n = 256, the risk peak occurs at N = n, while the right endpoint is below the U-curve minimum and the learned-function norm decreases after N > n.
  • The supplied captions document double-descent curves for random forests and L2-boosting trees under increasing model complexity.

D Additional results with Random Forests

Random-forest experiments control model capacity with tree count and per-tree leaf limits. Double descent appears under both bootstrap-disabled and bootstrap-enabled settings, for squared loss and zero-one loss, although the U-shape is less apparent with zero-one loss.

  • Random-forest capacity is controlled by the number of trees and the maximum number of leaves allowed per tree.
  • Trees are grown without depth limits or minimum growth constraints, splitting nodes whenever possible.
  • With bootstrap resampling disabled, random forests show double descent under both squared loss and zero-one loss as capacity increases.
  • Bootstrap resampling produces similar double-descent behavior, while the U-shaped curve is less apparent with zero-one loss.

E Results with L2-boosting

L2-boosting experiments increase capacity through the numbers of trees and forests, producing double descent under both squared and zero-one loss. Strong shrinkage makes the pattern less apparent, consistent with a regularization effect.

  • Each L2-boosting tree has at most 10 leaves, and capacity is controlled by the numbers of trees per forest and forests averaged.
  • Double descent appears under both squared loss and zero-one loss as model capacity increases.
  • Strong overfitting occurs under squared loss before the interpolation threshold.
  • With shrinkage set to 0.1, the double-descent curve becomes less apparent because of the regularization effect of high shrinkage.
Loading 1812.11118v2…