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.
This paper establishes the generalization error of pooled min-ℓ2-norm interpolation in transfer learning, where data from diverse distributions are available. Min-norm interpolators arise naturally as implicit regularized limits of modern machine learning algorithms. Prior work has characterized their out-of-distribution risk when samples from the test distribution are unavailable during training. In many applications, however, limited test samples may be available at training time, yet properties of min-norm interpolation in this regime remain poorly understood. We address this gap by characterizing the bias and variance of pooled min-ℓ2-norm interpolation under both covariate shift and model shift. Our results yield several important implications. In certain cases under model shift, we show that adding data always hurts when the signal-to-noise ratio (SNR) is low. At higher SNR levels, transfer learning is beneficial provided the shift-to-signal ratio falls below a threshold that we characterize explicitly. Under covariate shift, we find that when the source sample size is small relative to the dimension, greater heterogeneity between domains reduces risk, and vice versa. While our model shift results are initially established for Gaussian designs, we extend them to more general designs through a universality argument. To illustrate the broader applicability of our technical tools beyond interpolation learning, we characterize the risk of a bias-corrected estimator that uses the pooled interpolator as an initialization and corrects the resulting bias with target data. On the technical side, we develop a novel anisotropic local law and a Lindeberg-swapping argument, yielding tools that may be of independent interest in random matrix theory and universality analysis. Finally, we supplement our theory with simulations demonstrating the finite-sample efficacy of our results.
Yanke Song, Kenneth Gu, Sohom Bhattacharya +1
Department of Statistics, Harvard University · Department of Statistics, Stanford University · Department of Statistics, University of Florida
A central problem in machine learning is that models can achieve near-perfect training performance while generalizing substantially less well to unseen examples. This gap is especially acute in high-dimensional, low-sample regimes, where many interpolating solutions exist and optimization must implicitly select among minima with different generalization properties. Following recent theoretical advances on optimization dynamics near the interpolation threshold, we note that the two-regime structure of risk minimization, with loss minimization followed by complexity minimization, motivates a biphasic optimization schedule. We thus theoretically demonstrate that GROKtimizer, a biphasic strategy that combines rapid convergence to interpolation with Critically Damped Momentum (CDM)-based post-interpolation norm minimization, offers a natural solution for selecting low-norm interpolating solutions. Under a local quadratic model of the post-interpolation basin, GROKtimizer provides a quadratic speedup over classical gradient descent, with provable optimality among first-order optimizers. To showcase the applicability of our method, we evaluate GROKtimizer on several synthetic benchmarks common in the classical grokking literature and on various real-world datasets. Finally, we reconcile our findings with the flat-minima hypothesis, highlighting the importance of post-interpolation dynamics in the construction of high-quality, generalizing models.
Understanding why predictors can generalize despite interpolating noisy training data is a central puzzle in machine learning. Most work on such "benign overfitting" studies minimum-2-norm linear regression, reflecting the inductive bias of gradient descent. However, modern optimizers such as Adam and Muon use non-Euclidean update geometries, favoring solutions associated with other norms. Analyzing regression for non-Euclidean norms is substantially more difficult, with known results essentially limited to Gaussians. In this paper, we develop a method to analyze benign overfitting in linear regression for general norms and general (sub-Gaussian) distributions. As a special case, we prove that minimum-p-norm interpolation with p>1 can benignly overfit even for non-Gaussian distributions, under suitable conditions. Perhaps surprisingly, for the 1-norm, benign overfitting does not hold in general for well-behaved (but non-Gaussian) distributions, showing that existing positive 1-norm results rely crucially on Gaussianity. Our proof analyzes the geometry of the dual optimization problem, using concentration and central limit tools to show it is approximately Euclidean in many high-dimensional cases.
Daniel Barzilai, Ohad Shamir
Weizmann Institute of Science · University of Toronto & Vector Institute