mlsanityData to 14 Oct 2026

Dimension-Free Rank Lifting from Random Hyperplane Arrangements

arXiv 2609.39855 ↗First posted 30 Sep 2026cs.LG math.PRcited by 0

Not on the map. Why?

Abstract (arXiv)

We study the width required for a randomly initialized hidden layer of a neural network to achieve rank lifting. Namely, given a dataset X ∈ ℝm × d of m, d-dimensional input vectors separated by an angle of at least θ, we consider the random feature matrix σ(XR), where R is standard Gaussian. For positively homogeneous nonpolynomial activations, which include sign, Heaviside, ReLU, and ReLU powers among others, we prove that n gtrsim frac1θmaxleftm,logleft(frac1δright)right neurons suffice for σ(XR) to have full row rank m with probability at least 1-δ. This dimension-free bound exponentially improves the previous general-dimensional guarantee for sign features (Drago et al., 2026) and is essentially tight. The proof shows that one random feature column escapes every proper subspace of ℝm with probability Omega(θ), using a coupling of nearby Gaussian directions and a local crossing of the induced hyperplane arrangement. We also study stable rank lifting, where the goal is to establish a quantitative analogue of exact rank lifting, i.e., a lower bound on the smallest eigenvalue of the empirical feature Gram matrix in high-probability. Our analysis unifies and generalizes stable rank guarantees for all q-homogeneous non-polynomial activations following prior work in Panigrahi et al. (2020) and Song (2026). In particular, we combine a diagonally dominant Taylor tail of the population kernel with truncation and matrix concentration, to show that for positively homogeneous nonpolynomial activations, stable rank lifting is achieved at width n gtrsim Cq fracmθ2q+1 log^2q+frac12left(fracmθright) logleft(fracmδright), where q is the degree of the activation and C > 0 is some universal constant.

Key facts. No citing papers in the map yet (data through 14 Oct 2026). Builds on 36 of its 62 references that are in the map. First posted on arXiv 30 Sep 2026.

Builds on

36 of 62 references.

References · 36

  1. 2018Neural Tangent Kernel: Convergence and Generalization in Neural Networkscited by 2,621
  2. 2018Reconciling modern machine learning practice and the bias-variance trade-offcited by 927
  3. 2018A Convergence Theory for Deep Learning via Over-Parameterizationcited by 787
  4. 2018Gradient Descent Provably Optimizes Over-parameterized Neural Networkscited by 659
  5. 2019The generalization error of random features regression: Precise asymptotics and double descent curvecited by 413
  6. 2015An Introduction to Matrix Concentration Inequalitiescited by 397
  7. 2014On the Number of Linear Regions of Deep Neural Networkscited by 381
  8. 2018Just Interpolate: Kernel "Ridgeless" Regression Can Generalizecited by 190
  9. 2019Towards moderate overparameterization: global convergence guarantees for training shallow neural networkscited by 176
  10. 2016Generalization Properties of Learning with Random Featurescited by 164
  11. 2017Bounding and Counting Linear Regions of Deep Neural Networkscited by 161
  12. 2015On the Equivalence between Kernel Quadrature Rules and Random Feature Expansionscited by 138
24 more
  1. 2016Toward Deeper Understanding of Neural Networks: The Power of Initialization and a Dual View on Expressivitycited by 138
  2. 2020Random Features for Kernel Approximation: A Survey on Algorithms, Theory, and Beyondcited by 109
  3. 2020Tight Bounds on the Smallest Eigenvalue of the Neural Tangent Kernel for Deep ReLU Networkscited by 87
  4. 2020Deep Equals Shallow for ReLU Networks in Kernel Regimescited by 85
  5. 2020The Interpolation Phase Transition in Neural Networks: Memorization and Generalization under Lazy Trainingcited by 84
  6. 2017A Random Matrix Approach to Neural Networkscited by 80
  7. 2020Spectra of the Conjugate Kernel and Neural Tangent Kernel for linear-width neural networkscited by 77
  8. 2020Deep Neural Tangent Kernel and Laplace Kernel Have the Same RKHScited by 74
  9. 2018Random Fourier Features for Kernel Ridge Regression: Approximation Bounds and Statistical Guaranteescited by 71
  10. 2022Spectrum of inner-product kernel matrices in the polynomial regime and multiple descent phenomenon in kernel ridge regressioncited by 45
  11. 2019Neural Networks Learning and Memorization with (almost) no Over-Parameterizationcited by 23
  12. 2022Characterizing the Spectrum of the NTK via a Power Series Expansioncited by 22
  13. 2014Randomized Nonlinear Component Analysiscited by 18
  14. 2023Mildly Overparameterized ReLU Networks Have a Favorable Loss Landscapecited by 17
  15. 2024A Random Matrix Theory Perspective on the Spectrum of Learned Features and Asymptotic Generalization Capabilitiescited by 16
  16. 2019The capacity of feedforward neural networkscited by 14
  17. 2019Effect of Activation Functions on the Training of Overparametrized Neural Netscited by 14
  18. 2021The Separation Capacity of Random Neural Networkscited by 14
  19. 2024The Positivity of the Neural Tangent Kernelcited by 13
  20. 2024Bounds for the smallest eigenvalue of the NTK for arbitrary spherical data of arbitrary dimensioncited by 13
  21. 2022Randomly Initialized One-Layer Neural Networks Make Data Linearly Separablecited by 6
  22. 2025Beyond ReLU: How Activations Affect Neural Kernels and Random Wide Networkscited by 3
  23. 2025Condition Numbers and Eigenvalue Spectra of Shallow Networks on Spherescited by 2
  24. 2026Tight Worst-Case Bounds for the Smallest Eigenvalue of ReLU NTK Gram Matricescited by 2

Built on by

Not cited yet.