🤖 machine learning

When Does $\ell_2$ -Boosting Overfit Benignly? High-Dimensional Risk Asymptotics and the $\ell_1$ Implicit Bias

This paper demonstrates that $\ell_2$ -boosting suffers from slow, logarithmic-rate benign overfitting due to its $\ell_1$ implicit bias localizing noise into sparse sets, but proposes a tuning-free early stopping rule that recovers Lasso-like optimality for $\ell_1$ -bounded signals.

Original authors: Ye Su, Jian Li, Yong Liu

Published 2026-05-08

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Ye Su, Jian Li, Yong Liu

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

The Big Picture: The "Too Many Choices" Problem

Imagine you are a chef trying to recreate a complex dish (the "signal") based on a few taste tests (the "data"). However, your pantry is overflowing with thousands of spices (features), and your taste tests are slightly noisy because the tasters had a cold (noise).

In the world of machine learning, there's a famous phenomenon called Benign Overfitting. This is when a model is so complex it memorizes the noisy taste tests perfectly, yet somehow still tastes great to new customers. Usually, this happens when the model spreads the "noise" out so thinly across thousands of ingredients that it becomes invisible.

This paper asks a specific question: What happens if the chef uses a "greedy" strategy? Instead of mixing everything gently, the chef picks the single best spice at every step to fix the flavor, ignoring the rest. This is how Boosting algorithms work. The authors wanted to know: Does this greedy, "pick-the-best" approach also allow for benign overfitting, or does it make things worse?

The Main Discovery: The "Noise Hoarder"

The authors found that the greedy approach behaves very differently from the gentle, spreading approach.

The Gentle Approach (ℓ2 Geometry): Imagine a drop of ink falling into a large bucket of water. The ink spreads out evenly until it's invisible. In math terms, the "noise" is distributed across all available features. This allows the model to ignore the noise easily, leading to fast improvement (linear decay) as you add more data.
The Greedy Approach (ℓ1 Geometry/Boosting): Imagine the same drop of ink, but instead of spreading, it gets sucked into a tiny, dense sponge. The greedy algorithm picks a few specific features (the sponge) and dumps all the noise into them. It creates a sparse active set—a small group of features that carry the burden of the noise.

The Result: Because the noise is hoarded in a small group of features rather than spread out, it doesn't disappear. Even if you add thousands more features, the model still struggles with that concentrated noise. The error rate drops, but extremely slowly (at a "logarithmic" rate). It's like trying to empty a bucket with a teaspoon instead of a hose; it works, but it takes forever.

The "Spiked" Scenario: When It Does Work (Sort Of)

The authors also tested a scenario where the "pantry" isn't just random spices. Imagine you have a few "super-spices" (the signal) that are very strong, and thousands of "weak spices" (the tail) that are all roughly the same.

The Finding: If you have a massive number of these weak spices (much more than your number of taste tests), the greedy model can eventually get rid of the noise.
The Catch: Even in this best-case scenario, the noise still gets hoarded into a small group of those weak spices. The error still drops, but it's much slower than the gentle approach. To get the same level of accuracy as the gentle method, the greedy method would need an exponentially larger number of features.

The Solution: Stop While You're Ahead

Since the greedy method is slow to get rid of noise if it keeps going forever, the authors asked: When should the chef stop cooking?

They discovered a precise "stop sign."

As the chef keeps adding spices, the model's confidence in its current mix (the correlation with the data) goes up.
Eventually, the chef starts picking spices just to match the "cold" in the tasters' voices (the noise).
The authors calculated a specific threshold—the "noise floor." This is the point where the model starts listening to the cold rather than the food.

The Fix: They proposed a rule to stop the algorithm exactly when the model's confidence hits this noise floor.

If you stop here, the model ignores the noise.
It achieves the best possible accuracy (minimax optimality) without needing to guess or tune any settings.
It's like a smart timer that says, "Stop now, you've got the flavor right; any more and you're just adding noise."

Summary of the Analogy

The Problem: Greedy algorithms (Boosting) are great at finding the best features, but they are bad at spreading out noise. They concentrate noise into a few features, making it hard to get rid of.
The Consequence: Even with infinite data, the error rate drops very slowly compared to other methods.
The Solution: Don't let the greedy algorithm run until it memorizes the noise. Stop it the moment it starts listening to the "static" (noise) rather than the "music" (signal). If you do this, it performs just as well as the best possible method, but without the need for complex tuning.

What This Means (According to the Paper)

The paper concludes that for Boosting (and similar greedy methods), "Benign Overfitting" (getting perfect results by memorizing everything) is not as "benign" as we thought. It's actually quite "malignant" because it holds onto noise tightly. However, if you know exactly when to stop the process, you can avoid the bad parts and get excellent results.

The authors also note that this behavior likely explains why real-world tools like XGBoost (which builds decision trees adaptively) behave the way they do: they naturally tend to focus on a few features, inheriting this "noise hoarding" trait, which is why they often need careful stopping rules to perform best.

Technical Summary: When Does $\ell_2$ -Boosting Overfit Benignly?

Problem Statement

While "benign overfitting"—where interpolating estimators achieve vanishing test risk—is well-characterized in $\ell_2$ geometries (e.g., minimum $\ell_2$ -norm interpolants, ridge regression), its behavior under the $\ell_1$ implicit bias of greedy ensemble methods like boosting remains unclear. Theoretical analysis of boosting is hindered by the non-linear coupling of coordinate selection thresholds, which invalidates standard spectral resolvent tools used in $\ell_2$ analysis.

The central question addressed is whether the greedy geometry of $\ell_2$ -Boosting (forward stagewise regression) can benignly absorb and delocalize noise in high-dimensional settings, or if it structurally localizes noise into a sparse active set, thereby preventing the vanishing of excess risk.

Methodology

The paper analyzes the continuous-time limit of $\ell_2$ -Boosting (the $\ell_2$ -Boosting flow) over a fixed dictionary of base learners. The methodology involves:

Differential Inclusion Formulation: The boosting trajectory is modeled as a subdifferential inclusion governed by the dual $\ell_\infty$ -norm: $\frac{d\beta(t)}{dt} \in \partial \|g(t)\|_\infty$ , where $g(t)$ is the negative gradient. This captures the greedy coordinate descent mechanism that implicitly minimizes the $\ell_1$ -norm.
Convex Gaussian Minimax Theorem (CGMT): To handle the non-smooth $\ell_1$ $ℓ_{1}$ interpolant and the lack of closed-form solutions, the authors employ the CGMT. This requires overcoming two major hurdles:
- Non-compact Primal Domain: The authors bound the $\ell_1$ -norm of the optimal solution via a feasible pseudo-inverse construction to restrict the domain to a compact set.
- Unbounded Dual Variable: They prove the stochastic boundedness of the optimal dual variable $\tau^*$ to ensure uniform convergence.
Asymptotic Expansions: The analysis relies on delicate asymptotic expansions of double-sided truncated Gaussian moments to resolve the non-smooth soft-thresholding operator induced by the greedy selection.
Dynamic Path Analysis: For early stopping, the authors apply Danskin's Envelope Theorem to the subdifferential inclusion to analyze the monotonicity of the residual correlation $\rho(t) = \|g(t)\|_\infty$ .

Key Contributions and Results

1. Logarithmic Variance Decay under Isotropic Designs

Under an isotropic pure-noise model ( $\Sigma = I_p$ ), the paper proves that benign overfitting fails at the linear rate observed in $\ell_2$ geometries.

Mechanism: Unlike $\ell_2$ interpolants that uniformly diffuse noise energy across all dimensions, the greedy $\ell_\infty$ -driven selection localizes noise into a sparse active set of size at most $n$ .
Rate: The excess variance decays at a logarithmic rate:
$\mathbb{E}[\mathcal{E}(\hat{\beta}_\infty)] = \Theta\left(\frac{\sigma^2}{\log(p/n)}\right)$
In the proportional regime ( $p/n \to \gamma > 1$ ), the risk remains $\Theta(\sigma^2)$ and does not vanish. This is significantly slower than the $\Theta(n/p)$ decay in $\ell_2$ settings.

2. Risk Asymptotics under Spiked-Isotropic Designs

The authors characterize the risk when the covariance matrix has a "spiked" structure (signal head of dimension $k^*$ and an isotropic tail of dimension $r_2 = p - k^*$ ).

Condition for Vanishing Risk: The risk converges to zero only if the tail dimension is sufficiently large ( $r_2 \gg n$ ).
Rate: Even in this favorable setting, the variance decay is restricted to a logarithmic rate:
$\mathcal{E}_{tail} = \Theta\left(\frac{\sigma^2}{\log(r_2/n)}\right)$
This contrasts with the linear decay $\Theta(n/r_2)$ seen in $\ell_2$ geometries, implying that $\ell_1$ interpolation requires an exponentially larger overparameterization ratio to achieve comparable variance attenuation.

3. Minimax Optimality via Analytical Early Stopping

Motivated by the slow convergence of the interpolation limit, the paper proposes a tuning-free early stopping rule.

Stopping Rule: The flow is halted at time $t^*$ when the maximum empirical correlation $\rho(t)$ drops to the noise floor $2\lambda_n$ , where $\lambda_n \approx \sigma\sqrt{2\log p/n}$ .
Theoretical Guarantee: Halting at $t^*$ recovers the Lasso basic inequality. Under a bounded $\ell_1$ -path condition ( $\|\beta(t^*)\|_1 \leq C\|\beta^*\|_1$ ), the early-stopped estimator attains the minimax-optimal empirical prediction rate for $\ell_1$ -bounded signals:
$\frac{1}{n}\|\Phi(\beta(t^*) - \beta^*)\|_2^2 = O\left(\|\beta^*\|_1 \sigma \sqrt{\frac{\log p}{n}}\right)$
Adaptivity: The rule can be made adaptive using consistent plug-in estimators for noise variance (e.g., via Refitted Cross-Validation), removing the need for oracle knowledge.

Significance and Claims

The paper claims to resolve the analytical barriers preventing the characterization of benign overfitting in greedy ensembles. Its primary significance lies in demonstrating a fundamental geometric distinction between $\ell_2$ and $\ell_1$ implicit biases:

Localization vs. Diffusion: While $\ell_2$ geometry allows noise to dissipate through spectral traces, the $\ell_1$ geometry of boosting structurally localizes noise into sparse active sets due to non-linear soft-thresholding.
Theoretical Baseline: The derived logarithmic decay rates serve as a conservative bound for the generalization penalty of $\ell_1$ geometry, even under ideal isotropic tail conditions.
Practical Implication: The analysis provides a rigorous justification for early stopping in boosting. It shows that without stopping, the algorithm inevitably interpolates noise in a way that prevents risk minimization, whereas stopping at the noise floor recovers optimal statistical rates without hyperparameter tuning.

The authors note that while the analysis assumes a fixed dictionary, the mechanism of noise localization likely persists in adaptive tree-based boosting (e.g., XGBoost), as the greedy splitting heuristic similarly favors sparse selection over uniform energy spread. However, extending the rigorous asymptotics to adaptive, data-dependent trees remains an open problem.