The merged-staircase property

$O(d)$ samples of SGD are $O(1)$ time of a $P$-dimensional PDE. Two approximations are chained. Propagation of chaos (Mei, Misiakiewicz and Montanari) puts the neurons' empirical measure on the mean-field PDE; a batch gradient is a $d$-dimensional subgaussian vector, which forces $\eta\lesssim b/d$, so $T/\eta$ steps use $n=Tb/\eta\asymp Td$ samples. Then symmetry reduces $d$ to $P$: flipping the signs of every neuron's noise coordinates maps solutions to solutions and fixes the initialization, so the network never depends on $r$, and $\langle v,r\rangle$ is a Rademacher sum close to $\|v\|_2G$ up to times $O(1)$. The equivalence is then the triangle inequality both ways, so learnability in $O(d)$ is a property of a fixed, $d$-free gradient flow started with the first layer at exactly zero.

Coordinates outside the staircase closure never move, which proves necessity. Take the largest MSP subfamily $\mathcal S^*$ and let $\Omega$ be the coordinates it never touches, so every remaining set contains at least two coordinates of $\Omega$. Integrating $z_i$ out of the first-layer drift for $i\in\Omega$ ($\mathbb E_{z_i}[F z_i]$ is half the difference of $F$ at $z_i=\pm1$) bounds each contribution by a weight on $\Omega$: for the network's own output, a monomial without $i$, and a monomial with $i$ and a second fresh $j$, $$\big|\mathbb E[\hat f\,\sigma'z_i]\big|\lesssim(1+t)|u_i|,\qquad \big|\mathbb E[\chi_S\sigma'z_i]\big|\le\|\sigma''\|_\infty|u_i|\ (i\notin S),\qquad \big|\mathbb E[\chi_S\sigma'z_i]\big|\le\|\sigma''\|_\infty|u_j|\ (j\in S\cap\Omega,\ j\ne i).$$ So $m_t=\max_{i\in\Omega}|u_i|$ obeys $\dot m_t\lesssim(1+t)^2m_t$ from $m_0=0$, and Grönwall keeps it at zero; the network then has zero Fourier coefficient on every set outside $\mathcal S^*$, and $R(\bar\rho_t)\ge\sum_{S\notin\mathcal S^*}\hat h_*(S)^2$. The zero start is the $d\to\infty$ limit of a $d^{-1/2}$ overlap: at finite $d$ SGD can leave this saddle, but only with more than $O(d)$ samples.

Sufficiency reduces to one nonsingular $2^P\times2^P$ kernel. The proof picks convenient hyperparameters: no penalties, $\mu_w=\delta_0$ (no smoothing), $a\sim\mathrm{Unif}[-1,1]$, and two phases. In Phase 1 only the first layer moves, for a short time $T_1$, so each neuron's weights are a deterministic function $u^{T_1}(a)$ of its output weight, the only source of diversity. In Phase 2 only the second layer moves, which is kernel gradient flow, $$K^{T_1}(z,z')=\mathbb E_{a}\big[\sigma(\langle u^{T_1}(a),z\rangle)\sigma(\langle u^{T_1}(a),z'\rangle)\big],\qquad \tfrac{d}{dt}\|g_t\|^2=-g_t^\top K^{T_1}g_t\le-\lambda_{\min}(K^{T_1})\|g_t\|^2$$ for the residual $g_t$. On the finite cube, convergence at a $d$-free rate means exactly $\lambda_{\min}(K^{T_1})\gt0$: the features $\sigma(\langle u^{T_1}(a),z\rangle)$, as $a$ varies, must span all functions on $\{\pm1\}^P$.

On a vanilla staircase, coordinate $k$ grows like $(at)^{2^{k-1}}$, and binary exponents make the kernel nonsingular. Taylor-expanding $\sigma$ at zero, the only leading term in the drift of $u_k$ comes from $z_1\cdots z_k$: $$\dot u_k\approx a\,\alpha_k\,m_k\prod_{j\lt k}u_j\quad\Longrightarrow\quad u_k^t(a)\approx c_k\,(at)^{2^{k-1}},$$ with $m_r=\sigma^{(r)}(0)$ and $c_k\ne0$, made rigorous by a Grönwall induction. So $z_1$ moves first, then $z_2$, then $z_3$. A neuron's Fourier coefficient on $S$ is then about a constant times $a^{\beta(S)}$, $\beta(S)=\sum_{k\in S}2^{k-1}$, and binary expansion makes $\beta$ a bijection onto $\{0,\dots,2^P-1\}$, so the kernel is a rescaled, slightly perturbed Gram matrix of $1,a,\dots,a^{2^P-1}$ under uniform $a$, which is positive definite for small $T_1$. Each stage of this induction needs its derivative $\sigma^{(r)}(0)\ne0$.

For a general MSP support, learnability reduces to a polynomial not vanishing identically. Several monomials can feed the same coordinate and cancel, so the proof makes everything exactly polynomial: $P$ discrete first-layer steps of small size $\eta$ with a polynomial activation, so each weight is a polynomial in $\zeta=\eta a$, the residual's Fourier coefficients and $\sigma$'s derivatives. The network output stays $O(\eta)$ ($\mathbb Ea=0$), so the residual can be replaced by the target's coefficients at cost $O(\eta)$. Stacking $2^P$ independent neurons into a matrix $B$ and using $\lambda_{\min}(BB^\top)\ge\det(B)^2/\lambda_{\max}(B)^{2(2^P-1)}$ with anti-concentration of polynomials, $$\lambda_{\min}(K^{k_1})\ \ge\ c\ \mathbb E_{a}\big[\det M(\eta a,\beta,m)^2\big]\ \ge\ c\sum_\gamma\eta^{2|\gamma|}\big(|h_\gamma|-C\eta\big)_+^2,$$ with $h_\gamma$ the coefficients of the determinant in $\zeta$. So if that determinant is not the zero polynomial, a small $\eta$ gives a positive, $d$-free $\lambda_{\min}$.

The determinant is nonzero, because distinct inputs get distinct preactivation polynomials and high powers of distinct polynomials are independent. Treat the coefficients as variables; a nonzero polynomial is nonzero for almost every $\alpha$, and it suffices to treat a minimal MSP chain $S_1,\dots,S_P$ with $i\in S_i\subseteq[i]$. There the staircase order becomes degrees in $\zeta$: weight $i$ starts at degree $o_i=1+\sum_{i'\in S_i\setminus\{i\}}o_{i'}$ with a leading coefficient distinct across $i$, so the preactivations $r_z(\zeta)$ are distinct polynomials for distinct $z$. With $\sigma=(1+x)^L$ the entries are $(1+r_z)^L$, and Newman and Slater show that $L$-th powers of $m$ pairwise non-proportional polynomials are linearly independent once $L\ge8m^2$; with $m=2^P$, $L=2^{8P}$ suffices, and a nonzero Wronskian makes the determinant nonzero. The degenerate example is the measure-zero failure of this step: for $z_1+z_2+z_1z_3+z_2z_4$ the swap $(1\,2)(3\,4)$ fixes $h_*$ and the zero start, so every neuron has $u_1=u_2$, $u_3=u_4$, and $z=(1,-1,1,-1)$, $z'=(1,-1,-1,1)$ get the same preactivation although $h_*(z)=2\ne-2=h_*(z')$.

Lower bound for linear methods, by a dimension count on a subspace. Whatever the loss, the fitted predictor lies in the span of $\psi(x_1),\dots,\psi(x_n)$, a subspace of dimension at most $\min(n,q)$ that does not depend on which permutation of the target generated the labels. For unit $g$, Cauchy-Schwarz gives $\sum_i\langle g,f_i\rangle^2\le\|G\|_{op}$ for the Gram matrix $G$ of $M$ unit functions, so a fixed $r$-dimensional subspace captures on average at most $r\|G\|_{op}/M$ of their energy. Apply this to the permutation orbit of $f_*$ projected onto its degree-$k$ part and bound $\|G\|_{op}$ by a row sum, $m/\binom dk$. Projecting onto the degree-$k$ part is what improves on SQ arguments: staircases are SQ-learnable one degree at a time, so their SQ dimension is polynomial, but their top-degree part still requires $\binom{d}{\lfloor\eta P/2\rfloor}$.