Proof. Represent \(\theta_r=g_r/\left\| g_r \right\|_2\), where \(g_r\sim N(0,I_d)\). A standard chi-square concentration bound gives \(\left\| g_r \right\|_2^2\asymp d\) for all \(r\le K\) with probability at least \(1-\delta/4\). On the same event, Gaussian maxima give \(\max_j|g_r(j)|\le C\sqrt{\log d}\), proving ?? .

For each fixed \(p\ge2\) in the finite set needed below, concentration of the polynomial \(\sum_j |g_r(j)|^p\), together with the lower bound on \(\left\| g_r \right\|_2\), gives \[\sum_{j=1}^d |\theta_r(j)|^p \le C_{p,K,\delta}d^{1-p/2}.\] Taking \(p=2b\) proves ?? . Taking \(p=m\) proves ?? for even \(m\ge4\). For odd \(m\ge3\), the signed numerator \(\sum_j g_r(j)^m\) is a centered fixed-degree Gaussian polynomial with variance of order \(d\). Hypercontractivity and Markov’s inequality, or equivalently a standard tail bound for fixed-degree Gaussian chaoses, imply \[\left|\sum_{j=1}^d g_r(j)^m\right| \le C_{m,K,\delta}d^{1/2}\] with probability at least \(1-\delta/(4KM)\). Dividing by \(\left\| g_r \right\|_2^m\asymp d^{m/2}\) yields \(|P_{r,m}|\le C d^{-(m-1)/2}\), which is ?? for odd \(m\). Finally, \(P_{r,1}=\langle \theta_r,{\boldsymbol{1}}\rangle\) has the distribution of the first coordinate of a uniform vector on the sphere multiplied by \(\sqrt d\), so ?? follows from the usual spherical cap tail bound. A union bound over the finitely many \(r,m,b\) completes the proof, and ?? follows by multiplying the displayed bounds. ◻

Proof. This is a standard smooth Edgeworth expansion for triangular arrays. We include the argument to identify the signed quantities that enter the expansion. Let \(\psi(t)=\mathbb{E}e^{itV}\) be the characteristic function of \(V\). The characteristic function of \(S_w\) is \[\prod_{j=1}^d\psi(tw_j) =\exp\left\{\sum_{j=1}^d\log\psi(tw_j)\right\}.\] Expanding \(\log\psi(u)\) through order \(2J+2\) gives \[\sum_{j=1}^d\log\psi(tw_j) = -\frac{t^2}{2} + \sum_{m=1}^{2J+2}\frac{(it)^m}{m!}\Delta_m(w,V) +\operatorname{Err}_{J}(t,w),\] where the term \(-t^2/2\) is the reference Gaussian exponent and where \(\operatorname{Err}_{J}\) is bounded by \[C_J |t|^{2J+3}\sum_j |w_j|^{2J+3}\mathbb{E}(1+|V|^{2J+3}).\] Thanks to the subgaussianity assumption and the moment bounds on \(w\), we have \(\sum_j |w_j|^{2J+3}\le C d^{-(2J+1)/2}\). Fourier inversion for smooth test functions, after multiplying by a standard cutoff and using bounded derivatives of \(h\), allows the characteristic-function expansion to be integrated term by term. Expanding the exponential of \(\sum_m (it)^m\Delta_m/m!\) and keeping only monomials of formal order at most \(J\) gives ?? ; all discarded terms and the Fourier-tail contribution are bounded by \(C_{h,J}d^{-(J+1)/2}\). Equivalently, the coefficients can be written as Gaussian expectations of derivatives through the formal identity \[\mathbb{E}h(G) (it)^m\quad \longleftrightarrow\quad \mathbb{E}h^{(m)}(G),\] which proves the stated form of the constants. ◻

Proof. Let \(\eta\in C_c^\infty(\mathbb{R})\) satisfy \[0\le \eta\le 1,\qquad \eta(x)=1 \text{ for } |x|\le 1,\qquad \eta(x)=0 \text{ for } |x|\ge 2.\] For \(R\ge 1\), define \[h_R(x):=h(x)\eta(x/R).\] Since \(\mathcal{H}\) is finite and the derivatives of the functions in \(\mathcal{H}\) have polynomial growth, there is a constant \(C_{\mathcal{H}}\) such that \[|h^{(r)}(x)|\le C_{\mathcal{H}}(1+|x|)^Q, \qquad h\in\mathcal{H},\quad 0\le r\le L .\] By Leibniz’ rule, \[h_R^{(r)}(x) = \sum_{a=0}^r \binom{r}{a} h^{(a)}(x) R^{-(r-a)}\eta^{(r-a)}(x/R).\] The derivatives of \(\eta\) are supported on \(|x|\le 2R\), and \(R\ge1\). Therefore, uniformly in \(h\in\mathcal{H}\), \[\|h_R\|_{C_b^L} \le C_{\mathcal{H},L,\eta}(1+R)^Q .\]

We apply the quantitative bounded-derivative Edgeworth expansion ?? to \(h_R\). This gives \[\label{eq:edgeworth95d3} \mathbb{E} h_R(S_w) = \sum_{\ell\in\mathfrak E_J} c_{h_R,\ell} \prod_{m=1}^{2J+2}\Delta_m(w,V)^{\ell_m} + O_{\mathcal{H},J}\!\left( (1+R)^Q d^{-(J+1)/2} \right),\tag{11}\] uniformly in \(h\in\mathcal{H}\) and \(w\).

It remains to compare \(h_R\) with \(h\). First, the variables \(S_w\) have uniform subgaussian tails. Indeed, \(V-\mathbb{E}V\) is subgaussian, and \(\|w\|_2\le1\), while \[|\mathbb{E} S_w| = |\mathbb{E}V|\,\Big|\sum_j w_j\Big| \le C .\] Hence there are constants \(C,c>0\), independent of \(d,w\), such that \[\mathbb{P}(|S_w|>t)\le C e^{-c t^2}, \qquad t\ge0.\] Consequently, \[\mathbb{E}\left[(1+|S_w|)^Q\mathbf{1}_{\{|S_w|>R\}}\right] \le C_{\mathcal{H},Q} (1+R)^Q e^{-cR^2}. \label{eq:edgeworth95d5}\tag{12}\] Since \(h_R=h\) on \([-R,R]\), 12 implies \[\sup_{h\in\mathcal{H}} \left| \mathbb{E} h(S_w)-\mathbb{E} h_R(S_w) \right| \le C_{\mathcal{H},Q}(1+R)^Q e^{-cR^2}. \label{eq:edgeworth95d6}\tag{13}\]

Next we compare the Edgeworth coefficients. Each coefficient \(c_{h,\ell}\) is a finite linear combination, depending only on \(J\) and \(\ell\), of Gaussian expectations of derivatives of \(h\) up to order \(2J+2\). Therefore, using again Leibniz’ rule and the fact that \(h_R=h\) on \([-R,R]\), \[|c_{h_R,\ell}-c_{h,\ell}| \le C_{\mathcal{H},J} (1+R)^Q e^{-cR^2}. \label{eq:edgeworth95d7}\tag{14}\] The cumulant factors are uniformly bounded over admissible weights. Indeed, \[|\Delta_1(w,V)|\le C,\qquad |\Delta_2(w,V)|\le C,\] and for \(m\ge3\), \[|\Delta_m(w,V)| \le C_m\sum_j |w_j|^m \le C_m d^{1-m/2} \le C_m .\] Since \(\mathfrak E_J\) is finite, 14 gives \[\sum_{\ell\in\mathfrak E_J} |c_{h_R,\ell}-c_{h,\ell}| \prod_{m=1}^{2J+2} |\Delta_m(w,V)|^{\ell_m} \le C_{\mathcal{H},J}(1+R)^Q e^{-cR^2}. \label{eq:edgeworth95d8}\tag{15}\]

Combining 11 , 13 , and 15 , we obtain \[\mathbb{E} h(S_w) = \sum_{\ell\in\mathfrak E_J} c_{h,\ell} \prod_{m=1}^{2J+2}\Delta_m(w,V)^{\ell_m} + O_{\mathcal{H},J}\!\left( (1+R)^Q d^{-(J+1)/2} +(1+R)^Q e^{-cR^2} \right).\] Finally choose \[R=R_d=A\sqrt{\log d},\] with \(A\) large enough that \[(1+R_d)^Q e^{-cR_d^2} \le C_{\mathcal{H},J} d^{-(J+1)/2}.\] Then \[(1+R_d)^Q d^{-(J+1)/2} \le C_{\mathcal{H},J} (\log d)^{Q/2}d^{-(J+1)/2},\] which proves the claim. The finitely many small values of \(d\) can be absorbed into the constant. ◻

Proof. The proof proceeds by induction on \(r\). For \(r=1\), the summands in \(R_{1,a}\) are independent standard Gaussians, and therefore \[R_{1,a}\sim N(0,1-\theta_1(a)^2).\] Expanding the map \(\sigma^2\mapsto \mathbb{E}h(\sigma G)\) around \(\sigma^2=1\) gives \[\mathbb{E}h(R_{1,a}) = \sum_{q=0}^{\lfloor(J-1)/2\rfloor} c_{h,q}\theta_1(a)^{2q} +O\bigl(|\theta_1(a)|^{J}\bigr),\] which has the required tensorized form because \(\left\| \theta_1^{\odot(b+J)} \right\|_2\le C d^{-(J+b-1)/2}\).

Assume the claim holds up to layer \(r-1\) for all test functions needed below. A generic input to layer \(r\) has the form \[V=\phi(Y_{r-1}),\] where \(Y_{r-1}\) is a generic coordinate of the previous preactivation. The cumulants \(\chi_m(V)\), for \(m\le 2J+4\), are polynomials in moments \(\mathbb{E}\phi(Y_{r-1})^a\) of bounded degree. Applying the induction hypothesis to the finite family of functions \(x\mapsto \phi(x)^a\) shows that each cumulant has a finite expansion in signed power sums of the previous directions, with the tensorized remainder bound ?? .

Now write \[R_{r,a}=\sum_{j\ne a}\theta_r(j)V_j,\] where \(V_j\) are iid copies of \(V\). We then apply Lemma 3 together with the slackened truncation convention of Remark 5 to the deleted weights \(w_j=\theta_r(j)\mathbf{1}_{\{j\ne a\}}\). Their signed power sums are exactly \[\sum_j w_j^m=P_{r,m}-\theta_r(a)^m. \label{eq:app-deleted-power-sum}\tag{18}\] Substituting the inductive cumulant expansions and 18 into ?? , and then expanding the finite polynomial, produces precisely the finite sum in ?? . The factors \(P_{u,1}\) that appear from mean shifts have formal order zero and are bounded by \(C\) on the spherical event. The Edgeworth remainder is \(O(d^{-J/2})\), and all discarded local coordinate monomials have coordinate degree at least \(J\). Multiplying by \(\theta_r^{\odot b}\) and using Lemma 1 therefore gives ?? . This proves the induction step. ◻

Proof. The variables \(U_r\) and \(D_r\) are generated from the independent innovations \(\xi,R_1,\ldots,R_K\) by the smooth recursion 16 . For fixed innovations, the map \[\beta=(\beta_1,\ldots,\beta_K) \mapsto \prod_{r=1}^K D_r\] is \(C^K\). Taylor expansion around \(\beta=0\) to total degree \(K-1\) gives \[\prod_{r=1}^K D_r = \sum_{|\alpha|\le K-1} \beta^\alpha H_\alpha(\xi,R_1,\ldots,R_K) +\widetilde{R}_K(\beta,\xi,R_1,\ldots,R_K),\] where the derivatives defining \(H_\alpha\) are finite sums of products of functions of the single variables \(\xi,R_1,\ldots,R_K\). This follows by induction from the recursion: differentiating \(U_r=\phi(R_r+\beta_rU_{r-1})\) or \(D_r=\phi'(R_r+\beta_rU_{r-1})\) only produces products of derivatives of \(\phi\) evaluated at one innovation and lower-order derivatives of previous \(U_s\)’s. Since the innovations are independent, taking expectation factors each product, yielding ?? .

The Taylor remainder is bounded by a finite sum of terms of the form \[C\prod_{r=1}^K |\beta_r|^{\alpha_r} M_{\boldsymbol{i}}, \qquad |\alpha|=K,\] where \(M_{\boldsymbol{i}}\) has bounded second moment uniformly in \(d\). This uses the boundedness, or polynomial growth together with subgaussianity, of the required derivatives of \(\phi\). After multiplication by the base factor, a term with \(|\alpha|=K\) has tensor norm \[\prod_{r=1}^K \left\| \theta_r^{\odot(\alpha_r+1)} \right\|_2 \le C d^{-K/2}\] by Lemma 1. Summing over the finitely many \(\alpha\)’s proves ?? . ◻

Proof of Theorem 4. Work on the high-probability event of Lemma 1 with \(M=2K+2\), and also on the event where the recursive Edgeworth expansions of Lemma 4 hold for the finite family of test functions generated by Lemma 5. This combined event has probability at least \(1-\delta\), after adjusting constants.

We now insert the path expansion ?? into 19 . Fix a path degree \(\alpha\) with \(|\alpha|\le K-1\). The corresponding tensor factor from the base spike and the path monomial is \[\bigotimes_{r=1}^K \theta_r^{\odot(\alpha_r+1)},\] which has formal tensor order \(|\alpha|\).

Set \[J_\alpha := K-|\alpha|.\] We invoke the slackened Edgeworth convention of Remark 5: for each coefficient factor in the separated product, we retain only coefficient terms of formal order strictly smaller than \(J_\alpha\). The explicit coefficient terms of formal order exactly \(J_\alpha\), together with the analytic polynomial-growth Edgeworth remainder from Lemma 3, are placed in the remainder. After multiplication by the path tensor of formal order \(|\alpha|\), this contributes \[O\!\left(d^{-(|\alpha|+J_\alpha)/2}\right) = O(d^{-K/2}).\] Thus the retained atoms have total formal order \(q<K\), and hence belong to the levels \(G_\theta^{[0]},\ldots,G_\theta^{[K-1]}\), while all order-\(K\) and smaller analytic remainders are absorbed into \(\mathcal{R}_K\).

Applying Lemma 4 with \(J=J_\alpha\) gives, for each factor \(\mathbb{E}h_{\alpha,a,r}(R_{r,i_r})\), a finite expansion in scalar power sums and local coordinate powers \(\theta_r(i_r)^v\). Multiplying the finitely many factors in the separated product and expanding produces terms of the form \[C_\tau \left(\prod_{u=1}^K\prod_{m=1}^{2K+2}P_{u,m}^{\ell_{\tau,u,m}}\right) \prod_{r=1}^K\theta_r(i_r)^{v_{\tau,r}},\] with coefficient formal order strictly smaller than \(J_\alpha\). Multiplying by the base factor and by the path monomial gives the rank-one tensor atom \[C_\tau \left(\prod_{u=1}^K\prod_{m=1}^{2K+2}P_{u,m}^{\ell_{\tau,u,m}}\right) \bigotimes_{r=1}^K \theta_r^{\odot(1+ \alpha_r+v_{\tau,r})}.\] Its formal order is \[|\alpha|+ \sum_{r=1}^K v_{\tau,r}+ \sum_{u=1}^K\sum_{m=1}^{2K+2}\ell_{\tau,u,m}\omega_m,\] which is strictly less than \(K\). Grouping all atoms with the same formal order \(q\in\{0,\ldots,K-1\}\) defines \(\mathcal{G}_\theta^{[q]}\) and yields ?? .

It remains to bound the accumulated errors. The path remainder is controlled by Lemma 5. For the coefficient errors, note that a coefficient error in the \(r\)-th factor is multiplied in Frobenius norm by \[\prod_{s\ne r}\left\| \theta_s^{\odot(\alpha_s+1)} \right\|_2 \cdot \left\| \theta_r^{\odot(\alpha_r+1)} \odot\rho_{h_{\alpha,a,r},r,J_\alpha} \right\|_2 \le C d^{-(|\alpha|+J_\alpha)/2}.\] Since \(J_\alpha=K-|\alpha|\), each such error is \(O(d^{-K/2})\). There are only \(O_K(1)\) path terms, separated products, and coefficient factors, so the total remainder satisfies \[\left\| \mathcal{R}_K \right\|_F \le C_{\phi,K,\delta}d^{-K/2}.\] The level-size estimate ?? follows immediately from Lemma 1, because every atom in level \(q\) has formal order \(q\).

We next prove the collected representation and the dictionary-rank bound. For any atom, set \[n_r:=b_{\tau,r}-1, \qquad n=(n_1,\ldots,n_K).\] The tensor-power part has formal order \(|n|\). The remaining order \(q-|n|\) is supplied by scalar Edgeworth power sums. Since all nonzero scalar orders \(\omega_m\), \(m\ge3\), are even, while \(P_{r,1}\) and \(P_{r,2}\) have order zero, we must have \(q-|n|\) even. There is also a parity constraint in mode one. The first path influence enters only through the symmetric product \(\beta_1\xi\), with \(\xi\sim N(0,1)\). Therefore \(\Lambda_{\boldsymbol{i}}\) is an even function of \(\beta_1\), so only even powers of \(\theta_1(i_1)\) beyond the base factor survive. Hence \(n_1\) is even. Thus all tensor profiles belong to \[\mathcal{N}_{K,q} = \{n\in\mathbb{N}_0^K:n_1\text{ even},\;|n|\le q, \;q-|n|\text{ even}\}.\] Collecting scalar coefficients with the same profile yields ?? . Since each profile gives one rank-one tensor atom, the CP rank is at most \(|\mathcal{N}_{K,q}|\).

Finally, compute this cardinality. Write \(|n|=p=q-2k\). If \(n_1=2a\), then the remaining \(K-1\) coordinates sum to \(p-2a\), giving \(\binom{K+p-2a-2}{p-2a}\) possibilities. Therefore \[|\mathcal{N}_{K,q}| = \sum_{k=0}^{\lfloor q/2\rfloor} \sum_{a=0}^{\lfloor(q-2k)/2\rfloor} \binom{K+q-2k-2a-2}{q-2k-2a}.\] Setting \(j=k+a\) gives \[|\mathcal{N}_{K,q}| = \sum_{j=0}^{\lfloor q/2\rfloor} (j+1)\binom{K+q-2j-2}{q-2j},\] which is ?? . This completes the proof of the theorem. ◻

Proof. We use a standard matrix Bernstein concentration argument combined with a recursive application of Wedin’s sine theorem, as in [2].

On an event where the population bias satisfies \(\left\| W_\theta \right\|_F\le b_d\), equations 10 and 21 imply \[M_*:=\mathsf{Mat}_a(\mathbb{E}_X[T_n\mid\theta]) =\lambda uv^\top+\mathsf{Mat}_a(W_\theta), \qquad \left\| \mathsf{Mat}_a(W_\theta) \right\|_\mathrm{op}\le b_d. \label{eq:population-matrix}\tag{24}\]

The matrices in the empirical average are independent across samples, but their entries are not independent within a sample. The following lemma is the needed matrix Bernstein bound, with truncation to handle the unbounded Lipschitz activation.

We now consider two elementary perturbation facts.

By 24 , \[\widehat M=\mathsf{Mat}_a(T_n)=\lambda uv^\top+E,\] where \[E:=\mathsf{Mat}_a(W_\theta)+\mathsf{Mat}_a(T_n-\mathbb{E}_XT_n).\] Thus \[\left\| E \right\|_\mathrm{op} \le \left\| W_\theta \right\|_F+ \left\| \mathsf{Mat}_a(T_n-\mathbb{E}_XT_n) \right\|_\mathrm{op} \le r_{n,d}\] with probability at least \(1-\delta\) over the samples, by Lemma 23. If \(r_{n,d}\le c\left| \lambda \right|\), Lemma 24 gives \[\operatorname{dist}_{\pm}(\widehat u,u)+\operatorname{dist}_{\pm}(\widehat v,v) \le C\frac{r_{n,d}}{\left| \lambda \right|}.\] Applying Lemma 25 to \(\widehat u\) and to \(\widehat v\) yields, for every factor in the left and right blocks, \[\operatorname{dist}_{\pm}(\widehat\theta_k,\theta_k) \le C_K\frac{r_{n,d}}{\left| \lambda \right|}.\] This proves ?? . ◻

Proof of Corollary 1. Let us consider the confidence levels \(\delta_\theta = 1/\log d\) over directions and \(\delta_{X} = d^{-c}\) over samples. Write \(\theta=g/\left\| g \right\|_2\), where \(g\sim N(0,I_d)\). Standard Gaussian concentration gives, after a union bound over \(r\le K\), \[\max_{1\le r\le K}\left\| \theta_r \right\|_\infty \le C\sqrt{\frac{\log(8Kd/\delta)}{d}} \label{eq:sphere-infty}\tag{25}\] with probability at least \(1-\delta/4\). Similarly, \[\sum_{j=1}^d\theta(j)=\frac{\sum_{j=1}^d g_j}{\left\| g \right\|_2},\] with \(\sum_jg_j\sim N(0,d)\), so \[\max_{1\le r\le K}\left| \sum_{j=1}^d\theta_r(j) \right| \le C\sqrt{\log(8K/\delta)} \label{eq:sphere-s}\tag{26}\] with probability at least \(1-\delta/4\). Standard moment concentration for \(g\sim N(0,I_d)\) gives, again after a union bound over \(r\le K\), \[\max_{r\le K}\sum_{j=1}^d\left| \theta_r(j) \right|^3 \le C_{K,\delta}d^{-1/2}, \qquad \max_{r\le K}\left\| \theta_r \right\|_4^4 \le C_{K,\delta}d^{-1} \label{eq:sphere-zeta-l4}\tag{27}\] with probability at least \(1-\delta/2\).

Then using 10 and the bounds on \(s\), \(\zeta\) and \(\|\theta\|_4^4\) from 26 , 27 , we have, with probability \(1- \delta_{\theta}\), \[\begin{align} \label{eq:frob95bound} \|W_\theta\|_F & \leq C_{\phi, K} \frac{(\log \log d)^{a_{K, \phi}/2}}{\sqrt{d}} \leq C_{\phi, K} \sqrt{\frac{\log d}{d}}~, \end{align}\tag{28}\] where the second inequality holds for sufficiently large \(d\). Concerning the empirical term, for \(\delta_X=d^{-c}\), \[\log((D_L+D_R)/\delta_X)=O_{K,c}(\log d), \qquad D_*=d^{\lceil K/2\rceil}.\] The simplified concentration bound ?? gives \[\begin{align} \label{eq:bernbound} \left\| \mathsf{Mat}_a(T_n-\mathbb{E}_XT_n) \right\|_\mathrm{op} &=O_{\phi,K,c}\left( \sqrt{\frac{d^{\lceil K/2\rceil}\log d}{n}} \right) \end{align}\tag{29}\] whenever the lower-order Bernstein envelope term is dominated.

Substituting 28 and 29 into Theorem 6 proves ?? . ◻

Proof. A CP rank-one tensor \(u_1\otimes\cdots\otimes u_R\) becomes the rank-one matrix \[\left(\bigotimes_{a\in S}u_a\right) \left(\bigotimes_{a\in S^c}u_a\right)^\top\] under the flattening \(\operatorname{Mat}_S\). Hence every CP-rank-\(m\) tensor has flattening rank at most \(m\). Applying the Eckart–Young theorem to the matrix \(\operatorname{Mat}_S(T)\) gives ?? . ◻

Proof. Write an input coordinate in the \(a\)-th copy as \(\mathbf{i}^{(a)}=(i^{(a)}_1,\ldots,i^{(a)}_K)\). Applying \(\partial_{\mathbf{i}^{(1)}}\cdots\partial_{\mathbf{i}^{(R)}}\) to the computation tree of the MSIM produces \(R\) derivative spines. At physical layer \(\ell\), two spines are in the same block precisely when, before the coordinate \(i_\ell^{(a)}\) is chosen, they have coalesced into the same upper-layer node. Thus the possible coalescence histories are exactly the chains \(\boldsymbol{\pi}=(\pi_1,\ldots,\pi_{K+1})\) in 31 .

Fix such a chain. During the transition \(\pi_\ell\preceq\pi_{\ell+1}\), each block \(B\in\pi_{\ell+1}\) is formed from \(n_\ell(B)\) child blocks of \(\pi_\ell\). Applying the Faà di Bruno formula therefore contributes one local derivative factor \(\phi^{(n_\ell(B))}\) at the corresponding activation node. The linear contraction at scale \(\ell\) contributes one factor of \(\theta_\ell\) for each block of \(\pi_\ell\), with all spines in the block sharing the same physical coordinate. Consequently the coordinate tensor associated with the chain is exactly \[\bigotimes_{\ell=1}^K \Delta_{\theta_\ell,\pi_\ell} =\mathcal{A}_{\boldsymbol{\pi}}(\theta).\] At zeroth Edgeworth order, the finitely many preactivations appearing along this genealogy are replaced by independent standard Gaussians. Hence the expectation of the derivative factors factorizes as \[\prod_{\ell=1}^{K}\prod_{B\in\pi_{\ell+1}} \mathbb{E}\phi^{(n_\ell(B))}(G) =c_\phi(\boldsymbol{\pi}),\] which proves ?? after summing over all chains.

We now derive the full two-parameter expansion. For each fixed chain, delete the finitely many coordinates lying on its \(R\) spines. The remaining preactivation variables entering the derivative factors are weighted sums of off-spine descendants with weights given by the coordinates of \(\theta_1,\ldots,\theta_K\). Applying the weighted Edgeworth expansion from the proof of Theorem 4 to this finite family of smooth test functions gives a finite expansion, up to total order \(A\), in monomials of the signed power sums \(P_{u,m}\) and in additional local coordinate powers. Every term is therefore of the decorated form \[c_\tau(\phi)P_\tau(\theta)\mathsf A_{S,\tau}(\theta), \qquad \tau\in\mathfrak T_{K,R,A}, \label{eq:decorated-term-form-in-proof}\tag{48}\] with \(P_\tau\), \(\mathsf A_{S,\tau}\), \(q(\tau)\) and \(\rho_S(\tau)\) defined in 42 –45 . Grouping the terms in 48 by the value of \(q(\tau)+\rho_S(\tau)=a\) gives exactly ?? , with \(\mathcal{M}_S^{[q,\rho]}\) defined by 46 . The terms with \(q(\tau)+\rho_S(\tau)>A\), together with the analytic Edgeworth remainders, are absorbed into \(\mathcal{E}_{S,A+1}\).

It remains to prove the rank and operator bounds. We first show the local matrix estimate. Let \(v_B\in\mathbb{R}^d\) be arbitrary vectors and set \(T_\pi:=\bigotimes_{B\in\pi}\Delta_{v_B,B}\). If \(B\) crosses the cut, then \[\operatorname{Mat}_S(\Delta_{v_B,B}) =\sum_{a=1}^d v_B(a) \left(\bigotimes_{r\in B\cap S}e_a^{(r)}\right) \left(\bigotimes_{r\in B\cap S^c}e_a^{(r)}\right)^\top,\] so its nonzero singular values are \(\{|v_B(a)|:a\in[d]\}\). If \(B\) does not cross the cut, the flattening is a row or column vector of Euclidean norm \(\|v_B\|_2\). Since singular values multiply under tensor products, \[\operatorname{rank}\big(\operatorname{Mat}_S(T_\pi)\big) \le d^{c_S(\pi)}, \qquad \big\|\operatorname{Mat}_S(T_\pi)\big\|_{\rm op} \le \prod_{B\in\chi_S(\pi)}\|v_B\|_\infty \prod_{B\notin\chi_S(\pi)}\|v_B\|_2 . \label{eq:decorated-local-rank-op}\tag{49}\] We now apply this estimate with \(v_B=\theta_\ell^{\odot b_{\tau,\ell,B}}\) at each layer and multiply over \(\ell\). On the event of Lemma 1, \[\|\theta_\ell^{\odot b}\|_2\le C d^{-(b-1)/2}, \qquad \|\theta_\ell^{\odot b}\|_\infty \le C(\log d)^{b/2}d^{-b/2} \le C(\log d)^{C_{K,R,A}}d^{-1/2}d^{-(b-1)/2}.\] Therefore \[\operatorname{rank}\big(\mathsf A_{S,\tau}(\theta)\big) \le d^{\rho_S(\tau)}, \qquad \|\mathsf A_{S,\tau}(\theta)\|_{\rm op} \le C(\log d)^{C_{K,R,A}} d^{-\rho_S(\tau)/2} d^{-\frac{1}{2}\sum_{\ell,B}(b_{\tau,\ell,B}-1)} . \label{eq:decorated-atom-rank-op}\tag{50}\] The scalar power-sum part satisfies, again by Lemma 1, \[|P_\tau(\theta)| \le C d^{-\frac{1}{2}\sum_{u,m}p_{\tau,u,m}\omega_m} . \label{eq:decorated-power-sum-bound}\tag{51}\] Combining 50 and 51 with the definition of \(q(\tau)\) gives \[\operatorname{rank}\big(P_\tau(\theta)\mathsf A_{S,\tau}(\theta)\big) \le d^{\rho_S(\tau)}, \qquad \big\|P_\tau(\theta)\mathsf A_{S,\tau}(\theta)\big\|_{\rm op} \le C(\log d)^{C_{K,R,A}}d^{-(q(\tau)+\rho_S(\tau))/2}. \label{eq:single-decorated-term-bound}\tag{52}\] There are only \(O_{K,R,A}(1)\) decorated symbols, and the coefficients \(c_\tau(\phi)\) are bounded in terms of \((\phi,K,R,A)\). Summing the terms with \(q(\tau)=q\) and \(\rho_S(\tau)=\rho\) proves ?? .

Finally, every term placed in \(\mathcal{E}_{S,A+1}\) has \(q(\tau)+\rho_S(\tau)\ge A+1\), and the analytic Edgeworth remainder has the same formal order by the choice of smoothness/truncation. Repeating the bound 52 for these terms gives ?? . For \(q=0\) there are no power-sum corrections and no extra coordinate powers, so 47 is exactly the flattening of the leading Gaussian expansion grouped by crossing complexity. This completes the proof. ◻

Proof. For a single block \(B\), the flattening of 32 is \[\operatorname{Mat}_S(\Delta_{u,B}) = \sum_{a=1}^d u(a) \left(\bigotimes_{r\in B\cap S}e_a^{(r)}\right) \left(\bigotimes_{r\in B\cap S^c}e_a^{(r)}\right)^\top .\] If \(B\) does not cross the cut, this is a row or column vector of norm \(\|u\|_2=1\), hence contributes one singular value equal to one. If \(B\) crosses the cut, the row vectors \(\{\otimes_{r\in B\cap S}e_a^{(r)}\}_{a=1}^d\) and the column vectors \(\{\otimes_{r\in B\cap S^c}e_a^{(r)}\}_{a=1}^d\) are orthonormal families, so the singular values are exactly \(|u(1)|,\ldots,|u(d)|\). Since \(\Delta_{u,\pi}\) is the tensor product over blocks \(B\in\pi\), the singular values multiply over crossing blocks. This proves ?? . The multiscale atom is the tensor product of the local layer atoms, so its singular values multiply over \(\ell=1,\ldots,K\), giving ?? . ◻

Proof. Write \(\theta=g/\|g\|_2\) with \(g\sim N(0,I_d)\). Choose constants \(0<a_0<a_1<\infty\) such that \(p_0:=\mathbb{P}(a_0\le |G|\le a_1)>0\) for \(G\sim N(0,1)\). By a binomial concentration bound, \[\#\{a\in[d]:a_0\le |g(a)|\le a_1\}\ge \frac{p_0}{2}d\] with probability at least \(1-e^{-c d}\). On the same event, after increasing constants, \(\|g\|_2\asymp\sqrt d\) and \(\|g\|_\infty\le C\sqrt{\log d}\) with probability at least \(1-\delta/K\) for all large \(d\). Union bounding over \(\ell\in[K]\) gives ?? –?? .

We now prove the singular-value statement on this event. Fix a coalescence chain \(\boldsymbol{\pi}\). By Lemma 10, the nonzero singular values of \(\operatorname{Mat}_S(\mathcal{A}_{\boldsymbol{\pi}}(\theta))\) are exactly \[\sigma(\mathbf{a}) =\prod_{(\ell,B)\in\mathsf C_S(\boldsymbol{\pi})} |\theta_\ell(a_{\ell,B})|, \qquad \mathbf{a}=(a_{\ell,B})_{(\ell,B)\in\mathsf C_S(\boldsymbol{\pi})} \in[d]^{\mathsf C_S(\boldsymbol{\pi})} . \label{eq:atom-singular-indexed-products}\tag{53}\] Here the coordinate choices are made independently for each crossing block \((\ell,B)\); if several crossing blocks occur at the same physical layer, they produce independent tensor-product factors and hence independent indices in 53 .

Restricting in 53 to assignments with \(a_{\ell,B}\in\mathsf G_\ell\) for every crossing block gives at least \[\prod_{\ell=1}^K |\mathsf G_\ell|^{|\chi_S(\pi_\ell)|} \ge (\gamma d)^{\rho_S(\boldsymbol{\pi})}\] singular values, counted with multiplicity. Each of these satisfies \[\sigma(\mathbf{a}) \ge (c_0d^{-1/2})^{\rho_S(\boldsymbol{\pi})} =c_0^{\rho_S(\boldsymbol{\pi})}d^{-\rho_S(\boldsymbol{\pi})/2}.\] Since \(\rho_S(\boldsymbol{\pi})\le (K-1)\lfloor R/2\rfloor\) is bounded in terms of \((K,R)\), the constants can be absorbed into a single \(c>0\). The upper bound follows similarly from \[\sigma(\mathbf{a}) \le \prod_{(\ell,B)\in\mathsf C_S(\boldsymbol{\pi})} \|\theta_\ell\|_\infty \le C_0^{\rho_S(\boldsymbol{\pi})} (\log d)^{\rho_S(\boldsymbol{\pi})/2}d^{-\rho_S(\boldsymbol{\pi})/2},\] and the boundedness of \(\rho_S(\boldsymbol{\pi})\) again absorbs constants into \(C\). ◻

Proof. We prove the lower bound first. Fix \(\rho\). Decompose \(M_S^{(R)}\) using ?? with \(A\ge \rho+1\): \[M_S^{(R)} = \mathcal{M}_S^{[0,\rho]} + L_{<\rho}+E_{>\rho},\] where \(L_{<\rho}\) is the sum of all components \(\mathcal{M}_S^{[q,\rho']}\) with \(q+\rho'\le\rho\) except the leading piece \((q,\rho')=(0,\rho)\), and \(E_{>\rho}\) is the sum of all components of total order \(q+\rho'>\rho\) plus the Edgeworth remainder. Since \(q\ge1\) in every term of \(L_{<\rho}\) or \(\rho'<\rho\), the rank bound ?? gives \[\operatorname{rank}(L_{<\rho}) \le C d^{\rho-1} \label{eq:lower-order-rank-bound}\tag{55}\] with the convention that this rank is zero when \(\rho=0\). The operator bounds ?? –?? give \[\|E_{>\rho}\|_{\rm op} \le C(\log d)^A d^{-(\rho+1)/2} = o(d^{-\rho/2}). \label{eq:higher-order-op-bound}\tag{56}\] By the non-cancellation assumption, \[\sigma_{\lfloor a_\rho d^\rho\rfloor} (\mathcal{M}_S^{[0,\rho]}) \ge b_\rho d^{-\rho/2}.\] The singular-value rank inequality \[\sigma_{j+r}(A+B) \ge \sigma_j(A)-\sigma_{r+1}(B)\] with \(A=\mathcal{M}_S^{[0,\rho]}\), \(B=L_{<\rho}+E_{>\rho}\), and \(r=\operatorname{rank}(L_{<\rho})\) gives, after decreasing constants, \[\sigma_{\lfloor c_\rho d^\rho\rfloor}(M_S^{(R)}) \ge c_\rho d^{-\rho/2},\] because \(d^{\rho-1}=o(d^\rho)\) and \(\|E_{>\rho}\|_{\rm op}=o(d^{-\rho/2})\). This proves ?? .

For the upper bound, write \(M_S^{(R)}=L_{\le\rho}+E_{>\rho}\), where \(L_{\le\rho}\) is the sum of all terms of total order \(q+\rho'\le\rho\). By ?? , \[\operatorname{rank}(L_{\le\rho})\le C d^\rho,\] and by ?? , \[\|E_{>\rho}\|_{\rm op} \le C(\log d)^A d^{-(\rho+1)/2}.\] Therefore all singular values after the first \(C d^\rho\) are bounded by the operator norm of \(E_{>\rho}\), which proves ?? . ◻

Proof. Combine Lemma 9 with the lower bound ?? . The plateau contains order \(d^\rho\) singular values of size at least order \(d^{-\rho/2}\), so its squared Frobenius mass is order one: \[d^\rho\cdot d^{-\rho}=1.\] This gives ?? and ?? . Taking \(\rho=\rho_{\max}\) gives ?? . ◻

Proof. This is the two-dimensional weighted Edgeworth expansion used throughout the proof of Theorem 4. We recall the calculation because the cancellation scale matters here. Replace the variables \((U_i,V_i)\) one at a time by Gaussian pairs \((G_{1,i},G_{2,i})\) with the same covariance. At the \(i\)-th replacement, Taylor-expand the test function around the partial sum excluding the \(i\)-th variable to order three. The order-one and order-two terms cancel because the means and covariance matrices match. The third-order contribution is \[\frac{u(i)^3}{6}\sum_{a,b,c\in\{1,2\}} \operatorname{cum}(W_a,W_b,W_c) \mathbb{E}\big[\partial_{abc}F(G_1,G_2)\big],\] up to an error of order \(O_{F,B}(|u(i)|^4)\). Summing over \(i\) gives the signed cubic factor \(\sum_i u(i)^3\) and the fourth-order remainder \(\sum_i u(i)^4\), proving ?? . The displayed coefficient ?? is the standard third-cumulant Edgeworth coefficient. Differentiating the same finite Taylor/Lindeberg expansion in \(\rho\) gives ?? ; the assumed moment and smoothness bounds justify differentiating under the expectation and control the remainders uniformly. ◻

Proof. Fix \(\ell\ge1\). Conditional on the lower layers, the corresponding features entering the \(\ell\)-th contraction form iid pairs \((U_i,V_i)_{i=1}^d\), where \((U_i,V_i)\) has the law of \[\left( Z^{(\ell-1)}_{i,i_{\ell+1},\ldots,i_K}(X), Z^{(\ell-1)}_{i,i_{\ell+1},\ldots,i_K}(X^\rho) \right).\] Their means may be nonzero at finite \(d\), but by the same induction used below they satisfy \[|\mathbb{E}U_i|+|\mathbb{E}V_i|\le C_{\phi,K,B_1(\theta)}\sum_{r<\ell}\eta(\theta_r).\] Their second moments are \[\mathbb{E}U_i^2=\mathbb{E}V_i^2=V_{\ell-1,\theta}, \qquad \mathbb{E}U_iV_i=Q_{\ell-1,\theta}(\rho), \qquad V_{\ell-1,\theta}:=Q_{\ell-1,\theta}(1).\] After centering the pairs, the induced preactivation mean is bounded by \(C_{\phi,K,B_1(\theta)}\sum_{r<\ell}\eta(\theta_r)\), because \(|P_{\ell,1}|\le B_1(\theta)\). This mean perturbation is absorbed into the same error budget by smoothness of \(\phi\). The two preactivations at layer \(\ell\) are \[S_\ell=\sum_{i=1}^d\theta_\ell(i)U_i, \qquad T_\ell=\sum_{i=1}^d\theta_\ell(i)V_i.\] Applying Lemma 12 with \(F(x,y)=\phi(x)\phi(y)\), after the harmless rescaling that matches the variance \(V_{\ell-1,\theta}\), gives \[Q_{\ell,\theta}(\rho) = \mathbb{E}\phi(S_\ell)\phi(T_\ell) = \Phi \big(V_{\ell-1,\theta},Q_{\ell-1,\theta}(\rho)\big) +\widetilde{\varepsilon}_{\ell,\theta}(\rho),\] where \(\Phi(v,q)\) denotes the Gaussian expectation \[\Phi(v,q):=\mathbb{E}\phi(G_1)\phi(G_2), \qquad \mathbb{E}G_1^2=\mathbb{E}G_2^2=v, \quad \mathbb{E}G_1G_2=q,\] and \(\|\widetilde{\varepsilon}_{\ell,\theta}\|_{C^J}\le C_{\phi,K,J,\rho_0,B_1(\theta)}\eta(\theta_\ell)\). By induction from the same estimate at \(\rho=1\), \(\left| V_{\ell-1,\theta}-1 \right|\le C_{\phi,K,B_1(\theta)}\sum_{r<\ell}\eta(\theta_r)\). Since \(\Phi\) is smooth near \(v=1\) and \(\Phi(1,q)=\mathsf{s}(q)\), the variance perturbation is absorbed into the same error budget. This yields ?? and ?? . Moment and derivative bounds for the lower-layer pair distributions follow recursively from the polynomial growth bounds on the derivatives of \(\phi\) and the fact that \(K,J\) are fixed.

It remains to compare the recursion to its Gaussian limit. Let \(E_\ell:=\|Q_{\ell,\theta}-\mathsf{s}_\ell\|_{C^J([-\rho_0,\rho_0])}\). Since \(\mathsf{s}\) is \(C^J\) on \([-1,1]\), the chain rule gives \[E_\ell\le C_{\phi,J,\rho_0,B_1(\theta)}E_{\ell-1} + C_{\phi,K,J,\rho_0,B_1(\theta)}\eta(\theta_\ell), \qquad E_0=0.\] Iterating for the fixed number \(K\) of layers gives ?? . The uniform \(J=0\) bound on \([-1,1]\) follows from the same argument without differentiating in \(\rho\). ◻

Proof. By 64 , \(\Lambda_r(\theta)=\mathsf S_\theta^{(r)}(0)/r!\). By definition, \(\bar\Lambda_r^{(K)}=\mathsf{s}_K^{(r)}(0)/r!\). Applying Proposition 10 and extracting derivatives at zero proves ?? .

Under the spherical prior, Lemma 1 gives, with probability at least \(1-\delta\), \[\max_{1\le\ell\le K}\left|\sum_{i=1}^d\theta_\ell(i)^3\right| \le C_{K,\delta}d^{-1}, \qquad \max_{1\le\ell\le K}\sum_{i=1}^d\theta_\ell(i)^4 \le C_{K,\delta}d^{-1},\] after adjusting constants for the fixed-confidence event. Substituting into ?? gives ?? . ◻

Proof. Expand \(\mathsf{s}_K=\mathsf{s}\circ\cdots\circ\mathsf{s}\). Fix \(a\in\{0,\ldots,K-1\}\). Choose one occurrence of the monomial \(\lambda_R q^R\) at depth \(a\) from the input side, and choose the linear monomial \(\lambda_1 q\) at every other node of the resulting composition tree. Before the \(R\)-branching event there are \(K-1-a\) linear edges; after it, the \(R\) descendants each traverse \(a\) linear edges. The resulting contribution to the coefficient of \(\rho^R\) is \(\lambda_R\lambda_1^{K-1-a+Ra}\). All coefficients in \(\mathsf{s}\) are nonnegative, so summing these \(K\) contributions gives ?? . The finite-\(d\) estimate ?? follows from Theorem 11 with \(J=R\). ◻

Proof. If \(W=0\), then \(g_{W,b}\) is constant and its chaoses of order \(R\ge1\) vanish. Otherwise write \(W=s u\), where \(s=\|W\|_2>0\) and \(u\in V_d\) is a unit vector. Since \(\langle X,u\rangle\sim N(0,1)\), the univariate function \(z\mapsto \varrho(sz-b)\) has an \(L^2(\gamma_1)\) Hermite expansion \[\varrho(sz-b)=\sum_{R\ge0}\beta_R(s,b)h_R(z).\] Therefore \[g_{W,b}(X)=\sum_{R\ge0}\beta_R(s,b)h_R(\langle X,u\rangle).\] By the defining property of the multivariate Hermite tensors, \[h_R(\langle X,u\rangle) =\langle H_R(X),u^{\otimes R}\rangle.\] Thus the degree-\(R\) coefficient tensor of the neuron is \(\beta_R(s,b)u^{\otimes R}\), which has symmetric CP rank at most one. Summing over \(m=1,\ldots,M\) proves ?? . ◻

Proof. Let \(N_R=\lfloor a_Rd^{\chi_R}\rfloor\) and \(s_R=b_R\sqrt{\Lambda_R(\theta)}d^{-\chi_R/2}\). By ?? , the balanced flattening of \(G_R(\theta)\) has at least \(N_R\) singular values larger than \(s_R\). Every CP-rank-\(M\) tensor has balanced-flattening rank at most \(M\). Hence, by Eckart–Young and Lemma 9, \[\|G_R(\theta)-A\|_F^2 \ge \sum_{j>M}\sigma_j\! \left(\operatorname{Mat}_{\rm bal,R}(G_R(\theta))\right)^2 \ge (N_R-M)s_R^2.\] For all sufficiently large \(d\), \(N_R-M\ge (a_R/4)d^{\chi_R}\), and therefore \[(N_R-M)s_R^2 \ge \frac{a_R}{4}d^{\chi_R}\cdot b_R^2\Lambda_R(\theta)d^{-\chi_R} =\frac{a_Rb_R^2}{4}\Lambda_R(\theta).\] ◻

Proof. By orthogonality of Wiener chaoses, \[\|f_\theta-V\|_{L^2(\gamma_D)}^2 =\sum_{R\ge0}\|G_R(\theta)-G_R(V)\|_F^2 \ge \sum_{R=J}^L\|G_R(\theta)-G_R(V)\|_F^2.\] By Lemma 13, \(\operatorname{rank}_{\rm CP}(G_R(V))\le M\) for each \(R\ge1\). Since \(\chi_R\) is nondecreasing in \(R\), condition ?? implies \(M\le (a_R/2)d^{\chi_R}\) for every \(R\in[J,L]\). Applying Lemma 14 to each \(R\in[J,L]\) gives \[\|G_R(\theta)-G_R(V)\|_F^2 \ge \eta_R\Lambda_R(\theta) \ge \eta_{J:L}\Lambda_R(\theta),\] and summing over \(R=J,\ldots,L\) proves the claim. ◻

Proof. Choose \(L\ge J\) so that \(\bar T_K(J,L)\ge \bar T_K(J)-\xi\). This is possible because \(\sum_R\bar\Lambda_R^{(K)}<\infty\). Under the spherical prior on the planted directions, for every fixed \(\delta\in(0,1)\), we claim that with probability at least \(1-\delta\), for all sufficiently large \(d\), every width \[M\le \frac{a_{J:L}}{2}d^{\chi_J}\] satisfies \[\inf_{V\in\mathcal{N}_M(\varrho)} \|f_\theta-V\|_{L^2(\gamma_D)}^2 \ge \eta_{J:L}\bar T_K(J,L)-C_{\phi,K,J,L,\delta}d^{-1}. \label{eq:fixed-block-depth-separation}\tag{76}\] Indeed, by combining Theorem 12 with the fixed-degree energy transfer estimate of Theorem 11, we obtain \[\max_{0\le R\le L}|\Lambda_R(\theta)-\bar\Lambda_R^{(K)}| \le C_{\phi,K,L,\delta}d^{-1}\] with probability at least \(1-\delta\). Summing over the fixed block \(R=J,\ldots,L\) gives 76 . Now, absorbing the fixed constants into \(c_{J,\xi}:=a_{J:L}/2\) and \(\eta_{J,\xi}:=\eta_{J:L}\), ?? follows. The final interpretation follows by solving the threshold relation \(M\asymp d^{\chi_R}\) for \(R\). ◻

Proof. Observe first that we can find a constant \(c_\epsilon>0\), independent of \(d\), such that, with high probability over the spherical planted directions and for all sufficiently large \(d\), \[M\le c_\epsilon d^{\chi_{J_\epsilon}} \quad\Longrightarrow\quad \inf_{V\in\mathcal{N}_M(\varrho)} \|f_\theta-V\|_{L^2(\gamma_D)}^2 \ge \epsilon. \label{eq:epsilon-depth-separation-block}\tag{77}\] Indeed, we apply 76 to the block \(J_\epsilon,\ldots,L_\epsilon\). Namely, if \(M\le (a_{J_\epsilon:L_\epsilon}/2)d^{\chi_{J_\epsilon}}\), then \[\inf_{V\in\mathcal{N}_M(\varrho)} \|f_\theta-V\|_{L^2(\gamma_D)}^2 \ge \eta_{J_\epsilon:L_\epsilon}\bar T_K(J_\epsilon,L_\epsilon)-o_d(1) \ge 2\epsilon-o_d(1),\] which is at least \(\epsilon\) for all sufficiently large \(d\). Thus \(c_\epsilon=a_{J_\epsilon:L_\epsilon}/2\) is admissible.

Assume now the slow-tail condition and quantitative uniform non-cancellation. Then there is a constant \(\eta_0>0\) such that the block constants can be chosen with \(\eta_{J:L}\ge\eta_0\) throughout the relevant ranges. Pick \(J_\epsilon\asymp \epsilon^{-1/p}\) so that \(\eta_0\bar T_K(J_\epsilon)\ge4\epsilon\), possible by ?? , and then choose \(L_\epsilon\ge J_\epsilon\) so that \(\bar T_K(J_\epsilon,L_\epsilon)\ge\bar T_K(J_\epsilon)/2\). The first part of the corollary gives the lower bound for widths below a constant multiple of \(d^{\chi_{J_\epsilon}}\). Since \(\chi_{J_\epsilon}=(K-1)\lfloor J_\epsilon/2\rfloor\asymp_K \epsilon^{-1/p}\), one may choose \(C_{\rm sep}>0\), independent of \(\epsilon\), such that \(d^{C_{\rm sep}\epsilon^{-1/p}}\) lies below this threshold for all sufficiently large \(d\). This proves ?? . ◻

Proof. Recall from Theorem 4 the following structure in the population gradient tensor. The population gradient tensor admits the expansion \[\mathcal{G}_\theta = \sum_{q=0}^{K-1}\mathcal{G}_\theta^{[q]} + \mathcal{R}_K, \qquad \left\| \mathcal{R}_K \right\|_F \le C_{\phi,K,\delta}d^{-K/2}. \label{eq:edgeworth-hierarchy-gflow}\tag{84}\] The leading level is \[\mathcal{G}_\theta^{[0]} = \lambda\,u_{1,1}\otimes\cdots\otimes u_{K,1}. \label{eq:leading-level}\tag{85}\] For \(q=1,\ldots,K-1\), the level-\(q\) term has a finite-rank representation \[\mathcal{G}_\theta^{[q]} = \sum_{\tau\in\mathcal{T}_q} a_\tau(\theta) \bigotimes_{r=1}^K u_{r,b_{\tau,r}}, \label{eq:level-q-representation}\tag{86}\] where \(b_{\tau,r}\in\{1,\ldots,K\}\) and the atom has formal order \(q\), meaning that \[\sigma_\tau+\sum_{r=1}^K(b_{\tau,r}-1)=q \label{eq:formal-order}\tag{87}\] for some scalar Edgeworth order \(\sigma_\tau\ge0\), where its coefficient satisfies \[\left| a_\tau(\theta) \right| \le C_{\phi,K,\delta}d^{-\sigma_\tau/2}. \label{eq:coefficient-bound}\tag{88}\] After collecting equal tensor-power profiles, we have \[\left| \mathcal{T}_q \right| \le R_{K,q}^{\sharp} := \sum_{j=0}^{\lfloor q/2\rfloor} (j+1)\binom{K+q-2j-2}{q-2j} = O_{K,q}(1). \label{eq:sharp-rank}\tag{89}\]

We prove the result using a standard bootstrap argument.

For a rank-one tensor atom \(T=a\,v_1\otimes\cdots\otimes v_K,\) its contribution to the Euclidean gradient in mode \(j\) is \[a\left(\prod_{\ell\ne j}\left\langle {\tilde{\theta}}_\ell,v_\ell\right\rangle\right)v_j.\] Therefore its contribution to the spherical derivative of \(h_{j,p}(t)=\left\langle {\tilde{\theta}}_j(t),u_{j,p}\right\rangle\) is \[a\left(\prod_{\ell\ne j}\left\langle {\tilde{\theta}}_\ell,v_\ell\right\rangle\right) \left[ \left\langle u_{j,p},v_j\right\rangle - h_{j,p}(t)\left\langle {\tilde{\theta}}_j(t),v_j\right\rangle \right]. \label{eq:rank-one-derivative}\tag{90}\] This identity follows directly from \(\dot{\tilde{\theta}}_j=(I-{\tilde{\theta}}_j{\tilde{\theta}}_j^\top)\nabla_{{\tilde{\theta}}_j}L\).

Now define \[\tau := \inf\left\{ t\ge0: \min_j m_j(t)\ge\varepsilon \text{ or } \min_j m_j(t)\le \frac{a}{2\sqrt d} \text{ or } \max_{j,2\le p\le K}\left| h_{j,p}(t) \right|\ge \frac{B}{d} \right\}. \label{eq:bootstrap-time}\tag{91}\] On \([0,\tau]\) we have \[m_j(t)\ge \frac{a}{2\sqrt d}, \qquad \left| h_{j,p}(t) \right|\le \frac{B}{d}, \qquad 2\le p\le K. \label{eq:bootstrap-bounds}\tag{92}\] We will show that the second and third alternatives in the definition of \(\tau\) cannot occur before weak recovery.

The leading atom \(\lambda u_{1,1}\otimes\cdots\otimes u_{K,1}\) gives exactly \(\lambda\left(\prod_{\ell\ne j}m_\ell\right)(1-m_j^2)\) to \(\dot{m}_j\). Now consider a non-leading atom from 86 , \(a_\tau(\theta)\bigotimes_{r=1}^K u_{r,b_{\tau,r}}\). For \(\ell\ne j\), if \(b_{\tau,\ell}=1\), then \(\left\langle {\tilde{\theta}}_\ell,u_{\ell,b_{\tau,\ell}}\right\rangle=m_\ell\). If \(b_{\tau,\ell}\ge2\), the bootstrap bound gives \[\left| \left\langle {\tilde{\theta}}_\ell,u_{\ell,b_{\tau,\ell}}\right\rangle \right| \le \frac{B}{d} \le \frac{2B}{a\sqrt d}m_\ell. \label{eq:aux-contraction-replace}\tag{93}\] In the \(j\)-th mode, the bracket in 90 with \(p=1\) is \[\left\langle u_{j,1},u_{j,b_{\tau,j}}\right\rangle - m_j\left\langle {\tilde{\theta}}_j,u_{j,b_{\tau,j}}\right\rangle.\] If \(b_{\tau,j}=1\), this is \(1-m_j^2\), hence bounded by one. If \(b_{\tau,j}\ge2\), then by 82 and 92 , \[\left| \left\langle u_{j,1},u_{j,b_{\tau,j}}\right\rangle - m_j\left\langle {\tilde{\theta}}_j,u_{j,b_{\tau,j}}\right\rangle \right| \le C_{K,\delta,B}d^{-1}. \label{eq:small-j-bracket}\tag{94}\] Since the atom is non-leading, its formal order is at least one: \[\sigma_\tau+\sum_{r=1}^K(b_{\tau,r}-1)\ge1.\] Combining the coefficient bound 88 , the auxiliary replacement bound 93 , and the small bracket bound 94 , its contribution to \(\dot{m}_j\) is at most \[C_{\phi,K,\delta,B}d^{-1/2} \prod_{\ell\ne j}m_\ell. \label{eq:nonleading-m-contribution}\tag{95}\] Indeed, the smallest possible loss relative to the leading drift is one half-power of \(d\): either from a scalar Edgeworth coefficient \(d^{-\sigma_\tau/2}\) with \(\sigma_\tau\ge1\), or from replacing one planted contraction by an auxiliary contraction, or from a small \(j\)-mode bracket.

The residual contributes at most \[\left\| \mathcal{R}_K \right\|_F \le C_{\phi,K,\delta}d^{-K/2}.\] On the bootstrap region, \[\prod_{\ell\ne j}m_\ell \ge \left(\frac{a}{2\sqrt d}\right)^{K-1} = C_a d^{-(K-1)/2}.\] Thus \[d^{-K/2} \le C_a d^{-1/2}\prod_{\ell\ne j}m_\ell.\] Summing over the \(O_K(1)\) atoms in the hierarchy proves that, for every \(j\), the planted-overlap dynamics satisfy, for \(t \in [0,\tau]\), \[\dot{m}_j(t) = \lambda \left(\prod_{\ell\ne j}m_\ell(t)\right) (1-m_j(t)^2) + e_j(t), \label{eq:overlap-dynamics}\tag{96}\] where, uniformly for \(0\le t\le\tau_\varepsilon\), \[\left| e_j(t) \right| \le C_{\phi,K,\delta}d^{-1/2} \prod_{\ell\ne j}m_\ell(t). \label{eq:overlap-error}\tag{97}\]

We now choose \(\varepsilon\le1/2\). Before weak recovery, we have

\[1-m_j^2\ge 1-\varepsilon^2\ge \frac{3}{4} ~.\] Taking \(d\) sufficiently large so that \[C_{\phi,K,\delta}d^{-1/2}\le \frac{\lambda}{4},\] we obtain \[\dot{m}_j(t) \ge \frac{\lambda}{2}\prod_{\ell\ne j}m_\ell(t)\] on \([0,\tau]\). In particular, no planted overlap can decrease below \(a/(2\sqrt d)\), so the second stopping alternative cannot occur.

Let us now establish a uniform control of the auxiliary, high-order overlaps. Fix \(j\in\{1,\ldots,K\}\) and \(p\in\{2,\ldots,K\}\). For any atom in the hierarchy, the bracket in 90 is \[\left\langle u_{j,p},u_{j,b_{\tau,j}}\right\rangle - h_{j,p}\left\langle {\tilde{\theta}}_j,u_{j,b_{\tau,j}}\right\rangle.\] Since \(p\ge2\), the power-sum bound 82 gives \[\left| \left\langle u_{j,p},u_{j,b_{\tau,j}}\right\rangle \right| \le C_{K,\delta}d^{-1}.\] Also, on the bootstrap region, \[\left| h_{j,p}\left\langle {\tilde{\theta}}_j,u_{j,b_{\tau,j}}\right\rangle \right| \le C_{K,\delta,B}d^{-1}.\] Therefore the bracket is \(O_{K,\delta,B}(d^{-1})\).

The contractions in the remaining \(K-1\) modes are controlled as before: a mode with \(b_{\tau,\ell}=1\) gives \(m_\ell\), and a mode with \(b_{\tau,\ell}\ge2\) gives at most \(B/d\le C d^{-1/2}m_\ell\) on the bootstrap region. Hence every atom contributes at most \[C_{\phi,K,\delta,B}d^{-1} \prod_{\ell\ne j}m_\ell\] to \(\dot{h}_{j,p}\). The residual contributes at most \[\left\| u_{j,p} \right\|_2\left\| \mathcal{R}_K \right\|_F \le C_{\phi,K,\delta}d^{-1/2}d^{-K/2} = C_{\phi,K,\delta}d^{-(K+1)/2}.\] On the bootstrap region, \[d^{-1}\prod_{\ell\ne j}m_\ell \ge c_a d^{-1}d^{-(K-1)/2} = c_a d^{-(K+1)/2},\] so the residual is absorbed. Thus \[\left| \dot{h}_{j,p}(t) \right| \le C_{\phi,K,\delta,B}d^{-1} \prod_{\ell\ne j}m_\ell(t), \qquad 2\le p\le K. \label{eq:aux-derivative}\tag{98}\]

We integrate this estimate. By the positive drift bound, \[\dot{m}_j(t) \ge \frac{\lambda}{2}\prod_{\ell\ne j}m_\ell(t),\] so \[\int_0^\tau \prod_{\ell\ne j}m_\ell(t)\,dt \le \frac{2}{\lambda}\bigl(m_j(\tau)-m_j(0)\bigr) \le \frac{2}{\lambda}. \label{eq:product-integral}\tag{99}\] Using ?? , 98 , and 99 , we obtain \[\left| h_{j,p}(t) \right| \le \frac{B}{4d} + \frac{C_{\phi,K,\delta,B}}{d}, \qquad 0\le t\le\tau.\] Choosing \(B\) sufficiently large, depending only on \(\phi,K,\delta\), gives \[\left| h_{j,p}(t) \right|\le \frac{B}{2d}, \qquad 0\le t\le\tau.\] Hence the auxiliary stopping alternative cannot occur.

Let us finally control the hitting-time bound. Let \(m_*(t):=\min_{1\le j\le K}m_j(t)\). The lower Dini derivative satisfies \[D^+m_*(t) \ge \frac{\lambda}{2}m_*(t)^{K-1}\] as long as \(m_*(t)<\varepsilon\). Let us first consider the setting \(K\ge3\). Then \[\frac{d}{dt}m_*(t)^{-(K-2)} \le -\frac{\lambda}{2}(K-2)\] in the Dini sense. Therefore \[m_*(t)^{-(K-2)} \le m_*(0)^{-(K-2)} - \frac{\lambda}{2}(K-2)t.\] Since \(m_*(0)\ge a/\sqrt d\), the time needed to reach \(\varepsilon\) is at most \[T_\varepsilon \le \frac{2}{\lambda(K-2)} \left[ \left(\frac{\sqrt d}{a}\right)^{K-2} - \varepsilon^{-(K-2)} \right] \le C d^{(K-2)/2}.\] Finally, when \(K=2\), we have \[\frac{d}{dt} \log m_*(t) \geq \frac{\lambda}{2}~,\] and thus \(m_*(t) \geq m_*(0) e^{\lambda t /2}\) and the time to reach overlap \(\varepsilon\) is \[T_\varepsilon \leq \frac{2}{\lambda}\log \frac{\varepsilon \sqrt{d}}{a} = O(\log d).\]

Because neither the lower-overlap nor auxiliary stopping alternatives can occur first, this \(T_\varepsilon\) equals the weak-recovery hitting time up to the stated constant. This concludes the weak recovery proof.

Proof of Strong Recovery: After the weak recovery phase, the gradient flow dynamics enter a linear contraction phase. The key estimate is provided in Lemma 15 below.

For \(\epsilon_0\in(0,1)\) and \(A\ge1\), define the strong basin \[\mathcal{B}(\epsilon_0,A) := \left\{ \{\tilde{\theta}\in(\mathcal{S}^{d-1})^K: \min_{j\le K}m_j\ge\epsilon_0, \quad \max_{j\le K,\,2\le p\le K}|h_{j,p}| \le \frac{A}{d} \right\}. \label{eq:strong-basin}\tag{100}\] We shall use the notation \[\Delta_j:=1-m_j^2, \qquad \Delta_*:=\max_{1\le j\le K}\Delta_j. \label{eq:delta-j-strong}\tag{101}\]

Let us now go back to the proof of Theorem 14. Choose \(A\ge 2B_0\) large enough so that the conclusion of Lemma 15 holds with constants \(c_0,C_0,c_1,C_1\). Let \(\tau\) be the first time after \(t_0\) at which either \(\min_jm_j(t)<\epsilon_0/2\) or \(\max_{j,p}|h_{j,p}(t)|>A/d\). On \([t_0,\tau]\) the trajectory lies in \(\mathcal{B}(\epsilon_0/2,A)\), so Lemma 15 applies.

For the auxiliary overlaps, Gronwall’s inequality gives \[|h_{j,p}(t)| \le e^{-c_1(t-t_0)}|h_{j,p}(t_0)| +\frac{C_1}{c_1d} \le \frac{B_0+C_1/c_1}{d}, \qquad t\le\tau.\] Choosing \(A>2(B_0+C_1/c_1)\) shows that the auxiliary stopping alternative cannot occur.

Similarly, ?? gives \[\Delta_j(t) \le e^{-c_0(t-t_0)}\Delta_j(t_0) +\frac{C_0}{c_0d}, \qquad t\le\tau. \label{eq:delta-gronwall}\tag{105}\] Since \(\Delta_j(t_0)\le 1-\epsilon_0^2\), the right-hand side is never large enough to force \(m_j(t)\) below \(\epsilon_0/2\), for all sufficiently large \(d\). Hence the lower-overlap stopping alternative cannot occur either, and \(\tau=\infty\). Taking the maximum over \(j\) in 105 proves \[\max_{j\le K}\bigl(1-m_j(t)^2\bigr) \le e^{-c(t-t_0)} \max_{j\le K}\bigl(1-m_j(t_0)^2\bigr) +\frac{C}{d}. \label{eq:strong-logistic-bound}\tag{106}\] Choosing \(T_{\rm str}\ge c_0^{-1}\log d\) gives \(\Delta_j(t_0+T_{\rm str})\le C/d\). Since \(m_j\ge0\), \(1-m_j\le 1-m_j^2\), which proves \[\min_{j\le K}m_j(t_0+T_{\rm str}) \ge 1-\frac{C}{d}. \label{eq:population-strong-overlap}\tag{107}\]  ◻

Proof of Corollary 5. For fixed planted directions, \[\sqrt d\,\left\langle {\tilde{\theta}}_j(0),\theta_j\right\rangle \Rightarrow N(0,1),\] and the convergence is uniform for fixed \(K\). Thus, after conditioning on the correct sign pattern, the event \[\left\langle {\tilde{\theta}}_j(0),\theta_j\right\rangle\ge \frac{a}{\sqrt d}, \qquad j=1,\ldots,K,\] has probability bounded below by a positive constant depending only on \(a\) and \(K\).

For \(p\ge2\), \[\left\| u_{j,p} \right\|_2\le C_{K,\delta}d^{-(p-1)/2}\le C_{K,\delta}d^{-1/2}.\] A random unit vector has one-dimensional projection of size \(\left\| u_{j,p} \right\|_2/\sqrt d\), hence \[d\,\left\langle {\tilde{\theta}}_j(0),u_{j,p}\right\rangle\] is tight for \(p=2\) and smaller for \(p\ge3\). By taking \(B\) sufficiently large, the bounds \[\left| h_{j,p}(0) \right|\le \frac{B}{4d}, \qquad j=1,\ldots,K, \quad 2\le p\le K,\] hold with probability bounded below by another positive constant. Intersecting finitely many fixed-probability events gives the result. The recovery time then follows from Theorem 14. ◻

Proof. One-step Stochastic Estimates: We start by establishing standard stochastic estimates by exploiting the regularity of the link function and Gaussian concentration.

We will also use the following martingale consequence.

Weak Recovery: We work on the event of Lemma 17. Let \[F_j({\tilde{\theta}}) := (I-{\tilde{\theta}}_j{\tilde{\theta}}_j^\top) \left(\mathcal{G}_\theta\times_{\ell\ne j}{\tilde{\theta}}_\ell\right)\] be the population spherical gradient. Since \(\mathbb{E}[T_n\mid\theta]=\mathcal{G}_\theta\), \[\mathbb{E}[\widehat G_{j,n}({\tilde{\theta}}_n)\mid\mathcal{F}_n]=F_j({\tilde{\theta}}_n).\]

We use the rescaled planted overlaps \[x_j(n):=\sqrt d\,m_j(n) =\sqrt d\,\left\langle {\tilde{\theta}}_{j,n},\theta_j\right\rangle, \qquad j=1,\ldots,K, \label{eq:rescaled-planted-overlaps}\tag{117}\] and the rescaled auxiliary overlaps \[y_{j,p}(n):=d\,h_{j,p}(n) =d\,\left\langle {\tilde{\theta}}_{j,n},u_{j,p}\right\rangle, \qquad j=1,\ldots,K, \quad 2\le p\le K. \label{eq:rescaled-aux-overlaps}\tag{118}\] The effective discrete time step for the \(x\)-variables is \[h_d:=\eta_0 d^{-(K-1)} \upsilon_{K,d}. \label{eq:effective-time-step}\tag{119}\] Indeed, the leading population drift in \(x_j\) is \[\sqrt d\,\eta_d\,\lambda\prod_{\ell\ne j}m_\ell = h_d\,\lambda\prod_{\ell\ne j}x_\ell.\] Thus \(O(d^{K-1} \upsilon_{K,d}^{-1})\) online samples correspond to \(O(1)\) time in the rescaled population dynamics.

Define the stopped time \[\tau := \inf\left\{ n\ge0: \min_j x_j(n)\ge \varepsilon\sqrt d \text{ or } \min_j x_j(n)\le \frac{a}{2} \text{ or } \max_{j,p}|y_{j,p}(n)|\ge B \right\}.\] On \([0,\tau]\) we have \[x_j(n)\ge \frac{a}{2}, \qquad |y_{j,p}(n)|\le B. \label{eq:sgd-bootstrap-region}\tag{120}\] Equivalently, \[m_j(n)\ge \frac{a}{2\sqrt d}, \qquad |h_{j,p}(n)|\le \frac{B}{d}.\] Thus the population estimates from Theorem 14 and its proof apply on the stopped region: \[\begin{align} \left\langle F_j({\tilde{\theta}}_n),\theta_j\right\rangle &= \lambda\prod_{\ell\ne j}m_\ell(n)(1-m_j(n)^2) +e_j(n), \tag{121}\\ |e_j(n)| &\le C_{\phi,K,\delta}d^{-1/2} \prod_{\ell\ne j}m_\ell(n), \tag{122}\\ \left|\left\langle F_j({\tilde{\theta}}_n),u_{j,p}\right\rangle\right| &\le C_{\phi,K,\delta,B}d^{-1} \prod_{\ell\ne j}m_\ell(n), \qquad 2\le p\le K. \tag{123} \end{align}\]

5.2.0.1 Recursion for the planted overlaps.

The retraction expansion gives, for \(n<\tau\), \[\begin{align} x_j(n+1)-x_j(n) &= \sqrt d\,\eta_d\left\langle F_j({\tilde{\theta}}_n),\theta_j\right\rangle +\Delta M^x_{j,n} +R^x_{j,n}, \label{eq:x-recursion-raw} \end{align}\tag{124}\] where \(\Delta M^x_{j,n}=M^x_{j,n+1}-M^x_{j,n}\) and the cumulative effect of \(R^x_{j,n}\) is controlled by ?? . Using 121 –122 and \(m_\ell=x_\ell/\sqrt d\), we get \[\sqrt d\,\eta_d\left\langle F_j({\tilde{\theta}}_n),\theta_j\right\rangle = h_d\lambda\prod_{\ell\ne j}x_\ell(n) +r^x_{j,n}, \label{eq:x-pop-main}\tag{125}\] with \[|r^x_{j,n}| \le C_{\phi,K,\delta}d^{-1/2}h_d \prod_{\ell\ne j}x_\ell(n) +C_{\phi,K,\delta}h_d m_j(n)^2 \prod_{\ell\ne j}x_\ell(n). \label{eq:x-pop-error}\tag{126}\] Before weak recovery, \(m_j(n)\le\varepsilon\). Taking \(\varepsilon\) small and then \(d\) large makes 126 at most \[\frac{\lambda}{8}h_d\prod_{\ell\ne j}x_\ell(n). \label{eq:x-error-small}\tag{127}\] The retraction term contributes a linear damping of size at most \[C_{\phi,K,\delta,\delta_{\rm sgd}}\eta_0 h_d x_j(n) \label{eq:x-retraction-damping}\tag{128}\] in rescaled time, up to the cumulative martingale error already included in Lemma 17. Thus the stopped recursion has the lower bound \[x_j(n+1)-x_j(n) \ge h_d\left[ \frac{3\lambda}{4}\prod_{\ell\ne j}x_\ell(n) -C_{\phi,K,\delta,\delta_{\rm sgd}}\eta_0 x_j(n) \right] +\Delta M^x_{j,n} \label{eq:x-lower-recursion-with-damping}\tag{129}\] for all \(n<\tau\), after absorbing the lower-order Edgeworth errors.

When \(j\) realizes the current minimum, \(x_j(n)=x_*(n):=\min_q x_q(n)\) and \[\prod_{\ell\ne j}x_\ell(n)\ge x_*(n)^{K-1}.\] Choose \(a\) and \(\eta_0\) so that \[C_{\phi,K,\delta,\delta_{\rm sgd}}\eta_0 x_* \le \frac{\lambda}{4}x_*^{K-1} \qquad\text{for all }x_*\ge a/2~, \label{eq:damping-dominated}\tag{130}\] where we used the fact \(K\ge 2\). Consequently, for every index \(j\) attaining the minimum, \[x_j(n+1)-x_j(n) \ge \frac{\lambda}{2}h_d x_*(n)^{K-1} +\Delta M^x_{j,n}. \label{eq:x-lower-recursion}\tag{131}\]

5.2.0.2 Recursion for the auxiliary overlaps.

Similarly, using 123 , for \(2\le p\le K\), \[\begin{align} y_{j,p}(n+1)-y_{j,p}(n) &= d\eta_d\left\langle F_j({\tilde{\theta}}_n),u_{j,p}\right\rangle +\Delta M^y_{j,p,n} +R^y_{j,p,n}. \label{eq:y-recursion} \end{align}\tag{132}\] Since \[d\eta_d\,d^{-1}\prod_{\ell\ne j}m_\ell = \eta_0 d^{-K/2} \upsilon_{K,d} \prod_{\ell\ne j}m_\ell = h_d d^{-1/2}\prod_{\ell\ne j}x_\ell,\] the deterministic auxiliary drift is smaller by a factor \(d^{-1/2}\) than the planted drift in the rescaled \(x\)-variables. Along the stopped trajectory, \[\sum_{n<\tau}h_d\prod_{\ell\ne j}x_\ell(n) \le C_{\phi,K,\delta,\delta_{\rm sgd}}\sqrt d,\] because the same sum controls the increase of \(x_j\) up to the weak-recovery level \(\varepsilon\sqrt d\), modulo the already-controlled martingale and retraction terms. Hence the total deterministic auxiliary contribution is \(O_{\phi,K,\delta,\delta_{\rm sgd}}(1)\). The retraction contribution is bounded by ?? , and the martingale contribution by ?? . Therefore, after choosing \(B\) large and \(\eta_0\) small, \[|y_{j,p}(n)|\le \frac{B}{2} \qquad\text{for all }n\le\tau. \label{eq:y-bootstrap-improved}\tag{133}\] Thus the auxiliary stopping alternative cannot occur.

5.2.0.3 Growth of the minimum planted overlap.

By ?? , the cumulative martingale fluctuation in each \(x_j\) is at most \(C\sqrt{\eta_0}\). Choose \(\eta_0\) sufficiently small that this is at most \(a/8\). The minimum-overlap estimate 131 then implies that no planted overlap can fall below \(a/2\) before weak recovery, so the lower-overlap stopping alternative cannot occur.

Ignoring the harmless martingale fluctuation, 131 compares \(x_*\) from below with the Euler discretization \[z_{n+1}=z_n+\frac{\lambda}{4}h_d z_n^{K-1}, \qquad z_0=\frac{a}{2}. \label{eq:euler-comparison}\tag{134}\] For \(h_d\) sufficiently small, this discrete recursion is bounded below by the solution of \[\dot{z}=\frac{\lambda}{8}z^{K-1}, \qquad z(0)=\frac{a}{2}, \label{eq:comparison-ode-sgd}\tag{135}\] observed at times \(s_n=nh_d\). For \(K\ge3\), this ODE reaches any level \(\varepsilon\sqrt d\) by a time bounded by a constant \[S \ge \frac{8}{\lambda(K-2)} \left(\frac{2}{a}\right)^{K-2}, \label{eq:S-choice}\tag{136}\] independent of \(d\); more precisely, the time to reach \(\varepsilon\sqrt d\) is \[\frac{8}{\lambda(K-2)} \left[ \left(\frac{2}{a}\right)^{K-2} - (\varepsilon\sqrt d)^{-(K-2)} \right] \le S.\] Thus weak recovery occurs before \(N_S=\lceil S\eta_0^{-1}d^{K-1}\rceil\) iterations. For \(K=2\), the ODE (135 ) reaches level \(\varepsilon \sqrt{d}\) in time \(O(\log d)\), leading to a sample complexity \(N_S = \lceil S \eta_0^{-1} d (\log d)^2 \rceil\) in this case. This proves 111 –112 .

Strong Recovery: Let \(n_\epsilon\) be a weak-recovery time at which \[\min_{j\le K}m_j(n_\epsilon)\ge\epsilon_0, \qquad \max_{j,p}|h_{j,p}(n_\epsilon)|\le \frac{B_0}{d}, \quad 2\le p\le K, \label{eq:online-strong-start}\tag{137}\] for fixed constants \(\epsilon_0,B_0>0\). We give the proof conditionally on the state at \(n_\epsilon\) satisfying 137 . Let \(N=N_{\rm str}\) and write \(s=n-n_\epsilon\) for the additional time index. The population part of the one-step update is controlled by Lemma 15. In particular, as long as \[\min_jm_j(n)\ge\epsilon_0/2, \qquad \max_{j,p}|h_{j,p}(n)|\le \frac{A}{d}, \label{eq:online-strong-bootstrap}\tag{138}\] we have, for suitable constants \(c,C>0\), \[\mathbb{E}[\Delta_j(n+1)-\Delta_j(n)\mid\mathcal{F}_n] \le -c\eta_d\Delta_j(n) +C\eta_d d^{-1} +C\eta_d^2\mathbb{E}[\|\widehat G_{j,n}({\tilde{\theta}}_n)\|_2^2\mid\mathcal{F}_n]. \label{eq:online-delta-drift}\tag{139}\] The last term is the retraction contribution. By Lemma 16, \(\mathbb{E}[\|\widehat G_{j,n}({\tilde{\theta}}_n)\|_2^2\mid\mathcal{F}_n]\le C_{\phi,K}d\); hence \[\mathbb{E}[\Delta_j(n+1)-\Delta_j(n)\mid\mathcal{F}_n] \le -c\eta_d\Delta_j(n) +C\eta_d d^{-1} +C\eta_d^2 d. \label{eq:online-delta-drift-2}\tag{140}\] Since \(\eta_d=d^{-K/2} \upsilon_{K,d} \eta_0\), the last term contributes the deterministic floor \(C\eta_d d=C\eta_0 d^{1-K/2} \upsilon_{K,d}\) after division by the contraction rate.

The martingale increments in the \(m_j\)-coordinates over this strong phase have conditional subexponential norm at most \(C\eta_d\) and conditional variance at most \(C\eta_d^2\). Therefore, by Freedman’s inequality and a union bound over the \(K\) planted overlaps, \[\sup_{0\le s\le N} \left| \sum_{r=0}^{s-1} \eta_d \left\langle \widehat G_{j,n_\epsilon+r}- \mathbb{E}[\widehat G_{j,n_\epsilon+r}\mid\mathcal{F}_{n_\epsilon+r}], \theta_j \right\rangle \right| \le C d^{-K/4} \upsilon_{K,d} \sqrt{\log d} \label{eq:online-strong-martingale}\tag{141}\] with probability at least \(1-\delta_{\rm str}/4\), uniformly in \(j\). Indeed, \(N\eta_d^2\le C\eta_0 d^{-K/2} \upsilon_{K,d}^2 \log d\).

Combining 140 with 141 gives the discrete comparison \[\Delta_j(n_\epsilon+s) \le (1-c\eta_d)^s\Delta_j(n_\epsilon) +C\left(d^{-1}+\eta_0d^{1-K/2} \upsilon_{K,d} \right) +C d^{-K/4} \upsilon_{K,d} \sqrt{\log d} \label{eq:online-delta-comparison}\tag{142}\] for all \(s\le N\), up to the bootstrap stopping time. Choosing the constant in \(N_{\rm str}\) large enough makes \((1-c\eta_d)^N\le d^{-2}\). Thus \[\Delta_j(n_\epsilon+N) \le C\left( d^{-1} +\eta_0d^{1-K/2} \upsilon_{K,d} +d^{-K/4}\upsilon_{K,d} \sqrt{\log d} \right). \label{eq:online-delta-final}\tag{143}\] The slightly larger bound 116 , with the harmless \(\log d\) multiplying the retraction floor, covers the uniform-in-time envelope. Since \(1-m_j\le \Delta_j\), this proves 115 , provided the bootstrap remains valid.

For that purpose, we must finally control the auxiliary overlaps. In the strong basin, the population part satisfies, by Lemma 15, \[\frac{d}{dt}|h_{j,p}| \le -c|h_{j,p}|+Cd^{-1}.\] The same one-step expansion as above therefore yields \[\mathbb{E}[|h_{j,p}(n+1)|-|h_{j,p}(n)|\mid\mathcal{F}_n] \le -c\eta_d|h_{j,p}(n)|+C\eta_d d^{-1}+C\eta_d^2d|h_{j,p}(n)|. \label{eq:online-aux-drift-strong}\tag{144}\] For \(d\) large, the retraction term is absorbed into the damping. The martingale increment in the \(h_{j,p}\) coordinate has conditional subexponential norm at most \(C\eta_d\|u_{j,p}\|_2\le C\eta_dd^{-1/2}\), so over \(N\) steps its cumulative size is at most \[C\eta_d d^{-1/2}\sqrt{N\log d} \le C d^{-(K/4+1/2)} \upsilon_{K,d} \log d \le C d^{-1} \label{eq:online-strong-aux-martingale}\tag{145}\] for fixed \(K\ge 2\), after increasing constants at the finitely many small values of \(K\). Hence the discrete Gronwall argument gives \(|h_{j,p}(n)|\le C/d\) throughout the strong phase. The lower-overlap part of the bootstrap follows from 142 , because the right-hand side is \(o(1)\). Thus the bootstrap cannot fail, and the theorem follows. ◻

Proof. We give the standard Lindeberg proof to make the uniformity explicit. Let \((\Gamma_a,\Xi_a)\) be iid centered Gaussian pairs with the same covariance matrix as \((V_a,W_a)\). Replace the summands one coordinate at a time. At the \(a\)-th replacement, write the contribution of the other coordinates as \(T_a\) and consider \[R_a(t_1,t_2):=h(T_a+(u_at_1,v_at_2)).\] Taylor expand \(R_a\) at \((0,0)\) to order \(P+1\). The terms of total degree one and two cancel because the Gaussian pair matches the first two joint moments. For \(r+s\ge3\) the Taylor coefficients contribute \[\frac{u_a^rv_a^s}{r!s!} \bigl(\mathbb{E}[V_a^rW_a^s]-\mathbb{E}[\Gamma_a^r\Xi_a^s]\bigr) \mathbb{E}[\partial_1^r\partial_2^s h(T_a)] .\] Summing over \(a\) produces the signed contractions \(C_{r,s}(u,v)\). Applying the same replacement expansion recursively to the derivative expectations gives the finite Edgeworth polynomial in ?? . The Taylor remainders are uniformly bounded because the summands are subgaussian, the derivatives of \(h\) have polynomial growth, and the number of expansion orders is fixed. The mixed-incoherent bounds on the contractions then give a uniform remainder estimate. The coordinate envelope \(\iota_d\) is used only to control the finitely many uncontracted coordinate-power vectors and the Taylor remainder uniformly; the contracted estimates below are governed by the signed moment bounds rather than by \(\iota_d\).

For the differentiated expansion, differentiate the finite Lindeberg identity with respect to \(v_b\). Dominated convergence is justified by the same subgaussian moment and polynomial derivative bounds. The derivative either hits an explicit factor \(v_a^s\), producing a mixed-power vector in coordinate \(b\), or it hits the covariance of the Gaussian comparison, producing exactly the derivative of the Gaussian expectation. All non-Gaussian differentiated terms still contain either a positive-order signed contraction or a positive-order mixed-power vector. This proves the differentiated statement. ◻

Proof. We prove this result from a common finite-order Edgeworth expansion. Throughout the proof \(K,M\) are fixed, and constants may depend on \(\phi,K,M\) and on the incoherence constant \(B\), but never on \(d\).

We expand \[{\mathcal{L}}({\tilde{\theta}})=\mathbb{E}[f_\theta(X)f_{\tilde{\theta}}(X)].\] At layer \(r\) the coupled teacher–student preactivation pair has the form \[\left( \sum_a \theta_r(a)Z^{(r-1)}_{\theta,a}, \sum_a {\tilde{\theta}}_r(a)Z^{(r-1)}_{{\tilde{\theta}},a} \right), \label{eq:proof-coupled-layer}\tag{166}\] where the pairs \((Z^{(r-1)}_{\theta,a},Z^{(r-1)}_{{\tilde{\theta}},a})\) are iid over \(a\), conditional on the previous recursive construction. Since \(\phi\) is globally Lipschitz and \(K\) is fixed, all variables in this recursion have subgaussian norms and moments up to order \(L\) bounded by a constant depending only on \(\phi,K,L\).

Applying the weighted Edgeworth expansion from Lemma 18 recursively to 166 yields \[{\mathcal{L}}({\tilde{\theta}}) = q_K(s) + \sum_{1\le q\le M} \sum_{\tau\in\mathcal{T}_q^{\rm nl}} c_\tau(s)\, \mathsf M_\tau(\theta,{\tilde{\theta}}) + \mathcal{R}^{\rm nl}_{M+1}({\tilde{\theta}},\theta). \label{eq:proof-nl-scalar-expansion}\tag{167}\] Here \(q_0=1\) and \(q_r=\Psi(s_rq_{r-1})\) are exactly the Gaussian proxy recursions; \(c_\tau(s)\) are smooth functions of the scalar overlaps and of the intermediate Gaussian covariances; and \(\mathsf M_\tau\) is a monomial in signed teacher, student, and mixed moments \[S_r^{p,q}=\sum_a\theta_r(a)^p{\tilde{\theta}}_r(a)^q, \qquad p+q\ge3.\] Every non-Gaussian term in the second sum has positive formal order. The remainder is bounded by \(C d^{-(M+1)/2}\) under the signed moment bounds.

The smoothness assumptions allow differentiation of 167 under the expectation; equivalently, one may apply the differentiated form of the weighted Edgeworth expansion in Lemma 18. Differentiating the Gaussian proxy gives \[\nabla_{{\tilde{\theta}}_j}q_K(s) = \frac{\partial q_K}{\partial s_j}\,\theta_j = A_j(s)\theta_j,\] with \(A_j(s)\) as in 165 . Differentiating a mixed moment in mode \(j\) gives the exact identity \[\nabla_{{\tilde{\theta}}_j}S_j^{p,q} =q\,\theta_j^{\odot p}\odot{\tilde{\theta}}_j^{\odot(q-1)}, \qquad q\ge1.\] Moments in modes \(r\ne j\) remain scalar coefficients. Therefore \[\nabla_{{\tilde{\theta}}_j}{\mathcal{L}}({\tilde{\theta}}) =A_j(s)\theta_j + \sum_{1\le q\le M}\widetilde{V}_j^{[q]}({\tilde{\theta}},\theta) + \widetilde{R}_{j,M+1}({\tilde{\theta}},\theta), \label{eq:proof-nl-vector-expansion}\tag{168}\] where each \(\widetilde{V}_j^{[q]}\) is a finite sum of mixed-power vectors multiplied by signed mixed moment monomials of total formal order \(q\). This is ?? .

The norm bounds follow by the same order counting. A vector \(\theta_j^{\odot p}\odot{\tilde{\theta}}_j^{\odot q}\) of positive formal order has norm \(O(d^{-1/2})\) when its signed second moment is controlled at spherical scale; Scalar mixed moments of positive formal order are controlled by Definition 1 . Thus a level-\(q\) term has norm at most \(C d^{-q/2}\) on the signed moment event, and the remainder has norm \(C d^{-(M+1)/2}\). This proves ?? and ?? .

At first order there are only two possibilities. Either the positive formal order is carried by the differentiated-mode vector, yielding one of \(\theta_j^{\odot 2},\quad \theta_j\odot{\tilde{\theta}}_j, \quad {\tilde{\theta}}_j^{\odot 2},\) or the differentiated-mode vector is the leading direction \(\theta_j\) or \({\tilde{\theta}}_j\) and the positive formal order is carried by a scalar mixed moment in another mode, such as \(S_r^{2,1}\), \(S_r^{1,2}\), \(S_r^{3,0}\), \(S_r^{0,3}\), or a product of first-order moments. This is exactly the structural description in ?? . The proof of Proposition 18 is complete. ◻

Proof. The Gaussian part is exactly 174 . It remains to bound the finite-dimensional Edgeworth levels and the residual relative to \(M_{-i}\).

Consider first a single level-\(q\) Edgeworth atom in \({\varphi_i}^{S,[q]}\). By the separated structure of the Edgeworth expansion, the atom is a product of contractions in modes \(r\ne i\) and one vector in the differentiated mode \(i\), followed by spherical projection. Let \(a_i/2\) be the formal order of the remaining vector in mode \(i\), and let \(a_r/2\) be the formal order of the scalar correction in mode \(r\ne i\). The level condition gives \[a_i+\sum_{r\ne i}a_r=q.\] By relative mixed incoherence, \[\|w_i\|_2\le B d^{-a_i/2}, \qquad |\chi_r|\le B d^{-a_r/2}m_r, \quad r\ne i.\] Therefore the norm of the projected atom is bounded by \[C_{\phi,K,M,B} d^{-a_i/2} \prod_{r\ne i}\left(d^{-a_r/2}m_r\right) = C_{\phi,K,M,B}d^{-q/2}|M_{-i}(m)|.\] Since the number of atoms through order \(M\) is bounded by a constant depending only on \(K\) and \(M\), summing over the level-\(q\) atoms gives \[\|{\varphi_i}^{S,[q]}\|_2 \le C_{\phi,K,M,B}d^{-q/2}|M_{-i}(m)|, \qquad 1\le q\le M. \label{eq:level-q-product-bound-proof}\tag{178}\] The sum of \(q=1,\ldots,M\) is dominated by the \(q=1\) contribution, giving \(C d^{-1/2}|M_{-i}|\).

The residual satisfies \[\|\mathcal{R}_{i,M+1}\|_2 \le C_{\phi,K,M,B}d^{-(M+1)/2}.\] Because \(M\ge K-1\) and \(m_*\ge a d^{-1/2}\), \[|M_{-i}(m)| \ge a^{K-1}d^{-(K-1)/2}.\] Hence \[d^{-(M+1)/2} \le a^{-(K-1)}d^{-(M-K+2)/2}|M_{-i}(m)| \le C_a d^{-1/2}|M_{-i}(m)|,\] where the last inequality uses \(M\ge K-1\). This absorbs the residual into ?? . Combining the Gaussian product factorization with the Edgeworth and residual bounds proves ?? –?? . The small-overlap refinement follows from 176 . ◻

Proof. The proof is a uniform finite-order Edgeworth expansion for the coupled teacher–student recursive tree, followed by differentiation.

6.5.0.1 Step 1: Gaussian approximation and its derivative.

Let \[\Psi(q):=\mathbb{E}[\phi(G_1)\phi(G_2)], \qquad \mathrm{Corr}(G_1,G_2)=q .\] For two Gaussian layer-wise trees whose correlations are described only by the scalar overlaps \(m_r=\left\langle {\tilde{\theta}}_r,\theta_r\right\rangle\), the layer correlations obey \[q_0=1,\qquad q_r=\Psi(m_rq_{r-1}),\qquad r=1,\ldots,K.\] Recall the Gaussian proxy given by \({\mathcal{L}}_G(m)=q_K\). Differentiating this scalar recursion gives \[\frac{\partial q_K}{\partial m_j} =A_j(m) =q_{j-1}\Psi'(m_jq_{j-1}) \prod_{r=j+1}^K m_r\Psi'(m_rq_{r-1}), \label{eq:Aj-proof}\tag{181}\] which is exactly 165 . Hence the spherical gradient of the Gaussian proxy in mode \(j\) is \[\nabla_{{\tilde{\theta}}_j}^{S}{\mathcal{L}}_G =A_j(m)(\theta_j-m_j{\tilde{\theta}}_j). \label{eq:gaussian-proxy-vector-field}\tag{182}\] This identifies the leading term in ?? .

6.5.0.2 Step 2: Uniform mixed Edgeworth expansion.

We now apply Lemma 18 recursively to the two trees \((Z^{(r)}_\theta,Z^{(r)}_{\tilde{\theta}})\). At layer \(r\), the preactivation pair is \[\left( \sum_a\theta_r(a)Z^{(r-1)}_{\theta,a}, \sum_a{\tilde{\theta}}_r(a)Z^{(r-1)}_{{\tilde{\theta}},a} \right), \label{eq:coupled-layer-weighted-sum}\tag{183}\] where the pairs \((Z^{(r-1)}_{\theta,a},Z^{(r-1)}_{{\tilde{\theta}},a})\) are iid conditional on the previous levels. Smoothness and Lipschitzness of \(\phi\) propagate subgaussian moments uniformly through the fixed depth. Induction over \(r\) therefore gives a uniform finite expansion for every layer correlation, and in particular for \({\mathcal{L}}({\tilde{\theta}})\), of the form \[{\mathcal{L}}({\tilde{\theta}}) ={\mathcal{L}}_G(m) +\sum_{\tau\in\mathcal{T}_{\le P}} c_\tau\, \mathsf S_\tau(\theta,{\tilde{\theta}}) \prod_{r=1}^K m_r^{\ell_{\tau,r}} +\mathcal{R}_{P+1}({\tilde{\theta}}). \label{eq:Ltilde-edgeworth-expanded}\tag{184}\] Here \(\mathcal{T}_{\le P}\) is a finite set depending only on \(K,P\); each \(\mathsf S_\tau\) is a product of signed teacher, student, or mixed coordinate moments \[S_r^{p,q}=\sum_a\theta_r(a)^p{\tilde{\theta}}_r(a)^q, \qquad p+q\ge3,\] and every non-Gaussian term in the sum has at least one unit of formal order. Uniformly on \(\mathcal{J}_{P,B}\), \[\left| \mathsf S_\tau(\theta,{\tilde{\theta}}) \prod_{r=1}^K m_r^{\ell_{\tau,r}} \right| \le C_{\phi,K,P,B}\,d^{-1/2}\,\text{(corresponding Gaussian product)}, \label{eq:nonleading-one-half-loss}\tag{185}\] whenever the term contributes to a first derivative in a favorable basin. This is the same half-order gain as in the first Stein tensor hierarchy: it comes either from a scalar Edgeworth coefficient, from replacing a planted contraction by a mixed-incoherent contraction, or from a small differentiated-mode bracket.

6.5.0.3 Step 3: Differentiating the expansion.

We now differentiate 184 with respect to \({\tilde{\theta}}_j\) and project onto the tangent space. Differentiating the Gaussian term gives 182 . All remaining terms form \(E_j({\tilde{\theta}})\). Since the expansion is finite and the derivative of any mixed moment is another mixed coordinate-power vector, \[\nabla_{{\tilde{\theta}}_j} S_j^{p,q} =q\,\theta_j^{\odot p}\odot{\tilde{\theta}}_j^{\odot(q-1)}, \qquad q\ge1, \label{eq:mixed-moment-gradient}\tag{186}\] while moments in modes \(r\ne j\) contribute only scalar differentiated factors. Thus every component of \(E_j\) is a finite sum of atoms of the schematic form \[C_\tau\, \mathsf S_\tau(\theta,{\tilde{\theta}}) \left(\prod_{r\ne j} T_{\tau,r}({\tilde{\theta}}_r,\theta_r)\right) \left(\theta_j^{\odot p}\odot{\tilde{\theta}}_j^{\odot q}\right), \label{eq:E-atom-normal-form}\tag{187}\] where the total formal order of the atom is positive. The contractions \(T_{\tau,r}\) are either planted overlaps \(m_r\) or mixed moments satisfying the bounds in \(\mathcal{J}_{P,B}\).

We now estimate the three quantities in the proposition.

Overlap estimate. Contracting 187 with \(\theta_j\) produces either a signed power sum of total degree at least three in the \(j\)-th mode, or an atom that already contains a positive-order scalar Edgeworth factor. By \(\mathcal{J}_{P,B}\) and the teacher power-sum event, this costs at least one factor \(d^{-1/2}\) relative to the leading Gaussian contraction. Since \(A_j(m)\asymp M_{-j}(m)\) in the small positive-overlap regime, summing the finite number of atoms gives \[|\left\langle E_j({\tilde{\theta}}),\theta_j\right\rangle| \le C d^{-1/2}A_j(m),\] which is ?? .

Coordinate estimate. Each coordinate of the vector \(\theta_j^{\odot p}\odot{\tilde{\theta}}_j^{\odot q}\) appearing in 187 is bounded by a power of the coordinate envelope \(\iota_d\). The leading possible differentiated-mode vector has coordinate size \(O(\iota_d)\), and every non-leading atom has at least one additional half-order from the scalar/mixed part. Consequently \[\left\| E_j({\tilde{\theta}}) \right\|_\infty \le C \iota_d A_j(m),\] which proves ?? .

Mixed-moment estimate. We now contract 187 against \(\theta_j^{\odot p}\odot{\tilde{\theta}}_j^{\odot(q-1)}\). The differentiated-mode contraction is a signed mixed moment of total coordinate degree at least \(p+q\), possibly multiplied by additional positive-order scalar moments. By the definition of \(\mathcal{J}_{P,B}\) and by the planted power-sum event, this contraction is bounded by \(C\tau_{p+q}(d)m_j\) times the same product scale that appears in \(A_j(m)\). Therefore \[\left| q\sum_{a=1}^d\theta_j(a)^p{\tilde{\theta}}_j(a)^{q-1}E_j({\tilde{\theta}})_a \right| \le C A_j(m)\tau_{p+q}(d)m_j,\] which is ?? .

Finally, from 171 and 172 , we verify that the function \(B_j\) is continuous and \(B_j(0)={\lambda^2}>0\). Choosing \(\varepsilon>0\) small enough gives \(c_0\le B_j(m)\le C_0\) whenever \(\left\| m \right\|_\infty\le\varepsilon\), proving ?? . This completes the proof. ◻

Proof. The proof is a stopping-time bootstrap. Let \(B\ge4B_0\) be chosen below and set \[\tau:=\inf\Bigl\{t\ge0: \min_j m_j(t)\ge\varepsilon \text{ or } \min_j m_j(t)\le \frac{a}{2\sqrt d} \text{ or } (\theta,{\tilde{\theta}}(t))\notin\mathcal{J}_{P,B} \Bigr\}.\] We prove that, for \(d\) large, neither the lower-overlap nor the mixed-incoherence stopping alternative can occur before weak recovery.

6.5.0.4 Leading mixed-moment transport.

We start by establishing a mixed-moment transport for the gaussian field.

6.5.0.5 Overlap drift.

Using ?? , \[\dot{m}_j =A_j(m)(1-m_j^2)+\left\langle E_j,\theta_j\right\rangle.\] By ?? , ?? , and \(m_j\le\varepsilon\le1/2\) before weak recovery, \[\dot{m}_j \ge \frac{3}{4}A_j(m)-Cd^{-1/2}A_j(m) \ge cM_{-j}(m)\] for \(d\) large. This proves ?? on the bootstrap interval, and in particular the lower-overlap stopping alternative cannot occur.

6.5.0.6 Coordinate incoherence.

For each coordinate \(a\), \[\dot{\tilde{\theta}}_j(a)=A_j(m)(\theta_j(a)-m_j{\tilde{\theta}}_j(a))+E_j(a).\] On the bootstrap interval, \(|\theta_j(a)|+|{\tilde{\theta}}_j(a)|\le B\iota_d\) and \(m_j\le1\). Together with ?? , this gives \[\frac{\mathrm d}{\mathrm dt}|{\tilde{\theta}}_j(a)| \le C B \iota_d A_j(m). \label{eq:coordinate-derivative-bound}\tag{188}\] Also, from the positive drift and \(A_j(m)\le C M_{-j}(m)\), \[\int_0^\tau A_j(m(t))\,\mathrm dt \le C\int_0^\tau \dot{m}_j(t)\,\mathrm dt \le C.\] Integrating 188 and increasing \(B\) gives \[\left\| {\tilde{\theta}}_j(t) \right\|_\infty\le B\iota_d, \qquad 0\le t\le\tau.\]

6.5.0.7 Mixed moments.

Fix \(j\) and \((p,q)\) with \(3\le n:=p+q\le P\). If \(q=0\), then \(S_j^{p,0}\) is fixed. Since \(m_j(t)\ge m_j(0)/2\) on the bootstrap interval, ?? implies \[|S_j^{p,0}| \le 2B_0\tau_p(d)m_j(t) \le B\tau_p(d)m_j(t)\] after increasing \(B\).

Now suppose \(q\ge1\). Combining Lemma 19 with ?? yields \[\dot{S}_j^{p,q} =qA_j(m)\bigl(S_j^{p+1,q-1}-m_jS_j^{p,q}\bigr)+\mathcal{E}_j^{p,q}, \qquad |\mathcal{E}_j^{p,q}| \le C A_j(m)\tau_n(d)m_j. \label{eq:Spq-evolution-propagation}\tag{189}\] Define the relative ratio \[R_j^{p,q}(t):=\frac{|S_j^{p,q}(t)|}{m_j(t)}.\] Since \(\dot{m}_j\ge0\) on the bootstrap interval, the upper Dini derivative obeys \[\begin{align} D^+R_j^{p,q}(t) &\le \frac{|\dot{S}_j^{p,q}(t)|}{m_j(t)}\nonumber\\ &\le C A_j(m)R_j^{p,q}(t) +C A_j(m)\frac{|S_j^{p+1,q-1}(t)|}{m_j(t)} +C A_j(m)\tau_n(d). \label{eq:R-evolution-propagation} \end{align}\tag{190}\] The source moment \(S_j^{p+1,q-1}\) has the same total degree \(n\) and one fewer student power. We therefore argue by induction on \(q\). The case \(q=0\) was proved above. If the bound holds for \(q-1\), then \[|S_j^{p+1,q-1}(t)|\le B\tau_n(d)m_j(t),\] and hence \[D^+R_j^{p,q}(t) \le C A_j(m)R_j^{p,q}(t)+CB A_j(m)\tau_n(d).\] As above, \(\int_0^\tau A_j(m(t))\,\mathrm dt\le C\). Gronwall’s inequality therefore gives \[R_j^{p,q}(t) \le C\bigl(R_j^{p,q}(0)+B\tau_n(d)\bigr) \le C'B\tau_n(d).\] Increasing \(B\) uniformly over the finite collection \(3\le p+q\le P\) closes the induction and proves ?? on \([0,\tau]\). Thus no mixed-incoherence constraint can be the first stopping alternative. The bootstrap closes, so ?? holds until weak recovery. ◻

Proof. The rescaled linear vector field is generated by \(\nabla^S_{{\tilde{\theta}}_i}({\lambda} L)\). The leading level of the first Stein tensor is \({\lambda}\theta_1\otimes\cdots\otimes\theta_K\), so after multiplication by \({\lambda}\) the leading mode-\(i\) spherical drift is exactly \[{\lambda^2}M_{-i}(m)(\theta_i-m_i{\tilde{\theta}}_i).\] Taking inner product with \(\theta_i\) gives \({\lambda^2}M_{-i}(m)(1-m_i^2)\). The higher Edgeworth levels have the same finite-rank structure as in the linear weak-recovery theorem. Under the auxiliary overlap bounds, each non-leading atom has at least one additional formal half-order and therefore contributes at most \(C_{\phi,K}d^{-1/2}|M_{-i}|\) to the planted-overlap drift. The order-\(K\) residual is absorbed in the same way using \(\min_jm_j\ge a d^{-1/2}\). This proves ?? –?? . ◻

Proof. The proof is a stopping-time comparison with the rescaled linear flow. Let \[\tau:=\inf\Bigl\{t\ge0: \min_i m_i(t)\ge\varepsilon \text{ or } \min_i m_i(t)\le \frac{a}{2\sqrt d} \text{ or } (\theta,{\tilde{\theta}}(t))\notin\mathcal{J}_{P,B} \Bigr\}.\] On \([0,\tau]\), by choosing \(\varepsilon\le1/2\), we have \[m_i(t)\in\left[\frac{a}{2\sqrt d},\varepsilon\right], \qquad (\theta,{\tilde{\theta}}(t))\in\mathcal{J}_{P,B}.\] Theorem 22 gives propagation of the mixed moments once we have the positive product drift; conversely, the gradient comparison is valid on the mixed-incoherent bootstrap region. We now verify the drift bound.

For each \(i\), write \[\dot{m}_i(t)=\left\langle F_i^{\rm nl}({\tilde{\theta}}(t)),\theta_i\right\rangle.\] We now insert the rescaled linear vector field: \[\begin{align} \dot{m}_i(t) &=\left\langle F_i^{\rm lin}({\tilde{\theta}}(t)),\theta_i\right\rangle +\left\langle F_i^{\rm nl}({\tilde{\theta}}(t))-F_i^{\rm lin}({\tilde{\theta}}(t)),\theta_i\right\rangle. \label{eq:nl-drift-linear-plus-error} \end{align}\tag{192}\] By Lemma 20, \[\left\langle F_i^{\rm lin}({\tilde{\theta}}(t)),\theta_i\right\rangle \ge {\lambda^2}M_{-i}(t)(1-m_i(t)^2) -C d^{-1/2}M_{-i}(t). \label{eq:linear-drift-lower-proof}\tag{193}\] On the bootstrap region, Corollary 6, or Theorem 20 applied pointwise, gives \[\left\| F_i^{\rm nl}({\tilde{\theta}}(t))-F_i^{\rm lin}({\tilde{\theta}}(t)) \right\|_2 \le C\left(\left\| m(t) \right\|_\infty+d^{-1/2}\right)M_{-i}(t). \label{eq:nl-linear-product-error-proof}\tag{194}\] Thus \[\dot{m}_i(t) \ge {\lambda^2}M_{-i}(t)(1-m_i(t)^2) -C\left(\varepsilon+d^{-1/2}\right)M_{-i}(t). \label{eq:nl-drift-lower-before-choice}\tag{195}\] Choose \(\varepsilon>0\) sufficiently small so that \[1-\varepsilon^2\ge \frac{3}{4}, \qquad C\varepsilon\le \frac{1}{4}{\lambda^2},\] and then choose \(d\) sufficiently large so that \(Cd^{-1/2}\le{\lambda^2}/4\). Then \[\dot{m}_i(t) \ge c M_{-i}(t), \qquad c:=\frac{1}{4}{\lambda^2}>0, \label{eq:nl-drift-lower-final}\tag{196}\] for all \(t\le\tau\). Hence the lower-overlap stopping alternative cannot occur. The mixed-incoherence stopping alternative cannot occur by Theorem 22. Therefore \(\tau=\tau_\varepsilon\), and ?? and ?? hold up to weak recovery.

It remains to estimate the hitting time. Let \[m_*(t):=\min_{1\le i\le K}m_i(t).\] The lower Dini derivative satisfies \[D^+m_*(t)\ge c m_*(t)^{K-1}, \qquad 0\le t\le\tau_\varepsilon.\] For \(K\ge3\), this implies \[\frac{\mathrm d}{\mathrm dt}m_*(t)^{-(K-2)} \le -c(K-2).\] Using \(m_*(0)\ge a d^{-1/2}\), we obtain \[m_*(t)^{-(K-2)} \le \left(\frac{\sqrt d}{a}\right)^{K-2} -c(K-2)t.\] Therefore \(m_*(t)\) reaches the fixed level \(\varepsilon\) by time \[T_\varepsilon \le \frac{1}{c(K-2)} \left[ \left(\frac{\sqrt d}{a}\right)^{K-2}-\varepsilon^{-(K-2)} \right] \le C d^{(K-2)/2}.\] Finally, for \(K=2\) we have \(m_*(t) \geq m_*(0) \exp( ct) \geq a d^{-1/2} \exp(c t)\), and thus \(m_*(t)\) reaches level \(\varepsilon\) by time \(T_\varepsilon \leq \frac{1}{2c} \log\left(\frac{d \varepsilon^2}{a^2} \right) = O( \log d)\). This proves ?? and completes the proof. ◻

Proof. For independent spherical vectors, \(\sqrt d\,\left\langle {\tilde{\theta}}_i(0),\theta_i\right\rangle\) converges in distribution to a standard normal. Hence, after conditioning on the correct signs, the event \(m_i(0)\ge a d^{-1/2}\) for all \(i\) has probability bounded below by a positive constant depending only on \(a\) and \(K\). The coordinate envelope \(\left\| {\tilde{\theta}}_i(0) \right\|_\infty\le (B/4)\iota_d\) holds with probability tending to one for \(B\) large enough. The signed mixed moments defining \(\mathcal{J}_{P,B/4}\) are finite in number and have their natural spherical scales with constant probability when the two vectors are independent. Thus the intersection of the favorable-overlap event, the coordinate-envelope event, and the finite mixed-moment event has probability bounded below by a positive constant. Taking \(B\) large enough yields the claim. ◻

Proof. By 161 , \[\Psi(q)=\sum_{r\ge1}a_r^2q^r, \qquad a_1=\kappa\ne0 .\] For \(q\in[0,1]\), \[H(q)=\frac{\Psi(q)}{q}=\sum_{r\ge1}a_r^2q^{r-1}\ge\kappa^2, \qquad \Psi'(q)=\sum_{r\ge1}r a_r^2q^{r-1}\ge\kappa^2,\] with the continuous interpretation \(H(0)=\kappa^2\). The recursion 162 keeps \(q_r\in[0,1]\) whenever all scalar overlaps lie in \([0,1]\). Thus every factor in 172 is bounded below by \(\kappa^2\). The upper bound follows from continuity of \(H\) and \(\Psi'\) on \([0,1]\). The estimate for \(A_i=M_{-i}B_i\) follows from 171 . ◻

Proof. We leverage the nonlinear general-overlap Edgeworth hierarchy from 18. By ?? , with \(M\ge P\) fixed, \[\nabla_{{\tilde{\theta}}_j}{\mathcal{L}}({\tilde{\theta}}) = A_j(m)\theta_j+ \widetilde{V}_j^{[1]}({\tilde{\theta}},\theta)+ \sum_{r=2}^{M}\widetilde{V}_j^{[r]}({\tilde{\theta}},\theta)+ \widetilde{R}_{j,M+1}({\tilde{\theta}},\theta). \label{eq:nl-naive-J-euclidean-expansion-proof}\tag{197}\] After spherical projection, the Gaussian part gives exactly \(A_j(m)(\theta_j-m_j{\tilde{\theta}}_j)\), which is the first term in ?? .

Consider the first nonlinear Edgeworth level, using ?? . The possible differentiated-mode vectors are \(\theta_j^{\odot 2}\), \(\theta_j\odot{\tilde{\theta}}_j\), \({\tilde{\theta}}_j^{\odot 2}\), \(\theta_j\), and \({\tilde{\theta}}_j\), up to scalar coefficients depending smoothly on macroscopic overlaps. After spherical projection and contraction with \(\theta_j\), the first three vector types produce linear combinations of \[S_j^{3,0}-m_jS_j^{2,1}, \qquad S_j^{2,1}-m_jS_j^{1,2}, \qquad S_j^{1,2}-m_jS_j^{0,3}. \label{eq:nl-naive-J-degree-three-brackets}\tag{198}\] On \(\mathcal{C}^{\rm nl}_{P,B}(\epsilon_0)\), each term in 198 is bounded by \(O_B(\tau_3(d)m_j)=O_{B,\epsilon_0}(d^{-1/2})\). If the vector part is \(\theta_j\), then the scalar coefficient has positive mixed Edgeworth order and is again \(O(d^{-1/2})\), giving an \(O(d^{-1/2})(1-m_j^2)\) multiplicative correction; if the vector part is \({\tilde{\theta}}_j\), the spherical projection kills it. This proves the overlap decomposition ?? –?? up to higher-order terms.

The coordinate estimate ?? follows from the same finite expansion: every differentiated-mode vector has coordinate size at most a fixed power of the coordinate envelope, and every non-Gaussian scalar coefficient has positive formal order. Since the class \(\mathcal{C}^{\rm nl}_{P,B}(\epsilon_0)\) already includes \(\left\| {\tilde{\theta}}_j \right\|_\infty+\left\| \theta_j \right\|_\infty\lesssim\iota_d\), all finitely many atoms are bounded by \(C\iota_d\) in \(\ell_\infty\).

For ?? , we contract each non-Gaussian atom against \(q\theta_j^{\odot p}\odot{\tilde{\theta}}_j^{\odot(q-1)}\). The resulting scalar is either a signed mixed moment of total coordinate degree at least \(n=p+q\), or a lower coordinate-degree moment multiplied by an additional positive-order scalar Edgeworth coefficient. In both cases, the bounds in \(\mathcal{J}_{P,B}\), together with the fixed planted-direction power-sum event, give the scale \(\tau_n(d)m_j\). Summing the finite number of atoms gives ?? . All higher nonlinear Edgeworth levels have formal order at least two and are therefore smaller than the first-level contribution by ?? ; the remainder is smaller by ?? .

Finally, by 21, \(A_j(m)\ge c_{\phi,K,\epsilon_0}>0\) on the positive macroscopic branch. Since \(m_j\ge\epsilon_0\), \[\dot{\Delta}_j=-2m_j\dot{m}_j \le -c_0\Delta_j+C_0d^{-1/2},\] which is ?? . ◻

Proof. The proof is a macroscopic stopping-time bootstrap, analogous to the proof of 22, but with the damping in the triangular transport kept rather than discarded. Choose \(B\ge B_0\) large, set \(T_d:=t_0+C_T\log d\), and define \(\tau\) as the first time in \([t_0,T_d]\) at which either \[\min_j m_j(t)\le \epsilon_0/2 \quad\text{or}\quad (\theta,{\tilde{\theta}}(t))\notin\mathcal{J}_{P,B}.\] On \([t_0,\tau]\), the estimates of 22 apply with \(\epsilon_0/2\). The differential inequality ?? gives, for each \(j\), \[\Delta_j(t) \le e^{-c(t-t_0)}\Delta_j(t_0)+C d^{-1/2}, \qquad t_0\le t\le\tau .\] Taking the maximum over \(j\) gives ?? on the stopped interval. This also rules out the lower-overlap exit for large \(d\): if \(m_j\) reached \(\epsilon_0/2\), then \(\Delta_j=1-\epsilon_0^2/4\), whereas the last display is at most \(1-\epsilon_0^2+o_d(1)\) at the first such time.

It remains to rule out exit from \(\mathcal{J}_{P,B}\). For coordinates, using ?? and ?? , \[D^+|{\tilde{\theta}}_j(a)| \le -A_j(m)m_j|{\tilde{\theta}}_j(a)|+A_j(m)|\theta_j(a)|+C\iota_d \le -c|{\tilde{\theta}}_j(a)|+C\iota_d\] on the stopped interval, because \(A_j(m)m_j\ge c_{\phi,K,\epsilon_0}>0\) and \(A_j(m)\le C_{\phi,K}\). Hence \(\left\| {\tilde{\theta}}_j(t) \right\|_\infty\le C\iota_d\) on \([t_0,\tau]\), and increasing \(B\) rules out coordinate-envelope exit.

For mixed moments, fix \(j\) and \(3\le n:=p+q\le P\). If \(q=0\), then \(S_j^{p,0}\) is fixed, and the initial bound together with \(m_j(t)\ge\epsilon_0/2\) gives \(|S_j^{p,0}|\le C_{B_0,\epsilon_0}\tau_p(d)m_j(t)\). Now let \(q\ge1\). Combining 19 with ?? gives \[\dot{S}_j^{p,q} =qA_j(m)\bigl(S_j^{p+1,q-1}-m_jS_j^{p,q}\bigr)+\mathcal{E}_j^{p,q}, \qquad |\mathcal{E}_j^{p,q}|\le C\tau_n(d)m_j . \label{eq:nl-macroscopic-Spq-evolution}\tag{199}\] The crucial point, compared with the small-overlap proof, is the damping term \(-qA_j(m)m_jS_j^{p,q}\), whose coefficient is bounded below by a positive constant in the macroscopic basin. Inducting on \(q\), assume first that \(|S_j^{p+1,q-1}(t)|\le C_{q-1}\tau_n(d)\) on the stopped interval. Then 199 implies \[D^+|S_j^{p,q}| \le -c|S_j^{p,q}|+C_q\tau_n(d).\] Gronwall gives \(|S_j^{p,q}(t)|\le C_q'\tau_n(d)\) uniformly up to \(\tau\). Since \(m_j(t)\ge\epsilon_0/2\), this implies \(|S_j^{p,q}(t)|\le (2C_q'/\epsilon_0)\tau_n(d)m_j(t)\). A finite induction over \(q=0,1,\ldots,n\), then over \(3\le n\le P\), and a final enlargement of \(B\), rules out mixed-moment exit. Thus \(\tau=T_d\), proving ?? .

Finally, choose \(C_T\) large enough that \(e^{-cC_T\log d}\Delta_*(t_0)\le d^{-1/2}\). Then ?? follows from ?? and the inequality \(1-m_j\le1-m_j^2\) on the positive branch. ◻

Proof. We only address the standard estimates needed later. Since \(\phi\) is globally Lipschitz with polynomially controlled derivatives and every parameter vector has unit norm, the random variables \(f_\theta(X_n)\) and \(f_{{\tilde{\theta}}_n}(X_n)\) are subgaussian with constants depending only on \(\phi,K\). Moreover, for every deterministic unit vector \(v\in{\mathcal{S}^{d-1}}\) and every mode \(j\), \[\left\| \left\langle (I-{\tilde{\theta}}_{j,n}{\tilde{\theta}}_{j,n}^{\top}) \nabla_{{\tilde{\theta}}_j}[f_\theta(X_n)f_{\tilde{\theta}}(X_n)]_{{\tilde{\theta}}={\tilde{\theta}}_n},v\right\rangle \right\|_{\psi_1\mid\mathcal{F}_n} \le C_{\phi,K}. \label{eq:nl-projection-psi1}\tag{200}\] The same chain-rule calculation also gives \[\mathbb{E}\left[ \left\| \widehat F^{\rm nl}_{j,n}({\tilde{\theta}}_n) \right\|_2^2 \mid\mathcal{F}_n \right] \le C_{\phi,K}d . \label{eq:nl-gradient-second-moment}\tag{201}\] A Bernstein bound for subexponential variables, applied to a fixed coordinate net and then union-bounded over \(j\le K\) and \(n\le N\), yields ?? . Since \(\eta_d=\eta_0d^{-K/2} \upsilon_{K,d}\), this implies ?? .

For the planted overlap martingale, 200 with \(v=\theta_j\) gives \[\left\| \xi_{j,n} \right\|_{\psi_1\mid\mathcal{F}_n} \le C\sqrt d\,\eta_d = C\eta_0 d^{-(K-1)/2} \upsilon_{K,d}.\] The predictable quadratic variation up to time \(N\) is therefore bounded by \(C\eta_0\), and the individual envelope is \(o(1)\) for fixed \(K\ge2\). Freedman’s inequality for martingales with subexponential increments gives ?? , after absorbing the logarithm depending on \(\delta_{\rm sgd}\) into \(C\).

For the mixed moment martingales, set \[v_{j,p,q,n}(r):=q\theta_j(r)^p{\tilde{\theta}}_{j,n}(r)^{q-1}.\] On \(\mathcal{J}_{P,B}\) and the planted power-sum event, \[\left\| v_{j,p,q,n} \right\|_2 \le C_{B,P}\tau_{p+q}(d), \label{eq:mixed-vector-norm-for-mart}\tag{202}\] with the convention that the bound is trivial if \(q=0\). Applying 200 with \(v=v_{j,p,q,n}/\left\| v_{j,p,q,n} \right\|_2\) gives \[\left\| \zeta_{j,p,q,n} \right\|_{\psi_1\mid\mathcal{F}_n} \le C\eta_d\tau_{p+q}(d).\] Over \(N=O(\eta_0^{-1}d^{K-1})\) steps for \(K>2\) and \(N=O( d (\log d)^2 )\) for \(K=2\), the quadratic variation is bounded by \(C\eta_0\tau_{p+q}(d)^2d^{-1}\), and Freedman’s inequality gives ?? . The coordinate estimate is identical, with \(v=e_r\) and a union bound over \(r\le d\); the factor \(\sqrt{\log(ed)}\) is precisely the coordinate envelope \(\iota_d\). ◻

Proof. The proof is a stopped stochastic comparison with the population theorem. Let \[x_j(n):=\sqrt d\,m_j(n), \qquad x_*(n):=\min_j x_j(n).\] As we did in the linear setting, define the stopping time \(\tau\) to be the first \(n\) such that one of the following occurs:

1. \(\min_j m_j(n)\ge\varepsilon\);

2. \(\min_j m_j(n)<a/(2\sqrt d)\);

3. \((\theta,{\tilde{\theta}}_n)\notin\mathcal{J}_{P,B}\).

We prove that, on the high-probability event of Proposition 26, the second and third alternatives cannot occur before the first, and that the first occurs before \(n_\varepsilon\) steps.

Let us start by establishing the one-step planted-overlap recursion. Since \(\widehat F^{\rm nl}_{j,n}\) is tangent to the sphere at \({\tilde{\theta}}_{j,n}\), \[{\tilde{\theta}}_{j,n+1} = \frac{{\tilde{\theta}}_{j,n}+\eta_d\widehat F^{\rm nl}_{j,n}}{(1+\eta_d^2\left\| \widehat F^{\rm nl}_{j,n} \right\|_2^2)^{1/2}}.\] Therefore, for \(n<\tau\), \[\begin{align} x_j(n+1)-x_j(n) &= \sqrt d\,\eta_d \left\langle F_j^{\rm nl}({\tilde{\theta}}_n),\theta_j\right\rangle +\xi_{j,n} +R^{(m)}_{j,n}, \label{eq:nl-sgd-x-one-step} \end{align}\tag{203}\] where \(\xi_{j,n}\) is defined in ?? and the retraction remainder satisfies, by ?? , \[|R^{(m)}_{j,n}| \le C\eta_0^2 d^{1-K}x_j(n)(\log d)^2 \upsilon_{K,d}^2. \label{eq:nl-sgd-x-retraction-error}\tag{204}\] On the stopped trajectory, Theorem 23 and the gradient comparison imply the population drift lower bound \[\left\langle F_j^{\rm nl}({\tilde{\theta}}_n),\theta_j\right\rangle \ge c\prod_{\ell\ne j}m_\ell(n). \label{eq:nl-pop-drift-input-sgd}\tag{205}\] Consequently, \[x_j(n+1)-x_j(n) \ge c\eta_0 d^{-(K-1)} \prod_{\ell\ne j}x_\ell(n) +\xi_{j,n} -C\eta_0^2d^{1-K}x_j(n)(\log d)^2 \upsilon_{K,d}^2. \label{eq:nl-sgd-x-lower}\tag{206}\] Choosing \(\eta_0\) sufficiently small and then \(d\) sufficiently large, the last term is dominated by the positive drift whenever \(x_j(n)\) remains below \(\varepsilon\sqrt d\) and \(x_*(n)\ge a/2\). Thus \[x_j(n+1)-x_j(n) \ge c_1\eta_0 d^{-(K-1)} \prod_{\ell\ne j}x_\ell(n) +\xi_{j,n}. \label{eq:nl-sgd-x-comparison}\tag{207}\]

Let us now argue that the escape event (ii) cannot occur. Indeed, on the event ?? , the cumulative martingale perturbation in every planted-overlap coordinate is at most \(C\sqrt{\eta_0}\). We choose \(\eta_0\) so small that this is at most \(a/8\). The same discrete comparison we used in the proof of Theorem 15 for \[u_{n+1}=u_n+c_1\eta_0 d^{-(K-1)}u_n^{K-1}\] then gives the following: there exists \(S=S(a,\varepsilon,c_1,K)<\infty\) such that, before time \(S\eta_0^{-1}d^{K-1}\) for \(K>2\) (and \(S= \eta_0^{-1} d (\log d)^2\) for \(K=2\)), either \(x_*(n)\) reaches \(\varepsilon\sqrt d\) or one of the stopping alternatives (ii)–(iii) occurs. Moreover, the same comparison and the martingale bound prevent \(x_*(n)\) from falling below \(a/2\) before that time. Hence alternative (ii) cannot occur first.

It remains to show that alternative (iii) cannot occur first. Fix a mixed moment \(S_j^{p,q}\) with \(3\le p+q\le P\). A Taylor expansion of the retraction in 149 gives, for \(n<\tau\), \[\begin{align} S_j^{p,q}(n+1)-S_j^{p,q}(n) &= \eta_d q\sum_{r=1}^d\theta_j(r)^p{\tilde{\theta}}_{j,n}(r)^{q-1} F_j^{\rm nl}({\tilde{\theta}}_n)_r +\zeta_{j,p,q,n} +R^{(S)}_{j,p,q,n}. \label{eq:nl-sgd-mixed-one-step} \end{align}\tag{208}\] By Proposition 21, the deterministic term is bounded by \[C\eta_d A_j(m(n))\tau_{p+q}(d)m_j(n) \le C\eta_d M_{-j}(n)\tau_{p+q}(d)m_j(n). \label{eq:nl-sgd-mixed-drift-bound}\tag{209}\] The retraction remainder is bounded by the same quantity multiplied by \(O(\eta_0\log^2 d)\), and is absorbed by decreasing \(\eta_0\) and increasing \(d_0\). Summing over time and using the positive planted-overlap drift in 205 gives \[\sum_{n<\tau}\eta_d M_{-j}(n) \le C, \label{eq:nl-sgd-sum-M}\tag{210}\] just as in the population proof, because the left-hand side is controlled by the total increase of \(m_j\). Therefore the accumulated deterministic drift of \(S_j^{p,q}\) is at most \(C\tau_{p+q}(d)m_j(n)\) at the relevant scale. The accumulated martingale part is controlled by ?? ; choosing \(B\) large and then \(\eta_0\) small makes it smaller than \((B/8)\tau_{p+q}(d)m_j(n)\) throughout the stopped interval, using \(m_j(n)\ge a/(2\sqrt d)\). Since the initialization lies in \(\mathcal{J}_{P,B/4}\), all mixed-moment inequalities in \(\mathcal{J}_{P,B}\) remain valid up to \(\tau\).

For the coordinate envelope, the same retraction expansion coordinatewise, combined with ?? and the coordinate martingale bound ?? , gives \[\left\| {\tilde{\theta}}_{j,n} \right\|_\infty\le B\iota_d\] for all \(n<\tau\), after increasing \(B\) and taking \(\eta_0\) small. Hence the coordinate part of \(\mathcal{J}_{P,B}\) also propagates. Alternative (iii) therefore cannot occur first.

We have shown that the only possible first stopping event is weak recovery, and that it occurs by time \(S\eta_0^{-1}d^{K-1} \upsilon_{K,d}^{-2}\). This proves ?? –?? . ◻

Proof. The proof is the stopped stochastic version of 25. We stop the process when either ?? fails or one of the martingale and retraction estimates from 26 fails over the interval of length \(N^{\rm nl}\).

For the planted error \(\Delta_j(n):=1-m_j(n)^2\), the retraction expansion of 149 , together with the population inequality ?? , gives on the stopped interval \[\mathbb{E}\bigl[\Delta_j(n+1)-\Delta_j(n)\mid\mathcal{F}_n\bigr] \le -c\eta_d\Delta_j(n)+C\eta_d d^{-1/2}+C\eta_d^2d. \label{eq:nl-online-sqrt-delta-drift}\tag{211}\] The last term is the usual spherical-retraction error, using the one-sample gradient norm bound ?? . The planted-overlap martingale is controlled as in the strong phase of 15; over \(N^{\rm nl}\) steps it contributes \(O(d^{-K/4} \upsilon_{K,d} \sqrt{\log d})\) uniformly in \(j\). Discrete Gronwall therefore yields, for all \(r\le N^{\rm nl}\), \[\Delta_j(n_0+r) \le e^{-c\eta_dr}\Delta_j(n_0) +C\left(d^{-1/2} +\eta_0d^{1-K/2}\log d \upsilon_{K,d} +d^{-K/4}\upsilon_{K,d} \sqrt{\log d}\right). \label{eq:nl-online-sqrt-delta-comparison}\tag{212}\] Taking \(r=N^{\rm nl}\) and increasing \(C\) gives ?? .

The propagation of \(\mathcal{C}^{\rm nl}_{P,B}(\epsilon_0/2)\) follows from the same stopped induction as in the proof of 25, with martingale errors added to the coordinate and mixed-moment recursions. The leading mixed-moment transport is \[qA_j(m)\bigl(S_j^{p+1,q-1}-m_jS_j^{p,q}\bigr),\] where \(A_j(m)\asymp1\) and \(m_j\ge\epsilon_0/2\) on the stopped interval by 21. Thus the term \(-qA_j(m)m_jS_j^{p,q}\) damps each moment, while \(S_j^{p+1,q-1}\) is handled by induction on the number of student powers. The non-Gaussian corrections are estimated using 22; the martingale increments are the same ones controlled in ?? –?? , and the coordinate envelope follows from ?? . After increasing \(B\), no stopped exit occurs before \(N^{\rm nl}\) with probability at least \(1-\delta_{\rm str}\). ◻

Proof of Lemma 23. Let \(A:=\mathsf{Mat}_a(X)\in\mathbb{R}^{D_L\times D_R}\) and \(Y:=f_\theta(X)A\). Since \(\phi\) is globally Lipschitz and all contractions have norm one, each scalar coordinate generated by the network is subgaussian with a \(\psi_2\)-norm depending only on \(\phi\) and \(K\). In particular, \[\left\| f_\theta(X) \right\|_{\psi_2}\le C_{\phi,K}.\] Let \(Z:=Y-\mathbb{E}Y\). We first bound the matrix variance. For any unit vector \(p\in\mathbb{R}^{D_L}\), \[\begin{align} p^\top\mathbb{E}[YY^\top]p &=\mathbb{E}\bigl[f_\theta(X)^2\left\| A^\top p \right\|_2^2\bigr]\\ &=\sum_{j=1}^{D_R}\mathbb{E}\bigl[f_\theta(X)^2\left\langle A_{:j},p\right\rangle^2\bigr]. \end{align}\] For each column \(j\), \(\left\langle A_{:j},p\right\rangle\) is a standard Gaussian random variable. By Cauchy-Schwarz and the subgaussian moment bound for \(f_\theta(X)\), \[\mathbb{E}\bigl[f_\theta(X)^2\left\langle A_{:j},p\right\rangle^2\bigr] \le (\mathbb{E}f_\theta(X)^4)^{1/2}(\mathbb{E}\left\langle A_{:j},p\right\rangle^4)^{1/2} \le C_{\phi,K}.\] Hence \(\left\| \mathbb{E}YY^\top \right\|_\mathrm{op}\le C_{\phi,K}D_R\). Similarly, \(\left\| \mathbb{E}Y^\top Y \right\|_\mathrm{op}\le C_{\phi,K}D_L\). Centering can only decrease the second moment in the Loewner order after subtracting \((\mathbb{E}Y)(\mathbb{E}Y)^\top\) and its transpose. Therefore \[\sigma^2:= \max\{\left\| \mathbb{E}ZZ^\top \right\|_\mathrm{op},\left\| \mathbb{E}Z^\top Z \right\|_\mathrm{op}\} \le C_{\phi,K}D_*. \label{eq:variance-proxy}\tag{213}\]

The sample matrices are not bounded, so we truncate. Standard Gaussian matrix concentration gives \[\left\| A \right\|_\mathrm{op}\le C(\sqrt{D_L}+\sqrt{D_R}+t)\] with probability at least \(1-e^{-t^2}\), and subgaussianity gives \(\left| f_\theta(X) \right|\le C_{\phi,K}t\) with probability at least \(1-e^{-ct^2}\). Taking \(t\asymp\sqrt{\log(n/\delta)}\) and union bounding over \(n\) samples yields, except on an event of probability at most \(\delta/2\), \[\left\| Y_\ell \right\|_\mathrm{op} \le C_{\phi,K}\sqrt{D_*}\sqrt{\log(n/\delta)}, \qquad 1\le\ell\le n. \label{eq:sample-envelope}\tag{214}\] The expectation of the truncated tail is exponentially small at this level and is absorbed into the second term in ?? . Applying rectangular matrix Bernstein to the truncated independent centered matrices, with variance proxy \(n\sigma^2\) and envelope 214 , gives ?? . The simplified bound ?? follows when the envelope term is no larger than the square-root term. ◻

Proof of Lemma 24. This is Wedin’s sin-theta theorem for singular subspaces. The rank-one signal has first singular value \(\left| \lambda \right|\) and second singular value zero. Under \(\left\| E \right\|_\mathrm{op}\le\left| \lambda \right|/4\), the empirical spectral gap is at least \(\left| \lambda \right|/2\), so the sines of the principal angles between \(\widehat u,u\) and \(\widehat v,v\) are bounded by \(C\left\| E \right\|_\mathrm{op}/\left| \lambda \right|\). For unit vectors, Euclidean distance up to sign is bounded by a universal constant times the sine of the angle. ◻

Proof of Lemma 25. The proof is by induction on \(m\). The case \(m=1\) is immediate. For \(m\ge2\), write \(m_1=\lfloor m/2\rfloor\), \(m_2=m-m_1\), and define \[q_L:=q_1\otimes\cdots\otimes q_{m_1}, \qquad q_R:=q_{m_1+1}\otimes\cdots\otimes q_m.\] The balanced reshaping of \(q\) is exactly the rank-one matrix \(q_Lq_R^\top\), with singular value one. After choosing the sign of \(\widehat q\) so that \(\left\| \widehat q-q \right\|_2\le\epsilon\), the reshaped perturbation has Frobenius norm \(\epsilon\), hence operator norm at most \(\epsilon\). Wedin’s theorem applied to \[\mathsf{Mat}(\widehat q)=q_Lq_R^\top+E, \qquad \left\| E \right\|_\mathrm{op}\le\epsilon,\] gives \[\operatorname{dist}_{\pm}(\widehat q_L,q_L)+\operatorname{dist}_{\pm}(\widehat q_R,q_R) \le C\epsilon.\] Applying the induction hypothesis to \(\widehat q_L\) and \(\widehat q_R\) proves ?? , after increasing \(C_m\). ◻