Revisiting minimum description length complexity in overparameterized models

Abstract

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.

arXiv commentFirst two authors contributed equally

References in corpus (20)

• Scikit-learn: Machine Learning in Python
• Reconciling modern machine learning practice and the bias-variance trade-off
• Neural Tangent Kernel: Convergence and Generalization in Neural Networks
• OpenML: networked science in machine learning
• On the "degrees of freedom" of the lasso
• A Convergence Theory for Deep Learning via Over-Parameterization
• Benign Overfitting in Linear Regression
• Gradient Descent Provably Optimizes Over-parameterized Neural Networks
• Divide and Conquer Kernel Ridge Regression: A Distributed Algorithm with Minimax Optimal Rates
• A PAC-Bayesian Approach to Spectrally-Normalized Margin Bounds for Neural Networks
• Veridical Data Science
• Early stopping and non-parametric regression: An optimal data-dependent stopping rule
• From $\epsilon$-entropy to KL-entropy: Analysis of minimum information complexity density estimation
• To understand deep learning we need to understand kernel learning
• Benign overfitting in ridge regression
• Random design analysis of ridge regression
• Norm-Based Capacity Control in Neural Networks
• Measuring the Intrinsic Dimension of Objective Landscapes
• Optimal Regularization Can Mitigate Double Descent
• The Description Length of Deep Learning Models