How sparsity and regularization shape learning in overparameterized models

Grokking through the Lens of Minimum-Norm Interpolation

Machine Learning

Summary

Some machine learning models can perfectly fit their training data but only learn the true underlying patterns later, a phenomenon known as grokking. The authors study why this delayed understanding happens by looking at how certain mathematical tools called regularization norms encourage simpler or sparser solutions. They show that when these tools favor sparsity, models can better generalize from data even when perfectly fitting it. Their theory matches experiments with simple and more complex neural networks, highlighting that small changes in regularization can greatly affect how well the model learns beyond just memorizing the data.

What this means in practice

  • For machine learning engineers: Optimize model regularization to improve accuracy when training data fits perfectly, especially in large, sparse feature spaces.
  • For neural network architects: Design training strategies that exploit sparsity-promoting norms to achieve better generalization in overparameterized networks.

Tested on simulated data.

Authors

Gil Kur, Ileana Rugina, Clémentine Carla Juliette Dominé, Marco Mondelli

Abstract

Grokking shows that fitting the training data and learning the underlying signal can occur at very different stages. However, existing theories offer limited quantitative insight into how this delayed generalization depends on inductive bias and signal structure. Our work addresses the gap by developing a statistical theory that characterizes how regularization geometry and signal sparsity govern generalization near interpolation. In particular, we focus on the prototypical setting of high-dimensional regression and identify regimes in which sparsity-promoting regularization makes exact interpolation much more accurate than approximate fitting. In strongly overparameterized noiseless problems, we prove a zero--one generalization law and construct a family of convex norms whose interpolators transition from the trivial risk of the all-zero predictor to exact recovery, while keeping the training error equal to $0$. Furthermore, when feature dimension and sample size are proportional, we provide a precise characterization of training and generalization errors along $\ell_r$-regularization paths. This in turn allows us to quantify the generalization gain that remains near interpolation: we show that this gain increases as the norm becomes more sparsity-promoting and as the target becomes sparser, with a sharp drop in generalization reached for noiseless data and $\ell_1$ regularization. Experiments on diagonal linear networks and transformers trained on modular arithmetic demonstrate the generality of our theoretical predictions. Finally, beyond grokking, our work reveals a statistical instability in minimum-norm interpolation: small perturbations in the regularization strength can lead to drastically different generalization, while preserving small training error.