Open problem MAIS-O78 · posed in MAIS-A7 as Problem 3.11 · Status: open.
Tags: generalization · singular learning theory · training dynamics · developmental interpretability · statistics · probability. Difficulty: ★★★.
Authored by: Claude Fable 5 directed by Lionel Levine · Audited by: GPT 5.6 Sol.
Two staircases describe learning in the two-layer linear network $L(A,B) = \tfrac12 \Vert BA - \Phi \Vert _F^2$ (weights $A \in \mathbb{R}^{H \times M}$ and $B \in \mathbb{R}^{N \times H}$ with hidden width $H$; target $\Phi \in \mathbb{R}^{N \times M}$ of rank $r \le H$ with distinct singular values $s_1 > \dots > s_r > 0$), and they are graded by different variables. Gradient flow $\tau \dot A = -\partial_A L$, $\tau \dot B = -\partial_B L$ from a small aligned initialization of scale $u_0$ learns the singular modes of $\Phi$ one at a time, mode $k$ switching on at $t_k = \tfrac{\tau}{2 s_k} \log \tfrac{s_k}{u_0}$ (Saxe–McClelland–Ganguli [SMG14]); the Bayesian posterior, as the sample size $n$ grows, walks down a free-energy ladder whose rungs trade the rank-$k$ loss $L_k = \tfrac12 \sum_{\alpha > k} s_\alpha^2$ against the Aoyagi–Watanabe learning coefficient $\lambda_k^{\mathrm{AW}}$ [AW05]. Is there a dictionary between training time and sample size that carries one staircase to the other?
The safety interest is calibration. Developmental interpretability reads the formation of structure in a training network through the Bayesian theory of stages [LHFW+25]; that theory's clock ticks in samples, while the training it monitors ticks in seconds. The deep linear network is the one model where both staircases are exact, so it is where a dictionary between the two clocks should first be proved or refuted.
Fix $M = N = H$ and $1 \le r < H$, let the singular values of the target $\Phi(q)$ vary in a one-parameter family $s_1(q) > \dots > s_r(q) > 0$, $q \to \infty$, and use the aligned initialization: weights of scale $u_0$ along the singular frame of $\Phi(q)$, a form gradient flow preserves, under which each mode strength obeys its own scalar logistic equation (exact form in MAIS-A7). On the Bayesian side the same architecture is reduced rank regression — a parameter $(A,B)$ predicts $y = BAx + {}$standard Gaussian noise — and [AW05] computes its learning coefficients $\lambda_k^{\mathrm{AW}}$ in closed form; the problem needs only the increments $\Delta\lambda_k = \lambda_k^{\mathrm{AW}} - \lambda_{k-1}^{\mathrm{AW}}$, positive for $k < H$ (case formulas in MAIS-A7). The Bayesian crossover $n_k(q)$ is the sample size at which rung $k$ of the ladder overtakes rung $k-1$: the large root of $n / \log n = 2\Delta\lambda_k / s_k(q)^2$, the right side assumed to exceed $e$ and tend to infinity with $q$. The dynamical schedule is $t_k(q, u_0) = \tfrac{\tau}{2 s_k(q)} \log \tfrac{s_k(q)}{u_0}$, from the staircase above. Call the spectral family well separated if $n_1(q) < \dots < n_r(q)$ for all large $q$; this is substantive, since a near-flat spectrum can make the ladder skip rungs. The saddle sets $C_k(q)$ are the critical sets of the loss where only the top $k$ modes are fit, and their most degenerate points are those of minimal local learning coefficient, then maximal multiplicity. Here $\lambda_k^{\mathrm{AW}}$ is the invariant of the rank-$k$ model's own optimal set, not the two-sided coefficient of the saddle set $C_k$; whether the two agree is part of MAIS-O77.
Problem (MAIS-A7, Problem 3.11; time versus sample size). Fix $H, r, \tau$ and a well-separated spectral family as above.
- (a) Prove or refute that the Bayesian schedule is realized by the posterior in this joint limit. For each $q$, take i.i.d. data $(x_i, y_i)$ with standard Gaussian $x_i \in \mathbb{R}^H$ and $y_i = \Phi(q) x_i + {}$standard Gaussian noise, and a smooth positive prior on one compact parameter domain $W \subset \mathbb{R}^{2H^2}$ meeting every $C_k(q)$ and its most degenerate points. Write $\psi_{q,n}(k) = n L_k(q) + \lambda_k^{\mathrm{AW}} \log n$ and $k^\ast(q,n) = \arg\min_{0 \le k \le r} \psi_{q,n}(k)$. Show that there are radii $\delta_{q,n} \to 0$ along the joint limit and a constant $c > 0$ such that the following holds. For every sequence $q \to \infty$ and integers $n = n(q) \to \infty$ with $n(q) = O(n_r(q))$ and $\min_{1 \le k \le r} |n(q) - n_k(q)| \ge c \sqrt{n(q) \log n(q)}$, the window $\lbrace w \in W : \mathrm{dist}(w, C_{k^\ast(q,n)}(q)) < \delta_{q,n} \rbrace $ has maximal posterior mass among the $r+1$ saddle windows, with probability tending to $1$. The exclusion width separates the $\log n$ ladder terms from the $O_p(\sqrt{n})$ empirical fit fluctuations. This problem also requires the saddle-window free energy of MAIS-O81; the rim computation there keeps the refutation branch live.
- (b) Call a reparametrization admissible if $n(t) = \phi\bigl( t / \log(1/u_0) \bigr)$ for one continuous increasing $\phi\colon (0,\infty) \to (0,\infty)$ depending only on $H, r, \tau$, not on $q$, the spectrum, or $u_0$. Take any $u_0 = u_0(q) \to 0$ with $\log(1/s_r(q)) = o(\log(1/u_0(q)))$. Determine which of the following holds uniformly over $1 \le k \le r$ and over all well-separated spectral families: (i) some admissible $\phi$ gives $\phi(t_k / \log(1/u_0)) = n_k (1 + o(1))$; (ii) no admissible $\phi$ gives relative error $o(1)$, but one gives two-sided constant-factor bounds whose constants depend only on $H, r, \tau$; or (iii) even such uniform constant-factor bounds are impossible. Quantify the obstruction. The agenda's heuristic suggests (ii), with $\phi(x) \asymp x^2 \log x$ and the exact mode factor $\Delta\lambda_k$ as the obstruction to (i).
The heuristic, offered as such: eliminating $s_k$ between the two schedules gives $t \asymp \tfrac{\tau \log(1/u_0)}{2\sqrt{2 \Delta\lambda}} \sqrt{n / \log n}$. Training time exchanges against sample size at the rate $t \asymp \sqrt{n / \log n}$ — not $t \asymp n$, as a naive one-step-one-sample account would guess — and any of the three answers in (b) would be informative. See MAIS-A7, Section 3.5.
References
- [SMG14] A. M. Saxe, J. L. McClelland, S. Ganguli, Exact solutions to the nonlinear dynamics of learning in deep linear neural networks, International Conference on Learning Representations (ICLR), 2014. arXiv:1312.6120
- [AW05] M. Aoyagi, S. Watanabe, Stochastic complexities of reduced rank regression in Bayesian estimation, Neural Networks 18 (2005), 924–933.
- [LHFW+25] S. P. Lehalleur, J. Hoogland, M. Farrugia-Roberts, S. Wei, A. Gietelink Oldenziel, G. Wang, L. Carroll, D. Murfet, You are what you eat — AI alignment requires understanding how data shapes structure and generalisation, 2025. arXiv:2502.05475
Related: MAIS-O81 (the saddle free energy that part (a) presupposes) · MAIS-O77 (the invariant table for the same fiber and saddles) · MAIS-O7 (opposing staircases, the headline this dictionary would calibrate).