acceptodds
Under review as a conference paper at ICLR 2027

Benign Overfitting for General Norms and Distributions

Abstract

Understanding why predictors can generalize despite interpolating noisy training data is a central puzzle in machine learning. Most work on such "benign overfitting" studies minimum-2-norm linear regression, reflecting the inductive bias of gradient descent. However, modern optimizers such as Adam and Muon use non-Euclidean update geometries, favoring solutions associated with other norms. Analyzing regression for non-Euclidean norms is substantially more difficult, with known results essentially limited to Gaussians. In this paper, we develop a method to analyze benign overfitting in linear regression for general norms and general (sub-Gaussian) distributions. As a special case, we prove that minimum-p-norm interpolation with p>1 can benignly overfit even for non-Gaussian distributions, under suitable conditions. Perhaps surprisingly, for the 1-norm, benign overfitting does not hold in general for well-behaved (but non-Gaussian) distributions, showing that existing positive 1-norm results rely crucially on Gaussianity. Our proof analyzes the geometry of the dual optimization problem, using concentration and central limit tools to show it is approximately Euclidean in many high-dimensional cases.

Primary area:
learning theory
Keywords:
Regression, Generalization, Benign Overfitting

Reviews

Among:
Shape:
1234this paper, Top 49%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.33 over 3 reviews, above 51% of the others.
Reviewer_7ZqjOpenReview ↗
Rating
2
Confidence
4
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper studies minimum-norm interpolation in overparameterized linear regression with independent sub-Gaussian input coordinates and independent sub-Gaussian observation noise. Theorem 1 gives sufficient conditions for benign overfitting for ℓp\ell_p norms with p∈(1,∞]p\in(1,\infty], and Theorem 3 formulates an extension to general norms under assumptions on the expected dual geometry and its concentration. The positive argument approximates the residual interpolation cost by a Euclidean norm, using a quantitative central limit theorem on flat dual vectors together with truncation and uniform concentration. Theorem 2 gives a scaled-Rademacher example in which every minimum-ℓ1\ell_1 interpolator has excess risk Ω(σ2log⁡n)\Omega(\sigma^2\log n) with constant probability. The question is relevant, but the contribution needs to be distinguished more carefully from existing geometric analyses. In particular, the positive result does not recover known isotropic consistency regimes, and the negative result is a specific cube-based construction rather than a general characterization of non-Gaussian minimum-ℓ1\ell_1 interpolation.

Critical strengths

The paper provides an identifiable route beyond Gaussian designs: the dual optimizer need not be flat, so a fixed-direction central limit theorem alone is insufficient. Combining the expected-norm truncation argument in Lemma 3 with flat-vector approximation and uniform concentration addresses this obstacle. This is the most interesting methodological ingredient to me. The treatment of independent sub-Gaussian observation noise, anisotropic designs, and p>2p>2, including p=∞p=\infty, extends the scope of earlier results in useful directions. These extensions should not be confused with sharper statistical guarantees, but they are genuine strengths. The ℓ1\ell_1 counterexample has a transparent mechanism and applies to every minimum-norm solution, rather than relying on an unfavorable choice among multiple minimizers. The proof sketches in Section 4 are also helpful for understanding the positive argument.

Critical weaknesses

1. The main text does not adequately distinguish the contribution from existing non-Gaussian and geometric results

The abstract describes existing results for non-Euclidean norms as “essentially limited to Gaussian distributions.” However, the published ICML 2024 paper by Kur, Abdalla, Bizeul, and Yang [1] already develops a Banach-space geometric framework and establishes sharp bounds for the noise-effect term in ℓp\ell_p regression under sub-Gaussian covariates. The subsequent Kur–Bizeul manuscript [2] provides a more extensive treatment, including localized bounds for the structural-error term.

The submission acknowledges both papers and explicitly describes their bounds as sharp in Appendix A, page 16. My concern is therefore not the absence of a citation, but the lack of a substantive comparison in the main text. The introduction should distinguish what was already established from what is new here: the present work allows broader distributional assumptions and covers p>2p > 2, but its sufficient conditions do not recover some existing guarantees under common assumptions. This tradeoff is important for assessing the contribution and should not be left implicit.

2. The positive bound fails to recover consistency, not merely sharp rates, in an important common setting

Let m=∣N∣m=|N|, and consider S=1S=\\{1\\}, w⋆=e1w^\star=e_1, isotropic covariates with unit coordinate variances, and a fixed positive observation-noise variance. For 1<p<21 < p < 2, the dual exponent satisfies q>2q > 2. Specializing equation (1) to sN=1s_N=1 gives the incompatible requirements

m2/q≪n≪m2/q.m^{2/q}\ll n\ll m^{2/q}.

Thus, the stated sufficient conditions do not recover isotropic benign overfitting even in this basic one-sparse-signal setting.

For a concrete non-Gaussian comparison, take

Xij∼i.i.d.Unif⁡[−3,3],ξ∼N(0,In),w⋆=e1,X_{ij}\overset{\mathrm{i.i.d.}}{\sim} \operatorname{Unif}[-\sqrt{3},\sqrt{3}], \qquad \xi\sim N(0,I_n), \qquad w^\star=e_1,

with ξ\xi independent of XX, and choose p=3/2p=3/2, q=3q=3, and d=⌈n5/4⌉d=\lceil n^{5/4}\rceil. Specializing Corollary 1 and Theorem 4 of [2] to this setting gives

T1=O~!(dn3/2),T2=O!(nd),T_1=\widetilde{O}\\!\left(\frac{d}{n^{3/2}}\right), \qquad T_2=O\\!\left(\frac{n}{d}\right),

and therefore

E,R(w^)=T1+T2=O~(n−1/4).\mathbb{E} \\,\mathcal{R}(\widehat{w}) = T_1+T_2 = \widetilde{O}(n^{-1/4}) .

In contrast, setting δ=n−2\delta=n^{-2} in the present Theorem 1 yields the term

nlog⁡(nm/δ)m2/3≍n1/6log⁡n.\frac{n\log(nm/\delta)}{m^{2/3}} \asymp n^{1/6}\log n.

Consequently, the theorem's smallness prerequisite fails. This is a limitation of the guarantee, not evidence that the estimator itself is inconsistent. Nevertheless, the gap is more substantial than a nonoptimal rate: the bound does not establish consistency in a setting where consistency is already known.

One source of this loss is visible in Section 4.1, page 6. For p<2p < 2, the proof controls the noise-fitting coefficients through the global inequality

∣w^N∣22≤∣w^N∣p2,\\|\widehat{w}_N\\|_2^2 \le \\|\widehat{w}_N\\|_p^2,

leading to a noise-block risk estimate of order σ2n/m2/q\sigma^2 n/m^{2/q}. Although the inequality is correct, it does not exploit sufficient structure of the selected interpolator to recover the sharper behavior. The paper should explain this limitation through a direct comparison under common assumptions; listing differences in the admissible distribution classes does not address it.

3. The relationship to the existing quotient-body framework should be made explicit

For a noise-block unit ball KNK_N, define

QN:=XNKN,JN(r):=inf⁡XNu=r∣u∣KN.Q_N:=X_NK_N, \qquad J_N(r):=\inf_{X_Nu=r}\\|u\\|_{K_N}.

For a feasible residual rr, standard convex duality gives

JN(r)=∣r∣QN=sup⁡∣XN⊤λ∣KN∘≤1⟨r,λ⟩.J_N(r) = \\|r\\|_{Q_N} = \sup_{\\|X_N^\top\lambda\\|_{K_N^\circ}\le1} \langle r,\lambda\rangle.

The dual feasible set in Section 4 is therefore exactly the polar of the projected norm ball. The dual formulation and the quotient-norm formulation describe the same residual interpolation cost, rather than different underlying geometric objects.

The connection also extends to the variational comparison between fitting the signal and fitting the residual. In the ℓp\ell_p case, with finite pp, KN=BpmK_N=B_p^m, S=1S=\\{1\\}, and w⋆=e1w^\star=e_1, write

w=(1−δ)e1+u,u1=0.w=(1-\delta)e_1+u, \qquad u_1=0.

The interpolation constraint becomes XNuN=ξ+δX1X_Nu_N=\xi+\delta X_1, and the optimization reduces exactly to

\min_{\delta\in\mathbb{R}} \left\\{ |1-\delta|^p + J_N(\xi+\delta X_1)^p \right\\}.

This is the same scalar comparison between signal shrinkage and shifted-noise interpolation cost that appears in the localized quotient-norm formulation of [2, Section 6.1.2].

These identities are standard, and their equivalence does not imply that the complete proofs are identical. In particular, the flat-vector central limit theorem and truncation argument are meaningful distinguishing ingredients. The paper should explicitly identify those ingredients and explain their relationship to the existing geometric framework, rather than leaving the methodological comparison implicit.

4. The ℓ1\ell_1 counterexample has a transparent but elementary geometric mechanism, and its scope should be stated carefully

On the event that every sign pattern appears among the noise-block columns, the construction gives the exact identities

XNB1m=sNB∞n,JN(r)=∣r∣∞sN.X_NB_1^m=s_NB_\infty^n, \qquad J_N(r)=\frac{\\|r\\|_\infty}{s_N}.

The full image is consequently a cube with an additional pair of antipodal vertices:

XB1d=conv⁡!(sNB∞n∪±X1).XB_1^d = \operatorname{conv}\\!\left( s_NB_\infty^n\cup\\{\pm X_1\\} \right).

Since w⋆=0w^\star=0, the first coefficient minimizes

∣t∣+sN−1∣ξ−tX1∣∞.|t|+s_N^{-1}\\|\xi-tX_1\\|_\infty.

For sN<1s_N < 1, the elementary midrange calculation in Appendix E yields

w^1=max⁡i(Xi1ξi)+min⁡i(Xi1ξi)2.\widehat{w}_1 = \frac{ \max_i(X_{i1}\xi_i)+\min_i(X_{i1}\xi_i) }{2}.

The remaining statistical step is to choose an nn-dependent noise distribution with a rare magnitude of order σlog⁡n\sigma\sqrt{\log n} occurring with probability 1/n1/n. With constant probability, exactly one observation has this larger magnitude, producing the stated risk lower bound.

This is a valid and transparent counterexample, and simplicity is not itself a weakness. However, the argument does not require a new random-polytope estimate beyond ensuring that all cube vertices are sampled. Moreover, the cube identity alone does not imply the stated divergence: the distinguished higher-variance coordinate and the particular noise distribution are also essential to this proof.

The statistical interpretation should reflect these restrictions. The construction requires exponentially many coordinates and does not establish the same conclusion for polynomial-dimensional Rademacher designs or for standard Gaussian observation noise. It demonstrates a failure of uniform extension to the specified sub-Gaussian class, rather than a general characterization of non-Gaussian ℓ1\ell_1 interpolation.

Relatedly, the statement after equation (1) that the worsening dimension condition as p↓1p\downarrow1 is not a proof artifact needs qualification. A counterexample at p=1p=1 does not establish the necessity or sharpness of the particular sufficient dimension condition for finite p>1p > 1.

5. The p>2p > 2 and general-norm extensions need a more explicit interpretation

For a one-dimensional, unit-variance signal block and fixed remaining parameters, the sufficient conditions for fixed p>2p > 2 include

sN2m2−2/pn⟶0,nlog⁡(nm)m⟶0.\frac{s_N^2m^{2-2/p}}{n}\longrightarrow0, \qquad \frac{n\log(nm)}{m}\longrightarrow0.

These conditions require the variance of each noise-fitting coordinate to vanish relative to the signal-coordinate variance. They do not provide an isotropic consistency guarantee.

The conditions are nevertheless nonvacuous. For example,

p=4,m≍n3/2,sN2=1mp=4, \qquad m\asymp n^{3/2}, \qquad s_N^2=\frac{1}{m}

satisfy them while keeping

tr⁡(ΣN)=msN2=1.\operatorname{tr}(\Sigma_N)=ms_N^2=1.

Thus, the relevant limitation is not that the result is empty, but that it establishes consistency in an anisotropic regime where the covariance favors the signal coordinates. The paper should describe this contribution as a non-Gaussian extension in that regime, rather than leave its relationship to isotropic guarantees or sharp characterizations unclear.

Similarly, Theorem 3 provides an abstract sufficient-condition framework for general norms. Verifying its assumptions on the expected dual geometry and uniform concentration constitutes a substantial part of applying the theorem. The paper carries out this verification quantitatively for ℓp\ell_p norms, but should distinguish the abstract generality of the theorem from explicit statistical guarantees for additional norm families.

Questions for authors

I would be happy if the authors would address the bullets in the weaknesses, after addressing those and the ones of the other reviewers. I would gladly consider the increase the score of this work.

3 comments
AuthorsOpenReview ↗

Rebuttal to Reviewer 7Zqj

We thank the reviewer for the constructive and insightful feedback. Below, we address the reviewer’s concerns. If any concerns remain that prevent the reviewer from raising their score, please let us know.

  • Relation to prior work: We agree that Kur et al. (2024) and Kur–Bizeul (2026) should be discussed more prominently in the introduction. Their work provides sharper guarantees for 1<p≤21<p\leq2 in important isotropic sub-Gaussian settings, but they do not cover the regime p>2p>2 as we do in our paper. Our results are in some sense complementary: their bounds are based on geometric properties that do not hold for many common norms (e.g. ℓp\ell_p with p>2p > 2) but do cover isotropic designs when 1<p<21<p<2, whereas ours are intentionally based on more general uniform concentration and CLT arguments, making them applicable to more general norms under suitable assumptions. We will clarify these differences and the tradeoffs in the paper.

  • Isotropic consistency and quantitative sharpness: Indeed our sufficient conditions do not recover known consistency guarantees for isotropic designs when 1<p<21<p<2. The inequality ∥w^N∥2≤∥w^N∥p\lVert \widehat w_N \rVert_2\leq \lVert \widehat w_N\rVert_p that the reviewer mentioned is indeed loose in this regime. Our aim was to provide a framework that would be generally applicable, but case by case improvements are reserved for future work.

  • Relationship to quotient-body geometry: Indeed there is a strong relationship with the quotient-body framework, and we are not the first to analyze linear regression through the dual objective. The main technical contribution is the quantitative approximation of the dual objective by Euclidean geometry under non-Gaussian inputs, including the challenge that the dual optimizer need not be flat. Our CLT, truncation, and uniform concentration arguments address this challenge. We will explain the relationship to the existing geometric framework more clearly.

  • The ℓ1\ell_1 counterexample: We agree that the construction exploits a particularly tractable cube geometry, and that our counterexample does not establish the necessity of the dimensional requirements in our positive results as p→1p\to 1, and will clarify this distinction. The main point of the result is the statistical separation from p>1p>1: even under assumptions that suffice to prove benign overfitting when p>1p>1, every minimum-ℓ1\ell_1 interpolator can have diverging risk. The example is also chosen to cleanly illustrate the geometric differences. Although our construction requires exponentially many coordinates, this is also a regime where Gaussian-design minimum-ℓ1\ell_1 interpolation is known to benignly overfit (Koehler et al., 2021, e.g., d=⌈en2⌉d=\lceil e^{n^2}\rceil with the same covariance structure), demonstrating that the exponential dimensionality alone does not explain the failure. We will clarify the relevant discussions in the paper and the relation to the dimensional dependencies in the positive results, as you suggested.

  • The p>2p>2 and general-norm results: We agree that our explicit p>2p>2 consistency guarantees concern anisotropic distributions, and do not establish isotropic consistency. Nevertheless, as you mentioned, this is a meaningful extension beyond existing work, which does not establish benign overfitting for p>2p>2 under non-Gaussian distributions. Moreover, anisotropy is a natural condition in this context: even for isotropic Gaussian inputs, minimum-ℓ2\ell_2-norm interpolation is inconsistent for fixed nonzero targets when d/n→∞d/n \to \infty, since

=\left(1-\frac nd\right)\lVert w^\star\rVert_2^2 +\frac{\sigma^2 n}{d-n-1}.$$ Thus, the bias approaches $\lVert w^\star\rVert_2^2$, so the risk does not approach $0$. Regarding general norms, Theorem 3 indeed provides a conditional framework whose assumptions we explicitly verify for the $\ell_p$ family.

Thank you for the detailed response. I appreciate your acknowledgment of the concerns raised in the reviews. However, I remain concerned that the current manuscript overstates the scope of the results and does not clearly communicate the tradeoffs with prior work. I would therefore like to see a revised manuscript during the discussion period, with the substantive changes clearly indicated. I find it a bit surprising that with LLMs those overlaps did not appear before the submission of this manuscript and were ``hidden'' in the appendix.

  1. Positioning and prior work. Please revise the abstract and introduction to acknowledge the existing non-Gaussian results for 1<p≤21<p\leq 2 and explain precisely what your work adds. The current characterization of prior results as essentially limited to Gaussian distributions is misleading. The main text should clearly state the assumptions and regimes in which your guarantees establish benign overfitting.

  2. Loss of sharpness and distributional assumptions. Please explain in the main text where the analysis loses sharpness relative to existing results. As you acknowledge, the issue extends beyond suboptimal rates: your sufficient conditions do not recover known consistency guarantees for isotropic designs when 1<p<21<p<2.

  3. Relationship to existing proof approaches. Please make the connection to the quotient-body framework and the geometric ideas underlying earlier Gaussian analyses, including the work of Koehler et al. (2021), more explicit. The CLT, truncation, and uniform concentration arguments are meaningful technical contributions. Their novelty should be explained in the context of these existing approaches.

  4. Scope of the ℓ1\ell_1 counterexample. I understand the conceptual value of separating Gaussian and non-Gaussian behavior. Nevertheless, I still find the relevance of this example to standard statistical settings limited, given the exponentially large dimension and the particular sample-size-dependent noise distribution. Please state these restrictions prominently and make clear which conclusions the construction supports.

  5. Interpretation of the p>2p>2 results. I agree that the extension to non-Gaussian designs for p>2p>2 is novel. However, the manuscript should state more prominently that the sufficient conditions require a strong variance separation between the signal and noise-fitting coordinates. Please discuss whether some degree of anisotropy is intrinsic to the problem, particularly for p=∞p=\infty, and distinguish this from the necessity of the specific quantitative conditions imposed by your analysis.

I still believe the paper has sufficient merit for ICLR, provided that the presentation accurately reflects these qualifications. I would be happy to reconsider my score after reviewing a revised manuscript that addresses these points and the other reviewers.

Thanks for the careful follow-up. We uploaded a revised manuscript in which all substantive changes are marked in red. We agree that the comparison with prior non-Gaussian work belonged in the main text rather than the appendix. Below we summarize how each point is addressed.

1. Positioning and prior work. The abstract now states that non-Gaussian results are known for 1<p≤21<p\le2, while results for p>2p>2 remain largely limited to Gaussian designs. The related-work discussion has moved from the appendix into the introduction, where we state that Kur et al. (2024) and Kur–Bizeul (2026) give sharper guarantees for 1<p≤21<p\le2 under isotropic sub-Gaussian designs and Gaussian noise. What our work adds is: (i) p>2p>2, including p=∞p=\infty, for non-Gaussian designs; (ii) anisotropic designs and sub-Gaussian label noise; and (iii) a general-norm framework, which is conditional on Assumptions 3–4 and verified here for the ℓp\ell_p family (as now stated after Corollary 2). The first contribution bullet now states explicitly that our guarantees concern anisotropic regimes.

2. Loss of sharpness. Sec. 3 now states that for 1<p<21<p<2 our sufficient conditions do not recover known isotropic consistency regimes, and Sec. 4.1 identifies where this happens. With sN≍1s_N\asymp1, the two conditions in (1) become ∣N∣2/q≪n≪∣N∣2/q|N|^{2/q}\ll n\ll|N|^{2/q}, which are incompatible, although consistency is known there (e.g., your example with p=3/2p=3/2 and d≍n5/4d\asymp n^{5/4}). The loss occurs in the noise-block step: we bound ∥w^N∥2≤∥w^N∥p\lVert\widehat w_N\rVert_2\le\lVert\widehat w_N\rVert_p, which is tight only for sparse vectors, whereas for delocalized vectors ∥v∥2≈∣N∣1/2−1/p∥v∥p\lVert v\rVert_2\approx|N|^{1/2-1/p}\lVert v\rVert_p. If w^N\widehat w_N were delocalized, the noise-block term would be of order n/∣N∣n/|N| rather than n/∣N∣2/qn/|N|^{2/q}, and the two conditions would become compatible. Our dual argument controls ∥w^N∥p\lVert\widehat w_N\rVert_p but not the delocalization of w^N\widehat w_N, so it cannot recover these regimes.

3. Relationship to existing proof approaches. Sec. 4.1 now states that the dual feasible set is the polar of the quotient body XNBp,NX_NB_{p,N}, and that our decomposition (2) is the same comparison between signal shrinkage and residual-interpolation cost as in Koehler et al. (2021) and the localized quotient-norm analysis of Kur–Bizeul (2026). What differs is how the residual cost is approximated. For Gaussian designs, rotational invariance gives E∥XN⊤λ∥q=κN∥λ∥2\mathbb E\lVert X_N^\top\lambda\rVert_q=\kappa_N\lVert\lambda\rVert_2 for every λ\lambda. For non-Gaussian designs this holds only approximately and for flat λ\lambda, via a quantitative CLT, while the dual optimizer need not be flat. The revision now explains the truncation lemma and uniform concentration bound that bridge this gap in this context.

4. Scope of the ℓ1\ell_1 counterexample. The abstract, introduction, and Sec. 5 now state these restrictions explicitly. The construction uses exponentially many coordinates and an nn-dependent noise law (with uniformly bounded sub-Gaussian norm). It does not establish failure at polynomial dimension or for a fixed noise distribution such as Gaussian noise. Its conclusion is that Gaussian-design ℓ1\ell_1 guarantees do not extend uniformly to sub-Gaussians, not a characterization of non-Gaussian ℓ1\ell_1 interpolation. We also removed the claim that our dimension condition is "not an artifact", and now state that the example does not establish its necessity for any finite p>1p>1.

5. Interpretation of the p>2p>2 results. The introduction and Sec. 3 now state that our guarantees require the noise-fitting variances to be much smaller than the signal variances. Sec. 3 also explains why some anisotropy is intrinsic for p≥2p\ge2, including p=∞p=\infty, and separates this from our specific quantitative conditions. Write tN=n/κNt_N=\sqrt n/\kappa_N. Informally, in the regime where our dual approximation holds, the minimum-ℓp\ell_p-norm problem reduces to min⁡wS∥wS∥pp+tNp(σ2+∥ΣS1/2(wS−wS⋆)∥22)p/2.\min_{w_S}\lVert w_S\rVert_p^p+t_N^p\left(\sigma^2+\lVert\Sigma_S^{1/2}(w_S-w_S^\star)\rVert_2^2\right)^{p/2}. Unless tNt_N is large, the minimizer is shrunk away from wS⋆≠0w_S^\star\ne0 by a non-vanishing amount, so the bias does not vanish. Thus n≳κN2≍sN2∣N∣2/qn\gtrsim\kappa_N^2\asymp s_N^2|N|^{2/q}, the first condition in (1), is needed up to constants. For p≥2p\ge2 we have 2/q≥12/q\ge1, so with ∣N∣≫n|N|\gg n this forces sN2≪n/∣N∣s_N^2\ll n/|N|. For p=2p=2 this matches the exact isotropic Gaussian bias (1−n/d)∥w⋆∥22(1-n/d)\lVert w^\star\rVert_2^2. For p=∞p=\infty with isotropic coordinates, tN≍n/∣N∣→0t_N\asymp\sqrt n/|N|\to0, so the interpolator fits even the signal through the noise-fitting coordinates and w^S→0\widehat w_S\to0. Some variance separation is therefore intrinsic for p≥2p\ge2. By contrast, we do not claim that the second condition, n≪∣N∣min⁡{2/q,1}n\ll|N|^{\min\lbrace 2/q,1\rbrace}, or the logarithmic factors are necessary; for 1<p<21<p<2 the second condition is precisely where our analysis is loose (point 2).

We hope these revisions address your concerns.

Reviewer_5P7EOpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

The paper studies benign overfitting of minimum-norm interpolators in overparameterized linear regression beyond Gaussian designs. It establishes high-probability excess-risk bounds and sufficient conditions for consistency of minimum-ℓp\ell_p-norm interpolation for 1<p≤∞1<p\leq\infty, assuming independent sub-Gaussian input coordinates and independent sub-Gaussian noise. It also provides an abstract extension to general norms under suitable conditions on the expected dual norm and its uniform concentration. Conversely, it constructs a scaled Rademacher design with exponentially large dimension and sample-size-dependent sub-Gaussian noise for which minimum-ℓ1\ell_1 interpolation has excess risk of order at least σ2log⁡n\sigma^2\log n with constant probability.

The main methodological contribution combines convex duality, quantitative Gaussian approximation on flat directions, truncation of dual vectors, and uniform concentration to relate the interpolation problem to Euclidean residual minimization. Validation is primarily theoretical, through finite-sample bounds, asymptotic consistency results, and the explicit counterexample. Synthetic illustrations complement the analysis.

Critical strengths
  1. An extension beyond Gaussian designs, supported by a useful proof strategy. The paper establishes benign-overfitting guarantees for minimum-ℓp\ell_p-norm interpolation throughout 1<p≤∞1<p\leq\infty under independent sub-Gaussian coordinates and noise. The combination of duality, Gaussian approximation on flat directions, and dual truncation addresses a genuine obstacle to extending Gaussian analyses. In particular, the coverage of p>2p>2, including p=∞p=\infty, and the abstract general-norm formulation make this a meaningful methodological contribution rather than merely a change in distributional assumptions.

  2. A counterexample that clarifies the limits of distributional universality. The minimum-ℓ1\ell_1 failure construction shows that covariance and sub-Gaussian tail control alone cannot guarantee the benign behavior established under Gaussian designs. Its geometric explanation—noise fitting induces a maximal-residual objective rather than an approximately Euclidean one—provides insight into why the distribution matters. Despite the construction’s restrictive dimensional and noise requirements, this is a consequential conceptual result that complements the positive theory and strengthens the paper’s contribution.

Critical weaknesses
  1. The concrete scope of the general-norm framework remains limited. Theorem 3 requires approximate Euclidean behavior of the expected dual norm on flat directions and uniform concentration, but these conditions are verified only for the ℓp\ell_p family. The distributional extension also retains coordinate independence, which excludes many correlated feature models. Since earlier work already treats some non-Gaussian settings for 1<p≤21<p\leq2, an application to a substantially different norm would more convincingly establish the broader reach of the framework. This limits the demonstrated impact of the general-norm contribution.

  2. The results leave the quantitative boundary of benign overfitting unresolved. The positive results give sufficient conditions with potentially loose rates, while the negative result concerns p=1p=1, exponentially large dimension, and a sample-size-dependent noise distribution. Consequently, the counterexample does not establish that the increasingly restrictive dimensional requirements as p↓1p\downarrow1 are necessary, nor does it resolve failure under more conventional dimensional scalings and fixed noise distributions. This gap limits how sharply the paper answers when non-Euclidean interpolation benignly overfits.

Questions for authors
  1. The Gaussian comparison requires a stronger dimensional condition (p. 7, lines 370–372). The cited consistency criterion of Koehler et al. requires n/log⁡∣N∣→0n/\log |N|\to0, whereas Theorem 2 assumes only d>2n2nd>2n2^n. The latter permits log⁡d≍n\log d\asymp n, so the cited result does not establish Gaussian consistency throughout this range. The authors should specify a common regime in which the comparison holds, such as d=⌈en2⌉d=\lceil e^{n^2}\rceil.
  2. The informal consistency conditions omit logarithmic requirements (p. 9, following equation (17)). The claim that n≪∣N∣min⁡2/q,1n\ll |N|^{\min{2/q,1}} and rS≪nr_S\ll n imply εflat→0\varepsilon_{\mathrm{flat}}\to0 is not justified by the displayed concentration bounds without additional logarithmic conditions. Corollary 1 includes these factors correctly; the subsequent discussion should retain them or explicitly qualify its scaling statements.
  3. The endpoint counterexample does not establish quantitative sharpness near p=1p=1 (p. 4, lines 204–206). Failure at p=1p=1 shows that this endpoint cannot generally be included in the positive result. It does not establish that the dimensional requirement n≪∣N∣2/qn\ll |N|^{2/q} is necessary for 1<p<21<p<2, or that its deterioration as p↓1p\downarrow1 is unavoidable. The interpretation should be narrowed accordingly.
2 comments
AuthorsOpenReview ↗

Rebuttal to Reviewer 5P7E

We thank the reviewer for the thoughtful assessment and helpful suggestions.

  • Scope of the general-norm framework: Indeed the explicit verification of Theorem 3 is currently for ℓp\ell_p norms. The purpose of the general-norm formulation is to isolate the geometric and concentration properties needed for our analysis, separating them from the remainder of the proof, which is norm-independent. We believe this provides a useful framework for studying other norms, although verifying these properties requires additional work. Our concrete contribution is the analysis of the full ℓp\ell_p family under independent, potentially non-identically distributed sub-Gaussian designs, including regimes not covered by previous results. We will clarify the distinction between the general framework and its established applications, as well as the current restriction to independent coordinates.

  • Sharpness and the ℓ1\ell_1 endpoint: We agree that our ℓ1\ell_1 counterexample does not establish the necessity of the dimensional sharpness of our upper bounds as p→1p\to1. Its purpose is to demonstrate that benign overfitting for ℓ1\ell_1 cannot be guaranteed under the same distributional assumptions as our positive results. We will clarify this and more explicitly acknowledge the particular dimensional and noise assumptions of the construction.

  • Gaussian comparison: We agree with the reviewer that we should emphasize a regime where the assumptions of Koehler et al. hold, such as d=⌈en2⌉d=\lceil e^{n^2}\rceil, to establish a direct comparison between Gaussian and non-Gaussian covariates under the same covariance and noise distribution. Our theory already captures this, and we will make this common comparison regime explicit.

  • Logarithmic factors: Indeed, the informal discussion following the corollary omits logarithmic requirements needed for εflat→0\varepsilon_{\mathrm{flat}}\to0, and we will clarify the discussion.

Reviewer_5P7EOpenReview ↗

response to authors

Thank you for the rebuttal and the proposed revisions.

The fixed p>2p>2 results, including ℓ∞\ell_\infty, establish consistency in a different anisotropic regime under independent sub-Gaussian designs. I give that result and the truncation argument enough weight for weak acceptance.

Reviewer_4k4xOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper studied the benign overfitting for general norm with independent sub-Gaussian coordinates. It establishes sufficient conditions for minimum-ℓp\ell_p norm interpolation with fixed p>1p > 1, including p=∞p = \infty, and gives an extension to general norms. They also provided a construction to show that minimum-ℓ1\ell_1 interpolation can have diverging excess risk under a uniformly sub-Gaussian sequence of distributions. The results are supported by theoretical proofs, with a separate numerical illustration.

Critical strengths
  1. The dual truncation argument in Lemma 3 and Proposition 1 provides a substantive route from Gaussian to non-Gaussian designs: it works with nearly optimal flat dual vectors without requiring the original optimizer to be flat. Together with guarantees for all minimum-norm interpolators, including the potentially nonunique ℓ∞\ell_\infty case, these results have broad applicability.

  2. The ℓ1\ell_1 counterexample provides a concrete explanation for the failure through dual geometry and an explicit midpoint estimator. The contrast with fixed p>1p > 1 goes beyond establishing a lower bound and helps explain why the choice of norm matters.

Critical weaknesses
  1. The precise advance over existing non-Gaussian results is not sufficiently clear in the discussion of the main contributions. Appendix A already discusses relevant work by Kur et al. (2024), Kur and Bizeul (2026), and Chinot et al. (2022), while the abstract and introduction largely characterize prior non-ℓ2\ell_2 results as Gaussian. This distinction matters when assessing the significance of the contribution, particularly in terms of which norms, covariance structures, and noise assumptions are newly covered. This is a concern about the positioning of the paper, rather than a claim that the results are already known.

  2. The technical development is good, but I find the demonstrated scope of the contribution somewhat limited. The concrete positive results rely on independent covariate coordinates and a common-variance noise-fitting block, while the broader general-norm theorem remains conditional on additional geometric and concentration assumptions. A clearer explanation of which new settings the results address and what insights they provide beyond extending existing Gaussian analyses would help establish the significance of the contribution.

Questions for authors
  1. Assumption 1 requires independent covariate coordinates, which limits applicability to correlated features. Lines 148-149 mention that the analysis may extend to milder assumptions. Could you clarify which parts of the argument require coordinate independence, and whether any allow a weaker dependence structure, such as independent blocks of correlated coordinates? For ℓp\ell_p norms with p≠2p \ne 2, whitening generally changes the norm being minimized, so it does not directly extend the stated result to correlated designs. A discussion of the main obstacle and the scope of a possible relaxation would help assess this limitation; a new theorem is not necessary.

  2. Could you give a concise comparison with the non-Gaussian results discussed in Appendix A, specifying the norms, covariance and noise assumptions, and vanishing-risk regimes covered? In particular, which parts of the p>2p > 2 and anisotropic results are new relative to those works?

  3. Is there a specialization beyond the common-variance ℓp\ell_p example for which Assumptions 3 and 4 and the quantities κN\kappa_N, βS\beta_S, and βN,Σ\beta_{N,\Sigma} can be checked? An existing worked case with unequal variances or another norm would help establish the scope. If not, clarifying that the additional scope is conditional would address the concern; a new general theorem is not required.

  4. In lines 207-212, is the claimed match to necessary and sufficient ℓ2\ell_2 criteria intended only up to logarithmic factors? Corollary 1 requires nlog⁡(n∣N∣/δn)/∣N∣→0n\log(n|N|/\delta_n)/|N| \to 0 at p=2p = 2, whereas equation (1) displays n/∣N∣→0n/|N| \to 0. For example, ∣N∣=⌊nlog⁡log⁡n⌋|N| = \lfloor n\log\log n\rfloor separates these conditions. Please clarify whether the logarithms can be removed or the comparison should be qualified.

  5. Could you clarify how Figures 1 and 2 relate to the theoretical results? Figure 1 is briefly discussed in the introduction, but its coordinates xj=cos⁡(jz)/jx_j = \cos(jz)/j depend on the same scalar zz, so this example falls outside Assumption 1. Figure 2 illustrates the dual-geometric contrast discussed in Section 5. A short explanation distinguishing the motivating example in Figure 1 from the geometric illustration in Figure 2, and stating which observed behavior is covered by the theorems, would help readers interpret the figures.

3 comments
AuthorsOpenReview ↗

Rebuttal to Reviewer 4k4x

We thank the reviewer for their constructive feedback. Below, we address the reviewer’s concerns. If any concerns remain that prevent the reviewer from raising their score, please let us know.

  • Related Works: We agree that the distinction from Kur et al. (2024) and Kur–Bizeul (2026) deserves greater prominence in the main paper as opposed to the appendix. These works establish benign overfitting for ℓp\ell_p norms 1<p≤21<p\leq 2, but they do not cover the regime p>2p>2 as we do in our paper. This difference is fundamental: their bounds are based on geometric properties that do not hold for many common norms (e.g. ℓp\ell_p with p>2p > 2), whereas ours are intentionally based on more general uniform concentration and CLT arguments, making them applicable to more general norms. We emphasize that to our knowledge, no prior work covers p>2p>2 and non-Gaussian distributions. The closest work that addresses such norms is Koehler et al. (2021), but their results only apply to Gaussians. Regarding the covariance and noise assumptions, the explicit 1<p≤21 < p \leq 2 results of Kur et al. (2024) and Kur–Bizeul (2026) assume isotropic i.i.d. sub-Gaussian coordinates and Gaussian noise (although they discuss extensions), whereas ours allow independent, non-identically distributed sub-Gaussian coordinates, potentially unequal variances in the signal block and sub-Gaussian label noise. Regarding the bounds of Chinot et al. (2022), they do not actually prove benign overfitting, meaning they do not prove vanishing risk when there is label noise. We will make these distinctions explicit in the introduction.

  • Independent coordinates: Coordinate independence is primarily used to establish concentration of the empirical dual norm (Proposition 2) and to compare its expectation with Gaussian geometry (Lemma 13). We expect the analysis to extend to independent blocks of correlated coordinates of bounded size, by applying concentration across blocks instead of individual coordinates. This would introduce constants depending on block size and require using the block covariance in the risk bound. We will clarify these points and leave a formal extension for future work.

  • Theorem 3: Our Theorem 3 does allow for unequal coordinate variances. The choice of a common variance for the noise-fitting coordinates in the ℓp\ell_p specialization is for clarity, as even in the ℓ2\ell_2 case, the exact conditions on the variances that determine if benign overfitting occurs can become delicate. We will discuss this in the paper.

  • Comparison with ℓ2\ell_2 criteria: The reviewer is correct that our consistency conditions match the known criteria only up to logarithmic factors. We will clarify this in the relevant discussion.

  • Figures: Figure 1 is intended as a motivating illustration of the potentially different behavior of minimum-norm interpolators. The choice of distribution, where all coordinates depend on a scalar zz, was to make the visualization clear with a 2d plot. This means that the coordinates in this example are uncorrelated but not independent, so the example does not satisfy Assumption 1. Figure 2 illustrates the geometric mechanism underlying the ℓ1\ell_1 counterexample. Neither figure is intended as a direct numerical verification of the positive theorems. We will clarify this in the captions.

Thank you for the detailed response. I am satisfied with the response except that Q3 is not yet fully addressed. I understand that Theorem 3 allows unequal coordinate variances. My question was whether its conditions can be verified in a concrete setting beyond the common-variance example. Could you provide a short specialization with two variance levels in the noise-fitting block NN, showing how Assumptions 3 and 4 are checked and when the bound implies vanishing excess risk?

We thank the reviewer for this suggestion. Indeed, we can verify Assumptions 3 and 4 for two arbitrary variance levels under the same independent sub-Gaussian assumptions as Theorem 1. In fact, this holds for every fixed p∈(1,∞]p\in(1,\infty].

Specifically, let qq be the dual exponent of pp, and partition N=N1⊔N2N=N_1\sqcup N_2, with ∣N1∣=∣N2∣=m/2|N_1|=|N_2|=m/2. Suppose that xij=sNℓζijx_{ij}=s_{N_\ell}\zeta_{ij} for j∈Nℓj\in N_\ell, where the ζij\zeta_{ij} are independent, centered, variance-one, and uniformly sub-Gaussian. The scales sN1,sN2>0s_{N_1},s_{N_2}>0 are arbitrary, and need not have a bounded ratio. Write sks_k for the scale of coordinate k∈Nk\in N, s∗=max⁡{sN1,sN2}s_\ast=\max\lbrace s_{N_1},s_{N_2}\rbrace, and define

\qquad \kappa_N=\left(\mathbb E|G|^q\cdot W_q\right)^{1/q},$$ where $G\sim N(0,1)$. Note that $(m/2)^{1/q}s_\ast\le W_q^{1/q}\le m^{1/q}s_\ast$. The verification requires only minor changes to the existing lemmas in Appendix D: - **Lemma 13 (Assumption 3).** Replace the empirical moment $Z$ in its proof by $$Z=\frac{1}{W_q}\sum_{k\in N}s_k^q|b_{\lambda,k}|^q .$$ Since $$\frac{\sum_{k\in N}s_k^{2q}}{W_q^2}\le\frac2m,$$ Lemma 10, whose proof applies verbatim to weighted averages, still bounds the $q$-root bias by $O(m^{-1/(2q)})$. Lemma 12 applies without modification to each standardized coordinate, and averaging the Gaussian moment comparisons with weights $s_k^q/W_q$ preserves the $O(\lVert\lambda\rVert_\infty)$ error. The lower bound in Lemma 8 holds with $s_N m^{1/q}$ replaced by $s_\ast m^{1/q}/2$, since half the coordinates have scale $s_\ast$. Consequently, Assumption 3 holds with $A=\Omega_{q,R_X}(1)$ and $$\varphi(t)=O_{q,R_X}\left(t+m^{-1/(2q)}\right).$$ - **Lemma 11 and Proposition 2 (Assumption 4).** Replace $Y_k=|b_{\lambda,k}|^q$ by $Y_k=(s_k/s_\ast)^q|b_{\lambda,k}|^q$. These variables satisfy the same sub-Weibull bounds, and their average expectation remains bounded below since half the coordinates have scale $s_\ast$. Thus the fixed-vector concentration bound retains the same order. In Proposition 2, equations (52)--(55) are modified by replacing $s_N m^{1/q}$ with $W_q^{1/q}$ in the relevant Lipschitz and expectation bounds. These factors cancel after normalization, so the covering argument is unchanged. We obtain $$\varepsilon_{\mathrm{unif}}(\delta) =O_{q,R_X}\left( \sqrt{\frac{n\log(nm/\delta)}{m}} +\frac{\left(n\log(nm/\delta)\right)^{q/2}}{m} +m^{-1/(2q)} \right).$$ Finally, $\beta_S=|S|^{\max\lbrace 1/p-1/2,0\rbrace}$ as before, $\beta_{N,\Sigma}\asymp s_\ast m^{\max\lbrace 1/q-1/2,0\rbrace}$, and $\gamma_N\asymp s_\ast m^{1/q}/\sqrt n$, so $$\frac{\beta_{N,\Sigma}}{\gamma_N} \asymp\sqrt{\frac{n}{m^{\min\lbrace 2/q,1\rbrace}}}.$$ Thus, with a fixed-dimensional signal block and bounded target supported on it, Corollary 2 establishes vanishing excess risk whenever, for some $\delta_n\to0$, $$\frac{\left(n\log(nm/\delta_n)\right)^{\max\lbrace 1,q/2\rbrace}}{m}\to0, \qquad \frac{s_\ast m^{1/q}}{\sqrt n}\to0.$$ For example, these conditions hold with $m\asymp n^{\max\lbrace 2,q\rbrace}$ and $s_\ast=m^{-\max\lbrace 1/2,1/q\rbrace}$, irrespective of the ratio between the two variance levels. This example also has bounded covariance trace. We will add this specialization and the corresponding modifications to the appendix of the revised manuscript.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.