Pith. sign in

REVIEW 3 major objections 9 minor 300 references

Geometric proof recovers sharp risk bound for basis pursuit

Reviewed by Pith at T0; open to challenge. T0 means a machine referee read the full paper against a public rubric. the ladder, T0–T4 →

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

T0 review · glm-5.2

2026-07-09 01:54 UTC pith:5O5HWVVJ

load-bearing objection The geometric byproducts (Theorems 4–5, Corollary 2) are the real contribution; the statistical result (Theorem 3) recovers a known bound via a genuinely different method but has a real gap in its CGMT-independence claim. the 3 major comments →

arxiv 2607.07694 v1 pith:5O5HWVVJ submitted 2026-07-08 math.ST math.MGmath.PRstat.TH

Minimum Norm Interpolation via The Local Theory of Banach Spaces: The Role of Gaussianity

Gil Kur , Reese Pathak This is my paper
classification math.ST math.MGmath.PRstat.TH
keywords gaussianisotropicmathrmboundcgmtfirstfleurygeometry
verification ladder T0 review T1 audit T2 compute T3 formal T4 reserved

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

This paper rederives the sharp mean-squared error bound for the minimum ℓ₁-norm interpolator (basis pursuit) in overparameterized linear regression with isotropic Gaussian covariates, achieving the same rate as prior work but through an entirely different proof route. Where earlier analyses relied on the Convex Gaussian Min–Max Theorem (CGMT), a Gaussian comparison tool, the authors instead use the geometry of the symmetric Gaussian polytope — the convex hull of random Gaussian points — together with Fleury's exact characterization of how facets of this polytope are distributed. The central idea is that the ℓ₁-MNI solution lives on a facet of this polytope, and the statistical risk can be read off from the geometric properties of that facet: its height (distance from the origin), the shape of the simplex it forms, and the thin shell of typical radii. The paper decomposes the mean-squared error into shrinkage of the signal, orthogonal bias, and variance, and controls each term using tools from the local theory of Banach spaces — Dvoretzky-type theorems, Talagrand's L¹–L² inequality, and the KLS property of the canonical simplex. The main result (Theorem 3) shows that, for sparse ground truth and dimension d in a broad overparameterized regime, the squared ℓ₂ risk equals 1/log(d/n) + log log(d/n)/(2 log²(d/n)) + O(log(d/n)⁻²), matching the sharpest known bound. Along the way, the authors improve the estimate of the isotropic constant of the Gaussian symmetric polytope from a universal constant to 1 + O(log(d/n)⁻²) relative to the Euclidean ball, provide a refined thin-shell estimate, and give an elementary proof of Fleury's Poincaré inequality for these polytopes.

Core claim

The paper establishes that the sharp risk bound for the ℓ₁-minimum-norm interpolator can be obtained without Gaussian comparison inequalities, by instead exploiting the exact facet distribution of the symmetric Gaussian polytope (Fleury's distribution). The interpolator's solution lies on a random facet whose height, barycenter, and simplex geometry are sufficiently concentrated — thanks to the KLS property of the canonical simplex and determinant concentration of near-Gaussian matrices — that the ℓ₂-norm of the solution is pinned to 2M²_{n,d}/n + O(log(d/n)⁻²), where M_{n,d} is the expected gauge of the polytope. This yields the rate 1/log(d/n) + lower-order corrections, matching the best已知

What carries the argument

The proof combines: (1) Fleury's distribution for facets of the symmetric Gaussian polytope P_{n,d} = conv{±X_i}, which decomposes a typical facet into an independent height variable T_{n,d}, a near-Gaussian matrix Y, and a rotation; (2) the conic volume formula relating polytope volume to facet heights and areas; (3) Talagrand's L¹–L² inequality (via Cordero-Erausquin–Ledoux) to control the variance of the ℓ₁-MNI norm; (4) the KLS property of the canonical simplex to obtain thin-shell concentration; (5) a bootstrap argument iterating between volume estimates and facet-height concentration to tighten the polytope's radial containment; and (6) a facet-counting argument to reduce from nonzero-

Load-bearing premise

The proof of the main risk bound (Theorem 3) depends entirely on Fleury's 2012 exact characterization of the distribution of facets of the symmetric Gaussian polytope, which is specific to isotropic Gaussian covariates and has no known analogue for sub-Gaussian or heavier-tailed designs. If this distributional result were incorrect or required modification, the argument would collapse.

What would settle it

An error in Fleury's facet distribution theorem (Lemma 1), or a failure of the volume-biased Fleury transfer step that connects facet statistics to the MNI's behavior, would break the chain from polytope geometry to risk bound. In particular, the claim that the MNI ray hits a 'typical' facet with high probability (Lemma 21) is the load-bearing link between the polytope's facet distribution and the interpolator's risk.

Watch this falsifier — get emailed when new claim-graph text bears on it.

If this is right

  • The geometric proof route bypasses CGMT, suggesting that other interpolation problems previously analyzed only via Gaussian comparison may be tractable through high-dimensional convex geometry of random polytopes.
  • The improvement of the isotropic constant of P_{n,d} to 1 + O(log(d/n)⁻²) relative to the Euclidean ball provides a near-sharp geometric characterization of random Gaussian polytopes, which may inform thin-shell and KLS conjectures for random polytopes.
  • The facet-counting reduction from sparse signal to pure-noise (Step VII) provides a template for analyzing other minimum-norm interpolators where uniform convexity is unavailable, by controlling how many facets a perturbation can activate.
  • The open problems posed — a genuine (non-volume-weighted) thin-shell estimate and a KLS bound for P_{n,d} — if resolved, would yield cleaner proofs and potentially extend the framework to non-Gaussian designs.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The dependence on Fleury's exact facet distribution, which is specific to the isotropic Gaussian, suggests that the sharp 1/log(d/n) rate may genuinely require Gaussian structure, and that sub-Gaussian designs may only achieve O(1) risk through this geometric route — a distinction that CGMT-based proofs also struggled to overcome.
  • The bootstrap argument (iterating volume estimates against facet-height concentration until the exponent stabilizes at log⁻²(d/n)) may be a reusable technique for other random polytope problems where initial geometric bounds are too coarse.
  • If the KLS conjecture for the symmetric Gaussian polytope (Open Problem 2) were resolved affirmatively, the entire proof of Theorem 3 could likely be simplified, replacing the delicate facet-by-facet analysis with a direct Poincaré inequality on the polytope.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit.

Referee Report

3 major / 9 minor

Summary. The paper studies minimum-norm interpolation (MNI) in overparameterized linear regression with isotropic Gaussian covariates, focusing on the ℓ1-MNI (basis pursuit). The central result (Theorem 3) recovers the sharp MSE bound of Wang et al. [2022] using tools from high-dimensional convex geometry—specifically, Fleury's [2012] facet distribution for symmetric Gaussian polytopes, Gluskin's [1988] inradius bounds, and a variant of Talagrand's L1–L2 inequality (Cordero-Erausquin and Ledoux [2012])—rather than the convex Gaussian min–max theorem (CGMT). The paper also provides: Theorem 1, a localization principle for the shrinkage of the MNI when the unit ball is in isotropic position; Theorem 2, relating the variance of the ℓ1-MNI to its ℓ2-norm via the L1–L2 inequality; Theorem 4, sharpening the Klartag–Kozma [2009] isotropic constant bound for P_{n,d} to (1+O(log(d/n)^{-2}))L_{B_n}; Theorem 5, a volume-weighted thin-shell estimate; and Corollary 2, an elementary proof of Fleury's [2012] Poincaré inequality. The proofs are extensive, spanning Sections 5.1–5.5 with explicit error tracking and a bootstrapped volume argument (§5.3.6, Corollary 7).

Significance. The paper makes a genuine methodological contribution by providing a non-CGMT route to the sharp ℓ1-MNI risk bound, leveraging the local theory of Banach spaces and the geometry of Gaussian polytopes. The geometric byproducts—particularly the sharpened isotropic constant (Theorem 4), the thin-shell estimate (Theorem 5), and the elementary proof of Fleury's Poincaré inequality (Corollary 2)—are of independent interest to the convex geometry community. The volume bootstrap argument (§5.3.6) is a notable technical innovation. The paper provides falsifiable, explicit probability bounds and sharp asymptotic expansions (Corollary 1). However, the headline claim of 'avoiding CGMT' requires qualification (see Major Comments).

major comments (3)
  1. §1.4 (contribution iii) and Abstract: The paper claims that Theorem 3 recovers the sharp MSE bound 'without invoking Gaussian comparison inequalities or the CGMT.' However, the proof of Theorem 2—which is explicitly used in the proof of Theorem 3 at Step II (§5.3.3) to control the concentration of ‖ξ‖_n / E‖ξ‖_n—relies on the rate E‖ŵ_n‖²₂ ≍ 1/log(d/n) cited from Wang et al. [2022] (§5.2.1: 'where we used that Wang et al. [2022] implies n·E‖ŵ_n‖²₂ ≍ M²_{n,d}'). Since Wang et al. [2022] obtained this rate via CGMT, the proof of Theorem 3 is not fully independent of CGMT as stated. This gap appears fillable: the upper bound E‖ŵ_n‖²₂ ≤ M²_{n,d}/n follows from Cauchy–Schwarz (‖ŵ_n‖₂ ≤ ‖ŵ_n‖₁/√n, since ŵ_n has exactly n nonzero entries by Lemma 7) combined with the standard estimate M_{n,d} ≍ √(n/log(d/n)) (derivable from Gluskin [1988] and Dvoretzky's theorem, as in the paper's own Step I, §
  2. §5.3.3, Step II: The argument that 'the map ξ ↦ ‖ξ‖_n / E‖ξ‖_n is O(E‖ξ‖_n/√n)-Lipschitz' is used to convert volume bounds into solid-angle (directional) bounds via Theorem 2. The logical flow here is: Theorem 2 controls the variance of ‖ŵ_n‖₁, which then controls the Lipschitz constant of the radial function, which then feeds into the facet-selection argument. But Theorem 2's proof (§5.2.1) uses the rate E‖ŵ_n‖²₂ ≍ 1/log(d/n) from Wang et al. [2022] to identify the scale. If the authors replace this with the Cauchy–Schwarz upper bound and the Chinot et al. [2020] lower bound (both CGMT-free), they would obtain only the coarse rate E‖ŵ_n‖²₂ ≍ 1/log(d/n) rather than the sharp constant. The authors should verify that this coarse rate suffices for Theorem 2's conclusion (d²₀ ≲ 1/(n log²(d/n))), since Theorem 2 only needs the coarse identification E‖ŵ_n‖²₂ ≍ M²_{n,d}/n, not the sharp 2+o(1)·
  3. §5.3.5, Lemma 18: The statement claims that with probability at least 1−exp(−C·nL⁻²), ‖ξ − ‖ξ‖_n · c_F‖² = (1+O(L⁻¹))·M_{n,d}. The proof is deferred to 'below' but the argument as written in §5.3.5 is quite compressed, combining the height-selection (Lemma 21), the volume bootstrap (Corollary 7), and the thin-shell of the canonical simplex (Lemma 17). The key step—showing that the MNI ray ξ/‖ξ‖_n lands in the 'good' part of a typical facet—relies on the volume-to-angle conversion from §5.3.3, which in turn depends on Theorem 2. The authors should make explicit which quantitative bound on d²₀ (the deviation parameter from Theorem 2) is needed for the O(L⁻¹) error in Lemma 18, and verify that the coarse bound d²₀ ≲ 1/(nL²) (rather than any sharper estimate) is sufficient.
minor comments (9)
  1. §1.2.1: The Donoho–Tanner references [2009, 2010] are mentioned as connecting facets of P_{n,d} to ℓ1-MNI, but the specific connection (which facet property corresponds to which MNI property) is not spelled out. A sentence or two clarifying this would help readers from the statistics side.
  2. §2.1, Assumption 2: The polynomial tail assumption is stated for ∥P_H(ŵ_n)∥₂, but the exponent C₁ in log^{C₁}(d) is not specified even for the ℓp case. The remark says 'this assumption holds for the ℓp-norm, with an absolute constant,' but no reference or proof is given for this claim in the main text.
  3. §3.2: The notation L := L(n,d) = log(d/n) is introduced here but L is also used for the isotropic constant L_K (§2.3, Eq. 9). Consider using a different symbol (e.g., ℒ or L_{n,d}) for the log-ratio to avoid confusion.
  4. §5.3.1, Lemma 10: The statement references 'universal constants c₁, c₂, c₃ > 0' but the lower bound involves Var(‖ξ‖_{K°}/M*(K)) without specifying the measure (is it γ_d, i.e., Gaussian?). This should be clarified.
  5. §5.3.4, Lemma 15: The lower bound Pr(∥Z∥₂ ≤ (1−ε)E∥Z∥₂) ≥ exp(−c₂nε²) is stated but not used in the subsequent argument (only the upper bound is used in Lemma 16). Consider removing or marking as a remark.
  6. §5.4.12: The reduction to zero signal for sparse w⋆ is sketched but relies on a covering number argument (Eq. 2) that requires (s+1)log n ≤ c₀n/log²(d/n). This is consistent with the sparsity assumption ∥w⋆∥₀ ≲ n·log(d/n)^{−C} in Theorem 3, but the relationship between C and c₀ should be made explicit.
  7. References: The paper cites 'Kur and Bizeul [2026]' and 'Bizeul and Klartag [2025]' with arXiv numbers; please update with published references if available. Also, 'Fleury [2012]' is cited as 'B Fleury' in the reference list but 'Fleury [2012]' in text—please ensure consistency.
  8. §4.1: The discussion of sub-Gaussian extensions is valuable but somewhat terse. The key obstruction—that Dvoretzky's theorem in its sharpest form requires rotational invariance, yielding only a constant rather than 1+o(1) ratio—could be stated more prominently, perhaps as a formal remark.
  9. Typos: §5.2.1, Eq. (23): 'd·∥∇_{X₁}F∥²_{L²}' should likely be 'd·∥∇_{X₁}F∥²_{L²} · (1 + log(...))'. §5.3.6, Corollary 7, Eq. (1): the stopping condition 'nL²ε²_{n,d} ≳ nε_{n,d} + √(n/L)' has a dimensional inconsistency (nε vs. √(n/L)); please verify.

Simulated Author's Rebuttal

3 responses · 0 unresolved

We thank the referee for a careful reading and for identifying a genuine gap in our CGMT-independence claim. We agree that the proof of Theorem 2 currently cites a rate from Wang et al. [2022] (obtained via CGMT) to identify the scale of E||ŵ_n||_2^2, and that this should be replaced by a CGMT-free argument. As the referee observes, the needed bound follows from Cauchy-Schwarz and Gluskin's estimate. We will revise accordingly and verify that the coarse rate suffices downstream.

read point-by-point responses

  1. Referee: §1.4 (contribution iii) and Abstract: The paper claims that Theorem 3 recovers the sharp MSE bound 'without invoking Gaussian comparison inequalities or the CGMT.' However, the proof of Theorem 2—which is explicitly used in the proof of Theorem 3 at Step II (§5.3.3)—relies on the rate E||ŵ_n||_2^2 ≍ 1/log(d/n) cited from Wang et al. [2022]. Since Wang et al. [2022] obtained this rate via CGMT, the proof of Theorem 3 is not fully independent of CGMT as stated.

    Authors: The referee is correct, and we acknowledge this gap. In the current manuscript, the proof of Theorem 2 (§5.2.1) uses the identity n·E||ŵ_n||_2^2 ≍ M_{n,d}^2, citing Wang et al. [2022]. Since Wang et al. obtained this via CGMT, our CGMT-independence claim is not fully justified as stated. We will revise the proof to eliminate this dependency. Specifically, the upper bound E||ŵ_n||_2^2 ≤ M_{n,d}^2/n follows from Cauchy-Schwarz: since ŵ_n has exactly n nonzero entries (Lemma 7), ||ŵ_n||_2 ≤ ||ŵ_n||_1/√n, and taking expectations gives E||ŵ_n||_2^2 ≤ (E||ŵ_n||_1)^2/n = M_{n,d}^2/n. The lower bound E||ŵ_n||_2^2 ≥ M_{n,d}^2/n follows from Jensen's inequality (E||ŵ_n||_2^2 ≥ (E||ŵ_n||_1)^2/n), which is already noted in Remark 5. The scale M_{n,d} ≍ √(n/log(d/n)) is derived from Gluskin [1988] and Dvoretzky's theorem in our own Step I (§5.3.2, Lemma 14), without CGMT. Thus the identification E||ŵ_n||_2^2 ≍ 1/log(d/n) is obtainable entirely within our framework. We will rewrite §5.2.1 to make this self-contained and remove the citation to Wang et al. [2022] for this step. revision: yes

  2. Referee: §5.3.3, Step II: The argument that 'the map ξ ↦ ||ξ||_n / E||ξ||_n is O(E||ξ||_n/√n)-Lipschitz' is used to convert volume bounds into solid-angle bounds via Theorem 2. Theorem 2's proof uses the rate E||ŵ_n||_2^2 ≍ 1/log(d/n) from Wang et al. [2022] to identify the scale. If the authors replace this with the Cauchy-Schwarz upper bound and the Chinot et al. [2020] lower bound (both CGMT-free), they would obtain only the coarse rate. The authors should verify that this coarse rate suffices for Theorem 2's conclusion (d_0^2 ≲ 1/(n log^2(d/n))).

    Authors: We have verified that the coarse rate suffices. The conclusion of Theorem 2 is d_0^2 ≲ 1/(n log^2(d/n)), which requires only the identification E||ŵ_n||_2^2 ≍ M_{n,d}^2/n ≍ 1/log(d/n) — that is, matching up to absolute constants, not the sharp (2+o(1)) constant. As explained in our response to the first comment, this coarse identification follows from Cauchy-Schwarz (upper bound) and Jensen (lower bound), combined with M_{n,d} ≍ √(n/log(d/n)) from our own Step I. The sharp constant 2+o(1) appears only in Theorem 3, not in Theorem 2. The downstream usage in §5.3.3 (Step II) requires only the coarse bound d_0^2 ≲ 1/(nL^2) to control the Lipschitz constant of the radial map and hence the volume-to-angle conversion. We will add an explicit remark in the revised manuscript clarifying that Theorem 2 uses only the coarse scale, not the sharp constant. revision: yes

  3. Referee: §5.3.5, Lemma 18: The statement claims that with probability at least 1−exp(−C·nL^{-2}), ||ξ − ||ξ||_n · c_F||^2 = (1+O(L^{-1}))·M_{n,d}. The proof is deferred but the argument as written in §5.3.5 is quite compressed. The authors should make explicit which quantitative bound on d_0^2 is needed for the O(L^{-1}) error in Lemma 18, and verify that the coarse bound d_0^2 ≲ 1/(nL^2) (rather than any sharper estimate) is sufficient.

    Authors: We will expand the proof of Lemma 18 in the revised manuscript. The quantitative input needed is precisely the coarse bound d_0^2 ≲ 1/(nL^2) from Theorem 2. Here is the chain: Theorem 2 controls Var(||ŵ_n||_1) / (E||ŵ_n||_1)^2 ≤ d_0^2, which bounds the relative fluctuation of ||ξ||_n = ||ŵ_n||_1. This relative fluctuation enters the Lipschitz constant of the radial map ξ ↦ ||ξ||_n / E||ξ||_n in §5.3.3, which is O(E||ξ||_n/√n) = O(M_{n,d}/√n) = O(1/√L). The volume-to-angle conversion (Corollary 6) then requires that the radial fluctuation be at most O(L^{-1/2}), which is satisfied since M_{n,d}/√n ≍ 1/√L. The O(L^{-1}) error in Lemma 18 arises from combining: (i) the height-selection from Lemma 21 (error O(L^{-5/4}), which is o(L^{-1})), (ii) the volume bootstrap from Corollary 7 (error O(L^{-2})), and (iii) the thin-shell of the canonical simplex from Lemma 17 (error O(1/√n), negligible). The dominant error term is O(L^{-1}) from the tangential shell matching in §5.3.8, which uses only the coarse volume bound from Step I and the bootstrap. No sharper estimate on d_0^2 is needed. We will make these quantitative dependencies explicit in the revision. revision: yes

Circularity Check

2 steps flagged

Circular proof structure between Theorems 2 and 3 as written, plus non-load-bearing CGMT citation in Theorem 2's proof chain

specific steps
  1. fitted input called prediction [§5.2.1 (Proof of Theorem 2) and §5.3.3 (Step II of Proof of Theorem 3)]
    "Var(‖ŵ_n‖₁) ≲ E‖ŵ_n‖²₂ / log²(d/n) ≍ (E‖ŵ_n‖₁)² / (n log(d/n)²), where we used that Wang et al. [2022] implies n·E‖ŵ_n‖²₂ ≍ M²_{n,d} ≍ [E‖ŵ_n‖₁]² ≍ n/log(d/n). Hence by dividing both sides by M²_{n,d} = [E(‖ŵ_n‖₁)]², we obtain the claimed result. Note that the final equality made use of Theorem 3."

    Theorem 2's proof explicitly states it uses Theorem 3 ('the final equality made use of Theorem 3'), while Theorem 3's proof (§5.3.3, Step II) uses Theorem 2: 'the map ξ → ‖ξ‖_n / E‖ξ‖_n is O(E‖ξ‖_n/√n)-Lipschitz... Therefore, by Theorem 2, we can assume that E|P̄_{n,d} ∩ B̄_n| ≥ exp(-c√(n/L)) |B̄_n|'. This creates a circular dependency: Theorem 2 ↔ Theorem 3. Additionally, Theorem 2 cites Wang et al. [2022] (CGMT-based) for the rate E‖ŵ_n‖²₂ ≍ 1/log(d/n), which undermines Theorem 3's headline claim of avoiding CGMT. However, the circularity is NOT load-bearing: Theorem 2's conclusion d₀² ≲ 1/(n ln²(d/n)) only requires the upper bound E‖ŵ_n‖²₂ ≲ M²_{n,d}/n, which follows elementarily from Jensen's inequality and the sparsity of ŵ_n (Lemma 7: ‖ŵ_n‖₂ ≤ ‖ŵ_n‖₁/√n since ŵ_n has exactly n non-zZ

  2. fitted input called prediction [§5.2.1, Remark 5 (after Theorem 2)]
    "E‖ŵ_n‖²₂ / E‖ŵ_n‖²₁ = E‖ŵ_n‖²₂ / M²_{n,d} ≥ 1/n by Jensen's inequality; the converse bound follows from Theorem 3 below."

    The paper itself acknowledges that the lower bound E‖ŵ_n‖²₂ ≥ M²_{n,d}/n is established by Theorem 3, while the upper bound is elementary (Jensen). Yet in Theorem 2's proof, the ≍ symbol (requiring both bounds) is used, citing both Wang et al. [2022] and Theorem 3. Since Theorem 2 only claims an upper bound (≲), the lower bound — and hence the citations to both Wang et al. and Theorem 3 — is unnecessary for Theorem 2's conclusion. The proof could replace ≍ with ≲ and use only the elementary Jensen bound, breaking the circularity and removing the CGMT dependency. As written, the proof structure is circular but the gap is fillable with standard tools.

full rationale

The paper has a genuine circular proof structure as written: Theorem 2's proof states it uses Theorem 3, and Theorem 3's proof uses Theorem 2 (§5.3.3, Step II). Additionally, Theorem 2 cites Wang et al. [2022] (CGMT-based) for a rate that Theorem 3 claims to recover without CGMT. However, this circularity is not load-bearing. Theorem 2's conclusion (an upper bound d₀² ≲ 1/(n ln²(d/n))) only requires E‖ŵ_n‖²₂ ≲ M²_{n,d}/n, which follows from Jensen's inequality and the n-sparsity of ŵ_n (Lemma 7) — no CGMT and no Theorem 3 needed. The paper even acknowledges this in Remark 5. The lower bound E‖ŵ_n‖²₂ ≥ c·M²_{n,d}/n (which is what Theorem 3 establishes and Wang et al. [2022] also provides) is not needed for Theorem 2's upper-bound conclusion. Thus, while the proof as written contains a circular dependency and a non-load-bearing CGMT citation, the central geometric argument of Theorem 3 (using Fleury's facet distribution, the volume bootstrap, and thin-shell estimates) has substantial independent content. The gap is fillable: replacing ≍ with ≲ in Theorem 2's proof and using the elementary Jensen bound would break the circularity and remove the CGMT dependency. Score 4 reflects that the circularity exists as written but is not fundamental to the result.

Axiom & Free-Parameter Ledger

2 free parameters · 5 axioms · 0 invented entities

No new entities are postulated. The paper works entirely with standard objects from convex geometry (Gaussian polytopes, isotropic constants, thin-shell constants) and standard statistical objects (minimum-norm interpolators).

free parameters (2)
  • C (absolute constants) = unspecified universal constants
    Throughout the paper, absolute constants C, c, C₀, C₁, etc. appear in bounds and are not numerically specified. These are standard in the asymptotic geometry literature but affect the sharpness of finite-sample bounds.
  • c₁ (in Theorem 3 probability bound) = unspecified
    The probability bound 1 - exp(-c₁n log(d/n)^{-2}) involves an unspecified constant c₁ > 0.
axioms (5)
  • domain assumption Fleury's [2012] characterization of the conditional distribution of a facet of P_{n,d} (Lemma 1, §3.1): a facet's matrix is distributed as UA where U is Haar and A involves a near-Gaussian matrix Y and an independent height variable T_{n,d}.
    This is the foundational input for the proof of Theorem 3. It is an external result from Fleury [2012, Thm. 3-4], not proved here (though Corollary 2 gives an elementary proof of the Poincaré inequality part). If this result has errors, Theorem 3 fails.
  • domain assumption Assumption 1: K is in isotropic position, ∥w⋆∥ ≍ ∥w⋆∥₂ ≍ 1, and M_n(K) ≫ ∥w⋆∥.
    Stated in §2.1. This is a normalization/position assumption for Theorem 1. The paper notes it holds for ℓp norms with p ∈ [1,2].
  • domain assumption Assumption 2: The orthogonal component of the MNI has a polynomial upper tail at its natural second-moment scale.
    Stated in §2.1. This is a regularity assumption on the tail behavior of the MNI. The paper states it holds for ℓp-norms with p ∈ [1,2].
  • domain assumption The covariates are isotropic Gaussian N(0, I_d).
    Stated in §1. The entire approach depends on Gaussianity; §4.1 explains why sub-Gaussian extensions fail.
  • standard math Resolution of the slicing problem (Klartag-Lehec 2025, Bizeul 2025, Guan 2024) implying isotropic convex bodies are in M-position up to a universal constant.
    Invoked in §1.1 to connect isotropic position to classical positions. This is a recent major result in convex geometry.

pith-pipeline@v1.1.0-glm · 53735 in / 4582 out tokens · 419487 ms · 2026-07-09T01:54:58.784403+00:00 · methodology

0 comments
read the original abstract

We study minimum-norm interpolation (MNI) in overparameterized linear regression with isotropic Gaussian covariates, in settings where the MNI has no closed-form formula. Whereas most prior work relied on Gaussian comparison tools such as the convex Gaussian min--max theorem (CGMT), our approach uses tools from high-dimensional geometry and probability. First, when the norm is in isotropic position, we obtain an ``offset'' bound that controls the amount by which the MNI shrinks the ground truth. Second, we show that the ``intrinsic'' variance of the $\ell_1$-MNI is at most $O(\tfrac{1}{n\log(d/n)^2})$, using a variant of Talagrand's $L_1$--$L_2$ inequality due to Cordero-Erausquin and Ledoux [2012], together with a classical result of Gluskin [1988]. We recover the sharp mean-squared error (MSE) bound for the $\ell_1$-MNI obtained by Wang et al. [2022], using the work of Fleury [2012] on the symmetric Gaussian polytope, which is defined via \[ P_{n,d} := \mathrm{conv}\{\pm X_i\}_{i=1}^{d} \text{ where } X_i \overset{\mathrm{i.i.d.}}{\sim} N(0,\mathrm{I}_{n \times n}), \] rather than CGMT. Our methods also imply improvements on previous results in high-dimensional geometry that may be of independent interest. First, we show that with overwhelming probability, the ratio between the isotropic constant of $P_{n,d}$ and that of the Euclidean ball in $\mathbb{R}^n$ is at most $1+O((\log(d/n))^{-2})$, improving a result of Klartag and Kozma [2009]. We also establish a refined weighted thin-shell estimate on $P_{n,d}$, and provide an elementary proof of the main theorem of Fleury [2012].

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

300 extracted references · 300 canonical work pages · 48 internal anchors

  1. [1]

    and Litvak, A

    Gordon, Y. and Litvak, A. E. and Mendelson, S. and Pajor, A. , TITLE =. J. Approx. Theory , FJOURNAL =. 2007 , NUMBER =. doi:10.1016/j.jat.2007.04.007 , URL =

    work page doi:10.1016/j.jat.2007.04.007 2007

  2. [2]

    Proceedings of the American Mathematical Society , volume=

    On the Gaussian behavior of marginals and the mean width of random polytopes , author=. Proceedings of the American Mathematical Society , volume=

    work page

  3. [3]

    Gluskin, E. D. , TITLE =. Mat. Sb. (N.S.) , FJOURNAL =. 1988 , NUMBER =

    work page 1988

  4. [4]

    The slicing conjecture via small ball estimates

    The slicing conjecture via small ball estimates , author=. arXiv preprint arXiv:2501.06854 , year=

    work page internal anchor Pith review Pith/arXiv arXiv

  5. [5]

    International Mathematics Research Notices , volume=

    On the mean-width of isotropic convex bodies and their associated L p-centroid bodies , author=. International Mathematics Research Notices , volume=. 2015 , publisher=

    work page 2015

  6. [6]

    Geometric Aspects of Functional Analysis: Israel Seminar 2001-2002 , pages=

    _2 -Estimates for Linear Functionals on Zonoids , author=. Geometric Aspects of Functional Analysis: Israel Seminar 2001-2002 , pages=. 2004 , organization=

    work page 2001

  7. [7]

    A note on Bourgain's slicing problem

    A note on Bourgain's slicing problem , author=. arXiv preprint arXiv:2412.09075 , year=

    work page internal anchor Pith review Pith/arXiv arXiv

  8. [8]

    Geometric and Functional Analysis , pages=

    Affirmative resolution of Bourgain’s slicing problem using Guan’s bound , author=. Geometric and Functional Analysis , pages=. 2025 , publisher=

    work page 2025

  9. [9]

    Biometrika , volume=

    The convex hull of a random set of points , author=. Biometrika , volume=. 1965 , publisher=

    work page 1965

  10. [10]

    Limit Theorems in Probability, Statistics and Number Theory: In Honor of Friedrich G

    Moderate deviations for the determinant of Wigner matrices , author=. Limit Theorems in Probability, Statistics and Number Theory: In Honor of Friedrich G. 2013 , publisher=

    work page 2013

  11. [11]

    Information and Inference: A Journal of the IMA , volume=

    Debiased LASSO under Poisson--Gauss model , author=. Information and Inference: A Journal of the IMA , volume=. 2025 , publisher=

    work page 2025

  12. [12]

    Journal of Mathematical Sciences , volume=

    Gaussian Convex Bodies: a Nonasymptotic Approach , author=. Journal of Mathematical Sciences , volume=. 2019 , publisher=

    work page 2019

  13. [13]

    Fleury, B , journal=. Poincar. 2012 , publisher=

    work page 2012

  14. [14]

    The Journal of Geometric Analysis , volume=

    Facets of high-dimensional Gaussian polytopes , author=. The Journal of Geometric Analysis , volume=. 2024 , publisher=

    work page 2024

  15. [15]

    The Annals of mathematical statistics , volume=

    The distribution of the determinant of a complex Wishart distributed matrix , author=. The Annals of mathematical statistics , volume=. 1963 , publisher=

    work page 1963

  16. [16]

    On the geometry of polytopes generated by heavy-tailed random vectors , JOURNAL =

    Gu\'. On the geometry of polytopes generated by heavy-tailed random vectors , JOURNAL =. 2022 , NUMBER =. doi:10.1142/S0219199721500565 , URL =

    work page doi:10.1142/s0219199721500565 2022

  17. [17]

    The Annals of Probability , volume=

    Hypercontractivity and lower deviation estimates in normed spaces , author=. The Annals of Probability , volume=

    work page

  18. [18]

    Transactions of the American Mathematical Society , volume=

    Expected volumes of Gaussian polytopes, external angles, and multiple order statistics , author=. Transactions of the American Mathematical Society , volume=

    work page

  19. [19]

    Geometric & Functional Analysis GAFA , volume=

    Concentration of mass on convex bodies , author=. Geometric & Functional Analysis GAFA , volume=. 2006 , publisher=

    work page 2006

  20. [20]

    Israel Journal of Mathematics , volume=

    On the hyperplane conjecture for random convex sets , author=. Israel Journal of Mathematics , volume=. 2009 , publisher=

    work page 2009

  21. [21]

    A Gaussian Convexity for Logarithmic Moment Generating Functions with Applications in Spin Glasses

    A Gaussian Convexity for Logarithmic Moment Generating Functions with Applications in Spin Glasses , author=. arXiv preprint arXiv:2311.08351 , year=

    work page internal anchor Pith review Pith/arXiv arXiv

  22. [22]

    Proceedings of the National Academy of Sciences , volume =

    Mikhail Belkin and Daniel Hsu and Siyuan Ma and Soumik Mandal , title =. Proceedings of the National Academy of Sciences , volume =

    work page

  23. [23]

    Communications of the ACM , volume =

    Chiyuan Zhang and Samy Bengio and Moritz Hardt and Benjamin Recht and Oriol Vinyals , title =. Communications of the ACM , volume =

    work page

  24. [24]

    Bartlett and Philip M

    Peter L. Bartlett and Philip M. Long and G. Benign overfitting in linear regression , journal =

    work page

  25. [25]

    The Annals of Statistics , volume =

    Edgar Dobriban and Stefan Wager , title =. The Annals of Statistics , volume =

    work page

  26. [26]

    The Annals of Statistics , volume =

    Behrooz Ghorbani and Song Mei and Theodor Misiakiewicz and Andrea Montanari , title =. The Annals of Statistics , volume =

    work page

  27. [27]

    Communications on Pure and Applied Mathematics , year =

    Song Mei and Andrea Montanari , title =. Communications on Pure and Applied Mathematics , year =

    work page

  28. [28]

    Benign overfitting in ridge regression

    Alexander Tsigler and Peter L. Bartlett , title =. arXiv preprint arXiv:2009.14286 , year =

    work page internal anchor Pith review Pith/arXiv arXiv 2009

  29. [29]

    Journal of the Royal Statistical Society: Series B (Methodological) , volume =

    Robert Tibshirani , title =. Journal of the Royal Statistical Society: Series B (Methodological) , volume =

    work page

  30. [30]

    Van de Geer , title =

    Sara A. Van de Geer , title =. The Annals of Statistics , volume =

    work page

  31. [31]

    Donoho and Michael A

    Scott Shaobing Chen and David L. Donoho and Michael A. Saunders , title =. SIAM Journal on Scientific Computing , volume =

    work page

  32. [32]

    Candes , title =

    Emmanuel J. Candes , title =. Comptes Rendus Mathematique , volume =

    work page

  33. [33]

    Donoho and Michael Elad , title =

    David L. Donoho and Michael Elad , title =. Signal Processing , volume =

    work page

  34. [34]

    Uniform Convergence of Interpolators: Gaussian Width, Norm Bounds, and Benign Overfitting

    Frederic Koehler and Lijia Zhou and Danica J. Sutherland and Nathan Srebro , title =. arXiv preprint arXiv:2106.09276 , year =

    work page internal anchor Pith review Pith/arXiv arXiv

  35. [35]

    Advances in Neural Information Processing Systems , volume =

    Peizhong Ju and Xiaojun Lin and Jia Liu , title =. Advances in Neural Information Processing Systems , volume =

    work page

  36. [36]

    Wojtaszczyk , title =

    P. Wojtaszczyk , title =. Foundations of Computational Mathematics , volume =

    work page

  37. [37]

    Linear Algebra and its Applications , volume =

    Simon Foucart , title =. Linear Algebra and its Applications , volume =

    work page

  38. [38]

    On the robustness of minimum-norm interpolators , journal =

    Geoffrey Chinot and Matthias L. On the robustness of minimum-norm interpolators , journal =

    work page

  39. [39]

    A Quotient Property for Matrices with Heavy-Tailed Entries and its Application to Noise-Blind Compressed Sensing

    Felix Krahmer and Christian K. A quotient property for. arXiv preprint arXiv:1806.04261 , year =

    work page internal anchor Pith review Pith/arXiv arXiv

  40. [40]

    The Lie algebra structure of the $HH^1$ of the blocks of the sporadic Mathieu groups

    Niladri S. Chatterji and Philip M. Long , title =. arXiv preprint arXiv:2110.02941 , year =

    work page internal anchor Pith review Pith/arXiv arXiv

  41. [41]

    IEEE Journal on Selected Areas in Information Theory , volume =

    Vidya Muthukumar and Kailas Vodrahalli and Vignesh Subramanian and Anant Sahai , title =. IEEE Journal on Selected Areas in Information Theory , volume =

    work page

  42. [42]

    Stochastic processes and their applications , volume=

    Remarks on non-interacting conservative spin systems: the case of gamma distributions , author=. Stochastic processes and their applications , volume=. 2009 , publisher=

    work page 2009

  43. [43]

    Israel Journal of Mathematics , volume=

    Extremal problems and isotropic positions of convex bodies , author=. Israel Journal of Mathematics , volume=. 2000 , publisher=

    work page 2000

  44. [44]

    and Saunders, Michael A

    Chen, Scott Shaobing and Donoho, David L. and Saunders, Michael A. , TITLE =. SIAM J. Sci. Comput. , FJOURNAL =. 1998 , NUMBER =. doi:10.1137/S1064827596304010 , URL =

    work page doi:10.1137/s1064827596304010 1998

  45. [45]

    Paouris, Grigoris and Valettas, Petros , TITLE =. Adv. Geom. , FJOURNAL =. 2019 , NUMBER =. doi:10.1515/advgeom-2018-0030 , URL =

    work page doi:10.1515/advgeom-2018-0030 2019

  46. [46]

    2014 , PAGES =

    Chatterjee, Sourav , TITLE =. 2014 , PAGES =. doi:10.1007/978-3-319-03886-5 , URL =

    work page doi:10.1007/978-3-319-03886-5 2014

  47. [47]

    Talagrand, Michel , TITLE =. Ann. Probab. , FJOURNAL =. 1994 , NUMBER =

    work page 1994

  48. [48]

    The Annals of Statistics , volume=

    Convergence rates of least squares regression estimators with heavy-tailed errors , author=. The Annals of Statistics , volume=. 2019 , publisher=

    work page 2019

  49. [49]

    Spaces with Large Distance to ^

    Szarek, Stanislaw J , journal=. Spaces with Large Distance to ^. 1990 , publisher=

    work page 1990

  50. [50]

    Probability Theory and Related Fields , pages=

    Benign overfitting and adaptive nonparametric regression , author=. Probability Theory and Related Fields , pages=. 2024 , publisher=

    work page 2024

  51. [51]

    2017 , publisher=

    Alice and Bob meet Banach , author=. 2017 , publisher=

    work page 2017

  52. [52]

    International Mathematics Research Notices , volume=

    Small ball probabilities for linear images of high-dimensional distributions , author=. International Mathematics Research Notices , volume=. 2015 , publisher=

    work page 2015

  53. [53]

    International Conference on Algorithmic Learning Theory , pages=

    Tight bounds for maximum in ell-one -margin classifiers , author=. International Conference on Algorithmic Learning Theory , pages=. 2024 , organization=

    work page 2024

  54. [54]

    International Conference on Artificial Intelligence and Statistics , pages=

    Tight bounds for minimum in lone-norm interpolation of noisy data , author=. International Conference on Artificial Intelligence and Statistics , pages=. 2022 , organization=

    work page 2022

  55. [55]

    2017 , author =

    Random version of Dvoretzky’s theorem in _p , journal =. 2017 , author =

    work page 2017

  56. [56]

    Strong inductive biases provably prevent harmless interpolation , author=

    work page

  57. [57]

    Journal of Mathematical Analysis and Applications , volume=

    Upper bound for intermediate singular values of random matrices , author=. Journal of Mathematical Analysis and Applications , volume=. 2017 , publisher=

    work page 2017

  58. [58]

    Comptes Rendus Mathematique , volume=

    Random Euclidean embeddings in spaces of bounded volume ratio , author=. Comptes Rendus Mathematique , volume=. 2004 , publisher=

    work page 2004

  59. [59]

    International Conference on Artificial Intelligence and Statistics , pages=

    Adaptively Partitioning Max-Affine Estimators for Convex Regression , author=. International Conference on Artificial Intelligence and Statistics , pages=. 2022 , organization=

    work page 2022

  60. [60]

    Discrete & Computational Geometry , volume=

    Approximating a convex body by a polytope using the epsilon-net theorem , author=. Discrete & Computational Geometry , volume=. 2019 , publisher=

    work page 2019

  61. [61]

    Publications of the Research Institute for Mathematical Sciences , volume=

    A simple proof of Kwapien's theorem , author=. Publications of the Research Institute for Mathematical Sciences , volume=. 1984 , publisher=

    work page 1984

  62. [62]

    2014 , publisher=

    Upper and lower bounds for stochastic processes , author=. 2014 , publisher=

    work page 2014

  63. [63]

    IEEE transactions on information theory , volume=

    On coverings of ellipsoids in Euclidean spaces , author=. IEEE transactions on information theory , volume=. 2004 , publisher=

    work page 2004

  64. [64]

    Journal of Combinatorial Theory, Series A , volume=

    Covering an ellipsoid with equal balls , author=. Journal of Combinatorial Theory, Series A , volume=. 2006 , publisher=

    work page 2006

  65. [65]

    2017 , journal=

    A note on the approximate admissibility of regularized estimators in the Gaussian sequence model , author=. 2017 , journal=

    work page 2017

  66. [66]

    Journal of the ACM , volume=

    A universal law of robustness via isoperimetry , author=. Journal of the ACM , volume=. 2023 , publisher=

    work page 2023

  67. [67]

    Lecture Notes-Monograph Series , pages=

    Estimating a Polya Frequency Function , author=. Lecture Notes-Monograph Series , pages=. 2007 , publisher=

    work page 2007

  68. [68]

    The Annals of Statistics , volume=

    Set structured global empirical risk minimizers are rate optimal in general dimensions , author=. The Annals of Statistics , volume=. 2021 , publisher=

    work page 2021

  69. [69]

    Conference on Learning Theory , pages=

    On suboptimality of least squares with application to estimation of convex bodies , author=. Conference on Learning Theory , pages=. 2020 , organization=

    work page 2020

  70. [70]

    The Annals of Probability , volume=

    Concentration of the information in data with log-concave distributions , author=. The Annals of Probability , volume=. 2011 , publisher=

    work page 2011

  71. [71]

    Probability Theory and Related Fields , volume=

    Adaptive estimation of convex and polytopal density support , author=. Probability Theory and Related Fields , volume=. 2016 , publisher=

    work page 2016

  72. [72]

    Electronic Journal of Statistics , volume=

    Adaptive estimation of convex polytopes and convex sets from noisy data , author=. Electronic Journal of Statistics , volume=. 2013 , publisher=

    work page 2013

  73. [73]

    Spectrahedral Regression

    Spectrahedral Regression , author=. arXiv preprint arXiv:2110.14779 , year=

    work page internal anchor Pith review Pith/arXiv arXiv

  74. [74]

    Discrete & Computational Geometry , pages=

    Fitting tractable convex sets to support function evaluations , author=. Discrete & Computational Geometry , pages=. 2021 , publisher=

    work page 2021

  75. [75]

    IEEE Transactions on Information Theory , year=

    Max-affine regression: Parameter estimation for Gaussian designs , author=. IEEE Transactions on Information Theory , year=

    work page

  76. [76]

    A new computational framework for log-concave density estimation

    A new computational framework for log-concave density estimation , author=. arXiv preprint arXiv:2105.11387 , year=

    work page internal anchor Pith review Pith/arXiv arXiv

  77. [77]

    Proceedings of Thirty Fourth Conference on Learning Theory , pages =

    On the Minimal Error of Empirical Risk Minimization , author =. Proceedings of Thirty Fourth Conference on Learning Theory , pages =. 2021 , editor =

    work page 2021

  78. [78]

    The Annals of Statistics , volume=

    Isotonic regression with unknown permutations: Statistics, computation and adaptation , author=. The Annals of Statistics , volume=. 2022 , publisher=

    work page 2022

  79. [79]

    Advances in applied probability , volume=

    Rates of convergence for random approximations of convex sets , author=. Advances in applied probability , volume=. 1996 , publisher=

    work page 1996

  80. [80]

    Mathematica Scandinavica , pages=

    The convex floating body , author=. Mathematica Scandinavica , pages=. 1990 , publisher=

    work page 1990

Showing first 80 references.