The information exponent

Ben Arous et al.'s theorems. Let $\alpha_c(N,k)=1,\ \log N,\ N^{k-2}$ for $k=1,2,\ge3$. Recovery (Theorem 1.3): under A and B, with $\alpha^{-1}\ll\delta\ll\alpha^{-1/2}$ and $\alpha\gg1$, $\log^2N$, $N^{k-2}\log^2N$ respectively, SGD from a uniform start on the upper hemisphere has $m(X_M)\to1$ in probability; in samples that is $N$, $N\log^2N$ and $N^{k-1}\log^2N$. Refutation (Theorem 1.4): if $\alpha\ll\alpha_c$ and $\delta=O(1)$ ($k\le2$) or $\delta=O(\alpha^{-1/2})$ ($k\ge3$), then $\sup_{t\le M}|m(X_t)|\to0$, so the thresholds are sharp up to $\log^2N$; this is about online SGD in these step ranges only, since information-theoretically order $N$ samples suffice. Descent (Theorems 3.2 and 1.5): from $m(X_0)=\eta\gt0$ with $\alpha\delta^2\to0$, SGD tracks projected gradient descent on $\Phi$, $k$ plays no role, and the climb to $1-\eta$ takes order $N/\delta$ samples, small next to the search.

The escape time is set by a drift budget and a noise budget. Track only $m_t$. To first order, $$m_t\approx m_{t-1}+\tfrac{\delta}{N}\,a_k m_{t-1}^{k-1}-\tfrac{\delta}{N}\nabla H^t(X_{t-1})\cdot\theta,$$ a drift from the Taylor expansion of $\phi'$ plus the increment of the directional error martingale. In ODE time $s=\delta t/N$ the drift $\dot m=a_km^{k-1}$ from $m_0\approx N^{-1/2}$ needs time $1$, $\log N$ and $N^{(k-2)/2}$ for $k=1,2,\ge3$, and the run has ODE time $\alpha\delta$. The martingale over all $\alpha N$ steps is $\delta\sqrt{\alpha/N}$ by Doob, and it must stay below the lead $N^{-1/2}$, so $\alpha\delta^2=O(1)$ and the available ODE time is at most $\sqrt\alpha$; escape requires $\sqrt\alpha\gtrsim\log N$ or $N^{(k-2)/2}$, which is $\alpha_c(N,k)$ up to logs. During the search the noise is as large as $m_t$, so the trajectory does not concentrate, and the proof works without a law of large numbers.

The normalization costs less than half the drift as long as $\delta\lesssim m^{k-2}$. Since $\nabla L\perp X_{t-1}$, the spherical step is the Step 1 increment divided by $r_t=\|\tilde X_t\|$, $$m_t=\frac1{r_t}\Big(m_{t-1}-\tfrac{\delta}{N}\nabla\Phi\cdot\theta-\tfrac{\delta}{N}\nabla H^t\cdot\theta\Big),\qquad1\le r_t\le1+\delta^2\Big(\tfrac{A}{N^2}+\tfrac{L_t}{N}\Big),\quad L_t=\tfrac{\|\nabla H^t\|^2}{N}.$$ The division shrinks $m$ by about $\delta^2L_t|m|/N$ per step, second order but with $L_t$ of order one, and it stays below the drift $\delta a_km^{k-1}/N$ iff $\delta\lesssim m^{k-2}$. At $m\approx N^{-1/2}$ this is the step cap $\delta\lesssim N^{-(k-2)/2}/\log N$, a second reason small steps are forced for $k\ge3$. The rigorous version truncates $L_t$ and uses Markov and Freedman's inequality with a union bound.

The martingale stays below half the initial correlation, which gives a one-sided comparison. The proof does not need the noise to average out, only to stay below half the initial correlation, and the drift then compounds on the remaining half. Doob's $L^2$ maximal inequality keeps the directional martingale below $m_0/10$ up to $\bar t=N\gamma^2/(D^2\delta^2)$, so with Step 2, for $m_0\ge\gamma/\sqrt N$, with probability $1-C/D^2-o(1)$, $$m_t\ \ge\ \frac{m_0}{2}+\frac{\delta a_k}{8N}\sum_{j=0}^{t-1}m_j^{k-1}\qquad\text{for all }t\le\tau^+_\eta\wedge\bar t\wedge M.$$ The condition $\bar t\ge M$ is the noise budget $\alpha\delta^2\lesssim1$ of Step 1.

Solving the inequality gives the three escape times. It is a discrete version of the drift ODE started at $m_0/2$. For $k=1$ growth is linear, $t^*\asymp N/\delta$; for $k=2$ discrete Grönwall gives $m_t\ge\frac{m_0}{2}e^{\delta a_2t/(8N)}$, so $t^*\asymp N\log N/\delta$; for $k\ge3$ the discrete Bihari-LaSalle inequality compares with the finite-time blow-up of $\dot m=cm^{k-1}$, $$m_t\ \ge\ \frac{m_0}{\big(1-\frac{\delta a_k}{8N}(k-2)m_0^{k-2}\,t\big)^{1/(k-2)}},\qquad t^*\asymp\frac{N\cdot N^{(k-2)/2}}{\delta}.$$ The budget checks $t^*\le M$ and $t^*\le\bar t$ become, with $\delta\ll\alpha^{-1/2}$, Theorem 1.3's conditions; for $k=2$ the $\log^2N$ is exactly $\sqrt\alpha\gg\log N$. A uniform start has $m_0\ge\gamma/\sqrt N$ with probability near 1.

After weak recovery, a law of large numbers by Grönwall. From $m=\eta$ the drift is order one per unit ODE time, so noise of total size $o(1)$ cannot matter. Linearizing SGD and the population iterate, the dropped normalization terms sum to $O(\alpha\delta^2)=o(1)$, Doob controls the martingale, and Lipschitz continuity of the drift with discrete Grönwall gives $\sup|m_t-\bar m_t|\le C\varepsilon e^{KT}$ on a window long enough for the population iterate to reach $1-\gamma/5$, after which Assumption A keeps SGD close. The strong Markov property at $\tau^+_\eta$ connects this to Step 4.

The lower bound runs the same comparison upward, excursion by excursion. Upward the normalization only helps, since $r_t\ge1$, so while $m\gt0$ $$m_t\le m_{t-1}+\tfrac{\delta}{N}\tfrac32a_km_{t-1}^{k-1}-\tfrac{\delta}{N}\nabla H^t\cdot\theta.$$ Restart the comparison at every positive excursion: Chebyshev and a union bound keep each noise increment below $d_N/\sqrt N$, so every excursion starts below $d_NN^{-1/2}$, and reverse Grönwall or Bihari-LaSalle bounds keep $m$ below $\eta$ for order $N/\delta$, $N\log N/\delta$ and $N^{k/2}/\delta$ steps, which exceeds $M$ under the hypotheses. The step ranges come from the choice of $d_N$: for $k=2$ exponential growth sees the start only through $\log d_N$, so $d_N=N^{1/4}$ covers every $\delta=O(1)$; for $k\ge3$ a larger start shortens the blow-up, which forces $\alpha\delta^2=O(1)$.

Online SGD moves the overlap at the rate signal$^2$/noise. Damian et al. reread Step 1 as a signal-to-noise ratio. With $v_t$ the negative spherical gradient and renormalization, $$\alpha_{t+1}\approx\alpha_t+\eta_t\,(v_t\cdot w^\star)-\tfrac12\eta_t^2\|v_t\|^2\alpha_t ,$$ and with the largest step whose drag stays below the drift the overlap follows $\alpha'\approx\mathrm{SNR}/\alpha$, $\mathrm{SNR}=\mathbb E[v\cdot w^\star]^2/\mathbb E\|v\|^2$. Unsmoothed, the signal is of order $\alpha^{k^\star-1}$ by Hermite orthogonality and the noise of order $d$, so $\alpha'\approx\alpha^{2k^\star-3}/d$ and escape from $d^{-1/2}$ takes $d\,\alpha_0^{-2(k^\star-2)}=d^{k^\star-1}$. The rest of the proof changes the two halves of this ratio.

Below $\alpha=\lambda/\sqrt d$, smoothing gives the loss a floor of signal. The cap mixes in the random tangent step $\lambda z$, whose overlap with $w^\star$ is about $\lambda/\sqrt d$. Expanding binomially, odd moments of $z\cdot w^\star$ vanish and even ones are $\asymp d^{-j}$: $$\mathcal L_\lambda(\alpha^k)\ \asymp\ \Big(\frac{\alpha}{\sqrt{1+\lambda^2}}\Big)^k\sum_{j\le k/2}\Big(\frac{\lambda^2}{\alpha^2d}\Big)^j .$$ The sum is dominated by its first term when $\alpha\ge\lambda/\sqrt d$ and by its last, the far side of the cap, below. Smoothing nearly commutes with differentiation (a spherical Stein identity), so the smoothed drift is $\lambda^{-1}(\alpha/\lambda)^{k^\star-1}$ above the threshold and, below it, the constant $\lambda^{-1}d^{-(k^\star-1)/2}$ for odd $k^\star$ or linear in $\alpha$ for even $k^\star$: near the equator the smoothed landscape looks like information exponent 1 or 2, with a small slope.

Smoothing shrinks the gradient noise by $\lambda^{-2k^\star}$, as long as $\lambda\le d^{1/4}$. The per-sample loss depends on all of $x$, so Step 8 does not reach the noise. Hermite tensors make smoothing linear, $\mathrm{He}_k(w\cdot x)=\langle\mathrm{He}_k(x),w^{\otimes k}\rangle$, and their orthogonality gives $$\mathbb E_x\big(u\cdot\nabla_w\mathcal L_\lambda\mathrm{He}_k(w\cdot x)\big)^2=k!\,\big\|\nabla_wT_k(w)[u]\big\|_F^2\ \lesssim\ \frac{k!\,k^2}{1+\lambda^2}\,\mathcal L_\lambda(\alpha^{k-1})\Big|_{\alpha=1/\sqrt{1+\lambda^2}}:$$ the noise in a direction is the smoothed power at the overlap of the cap center with a typical cap point. That sits in Step 8's first regime exactly when $1/\lambda\ge\lambda/\sqrt d$, and then $\mathbb E\|v\|^2\lesssim d\lambda^{-2k^\star}$. Above the threshold signal$^2$ and noise shrink alike; below it the signal has its floor, a gain of $\lambda^{2k^\star-2}$ in SNR for odd $k^\star$. Past $\lambda^2\approx\sqrt d$ the noise falls only like $\lambda^{-2}$, no faster than the squared signal, so the gain stops at $\lambda=d^{1/4}$.

Stage 1 escapes from $d^{-1/2}$ to $\lambda d^{-1/2}$. A one-step progress bound makes Step 7 rigorous, and an induction with the Rosenthal-Burkholder-Pinelis inequality keeps $\alpha_t\ge\frac12(\alpha_0+\eta\sum_{s<t}c_\lambda(\alpha_s))$, as in Step 3. The step $\eta=d^{-k^\star/2}\lambda^{2k^\star-2}/\mathrm{polylog}(d)$ keeps the drag below half the drift, and for odd $k^\star$ the constant drift covers the distance in $$T_1\approx\frac{\lambda d^{-1/2}}{\eta\lambda^{-1}d^{-(k^\star-1)/2}}=d^{k^\star-1}\lambda^{-2k^\star+4}$$ steps, $d^{k^\star/2}$ at $\lambda=d^{1/4}$; for even $k^\star$ a Bihari-type comparison gives exponential growth in the same number of steps up to logs.

The rest of the trajectory is the unsmoothed problem. Above $\lambda d^{-1/2}$ smoothing no longer changes the SNR, so Ben Arous et al.'s analysis at the same step carries $\alpha$ to $1-1/k^\star$, and a contraction for $1-\alpha_t$ brings it to $d^{-1/4}$ by $T_1$. Then $\lambda=0$ and $\eta_t\propto1/(d+t)$: near $w^\star$ the loss is locally strongly convex, and the Robbins-Monro induction gives $1-\alpha_t\lesssim d/(d+t)$, the $d/\varepsilon$ term.

The CSQ lower bound comes from many nearly orthogonal directions. There are $\frac12e^{c\epsilon^2d}$ unit vectors with pairwise overlaps at most $\epsilon$, and Hermite orthogonality makes their models nearly uncorrelated, $$\big|\mathbb E\,\sigma(w_i\cdot x)\sigma(w_j\cdot x)\big|=\Big|\sum_k\frac{c_k^2}{k!}(w_i\cdot w_j)^k\Big|\le\epsilon^{k^\star}.$$ Szörényi's CSQ lemma then demands about $s(\tau^2-\epsilon^{k^\star})/2$ queries, and $\epsilon\asymp\sqrt{\log(qd^{k^\star/2})/d}$ gives the bound. The same $\epsilon^{k^\star}$ that flattens the landscape at the equator makes $e^{\Omega(d)}$ directions indistinguishable to correlational queries.