From 4855e065e8426244035b5ef9c0b4a4b74da163ce Mon Sep 17 00:00:00 2001 From: YurenHao0426 Date: Thu, 28 May 2026 22:45:41 -0500 Subject: Initialize project notes --- .gitignore | 38 +++++ notes/00_project_overview.md | 141 +++++++++++++++++ notes/01_theory_notes.md | 356 +++++++++++++++++++++++++++++++++++++++++++ notes/02_experiment_notes.md | 217 ++++++++++++++++++++++++++ notes/03_paper_outline.md | 194 +++++++++++++++++++++++ notes/README.md | 22 +++ 6 files changed, 968 insertions(+) create mode 100644 .gitignore create mode 100644 notes/00_project_overview.md create mode 100644 notes/01_theory_notes.md create mode 100644 notes/02_experiment_notes.md create mode 100644 notes/03_paper_outline.md create mode 100644 notes/README.md diff --git a/.gitignore b/.gitignore new file mode 100644 index 0000000..76f4c78 --- /dev/null +++ b/.gitignore @@ -0,0 +1,38 @@ +# Python +__pycache__/ +*.py[cod] +*.pyo +.pytest_cache/ +.mypy_cache/ +.ruff_cache/ +.coverage +htmlcov/ + +# Virtual environments +.venv/ +venv/ +env/ + +# Jupyter +.ipynb_checkpoints/ + +# Experiment outputs +runs/ +outputs/ +artifacts/ +checkpoints/ +wandb/ +tensorboard/ + +# Data +data/ +datasets/ + +# OS and editor files +.DS_Store +Thumbs.db +.idea/ +.vscode/ + +# Logs +*.log diff --git a/notes/00_project_overview.md b/notes/00_project_overview.md new file mode 100644 index 0000000..3f8696e --- /dev/null +++ b/notes/00_project_overview.md @@ -0,0 +1,141 @@ +# Project Overview + +## Working Title + +Distributional Capacity Bounds for Feedback Alignment in Multilayer Perceptrons + +## Core Question + +Feedback alignment (FA) replaces the exact BP feedback operator with a fixed random matrix. The central question is: + +> Can we quantify, distributionally and architecturally, how much additional alignment burden FA introduces relative to BP? + +The goal is not to claim that architecture alone predicts final test accuracy. The goal is to derive distributional bounds and capacity proxies for the extra alignment burden induced by random feedback, then validate how these proxies relate to observed FA/BP trajectory gaps. + +## Contribution Map + +### 1. Capacity Formalization + +Define a hierarchy of capacity notions for FA: + +- Angular alignment statistic. +- Log-volume parameter capacity cost. +- Task-projected functional capacity. + +Layerwise alignment: + +\[ +Q_l = +\cos^2(W_{l+1}^{\top}, B_l) += +\frac{ +\langle W_{l+1}^{\top}, B_l\rangle_F^2 +}{ +\|W_{l+1}^{\top}\|_F^2 \|B_l\|_F^2 +}. +\] + +If directions are independent and isotropic in dimension \(D_l=n_l n_{l+1}\): + +\[ +Q_l \sim \mathrm{Beta}\left(\frac12,\frac{D_l-1}{2}\right). +\] + +Define log-volume cost: + +\[ +C_l(q) = +-\log \Pr(Q_l\ge q) += +-\log\left[ +1-I_q\left(\frac12,\frac{D_l-1}{2}\right) +\right]. +\] + +### 2. Scaling Law and Redundancy Exhaustion + +Across independent layers: + +\[ +p_{\mathrm{all}} = \prod_l p_l(q_l), +\qquad +C_{\mathrm{all}} = -\log p_{\mathrm{all}} = \sum_l C_l(q_l). +\] + +Therefore: + +- Log-capacity cost accumulates linearly. +- Raw feasible volume decays geometrically. + +For equal-width MLPs with width \(n\), depth \(L\), and fixed threshold \(q\): + +\[ +C_{\mathrm{all}} = \Theta(Ln^2), +\qquad +p_{\mathrm{all}} = \exp[-\Theta(Ln^2)]. +\] + +Functional gap should appear when alignment constraints exhaust redundant directions. With total parameter dimension \(P\), local task rank \(d=\operatorname{rank}(J)\), and effective alignment constraint rank \(k\): + +\[ +\Delta d_{\mathrm{hard}} += +\max(0, k-(P-d)). +\] + +### 3. Prior-Free Minimax Bound + +For normalized feedback direction: + +\[ +\hat b = \frac{\operatorname{vec}(B)}{\|B\|_F}\in \mathbb S^{D-1}, +\] + +any initialization distribution \(\mu\) induces: + +\[ +M_\mu = \mathbb E_{\mu}[\hat b\hat b^\top], +\qquad +\operatorname{tr} M_\mu = 1. +\] + +For unknown target direction \(a\): + +\[ +\mathbb E_\mu[(a^\top \hat b)^2] = a^\top M_\mu a. +\] + +Thus: + +\[ +\sup_\mu \inf_{\|a\|=1} +\mathbb E_\mu[(a^\top \hat b)^2] += +\frac1D. +\] + +Isotropic random feedback achieves this minimax optimum. Scale, orthogonality, sparsity, and low rank can affect conditioning or cost, but cannot break the prior-free angular bound. + +### 4. Distributional Validation + +Validate: + +- The beta law for static alignment. +- Capacity scaling across width, depth, rank, sparsity, and threshold. +- Redundancy-exhaustion transition. +- Relationship between capacity proxies and trajectory-level FA/BP gaps. + +## Scope Control + +Initial scope: + +- MLPs. +- Dense FA first. +- Gaussian or isotropic feedback first. +- Synthetic regression and simple classification benchmarks. + +Defer: + +- CNNs, Transformers, BatchNorm, residual networks. +- Strong claims about final test accuracy. +- Biologically detailed interpretations. diff --git a/notes/01_theory_notes.md b/notes/01_theory_notes.md new file mode 100644 index 0000000..c0ac8fe --- /dev/null +++ b/notes/01_theory_notes.md @@ -0,0 +1,356 @@ +# Theory Notes + +## Notation + +MLP widths: + +\[ +n_0,n_1,\dots,n_L. +\] + +Forward weights: + +\[ +W_l\in \mathbb R^{n_l\times n_{l-1}}. +\] + +For ordinary FA, feedback matrix for layer \(l\): + +\[ +B_l\in \mathbb R^{n_l\times n_{l+1}}, +\] + +which replaces: + +\[ +W_{l+1}^{\top}\in \mathbb R^{n_l\times n_{l+1}}. +\] + +Matrix direction dimension: + +\[ +D_l=n_l n_{l+1}. +\] + +## Candidate Theorem 1: Static Alignment Distribution + +Assume: + +- \(A_l=W_{l+1}^{\top}\). +- \(A_l/\|A_l\|_F\) and \(B_l/\|B_l\|_F\) are independent isotropic directions in \(\mathbb R^{D_l}\). + +Define: + +\[ +Q_l = +\frac{ +\langle A_l,B_l\rangle_F^2 +}{ +\|A_l\|_F^2\|B_l\|_F^2 +}. +\] + +Then: + +\[ +Q_l\sim +\mathrm{Beta}\left(\frac12,\frac{D_l-1}{2}\right). +\] + +Consequences: + +\[ +\mathbb E[Q_l]=\frac1{D_l}. +\] + +\[ +D_lQ_l \Rightarrow \chi_1^2 +\quad +\text{as } D_l\to\infty. +\] + +Tail: + +\[ +\Pr(Q_l\ge q) += +1-I_q\left(\frac12,\frac{D_l-1}{2}\right). +\] + +High-dimensional approximation to refine: + +\[ +\Pr(Q_l\ge q) +\lesssim +2\exp\left[-\frac{(D_l-1)q}{2}\right]. +\] + +## Capacity Definition + +For a required alignment threshold \(q\): + +\[ +C_l(q) += +-\log \Pr(Q_l\ge q). +\] + +Under the beta law: + +\[ +C_l(q) += +-\log +\left[ +1-I_q\left(\frac12,\frac{D_l-1}{2}\right) +\right]. +\] + +High-dimensional approximation: + +\[ +C_l(q) +\approx +\frac{D_l-1}{2}\log\frac1{1-q}. +\] + +Small-\(q\) approximation: + +\[ +C_l(q)\approx \frac{D_l q}{2}. +\] + +Open detail: decide whether logs are natural logs or base-2 bits. Use natural logs in theorem statements unless the paper explicitly wants bit units. + +## Candidate Corollary 1: Multilayer Scaling + +If layerwise feedback matrices are independent and act on distinct matrix blocks, then: + +\[ +p_{\mathrm{all}} += +\prod_l +\Pr(Q_l\ge q_l), +\] + +and: + +\[ +C_{\mathrm{all}} += +\sum_l C_l(q_l). +\] + +Interpretation: + +- Log-capacity cost is additive. +- Raw feasible volume is multiplicative. + +Equal-width case: + +\[ +D_l\approx n^2. +\] + +Fixed threshold \(q>0\): + +\[ +C_{\mathrm{all}}=\Theta(Ln^2). +\] + +Chance-level threshold \(q=c/D_l\): + +\[ +C_l\approx c/2, +\qquad +C_{\mathrm{all}}=\Theta(L). +\] + +## Candidate Theorem 2: Prior-Free Minimax Bound + +Let: + +\[ +\hat b=\frac{\operatorname{vec}(B)}{\|B\|_F}\in\mathbb S^{D-1}. +\] + +Any feedback initialization distribution \(\mu\) induces: + +\[ +M_\mu=\mathbb E_\mu[\hat b\hat b^\top], +\qquad +\operatorname{tr}M_\mu=1. +\] + +For target direction \(a\in\mathbb S^{D-1}\): + +\[ +\mathbb E_\mu[(a^\top \hat b)^2]=a^\top M_\mu a. +\] + +Since: + +\[ +\lambda_{\min}(M_\mu)\le \frac{\operatorname{tr}M_\mu}{D}=\frac1D, +\] + +we have: + +\[ +\inf_{\|a\|=1} +\mathbb E_\mu[(a^\top \hat b)^2] +\le +\frac1D. +\] + +Thus: + +\[ +\sup_\mu +\inf_{\|a\|=1} +\mathbb E_\mu[(a^\top \hat b)^2] += +\frac1D. +\] + +Isotropic initialization attains this bound. + +## Prior-Aware Corollary + +If target directions have prior covariance: + +\[ +\Sigma_A=\mathbb E[aa^\top], +\] + +then: + +\[ +\mathbb E_{a,B}[(a^\top \hat b)^2] += +\operatorname{tr}(\Sigma_A M_\mu). +\] + +Therefore the optimal structured feedback distribution depends on the eigenspectrum of \(\Sigma_A\). Without prior information, isotropy is minimax; with prior information, top-eigenspace feedback can be better. + +## Functional Capacity + +Let total parameter dimension be: + +\[ +P=\sum_l n_l(n_{l-1}+1). +\] + +Let task Jacobian be: + +\[ +J=\frac{\partial f_\theta(X)}{\partial \theta}. +\] + +Local task rank: + +\[ +d=\operatorname{rank}(J). +\] + +If alignment constraints remove a generic \(k\)-dimensional parameter subspace, then hard local function rank after constraints is: + +\[ +d_{\mathrm{hard}}=\min(d,P-k). +\] + +Hard functional loss: + +\[ +\Delta d_{\mathrm{hard}} += +d-d_{\mathrm{hard}} += +\max(0,k-(P-d)). +\] + +Soft overlap model. Let \(E\) be the alignment constraint subspace and \(S\) be the task-sensitive subspace: + +\[ +T_k=\operatorname{tr}(P_E P_S). +\] + +For random subspaces: + +\[ +\mathbb E[T_k]=\frac{kd}{P}. +\] + +Variance: + +\[ +\operatorname{Var}(T_k) += +\frac{ +2kd(P-k)(P-d) +}{ +P^2(P-1)(P+2) +}. +\] + +Interpretation: + +- Hard rank loss has a redundancy-exhaustion threshold. +- Soft conditioning loss can grow approximately linearly from the start. + +## Trajectory Bridge + +BP gradient: + +\[ +g_t=\nabla_\theta L(\theta_t). +\] + +FA surrogate gradient: + +\[ +\tilde g_t(B). +\] + +Mismatch: + +\[ +\epsilon_t(B)=\tilde g_t(B)-g_t. +\] + +Linearized deviation from the BP trajectory: + +\[ +\delta\theta_T(B) +\approx +-\eta +\sum_{t How much capacity does random feedback alignment consume, how does it scale, and when does it become a functional FA/BP gap? + +Claims to avoid: + +- Do not claim architecture alone predicts final test accuracy. +- Do not claim the capacity proxy is identical to generalization gap. + +Main contributions: + +1. Capacity formalization. +2. Scaling law and redundancy-exhaustion phase transition. +3. Prior-free minimax bound for feedback initialization. +4. Distributional and trajectory-level empirical validation. + +## 2. Setup + +Define: + +- MLP architecture. +- BP feedback operator. +- FA feedback matrix. +- Layerwise alignment statistic \(Q_l\). +- Dense isotropic initialization assumptions. + +## 3. Distributional Alignment Law + +Theorem: + +\[ +Q_l\sim \mathrm{Beta}\left(\frac12,\frac{D_l-1}{2}\right). +\] + +Consequences: + +- \(\mathbb E[Q_l]=1/D_l\). +- \(D_lQ_l\Rightarrow \chi_1^2\). +- Tail probability via incomplete beta. + +## 4. Capacity Formalization + +Define: + +- Angular statistic. +- Log-volume cost: + +\[ +C_l(q)=-\log\Pr(Q_l\ge q). +\] + +- Functional capacity via task Jacobian \(J\). + +Explain why parameter-volume capacity and function capacity differ. + +## 5. Multilayer Scaling and Redundancy Exhaustion + +Multilayer: + +\[ +C_{\mathrm{all}}=\sum_l C_l(q_l). +\] + +Equal-width scaling: + +\[ +C_{\mathrm{all}}=\Theta(Ln^2) +\] + +for fixed \(q\). + +Functional phase transition: + +\[ +\Delta d_{\mathrm{hard}} += +\max(0,k-(P-d)). +\] + +Soft overlap: + +\[ +\mathbb E[\Delta d_{\mathrm{soft}}]\approx \frac{kd}{P}. +\] + +## 6. Prior-Free Minimax Bound + +Theorem: + +\[ +\sup_\mu +\inf_{\|a\|=1} +\mathbb E_\mu[(a^\top \hat b)^2] += +\frac1D. +\] + +Interpretation: + +- Isotropic feedback is minimax optimal without prior information. +- Scale affects norm dynamics, not angular bound. +- Orthogonality affects conditioning, not the prior-free angular limit. +- Sparsity and low rank trade coverage for efficiency. + +Prior-aware corollary: + +\[ +\mathbb E_{a,B}[(a^\top \hat b)^2] += +\operatorname{tr}(\Sigma_A M_\mu). +\] + +## 7. Trajectory Bridge + +Introduce local approximation: + +\[ +\epsilon_t(B)=\tilde g_t(B)-g_t. +\] + +\[ +\delta\theta_T(B) +\approx +-\eta +\sum_{t