4+3 Phases of Compute-Optimal Neural Scaling Laws

Given the sketch, the problem is a well-specified regression with a bias and an effective-dimension variance. For Gaussian design the part of $\langle x,w^*\rangle$ outside the range of $H^{1/2}S^\top$ is independent of $Sx$, so the approximation error is just extra label noise, and the sharp last-iterate analysis of geometric-decay SGD applies to covariance $SHS^\top$ with eigenvalues $\tilde\lambda_j$: $$\mathbb E\,\mathrm{Excess}\eqsim\Big\|\prod_{t=1}^N(I-\gamma_tSHS^\top)v^*\Big\|_{SHS^\top}^2+\frac{\sigma^2}{N_{\rm eff}}\Big(\#\{\tilde\lambda_j\ge\tfrac1{N_{\rm eff}\gamma}\}+(N_{\rm eff}\gamma)^2\!\!\sum_{\tilde\lambda_j\lt1/(N_{\rm eff}\gamma)}\!\!\tilde\lambda_j^2\Big).$$ The variance is the ridge variance of Bartlett et al. at ridge level $1/(N_{\rm eff}\gamma)$, because halving the step every $N/\log N$ steps caps the step sum near $2\gamma N_{\rm eff}$.

The sketch preserves the power law. Split $H$ at $k=M/c$. By the tail lemma of Bartlett et al. the tail block concentrates around a multiple of the identity, and the head keeps its eigenvalues up to $1\pm O(\sqrt{k/M})$, so $$\Big|\tilde\lambda_j-\Big(\lambda_j+\frac{\sum_{i>k}\lambda_i}{M}\Big)\Big|\lesssim\sqrt{\tfrac kM}\,\lambda_j+\lambda_{k+1}+\frac{\sqrt{\sum_{i>k}\lambda_i^2}}{M}:$$ the head spectrum plus an isotropic shift, the implicit ridge of the benign-overfitting papers. Under a power law the shift is $\eqsim M^{-a}$, the size of the smallest head eigenvalue, so $\tilde\lambda_j\eqsim j^{-a}$.

The variance is the number of learnable directions over $N_{\rm eff}$. With $\tilde\lambda_j\eqsim j^{-a}$ the count above $1/(N_{\rm eff}\gamma)$ is $\min\{M,(N_{\rm eff}\gamma)^{1/a}\}$, and the tail sum is the same order, so $\mathrm{Var}\eqsim\min\{M,k_{\rm eff}\}/N_{\rm eff}$. Parameters beyond $k_{\rm eff}$ never move far enough to fit noise, so the variance stops growing once $M\gt k_{\rm eff}$.

The approximation error is the tail beyond $M$. Under the isotropic prior $\mathbb E\,\mathrm{Approx}=\mathrm{tr}((I-P)H)$, and a rank-$M$ projection captures at most the top $M$ eigenvalues (Ky Fan), so $\mathbb E\,\mathrm{Approx}\ge\sum_{i\gt M}\lambda_i\eqsim M^{1-a}$. For the upper bound the head is fit by a ridge whose penalty is the tail sketch, $$\mathrm{Approx}\lesssim\|w^*_{k:\infty}\|_{H_{k:\infty}}^2+\Big\langle\big[H_{0:k}^{-1}+S_{0:k}^\top A_k^{-1}S_{0:k}\big]^{-1},w^*_{0:k}w^{*\top}_{0:k}\Big\rangle,\qquad A_k=S_{k:\infty}H_{k:\infty}S_{k:\infty}^\top ,$$ and with Step 2's $A_k$ both pieces are $\eqsim M^{1-a}$ at $k=M/2$.

The bias is the tail beyond $k_{\rm eff}$. Directions with $\tilde\lambda\ge1/(N_{\rm eff}\gamma)$ are learned, which gives the upper bound $\max\{M^{1-a},(N_{\rm eff}\gamma)^{1/a-1}\}$. For the lower bound the geometric schedule gives $\prod_t(I-\gamma_tSHS^\top)^2\succeq(I-2\gamma SHS^\top)^{2N_{\rm eff}}$, and averaging over the prior with von Neumann's trace inequality, $$\mathbb E_{w^*}\mathrm{Bias}\gtrsim\sum_{i:\ \tilde\lambda_i\lt1/(N_{\rm eff}\gamma)}\frac{\mu_i(SH^2S^\top)}{\mu_i(SHS^\top)}\eqsim\sum_{(N_{\rm eff}\gamma)^{1/a}\lesssim i\le M}i^{-a}\eqsim(N_{\rm eff}\gamma)^{1/a-1}:$$ each direction SGD has not reached keeps its full share $i^{-a}$.

The variance is at most $\gamma$ times the bias. At the cutoff $\lambda_{k_{\rm eff}}\approx1/(N_{\rm eff}\gamma)$, and under a power law the tail beyond it is about $k_{\rm eff}\lambda_{k_{\rm eff}}$, so $$\frac{\mathrm{Var}}{\mathrm{Bias}}\eqsim\frac{k_{\rm eff}/N_{\rm eff}}{k_{\rm eff}^{1-a}}=\frac{k_{\rm eff}^{\,a}}{N_{\rm eff}}=\gamma$$ (the paper proves $\mathrm{Var}\lesssim(N_{\rm eff}\gamma)^{1/a-1}$; the ratio form is my reading), and when $k_{\rm eff}\gt M$ the variance is $\gamma$ times the approximation error. With $\gamma\lesssim1$ the variance never dominates, and minimizing $M^{1-a}+N^{(1-a)/a}$ under $MN=C$ balances at $N\eqsim M^a$. The ratio also explains the source condition: for $b\gt a$ the tail beyond $k_{\rm eff}$ is $k_{\rm eff}^{1-b}$, smaller than $k_{\rm eff}\lambda_{k_{\rm eff}}$, so the variance dominates unless the step shrinks.

For Gaussian data and squared loss the expected SGD loss solves an exact renewal equation. Given $W$, the second-order term of a step needs fourth moments of $x$, which Wick's formula reduces to second moments, so the recursion closes. In the eigenbasis $(\lambda_j,w_j)$ of $W^\top DW$, with $\rho_j^2(r)$ the squared error along $w_j$, $$\mathbb E\rho_j^2(r+1)=\big(1-2\gamma B\lambda_j+\gamma^2B(B+1)\lambda_j^2\big)\,\mathbb E\rho_j^2(r)+\gamma^2B\lambda_j\,\mathbb E\,\mathcal P(\theta_r).$$ Each mode contracts as under gradient descent and is refilled in proportion to the current loss; summing over modes gives the Volterra equation, with $\mathcal F$ the gradient-descent loss and $\mathcal K(s)$ the excess loss $s$ steps after one unit of injected noise.

Replace the random spectrum by its deterministic equivalent. Write $\mathcal F,\mathcal K$ as contour integrals of $(\hat K-z)^{-1}$, $\hat K=D^{1/2}WW^\top D^{1/2}$, a sample covariance with population $D$ and $d$ samples, and substitute $\mathcal R(z)=\mathrm{diag}\big(1/(j^{-2\alpha}m(z)-z)\big)$ with $$m(z)=\Big(1+\frac1d\sum_{j=1}^v\frac{j^{-2\alpha}}{j^{-2\alpha}m(z)-z}\Big)^{-1},$$ the Silverstein-type fixed point, unique in the upper half-plane by Schwarz-Pick. The resulting solution matches SGD for $d$ from 200 to 12,800.

The loss is gradient descent plus the noise injected while the loss is still order one. The solution is the Neumann series $P=F+\sum_{j\ge1}K^{*j}*F$; a power-law kernel is subexponential, so Kesten's lemma sums the series to $F$ plus a constant times $K*F$. Splitting that convolution at $r/2$, $$\sum_{s\le r}K(r-s)F(s)\asymp K(r)\sum_{s\le r/2}F(s)+F(r)\sum_{s\le r/2}K(s)\asymp\frac{K(r)}{\gamma B}+\|K\|\,F(r),$$ since $F$ is of order one for the first $\asymp1/(\gamma B)$ steps. So $P\asymp F+K/(\gamma B)$: SGD noise matters only when the kernel decays more slowly than the gradient-descent loss.

Three parts of the spectrum give three forcing terms. Deform the contour into a loop around 0 and a path along the bulk. The loop sees the $v-d$ null directions of $\hat K$, and its residue is the floor; with $\lambda_j=j^{-2\alpha}$ it reads $$F_0\approx\sum_j\lambda_jb_j^2\,\frac{\lambda^\star}{\lambda_j+\lambda^\star},\qquad\sum_j\frac{\lambda_j}{\lambda_j+\lambda^\star}=d,$$ the effective-ridge equation of Bordelon et al. with $d$ features in place of $P$ samples (this rewriting is mine; a simulation of the projection residual matched it to within 10%), so $F_0$ is the error of the best predictor in the random $d$-dimensional span. The weight enters to the first power, so $F_0$ is not the ridgeless bias, which squares the weight, adds the $1/(1-\mathrm{df}_2/n)$ inflation, and with $d$ samples came out 2 to 100 times smaller in the same check. On the bulk, the real part of $m$ near 1 means the top eigenpairs of $\hat K$ are those of $D$, giving $F_{pp}$, population gradient descent on $b_j^2=j^{-2\beta}$; the imaginary part adds about $c_\beta/d$ to every mode, $c_\beta=\sum_jj^{-2\beta}$, as if the embedding spread a $1/d$ share of the target's norm over all modes, which gives $F_{ac}$ and exists only when the norm is finite. For the kernel only the pure-point part survives, because $\mathcal K$ carries a factor $z^2$.

Comparing decay rates gives the shape of each loss curve. Laplace asymptotics of the integrals give Theorem 2.1's power laws. Above the line, noise decays like $r^{-(2-1/(2\alpha))}$ and gradient descent like $r^{-(1+(2\beta-1)/(2\alpha))}$, so noise is the slower exactly when $\beta\gt\alpha$; distortion, decaying like $r^{-(1-1/(2\alpha))}$, is slower than both and takes over before the floor. So for $2\beta\gt1$ the curve runs through gradient descent (if $\beta\lt\alpha$) or noise (if $\beta\gt\alpha$), then distortion, then the floor; for $2\beta\lt1$, gradient descent then the floor. Below the line $\gamma\asymp d^{2\alpha-1}$ shrinks the noise term, distortion drops out, and noise beats gradient descent at $\gamma Br\asymp d^{2\alpha}$ exactly when $2\beta\gt1$, which separates Phase IV from Phase Ib.

The compute-optimal width is the crossing of a term that rises in $d$ with one that falls. Replace $P$ by its largest term. At fixed $f$, with $r=f/d$, each term $c\,r^{-\tau}d^{-\sigma}$ is a monomial in $d$, so the maximum is convex in $\log d$ and its minimum is where a term rising in $d$ crosses one falling in $d$, $$\arg\min_d\max\big\{(f/d)^{-\tau_0}d^{-\sigma_0},(f/d)^{-\tau_1}d^{-\sigma_1}\big\}\asymp f^{\frac{\tau_1-\tau_0}{\tau_1-\sigma_1-\tau_0+\sigma_0}}.$$ Only adjacent pieces of the loss curve can meet, and each phase is named by the pair. Gradient descent meets the floor in Phase Ia ($2\alpha\gt1$, $2\beta\lt1$), so one trains to the floor and $\xi=\frac1{2\alpha+1}$; in Ib ($2\alpha\lt1$, $2\beta\lt1\lt2\alpha+2\beta$), $\xi=\frac12$; in Ic ($\alpha\lt\frac14$, $2\beta\gt1$) only conditionally. Above the line with $2\beta\gt1$, gradient descent meets distortion in Phase II ($\beta\lt\alpha$), $\xi=\frac\beta{\alpha+\beta}$: distortion and the floor both fall with $d$, so widening the model lowers the loss more than training through the distorted modes. Noise meets distortion in Phase III ($\beta\gt\alpha$), $\xi=\frac12$, $\eta=1-\frac1{4\alpha}$, independent of $\beta$. Below the line, noise meets the floor in IVa ($1-\frac1{\sqrt2}\lt\alpha\lt\frac12$), $\xi=\frac12$, $\eta=\alpha$, and gradient descent in IVb; the boundary $\alpha=1-\frac1{\sqrt2}$ follows from $(2\alpha^2-4\alpha+1)(1-2\beta)=0$ (my algebra). Below $\alpha+\beta=\frac12$ there is no power law, an artifact of requiring $v\gt d$. With batch and step optimized too, $B=1$ is optimal, the largest stable $\gamma$ in Phases I to III, and an interior $\gamma^\star$ in Phase IV. On the toy model, Chinchilla's Approaches 1 and 2 give $d^\star\propto f^{0.508}$ and $f^{0.525}$ against $\frac12$.

Consequences and limits. Variance grows with model size only until $M$ reaches the $(N\gamma)^{1/a}$ directions SGD can move in $N$ steps, so in the simplest regime extra parameters never hurt. The even split $d^\star\propto f^{1/2}$ holds in Phases Ib, III and IVa for three different reasons (capacity against gradient descent, noise against distortion, noise against capacity), so a measured exponent of 1/2 does not identify the bottleneck, and in Phases III and IV the optimizer sets the exponents, so a different algorithm could change them. Exponents fit at accessible scales can be off by several hundredths: $d\gt1000$ gives exponents within about 0.05, and Phase IV needs larger $d$ than was simulated. Lin et al. read the multi-epoch breakdown of clean laws as variance returning, a conjecture. Limits: linear models of fixed random features with Gaussian data; fixed step schedules; and Lin's bounds hold on average over a prior, with constants depending on $a$ and a lower bound that needs $\sigma^2\gtrsim1$.