PaperlayerView exact revision on arXiv

Source-linked AI summary

Revisiting minimum description length complexity in overparameterized models

Raaz Dwivedi, Chandan Singh, Bin Yu, Martin J. Wainwright

arXiv:2006.10189v4cs.LGcs.ITmath.STstat.ML

TL;DR

Parameter count is not theoretically justified as a complexity measure for overparameterized models. The paper introduces MDL-COMP through ridge-induced encodings and finds that complexity can grow only logarithmically with dimension beyond the interpolation threshold while supporting practical tuning.

  • Problem

    Parameter count lacks theoretical justification as a complexity measure for overparameterized models and for ill-conditioned low-dimensional designs.

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

  • Method

    The paper defines MDL-COMP as the minimum excess code length induced by ridge-estimator model families and analyzes it for linear and kernel methods.

    Source: §1 · p. 3

  • Results

    MDL-COMP often grows logarithmically with d when d > n, upper-bounds in-sample MSE, informs minimax generalization, and supports computationally cheaper tuning than cross-validation.

    Source: §1 · p. 3, §6 · pp. 25–26

  • Takeaways & Limitations

    MDL-COMP offers a complexity measure for overparameterized settings, while its practical tuning scheme is a competitive alternative to cross-validation in limited-data regimes.

    Source: §6 · pp. 25–26

    Kernel-method results remain in the classical low-dimensional regime, leaving high-dimensional kernel behavior as an open direction.

    Source: §6.2 · p. 28

Abstract

from arXiv · show

Complexity is a fundamental concept underlying statistical learning theory that aims to inform generalization performance. Parameter count, while successful in low-dimensional settings, is not well-justified for overparameterized settings when the number of parameters is more than the number of training samples. We revisit complexity measures based on Rissanen's principle of minimum description length (MDL) and define a novel MDL-based complexity (MDL-COMP) that remains valid for overparameterized models. MDL-COMP is defined via an optimality criterion over the encodings induced by a good Ridge estimator class. We provide an extensive theoretical characterization of MDL-COMP for linear models and kernel methods and show that it is not just a function of parameter count, but rather a function of the singular values of the design or the kernel matrix and the signal-to-noise ratio. For a linear model with $n$ observations, $d$ parameters, and i.i.d. Gaussian predictors, MDL-COMP scales linearly with $d$ when $d<n$, but the scaling is exponentially smaller -- $\log d$ for $d>n$. For kernel methods, we show that MDL-COMP informs minimax in-sample error, and can decrease as the dimensionality of the input increases. We also prove that MDL-COMP upper bounds the in-sample mean squared error (MSE). Via an array of simulations and real-data experiments, we show that a data-driven Prac-MDL-COMP informs hyper-parameter tuning for optimizing test MSE with ridge regression in limited data settings, sometimes improving upon cross-validation and (always) saving computational costs. Finally, our findings also suggest that the recently observed double decent phenomenons in overparameterized models might be a consequence of the choice of non-ideal estimators.

1 Introduction

The paper introduces MDL-COMP, a minimum-description-length complexity measure designed for overparameterized linear and kernel models, and studies its theoretical behavior and practical use for regularization tuning. It shows that complexity depends on design or kernel structure and can remain informative when parameter counting and related measures fail.

Motivation and contribution

  • MDL-COMP is defined as the minimum excess bits required to transmit data using an optimal code from a family based on ridge estimators.The measure is motivated by algorithmic complexity and Rissanen’s minimum description length principle, whose existing linear-model measures can scale linearly with dimension or be infinite.Source: §1 · p. 3

Theoretical findings

  • For linear models, MDL-COMP depends on the design matrix and scales like d/n when d < n but only logarithmically in d when d > n.Parameter count is justified mainly for well-conditioned low-dimensional designs, whereas overparameterized and ill-conditioned settings make it an unreliable complexity measure.Source: §1 · pp. 2–3
  • MDL-COMP upper-bounds in-sample MSE and satisfies a minimax optimality criterion, while for Gaussian and Sobolev kernels it informs minimax in-sample generalization.For neural tangent kernels, MDL-COMP can decrease as input dimensionality increases.Source: §1 · p. 3

Practical evaluation

  • A data-driven MDL-COMP criterion achieves test-MSE performance competitive with cross-validation in simulations and real-data experiments, especially with limited data, while requiring computation for only a single fold.The criterion is particularly useful for tuning ridge-regression regularization and can save computation when training overparameterized models.Source: §1 · p. 3

Implications

  • The findings also provide insights into the recently observed double-descent phenomenon in overparameterized models.The introduction connects these insights to the possibility that double descent depends on the choice of estimator.Source: §1 · p. 3

2 Background on the principle of minimum description length

The paper frames complexity through MDL’s shortest-data-description principle, then develops optimal redundancy over LNML codes to address failures of standard MDL measures in overparameterized settings.

2.1 Basic principle

  • MDL treats probability models as prefix codes and selects the code with the shortest description of observed data, generalizing maximum likelihood beyond ordinary parametric families.The framework exploits redundancy for compression and remains defined over arbitrary code sets, even without a generative modeling assumption.Source: §2.1 · p. 4

2.2 Two-stage MDL

  • Two-stage MDL is equivalent to BIC, using a d/2 log n regularization term, so its complexity is essentially parameter counting.This formulation is designed for model selection across nested parametric classes with varying parameter dimensionality.Source: §2.2 · p. 5

2.3 Normalized maximum likelihood

  • NML provides a minimax-optimal universal code, and for fixed-dimensional regular parametric classes its complexity is asymptotically 1/2 d log n, matching BIC to first order.Its log normalization constant is called NML or Shtarkov complexity.Source: §2.3 · p. 5
  • In overparameterized Gaussian linear regression with d > n and full row-rank design, NML has infinite complexity, while truncation yields a trivial measure independent of X and d.Thus, the canonical fixes fail to provide a meaningful design- and dimensionality-sensitive complexity measure in this setting.Source: §2.3 · pp. 5–6

2.4 Luckiness normalized maximum likelihood

  • LNML resolves NML’s infinity problem through a user-chosen luckiness function, while this work instead optimizes over a family of LNML codes to define complexity principledly.LNML generalizes regularized maximum likelihood, and the investigated family uses positive semidefinite matrices to generate ridge estimators.Source: §2.4 · p. 6

2.5 Optimal redundancy as a complexity measure

  • Optimal redundancy measures complexity as the smallest expected excess code-length relative to the unknown true distribution, provided the candidate code set is sufficiently rich.The paper focuses its derivations on known generative models, while noting minimax redundancy as an alternative.Source: §2.5 · p. 7

3 Ridge-based minimum description length complexity

This section defines MDL-COMP through ridge-induced LNML codes, covering linear and kernel constructions as well as practical hyperparameter encoding. It also characterizes how the resulting upper bound depends on the luckiness function, hyperparameter class, encoding, and λ-dependent codelength choices.

3 Ridge-based minimum description length complexity

  • MDL-COMP uses ridge-induced LNML codes because ridge estimators are computationally feasible, predictively strong, and avoid OLS codes’ poor overparameterized performance and infinite complexity.Ridge estimators achieve minimax performance for linear and kernel methods, whereas OLS-based codes perform poorly in overparameterized or infinite-dimensional settings.Source: §3 · p. 7

3.1 Ridge-based LNML codes

  • The framework encodes response vectors conditional on known covariates, using ridge estimators for linear models and kernel ridge regression for RKHS functions.The linear and kernel constructions recap ridge estimators before defining their corresponding LNML codes.Source: §3.1.2 · p. 8, §3.1 · p. 8, §3.1.1 · p. 8

3.1.2 Defining ridge-based LNML codes

  • Each LNML code separates Gaussian data fit from a ridge-inspired luckiness factor, then encodes the regularization hyperparameters through quantization-based codelengths.Linear codes permit a matrix Λ aligned with X^⊤X, while kernel codes use a single regularization parameter λ.Source: §3.1.2 · pp. 9–10

3.2 Defining MDL-COMP via ridge-LNML codes

  • MDL-COMP is optimal redundancy over the ridge-code family plus the codelength for optimal hyperparameters, under linear-Gaussian or kernel-generative assumptions.The measure remains valid with arbitrary generative models, although the paper restricts analytical derivations to linear and RKHS-generative settings.Source: §3.2 · pp. 10–12

3.3.1 Relation of LNML code (15) with prior work

  • The LNML expression is consistent with prior MDL work, while this paper evaluates expected negative log-code length and minimizes redundancy to analyze linear and kernel models.Earlier studies did not provide corresponding analytical expressions for squared-loss linear or kernel models in overparameterized settings.Source: §3.3.1 · p. 12

3.3.2 The need for a true generative model

  • In practice, Prac-MDL-COMP directly minimizes the code length over Λ without requiring a true generative model, and tunes ridge regularization in experiments.A generative model is introduced for defining redundancy and obtaining analytical results, not as a requirement for applying the practical criterion to a dataset.Source: §3.3.2 · p. 12

3.3.3 Regularization set M: The tradeoff between expressivity and codelength

  • The regularization set M simultaneously diagonalizes Λ and X^⊤X, providing expressive codes while avoiding the excessive codelength of encoding arbitrary positive semidefinite matrices.Because X is shared, only the positive regularization eigenvalues require encoding, preserving flexibility without rapidly increasing hyperparameter codelength.Source: §3.3.3 · p. 13

3.3.4 Our LNML encoding vs one-part universal encoding

  • The post-optimization hyperparameter encoding is analytically convenient and practically motivated; Λopt minimizes in-sample MSE and achieves minimax codelength under bounded-variance noise.A one-part universal code would require a suitable luckiness function, whose denominator must remain finite.Source: §3.3.4 · pp. 13–14

3.3.5 Codelength for discretized Λ

  • For kernel regression, adding a term log(λopt)/n does not alter Theorem 3’s qualitative or Corollary 1’s quantitative conclusions.Only one regularization parameter is used in the kernel setting, motivating omission of an additional λ-dependent codelength.Source: §3.3.5 · p. 14
  • Changing the luckiness function, hyper-parameter class, or encoding codelength changes the resulting complexity measure.The paper notes that these design choices directly affect subsequent complexity calculations.Source: §3.3.5 · p. 14
  • MDL-COMP is an upper bound on true MDL complexity and can be loose, although it is tighter than parameter count for overparameterized linear models.The true complexity is the infimum over all possible choices of luckiness functions, hyper-parameter classes, and codelengths.Source: §3.3.5 · p. 14

4 Main results

The paper characterizes MDL-COMP for linear models and kernel methods, showing dependence on spectral structure and signal-to-noise rather than parameter count alone. It further relates MDL-COMP to fixed-design and minimax in-sample error, including regimes where complexity grows slowly or decreases with dimensionality.

4.1 Characterizing MDL-COMP for linear models

  • MDL-COMP for linear models depends on the eigenvalues of X⊤X and the rotated, noise-scaled true parameter rather than only d and n.The expression is oracle because it depends on the unknown θ⋆; a data-driven approximation is introduced later for practical computation.Source: §4.1 · p. 15

4.1.1 Scaling of MDL−COMP for various covariate designs

  • For Gaussian designs, MDL-COMP scales linearly with d when d < n but grows logarithmically when d > n, while spike designs can be non-linear even below n.The simulations vary fitted covariate dimension while holding generated data fixed, allowing under-specified and correctly or over-specified regimes to be compared.Source: §4.1.1 · p. 16, Figure 1 · p. 16, Figure 2 · p. 17

4.1.2 MDL−COMP informs fixed design mean-squared error

  • MDL-COMP bounds optimal fixed-design prediction error, while the optimal redundancy bounds optimal in-sample MSE and its achieving Λopt minimizes that MSE.A practical data-driven MDL-COMP variant can often minimize out-of-sample MSE and offers performance competitive with cross-validation-tuned ridge.Source: §4.1.2 · pp. 16–17

4.2 Characterizing MDL-COMP for kernel methods

  • For kernel methods, MDL-COMP has a generic upper bound depending on kernel-matrix eigenvalues and signal-to-noise ratio, expected to be tight for suitable f⋆.The bound applies broadly, including neural tangent kernels, although unlike the linear-model result it is not generally a closed-form expression.Source: §4.2 · p. 18
  • When n ≫ d, MDL-COMP matches minimax in-sample risk up to logarithmic factors for kernels with specified eigenvalue decay, and for ReLU NTKs it can decrease as d increases.For ReLU NTKs, the bound scales as SNR^2/(1+d) · ((d log n)/n)^(d/(d+1)), up to logarithmic factors, assuming dimensional changes do not alter SNR’s n-scaling.Source: §4.2 · pp. 18–19

5 Experiments with data-driven MDL-COMP

Prac-MDL-COMP provides a practical MDL-based criterion for tuning ridge regularization, closely tracking low-test-MSE models while requiring less computation than cross-validation. Across simulations and real datasets, it is competitive with or outperforms established baselines, including in limited-data settings.

5.1 MDL−COMP inspired hyper-parameter tuning

  • Prac-MDL-COMP is O(k) computationally more efficient than k-fold cross-validation while tuning ridge regularization through a data-driven MDL objective.The criterion addresses the infeasibility of computing MDL-COMP directly and uses a single regularization parameter; its kernel analogue is defined through kernel-matrix eigenvalues.Source: §5.1 · pp. 20–21

5.2 Prac-MDL-COMP informs test MSE in Gaussian simulations

  • In Gaussian simulations, minimizing the Prac-MDL-COMP objective selects models with test MSE close to the best ridge estimator chosen by LOOCV across d/n values from 1/10 to 10.The selected ridge models avoid the OLS double-descent peak and remain effective under additional forms of misspecification.Source: §5.2 · pp. 21–22, Figure 3 · p. 22

5.3 Experiments with PMLB datasets

  • On 19 PMLB datasets, Prac-MDL-COMP tends to outperform Ridge-CV when data are limited and performs comparably as the training-sample ratio increases.The experiments vary d/n by subsampling and evaluate test error on held-out data.Source: §5.3 · p. 23, Figure 4 · p. 23

5.4 Experiments with fMRI data

  • For fMRI ridge regression, Prac-MDL-COMP consistently outperforms Bayesian ARD and BIC across voxels while remaining roughly on par with cross-validation.Cross-validation wins for most voxels by a slight margin, whereas Prac-MDL-COMP wins on the remainder by a substantial margin.Source: §5.4 · p. 24, Figure 5 · p. 24
  • In fMRI data, increasing the Prac-MDL-COMP objective generally increases test MSE, and estimated bRopt has correlation 0.69 with test MSE.These results suggest that the data-driven redundancy estimate helps order models by test performance, beyond its theoretical in-sample-MSE guarantee.Source: §5.4 · p. 24, Figure 6 · p. 25

5.5 Experiments with neural tangent kernel on fMRI data

  • With neural tangent kernel ridge regression on fMRI data, Prac-MDL-COMP is roughly on par with LOOCV and remains a useful proxy for minimizing test error.The objective–test-error relationship is flatter than for linear ridge regression, but test error often decreases as the objective increases.Source: §5.5 · p. 25

6 Discussion

The discussion argues that MDL-COMP is a theoretically justified complexity measure for overparameterized linear and kernel models, with practical tuning benefits over cross-validation. It further attributes double descent primarily to poor estimator choice in ill-posed regimes and identifies several extensions for future work.

6 Discussion

  • MDL-COMP depends on dimension, sample size, design or kernel matrix, signal properties, and noise; for d > n, it often grows as log d rather than linearly.It informs fixed-design generalization error, provides good random-design empirical results, and enables computationally cheaper tuning that often outperforms cross-validation with limited observations.Source: §6 · pp. 25–26

6.1 Consequences for bias-variance tradeoff in overparameterized models

  • Tuned ridge estimators produce U-shaped test-error curves, whereas OLS can exhibit double or multiple descent across low- and high-dimensional, including ill-conditioned, regimes.Replacing parameter count with MDL-COMP does not remove double descent because it remains monotone in d; the findings instead implicate poor estimators in ill-posed settings.Source: §6.1 · pp. 27–28
  • The paper hypothesizes that double descent is likely caused by poor estimator choice rather than complexity measurement, since tuned regularization restores classical U-shaped error curves.OLS can show double or multiple descent depending on the covariate matrix, while tuned ridge estimators achieve minimum test error at the data-generating dimensionality and outperform OLS in studied designs.Source: §6.1 · pp. 27–28

6.2 Future directions

  • Future work includes out-of-sample guarantees, high-dimensional kernel analysis, sparse-model MDL-COMP, and extensions beyond linear and kernel methods to deep neural networks and classification.The current kernel results are classical low-dimensional results, and ridge-based measures may be unsuitable for sparse high-dimensional parameter estimation.Source: §6.2 · p. 28

1 Introduction · Appendix A. Further discussion of MDL−COMP · A.1 Simulation set-up

The appendix expands the MDL-COMP simulation setup and outlines supporting analyses of its scaling, optimality, and robustness. The simulations vary fitted dimensionality by selecting columns from a full covariate matrix while computing MDL-COMP from the corresponding ridge design.

Appendix A. Further discussion of MDL−COMP

  • The appendix previews analyses of MDL-COMP scaling, its behavior in Fig. 1, high-dimensional bounds for Ropt, broader-noise minimax optimality, and additional MDL background.These topics are developed across Appendices A.1–A.6.Source: Appendix A · p. 30

A.1 Simulation set-up

  • The simulations define d⋆ as the number of covariates generating observations, while Xfull contains the maximum available d covariates.The data satisfy y = eXθ⋆ + ξ, with dependence only on the first d⋆ covariates.Source: §A.1 · p. 30
  • For each fixed sample size n, varying d selects the first d columns of Xfull to form X, which is used to fit ridge regression and compute MDL-COMP.The plotted maximum d is determined by the largest displayed d/n ratio.Source: §A.1 · p. 30
  • MDL-COMP computation requires the eigenvalues ρ_i of X⊤X for the selected fitting matrix X.The same matrix determines the corresponding encoding and MDL-COMP.Source: §A.1 · p. 30
  • The simulation computes w as U⊤θ⋆, where U is d × d and θ⋆ has the true-model dimensionality d⋆.This construction connects the true signal to the eigenbasis used in the MDL-COMP calculation.Source: §A.1 · p. 30
  • When d < d⋆, θ⋆ is restricted to its first d dimensions before computing w = U⊤eθ⋆.The restricted vector eθ⋆ is described as the orthogonal projection of θ⋆ on X⊤X.Source: §A.1 · p. 31
  • When d > d⋆, the setup extends θ⋆ by appending d − d⋆ components before forming the corresponding w.This handles fitted models with more covariates than the true dimensionality.Source: §A.1 · p. 31

A.2 Proof sketch for random isotropic designs … A.6 Relation between NML and maximum likelihood principle

The appendices establish MDL-COMP’s logarithmic overparameterized scaling, bounded optimal redundancy under fixed signal norm, minimax robustness beyond Gaussian noise, and unchanged scaling under a modified code factor. They also clarify that NML generalizes beyond fixed-model maximum likelihood, while reducing to it for a single parametric family.

A.2 Proof sketch for random isotropic designs

  • For random isotropic designs, MDL-COMP scales as O(d/n) for small d but as O(log d) when d ≫ n, so d/n is not the default complexity in overparameterized regimes.The proof uses approximate isotropy for d ≪ n and rank-n covariance structure with nonzero eigenvalues near d/n for d ≫ n.Source: §A.2 · pp. 31–32

A.3 Expressions for Ropt for large scale settings

  • In large-scale settings, the optimal redundancy Ropt has a bound whose first term scales as d/n when ||θ⋆|| grows with d, but remains bounded when ||θ⋆|| is fixed.The bound has scaling comparable to the random-isotropic-design proof under the corresponding dimensional regimes.Source: §A.3 · p. 32

A.4 MDL−COMP over a wider range of noise distributions

  • Theorem 5 shows that the distribution QΛopt achieving MDL-COMP also achieves the minimax codelength over the bounded-variance noise class Pbndvar.This extends the minimax codelength guarantee beyond the Gaussian-noise setting while retaining the conditional mean Xθ⋆ and variance bound σ^2I_n.Source: §A.4 · p. 33

A.5 MDL-COMP with multiplicative factor 1 in equation (17)

  • Changing the multiplicative factor for the codelength of Λ from 1/2 to 1 changes the expressions but leaves MDL-COMP scaling unaffected.The new expressions are bounded by at most 2 times the previous expressions.Source: §A.5 · pp. 33–34

A.6 Relation between NML and maximum likelihood principle

  • Unlike maximum likelihood, MDL can optimize over codes for multiple model classes and need not interpret Q(y) as a likelihood or generative model.This flexibility is intended to select a code optimal across parametric model classes of different dimensions, including settings without a true generative model.Source: §A.6 · p. 34
  • When Q is a single parametric family, MDL reduces to maximum likelihood, with the optimal NML code combining the MLE log likelihood and a normalization term.The MLE is described as the continuum limit of two-part MDL in this setting.Source: §A.6 · p. 34
  • For fixed-dimensional linear models, two-part, stochastic-information, and NML complexities share the leading O(log n) term, while NML is asymptotically optimal for the O(1) term.The leading term scales like 1/2 d log n, and the constant term involves Jeffrey’s prior.Source: §A.6 · p. 34

Appendix B. Further numerical experiments · B.1 Misspecified linear models

Further experiments evaluate Prac-MDL-COMP in Gaussian and misspecified linear models, showing that it can guide model selection for good out-of-sample prediction. The appendix also reports robustness across real-data and cross-validation settings.

Appendix B. Further numerical experiments

  • Additional experiments assess the usefulness of data-driven Prac-MDL-COMP for informing out-of-sample MSE in Gaussian and misspecified linear models.The appendix introduces these experiments before presenting further real-data analyses in Appendix B.2.Source: Appendix B · p. 34

B.1 Misspecified linear models

  • The misspecification study defines three model-misspecification types from prior work and tests whether MDL-COMP selects models that generalize.The cited prior work is Yu and Kumbier, 2020.Source: §B.1 · p. 34
  • Prac-MDL-COMP successfully selects models that predict fMRI responses well compared with BIC, while comparisons with cross-validation and Ridge-ARD appear in Fig. 5.Figure B1 reports the fMRI comparison; the broader comparisons are referenced through Fig. 5.Source: Figure B1 · p. 35

Appendix B. Further numerical experiments

  • The results shown in Fig. 4 also hold when five-fold cross-validation replaces leave-one-out cross-validation.Figure B2 reports this cross-validation robustness check.Source: Figure B2 · p. 35

B.1 Misspecified linear models

  • Under misspecified conditions, MDL-COMP still selects a λ that generalizes fairly well, including heavy-tailed errors, structured covariance, and thresholded outcomes.The experiments cover t-distributed errors with three degrees of freedom, covariance eigenvalues decaying as 1/2^i, and indicator-function outcomes for X > 0.Source: §B.1 · pp. 34–35
  • The misspecified-model comparison uses leave-one-out cross-validation for Ridge-CV and Prac-MDL-COMP optimization for ridge-model selection.Ridge-CV is shown as an orange dotted line, while Prac-MDL-COMP is shown as a blue line.Source: §B.1 · p. 35

B.2 Real data experiments continued · Appendix C. Proofs

Further real-data experiments show that Prac-MDL-COMP-based regularization is promising in limited-data settings, while Appendix C collects proofs for all principal theoretical results. Across 28 OpenML datasets, MDL-COMP generally outperforms Ridge-CV when d/n is large, but this advantage narrows as sample size increases.

B.2 Real data experiments continued

  • Prac-MDL-COMP based linear models also perform well against 5-fold cross-validation, as shown in Fig. B2.Source: §B.2 · p. 35
  • Across 28 real datasets, MDL-COMP tends to outperform Ridge-CV in the limited-data regime, while cross-validation begins to outperform MDL-COMP as training samples increase.The datasets are identified by OpenML IDs, and the comparison is shown in Fig. B4.Source: §B.2 · pp. 35–36
  • Under various misspecifications, Prac-MDL-COMP still selects models that generalize reasonably well.In this experiment, d is fixed and the sample size n is varied.Source: Figure B3 · p. 36
  • These experiments provide evidence for Prac-MDL-COMP-based regularization in limited-data settings.Source: §B.2 · pp. 35–36

Appendix C. Proofs

  • Appendix C collects the proofs of all results presented in the paper.Source: Appendix C · p. 36
  • Proofs for Theorems 1 through 5 appear in Appendices C.1 through C.5, respectively.Source: Appendix C · p. 36
  • The proof of Corollary 1 is provided in Appendix C.6.Source: Appendix C · p. 36

C.1 Proof of Theorem 1 … C.1.3 Proof of claim (50b) (term T3):

The proof of Theorem 1 decomposes the MDL-COMP derivation into separable optimization and singular-value-based linear-algebra steps. For d<n, it derives the terms in claims (50a) and (50b), including the T2 and T3 contributions.

C.1 Proof of Theorem 1

  • Theorem 1’s proof reduces Ropt to minimizing a KL-divergence objective that separates across the components of λ.Each λ_i is therefore obtained by solving an independent univariate optimization problem.Source: §C.1 · p. 39
  • Boundary analysis and the inequality 1 + log a ≤ a establish that each scalar objective attains its minimum at λopt_i.Substitution of this optimizer yields the stated expression used in the theorem.Source: §C.1 · p. 39

C.1.1 Proof of claims (50a) and (50b) for the case d < n

  • For d<n, the proof uses the singular value decomposition of X and represents Λ in the corresponding singular-vector basis.The diagonal entries of D are the squared singular values, while VV⊤ is a rank-d projection.Source: §C.1.1 · pp. 39–40
  • The d<n derivation expresses the relevant quantities through D, Λ, and the orthogonal projection VV⊤, with the remaining proof relying on elementary linear algebra.The construction uses orthogonality and diagonal-matrix commutation in the singular basis.Source: §C.1.1 · p. 40

C.1.2 Proof of the expression (50a) for term T2

  • The T2 algebra uses the identities for claims (55a) and (55b), diagonal-matrix commutation, claim (55c), and a matrix-trace identity.These steps produce the displayed expression for term T2.Source: §C.1.2 · pp. 40–41
  • Term T2 is obtained by expanding the quadratic expression in the singular basis and separating the projection onto the orthogonal complement of X.The complement projection has rank n−d and satisfies (In−VV⊤)X=0.Source: §C.1.2 · p. 41

C.1.3 Proof of claim (50b) (term T3):

  • For T3, Gaussian-density normalization and the definition of CΛ yield eigenvalues λ_i/(λ_i+ρ_i) for i≤d and eigenvalue 1 with multiplicity n−d.Applying equation (59) then establishes claim (50b).Source: §C.1.3 · p. 41

C.1.4 Proof of claims (50a) and (50b) for the case d > n · C.1.5 Proof of claims (55a) and (63a) · C.2 Proof of Theorem 2

The appendix adapts the singular-value and linear-algebra arguments to the overparameterized case d > n, then uses them to establish Theorem 2’s optimal-regularization claims and prediction-error bound.

C.1.4 Proof of claims (50a) and (50b) for the case d > n

  • For d > n, the proofs of claims (50a) and (50b) retain the original argument with dimension-adjusted singular-value decompositions and n × n principal matrices.The nonzero entries of D are represented by eD, while Λ_n denotes the n × n principal minor of Λ.Source: §C.1.4 · pp. 41–42
  • The modified quadratic expression and eigenvalue calculation yield the claimed expression (50a) and complete the corresponding (50b) argument for d > n.The derivation applies equations (63a) and (63b), then uses VV^⊤ = I_n to characterize the eigenvalues of A_Λ.Source: §C.1.4 · p. 42

C.1.5 Proof of claims (55a) and (63a)

  • The linear-algebra proofs cover both n > d and n < d, assuming Λ is positive definite so its inverse exists and exploiting commutativity of diagonal matrices.The same notation is arranged to handle both dimensional regimes, with the remaining claims derived similarly.Source: §C.1.5 · p. 42
  • Claim (55a) is proved for n > d by substituting decomposition (54) and using orthogonality together with projection identities for I − VV^⊤.The proof relies on U^⊤U = I_d, (I − VV^⊤)V = 0, and V^⊤V = I_d.Source: §C.1.5 · p. 43
  • Claim (63a) is established for d > n using the decomposition (62), orthogonality relations for U and V, and the principal matrix Λ_n.The resulting expression directly yields the claim.Source: §C.1.5 · p. 43

C.2 Proof of Theorem 2

  • Theorem 2’s first claim follows by optimizing each separable in-sample MSE term over λ_i and examining the objective at λ_i = 0 and as λ_i tends to infinity.The proof invokes the optimal MDL-COMP regularization choice λ_i,opt and establishes claim (65).Source: §C.2 · pp. 43–44
  • The fixed-design prediction-error bound is obtained by substituting the optimal regularization into the redundancy expression and applying x ≤ −log(1 − x) for x ∈ [0, 1).The proof treats d > n and d < n together using claims (55) and (63), then concludes the bound.Source: §C.2 · p. 44

C.3 Proof of Theorem 3

The proof decomposes the ridge-based expression into noise and signal terms, diagonalizes the kernel matrix, and applies operator bounds to establish Theorem 3. It also identifies spectral-decay and finite-rank conditions under which the resulting inequalities are tight.

C.3 Proof of Theorem 3

  • The ridge criterion simplifies to a signal term involving λ(K + λI)^−1 and an additive noise contribution.This follows by substituting the ridge estimator into the residual-plus-penalty expression and taking expectation under the Gaussian observation model.Source: §C.3 · p. 45
  • Diagonalizing K with eigenvalues ρ_i and coordinates α = U^⊤y⋆ reduces the bound to componentwise spectral terms.The proof then represents the kernel and target function through feature-space operators to control the remaining expression.Source: §C.3 · pp. 45–46
  • The theorem follows by combining the operator representation with max{ρ_i, λ}/(λ + ρ_i) ≤ 1 and the preceding bound.The final step explicitly cites these two inequalities before concluding the proof.Source: §C.3 · p. 46
  • The inequalities become relatively tight when kernel eigenvalues decay rapidly, the relevant index i⋆ is below n, and the coefficient sequence decays suitably.These conditions are stated after optimizing the bound over λ, with λ_opt approximately matching ρ_i⋆.Source: §C.3 · p. 46
  • The second inequality is tight when the infinite kernel expansion is well approximated by its first n terms, including rapidly decaying eigenvalues or finite rank below n.Under this approximation, the feature-space operators reduce to n × n unitary matrices; the decay conditions in Corollary 1 suffice.Source: §C.3 · p. 46

C.4 Proof of Theorem 4 … C.6.2 Proof with exponential decay of eigenvalues

The proofs derive MDL-COMP through spectral representations and random-matrix limits, then establish bounds under polynomial and exponential eigenvalue decay. They also show that Theorem 5’s objective has the same minimizer as the preceding formulation.

C.4 Proof of Theorem 4

  • Under rotationally invariant θ⋆, MDL-COMP is rewritten using the empirical eigenvalue distribution of X⊤X and an integral involving log(1 + Z · snr).The proof applies Jensen’s inequality and rotational invariance before analyzing the eigenvalue distribution.Source: §C.4 · p. 47
  • As d,n →∞ with d/n →γ, the spectral integral converges almost surely to γ · E_Z∼MPγ[log(1 + snr · Z)], yielding Theorem 4’s expression.The limit uses the Marčenko–Pastur law and a closed-form Shannon transform.Source: §C.4 · pp. 47–48

C.5 Proof of Theorem 5

  • Theorem 5 follows by comparing positive-semidefinite trace terms, with equality when Var(y|X) = σ^2I_n, and its objective has the same minimizer as equation (51).The new objective differs from the earlier one only by an additive constant as a function of the eigenvalues.Source: §C.5 · p. 49

C.6 Proof of Corollary 1

  • Corollary 1 is proved separately for polynomial and exponential eigenvalue decay using the preceding algebra and spectral bounds.The polynomial case normalizes the eigenvalues under the trace constraint, while the exponential case uses a different reparameterization.Source: §C.6 · p. 49, §C.6.1 · p. 49, §C.6.2 · p. 50

C.6.1 Proof with polynomial decay of eigenvalues

  • For polynomial decay, trace normalization and MDL-COMP monotonicity reduce the analysis to ρ_i = n c_α i^-2α under finite-sum conditions.The assumptions ω > d/2 and d + a > 1 ensure 2α − 1 > 0 and finite c_α.Source: §C.6.1 · p. 49
  • Balancing the two terms after reparameterizing λ as nM^-2α recovers the first two bounds in display (32).The proof selects M by equating the terms in the resulting upper bound.Source: §C.6.1 · pp. 49–50

C.6.2 Proof with exponential decay of eigenvalues

  • For exponential eigenvalue decay, the proof reparameterizes λ as n exp(−M/d), bounds the resulting terms, and chooses M by equating them.The bounds use log(1 + e^x) ≤ c x for large x and log(1 + e^x) ≤ e^x for all x.Source: §C.6.2 · p. 50

Appendix D. Bias-variance tradeoff: Role of estimator and design matrix

Appendix D shows that OLS bias-variance behavior depends strongly on the design matrix and true dimensionality, producing double or multiple descent, whereas CV-tuned ridge remains U-shaped across designs.

Main findings

  • OLS can exhibit double- or multiple-descent test MSE, with peaks at design-dependent d/n values, while CV-tuned ridge remains classically U-shaped across all settings.These conclusions are supported by the four design-and-signal configurations in Fig. F1.Source: Appendix D · pp. 51–53, Figure F1 · p. 52

Experimental setup

  • The experiments vary fitted dimensionality d while holding n = 200 fixed across Gaussian and cosine designs and true dimensions d⋆ = 60 or 400.The four combinations are IA, IB, IIA, and IIB, with test MSE averaged over 50 noise redraws.Source: Appendix D · p. 51

Bias-variance tradeoff

  • For d < d⋆, both OLS and ridge show decreasing bias and increasing variance as dimensionality grows.For d > d⋆, tuned-ridge bias increases monotonically, while its variance rises until a design-dependent threshold and then decreases.Source: Appendix D · p. 52
  • Above d⋆, OLS bias generally increases with d, while design-dependent variance peaks can multiply and propagate into test-MSE peaks.The underlying bias-variance curves are shown for settings IA and IIA in Fig. F2.Source: Appendix D · pp. 52–53, Figure F2 · p. 53

Related papers

Loading 2006.10189v4…