PaperlayerView exact revision on arXiv

Source-linked AI summary

In Defense of Uniform Convergence: Generalization via derandomization with an application to interpolating predictors

Jeffrey Negrea, Gintare Karolina Dziugaite, Daniel M. Roy

arXiv:1912.04265v3cs.LGstat.ML

TL;DR

The paper asks how uniform convergence can explain low-risk, zero-training-error predictors when learned hypotheses may not lie in classes with tight uniform bounds. It analyzes coupled surrogate predictors, including conditioned or denoised versions, and shows that these surrogates can support risk bounds for interpolating algorithms.

  • Problem

    Overparameterized learning can achieve low risk and zero empirical risk even when the learned classifier is not in a class with uniformly small two-sided generalization error.

    Source: §1 · p. 2

  • Method

    The paper extends uniform convergence to structural Glivenko–Cantelli sequences and analyzes learned predictors through coupled surrogates constructed by conditioning or denoising.

    Source: §1 · pp. 2–3, §6 · p. 9

  • Results

    Surrogate classes are shown to have structural Glivenko–Cantelli properties and yield risk bounds for overparameterized linear regression and a Nagarajan–Kolter-inspired interpolating example.

    Source: §1 · pp. 2–3

  • Takeaways & Limitations

    Uniform convergence can remain useful for interpolating predictors when applied to carefully constructed surrogate hypotheses rather than directly to the learned hypotheses.

    Source: §1 · p. 2, §7.3 · p. 12

    Some restrictions on the regression dimension may reflect the use of Massart’s Lemma and could be loosened by a more refined Rademacher-complexity bound.

    Source: §7.3 · p. 12

Abstract

from arXiv · show

We propose to study the generalization error of a learned predictor $\hat h$ in terms of that of a surrogate (potentially randomized) predictor that is coupled to $\hat h$ and designed to trade empirical risk for control of generalization error. In the case where $\hat h$ interpolates the data, it is interesting to consider theoretical surrogate classifiers that are partially derandomized or rerandomized, e.g., fit to the training data but with modified label noise. We also show that replacing $\hat h$ by its conditional distribution with respect to an arbitrary $\sigma$-field is a convenient way to derandomize. We study two examples, inspired by the work of Nagarajan and Kolter (2019) and Bartlett et al. (2019), where the learned classifier $\hat h$ interpolates the training data with high probability, has small risk, and, yet, does not belong to a nonrandom class with a tight uniform bound on two-sided generalization error. At the same time, we bound the risk of $\hat h$ in terms of surrogates constructed by conditioning and denoising, respectively, and shown to belong to nonrandom classes with uniformly small generalization error.

1. Introduction

The paper defends uniform convergence for interpolating algorithms by analyzing them through surrogate predictors, extending uniform convergence to sequences of increasing-complexity learning problems. It applies this framework to overparameterized regression and a Nagarajan–Kolter-inspired example.

1. Introduction

  • The paper argues that learned classifiers can achieve low risk and zero empirical risk without belonging, even with high probability, to a class with uniformly small generalization error.This challenges the assumption underlying much recent work on generalization in overparameterized models, including the construction of Nagarajan and Kolter (2019).Source: §1 · p. 2
  • The paper defines structural Glivenko–Cantelli classes to extend uniform convergence to sequences of learning problems whose complexity increases with sample size.Traditional Glivenko–Cantelli classes do not apply when model complexity or even the sample space changes with the dataset size.Source: §1 · p. 2, §1.1 · p. 3
  • Surrogate predictors provide a general strategy for analyzing interpolating algorithms whose original hypotheses lack uniformly small two-sided generalization bounds.The surrogate mimics the original algorithm while belonging to a class with a uniform, vanishing generalization bound.Source: §1 · p. 2, §1.1 · p. 3

1.1. Contibutions.

  • For overparameterized linear regression, the paper shows that the original hypothesis spaces are not structural Glivenko–Cantelli but can be analyzed through surrogate sequences under the hypotheses of Bartlett et al. (2019).The surrogate is the minimum-norm interpolating solution with label noise removed, and the resulting risk bounds are similar to those of Bartlett et al. (2019).Source: §1 · p. 3, §1.1 · p. 3
  • Conditioning constructs surrogate classifiers by partially rerandomizing the training data, trading empirical risk against generalization error.Applied to a Nagarajan–Kolter-inspired example, the method yields a structural Glivenko–Cantelli surrogate class and risk bounds exhibiting double descent.Source: §1 · p. 3, §1.1 · p. 3
  • The paper’s contributions include defining structural Glivenko–Cantelli convergence, introducing surrogate-based analysis, and applying it to two overparameterized learning settings.The applications include overparameterized linear regression inspired by Bartlett et al. (2019) and a conditioning-based example inspired by Nagarajan and Kolter (2019).Source: §1.1 · p. 3

2. Preliminaries

The preliminaries formalize randomized hypotheses, empirical loss, population risk, and interpolation for a learned classifier. They represent deterministic hypotheses as degenerate distributions, allowing randomized surrogates in the same framework.

2. Preliminaries

  • A hypothesis space H is embedded into distributions over hypotheses by mapping each h to the Dirac measure δ_h.This lets deterministic and randomized predictors share common definitions of loss and risk.Source: §2 · p. 4
  • Empirical loss is defined using the empirical distribution of the training sample, while population risk is defined using the data distribution.For deterministic hypotheses, both quantities are recovered by evaluating the corresponding distributional definitions at δ_h.Source: §2 · p. 4
  • A hypothesis interpolates a dataset when its empirical loss is zero, and a learning algorithm is interpolating when this holds almost surely for its output.This formalizes the zero-training-error setting studied throughout the paper.Source: §2 · p. 4

3. Structural Uniform Convergence

Structural Glivenko–Cantelli generalizes uniform convergence to learning problems whose hypothesis classes and sample sizes vary together. This framework captures failures in interpolating regimes while connecting to classical, PAC, and nonuniform learnability.

3. Structural Uniform Convergence

  • Structural Glivenko–Cantelli addresses sequences where the learning problem size and sample size both vary, formalizing the failure of standard uniform convergence in interpolating examples.The classical notion is recovered when the classes are constant and the sample size equals the indexing parameter.Source: §3 · p. 4
  • A sequence of hypothesis classes is structural Glivenko–Cantelli when its uniform convergence guarantee is indexed jointly by the data-generating distributions and sample sizes.Source: §3 · p. 4
  • The property fails in the examples of Nagarajan and Kolter (2019), showing that no suitable structural uniform-convergence guarantee covers those interpolating learning problems.Source: §3 · p. 4
  • Structural Glivenko–Cantelli connects PAC learnability and nonuniform learnability to uniform convergence through their standard equivalences and class decompositions.PAC learnability implies structural Glivenko–Cantelli, while nonuniform learnability corresponds to a countable union of VC classes.Source: §3 · p. 5
  • Restricting empirical-risk minimization to H(p) at sample size n_p yields low generalization error under the structural framework.Source: §3 · p. 5

4. Decompositions of Generalization Error using Surrogate Classifiers

The surrogate decomposition rewrites a learned predictor’s generalization error into approximation and surrogate-generalization terms. Choosing a coupled surrogate trades empirical risk against a uniformly controllable generalization component.

4. Decompositions of Generalization Error using Surrogate Classifiers

  • The decomposition follows directly from linearity of expectation, provided the three terms on its right-hand side are finite.Source: §4 · p. 5
  • The decomposition separates the learned predictor’s generalization error into the surrogate’s generalization error and two risk-difference terms.Source: §4 · p. 5
  • For an interpolating predictor, a surrogate can trade excess empirical risk for lower surrogate generalization error.This is the central use of the decomposition when the learned predictor has zero empirical risk.Source: §4 · p. 5
  • Uniform control can be obtained by placing the coupled surrogate in a nonrandom class with a tight two-sided generalization bound.Source: §4 · p. 6
  • The surrogate class acts like a one-step cover whose uniformly controlled component is separated from approximation error that may not vanish uniformly.This divides the explanation of generalization into a uniform-convergence portion and a portion handled by other techniques.Source: §4 · p. 6

5. Overparameterized Linear Regression

In overparameterized linear regression, the learned minimum-norm interpolator lacks structural uniform convergence, but a label-denoised surrogate belongs to an SGC class and yields an expected-risk bound.

5.1. Construction.

  • The model uses random-design overparameterized linear regression with sub-Gaussian motivation, Gaussian specialization, squared loss, and a minimum-norm interpolating estimator.Source: §5 · p. 6, §5.1 · p. 7

5.3. Introducing a surrogate.

  • The minimum-norm interpolating predictor lacks structural uniform convergence, while its label-denoised surrogate has structural Glivenko–Cantelli behavior under benign covariance conditions.The surrogate-based analysis is presented for Gaussian random design and Gaussian responses, with sub-Gaussian extensions noted.Source: §5 · p. 6, §5.2 · p. 7, §5.3 · p. 8

5.2. Failure of uniform convergence for this problem.

  • The failure result rules out a sequence of measurable high-probability events on which the learned predictor would satisfy the required uniform generalization control.Source: §5.2 · p. 7

5.3. Introducing a surrogate.

  • The surrogate removes label noise by replacing the response-driven minimum-norm interpolator with the projection of the true coefficient vector onto the design’s row space.Source: §5.3 · p. 7
  • The surrogate decomposition matches the terms Bartlett et al. (2019) bounded separately, although this paper derives them from the surrogate choice rather than bias–variance decomposition.Source: §5.3 · p. 8
  • Theorem 5.4 combines surrogate-class uniform convergence with control of the learned predictor–surrogate risk difference to bound expected generalization error.The resulting bound is similar to what follows by converting Bartlett et al. (2019)’s high-probability bound into expectation.Source: §5.3 · p. 8
  • The surrogate’s approximation component need not vanish; under benign covariance matrices, it tends to σ2, while otherwise its behavior may be more erratic.Source: §5.3 · pp. 8–9

6. Constructing Surrogates by Conditioning

Conditioning constructs a surrogate as the conditional distribution of the learned predictor, preserving expected risk while reducing dependence on the training data. The method trades empirical fit for generalization control but has tautological endpoints.

6. Constructing Surrogates by Conditioning

  • The conditioning recipe retrains on data equal in distribution to the original sample but partially rerandomized, thereby trading empirical risk for generalization error.Source: §6 · p. 9
  • Conditioning on a σ-field produces a surrogate probability measure Q equal to the conditional distribution of the learned predictor.Source: §6 · p. 9
  • Derandomization via conditioning preserves expected population risk because E[LD(ĥ) − LD(Q)] = 0.Source: §6 · p. 9
  • The surrogate is less data-dependent than the learned predictor, so interpolation or overfitting can be exchanged for excess empirical risk and lower generalization error.Source: §6 · p. 9
  • Conditioning interpolates between two tautological endpoints: the unconditional distribution of ĥ and the point mass δ_ĥ obtained by conditioning on the full sample.Intermediate conditioning is intended to yield a non-tautological surrogate bound.Source: §6 · pp. 9–10

7. Hypercube classifier

The hypercube example shows that an interpolating classifier can have low risk even when uniform convergence fails for every relevant nonrandom class. Conditioning produces a surrogate with similar performance whose class satisfies structural Glivenko–Cantelli conditions, yielding a useful derandomized bound.

7.1. Construction.

  • The classifier errs only when a test point is absent from training but its antipode is present, explaining its small true risk despite interpolation.Source: §7.1 · p. 10, §7.2 · p. 11

7.2. Failure of uniform convergence for this problem.

  • For n_d ≤ 2^(2d−1), the accessible hypothesis class has VC dimension at least n_d, so standard VC-based uniform convergence is not informative.Source: §7.2 · p. 11
  • The hypercube classifier interpolates almost surely and has risk at most n_d 2^-2d when n_d is subexponential in 2^d.Source: §7.2 · p. 11

7.3. Introducing a surrogate classifier.

  • The surrogate Q conditions on a projection of the training data, effectively rerandomizing the first k_d features and associated labels while retaining the remaining features.Source: §7.3 · p. 11
  • Increasing derandomization trades training empirical risk for exponentially decreasing adversarial empirical risk, while leaving true risk unaffected.Source: §7.3 · p. 12
  • If n_d grows slower than 2^(k_d/d), the surrogate classes are structural Glivenko–Cantelli; suitable k_d choices make the original classifier’s generalization error vanish.Source: §7.3 · pp. 12–13

7.4. Interpreting the derandomization bound.

A. Proofs for hypercube classifier

The proofs bound antipodal collisions and surrogate complexity, then combine these estimates to establish the hypercube derandomization result.

B. Proofs for Overparameterized Linear Regression

The linear-regression proofs compare noisy and denoised interpolating solutions through a surrogate decomposition and use projection and covariance arguments to establish the required bounds.

Loading 1912.04265v3…