# Distributional Capacity Bounds for Feedback Alignment in Multilayer Perceptrons Status: integrated Markdown draft for the current project. This document consolidates the clean version of the theory and experiments. It uses plain-text formulas instead of TeX. ## One-Sentence Claim Random feedback alignment introduces a quantifiable distributional operator burden relative to BP. This burden can be exactly characterized at the level of random matrix alignment and at the initial FA operator level, and prior-free feedback initialization cannot beat the isotropic random baseline in worst-case angular alignment. ## Main Contributions 1. **Distributional capacity formalization.** We define feedback-alignment capacity through matrix-direction alignment and log-volume cost, and derive the exact Beta law for random feedback alignment. 2. **Capacity scaling law.** We prove that raw feasible volume multiplies across independent feedback blocks while log-capacity cost adds. For equal-width MLPs, fixed-threshold log-cost scales like `Theta(L n^2)`. 3. **Prior-free minimax feedback initialization.** We prove that without prior information about the target backward direction, no initialization can beat the `1/D` worst-case expected squared-alignment bound. Isotropic random feedback achieves the bound. 4. **Actual FA initial operator erosion.** We prove that the true initial FA operator burden is not the raw feedback-matrix constraint count. Conditional on fixed forward weights and residuals, the expected FA learning-speed loss equals the hidden-layer BP speed share. In one-hidden-layer Gaussian FA, the entire conditional erosion distribution is Gaussian. 5. **Distributional empirical validation.** We validate the theory by sampling large ensembles of random feedback matrices. The empirical matrix-alignment and initial-operator-erosion distributions match the predicted distributions without fitted parameters. ## What This Paper Does Not Claim Do not claim: ```text FA cannot converge in overparameterized networks. ``` This is contradicted by existing overparameterized FA theory in restricted settings. Do not claim: ```text hard capacity margin produces a sharp FA/BP phase transition. ``` Our long-training sweeps showed a soft ramp, not a hard kink. Do not claim: ```text architecture alone predicts all finite-time FA/BP loss gaps. ``` Finite-time gap prediction requires time-dependent operator dynamics. We have useful tangent-operator estimators, but they are not part of the main theorem stack in this cleaned version. ## Setup Consider an MLP with widths: ```text n_0, n_1, ..., n_L ``` Forward weights: ```text W_l in R^{n_l x n_{l-1}} ``` For ordinary FA, the feedback matrix replacing the BP backward map from layer `l+1` to layer `l` is: ```text B_l in R^{n_l x n_{l+1}} ``` The corresponding BP backward matrix is: ```text A_l = W_{l+1}^T ``` with matrix-direction dimension: ```text D_l = n_l n_{l+1} ``` For squared loss on a training set: ```text L = ||r||^2 / (2N) ``` where: ```text r = f_theta(X) - y ``` Let `g_l^BP` be the BP gradient block and `g_l^FA` be the FA pseudo-gradient block at layer `l`. Define the BP local learning speed: ```text speed_BP = sum_l ||g_l^BP||^2 ``` and the FA first-order local learning speed: ```text speed_FA = sum_l ``` The initial FA operator erosion is: ```text e_0(B) = 1 - speed_FA / speed_BP ``` This is the one-step fractional loss of BP learning speed caused by using FA instead of BP. ## Theorem 1: Random Feedback Alignment Has an Exact Beta Law ### Statement Let: ```text a = vec(A) / ||A||_F b = vec(B) / ||B||_F ``` where `a` and `b` are independent isotropic directions in `R^D`. Define squared alignment: ```text Q = (a^T b)^2 ``` Then: ```text Q ~ Beta(1/2, (D - 1)/2) ``` Equivalently: ```text P(Q <= q) = I_q(1/2, (D - 1)/2) ``` where `I_q` is the regularized incomplete beta function. For layer `l`: ```text D_l = n_l n_{l+1} Q_l = cos^2(W_{l+1}^T, B_l) Q_l ~ Beta(1/2, (D_l - 1)/2) ``` High-dimensional approximation: ```text D Q -> chi-square_1 E[Q] = 1/D typical |cos angle| = O(D^{-1/2}) ``` ### Capacity Cost For an alignment threshold `q`, define: ```text p(q) = P(Q >= q) C(q) = -log p(q) ``` Using the Beta law: ```text C(q) = -log [1 - I_q(1/2, (D - 1)/2)] ``` For small `q`: ```text C(q) approximately (D q) / 2 ``` For fixed `q` in high dimension: ```text C(q) approximately ((D - 1)/2) log(1/(1-q)) ``` ### Proof Sketch By rotational invariance, fix `a = e_1`. Then: ```text Q = b_1^2 ``` where `b` is uniform on the unit sphere in `R^D`. The squared first coordinate of a uniform sphere vector follows: ```text Beta(1/2, (D - 1)/2) ``` This gives the result. ## Theorem 2: Log-Capacity Cost Adds Across Independent Feedback Blocks ### Statement For independent layerwise feedback matrices, let: ```text p_l(q_l) = P(Q_l >= q_l) C_l(q_l) = -log p_l(q_l) ``` Then the probability that all alignment thresholds are met is: ```text p_all = product_l p_l(q_l) ``` and total log-volume capacity cost is: ```text C_all = -log p_all = sum_l C_l(q_l) ``` For equal-width hidden layers with width `n` and depth `L`, ordinary FA has: ```text D_l approximately n^2 ``` For fixed threshold `q > 0`: ```text C_all = Theta(L n^2) p_all = exp[-Theta(L n^2)] ``` For chance-level thresholds: ```text q_l = c / D_l ``` the per-layer cost is constant: ```text C_l approximately c/2 C_all = Theta(L) ``` ### Interpretation Capacity cost is linear in log-volume units. Raw feasible volume decays geometrically. This resolves the question: ```text linear or geometric? ``` Answer: ```text log-capacity cost: linear raw volume/probability: geometric/exponential ``` ### Proof Sketch Independence gives multiplication of feasible probabilities. Taking `-log` turns products into sums. The equal-width MLP scaling follows from: ```text D_l = n_l n_{l+1} approximately n^2 ``` and from the high-dimensional capacity approximation. ## Soft-Capacity Null Model This is not the exact FA theorem, but it is a useful sanity model. Let: ```text P = parameter dimension k = dimension of a random constrained subspace J = training-set output Jacobian K_BP = J J^T E = Haar-random k-dimensional subspace P_E = projection onto E Q = I - P_E K_Q = J Q J^T ``` Then: ```text E[P_E] = (k/P) I E[Q] = (1 - k/P) I E[K_Q | J] = (1 - k/P) K_BP ``` For residual direction `r`, define: ```text e(r) = 1 - (r^T K_Q r) / (r^T K_BP r) ``` If `v = J^T r`, then: ```text e(r) = ||P_E v||^2 / ||v||^2 ``` For Haar-random `E`: ```text e(r) ~ Beta(k/2, (P-k)/2) E[e(r)] = k/P ``` This proves the soft-capacity intuition: ```text capacity dilutes random constraints through k/P but does not make them exactly zero unless k=0 or k/P -> 0 ``` But actual FA is not literally Haar-random deletion of `k` parameter dimensions. Experiments showed hard `k` overpredicts real FA gaps. The actual FA theorem below is the main result for real FA. ## Theorem 3: Prior-Free Minimax Initialization Bound ### Statement Let: ```text b = normalized feedback direction in R^D a = unknown normalized target backward direction in R^D ``` Let `mu` be any feedback initialization distribution, and define: ```text M_mu = E_mu[b b^T] trace(M_mu) = 1 ``` Then for target direction `a`: ```text E_mu[(a^T b)^2] = a^T M_mu a ``` So: ```text inf_{||a||=1} E_mu[(a^T b)^2] = lambda_min(M_mu) <= 1/D ``` Therefore: ```text sup_mu inf_{||a||=1} E_mu[(a^T b)^2] = 1/D ``` Isotropic random feedback achieves the bound: ```text M_mu = I/D ``` ### Interpretation Without prior information about the target backward direction, no feedback initialization can beat isotropic random feedback in worst-case expected squared alignment. Scale, orthogonality, sparsity, and low rank may affect: ```text signal norm conditioning hardware cost rank/channel capacity ``` but they cannot beat the prior-free angular minimax bound. ### Prior-Aware Corollary If target directions follow a prior with covariance: ```text Sigma_A = E[a a^T] ``` then: ```text E_{a,b}[(a^T b)^2] = trace(Sigma_A M_mu) ``` With a prior, optimal feedback should allocate mass to high-eigenvalue directions of `Sigma_A`. Thus: ```text no prior -> isotropic minimax with prior -> structure-aware feedback can improve average alignment ``` ## Theorem 4: Actual FA Initial Operator Erosion ### Statement Fix: ```text forward weights W training data X,y residual r ReLU gates induced by W ``` Assume: ```text feedback matrices B_l are independent of W and r feedback matrices have zero first moment the output layer uses the true output gradient ``` Let: ```text speed_BP = sum_l ||g_l^BP||^2 speed_FA = sum_l e_0(B) = 1 - speed_FA / speed_BP ``` Then: ```text E_B[speed_FA | W,r] = ||g_output^BP||^2 ``` and: ```text E_B[e_0 | W,r] = 1 - ||g_output^BP||^2 / sum_l ||g_l^BP||^2 ``` Equivalently: ```text E_B[e_0 | W,r] = hidden BP speed share ``` ### Why This Matters The initial effective FA burden is not the raw number of feedback matrix constraints. It is the fraction of BP learning speed carried by hidden-layer gradient blocks. This is a real FA theorem, not a random-subspace proxy. ### Proof Sketch The output-layer FA gradient equals the BP gradient: ```text g_output^FA = g_output^BP ``` Thus: ```text = ||g_output^BP||^2 ``` For any hidden layer, the FA pseudo-gradient contains at least one zero-mean independent feedback matrix. Conditional on fixed `W`, `r`, activations, and gates: ```text E_B[g_l^FA | W,r] = 0 ``` Since `g_l^BP` is fixed under the same conditioning: ```text E_B[ | W,r] = = 0 ``` Summing layers leaves only the output-layer term. ## Theorem 5: Exact e0 Distribution for One-Hidden-Layer Gaussian FA ### Setup Consider a one-hidden-layer ReLU MLP: ```text x -> W1 -> ReLU -> W2 -> output ``` with Gaussian feedback: ```text B_{a,c} independent Normal(0, sigma_B^2) ``` For fixed `W1`, `W2`, data, residuals, activations, and gates: ```text speed_BP = ||g_output^BP||^2 + ||g_hidden^BP||^2 speed_FA = ||g_output^BP||^2 + ``` The hidden mixed term is linear in `B`: ```text = ``` where `C(W,r)` is an explicit coefficient matrix determined by data, activations, gates, residuals, and the BP hidden gradient. ### Statement Because `B` is Gaussian: ```text ~ Normal(0, sigma_B^2 ||C(W,r)||_F^2) ``` Therefore: ```text e_0(B) = 1 - speed_FA / speed_BP ``` has exact conditional distribution: ```text e_0(B) ~ Normal(mean_e, std_e^2) ``` with: ```text mean_e = 1 - ||g_output^BP||^2 / speed_BP std_e = sigma_B ||C(W,r)||_F / speed_BP ``` This is the cleanest distributional theorem for actual FA. ### Coefficient Matrix Let: ```text x_n = input sample n delta_n,c = output residual gradient for output c gate_n,a = ReLU gate of hidden unit a g_bp_a,d = BP hidden gradient entry for hidden unit a and input dim d ``` Then: ```text S_{a,c,d} = sum_n gate_n,a x_n,d delta_n,c C_{a,c} = sum_d g_bp_a,d S_{a,c,d} ``` and: ```text = sum_{a,c} C_{a,c} B_{a,c} ``` ## Experiments ### Experiment 1: Matrix Alignment Beta Law Object: ```text Q = cos^2(A,B) ``` Theory: ```text Q ~ Beta(1/2, (D - 1)/2) ``` Validation: ```text sample many independent A,B plot empirical histogram against Beta density run QQ/KS checks ``` Relevant script: ```text scripts/static_alignment_beta.py ``` ### Experiment 2: Capacity Scaling Object: ```text C_all = sum_l -log P(Q_l >= q_l) ``` Theory: ```text equal-width MLP, fixed q: C_all = Theta(L n^2) ``` Validation: ```text sweep width/depth compare computed log-volume capacity with predicted scaling ``` Relevant scripts: ```text scripts/capacity_scaling.py scripts/multilayer_capacity_distribution.py ``` ### Experiment 3: Actual FA Initial e0 Mean Object: ```text E_B[e_0 | W,r] ``` Theory: ```text E_B[e_0 | W,r] = hidden BP speed share ``` Validation: ```text fix W and data sample many B compare empirical mean e0 with predicted hidden BP speed share ``` Relevant script: ```text scripts/actual_fa_initial_operator_moments.py ``` Representative results: ```text width=16 init=0: theory=0.451931 empirical=0.444348 width=24 init=0: theory=0.312016 empirical=0.312286 width=32 init=0: theory=0.236058 empirical=0.239714 width=64 init=0: theory=0.209125 empirical=0.211261 width=96 init=0: theory=0.259765 empirical=0.259147 ``` ### Experiment 4: Exact e0 Distribution Object: ```text e_0(B) ``` Theory for one-hidden Gaussian FA: ```text e_0(B) ~ Normal(mean_e, std_e^2) ``` Validation: ```text fix W and data sample 4096 random feedback matrices B per initialization plot empirical histogram against predicted Gaussian density ``` Script: ```text scripts/actual_fa_initial_erosion_distribution.py ``` Run: ```text python scripts/actual_fa_initial_erosion_distribution.py \ --widths 16 32 64 128 \ --init-seeds 3 \ --feedback-samples 4096 \ --torch-threads 8 \ --outdir outputs/actual_fa_initial_erosion_distribution ``` Main figures: ```text outputs/actual_fa_initial_erosion_distribution/e0_distribution_theory_vs_empirical.png outputs/actual_fa_initial_erosion_distribution/e0_distribution_moment_calibration.png ``` Representative results: | width | init | theory mean | empirical mean | theory std | empirical std | KS | p-value | |---:|---:|---:|---:|---:|---:|---:|---:| | 16 | 0 | 0.113830 | 0.113413 | 0.027228 | 0.027401 | 0.0150 | 0.314 | | 16 | 1 | 0.113705 | 0.113859 | 0.027261 | 0.027278 | 0.0103 | 0.778 | | 32 | 0 | 0.121730 | 0.121544 | 0.018952 | 0.018693 | 0.0114 | 0.654 | | 32 | 2 | 0.227193 | 0.227691 | 0.031148 | 0.030779 | 0.0166 | 0.206 | | 64 | 0 | 0.031155 | 0.031119 | 0.003652 | 0.003583 | 0.0118 | 0.609 | | 128 | 0 | 0.023004 | 0.022989 | 0.001630 | 0.001610 | 0.0135 | 0.441 | Interpretation: ```text theory density and empirical random-feedback histogram coincide without fitted parameters ``` This is the current strongest figure. ## Related Work Positioning ### Lillicrap et al.: Random Feedback Can Learn Lillicrap et al. showed that fixed random feedback weights can support learning and observed alignment of forward weights with feedback pathways. Positioning: ```text They show random feedback can be useful. We quantify the distributional operator burden random feedback introduces. ``` Source: ```text https://www.nature.com/articles/ncomms13276 ``` ### Nøkland: Direct Feedback Alignment DFA showed random direct feedback can train deep networks in several settings. Positioning: ```text Eventual trainability does not imply BP-equivalent local operator dynamics. ``` Source: ```text https://papers.neurips.cc/paper/6441-direct-feedback-alignment-provides-learning-in-deep-neural-networks ``` ### Refinetti et al.: Align, Then Memorise Refinetti et al. developed an align-then-memorise picture for DFA dynamics. Positioning: ```text They analyze training-time alignment dynamics. Our main theorem isolates the exact initialization-level operator burden and its distribution. ``` Source: ```text https://arxiv.org/abs/2011.12428 ``` ### Song, Xu, and Lafferty: Overparameterized FA Convergence Song, Xu, and Lafferty prove convergence of two-layer FA in an overparameterized regime and show alignment need not occur without regularization. They decompose: ```text K_FA = G + H_FA ``` where `G` is a positive top-layer kernel and `H_FA` is the hidden feedback-dependent term. Positioning: ```text Their result shows FA can converge. Our result shows convergence does not imply zero initial operator burden or BP-equivalent local learning speed. ``` Our theorem is consistent with their decomposition: ```text E_B[H_FA,0 | W,r] = 0 E_B[K_FA,0 | W,r] = K_output ``` Source: ```text https://papers.nips.cc/paper/2021/file/a576eafbce762079f7d1f77fca1c5cc2-Paper.pdf ``` ### NTK and Lazy Training NTK and lazy-training theory justify local tangent-operator dynamics: ```text r_{t+1} approximately (I - eta K_t/N) r_t ``` For BP: ```text K_BP = J J^T ``` For FA: ```text K_FA = J J_tilde^T ``` Positioning: ```text We use tangent-operator language to define local FA erosion. We do not make finite-time tangent hierarchy the main contribution. ``` Sources: ```text https://papers.nips.cc/paper/8076-neural-tangent-kernel https://papers.nips.cc/paper/9063-wide-neural-networks-of-any-depth-evolve-as-linear-models-under-gradient-descent ``` ## Suggested Paper Structure 1. **Introduction** - FA replaces exact backward weights with random feedback. - Existing work asks whether FA can learn. - This paper asks how much distributional operator/capacity burden random feedback introduces. 2. **Preliminaries** - MLP and FA setup. - Matrix alignment statistic. - Local operator erosion statistic. 3. **Distributional Capacity of Random Feedback** - Theorem 1: Beta law. - Log-volume capacity definition. - Theorem 2: multi-layer scaling. 4. **Limits of Prior-Free Initialization** - Theorem 3: minimax bound. - Discussion of isotropic vs structured feedback. 5. **Actual FA Initial Operator Erosion** - Theorem 4: expected erosion equals hidden BP speed share. - Theorem 5: exact Gaussian e0 distribution for one-hidden Gaussian FA. - Relation to Song/Xu/Lafferty `G + H_FA`. 6. **Experiments** - Static alignment Beta distribution. - Capacity scaling. - e0 mean validation. - exact e0 distribution validation. 7. **Discussion** - What is proven vs estimated. - Why hard phase transition was the wrong model. - Future work: time-dependent alignment dynamics and FA tangent hierarchy. ## Suggested Figure List ### Figure 1: Random Matrix Alignment Distribution Theory: ```text Q ~ Beta(1/2, (D-1)/2) ``` Plot: ```text empirical histogram vs Beta density ``` ### Figure 2: Log-Capacity Scaling Theory: ```text C_all = Theta(L n^2) ``` Plot: ```text C_all vs width/depth ``` ### Figure 3: Minimax Initialization Bound Theory: ```text worst-case expected squared alignment <= 1/D ``` Plot: ```text isotropic feedback at bound; non-isotropic improves some directions and worsens others ``` ### Figure 4: Actual FA e0 Mean Calibration Theory: ```text E_B[e0 | W,r] = hidden BP speed share ``` Plot: ```text predicted mean vs empirical mean over feedback samples ``` Existing path: ```text outputs/actual_fa_initial_operator_moments/predicted_vs_empirical_initial_erosion_mean.png ``` ### Figure 5: Exact e0 Distribution Theory: ```text e0(B) ~ Normal(mean_e, std_e^2) ``` Plot: ```text theory Gaussian density vs empirical random-feedback histogram ``` Existing path: ```text outputs/actual_fa_initial_erosion_distribution/e0_distribution_theory_vs_empirical.png ``` This is currently the strongest figure. ## Open Problems and Appendix Material ### Time-Dependent FA Dynamics At time `t > 0`: ```text speed_FA,t = output_speed_t + hidden_alignment_gain_t ``` where: ```text hidden_alignment_gain_t = sum_hidden ``` At initialization, the hidden alignment gain has zero conditional mean. During training, `W_t` depends on `B`, so the hidden gain can become positive. This is actual feedback alignment. We tested tangent-hierarchy-style estimators: ```text K_FA,t = J_t J_tilde_t^T K_hat_t = K_0 + t (K_s - K_0)/s ``` Empirically, early average velocity improves finite-time gap prediction, but the infinitesimal derivative `dot_K_0` extrapolated to longer horizons is unstable. Conclusion: ```text do not put tangent hierarchy in the main contribution stack use it as appendix/future work ``` Relevant notes: ```text notes/30_literature_methods_for_fa_operator_dynamics.md notes/31_first_order_tangent_hierarchy_try.md ``` ### Deep Linear or Teacher-Student Full-Time Theory A controlled finite-time theory may be possible in: ```text deep linear FA two-layer teacher-student FA/DFA order-parameter dynamics ``` This is a separate project or appendix-level extension. ## Current Best Abstract Draft Feedback alignment replaces exact backpropagation weights with fixed random feedback matrices, raising a basic quantitative question: how much additional capacity or learning-speed burden does random feedback impose relative to BP? We formalize this burden distributionally for multilayer perceptrons. First, we show that the layerwise squared alignment between a random feedback matrix and the corresponding BP backward matrix follows an exact Beta law, yielding a log-volume capacity cost whose total multi-layer cost adds across independent feedback blocks. Second, we prove a prior-free minimax limit: without information about the target backward direction, no feedback initialization can exceed the `1/D` worst-case expected squared-alignment bound achieved by isotropic random feedback. Third, we derive an actual FA operator result: conditional on the forward initialization and residual, the expected initial FA learning-speed erosion equals the hidden-layer share of BP gradient energy. For one-hidden-layer Gaussian FA, the full conditional erosion distribution is Gaussian with computable mean and variance. Large random-feedback ensembles validate the predicted alignment and operator-erosion distributions without fitted parameters. These results separate eventual trainability from BP-equivalent local operator capacity, showing that random feedback may be sufficient for learning while still imposing a quantifiable distributional operator burden. ## Current Best Title ```text Distributional Capacity Bounds for Feedback Alignment in Multilayer Perceptrons ``` Alternative, more focused: ```text Distributional Operator Costs of Feedback Alignment ``` or: ```text Random Feedback Is Not Free: Distributional Operator Bounds for Feedback Alignment ``` The first title is safer and closer to the original project.