Replace transition theory with tangent capacity

1 files changed, 372 insertions, 0 deletions

diff --git a/notes/07_bp_capacity_theory.md b/notes/07_bp_capacity_theory.md
new file mode 100644
index 0000000..c7ac1f3
--- /dev/null
+++ b/notes/07_bp_capacity_theory.md
@@ -0,0 +1,372 @@
+# BP-Capacity Theory Correction
+
+The previous hard-count transition model is not acceptable as a main theory:
+
+\[
+M_{\mathrm{FA}}=P-K_{\mathrm{FA}}-Nn_L
+\]
+
+is only a crude diagnostic. It treats BP capacity as raw parameter count and
+treats FA alignment as full hard constraints. The main paper should instead use
+a capacity definition grounded in the training-set Jacobian / NTK.
+
+## Literature-Supported BP Capacity
+
+For squared loss on a finite training set, the mature local object is the output
+Jacobian
+
+\[
+J_{\mathrm{BP}}(\theta, X)
+=
+\frac{\partial f_\theta(X)}{\partial \theta}
+\in
+\mathbb R^{Nn_L\times P}.
+\]
+
+Karhadkar et al. prove the key local lemma: at a differentiable critical point,
+if the training-set Jacobian has full row rank, then the squared-loss critical
+point is a global minimizer. Their deep-ReLU results further show that many
+activation regions have full-rank Jacobian under explicit activation-pattern
+rank conditions.
+
+Therefore the hard BP interpolation capacity should be
+
+\[
+r_{\mathrm{BP}}(\theta)
+=
+\operatorname{rank} J_{\mathrm{BP}}(\theta, X),
+\]
+
+not \(P\) and not an empirical fitted multiple of \(Nn_L\).
+
+For finite-time or ill-conditioned training, use the empirical NTK
+
+\[
+K_{\mathrm{BP}}(\theta)
+=
+J_{\mathrm{BP}}(\theta,X)J_{\mathrm{BP}}(\theta,X)^\top
+\]
+
+and its effective dimension
+
+\[
+d_{\mathrm{BP}}(\sigma^2)
+=
+\operatorname{tr}
+\left[
+K_{\mathrm{BP}}
+\left(K_{\mathrm{BP}}+\sigma^2 I\right)^{-1}
+\right].
+\]
+
+This follows the NTK view: training progress on finite data is governed by the
+kernel Gram spectrum, with fast convergence in large-eigenvalue directions and
+slow convergence in small-eigenvalue directions.
+
+## FA Capacity Occupation
+
+There are two separate FA capacity notions.
+
+1. Matrix-alignment capacity: how much parameter-direction volume is occupied by
+   making forward matrices align with feedback matrices.
+2. Downstream training capacity: how much of BP's local training kernel survives
+   when BP gradients are replaced by FA surrogate gradients.
+
+The downstream experiment should use the second object as its main predictor.
+
+## FA Surrogate-Gradient Kernel
+
+Let \(m=Nn_L\). For each output coordinate basis vector \(e_i\in\mathbb R^m\),
+define the FA pseudo-gradient direction
+
+\[
+\tilde g_i^{\mathrm{FA}}(B,\theta)
+\in
+\mathbb R^P
+\]
+
+obtained by running the FA backward rule with output residual \(e_i\). Stack
+these rows into
+
+\[
+\tilde J_{\mathrm{FA}}(B,\theta)
+\in
+\mathbb R^{m\times P}.
+\]
+
+For squared loss with residual \(r=f_\theta(X)-y\), the BP update is
+
+\[
+\Delta\theta_{\mathrm{BP}}
+=
+-\eta J_{\mathrm{BP}}^\top r,
+\]
+
+and the FA update is
+
+\[
+\Delta\theta_{\mathrm{FA}}
+=
+-\eta \tilde J_{\mathrm{FA}}^\top r.
+\]
+
+The induced first-order output dynamics are therefore
+
+\[
+\Delta f_{\mathrm{BP}}
+=
+-\eta
+K_{\mathrm{BP}}r,
+\qquad
+K_{\mathrm{BP}}=J_{\mathrm{BP}}J_{\mathrm{BP}}^\top,
+\]
+
+and
+
+\[
+\Delta f_{\mathrm{FA}}
+=
+-\eta
+K_{\mathrm{FA}}r,
+\qquad
+K_{\mathrm{FA}}
+=
+J_{\mathrm{BP}}\tilde J_{\mathrm{FA}}^\top.
+\]
+
+This is the correct local object for downstream FA/BP gap. It is also the
+natural analogue of the surrogate-gradient NTK: the forward Jacobian controls
+how parameter motion changes outputs, while the surrogate Jacobian controls the
+parameter motion chosen by the learning rule.
+
+Since \(K_{\mathrm{FA}}\) can be non-symmetric, hard local solvability is governed
+by
+
+\[
+\operatorname{rank}(K_{\mathrm{FA}}),
+\]
+
+while stable finite-time learning should be measured by the spectrum of the
+symmetrized or positive-real part of the operator. A conservative symmetric
+capacity proxy is
+
+\[
+H_{\mathrm{FA}}
+=
+\frac{K_{\mathrm{FA}}+K_{\mathrm{FA}}^\top}{2},
+\]
+
+with positive eigenvalues \(\lambda_i^+\). Then
+
+\[
+d_{\mathrm{FA}}^{\mathrm{dyn}}(\sigma^2)
+=
+\sum_i
+\frac{\max(\lambda_i,0)}
+{\max(\lambda_i,0)+\sigma^2}.
+\]
+
+This is not a fitted scale. It is computed directly from the local FA learning
+operator.
+
+## Alignment-Constraint Projection
+
+Let \(C_{\mathrm{FA}}\) be the local Jacobian of the FA alignment constraints
+with respect to parameters. The hard constraint projector is
+
+\[
+\Pi_C
+=
+I
+-
+C_{\mathrm{FA}}^\top
+\left(C_{\mathrm{FA}}C_{\mathrm{FA}}^\top\right)^+
+C_{\mathrm{FA}}.
+\]
+
+The hard FA-accessible task rank is
+
+\[
+r_{\mathrm{FA}}
+=
+\operatorname{rank}
+\left(
+J_{\mathrm{BP}}\Pi_C J_{\mathrm{BP}}^\top
+\right).
+\]
+
+So the capacity loss is
+
+\[
+\Delta r
+=
+r_{\mathrm{BP}}-r_{\mathrm{FA}}.
+\]
+
+For a soft alignment burden, use
+
+\[
+K_{\mathrm{FA},\lambda}
+=
+J_{\mathrm{BP}}
+\left(M+\lambda C_{\mathrm{FA}}^\top C_{\mathrm{FA}}\right)^{-1}
+J_{\mathrm{BP}}^\top,
+\]
+
+and
+
+\[
+d_{\mathrm{FA},\lambda}(\sigma^2)
+=
+\operatorname{tr}
+\left[
+K_{\mathrm{FA},\lambda}
+\left(K_{\mathrm{FA},\lambda}+\sigma^2 I\right)^{-1}
+\right].
+\]
+
+The soft capacity loss is
+
+\[
+\Delta d_\lambda
+=
+d_{\mathrm{BP}}(\sigma^2)
+-
+d_{\mathrm{FA},\lambda}(\sigma^2).
+\]
+
+No fitted scalar is allowed here. Every quantity is computed from \(J\), \(C\),
+and a declared metric \(M\).
+
+## Correct Transition Statement
+
+For downstream memorization experiments, the FA/BP transition should first be
+predicted by the FA surrogate-gradient kernel:
+
+\[
+\operatorname{rank}(K_{\mathrm{FA}})\approx Nn_L
+\]
+
+or, for finite-time training,
+
+\[
+d_{\mathrm{FA}}^{\mathrm{dyn}}(\sigma^2)\approx Nn_L.
+\]
+
+For the matrix-alignment capacity theory, the transition can also be written as
+
+\[
+r_{\mathrm{FA}}\approx Nn_L
+\]
+
+in the hard projected-rank model, or by
+
+\[
+d_{\mathrm{FA},\lambda}(\sigma^2)\approx Nn_L
+\]
+
+in the finite-time/effective-rank model.
+
+Equivalently: the breakpoint occurs when FA-projected tangent capacity can no
+longer span the training output constraints.
+
+This is the clean version of "redundancy exhaustion":
+
+\[
+\operatorname{range}(J_{\mathrm{BP}}^\top)
+\]
+
+is the BP task-sensitive subspace. FA alignment only hurts downstream capacity
+to the extent that its constraint directions overlap this subspace.
+
+Under a generic random-subspace approximation with
+
+\[
+r_{\mathrm{BP}}=\operatorname{rank}J_{\mathrm{BP}},
+\qquad
+k=\operatorname{rank}C_{\mathrm{FA}},
+\]
+
+the expected soft overlap is
+
+\[
+\mathbb E\operatorname{tr}(P_C P_J)
+=
+\frac{kr_{\mathrm{BP}}}{P}.
+\]
+
+The hard generic rank after projection is
+
+\[
+r_{\mathrm{FA}}
+=
+\min(r_{\mathrm{BP}}, P-k).
+\]
+
+This gives a simple theorem without post-hoc parameters, but the experimentally
+plotted prediction should prefer the directly measured Jacobian/NTK quantities.
+
+## What To Change In Experiments
+
+The next downstream-capacity plot should not use only
+\(P-K_{\mathrm{FA}}-Nn_L\). It should compute, per architecture and seed:
+
+1. \(r_{\mathrm{BP}}\) or \(d_{\mathrm{BP}}(\sigma^2)\) on the full training set.
+2. \(\operatorname{rank}(K_{\mathrm{FA}})\) and
+   \(d_{\mathrm{FA}}^{\mathrm{dyn}}(\sigma^2)\) from the FA pseudo-gradient
+   kernel.
+3. \(r_{\mathrm{FA}}\) or \(d_{\mathrm{FA},\lambda}(\sigma^2)\) after applying
+   the FA alignment projector / penalty as the matrix-capacity ablation.
+4. A predicted distribution of train-gap transition from these computed spectra,
+   not from a fitted shift.
+
+The old hard margin may remain as an ablation or sanity-check axis, not as the
+main theorem.
+
+## Current Diagnostic
+
+The script
+
+`scripts/fa_tangent_kernel_capacity.py`
+
+computes \(J_{\mathrm{BP}}\), \(\tilde J_{\mathrm{FA}}\),
+\(K_{\mathrm{BP}}\), and \(K_{\mathrm{FA}}\) on the full training set for the
+existing downstream sweep.
+
+A smoke/probe run on the current random-label Adam experiment shows that the
+initial \(K_{\mathrm{FA}}\) often has a large negative symmetric spectrum. The
+continuous-time initial-kernel prediction therefore greatly overestimates FA
+failure, while the actual Adam FA trajectories recover through nonlinear
+alignment dynamics.
+
+This means:
+
+1. the FA tangent-kernel object is the right local capacity object;
+2. the current Adam random-label experiment is not a valid test of a fixed
+   initialization-kernel final-gap theorem;
+3. a quantitative final-gap theory must either use an experiment in the
+   SGD/lazy-kernel regime, or model the time-varying FA alignment trajectory.
+
+Do not present the initial-kernel prediction as a main downstream theorem for
+the existing Adam trajectories.
+
+## References To Cite
+
+- Karhadkar et al., *Mildly Overparameterized ReLU Networks Have a Favorable
+  Loss Landscape*: full-rank training-set Jacobian implies squared-loss critical
+  points are global minimizers; deep-ReLU activation regions can have full-rank
+  Jacobians under explicit rank conditions.
+- Jacot et al., *Neural Tangent Kernel*: finite-data training dynamics are
+  governed by the NTK Gram spectrum; convergence follows kernel principal
+  components.
+- Eilers et al., *A Generalized Neural Tangent Kernel for Surrogate Gradient
+  Learning*: surrogate-gradient methods can be analyzed by a generalized NTK;
+  FA should be treated as a surrogate-gradient learning rule for downstream
+  dynamics.
+- Yun et al., *Small ReLU Networks Are Powerful Memorizers*: ReLU memorization
+  capacity scales with hidden-layer parameter products, supporting the need to
+  treat memorization capacity separately from raw parameter count.
+- Bartlett et al., *Nearly-Tight VC-Dimension and Pseudodimension Bounds for
+  Piecewise Linear Neural Networks*: worst-case expressivity scales differently
+  from local trainability; useful as a background upper-bound reference, not the
+  exact transition predictor.