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