betaFeedback

WorksComputer Science

What Interpolators Store and What They Express: An Information-Theoretic Framework for Benign Overfitting and Label-Free Model Selection

Abstract

Overparameterized learners can fit noisy training labels perfectly and still predict well, which neither classical complexity measures nor information-theoretic generalization bounds explain. We develop an information-theoretic framework that separates two things an interpolating learner does with its sample: storage, the information the trained model retains about its training labels, and expression, the information about the sample that reaches its predictions at fresh inputs. We first characterize the ideal model: for a loss l, the least complex l-sufficient representation is the Bayes act, whose entropy is the minimal sufficient complexity; this generalizes, and corrects, an earlier "lossless maximal compression" view of boosting. We then show that every interpolator stores exactly nH(Y|X) bits of label noise, so storage, and bounds built on it (including CMI bounds), cannot tell interpolators apart. Expression can: excess risk is bounded above and below by the expressed information V, the entropy over training samples of the prediction at an input, plus a modal-bias term, exactly so for binary labels. Benign overfitting is therefore vanishing expression, a picture that covers nearest-neighbour rules, averaging, minimum-norm least squares and double descent, and that links V to classical bias-variance decompositions and to model disagreement. Finally, V gives a model-selection criterion that needs no held-out labels. Among overparameterized learners on 15 noisy datasets, V estimated from two disjoint halves has 60% less regret than holdout validation at the same cost and matches 5-fold cross-validation at a quarter of its cost; at matched cost it also beats selection by conditional mutual information. We characterize when it fails and give remedies. Code: https://github.com/nnikolaou/GLMC

Introduction

Modern learners are routinely trained until they fit their training data perfectly, even when some of the training labels are wrong. Deep networks fit randomly relabelled data [75]. Random forests and boosted ensembles reach zero training error and keep improving [62, 72]. Minimum-norm least squares interpolates noisy targets and can still be consistent [7, 33]. This behaviour is called benign overfitting. It is not universal: other interpolators, such as the 1-nearest-neighbour rule, settle at a fixed excess risk (tempered overfitting), and some fail completely (catastrophic overfitting) [48]. All three kinds of learner have the same training error, zero, so whatever separates them is invisible on the training set.

In this paper we ask two questions about interpolating learners.

(Q1) What separates a benign interpolator from a harmful one? In particular, is there an information-theoretic quantity that does so, given that interpolators all memorize their training labels?

(Q2) Can we use that quantity to choose among interpolating learners? Training error cannot rank them, and validation labels may be scarce or noisy themselves.

Why information theory, and why it has struggled here. Information theory gives a natural language for “how much a model has learned from its data”. Information-theoretic generalization bounds control the generalization gap by the mutual information I(W;S)I(W; S) between the trained weights WW and the training sample SS [60, 73, 65]. The information bottleneck (IB) describes good representations as those that compress the input while keeping what is relevant for the label [69, 68]. Both views have difficulties with interpolators. Any learner that fits noisy labels must store them, so I(W;S)I(W; S) is large for every interpolator, benign or not [31, 46]. And for deterministic models the IB quantities are degenerate [3, 43, 61].

An earlier attempt. Two earlier non-archival papers by the author described margin-maximizing boosting as lossless maximal compression (LMC): a model whose output keeps all the information about the label that the input has, while being as compressed as possible [55, 54]; we refer to them as the LMC papers. That work had flaws. Its central object does not exist when labels are noisy, its empirical estimates are degenerate for any interpolator, and some of its experimental claims do not survive replication. We therefore do not treat it as an established framework. This paper builds the framework from scratch and corrects the earlier work as it goes. Appendix § 18 gives a full erratum.

Our approach in one paragraph. We separate what a learner stores from what it expresses. Storage is the information the trained model keeps about the training labels, I(W;Yn∣Xn)I(W; Y^n \mid X^n). Expression is the information about the training sample that reaches the model’s prediction at a fresh input xx. We measure it by the expressed information

V(x)=H(hW(x)),V(x) = H(h_W(x)),

the entropy1 of the prediction hW(x)h_W(x) at xx when the training sample (and any training randomness) is drawn afresh. In plain terms, V(x)V(x) is zero if every training sample leads to the same prediction at

xx, and it is large if the prediction at xx depends on which particular sample, and so which particular noisy labels, the learner happened to see. § 4.1 explains both words informally, with an analogy; in this sense, both are terms introduced in this paper (Table 2 lists which of our terms are new and which are standard). Storage and expression behave very differently for interpolators. Every interpolator stores exactly n H(Y∣X)n\,H(Y \mid X) bits of label noise (Theorem 5), so storage cannot tell them apart. Expression can: excess risk is controlled from above and below by expressed information plus a “modal bias” term (Theorem 9).

TermStatusDefinition and origin
ℓ\ell-sufficient, ℓ\ell-deficiencyAdaptedDecision-theoretic sufficiency and deficiency ([13, 45]) for one loss; Def. 1
Recalibrated risk Rℓ(T)R_{\ell}(T)New nameRisk of the best decoder of TT; standard idea; § 3.1
Minimal sufficient complexity Cℓ∗=H(a∗(X))C_{\ell}^{*} = H(a^{*}(X))NewUnder log-loss, the end point of the IB curve (Tishby et al. [69]); Def. 2
Maximal complexity Cmax⁡C_{\max}AdaptedFrom the LMC papers (Nikolaou et al. [55]); Def. 2
Excess complexity Eℓ\mathcal{E}_{\ell}NewRedundancy above the indirect rate–distortion function; Def. 2
G-LMCNewMinimal ℓ\ell-sufficient representation; generalizes the LMC of Nikolaou et al. [55]; Def. 2
Indirect rate–distortion functionStandardDobrushin and Tsybakov [22]; Witsenhausen [71]; eq. (1)
Storage I(W;Yn∣Xn)I(W;Y^{n}\mid X^{n})New termThe quantity appears in Harutyunyan et al. [31]; the name “storage” is ours; § 4.1, Thm. 5
Expression, expressed information V(x)V(x)NewDef. 3; relation to existing variances in § 4.6
Modal prediction m(x)m(x)New nameDomingos’ “main prediction” (Domingos [23]); Def. 3
Modal biasNew nameDomingos’ bias, here weighted by the margin; Thm. 9
Benign / tempered / catastrophicStandardMallinar et al. [48]; information reading in § 5.1
Memorize-and-smoothNewAn explicit benign interpolator; Prop. 16
Min-VV, V2V_{2}, V5V_{5}NewSelection by least expressed information, estimated from 2 disjoint halves or 5 folds; § 6
Consensus criterion, switch ruleNewLabel-free modal-bias estimate; asymmetry-triggered noise correction; § 6.4
Disagreement, GDEStandardJiang et al. [39]; § 4.6
CMI, supersampleStandardSteinke and Zakynthinou [65]; § 4.2

Table 2. Terminology. “New”: term (and, where stated, quantity) introduced in this paper. “Adapted”: an existing notion specialized or renamed here. “Standard”: used as in the cited literature.

A running example. We will use one simple task throughout the paper (Example 1 in § 2). The input consists of one informative discrete feature and 16 irrelevant binary features; the label is a noisy function of the informative feature. Every learner in Table 1 interpolates its noisy training labels, including a memorize-and-smooth learner that we construct for this purpose,2 and every one has the same score under the old LMC criterion.3 Yet their excess risks differ by two orders of magnitude, and their expressed information ranks them correctly. We return to this example at each step of the development.

LearnerTraining errorLegacy LMC scoreVV (bits)Excess risk
Memorize-and-smooth†0.0010.990.0070.001
Random forest0.0010.990.0450.005
Gradient boosting0.0010.990.4060.064
1-nearest neighbour0.0010.990.6420.125
Decision tree (full depth)0.0010.990.6600.131

Table 1. The running example (Example 1) with n=4096n = 4096 training points and label noise ε=0.2\varepsilon= 0.2. All five learners interpolate. The legacy LMC score of Nikolaou et al. [55] is the same for all of them, while their excess risks differ by two orders of magnitude. Expressed information VV (§ 4.3) ranks them correctly. Best value per column in bold (the two degenerate columns are identical for all learners). †: learner constructed in this paper (Proposition 16).

Contributions. Our contributions are the following.

  1. A framework for the ideal model (§ 3). For a general loss we define ℓ\ell-sufficient representations, the minimal sufficient complexity Cℓ∗=H(a∗(X))C_\ell^* = H(a^*(X)) (the entropy of the Bayes act), maximal complexity, and excess complexity. We relate them to decision-theoretic sufficiency, to the indirect rate–distortion function, and to the information bottleneck. We show that the original LMC exists only in degenerate cases, and that its generalized form, the minimal ℓ\ell-sufficient representation, always exists.

  1. Storage versus expression (§ 4). We show that every interpolator stores exactly n H(Y∣n\,H(Y \mid

X) bits of label noise (sharpening a bound of Harutyunyan et al., [31]), and that information-theoretic generalization bounds, including those based on conditional mutual information (Steinke and Zakynthinou, [65]), therefore cannot separate benign from tempered interpolators. We introduce expressed information and prove a two-sided information decomposition of excess risk, which is exact for binary labels. We show that a learner’s output entropy at fresh inputs splits into complexity and expression, and that a consistent learner’s outputs converge to the minimal sufficient representation.

  1. Benign overfitting as vanishing expression (§ 5). We give an information-theoretic version of the benign/tempered/catastrophic taxonomy. We work it out for an explicit benign interpolator, for nearest-neighbour rules (recovering the classical result of Cover and Hart, [17]), for averaging, and for minimum-norm least squares, where the expressed information equals the variance term of Bartlett et al. [7]. Double descent appears as a peak of expressed information.

  1. Expressed information as a model-selection criterion (§ 6). We show that among candidates with no modal bias, excess risk is monotone in expressed information, and we argue that the overparameterized regime is where this condition is most nearly met. We explain how to estimate VV from a single dataset, and why disjoint splits must be used. Because it needs no held-out labels, only unlabelled inputs, it suits settings where validation labels are scarce, delayed or noisy (semi-supervised and streaming data, label noise, covariate shift; § 9). We characterize where VV alone fails and give two remedies: a label-free consensus criterion, and a switch to noise-corrected validation when the label noise is asymmetric.

  1. Connections to bias–variance and disagreement (§ 4.6). We show that the 0-1 variances of Kohavi–Wolpert, Domingos and James and the disagreement of two independently trained models are equivalent to VV up to explicit bounds, and that disagreement bounds excess risk from above and below: the generalization disagreement equality of Jiang et al. [39] holds exactly for the 1-NN rule and fails by the Bayes risk for benign learners.

  1. Experiments (§ 7) on synthetic tasks with exact excess risk and on 15 real datasets. Among overparameterized candidates on a single noisy dataset, VV computed from two disjoint halves has 60% less regret than holdout validation and 44% less than 2-fold cross-validation at about the same cost, and matches 5-fold cross-validation (15 datasets, five seeds each). At matched cost it also beats selection by conditional mutual information, which, unlike VV, needs held-out labels.

Roadmap. § 2 fixes notation and introduces the running example. § 3 describes the ideal model. § 4 separates storage from expression, and § 5 uses this separation to explain benign overfitting. § 6 turns expressed information into a selection rule, and § 7 tests the theory and the rule. § 8 discusses connections to existing work, and § 9 discusses limitations. Proofs, further theory, the erratum for the LMC papers, experimental details, additional results and the extension to regression are in the appendices, which form the supplementary material. Code to reproduce every result is available at https://github.com/nnickolaou/GLMC, and Appendix § 24 describes it.

Setting, notation and a running example

Let us first fix the notation that we will use throughout, and introduce the simple example that we will return to in every section.

Data and Bayes classifier. A pair (X,Y)(X,Y) is drawn from a distribution PP on X×Y\mathcal{X} \times\mathcal{Y}. In most of the paper Y=[K]={1,…,K}\mathcal{Y} = [K] = \{1,\ldots,K\} is a set of KK classes; § 4.5 treats real-valued YY. For the information-theoretic statements we take X\mathcal{X} to be finite or countable with H(X)<∞H(X) < \infty (continuous inputs are handled by the learner-level quantities of § 4, which do not need this). We write

η(x)=(P(Y=1∣X=x),…,P(Y=K∣X=x))\eta(x) = \left(\mathbb{P}(Y=1 \mid X=x),\ldots,\mathbb{P}(Y=K \mid X=x)\right)

for the vector of class probabilities at xx. The Bayes classifier predicts the most likely class, b∗(x)=arg⁡max⁡kηk(x)b^*(x) = \arg\max_k \eta_k(x), and the Bayes risk R∗=P(b∗(X)≠Y)R^* = \mathbb{P}(b^*(X) \ne Y) is the smallest achievable error. Its excess risk, R(h)−R∗R(h)-R^* with R(h)=P(h(X)≠Y)R(h) = \mathbb{P}(h(X) \ne Y), measures how far a classifier hh is from that ideal. When the labels are noisy, R∗>0R^* > 0: even the best classifier makes mistakes, because the label is not a function of the input.

Learners. A training sample S=((X1,Y1),…,(Xn,Yn))S = ((X_1,Y_1),\ldots,(X_n,Y_n)) consists of nn independent draws from PP. A learner AA maps the sample, and possibly some internal randomness ξ\xi (a random seed, independent of SS), to a trained model W=A(S,ξ)W = A(S,\xi), which induces a classifier hW:X→[K]h_W : \mathcal{X} \to[K]. We say that the learner interpolates if hW(Xi)=Yih_W(X_i) = Y_i for every training point, almost surely. The important point to keep in mind is that WW is random: a different sample, or a different seed, gives a different trained model. Much of this paper is about how much the predictions of hWh_W vary because of this randomness.

Information measures. H(⋅)H(\cdot) denotes Shannon entropy, H(⋅∣⋅)H(\cdot\mid\cdot) conditional entropy and I(⋅;⋅)I(\cdot;\cdot) mutual information ([18]). Unless stated otherwise we measure them in bits. For a probability vector qq we write H(q)=−∑kqklog⁡2qkH(q) = -\sum_k q_k \log_2 q_k, and h(t)=H((t,1−t))h(t) = H((t,1-t)) is the binary entropy. Two quantities of the data distribution will appear repeatedly: H(Y∣X)H(Y \mid X), the label noise (the uncertainty about YY that remains when XX is known), and I(X;Y)I(X;Y), the information the input carries about the label.

The running example. We will illustrate every definition and result on the following task. It is chosen so that all quantities can be computed exactly, and so that it contains the two ingredients that matter: label noise, and input features that carry no information about the label.

Example 1 (Running example). The input is X=(Z,U)X = (Z,U), where ZZ is uniform on {0,1,…,7}\{0,1,\ldots,7\} and UU is uniform on {0,1}16\{0,1\}^{16}, independent of ZZ. The label is Y∈{0,1}Y \in\{0,1\}, and it depends on ZZ only: the clean label is 1{Z≥4}1\{Z \ge4\}, and it is flipped with probability ε\varepsilon when ZZ is even and with probability ε/2\varepsilon/2 when ZZ is odd. So ZZ is the informative part of the input, and the 16 bits of UU are pure distractors.

For ε=0.2\varepsilon= 0.2, which we use throughout unless stated otherwise, the quantities above are as follows.

  • The Bayes classifier is b∗(X)=1{Z≥4}b^*(X) = 1\{Z \ge4\}, and the Bayes risk is R∗=12(0.2)+12(0.1)=0.15R^* = \frac{1}{2}(0.2) + \frac{1}{2}(0.1) = 0.15.

  • The label noise is H(Y∣X)=12h(0.2)+12h(0.1)=0.595H(Y \mid X) = \frac{1}{2}h(0.2) + \frac{1}{2}h(0.1) = 0.595 bits per example.

  • H(X)=3+16=19H(X) = 3 + 16 = 19 bits, H(b∗(X))=1H(b^*(X)) = 1 bit, and η(X)\eta(X) takes four equally likely values, so H(η(X))=2H(\eta(X)) = 2 bits.

In words: a good model of this task needs to know only one bit about each input (which half ZZ falls in), out of the 19 bits the input contains. We will see in § 3 that these three numbers, 1, 2 and 19 bits, are respectively the minimal sufficient complexity under 0-1 loss, the minimal sufficient complexity under log-loss, and the maximal complexity. In § 4 we will see that the label noise of 0.595 bits per example is exactly what every interpolator must store.

Losses. Sections 4–6 focus on classification error (0-1 loss). The definitions of § 3 hold for a general loss ℓ:A×Y→[0,∞]\ell: \mathcal{A} \times\mathcal{Y} \to[0,\infty], where A\mathcal{A} is a set of actions. For a probability vector qq, let L(a,q)=∑kqkℓ(a,k)L(a,q) = \sum_k q_k \ell(a,k) be the expected loss of action aa when the label has distribution qq. The Bayes act at xx, written a∗(x)a^*(x), is the action that minimizes L(a,η(x))L(a,\eta(x)). Two cases will be used repeatedly.

  • Under 0-1 loss, A=[K]\mathcal{A} = [K] and the Bayes act is the Bayes classifier, a∗=b∗a^* = b^*.

  • Under log-loss, the action is a probability vector qq, ℓ(q,k)=−log⁡qk\ell(q,k) = -\log q_k, and the Bayes act is the vector of true class probabilities, a∗=ηa^* = \eta.

We assume, as is standard, that minimizers exist and that the Bayes act is unique for almost every xx (for 0-1 loss: there are no ties). Appendix § 12 states these regularity conditions precisely.

Terminology. Because this paper connects several literatures, and introduces some terms of its own, Table 2 lists the main terms, says which are standard, which adapt an existing notion, and which are introduced here, and points to where each is defined.

The ideal model: sufficiency, minimal and excess complexity

Before studying what learners do, it is useful to describe what an ideal model would look like in information-theoretic terms. In this section we ask: what is the least information about the input that a model’s output must carry to be optimal, and how much more than that does a given model carry? This gives us three reference points, the minimal sufficient, maximal and excess complexity, which we will use in § 4 and § 5 to describe what benign interpolators converge to. Everything in this section is a property of the data distribution and of a fixed model; learning from samples enters only in § 4.

Representations and sufficiency

A representation of the input is a random variable TT computed from XX, possibly with extra randomness that does not depend on YY. Formally, Y−X−TY - X - T is a Markov chain. The output F=f(X)F = f(X) of a fixed model is a representation, but so is an intermediate layer, a clustering of the inputs, or the input itself. To judge how useful a representation is for a loss ℓ\ell, we allow ourselves to post-process it in the best possible way. The recalibrated risk of TT is

Rℓ(T)=inf⁡gEℓ(g(T),Y),R_{\ell}(T) = \inf_{g} \mathbb{E} \ell(g(T),Y),

where the infimum is over all functions gg from the values of TT to actions. In plain terms, Rℓ(T)R_{\ell}(T) is the risk of the best decision rule that only gets to see TT. Recalibration makes the theory invariant to relabelling the values of TT, as mutual information is. For example, a classifier that always outputs the wrong one of two classes is, after recalibration, a perfect classifier. Under log-loss the recalibrated risk is simply the conditional entropy, Rlog⁡(T)=H(Y∣T)R_{\log}(T) = H(Y \mid T).

References

  1. [1]Alessandro Achille and Stefano Soatto. Emergence of invariance and disentanglement in deep representations. JMLR, 2018.arxiv.org/abs/1706.01350
  2. [2]Ben Adlam and Jeffrey Pennington. Understanding double descent requires a fine-grained bias-variance decomposition. In NeurIPS, 2020.arxiv.org/abs/2011.03321
  3. [3]Rana Ali Amjad and Bernhard C. Geiger. Learning representations for neural network-based classification using the information bottleneck principle. IEEE TPAMI, 2019.
  4. [4]Sylvain Arlot and Alain Celisse. A survey of cross-validation procedures for model selection. Statistics Surveys, 4:40–79, 2010.
  5. [5]Jean-Yves Audibert and Alexandre B. Tsybakov. Fast learning rates for plug-in classifiers. The Annals of Statistics, 35(2):608–633, 2007.DOI
  6. [6]Christina Baek, Yiding Jiang, Aditi Raghunathan, and J. Zico Kolter. Agreement-on-the-line: Predicting the performance of neural networks under distribution shift. In NeurIPS, 2022.arxiv.org/abs/2206.13089
  7. [7]Peter L. Bartlett, Philip M. Long, Gábor Lugosi, and Alexander T sigler. Benign overfitting in linear regression. PNAS, 117(48):30063–30070, 2020.DOI
  8. [8]Raef Bassily, Shay Moran, Ido Nachum, Jonathan Shafer, and Amir Yehudayoff. Learners that use little information. In ALT, 2018.arxiv.org/abs/1710.05233
  9. [9]Mikhail Belkin, Daniel Hsu, Siyuan Ma, and Soumik Mandal. Reconciling modern machine-learning practice and the classical bias–variance trade-off. PNAS, 2019a.DOI
  10. [10]Mikhail Belkin, Alexander Rakhlin, and Alexandre B. Tsybakov. Does data interpolation contradict statistical optimality? In AISTATS, 2019b.arxiv.org/abs/1806.09471
  11. [11]Shai Ben-David, Ulrike von Luxburg, and Dávid Pál. A sober look at clustering stability. In Conference on Learning Theory (COLT), pages 5–19, 2006.
  12. [12]Asa Ben-Hur, André Elisseeff, and Isabelle Guyon. A stability based method for discovering structure in clustered data. In Pacific Symposium on Biocomputing, pages 6–17, 2002.
  13. [13]David Blackwell. Equivalent comparisons of experiments. Annals of Mathematical Statistics, 24:265–272, 1953.DOI
  14. [14]Olivier Bousquet and André Elisseeff. Stability and generalization. JMLR, 2002.
  15. [15]Leo Breiman. Bagging predictors. Machine Learning, 1996.
  16. [16]Gavin Brown, Mark Bun, Vitaly Feldman, Adam Smith, and Kunal Talwar. When is memorization of irrelevant training data necessary for high-accuracy learning? In STOC, 2021.DOI
  17. [17]Thomas M. Cover and Peter E. Hart. Nearest neighbor pattern classification. IEEE Transactions on Information Theory, 1967.DOI
  18. [18]Thomas M. Cover and Joy A. Thomas. Elements of Information Theory. Wiley, 2nd edition, 2006.
  19. [19]James P. Crutchfield and Karl Young. Inferring statistical complexity. Physical Review Letters, 63 (2):105–108, 1989.pubmed.ncbi.nlm.nih.gov/10040781
  20. [20]Stefan Depeweg, José Miguel Hernández-Lobato, Finale Doshi-Velez, and Steffen U dluft. Decomposition of uncertainty in Bayesian deep learning for efficient and risk-sensitive learning. In ICML, 2018.arxiv.org/abs/1710.07283
  21. [21]Luc Devroye, László Györfi, and Gábor Lugosi. A Probabilistic Theory of Pattern Recognition. Springer, 1996.DOI
  22. [22]Roland L. Dobrushin and Boris S. Tsybakov. Information transmission with additional noise. IEEE Transactions on Information Theory, 8(5):293–304, 1962.DOI
  23. [23]Pedro Domingos. A unified bias-variance decomposition for zero-one and squared loss. In AAAI, 2000.
  24. [24]Meir Feder and Neri Merhav. Relations between entropy and error probability. IEEE Trans. Inf. Theory, 1994.
  25. [26]Vitaly Feldman and Chiyuan Zhang. What neural networks memorize and why: Discovering the long tail via influence estimation. In Advances in Neural Information Processing Systems, 2020.arxiv.org/abs/2008.03703
  26. [27]Peter Gács and János Körner. Common information is far less than mutual information. Problems of Control and Information Theory, 1973.
  27. [28]Ziv Goldfeld et al. Estimating information flow in deep neural networks. In ICML, 2019.arxiv.org/abs/1810.05728
  28. [29]Dongning Guo, Shlomo Shamai, and Sergio Verdú. Mutual information and minimum mean-square error in Gaussian channels. IEEE Transactions on Information Theory, 51(4):1261–1282, 2005.arxiv.org/abs/cs/0412108
  29. [30]Mahdi Haghifam, Borja Rodríguez-Gálvez, Ragnar Thobaben, Mikael Skoglund, Daniel M. Roy, and Gintare Karolina Dziugaite. Limitations of information-theoretic generalization bounds for gradient descent methods in stochastic convex optimization. In ALT, 2023.arxiv.org/abs/2212.13556
  30. [31]Hrayr Harutyunyan, Kyle Reing, Greg Ver Steeg, and Aram Galstyan. Improving generalization by controlling label-noise information in neural network weights. In ICML, 2020.arxiv.org/abs/2002.07933
  31. [32]Hrayr Harutyunyan, Maxim Raginsky, Greg Ver Steeg, and Aram Galstyan. Information-theoretic generalization bounds for black-box learning algorithms. In NeurIPS, 2021.arxiv.org/abs/2110.01584
  32. [33]Trevor Hastie, Andrea Montanari, Saharon Rosset, and Ryan J. Tibshirani. Surprises in high-dimensional ridgeless least squares interpolation. The Annals of Statistics, 50(2):949–986, 2022.DOI
  33. [34]Fredrik Hellström and Giuseppe Durisi. A new family of generalization bounds using samplewise evaluated CMI. In Advances in Neural Information Processing Systems, 2022.arxiv.org/abs/2210.06422
  34. [35]Tom Heskes. Bias/variance decompositions for likelihood-based estimators. Neural Computation, 10 (6):1425–1433, 1998.pubmed.ncbi.nlm.nih.gov/9698350
  35. [36]Andrew Ilyas, Sung Min Park, Logan Engstrom, Guillaume Leclerc, and Aleksander Madry. Data-models: Predicting predictions from training data. In International Conference on Machine Learning (ICML), 2022.
  36. [37]Gareth James, Daniela Witten, Trevor Hastie, Robert Tibshirani, and Jonathan Taylor. An Introduction to Statistical Learning: with Applications in Python. Springer, 2023.
  37. [38]Gareth M. James. Variance and bias for general loss functions. Machine Learning, 51(2):115–135, 2003.DOI
  38. [39]Yiding Jiang, Vaishnavh Nagarajan, Christina Baek, and J. Zico Kolter. Assessing generalization of SGD via disagreement. In ICLR, 2022.arxiv.org/abs/2106.13799
  39. [40]Kenji Kawaguchi, Zhun Deng, Xu Ji, and Jiaoyang Huang. How does information bottleneck help deep learning? In ICML, 2023.arxiv.org/abs/2305.18887
  40. [41]Pang Wei Koh and Percy Liang. Understanding black-box predictions via influence functions. In International Conference on Machine Learning (ICML), 2017.arxiv.org/abs/1703.04730
  41. [42]Ron Kohavi and David H. Wolpert. Bias plus variance decomposition for zero-one loss functions. In ICML, 1996.
  42. [43]Artemy Kolchinsky, Brendan D. Tracey, and Steven Van Kuyk. Caveats for information bottleneck in deterministic scenarios. In ICLR, 2019.arxiv.org/abs/1808.07593
  43. [44]Tilman Lange, Volker Roth, Mikio L. Braun, and Joachim M. Buhmann. Stability-based validation of clustering solutions. Neural Computation, 16(6):1299–1323, 2004.pubmed.ncbi.nlm.nih.gov/15130251
  44. [45]Lucien Le Cam. Sufficiency and approximate sufficiency. Annals of Mathematical Statistics, 35:1419–1455, 1964.DOI
  45. [46]Roi Livni. Information theoretic lower bounds for information theoretic upper bounds. In NeurIPS, 2023.arxiv.org/abs/2302.04925
  46. [47]Philip M. Long and Rocco A. Servedio. Random classification noise defeats all convex potential boosters. Machine Learning, 2010.
  47. [48]Neil Mallinar, James B. Simon, Amirhesam Abedsoltan, Parthe Pandit, Mikhail Belkin, and Preetum Nakkiran. Benign, tempered, or catastrophic: A taxonomy of overfitting. In NeurIPS, 2022.arxiv.org/abs/2207.06569
  48. [49]Song Mei and Andrea Montanari. The generalization error of random features regression: Precise asymptotics and the double descent curve. Communications on Pure and Applied Mathematics, 75(4):667–766, 2022.
  49. [50]George A. Miller. Note on the bias of information estimates. In Henry Quastler, editor, Information Theory in Psychology: Problems and Methods, pages 95–100. Free Press, 1955.
  50. [51]Vidya Muthukumar, Kailas Vodrahalli, Vignesh Subramanian, and Anant Sahai. Harmless interpolation of noisy data in regression. IEEE JSAIT, 2020.arxiv.org/abs/1903.09139
  51. [52]Preetum Nakkiran and Yamini Bansal. Distributional generalization: A new kind of generalization. arXiv preprint arXiv:2009.08092, 2020.arxiv.org/abs/2009.08092
  52. [53]Nagarajan Natarajan, Inderjit S. Dhillon, Pradeep K. Ravikumar, and Ambuj Tewari. Learning with noisy labels. In NeurIPS, 2013.
  53. [54]Nikolaos Nikolaou. Lossless compression & generalization in overparameterized models: The case of boosting. In ICLR (short paper), 2021.
  54. [55]Nikolaos Nikolaou, Henry Reeve, and Gavin Brown. Margin maximization as lossless maximal compression. arXiv preprint arXiv:2001.10318, 2020.arxiv.org/abs/2001.10318
  55. [56]Randal S. Olson, William La Cava, Patryk Orzechowski, Ryan J. Urbanowicz, and Jason H. Moore. PMLB: a large benchmark suite for machine learning evaluation and comparison. BioData Mining, 10:36, 2017.arxiv.org/abs/1703.00512
  56. [57]Giorgio Patrini, Alessandro Rozza, Aditya Krishna Menon, Richard Nock, and Lihzen Qu. Making deep neural networks robust to label noise: A loss correction approach. In CVPR, 2017.arxiv.org/abs/1609.03683
  57. [58]Fabian Pedregosa et al. Scikit-learn: Machine learning in Python. Journal of Machine Learning Research, 12:2825–2830, 2011.arxiv.org/abs/1201.0490
  58. [59]Emmanouil Antonios Platanios, Avinava Dubey, and Tom M. Mitchell. Estimating accuracy from unlabeled data: A Bayesian approach. In ICML, 2016.
  59. [60]Daniel Russo and James Zou. How much does your data exploration overfit? controlling bias via information usage. IEEE Transactions on Information Theory, 66(1):302–323, 2020. Conference version: AISTATS 2016.arxiv.org/abs/1511.05219
  60. [61]Andrew M. Saxe et al. On the information bottleneck theory of deep learning. In ICLR, 2018.DOI
  61. [62]Robert E. Schapire, Yoav Freund, Peter Bartlett, and Wee Sun Lee. Boosting the margin: A new explanation for the effectiveness of voting methods. Annals of Statistics, 1998.
  62. [63]Ohad Shamir, Sivan Sabato, and Naftali Tishby. Learning and generalization with the information bottleneck. Theoretical Computer Science, 2010.
  63. [64]Ravid Shwartz-Ziv and Naftali Tishby. Opening the black box of deep neural networks via information. arXiv preprint arXiv:1703.00810, 2017.
  64. [65]Thomas Steinke and Lydia Zakynthinou. Reasoning about generalization via conditional mutual information. In COLT, 2020.arxiv.org/abs/2001.09122
  65. [66]DJ Strouse and David J. Schwab. The deterministic information bottleneck. Neural Computation, 2017.DOI
  66. [67]Robert Tibshirani and Guenther Walther. Cluster validation by prediction strength. Journal of Computational and Graphical Statistics, 14(3):511–528, 2005.DOI
  67. [68]Naftali Tishby and Noga Zaslavsky. Deep learning and the information bottleneck principle. In IEEE Information Theory Workshop, 2015.arxiv.org/abs/1503.02406
  68. [69]Naftali Tishby, Fernando C. Pereira, and William Bialek. The information bottleneck method. arXiv preprint physics/0004057, 2000.
  69. [70]Ulrike von Luxburg. Clustering stability: an overview. Foundations and Trends in Machine Learning, 2(3):235–274, 2010.DOI
  70. [71]Hans S. Witsenhausen. Indirect rate distortion problems. IEEE Transactions on Information Theory, 26(5):518–521, 1980.DOI
  71. [72]Abraham J. Wyner, Matthew Olson, Justin Bleich, and David Mease. Explaining the success of adaboost and random forests as interpolating classifiers. JMLR, 2017.
  72. [73]Aolin Xu and Maxim Raginsky. Information-theoretic analysis of generalization capability of learning algorithms. In NeurIPS, 2017.arxiv.org/abs/1705.07809
  73. [74]Zitong Yang, Yaodong Yu, Chong You, Jacob Steinhardt, and Yi Ma. Rethinking bias-variance trade-off for generalization of neural networks. In ICML, 2020.arxiv.org/abs/2002.11328
  74. [75]Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht, and Oriol Vinyals. Understanding deep learning requires rethinking generalization. In ICLR, 2017.arxiv.org/abs/1611.03530

Paper details

vlnc:W_eqcndksm
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 4

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

Claude Opus 5.5 (bare)

View statement
Looking for related papers…
Contents