PaperlayerView exact revision on arXiv

Source-linked AI summary

RATT: Leveraging Unlabeled Data to Guarantee Generalization

Saurabh Garg, Sivaraman Balakrishnan, J. Zico Kolter, Zachary C. Lipton

arXiv:2105.00303v2cs.LGstat.ML

TL;DR

Conventional bounds can be vacuous for overparameterized models, while holdout validation reduces training data and repeated reuse can erode its validity. RATT adds randomly labeled fresh unlabeled examples to training data, tracks their error to upper-bound population risk, and proves results for linear classifiers trained by gradient descent on squared loss. Across computer-vision and NLP benchmarks, the bound is non-vacuous and tracks test error; deep-learning guarantees require an additional assumption.

  • Problem

    Conventional bounds can be vacuous for overparameterized models, while holdout validation reduces training data and repeated reuse can erode its validity.

    Source: §1 · p. 1

  • Method

    RATT adds randomly labeled fresh unlabeled examples to training data, tracks their error to upper-bound population risk, and proves results for linear classifiers trained by gradient descent on squared loss.

    Source: §1 · pp. 1–2

  • Results

    Across computer-vision and NLP benchmarks, the bound is non-vacuous and tracks test error; deep-learning guarantees require an additional assumption.

    Source: §1 · p. 2

  • Takeaways & Limitations

    RATT offers a post-training generalization-bound option when holdout validation is unavailable, and its bounds exploit early learning when it occurs.

    Source: §1 · p. 2, §6 · p. 8

    The theory does not guarantee that early learning will occur, so non-vacuous bounds are available a posteriori when that phenomenon occurs.

    Source: §1 · p. 2

Abstract

from arXiv · show

To assess generalization, machine learning scientists typically either (i) bound the generalization gap and then (after training) plug in the empirical risk to obtain a bound on the true risk; or (ii) validate empirically on holdout data. However, (i) typically yields vacuous guarantees for overparameterized models. Furthermore, (ii) shrinks the training set and its guarantee erodes with each re-use of the holdout set. In this paper, we introduce a method that leverages unlabeled data to produce generalization bounds. After augmenting our (labeled) training set with randomly labeled fresh examples, we train in the standard fashion. Whenever classifiers achieve low error on clean data and high error on noisy data, our bound provides a tight upper bound on the true risk. We prove that our bound is valid for 0-1 empirical risk minimization and with linear classifiers trained by gradient descent. Our approach is especially useful in conjunction with deep learning due to the early learning phenomenon whereby networks fit true labels before noisy labels but requires one intuitive assumption. Empirically, on canonical computer vision and NLP tasks, our bound provides non-vacuous generalization guarantees that track actual performance closely. This work provides practitioners with an option for certifying the generalization of deep nets even when unseen labeled data is unavailable and provides theoretical insights into the relationship between random label noise and generalization.

1. Introduction

Existing generalization bounds and holdout validation each have drawbacks; RATT uses randomly labeled unlabeled examples to estimate a post-training risk bound. Its guarantees apply directly to 0-1 ERM and linear models, while deep-learning guarantees rely on an additional assumption and benefit when early learning occurs.

1. Introduction

  • Uniform-convergence bounds can fail to explain overparameterized networks’ generalization, while holdout validation reduces training data and loses validity with repeated reuse.The paper also notes empirical studies finding adaptive overfitting surprisingly absent on large benchmarks.Source: §1 · p. 1
  • RATT augments clean training data with fresh unlabeled examples assigned random labels, then tracks error on that portion to upper-bound population error.The tracked error estimates error on the mislabeled portion.Source: §1 · p. 1
  • RATT’s bound is non-vacuous when classifiers fit clean data but retain high error on randomly labeled data, and its validity is proved for 0-1 ERM.The guarantee is post hoc: the theory does not ensure that early learning will occur.Source: §1 · pp. 1–2
  • On binary CIFAR, the RATT bound closely tracks clean-data population accuracy for ResNet and MLP results aggregated over five seeds.The asterisk marks best test performance using only clean data with the same hyperparameters, except for stopping point.Source: Figure 1 · p. 2
  • For linear classifiers, the results extend to gradient descent and early stopping, and—without data-distribution assumptions—to kernel regression and neural networks in the NTK regime.The early-stopping extension uses the connection between early stopping and ℓ2 regularization in linear models.Source: §1 · p. 2
  • For deep learning, the guarantee requires an additional assumption; the authors present RATT as an option when holdout validation is unavailable, not a blanket replacement.They motivate its usefulness through early learning, when networks fit true labels before noisy labels.Source: §1 · p. 2

2. Preliminaries

The preliminaries establish notation for classification error and datasets, then define randomly labeled data and its clean and mislabeled portions.

2. Preliminaries

  • The paper uses Euclidean norm and inner-product notation, vector-coordinate notation, and an event indicator.The indicator is binary.Source: §2 · p. 2
  • A dataset S contains n i.i.d. examples from distribution D, and empirical distributions are denoted for datasets S, T, and rS.The classifier class F maps inputs to real-valued class scores, and a training algorithm returns a classifier in F.Source: §2 · p. 2
  • Randomly labeled data draws inputs from the underlying input distribution and assigns labels uniformly at random; its examples split into clean and mislabeled portions.The mislabeled distribution reassigns labels to incorrect classes, renormalizing the label marginal.Source: §2 · p. 2

3. Generalization Bound for RATT with ERM

The ERM result bounds clean population error using clean-training error and error on randomly labeled training data. The section develops estimation steps for that bound and extends it to regularized ERM and multiclass classification.

3. Generalization Bound for RATT with ERM

  • For binary classification, the clean population error is bounded by clean empirical error plus 1 − 2 times error on randomly labeled data, with a finite-sample term.The bound is useful when clean-data error is low and randomly labeled-data error is high; the finite-sample term is independent of hypothesis-class complexity and decays at O(1/√m) when m < n.Source: §3 · p. 3
  • The proof first bounds population error using error on the mislabeled subset, then estimates that error from randomly labeled and clean training data.Clean and randomly labeled examples with correct labels are exchangeable, enabling estimation from clean-training error.Source: §3 · p. 3
  • The binary bound’s dominating term is no looser than a Rademacher-complexity bound, as randomly labeled-data accuracy is bounded by that complexity measure.The comparison applies to the underlying input distribution.Source: §3 · p. 4
  • For regularized ERM, the guarantee holds when the regularization coefficient is independent of the training data.The result also yields a corollary for L2-penalized parameters when randomly labeled-data error is high.Source: §3 · p. 4
  • The multiclass extension assigns random labels uniformly among classes and bounds population error using clean and randomly labeled-data errors.Its proof separates errors on mislabeled examples according to whether the classifier predicts the true label or neither the true nor assigned label.Source: §3 · p. 4

4. Generalization Bound for RATT with Gradient Descent

For linear classifiers, the section extends RATT’s bound to gradient descent on squared loss under a hypothesis-stability condition, with a corresponding multiclass extension. It also connects the result to kernel and NTK models and explains when early-stopped GD may inherit the guarantee.

4. Generalization Bound for RATT with Gradient Descent

  • For linear models, the analysis uses gradient descent on an L2-regularized problem, motivated partly by squared loss’s analytical convenience.The discussion notes that squared-loss minimization can be comparable to cross-entropy on classification tasks.Source: §4 · p. 5
  • With Condition 1 and β = O(1), Theorem 4 bounds clean population error for a linear classifier trained by gradient descent; a parallel result extends to multiclass classification.The section states that the squared-loss GD bound has the same dominating population-error term as Theorem 1.Source: §4 · p. 5
  • Hypothesis stability relates training error on a mislabeled point to leave-one-out error, which is then compared with population error on the mislabeled distribution.The section describes this condition as mild but not sufficient to guarantee generalization.Source: §4 · p. 5
  • Because the linear-model result assumes no data-distribution regularity, it extends to kernel regression and wide neural networks in the NTK regime.The neural-network connection applies where weights change little during training.Source: §4 · pp. 5–6
  • For λ = 1/(tη), sufficiently late GD iterates stay close to a corresponding regularized solution, suggesting RATT guarantees may hold for early-stopped GD.The proposition bounds expected squared difference; relating that quantity to classification-error differences requires additional conditions.Source: §4 · p. 6
  • That squared-difference bound does not generally imply a bound on expected classification-error differences, though low-noise margin assumptions can relate them.The section gives the Tsybakov noise condition as an example.Source: §4 · p. 6
  • For deep models, extending the guarantee requires assuming training on clean and randomly labeled data overfits the randomly labeled portion in the stated sense.Under that assumption, the earlier results extend beyond 0-1 ERM to general learning algorithms.Source: §4 · p. 6

5. Empirical Study and Implications

Across the reported multiclass settings, RATT gives non-vacuous bounds, and experiments on deep and simpler models show bounds tracking unseen-data performance under suitable training conditions. Interpolation without regularization can make the bound vacuous, whereas early stopping or weight decay yields tighter guarantees.

Experimental setup

  • Experiments cover toy and benchmark binary tasks plus MNIST and CIFAR-10 multiclass tasks, using clean data augmented with randomly labeled examples and standard training.The evaluation spans wide networks, MLPs, ResNet-18, LSTMs with ELMo embeddings, and fine-tuned BERT.Source: §5 · pp. 6–7

Underparameterized linear models

  • On toy Gaussian data, adding randomly labeled examples barely changes clean unseen accuracy, while RATT gives a tight lower bound on that accuracy.The experiments report the same behavior with SGD; the predicted accuracy bound rises as the unlabeled fraction increases.Source: §5 · p. 7

Wide Nets

  • With wide-network SGD interpolation and no regularization, extra random labels hurt clean performance and the bound is vacuous; early stopping or weight decay gives tight bounds with little performance change.The reported behavior also holds for GD and when cross-entropy replaces MSE.Source: §5 · p. 7

Empirical results

  • Across all four multiclass settings, RATT predicts non-vacuous performance on unseen data, with a tight bound and a small gap between best and test accuracy.Table 1 reports predicted accuracy, test accuracy on unseen clean data, and best accuracy from clean-only training; its remaining bound term is 30.7 at the stated sample size and δ = 0.1.Source: Table 1 · p. 8, §5 · p. 8

Deep Nets

  • 79.8 predicted accuracy versus 88.04 true performance on IMDb BERT; across tested deep models, bounds were never violated and tracked performance from training’s start.The experiments include ResNet-18 and 5-layer MLPs on binary CIFAR, plus ELMo-LSTM and BERT-Base on IMDb.Source: §5 · pp. 7–8, Figure 2 · p. 7

6. Discussion and Connections to Prior Work

The paper positions RATT as a post-hoc bound that uses unlabeled data and the early-learning pattern rather than relying directly on model-class complexity. It distinguishes this approach from related complexity-based and noisy-data methods while noting its reliance on early stopping or weight decay for overparameterized networks.

Implicit bias in deep learning

  • Prior work reports that gradient descent often fits clean data before mislabeled data early in training; RATT uses this pattern to produce non-vacuous bounds.The paper says early stopping or weight decay can accentuate the pattern and tighten guarantees.Source: §6 · p. 8

Generalization bounds

  • Unlike uniform-convergence bounds that are typically numerically loose, RATT avoids direct dependence on model-class complexity and can permit a perfect clean-data fit when mislabeled-data fit remains poor.The paper describes its bound as post-hoc and enabled by unlabeled data.Source: §6 · p. 8

Leveraging noisy data to provide generalization guarantees

  • Compared with Bansal et al. (2020), RATT addresses supervised learning and relies on early learning, while the cited parallel work bounds linear classifiers on self-supervised representations.The paper says the frameworks’ methodologies, claims, and generalization results differ.Source: §6 · p. 8

Other related work

  • RATT assumes a benign stability condition to relate leave-one-out performance to population error, but not a stability condition that itself implies generalization.The related-work discussion contrasts this with work deriving guarantees from uniform stability of early-stopped SGD.Source: §6 · p. 9

7. Conclusion and Future work

The conclusion presents RATT as a way to obtain bounds that do not directly depend on model-class complexity and identifies broader theoretical and interpolation-regime extensions as future work.

7. Conclusion and Future work

  • A next theoretical target is proving the random-label overfitting step for SGD across broader model classes and loss functions.The conclusion also proposes studying interpolation by discarding randomly labeled data after initial training stages.Source: §7 · p. 9

Supplementary Material

The supplementary material supplies concentration tools and proof details for the binary results, including the regularized ERM extension. The proofs combine bounds on clean and randomly labeled data to control clean population error.

Supplementary Material

  • The concentration toolkit includes Hoeffding bounds for independent bounded variables and sampling without replacement, plus McDiarmid’s inequality under a bounded-difference condition.It also introduces a condition for extending exponential concentration to dependent random variables.Source: Supplementary Material · p. 13

A.1. Proof of Theorem 1

  • Theorem 1’s proof combines three intermediate bounds to upper-bound clean population error with probability at least 1 − δ.The proof relates the mislabeled portion, the clean portion of randomly labeled data, and clean training error; its setup assumes roughly half the randomly labeled points are mislabeled.Source: §A.1 · p. 15

A.2. Proof of Proposition 1

  • The Proposition 1 proof rewrites binary classification accuracy using y · f(x) and applies McDiarmid’s inequality to obtain the desired result.The proof defines functions over random labels and inputs and establishes bounded-difference conditions for them.Source: §A.2 · p. 16

A.3. Proof of Theorem 2

  • Theorem 2’s proof extends the Theorem 1 argument to regularized ERM by comparing empirical error plus λR across the learned classifier and an optimizer.The proof retains the same general structure and assumes the randomly labeled dataset has approximately half mislabeled points.Source: §A.3 · pp. 16–17

A.4. Proof of Theorem 3

The multiclass proof relates error on randomly mislabeled data to clean population error, then combines concentration bounds to obtain a clean-error bound. The following section sets up a gradient-descent proof for a regularized linear model.

A.4. Proof of Theorem 3

  • For the mislabeled distribution, the proof gives E_D1[ f ] = 1 − (1/(k − 1)) E_D[ f ], relating its error to clean population error across k labels.The derivation handles the multiclass case by separating predictions of the true label from predictions of neither the true nor assigned label.Source: §A.4 · pp. 17–18
  • The multiclass proof combines three intermediate bounds to control clean population error from clean-training and randomly labeled-data errors.The proof treats the clean portion of the data as fixed and relates the mislabeled-data error to clean population error before combining the bounds.Source: §A.4 · pp. 19–20

B. Proofs from Sec. 4

  • The Sec. 4 proof sets up gradient descent on an L2-regularized objective for a linear model and states that its iterates converge to a limiting solution.The setup uses a clean dataset, a randomly labeled dataset, and initialization at w0 = 0.Source: B. Proofs from Sec. 4 · p. 21

B.1. Proof of Theorem 4

These parts develop generalization bounds for gradient-descent classifiers by relating training and leave-one-out errors and extending the analysis to multiclass settings. They examine the assumptions and stability conditions involved and analyze how regularized linear regression and gradient descent differ at training and test points.

B.1. Proof of Theorem 4

  • The proof obtains a relationship between E r SM and ED1 with polynomial rather than exponential concentration, combining Lemmas 2 and 3 with (74) by union bound with probability at least 1 − δ.Source: §B.1 · p. 23

B.2. Extension to multiclass classification

  • Theorem 5 extends the bound to multiclass squared-loss classifiers with one-hot labels and gradient descent satisfying Condition 1 with β = O(1).Its final inequality uses clean and randomly labeled data and, like the binary case, has polynomial concentration.Source: §B.2 · pp. 23–24

B.3. Discussion on Condition 1

  • Hypothesis stability controls the variance of empirical leave-one-out error; using Chebyshev’s inequality yields polynomial concentration, while stronger stability may allow exponential concentration (Abou-Moustafa & Szepesvári, 2019).The discussion notes that Theorem 4’s dominating term matches Theorem 1’s ERM bound, but its dependence on 1/δ is polynomial.Source: §B.3 · pp. 24–25

B.4. Formal statement and proof of Proposition 2

  • The appendix derives a closed-form expression for gradient-descent iterates using the SVD of the data matrix and states a proposition for λ = 1/(tη).It also introduces a lemma bounding 1 − (1 − x)^k for x in [0, 1] and positive integers k.Source: §B.4 · p. 25
  • The proof compares expected squared output differences for regularized linear regression and the tth gradient-descent iterate at training and unseen points, using λ = 1/(ηt).The unseen-point analysis uses the underlying covariance matrix Σ.Source: §B.4 · pp. 25–27

B.5. Extension to deep learning

  • Theorem 6 states a bound for multiclass classification with k classes under Assumption 1: for any δ > 0, its conclusion holds with probability at least 1 − δ.Source: §B.5 · p. 27

B.6. Justifying Assumption 1

  • Hypothesis stability and an assumption bounding training error by leave-one-out error imply Assumption 1 with a polynomial residual when β = O(1).The training-error condition says that error on a randomly labeled training datum is at most its error under a model trained with that datum left out.Source: §B.6 · pp. 27–28

C.1. Datasets

The experiments use a synthetic toy dataset and vision and NLP benchmarks, with linear and deep-network architectures. Figure 3 tracks accuracy and the bound as the unlabeled-data fraction varies for an SGD-trained linear model.

C.1. Datasets

  • The toy features pair label-dependent x1 with additional label-independent noise x2.The setup fixes d = 100, μ = 1.0, and σ at an incompletely specified value.Source: §C.1 · p. 29
  • MNIST and CIFAR10 are used for computer vision, with classes 0–4 mapped to 1 and 5–9 to −1; the NLP dataset is IMDb sentiment.CIFAR experiments use random crops and horizontal flips.Source: §C.1 · p. 29

C.2. Architecture Details

  • The architectures include a toy linear model, 2-layer wide networks, 4-layer MLPs, ResNet18, an ELMo-initialized LSTM, and fine-tuned BERT.The wide network experiments either fix the second layer at initialization or train both layers.Source: §C.2 · p. 29

Results with SGD on underparameterized linear models

  • Figure 3 plots accuracy and the corresponding bound against unlabeled-data fraction for the toy binary task with an SGD-trained linear model.Results aggregate three seeds; the supplied passage does not report the plotted values or trend.Source: Figure 3 · p. 30

Results with wide nets on binary MNIST

On CIFAR10 and MNIST, the oracle bound is tight and never violated in practice, while the theorem's dominating bound term is looser. On CIFAR100, RATT's bound is vacuous, though the oracle bound is tight early in learning.

Results with wide nets on binary MNIST

C.4. Hyperparameter Details

D. Proof of Lemma 12

The proof of Lemma 12 expresses the gap between population error and leave-one-out error on mislabeled points through component terms. It bounds these terms and combines them with a hypothesis-stability condition.

D. Proof of Lemma 12

  • The proof defines leave-one-out error on mislabeled points using classifiers trained after excluding individual examples.It denotes the resulting classifier by f(i) and the reduced training set by S1.Source: D. Proof of Lemma 12 · p. 33
  • In the proof, the authors state that they will bound term III and invoke Cauchy–Schwarz’s inequality to do so.Source: D. Proof of Lemma 12 · p. 33
  • Combining bounds on terms I and II from Bousquet and Elisseeff (2002) with the bound on term III and Condition 1 yields the required claim.The cited bounds apply because the sampled points come from the same distribution D1.Source: D. Proof of Lemma 12 · p. 33
Loading 2105.00303v2…