Revisiting minimum description length complexity in overparameterized models

Understand

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.