CS Paper Radar

Dimension-Free Rank Lifting from Random Hyperplane Arrangements

Luca Becchetti, Matteo Russo, Ruben Skorupinski

cs.LG math.PR ·submitted 2026-09-30 14:43 UTC · v1
theory

Abstract

We study the width required for a randomly initialized hidden layer of a neural network to achieve rank lifting. Namely, given a dataset $X \in \mathbb{R}^{m \times 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 \frac{1}θ\max\left\{m,\log\left(\frac{1}δ\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 $\mathbb{R}^m$ with probability $Ω(θ)$, 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 C^q \frac{m}{θ^{2q+1}} \log^{2q+\frac{1}{2}}\left(\frac{m}θ\right) \log\left(\frac{m}δ\right),$$ where $q$ is the degree of the activation and $C > 0$ is some universal constant.

Closest papers

Nearest neighbours by meaning across the whole index.

Subgroup Rank-1 Lattice for Practical High-dimensional Black-box Integral Approximation

cs.LG ·2026-09-28 ·Yueming Lyu
theory similarity 0.60
Abstract

Estimating integrals of black-box, high-dimensional functions, from expectations and kernel mean embeddings to the softmax kernel in self-attention, is a basic subroutine in machine learning. Rank-1 lattice rules suit this setting: they query the integrand only at a fixed point set and need no gradients. When the $n$ points serve as a design matrix $X\in\mathbb{R}^{n\times d}$ for a feature map, however, computing $Ψ(X)^\top v$ or $Ψ(X)w$ for an elementwise nonlinearity $Ψ$ costs $O(nd)$ time and memory for any standard quasi-Monte Carlo point set. We study subgroup rank-1 lattices, whose Korobov generator $(1,t,\dots,t^{d-1})$ uses a scalar $t$ of fixed multiplicative order $m$. Splitting $\mathbb{F}_n^\times$ into cosets of $\langle t\rangle$ reduces both maps to short cyclic correlations evaluated by FFT, giving exact results for arbitrary $Ψ$ in $O(n\log m)$ time and $O(n)$ memory, without forming $X$. Since fixing $m$ falls outside classical component-by-component theory, we prove convergence directly: via resultants with the cyclotomic polynomial $Φ_m$, the squared worst-case error in the Korobov space decays as $O(n^{-(α-1)/(m-1)})$ for prime $m\ge d+1$, and this threshold is exact. Using the splitting of $n$ in $\mathbb{Q}(ζ_m)$, averaging over the $m-1$ admissible generators improves the constant by a factor $Θ(m-1)$. Empirically, the subgroup lattice beats Gaussian and orthogonal random features and scrambled Sobol' and Halton points in 49 of 54 synthetic kernel-estimation settings and all 45 softmax-attention settings on nine real datasets, and builds a sample set with $d=2048$, $n\approx4.1\times10^7$ in 2.3 ms.

0.27

"Deep lifts": Neural networks can generalize even with the dumbest optimizer

cs.LG ·2026-10-16 ·Sunil Madhow, Yu-Xiang Wang
similarity 0.59
Abstract

Given a labeled dataset $\{(x_i, y_i)\}_{i = 1}^n$, consider drawing a parameter vector $\hatθ$ uniformly at random from those that interpolate the data within a width-$W$ depth-$D$ ReLU architecture with continuous weights bounded within $[-M, M]$. We study the generalization properties of $\hatθ$ in the case where the dataset can, in fact, be explained by a smaller $w$-by-$d$ ReLU network. Despite the obliviousness of the selection rule for $\hatθ$, it adaptively generalizes at the rate $\tilde O\left(\frac{wdWD}{n}\right)$, rather than being governed by the VC dimension of the full $W$-by-$D$ hypothesis class. The reason is due to a particular inductive bias in ReLU networks: the $w$-by-$d$ parameter *witnesses* an exponential volume of $W$-by-$D$ interpolating parameters, which dwarfs the volume of poorly generalizing parameters (conditioned on interpolation). We explicitly construct this set of near-equivalent $W$-by-$D$ parameters by a proof technique called *deep lifting*, and then tie the achievable volume to stability properties of the $w$-by-$d$ witness. Examples show that these techniques allow us to convert approximation-theoretic results into generalization guarantees for nonparametric classes. We further show that generalization of uniform-random interpolators can survive label corruptions.

0.31

Lifting Finite-Sample Gaussian Approximation of Wide Neural Networks to Functional Convergence

cs.AI stat.MLcs.LG ·2026-10-13 ·Luis Wiederhold, Nil Ayday, Debarghya Ghoshdastidar
similarity 0.59
Abstract · 19 pages, 1 table, 1 figure, preprint

Randomly initialised neural networks of width $m$ converge to Gaussian processes as $m \to \infty$, with two types of quantitative bounds characterising this convergence. Finite-sample bounds compare the network with its Gaussian limit at a fixed finite sample set, on an arbitrary domain, in the quadratic Wasserstein distance $\mathcal W_2$, achieving a convergence rate of $m^{-1/2}$ with explicit constants. However, these constants grow with the number of samples, so the bound becomes uninformative as the sample set is refined. Functional bounds remove that dependence by comparing the two as random functions, at the price of spherical input, metrics weaker than $\mathcal W_2$, or slower rates. In this paper, we therefore lift a finite-sample bound to a functional one. The lifting refines the sample set until it is dense in the domain, so the bound must first be made independent of the number of samples. We achieve this by measuring the error per sample, which makes the constant uniform. For a polynomial activation and any compact input set, this gives a rate of $m^{-1/2}$ in the supremum norm, with an explicit constant.

0.27

The rank of the random $k$-XORSAT matrix beyond satisfiability

cs.DM math.PRmath.CO ·2026-10-19 ·Amin Coja-Oghlan, Maurice Rolvien
similarity 0.59
Abstract

The random $k$-XORSAT matrix is an $m\times n$ random matrix $\mathbf A$ over $\mathbb F_2$ that represents a random instance of the $k$-XORSAT problem. Each row of $\mathbf A$ contains precisely $k\geq3$ non-zero entries in random positions. The rows are drawn independently. The matrix $\mathbf A$ is known to have full row rank for $m/n$ below the random $k$-XORSAT satisfiability threshold, which is known explicitly [Dubois, Mandler~2002; Pittel, Sorkin~2016]. Motivated by a problem from quantum game theory and refining a result of Cooper, Frieze and Pegden (2019), we determine the limiting distribution of the rank of $\mathbf A$ beyond the satisfiability threshold.

0.25

Quadratic Weak-to-Strong Generalization in Random Feature Networks via Random Matrix Theory

cs.LG stat.MLmath.PR ·2026-10-06 ·Deborah Oliveira, Elliot Paquette
theory similarity 0.59
Abstract

Weak-to-strong generalization is the phenomenon where a strong student model trained with labels produced by a weak teacher model is able to generalize better than the teacher. In this paper, we study this phenomenon in two-layer random feature networks where the model strength is determined by its width. Using tools from random matrix theory, we derive deterministic equivalents for the population errors of an optimally trained teacher and a student trained with gradient flow. For ReLU activation and a pure spherical harmonic target, we obtain sharp asymptotics under a Gaussian universality assumption, showing a quadratic improvement: the student error scales as the square of the teacher error. These results attain the general lower bound of Medvedev at al (2025). We also analyze how the student behaves under more general stopping times and targets supported on multiple harmonic degrees, characterizing the regimes in which weak-to-strong generalization occurs and identifying the transition between quadratic, non-quadratic, and no improvement.

0.17

RDT based upper bounds on the largest average submatrix values

cs.IT math.PRcond-mat.stat-mechmath.ST ·2026-09-16 ·Mihailo Stojnic
theory similarity 0.58
Abstract

We study statistical variants of the classical largest average submatrix problem. For small submatrices (where the dimension is less than linearly proportional to the original matrix), the problem is typically well understood and believed to exhibit the statistical-computational gap (SCG). However, analytical treatment of both the information-theoretic and algorithmic aspects of the linear regime remains challenging, and no mathematically rigorous results have yet arrived anywhere close to proving or disproving SCG existence in this setting. Focusing on the linear regime, we make strong progress in several key directions: 1) We develop a generic Random Duality Theory (RDT) framework to characterize largest average submatrix values. 2) Using the plain RDT variant, we obtain closed-form upper bounds as explicit functions of dimensionality proportionality parameters. 3) We demonstrate that a lifted RDT variant strictly improves upon the plain RDT within a certain linear range of submatrix dimensions. 4) For small submatrices where the dimensional proportionality constants approach zero, we prove that our results match both the replica results from [34] (obtained via one-step replica symmetry breaking) and the sublinear results from [18,45].

0.30

Formalizing the Intrinsic Dimension of Objective Landscapes by a Generalized Notion of Co-dimension

cs.LG stat.MLmath.MG ·2026-10-29 ·Ernesto Araya, Gitta Kutyniok, Weilin Li, Johannes Maly, Manjot Singh
similarity 0.58
Abstract

In this work, we formalize the concept of intrinsic dimension of objective landscapes introduced in Li et al. (2018), which measures the structural complexity of learning problems by training along randomly generated subspaces. We define the intrinsic dimension of a set $Θ\subset\mathbb{R}^p$ as the minimal dimension $d_{\mathrm{int}}(Θ)$ such that a random plane of dimension $d_{\mathrm{int}}(Θ)$ in $\mathbb{R}^p$ intersects $Θ$ with probability one. We show that it is a generalized notion of co-dimension that depends on the global geometry of $Θ$. We study mathematical properties of the intrinsic dimension and develop techniques to estimate the intrinsic dimension of sets $Θ$ that arise in learning problems. More specifically, we derive upper and/or lower bounds where $Θ$ is the set of optimal parameters in student-teacher settings with shallow and deep ReLU networks, including finite and infinite sample cases, and with and without regularization. We discuss how our theory leads to novel types of generalization bounds, thereby showing that the intrinsic dimension is a measure of learning complexity. Our results connect techniques from seemingly different areas of machine learning research such as classification of symmetries of ReLU networks and stochastic geometry.

0.15

Exact Limits of Random Projections for Preserving Geometry: Distance Recovery, Nearest-Neighbor Rankings, and Covariance Shape in Gaussian Models

cs.LG cs.ITmath.NAmath.PR+1 ·2026-09-02 ·Piyush Sao
code/data similarity 0.58
Abstract · 41 pages, 6 figures, 4 tables. Reproducibility code: https://github.com/piyush314/random-projection-geometry (pinned as a submodule). Compan…

The Johnson-Lindenstrauss (JL) lemma guarantees that a random projection of $n$ points to $m=O(\varepsilon^{-2}\log n)$ dimensions preserves pairwise squared distances within relative error $\varepsilon$ with high probability, and this dimension order is asymptotically optimal. In high dimensions, however, distances concentrate around a baseline while key geometric information lies in much smaller fluctuations. We show that the JL bound can therefore be uninformative about retained geometry: an independent Gaussian replacement map can satisfy it even though the replacement cloud is independent of the original data. We then ask how well any decoder can recover a feature $f(D)$ of a squared distance $D$ from a linear sketch. Under squared-error loss, the optimal decoder is conditional expectation, so recovery defines a linear operator whose singular values quantify feature recovery. For isotropic Gaussian data ($Σ=σ^2 I_d$), we diagonalize this operator in closed form. For fixed $k$ with $m,d-m\to\infty$, its $k$th singular value satisfies $\ell_k\approx(m/ d)^{k/2}$. This yields three sharp consequences. A rank-$m$ sketch retains at most an $m/d$ fraction of the variance of any feature of one squared distance. If $m\to\infty$ and $m/d\to0$, the expected Kendall correlation is $\frac{2}π\sqrt{m/d}(1+o(1))$; for fixed $q$, nearest- neighbor agreement tends to $1/q$. Yet one projection can satisfy the JL bound while mean Kendall correlation vanishes when $\log n\ll m\ll d$. After removing scale, Haar-averaged retained covariance-shape information is $(m/d)^2$. Thus JL distance preservation does not quantify the geometry available for comparison or inference.

0.38