Tight Worst-Case Bounds for the Smallest Eigenvalue of ReLU NTK Gram Matrices

Zhao Song

Tight Worst-Case Bounds for the Smallest Eigenvalue of ReLU NTK Gram Matrices

T0 review · 0 major / 4 minor · reviewed 2026-08-05 · deepseek-v4-flash

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

Pith's one-line read The smallest eigenvalue of the ReLU NTK Gram matrix is always at least order Δ±/√log n, and the bound is tight in the worst case.

desk verdict The paper's tight bounds are real; the reader's main counterexample is a false alarm. read the letter →

arxiv 2608.03368 v1 pith:BWCFNFAJ submitted 2026-08-04 cs.LG

Zhao Song This is my paper · ORCID

classification cs.LG MSC 68T0715A42

keywords neuraltangentkernelReLUactivationGrammatrixsmallesteigenvalueprojectiveseparationHadamardpowerbinarylinearcodelazyrandomwalkspectralconditioning

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

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

The reading

The paper studies the infinite-width hidden-layer Gram matrix $H$ of a two-layer ReLU network on $n$ unit input vectors in $\mathbb{R}^d$. It claims a dimension-free lower bound on its smallest eigenvalue: $\lambda_{\min}(H) = \Omega(\Delta_\pm/\sqrt{\log n})$, where $\Delta_\pm$ is the smallest Euclidean distance between any two inputs or their negatives. It also constructs worst-case families with $n=2^{\Theta(d)}$ for which $\lambda_{\min}(H)=O(\Delta_\pm/\sqrt{\log n})$, so the logarithmic rate is tight up to universal constants. The smallest eigenvalue controls the conditioning and convergence speed of linearized ReLU training, so the result sharpens the previous polynomial-in-$n$ guarantee to a dimension-free rate.

What carries the argument

The central object is $H$, the population NTK Gram matrix of the hidden-weight derivative of a two-layer ReLU network, averaged over a Gaussian weight direction. The lower bound is carried by the arcsine-kernel identity $H=\frac14 G+\frac{1}{2\pi}\sum_{k=0}^\infty a_k G^{\circ(2k+2)}$ with positive $a_k$, where $G$ is the data Gram matrix and $\circ$ is entrywise (Hadamard) power; the Schur product theorem makes every term positive semidefinite, and the high-degree tail is diagonally dominant under $\Delta_\pm$ separation. The upper bound is carried by a binary linear code embedded in a spherical cap, whose Gram matrix is a convolution matrix on the code; Fourier diagonalization over the dua

What would settle it

Compute the two sides of the identity in the middle of the upper-bound proof for $D=2$, $\tau=1/4$, $r=2$, $L=1$: the Fourier-coefficient sum $2^{-D}\sum_{|b|\ge L}\Lambda_b$ equals $0.34375$, while the corresponding lazy-walk probability term is $0.4375$. The mismatch directly disproves the displayed proof step, so the theorem requires a replacement argument before the matching upper bound is established.

Watch

Extended reading notes

Core claim

The paper's central claim is that the population ReLU derivative NTK Gram matrix $H$, with entries $H_{ij}=\mathbb{E}_w[x_i^\top x_j \mathbf{1}\{w^\top x_i\ge 0\}\mathbf{1}\{w^\top x_j\ge 0\}]$, has smallest eigenvalue governed by the projective separation $\Delta_\pm$. On the lower side, it proves $H \succeq \frac{\Delta_\pm}{70\sqrt{\log n}} I_n$ by expanding $H$ as a positive linear combination of even Hadamard powers of the data Gram matrix and showing the high-degree tail is diagonally dominant. On the upper side, it constructs binary linear codes embedded in a spherical cap, giving $n=2^{\Theta(d)}$ unit vectors with all pairwise correlations near $1$, and analyzes the resulting convol

Load-bearing premise

The upper-bound construction rests on an exact equality between a sum of Fourier coefficients of the kernel and the tail probability of a lazy random walk; in a simple two-coordinate case the two sides are unequal, so that equality cannot be the load-bearing step as written.

Editorial extensions

If this is right

If the lower bound is correct, every projectively separated set of $n$ unit vectors has ReLU NTK conditioning at least of order $1/\sqrt{\log n}$, with no dependence on the ambient dimension.
The matching construction shows the $\sqrt{\log n}$ degradation is intrinsic: there exist exponentially large configurations whose smallest eigenvalue is no larger than this rate.
For data with nonnegative pairwise inner products, the same rate holds with ordinary separation $\Delta_-$ in place of $\Delta_\pm$, since projective and ordinary separation coincide there.
The regular-hexagon example shows that no lower bound depending only on ordinary separation $\Delta_-$ can hold: even with $\Delta_-=1$ and $n=6$, the smallest eigenvalue can be zero, and the obstruction survives small rotations.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

The displayed identity at the heart of the upper-bound proof is not established by the paper; a small-parameter check separates the two sides, so a repaired argument is needed before the matching upper bound is established.
A natural repair would replace the exact identity with two-sided control of the Fourier tail, or restrict the code and parameters so the identity holds; either route would likely change constants but not the $\Delta_\pm/\sqrt{\log n}$ power.
The same positive-Hadamard-power expansion could apply to other kernels whose angular dependence has a nonnegative series, potentially giving dimension-free eigenvalue lower bounds for higher-order ReLU or smooth activations.
The spherical-cap construction suggests that random codes with weight concentration, not only balanced linear codes, may exhibit the same worst-case eigenvalue profile; small constant-weight codes would be a cheap numerical check.

Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

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

Desk Editor's Note

read the letter

I read this with the reader's report in hand, and I think the rejection is wrong. The claimed false identity in Lemma 2.2 is exact. The proof only needs it for L = ceil(beta D) with beta > 0, so L >= 2; for that range the linear term has zero Fourier mass. The reader's counterexample uses L=1, which is outside the proof's range, and the arithmetic is off: for D=2, tau=1/4, r=2, both sides of the quadratic identity are 13/(64 pi), not the numbers claimed. The upper-bound construction survives.

What's actually new: the lower bound Omega(Delta/sqrt(log n)) improves on all cited prior bounds and is dimension-free. The upper-bound construction using balanced binary codes in a spherical cap plus Fourier diagonalization over the code is not a routine extension; it's a real idea. The lower-bound proof—arcsine expansion, Schur product, Gershgorin on the high-degree tail—is clean. Section 3's hexagon example and the continuous perturbation correctly show that ordinary separation cannot replace projective separation, which is a useful clarification.

Soft spots: the paper is terse; the Fourier identity in Lemma 2.2 is stated without derivation, which is probably why the reader tripped. A referee should ask for a short explanation there. The upper-bound construction is existential via random coding, not explicit, and the constants are not optimized. That's standard for this area. The paper is about the population NTK Gram matrix only; finite-width effects are out of scope, and the paper says so.

The citation pattern is fine. The open problem is cited from the author's own thesis, but that thesis only poses the question; the proof here is self-contained and does not rely on anything from it.

This deserves a serious referee. I would send it out. The central theorem is correct, the proof is self-contained, and the improvement over the literature is substantial. Anyone working on NTK conditioning or two-layer training analyses will use this.

Referee Report

0 major / 4 minor

Summary. The paper studies the continuous ReLU derivative Gram matrix H_ij = E_w[x_i^T x_j 1_{w^T x_i >= 0} 1_{w^T x_j >= 0}] for n unit vectors, and proves two results: (i) a universal lower bound lambda_min(H) = Omega(Delta_pm / sqrt(log n)) for any projectively separated data set; and (ii) an existential matching upper bound, lambda_min(H) = O(Delta_pm / sqrt(log n)), for families with n = 2^{Theta(d)}. The lower bound is proved via the arcsine expansion, the Schur product theorem, Gershgorin's theorem, and standard tail estimates. The upper bound is obtained from random binary linear codes embedded in a spherical cap, followed by Fourier diagonalization of the resulting convolution Gram matrix and a lazy coordinate walk estimate. Section 3 shows by a robust example that ordinary separation Delta_- cannot replace the projective separation Delta_pm. I verified the key steps, including the Fourier-mass identity in Lemma 2.2, and found the arguments sound.

Significance. If correct, the result resolves an open question in [Son19] and improves the Oymak--Soltanolkotabi polynomial-in-1/n bound to a dimension-free rate that is tight up to universal constants. The proof is self-contained, uses standard and appropriate tools, and contains no fitted parameters or circular dependencies. The construction with binary linear codes is elegant and gives a matching upper bound. I verified the identity disputed in the other reader report: 2^{-D} sum_{|b|>=L} Lambda_b = sum_{r even >= 2} q_r Pr[|Z_r| >= L] is exact, not approximate; the claimed counterexample is arithmetically incorrect. The paper is a solid contribution to the conditioning theory of ReLU NTK matrices.

minor comments (4)

[Lemma 2.2] Please expand the Fourier-inversion step. The identity 2^{-D} sum_{|b|>=L} Lambda_b = sum_{r even >= 2} q_r Pr[|Z_r|>=L] is correct, but it is easy to misread: one must use Lambda_b = 2^D sum_r q_r p_r(b), where p_r is the r-step lazy-walk distribution, not its Fourier transform. The linear term contributes only at Hamming weights 0 and 1, so the identity holds for L >= 2; state this explicitly.
[Lemma 2.1] The bound K <= 5 log n / Delta_pm^2 uses 3 log 2 > 2. This is true but might be worth spelling out for readability.
[Section 3] In the regular hexagon example, the identity Phi_w(u) - Phi_w(-u) = u holds for almost every Gaussian w (specifically, whenever w.u != 0). Please state this 'almost surely' qualification explicitly.
[Abstract and main text] Minor typo: the abstract contains 'Forn unit vectors' and the main text has 'For nunit vectors' without a space.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: all load-bearing claims are proved from standard matrix/Fourier facts, with self-citations only contextual.

full rationale

The central lower bound is self-contained: H is expanded exactly as 1/4 G + (1/2π)∑ a_k G∘(2k+2), and the eigenvalue bound follows from the Schur product theorem, Gershgorin's theorem, Wallis-type binomial estimates, and the decay of off-diagonal Hadamard powers. None of these ingredients assume the target bound. The upper-bound construction independently chooses a random binary linear code, computes the convolution eigenvalues by Fourier diagonalization, and bounds the high-weight Fourier mass using the exact lazy-random-walk identity obtained by Fourier inversion; the constants α, β, R, and τ are free parameters chosen to satisfy existence/entropy inequalities, not fitted to the target eigenvalue. The only self-citations ([Son19] for posing the open problem, [AZLS19] for noting a normalization convention) are contextual and do not supply a load-bearing ingredient; no uniqueness theorem is imported, no ansatz is smuggled in through a citation, and no known result is merely renamed. The paper even proves the necessity of Δ± rather than Δ− with an explicit hexagon example. Thus the derivation chain is genuinely independent of its conclusions, so the circularity score is 0.

Assumptions & free parameters 0 free parameters · 7 assumptions · 0 invented entities

No fitted parameters; the bounds are universal. The upper construction's tau is a variable, not a fitted constant. All entities are standard mathematical objects; no new particles or forces.

assumptions (7)

standard math Schur product theorem: entrywise powers of a PSD matrix are PSD
Used in Lemma 2.1 to keep Hadamard-power terms PSD.
standard math Gershgorin circle theorem
Used to lower bound the minimum eigenvalue of high Hadamard powers after off-diagonal decay.
standard math Wallis inequalities for central binomial coefficients
Used to lower bound the tail sum of arcsine coefficients.
standard math Existence of binary linear codes with prescribed weight via probabilistic method
Used in Lemma 2.2 to build the spherical cap configuration.
standard math Fourier inversion and character theory on the hypercube
Used to compute eigenvalues of convolution matrices on the code.
standard math Lazy random walk representation of (1 - 2 tau |b|/D)^r
Used to relate Fourier coefficients to walk probabilities.
domain assumption Data x_i are unit vectors and w ~ N(0, I_d)
The definition of H and the bivariate Gaussian correlation structure.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Tight Worst-Case Bounds for the Smallest Eigenvalue of ReLU NTK Gram Matrices." pith.science (2026). https://pith.science/paper/BWCFNFAJ

@misc{pith2026260803368,
  author       = {Pith},
  title        = {Pith review of: Tight Worst-Case Bounds for the Smallest Eigenvalue of ReLU NTK Gram Matrices},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/BWCFNFAJ}},
  note         = {Machine review of arXiv:2608.03368}
}

abstract

For $n$ unit vectors $x_1,\ldots,x_n \in \mathbb{R}^d$, we study the continuous ReLU derivative Gram matrix $H$, whose entries are obtained by averaging pairwise gated inner products over a standard Gaussian direction. Writing $ \Delta_\pm := \min_{i \neq j} \min\{ \|x_i-x_j\|_2, \|x_i+x_j\|_2 \} $ for their projective separation, we prove the universal dimension-free lower bound $ \lambda_{\min}(H) = \Omega( \Delta_\pm/\sqrt{\log n} ) $. Conversely, we construct worst-case families satisfying the matching upper bound $ \lambda_{\min}(H) = O( \Delta_\pm/\sqrt{\log n} ) $, showing that this rate is tight up to universal constants.

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

Training Under Challenge: Executable Certificates and Challenge-Closed Optimality for Neural Networks
cs.LG 2026-08 accept novelty 6.0 of 10

Executable challenger models give provable lower bounds on a checkpoint's empirical optimality gap, and spectral coverage conditions upgrade finite-suite passage into quantitative near-globality certificates.

Reference graph

Works this paper leans on

10 extracted references · 10 canonical work pages · cited by 1 Pith paper

[1]

A convergence theory for deep learning via over-parameterization

Zeyuan Allen-Zhu, Yuanzhi Li, and Zhao Song. A convergence theory for deep learning via over-parameterization. In Proceedings of the 36th International Conference on Machine Learning , volume 97 of Proceedings of Machine Learning Research , pages 242--252. PMLR, 2019

work page 2019
[2]

Chandrasekharan

K. Chandrasekharan. Introduction to Analytic Number Theory , volume 148 of Grundlehren der mathematischen Wissenschaften . Springer-Verlag, Berlin, Heidelberg, 1968

work page 1968
[3]

Du, Xiyu Zhai, Barnab \'a s P \'o czos, and Aarti Singh

Simon S. Du, Xiyu Zhai, Barnab \'a s P \'o czos, and Aarti Singh. Gradient descent provably optimizes over-parameterized neural networks. In International Conference on Learning Representations , 2019

work page 2019
[4]

Horn and Charles R

Roger A. Horn and Charles R. Johnson. Matrix Analysis . Cambridge University Press, Cambridge, 2 edition, 2012

work page 2012
[5]

Neural tangent kernel: Convergence and generalization in neural networks

Arthur Jacot, Franck Gabriel, and Cl \'e ment Hongler. Neural tangent kernel: Convergence and generalization in neural networks. In Advances in Neural Information Processing Systems , volume 31, pages 8571--8580, 2018

work page 2018
[6]

Bounds for the smallest eigenvalue of the NTK for arbitrary spherical data of arbitrary dimension

Kedar Karhadkar, Michael Murray, and Guido Mont \'u far. Bounds for the smallest eigenvalue of the NTK for arbitrary spherical data of arbitrary dimension. In Advances in Neural Information Processing Systems , volume 37, pages 138197--138249, 2024

work page 2024
[7]

Condition numbers and eigenvalue spectra of shallow networks on spheres, 2025

Xinliang Liu, Tong Mao, and Jinchao Xu. Condition numbers and eigenvalue spectra of shallow networks on spheres, 2025

work page 2025
[8]

Toward moderate overparameterization: Global convergence guarantees for training shallow neural networks

Samet Oymak and Mahdi Soltanolkotabi. Toward moderate overparameterization: Global convergence guarantees for training shallow neural networks. IEEE Journal on Selected Areas in Information Theory , 1(1):84--105, 2020

work page 2020

Show all 10 references

[9]

Effect of activation functions on the training of overparametrized neural nets

Abhishek Panigrahi, Abhishek Shetty, and Navin Goyal. Effect of activation functions on the training of overparametrized neural nets. In International Conference on Learning Representations , 2020

2020
[10]

Matrix Theory: Optimization, Concentration and Algorithms

Zhao Song. Matrix Theory: Optimization, Concentration and Algorithms . PhD thesis, The University of Texas at Austin, August 2019

2019

Pith tools

Reviewed August 5, 2026 · model on record in the stance chip above.

[1] [1]

A convergence theory for deep learning via over-parameterization

Zeyuan Allen-Zhu, Yuanzhi Li, and Zhao Song. A convergence theory for deep learning via over-parameterization. In Proceedings of the 36th International Conference on Machine Learning , volume 97 of Proceedings of Machine Learning Research , pages 242--252. PMLR, 2019

work page 2019

[2] [2]

Chandrasekharan

K. Chandrasekharan. Introduction to Analytic Number Theory , volume 148 of Grundlehren der mathematischen Wissenschaften . Springer-Verlag, Berlin, Heidelberg, 1968

work page 1968

[3] [3]

Du, Xiyu Zhai, Barnab \'a s P \'o czos, and Aarti Singh

Simon S. Du, Xiyu Zhai, Barnab \'a s P \'o czos, and Aarti Singh. Gradient descent provably optimizes over-parameterized neural networks. In International Conference on Learning Representations , 2019

work page 2019

[4] [4]

Horn and Charles R

Roger A. Horn and Charles R. Johnson. Matrix Analysis . Cambridge University Press, Cambridge, 2 edition, 2012

work page 2012

[5] [5]

Neural tangent kernel: Convergence and generalization in neural networks

Arthur Jacot, Franck Gabriel, and Cl \'e ment Hongler. Neural tangent kernel: Convergence and generalization in neural networks. In Advances in Neural Information Processing Systems , volume 31, pages 8571--8580, 2018

work page 2018

[6] [6]

Bounds for the smallest eigenvalue of the NTK for arbitrary spherical data of arbitrary dimension

Kedar Karhadkar, Michael Murray, and Guido Mont \'u far. Bounds for the smallest eigenvalue of the NTK for arbitrary spherical data of arbitrary dimension. In Advances in Neural Information Processing Systems , volume 37, pages 138197--138249, 2024

work page 2024

[7] [7]

Condition numbers and eigenvalue spectra of shallow networks on spheres, 2025

Xinliang Liu, Tong Mao, and Jinchao Xu. Condition numbers and eigenvalue spectra of shallow networks on spheres, 2025

work page 2025

[8] [8]

Toward moderate overparameterization: Global convergence guarantees for training shallow neural networks

Samet Oymak and Mahdi Soltanolkotabi. Toward moderate overparameterization: Global convergence guarantees for training shallow neural networks. IEEE Journal on Selected Areas in Information Theory , 1(1):84--105, 2020

work page 2020