The Interplay Between Interpolation and Aggregation in Regression: Optimal Sample Complexity

Mikael Møller Høgsgaard; Kasper Green Larsen; Liang-Yu Zou

cs.LGMay 28, 2026

The Interplay Between Interpolation and Aggregation in Regression: Optimal Sample Complexity

Authors: Mikael Møller Høgsgaard, Kasper Green Larsen, Liang-Yu Zou

Organizations: Department of Computer Science, Aarhus University, Aarhus, Denmark · Department of Statistics, University of Oxford, Oxford, United Kingdom

Abstract

This work investigates theoretically the interplay between interpolation and aggregation in regression. We establish that the $γ$ -graph dimension characterizes learnability for a broad class of natural aggregation procedures. Furthermore, we prove that an extremely simple aggregation procedure, combining three interpolating hypotheses via the median, is optimal among all these aggregation procedures, and is strictly more powerful than proper learning. Finally, we show that some hypothesis classes are learnable only by aggregating infinitely many hypotheses or by using non-interpolating aggregation rules (which may predict outside the range of their inputs), and any finite interpolating aggregation fails to achieve even trivial performance.

Explore similar work

How abundant are good interpolators?
Jun 4, 2026August Y. Chen, Ahmed El AlaouiOver-Parameterized Neural Networks Empirical Risk Minimization
Scale-Sensitive Shattering: Learnability and Evaluability at Optimal Scale
May 13, 2026Shashaank Aiyer, Yishay Mansour, Shay Moran +2Neural Scaling Laws
A Near-optimal SQ Lower Bound for Smoothed Agnostic Learning of Boolean Halfspaces
May 4, 2026Tim SinenOptimal Sample Complexity Sample Complexity

Jun 4, 2026 · math.STJ/K move · Enter open · S save

How abundant are good interpolators?

August Y. Chen, Ahmed El Alaoui

Let

S

be the set of unit norm linear classifiers

θ\in \mathbb{R}^d

which correctly classify every point of a labeled dataset

(X_i,y_i)_{i=1}^n

X_i \in \mathbb{R}^d

y_i \in \{-1,+1\}

, with a possibly negative margin

κ

fixed in advance. Under two natural data-generating distributions of the

(X,y)

pairs -- a Gaussian mixture model and a logistic model with Gaussian features -- and in the proportional regime

n/d \to α

with small enough

α

, we establish a large deviation principle on the event that a point

θ

chosen uniformly at random from

S

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

d

, 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

S

, 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.

Over-Parameterized Neural Networks Empirical Risk Minimization Interpolation Gradient Descent Gaussian Mixture Models

Open paper Ask about it PDF

Abstract

Explore similar work

How abundant are good interpolators?

Scale-Sensitive Shattering: Learnability and Evaluability at Optimal Scale

A Near-optimal SQ Lower Bound for Smoothed Agnostic Learning of Boolean Halfspaces