How Abundant Are Good Interpolators? A Large Deviation Analysis of Overparametrized Learning

Paper: 2606.06469 Authors: August Y. Chen, Ahmed El Alaoui Categories: math.ST, cs.LG, math.pr

The Gap

Deep learning’s success in the overparametrized regime (more parameters than data) contradicts classical wisdom: models that perfectly interpolate training data should overfit catastrophically. Prior work showed that gradient descent finds interpolators with good generalization (“benign overfitting”), but left a fundamental question unanswered: Are such good interpolators rare exceptions, or do they dominate the space of all possible solutions?

Existing papers studied specific algorithms (gradient descent, ridge regression) but never characterized the landscape geometry of the entire solution set. Without this, we don’t know if gradient descent succeeds because good solutions are abundant (easy problem) or because it’s cleverly navigating toward rare islands of good performance (hard problem requiring algorithmic magic).

Classical view          Prior work            This paper's question
--------------          ----------            -------------------
   Data                GD finds              How many good ones
    |                  good fit              exist in total?
    v                     |                         |
Parameters  -------->  Overfit      vs.    [ ? ? ? ? ? ? ? ]
(too many)             (expected)          (Solution space S)
                           |                         |
                           v                         v
                       Actually                  Measure the
                       generalizes!              abundance

The Increment

One sentence: Before this paper, we knew gradient descent finds good interpolators in overparametrized settings; after, we know such solutions are exponentially rare — gradient descent performs nontrivial algorithmic work, not random search.

Core Mechanism

The paper establishes a large deviation principle for the generalization error distribution over all interpolators. Here’s the machinery:

Fix a labeled dataset of size n in d dimensions. Let S be the set of all unit-norm linear classifiers θ that correctly classify every training point (possibly with negative margin κ). The question: if you pick θ uniformly at random from S, what’s its generalization error?

Under Gaussian mixture models or logistic models with Gaussian features, in the proportional regime n/d → α (with α small enough), the paper proves that the probability a random interpolator achieves generalization error ε follows a large deviation principle with rate function I(ε). This means: P(error = ε) ≈ exp(-d · I(ε)).

The rate function I(ε) is deterministic and has a unique maximizer ε**. This creates a concentration phenomenon: all but an exponentially vanishing fraction of interpolators have error extremely close to ε*. The paper then numerically compares ε* to the error achieved by gradient descent and linear programming, finding that efficient algorithms substantially outperform the typical interpolator.

Solution space S visualization:

              Good region          Typical region (most of S)
              (exp(-d*c1))         (1 - exp(-d*c2))
                   |                      |
                   v                      v
    [*****]  [==========================]
       ^                    ^
       |                    |
    GD finds          Random pick lands
    (error ~ 0.1)     (error ~ 0.5 = eps*)

Exponential scale: fraction ~ exp(-d * I(eps))
                             ----------------
                             rate function
                             
As d grows, good region shrinks exponentially fast

Think of the solution space as a stadium of seats. You have a massive stadium (all interpolators S) where the vast majority of seats are in the nosebleed section (typical performance ε**). There’s a tiny VIP section near the field (good interpolators with low error), but it occupies only exp(-d · c) fraction of seats — exponentially shrinking as dimension d grows.

Random search is like getting a random ticket: you almost certainly end up in the nosebleed section. Gradient descent is like having a VIP pass: it navigates directly to the rare good seats. The paper proves the stadium has this geometry by computing the exact “seating chart” (rate function I) and showing that the typical seat location (ε*) is deterministic and far from optimal.

The metaphor’s load-bearing insight: spatial abundance drives algorithmic necessity. If good seats were plentiful, any search would work. Because they’re exponentially rare, finding them requires algorithmic structure (gradient flow toward implicit bias).

Key Concepts

• Large Deviation Principle (LDP): Imagine flipping 1000 fair coins. Getting exactly 500 heads has probability ≈ 1/√1000 (typical). Getting 900 heads has probability exp(-1000 · I(0.9)) where I(0.9) > 0 (exponentially rare). An LDP quantifies how the probability of rare events decays exponentially with a “rate function” I. Here, I(ε) measures how atypical it is for a random interpolator to achieve generalization error ε. The unique minimizer of I (where probability concentrates) reveals the typical behavior.

• Interpolation vs. Generalization in High Dimensions: An interpolator perfectly fits training data (training error = 0). In classical learning theory with n samples and d parameters where n >> d, interpolation usually means overfitting. But when d >> n (overparametrized), there are infinitely many interpolators. Some generalize well, others don’t. This paper shows the distribution: most generalize similarly (badly), while efficient algorithms find the rare ones that generalize well.

• Proportional Regime: Setting n/d → α means sample size and dimension grow at a fixed ratio. When α is small (few samples per dimension), you’re deeply overparametrized. This regime enables tractable mathematical analysis because both n and d are large, allowing concentration inequalities and random matrix theory to kick in. The paper’s results hold in this asymptotic regime, giving exact characterizations unavailable in finite dimensions.

Framework Shift

Before (algorithmic focus):              After (landscape geometry):

    Data --> [GD] --> Good model              Solution space S
              ^                                      |
              |                                      v
         Why does this              Measure abundance at exp scale
         work so well?                      |
                                            v
                                     [ tiny good region ]
                                     [   huge bad region  ]
                                            |
                                            v
                                   GD navigates to rare zone
                                   (algorithmic necessity)

From “gradient descent somehow finds good solutions” to “the solution space has exponential stratification where good solutions are provably rare, making gradient descent’s success nontrivial.”

Expert Assessment

Problem choice: This is a genuine foundational gap. The benign overfitting phenomenon has been observed empirically and studied algorithmically, but the geometric structure of the solution space remained uncharacterized. Understanding whether good solutions are abundant or rare is critical for interpreting why modern deep learning works. The question is well-posed and sits at the intersection of statistical learning theory and high-dimensional geometry.

Method maturity: The paper brings serious mathematical machinery (large deviation theory, random matrix theory, convex geometry) to bear on the problem. The choice to study linear classifiers is a limitation but also a strength — it’s the simplest nontrivial setting where overparametrization occurs. The LDP framework is elegant and provides sharp, non-asymptotic characterizations. However, the assumption of Gaussian features is restrictive; real data rarely satisfies this. The numerical comparison to gradient descent is somewhat thin — more extensive experiments across different α values and architectures would strengthen the claim.

Experimental integrity: The baselines (gradient descent, linear programming) are reasonable but not exhaustive. The paper doesn’t compare to other interpolation schemes (e.g., minimum ℓ1-norm, random projections). The numerical plots are clean but lack error bars or confidence intervals. The claim that gradient descent “outperforms the vast majority” relies on comparing a point estimate (GD’s error) to the rate function’s maximizer (typical error), which is theoretically sound but could be validated more robustly with sampling experiments.

Writing quality: The paper is mathematically rigorous but dense. The introduction could better motivate why characterizing the entire solution space matters beyond algorithmic curiosity. Section 3 (main results) front-loads heavy notation before building intuition — reversing this order would help accessibility. The numerical section (Section 5) feels tacked on; integrating it earlier with stronger experimental design would elevate the narrative.

Verdict: weak accept — Solid theoretical contribution addressing a real gap, but limited to restrictive models and thin experimental validation. The core result is important for understanding overparametrization, but the paper’s impact is currently confined to the theory community due to strong distributional assumptions.

Takeaways

For theorists: The large deviation principle framework is a powerful lens for analyzing high-dimensional learning. The rate function I(ε) encodes the geometry of performance landscapes at the exponential scale — this technique could extend to nonlinear models, other loss functions, or different regularization schemes.

For practitioners: When debugging why your overparametrized model generalizes, don’t assume “all interpolators are roughly the same.” The optimization algorithm matters exponentially. If switching from one optimizer to another drastically changes generalization, you’ve likely moved between different exponential strata of the solution space.

Transferable technique: The paper’s approach of characterizing solution space geometry before studying algorithms inverts the usual research flow. Instead of “algorithm X works, let’s prove why,” it asks “what does the landscape look like, then where does algorithm X land?” This framing could apply to neural architecture search, hyperparameter tuning, or any setting where multiple solutions achieve zero training loss.

Limitation to remember: All results assume Gaussian features. Real-world data (images, text, graphs) violates this severely. The paper establishes a baseline for idealized settings but doesn’t tell us whether gradient descent’s advantage persists under distribution shift, label noise, or structured data.