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 does not adequately characterize complexity in overparameterized models, motivating a new MDL-based measure. The paper defines MDL-COMP through ridge-estimator-induced codes and characterizes it for linear and kernel methods. MDL-COMP can grow only logarithmically with d beyond interpolation, upper-bound in-sample MSE, and guide competitive, cheaper ridge hyperparameter tuning in limited-data settings.

  • Problem

    Parameter count is not well justified as a complexity measure when the number of parameters exceeds the number of training samples.

  • Method

    The paper defines MDL-COMP using an optimality criterion over encodings induced by ridge estimators for linear and kernel methods.

  • Results

    MDL-COMP often grows like log d for d > n, upper-bounds in-sample MSE, and supports competitive test-MSE tuning with computational savings over K-fold cross-validation.

  • Takeaways & Limitations

    Complexity in overparameterized models depends on data geometry, signal, and noise rather than parameter count alone, and MDL-COMP can provide a practical alternative to cross-validation in limited-data regimes.

  • Takeaways & Limitations

    The kernel-method results are in the classical low-dimensional regime, and extending the MDL analysis to high-dimensional kernels remains an open direction.

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

Parameter count is well justified for well-conditioned low-dimensional models but becomes inadequate in overparameterized settings. The paper introduces MDL-COMP, studies its behavior for linear and kernel methods, and evaluates a practical tuning criterion.

  • Motivation: Parameter count is rigorously justified mainly when d < n and the design matrix is well-conditioned, leaving its use unjustified for d > n or ill-conditioned designs.In high-dimensional models, the design matrix lacks full rank, so parameter counting does not reflect how directions contribute to fitting and prediction.
  • Contributions: MDL-COMP is proposed as a complexity measure for overparameterized linear and kernel models, using optimal codes induced by ridge estimators.The construction is motivated by minimum description length and is intended to support regularization-parameter tuning.
  • Theoretical results: MDL-COMP depends on the design or kernel matrix and can scale like d/n for d < n but only logarithmically in d for d > n.This behavior shows that the proposed complexity is not determined by parameter count alone.
  • Theoretical results: For kernel methods, MDL-COMP informs minimax in-sample generalization, while for linear models it provides an upper bound for in-sample MSE.The kernel result includes kernels in Gaussian and Sobolev spaces, and the minimax statement is formalized through the paper’s theorems.
  • Experiments: A data-driven MDL-COMP criterion achieves competitive test MSE with cross-validation in simulations and real-data experiments, especially with limited data, while reducing computation.The method is particularly advantageous for overparameterized models because it avoids the repeated training required by vanilla K-fold cross-validation.

2 Background on the principle of minimum description length

MDL treats statistical models as codes and selects the shortest description of observed data. The section reviews classical and normalized maximum-likelihood codes, explains their overparameterized limitations, and motivates luckiness-based codes as a principled alternative.

  • 2.1 Basic principle: The MDL principle selects the probability model or code that gives the shortest description length for the observed data.For a distribution Q, the description length is log(1/Q(y)); minimizing this quantity over a model class recovers maximum likelihood for a simple parametric family.
  • Classical MDL: Two-stage MDL is equivalent to BIC and therefore reduces, apart from a logarithmic term, to parameter counting.Its regularization term is d/2 log n, so it does not by itself resolve the overparameterized complexity problem.
  • 2.3 Normalized maximum likelihood: Normalized maximum likelihood provides a universal minimax code whose logarithmic normalization constant serves as a complexity measure under suitable regularity conditions.For a fixed-dimensional parametric class, its asymptotic complexity is 1/2 d log n to first order.
  • 2.3 Normalized maximum likelihood: In overparameterized linear regression, NML can be undefined because its normalization constant is infinite; truncating the response space can yield a trivial measure independent of X and d.When d > n and X has full row rank, the maximum likelihood can be constant across responses, producing the infinity problem.
  • 2.4 Luckiness normalized maximum likelihood: Luckiness normalized maximum likelihood uses a luckiness function to regularize the code, and the paper derives a complexity measure by optimizing over a family of such codes.The resulting framework connects LNML with regularized maximum likelihood and supports MDL estimators parameterized by positive semidefinite matrices.

3 Ridge-based minimum description length complexity

The paper defines MDL-COMP through a family of ridge-induced LNML codes, optimizing data encoding while accounting for regularization-hyperparameter codelength. The construction is computationally feasible, analytically tractable, and tailored to complexity in overparameterized linear and kernel models.

  • Ridge-induced codes: Ridge estimators provide the code family because they are computationally feasible and can achieve strong predictive performance in linear and kernel methods.The luckiness function is inspired by ridge’s regularization penalty, and the resulting codes are indexed by regularization matrices.
  • MDL-COMP definition: MDL-COMP is defined as the minimum excess description length obtained from ridge-induced LNML codes for a fixed design matrix.The encoded object is the response vector, while the covariate matrix is assumed known to sender and receiver.
  • LNML construction: The LNML construction separates data-fit coding from a luckiness factor representing the regularization penalty, then normalizes the result into a valid code distribution.A hyperparameter codelength is added after optimizing redundancy, using a quantization-based encoding for the regularization parameters.
  • Codelength choice: The discretized-Λ codelength is an analytical approximation, and alternative luckiness functions, code families, or hyperparameter codelengths would define different complexity measures.The paper therefore presents MDL-COMP as an upper bound on the true MDL complexity, while arguing it can be tighter than parameter count in overparameterized linear models.

4 Main results

The theoretical results characterize MDL-COMP through design or kernel spectra and signal-to-noise properties, including nonlinear scaling beyond the interpolation threshold. They also connect the measure to prediction error, minimax in-sample risk, and practical ridge hyperparameter selection.

  • 4 Main results: MDL-COMP depends on the design or kernel eigenvalues and signal-to-noise ratio rather than only on parameter count.The linear characterization uses eigenvalues of X⊤X and the signal coordinates in that eigenbasis; the kernel bound has analogous spectral and signal-to-noise dependence.
  • Practical implications: A data-driven Prac-MDL-COMP criterion is proposed for ridge hyperparameter tuning and can achieve test-MSE performance competitive with cross-validation while reducing computational cost.The practical criterion avoids requiring knowledge of the unknown true parameter θ⋆.
  • 4.1.1 Scaling of MDL-COMP: MDL-COMP scales linearly with d below n but grows logarithmically in d above n for Gaussian designs, while spike designs can produce nonlinearity even when d<n.The simulations vary covariate dimension under Gaussian and spike covariance structures, with n=200 and differing noise, eigenvalue-decay, and spike settings.
  • 4.1.2 MDL-COMP informs fixed design mean-squared error: MDL-COMP bounds the optimal fixed-design in-sample MSE for ridge estimators, linking minimum-description complexity to prediction error.The optimal redundancy and the regularization choice attaining it are used in the bound.
  • 4.2 Characterizing MDL-COMP for kernel methods: For kernel methods, MDL-COMP can inform minimax in-sample generalization, with matching rates in the stated Gaussian and Sobolev settings.The result is presented as an indirect justification for the ridge-based LNML codes.
  • 4.2 Characterizing MDL-COMP for kernel methods: For ReLU neural tangent kernels, MDL-COMP can decrease as input dimension increases when n≫d and the dimension-dependent SNR does not change the n-scaling.The reported scaling is SNR^2/(1+d) · ((d log n)/n)^(d/(d+1)), up to logarithmic factors.

5 Experiments with data-driven MDL-COMP

Experiments evaluate Prac-MDL-COMP as a data-driven ridge and kernel hyperparameter criterion, finding competitive or superior test-error performance with lower computational cost than cross-validation.

  • 5.1 MDL−COMP inspired hyper-parameter tuning: The practical criterion approximates MDL-COMP without knowing the true parameter and uses a single regularization hyperparameter for ridge or kernel ridge models.For kernels, the criterion uses the kernel matrix eigenvalues and the estimator (K + λI)^-1y.
  • 5.1 MDL−COMP inspired hyper-parameter tuning: Prac-MDL-COMP is computationally cheaper than k-fold cross-validation because it trains one model per hyperparameter rather than k models.The paper summarizes this as O(k) computationally more efficient than k-fold cross-validation.
  • 5.2 Prac-MDL-COMP informs test MSE in Gaussian simulations: In Gaussian simulations, minimizing the Prac-MDL-COMP objective selects ridge models with low test MSE across varied d/n ratios, near leave-one-out cross-validation and avoiding the OLS peak.This behavior is reported for d/n values from 1/10 to 10.
  • 5.3 Experiments with PMLB datasets: Prac-MDL-COMP outperforms Ridge-CV in limited-data settings and becomes comparable as training samples increase.The advantage decreases as d/n decreases.
  • 5.4 Experiments with fMRI data: On fMRI data, Prac-MDL-COMP outperforms Bayesian ARD and BIC across voxels while remaining roughly on par with cross-validation.Cross-validation is slightly better for most voxels, whereas Prac-MDL-COMP wins by a larger margin on the remainder.
  • 5.4 Experiments with fMRI data: The Prac-MDL-COMP objective tracks test error on fMRI data, with test error generally increasing as the objective increases and estimated bRopt correlating 0.69 with test MSE.The relationship is also examined for neural tangent kernel regression, where the curves are flatter but still support objective-based selection.

6 Discussion

The discussion argues that MDL-COMP is a more defensible complexity measure than parameter count in overparameterized settings and links estimator choice to double descent.

  • MDL-COMP is valid for overparameterized models, while parameter count lacks theoretical justification there.
  • Prac-MDL-COMP offers a computationally efficient alternative to cross-validation for ridge hyperparameter tuning, with competitive or sometimes better test performance in limited-data settings.
  • 6.1 Consequences for bias-variance tradeoff in overparameterized models: Replacing parameter count with MDL-COMP does not remove double descent, because MDL-COMP remains monotone in dimension.
  • 6.1 Consequences for bias-variance tradeoff in overparameterized models: Tuned ridge estimators instead show classical U-shaped test-error curves and outperform OLS on ill-conditioned designs, whereas OLS can exhibit double or multiple descent.
  • 6.1 Consequences for bias-variance tradeoff in overparameterized models: The authors hypothesize that double descent may reflect poor estimator choice in ill-posed regimes rather than parameter count alone.
  • 6.2 Future directions: Future work includes out-of-sample guarantees, high-dimensional kernel regimes, and MDL-COMP variants adapted to sparse ℓ1-regularized models.

1 Introduction

The appendix details simulation settings and proof support for MDL-COMP, including how fitted dimensions and eigenstructures are constructed for ridge models.

  • A.1 Simulation set-up: The appendix sketches MDL-COMP scaling proofs, derives high-dimensional bounds, extends minimax optimality beyond Gaussian noise, and supplies MDL background.
  • A.1 Simulation set-up: The simulations vary the fitted dimension d by selecting the first d columns of a full design matrix while holding the sample size fixed.
  • A.1 Simulation set-up: MDL-COMP computation requires eigenvalues of X⊤X and a transformed true parameter vector w based on restriction or zero-padding.

A.2 Proof sketch for random isotropic designs

For isotropic Gaussian designs, the proof sketch explains MDL-COMP scaling through the spectrum of X⊤X, while related results establish minimax coding properties under broader noise classes.

  • A.2 Proof sketch for random isotropic designs: For d ≫ n, XX⊤ is approximately (d/n)I_n, giving X⊤X rank n with nonzero eigenvalues near d/n.
  • A.2 Proof sketch for random isotropic designs: The scaling argument depends on whether the fitted dimension is below or above the true dimension and on the transformed signal norm.
  • A.2 Proof sketch for random isotropic designs: MDL-COMP scales as O(d/n) for small d and O(log d) when d ≫ n, so d/n should not be the default overparameterized complexity.
  • A.2 Proof sketch for random isotropic designs: The optimal redundancy bound can scale as d/n when the true-parameter norm grows with d, but remains bounded when that norm is fixed.
  • The MDL-COMP code is minimax over a broader bounded-variance noise class, not only Gaussian noise.
  • MDL complexity generalizes maximum likelihood when the code family is broad, whereas for a single parametric family it reduces to the MLE principle.

Appendix B. Further numerical experiments

Additional experiments test Prac-MDL-COMP under misspecification and alternative validation procedures, finding that it often selects models that generalize well.

  • The appendix evaluates Prac-MDL-COMP for out-of-sample MSE in Gaussian and misspecified linear models.
  • B.1 Misspecified linear models: Prac-MDL-COMP is compared with BIC for fMRI prediction, while cross-validation and Ridge-ARD comparisons are reported elsewhere.
  • B.1 Misspecified linear models: The reported Fig. 4 results remain when five-fold cross-validation replaces leave-one-out cross-validation.
  • B.1 Misspecified linear models: Prac-MDL-COMP still selects a λ that generalizes fairly well under t-distributed errors, decaying eigenvalues, and thresholded outcomes.

B.2 Real data experiments continued

Prac-MDL-COMP performs competitively with cross-validation for ridge regression, with its strongest evidence in limited-data real-data settings and under model misspecification.

  • Comparison with cross-validation: Prac-MDL-COMP’s good performance for linear models also holds against 5-fold cross-validation.The comparison is reported in Fig. B2.
  • Real-data experiments: In 28 real datasets, MDL-COMP tends to outperform Ridge-CV when d/n is large, while cross-validation catches up or wins as training samples increase.These comparisons use varying numbers of training points sampled from real datasets.
  • Model selection under misspecification: Under various misspecifications, Prac-MDL-COMP still selects models that generalize reasonably well while sample size varies with fixed d.This setup differs from other figures in which d is varied.

C.1 Proof of Theorem 1

The proof of Theorem 1 analyzes the MDL-COMP objective through the singular-value decomposition of the design matrix and separates low- and high-dimensional cases.

  • Proof setup: The Gaussian observation model and ridge estimator determine the expressions whose algebraic simplification yields the claimed formulas for Ropt and MDL-COMP.The argument explicitly compares the data distribution with the ridge-based encoding quantities.
  • Optimization of regularization: The proof identifies optimal regularization by minimizing a separable objective over the regularization components λ_i.Stationary-point and boundary arguments are used to characterize each component.
  • Dimensional regimes: The proof treats the low-dimensional case d<n first and states that the high-dimensional case requires analogous linear-algebraic adaptations.The d>n derivation changes the matrix dimensions and uses the nonzero singular-value block.
  • Singular-value decomposition: For n>d, the analysis expresses the relevant quantities using the singular values and singular vectors of X, with Λ represented in the corresponding basis.The projection onto the orthogonal complement of the column space of X handles the residual component.

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

For d>n, the proof modifies the singular-value decomposition calculations to accommodate rank at most n and derives the corresponding MDL-COMP expressions.

  • High-dimensional decomposition: When d>n, the singular-value decomposition uses n-dimensional matrices for the nonzero components, while the remaining d−n directions do not contribute nonzero singular values.The proof introduces the n×n principal minor Λ_n and the matrix eD containing the nonzero entries.
  • Modified quadratic forms: The ridge quadratic form is rewritten using VΛ_n(eD+Λ_n)^−1V⊤, yielding the modified expression needed for the high-dimensional case.This replaces the corresponding formula used when n>d.
  • Deriving the claims: The resulting calculation establishes the claimed expression for T2 when d>n.The proof then proceeds to the second claimed quantity using the modified matrix A_Λ.
  • MSE bound: The proof of the in-sample MSE bound optimizes each λ_i separately and checks the objective at the boundary values λ_i=0 and λ_i→∞.It then substitutes the optimal values and applies x≤−log(1−x) to obtain the bound.

C.3 Proof of Theorem 3

Theorem 3 analyzes kernel methods through the kernel eigendecomposition and relates the resulting bounds to eigenvalue decay and finite-rank structure.

  • Kernel eigendecomposition: The kernel proof decomposes K into eigenvalues and eigenvectors, expressing the signal coefficients in that eigenbasis.The ridge objective is then written in terms of the kernel eigenvalues and transformed signal.
  • Operator representation: The proof represents the target function and kernel matrix through feature operators, an eigenvalue operator, and an operator Γ satisfying ΓΓ*=I_n.This connects the infinite-dimensional kernel representation to the observed n-dimensional kernel matrix.
  • Tightness conditions: Additional tightness depends on rapid decay of the relevant eigenvalue or coefficient sequences and on the optimizer occurring before index n.These conditions concern the inequalities used in optimizing the bound.
  • Tightness conditions: The resulting inequalities are relatively tight when kernel eigenvalues decay quickly or the kernel has finite rank below n.Under these conditions, the kernel expansion can be approximated using its first n terms.

C.4 Proof of Theorem 4

The proof derives MDL-COMP expressions from the empirical eigenvalue distribution of X⊤X and analyzes their asymptotic behavior using random matrix theory. It connects the limiting expression to the Shannon transform under the Marčenko–Pastur law and preserves the same optimizer under a shifted objective.

  • Eigenvalue representation: MDL-COMP is rewritten using the empirical distribution F_d of the eigenvalues of X⊤X, leveraging rotational invariance of θ⋆.The proof applies Jensen’s inequality and E[θ⋆_i^2] = E[∥θ⋆∥^2]/d under a rotationally invariant distribution.
  • Random matrix limit: As d,n → ∞ with d/n → γ, F_d converges almost surely to the Marčenko–Pastur distribution MP_γ.The limiting distribution has support determined by b1 = (1 − √γ)^2 and b2 = (1 + √γ)^2.
  • Asymptotic evaluation: The log-integral converges almost surely to γ·E_Z∼MPγ[log(1 + snr·Z)], yielding the theorem’s closed-form expression through the Shannon transform.The proof uses the Portmanteau theorem and eigenvalue bounds to control the integral, then substitutes the closed-form transform into the limiting expression.
  • Optimization consequence: The theorem’s objective differs from the earlier objective only by a constant shift in the eigenvalues, so both objectives have the same minimizer.The proof separately establishes bounds for polynomial and exponential eigenvalue decay under the stated decay assumptions.

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

The appendix compares OLS and cross-validation-tuned ridge across Gaussian and cosine designs and different true dimensionalities. Ridge retains a classical U-shaped test-MSE curve, whereas OLS exhibits design-dependent double or multiple descent.

  • Overall comparison: CV-tuned ridge exhibits a classical U-shaped test-MSE curve across all four design and signal settings, while OLS behavior depends strongly on the covariate design and true dimension.The experiments vary fitted dimensionality with n = 200 and compare OLS with CV-tuned ridge across four settings.
  • OLS behavior: OLS can show double-descent or multiple-descent test MSE, with variance peaks occurring at design-dependent values of d/n rather than necessarily at 1.Above the true dimension d⋆, OLS bias generally increases while the variance term can develop multiple peaks that appear in test MSE.
  • Experimental design: The experiments use n = 200, up to 2000 covariates, Gaussian or cosine design matrices, and true dimensions d⋆ = 60 or d⋆ = 400.The four settings combine two design ensembles with whether the true signal dimension is below or above the sample size.
  • Bias-variance tradeoff: For d < d⋆, both OLS and ridge show the classical bias-variance tradeoff, with decreasing bias and increasing variance as d grows.The appendix studies this tradeoff through test-MSE curves and underlying bias-variance plots.
Loading 2006.10189v4…