TL;DR
In high-dimensional noisy settings, the common wisdom that "stronger inductive bias is always better" fails for interpolating models. This paper proves that while a strong $\ell_1$ bias is optimal for noiseless data, "moderate" inductive biases ($\ell_p$ norms with $p \in (1, 2)$) achieve significantly faster polynomial generalization rates when forced to fit noisy training data.
What Problem Does This Paper Address?
Modern machine learning often involves "interpolating" models—overparameterized networks that fit the training data perfectly, even when that data contains noise. A central mystery in deep learning theory is why these models generalize so well instead of just memorizing the noise.
The standard explanation is implicit bias: optimization algorithms naturally favor "simple" solutions (e.g., those with small norms). For sparse signals, the strongest bias is the $\ell_1$ norm. However, previous research showed that $\ell_1$-norm interpolators generalize poorly on noisy data, achieving only slow, logarithmic rates. Conversely, the $\ell_2$ norm (ridge-like bias) is resilient to noise but fails to capture sparse structures.
The authors ask: Is there a "Goldilocks zone" of inductive bias that is strong enough to capture structure but flexible enough to handle noise?
Methods
The authors provide a rigorous theoretical analysis of two types of estimators in high-dimensional settings (where the number of features $d$ is much larger than the number of samples $n$):
- Minimum $\ell_p$-norm interpolators for linear regression.
- Maximum $\ell_p$-margin interpolators (hard-margin $\ell_p$-SVMs) for classification.
They focus on the range $p \in (1, 2)$ and use the Convex Gaussian Minimax Theorem (CGMT) to derive non-asymptotic upper and lower bounds on the estimation error. Their analysis assumes the ground truth is sparse and the features follow an isotropic Gaussian distribution.
Datasets
The paper validates its theoretical findings using:
- Synthetic Data: High-dimensional Gaussian features with a 1-sparse ground truth vector and varying levels of additive noise.
- Leukemia Classification Dataset: A classic high-dimensional biological dataset ($d=7070$ features, $n=72$ samples) used to test the classification theory on real-world data.
- Binarized MNIST: Used for experiments with Convolutional Neural Tangent Kernels (CNTK) to provide preliminary evidence that these insights extend to non-linear, deep-learning-adjacent models.
Key Insights and Ideas
- The Fragility of $\ell_1$: When forced to interpolate noise, an $\ell_1$ interpolator is too "brittle." To fit a noisy label, it must assign a very large weight to a single feature, which drastically increases the variance of the model.
- The "New" Bias-Variance Trade-off: The authors propose a trade-off specific to interpolating models. A stronger bias (decreasing $p \to 1$) aligns the model better with the ground truth (reducing bias) but makes it more vulnerable to noise (increasing variance).
- The Power of $p \in (1, 2)$: By choosing a $p$ slightly larger than 1, the model can "smear" the noise across more dimensions than $\ell_1$ would allow, while still remaining much more structured than an $\ell_2$ model.
- Polynomial vs. Logarithmic Rates: The most striking insight is the jump in performance. While $p=1$ is stuck with a slow logarithmic rate $1/\log(d/n)$, any $p > 1$ can achieve fast polynomial rates (e.g., $1/n$).
This trade-off is beautifully illustrated in the figure below, which shows how the optimal $p$ shifts away from 1 as noise is introduced:
Key Results
- Regression: For $p \in (1, 2)$, the estimation error decays at a polynomial rate close to $1/n$. This is a massive improvement over the near-constant or logarithmic rates seen for $p=1$ or $p=2$ in high dimensions.
- Classification: The results are even stronger here. For certain high-dimensional regimes ($\beta \ge 2$), the max-$\ell_p$-margin interpolator can actually match the minimax optimal rates (the best possible rate any estimator could achieve) up to logarithmic factors.
- Rate Exponents: The chart below visualizes these "rate exponents." You can see the "V-shape" where the error exponent $\alpha$ reaches its lowest (best) point for moderate values of $p$.
Limitations and Future Work
- Gaussian Assumption: The proofs rely heavily on the features being Gaussian to use the CGMT. Generalizing this to broader distributions remains a challenge.
- Sparsity Pattern: The theory is presented for 1-sparse signals. While the authors discuss generalizations to $s$-sparse signals, the bounds become more complex and less tight.
- Non-linear Models: While preliminary CNTK experiments are promising, a full theoretical treatment of non-linear neural networks is still missing. The authors hypothesize that the depth of a network might act as a proxy for the strength of inductive bias, suggesting a "Goldilocks depth" for noisy data.
Summary updated