Does Multi-Pass Gradient Descent Reach the Low-Degree Threshold?

Some hidden patterns in high-dimensional data can be found with relatively few samples by an exhaustive search, yet seem to need far more samples for any fast algorithm. The low-degree polynomial framework makes this precise. It asks whether any polynomial of modest degree in the data can tell signal from noise, and it uses that as a stand-in for "any efficient algorithm." A separate tradition, macroscopic learning dynamics, describes neural-network training in high dimensions through a few summary numbers. The main one is the overlap between the network's weights and the hidden signal direction, and these summaries follow deterministic equations as dimension grows.

The two traditions disagree about the price of learning higher-order structure. Streaming SGD, which sees each sample once, needs roughly $d^{k-1}$ samples to escape the initial "no information" state when the signal first appears in the $k$-th moment. The low-degree bound says $d^{k/2}$ should suffice for an efficient method. We propose to settle whether gradient descent that reuses a fixed dataset closes this gap, and to explain the mechanism. Our core observation is simple. After $t$ steps, a gradient-descent trajectory on reused data is itself a polynomial in the data of degree growing with $t$. The number of passes over the data therefore plays the role of the polynomial degree $D$. That turns low-degree bounds into statements about how long training stays stuck.

Core Claim

The concrete puzzle comes from two papers that seem to point in opposite directions.

Learning from higher-order statistics, efficiently builds a "spiked cumulant" model, in which a direction is hidden purely in the fourth-order cumulant of whitened data, so ordinary PCA cannot see it. The paper proves that the low-degree likelihood ratio diverges only once $n \gtrsim d^2$. It then reports that two-layer ReLU networks trained with SGD reach non-trivial accuracy at $n \sim d^2$. It explicitly leaves the training mechanism open. Taken at face value, $d^2$ is the low-degree rate $d^{k/2}$ for $k=4$, not the streaming rate $d^{3}$.

A Fourier perspective on the learning dynamics of neural networks reports instead an $N^3$ sample barrier for extracting phase (higher-order) information from flat-spectrum images. That rate matches the streaming prediction.

Our hypothesis is that the difference is data reuse, and more precisely the number of passes relative to $\log d$. We claim the following. Full-batch or many-epoch gradient descent from small initialization reaches the low-degree threshold $n \asymp d^{k^*/2}$, where $k^*$ is the generative exponent defined below. This requires $\Theta(\log d)$ effective passes. Streaming SGD, and any schedule with $O(1)$ reuses per sample, stays at the slower $d^{k^*-1}$ rate. If this holds, the low-degree framework predicts a training timescale (the length of the initial plateau), not just a yes/no feasibility threshold. If it fails, we learn that gradient descent is strictly weaker than the best low-degree method on these problems, which is equally worth knowing.

Relation to Prior Work

Three papers motivate the question by showing that data reuse changes what gradient methods can do.

Neural network learns low-dimensional polynomials with SGD near the information-theoretic limit proves that reusing a minibatch for two consecutive steps acts as an implicit transformation of the labels. This brings polynomial single-index targets down to $\tilde\Theta(d)$ samples. For general targets, however, its guarantee is $n \gtrsim d^{(p_*-1)\vee 1}$, which is still a streaming-type exponent.

Full-Batch Gradient Descent Outperforms One-Pass SGD shows that full-batch GD on a truncated quadratic reaches $n \simeq d$ while one-pass SGD needs $d\log d$. The mechanism is that early GD behaves like power iteration on an empirical Hessian with a spectral gap. That analysis stops at information exponent 2.

Computational-Statistical Gaps in Gaussian Single-Index Models defines the generative exponent $k^*$. This is the smallest "first nonzero Hermite order" (the information exponent) that any transformation of the labels can achieve. The paper proves low-degree and statistical-query lower bounds of $\Omega(d^{k^*/2})$. It matches them with a tensor "partial trace" spectral estimator that is not a neural network.

Our proposal sits exactly in the space these papers leave open. The setting is $k^*>2$, where data reuse is known to help but no gradient method is known to reach $d^{k^*/2}$.

The macroscopic side supplies our method.

A Noise Sensitivity Exponent Controls Large Statistical-to-Computational Gaps uses message-passing state evolution as its proxy for efficient algorithms rather than gradient descent. We treat its committee-machine predictions as a later extension, not a competitor.

Two papers constrain the design. The Quasi-Polynomial Low-Degree Conjecture is False warns us to restrict the degree-to-time correspondence to $D = \mathrm{polylog}(d)$. We will not claim anything for quasi-polynomial degree. The label-transformation issue raised by Damian et al. means our lower bounds must allow the trained second layer to act as an arbitrary label preprocessing.

Research Program

Theory: degree accounting. We will prove that $T$ steps of full-batch GD on a two-layer network with smooth activations and small initialization can be approximated, in the overlap it produces, by a polynomial of degree $\mathrm{poly}(T)$ in the samples. The approximation error must vanish as $d\to\infty$. Combined with low-degree recovery bounds, this gives a conditional lower bound. If $n \ll d^{k^*/2}$, no GD run of $T = \mathrm{polylog}(d)$ steps achieves overlap $m = \langle w, w^*\rangle/\|w\|$ bounded away from zero. This formalizes the reviewer's intuition from the file that iterative algorithms "execute polynomial preprocessing." It does so on the trajectory itself rather than on a designed estimator.

Theory: the upper-bound mechanism. Near $m=0$ we linearize the empirical gradient and ask what operator GD is effectively iterating. For $k^*=2$ this operator is the empirical Hessian, as in the full-batch paper. For $k^*>2$ the first-order term vanishes, and we must determine which combination of reused-sample terms survives.

  • Under the partial-trace hypothesis, interaction between the hidden layer and the second layer over many steps produces a matrix of the form $\frac{1}{n}\sum_i \zeta(y_i)\,\mathrm{He}_{k^*-2}$-weighted outer products. This would have a BBP transition at $n \asymp d^{k^*/2}$, mirroring Damian et al.'s estimator.
  • Under the competing tensor-power hypothesis, GD behaves like power iteration on the raw empirical tensor from a random start. It would then escape only at a larger exponent.

We will derive the plateau length for each hypothesis. Under the partial-trace hypothesis, the overlap grows geometrically at a rate set by the ratio of the top eigenvalue to the edge of the noise spectrum. The escape time is then $T_{\rm esc} \approx \tfrac12\log d / \log(\lambda_{\rm top}/\lambda_{\rm edge})$. The $\tfrac12 \log d$ comes from amplifying an initial overlap of order $d^{-1/2}$ to order one. These derivations are exact predictions to test numerically.

Macroscopic equations with reuse. We will extend the overlap description with one additional order parameter. It measures how much the weights align with the specific noise in the training set, which is what streaming theory sets to zero. Following the matrix-denoising approach, this quantity is computed from resolvents of the linearized operator. The result is a closed description of the early phase for $E$ passes. It should interpolate between the streaming equations at $E=1$ and the dynamic-BBP picture at $E\gtrsim\log d$.

Baselines

The naive reference point is streaming one-pass SGD on the same architecture. It should need roughly $d^{k^*-1}$ samples. Neural network learns low-dimensional polynomials reports that standard online SGD on a degree-3 polynomial fails even at $n = d^2$. We use the same network, initialization, and learning-rate grid as for the multi-pass runs, and differ only in sampling.

The strongest existing method on this question is the partial trace estimator of Computational-Statistical Gaps in Gaussian Single-Index Models. It reports weak recovery at $n \asymp d^{k^*/2}$, the low-degree optimum. We implement it with the same label transformation $\zeta$ given to it and to GD, on identical samples. The quantity compared is the sample-size exponent $\kappa$ at which the overlap crosses 0.1. GD "matches" it if the fitted $\kappa$ agrees within statistical error. GD cannot beat it in exponent, by the lower bound. GD could beat it in constants or in robustness to a misspecified $\zeta$, and we will measure both.

On the spiked cumulant model, the reported neural reference is from Learning from higher-order statistics, efficiently: two-layer ReLU nets reach non-trivial accuracy at $n\sim d^2$, and random features stay at chance there. The file gives no exact accuracy values, so we re-run both rather than quoting a number.

We also run the two-step minibatch-reuse schedule of the same polynomial-learning paper. Its stated guarantee is $n \gtrsim d^{(p_*-1)\vee1}$. It isolates whether any reuse suffices or whether many passes are needed.

The key ablation varies the number of passes $E$ from 1 to $c\log d$ at fixed $n$ and fixed total gradient steps. It is paired with a large-initialization control, in which the linearized early phase does not exist. If the threshold moves to $d^{k^*/2}$ only when $E$ grows with $\log d$ and initialization is small, the degree-as-passes mechanism is supported.

Why not just…?

Why not just use the partial trace estimator and skip neural networks? It already achieves the low-degree rate. But the question here is what gradient training does, because that determines how sample-hungry practical networks are on higher-order structure. The two image papers in the file disagree on that rate, $d^2$ versus $N^3$, and a hand-designed estimator cannot resolve the disagreement.

Why not just apply the streaming overlap equations? They are exact for one pass and predict $d^{k-1}$ escape. On the spiked cumulant model that is $d^3$, which contradicts the reported $d^2$ success. Either the reported networks were trained multi-pass, or the streaming theory is missing something. Our $E=1$ runs check whether the streaming equations remain accurate, so they serve as a control, not a rival.

Why not just say that reuse is a label transformation, so the generative exponent explains everything? This is the most serious alternative. It is the explanation Neural network learns low-dimensional polynomials gives, and it may be the whole story. It predicts $d^{k^*-1}$, while our claim predicts $d^{k^*/2}$, and the two separate cleanly once $k^*\ge3$. For $k^*=4$ the predictions are $d^3$ and $d^2$. A fitted exponent near 3 for many-epoch GD would refute our hypothesis and confirm the simpler one, and we will report it either way.

Why not just attribute the $d^2$ observation to finite-size effects? Fitting exponents over a range of $d$ that is too narrow can mislead. We therefore fit $\kappa$ over at least a factor of 8 in $d$, using finite-size collapse of overlap-versus-$n/d^{\kappa}$ curves. Our conclusion holds only if the collapse is sharp.

Proposed Experiments

Setting 1: single-index models. We use Gaussian single-index models with links of generative exponent $k^*=3$ and $k^*=4$, built following Damian et al. We use $d \in \{64,128,256,512\}$ and $n = \alpha d^{\kappa}$ over a grid of $\kappa$. Training is full-batch, multi-epoch, and streaming GD on two-layer networks with the second layer trained jointly. Metrics are the final overlap $m$, the plateau length $T_{\rm esc}$, and the fitted threshold exponent.

Setting 2: spiked cumulant model. We repeat the same protocol on the spiked cumulant model, which has $k=4$ and a proven low-degree threshold of $d^2$.

Setting 3: the image puzzle. On the flat-spectrum Fourier data model, we rerun the $N^3$ experiment with many epochs. The aim is to test directly whether reuse explains the gap with the spiked-cumulant result.

Decisive checks. There are three. First, measured $T_{\rm esc}$ at threshold should scale like $\log d$, as the power-iteration mechanism predicts. Second, the empirical top eigenvector of our predicted linearized operator should align with the early GD weights. Third, the threshold exponent should move from $k^*-1$ to $k^*/2$ only as passes grow past order $\log d$. If all three hold, the low-degree degree $D$ and the number of passes are the same resource. If the exponent stays at $k^*-1$, the gap between neural training and the best low-degree method is real, and our lower-bound theorem marks its location.