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 ℓ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 ℓ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.
Figures & tables
Figure 1: Training and generalization error (MSE) for regression regularized with the convex ℓ1−ℓ∞ norm in ( 8 ) (Left) and with ℓr norms (Center, Right). Left: We pick β∗ to be a k∗ -sparse vector with uniformly distributed ±1 entries, consider the estimator in ( 10 ) and plot normalized training (blue) and generalization (orange) errors as a function of regularization strength κ . We report the mean ± one standard error over 10 seeds. The generalization error exhibits a zero–one transition around κ=1 , while the training error remains close to 0 (Theorem 1 ). Center, Right: We pick B as in ( 21 ) with W a Rademacher random variable, δ=0.2 , σ=0.1 , n=1000 and p=5000 . We consider the estimator βκ,r in ( 2 ) and plot MSE gain MSEr(κ)−MSEr(κr⋆) as a function of training error E(βκ,r) . Solid curves are theoretical predictions from Lemma 2 , and dots are obtained by solving regularized regression numerically (mean ± one standard error over 20 seeds). In the central plot, for a fixed ρ=0.02 , the curves flatten as r increases (Theorem 2 ). In the right plot, for a fixed r=3/2 , the curves flatten as ρ increases (Theorem 4 ).
Figure 2: Residual generalization error as a function of the training error. Diagonal linear networks (Left, Center) are trained by gradient descent on the square-root loss ( δ=0.2 , σ=0.03 , n=2000 , p=104 ; mean ± one standard deviation over 20 seeds). Left: at fixed ρ=0.02 , the gain in generalization near interpolation decreases as k increases, mirroring the decrease of Sr in r (Theorem 2 ). Center: at fixed k=0.01 , the gain in generalization near interpolation decreases as ρ increases (Theorem 4 ). Transformers (Right) are trained by AdamW on the cross-entropy loss for a modular arithmetic task (mean ± one standard deviation over 5 seeds). We regulate the output scale α controlling the learning regime and implicit bias. As expected, the gain in generalization near interpolation decreases with α . For implementation details, see Appendix E .
Appendix figures & tables1 asset
Supplementary material from the paper’s appendix.
Appendix
Figure 3: Early-stopped gradient descent on diagonal linear networks (solid lines) versus Qk -regularized regression solved with CVXPY (squares), for several initialization scales k . Both are plotted as parameter MSE against training error; time along the gradient-descent trajectories flows from right to left. Stars mark the state-evolution prediction for the minimum- Qk interpolator, the common endpoint of both methods. For k=100 , each square is annotated with its κ (as a multiple of the interpolation threshold κ∗ ) and the gradient-descent time t at which it reaches the same training error.