math.STJun 20, 2024

Generalization error of min-norm interpolators in transfer learning

Authors: Yanke Song, Kenneth Gu, Sohom Bhattacharya, Pragya Sur

Abstract

This paper establishes the generalization error of pooled min-ℓ2\ell_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\ell_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.

Explore similar work

CardsList
Jun 4, 2026math.ST

How abundant are good interpolators?

Let SS be the set of unit norm linear classifiers θ∈Rdθ\in \mathbb{R}^d which correctly classify every point of a labeled dataset (Xi,yi)i=1n(X_i,y_i)_{i=1}^n, Xi∈RdX_i \in \mathbb{R}^d, yi∈{−1,+1}y_i \in \{-1,+1\}, with a possibly negative margin κκ fixed in advance. Under two natural data-generating distributions of the (X,y)(X,y) pairs -- a Gaussian mixture model and a logistic model with Gaussian features -- and in the proportional regime n/d→αn/d \to α with small enough αα, we establish a large deviation principle on the event that a point θθ chosen uniformly at random from SS achieves a given generalization error, with high probability over the choice of the data. The associated large deviation rate function is deterministic and describes the proportion, at the exponential scale in dd, of interpolating classifiers having a given desired performance. As a consequence, we establish the following concentration phenomenon: all but an exponentially small fraction of interpolating classifiers have approximately the same generalization performance given by the unique maximizer of this rate function. We numerically compare this maximizer to the performance of empirical risk minimization by gradient descent and to the performance of a natural linear program, both finding a point in SS, and deduce that in the overparametrized regime of small αα, these efficient procedures outperform the vast majority of interpolators, pointing to their nontrivial benign overfitting in this setting.
August Y. Chen, Ahmed El Alaoui
Empirical Risk MinimizationInterpolationGradient DescentLarge Deviations TheoryGaussian Mixture Models
AskPDF
Jun 1, 2026cs.LG

Fast Generalization after Interpolation via Critically Damped Momentum Optimization

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.
Luca Muscarnera, Silas Ruhrberg Estévez, Yuanzhang Xiao +1
Gradient DescentInterpolationRegularization MethodsLow-Data RegimesGrokkingMomentum
AskPDF
Jan 18, 2025stat.ML

Fixed-Gaussian Spectral Algorithms: Minimax Optimal Rates for Misspecified Learning and Transfer

The principal objective of this work is twofold within nonparametric regression settings: (1) to establish the minimax optimal convergence rates for fixed-bandwidth Gaussian kernel spectral algorithms when the true regression function resides in a Sobolev space, and (2) to apply Gaussian spectral algorithms for achieving robust and adaptive transfer learning under concept shift. While minimax optimality of misspecified spectral algorithms has been established, existing guarantees are typically restricted to the non-saturation regime. We demonstrate that the infinite smoothness of fixed-bandwidth Gaussian kernels provides universal robustness to model misspecification by showing that this kernel choice enables any spectral algorithm to attain minimax optimal rates, provided the regularization parameter decays exponentially. This result effectively decouples optimality from the algorithm's inherent qualification. Building on this, we then advocate Gaussian spectral algorithms as powerful components in a learning framework for robust and adaptive transfer. Specifically, we derive the adaptive convergence rate of the excess risk for this framework and show that the rates are optimal up to logarithmic factors. Our results also reveal the impact of the magnitude of the concept shift and the sample size on the generalization error.
Haotian Lin, Matthew Reimherr
Spectral AlgorithmsKernel Ridge RegressionTransfer LearningRegularization Methods
AskPDF