深度網路為何泛化

設 $\mathcal{D}$ 為資料分佈，$S = \{(x_i, y_i)\} \sim \mathcal{D}^n$，模型 $f_S = A(S)$。

泛化缺口 $\Delta = R(f_S) - R_S(f_S)$，其中 $R = \mathbb{E}_\mathcal{D}[\ell(f,y)]$，$R_S = \frac{1}{n}\sum\ell(f,y_i)$。

經典界 $\Delta \leq O\!\left(\sqrt{p/n}\right)$，$p \gg n$ 時 vacuous。需要不依賴 $p$ 的界。

設 $f(\cdot;\theta)$ 為參數化預測器，Jacobian $J \in \mathbb{R}^{n \times p}$，$J_{ij} = \partial f(x_i;\theta)/\partial\theta_j$。

SVD: $J = U\Sigma V^T$，奇異值 $\sigma_1 \geq \cdots \geq \sigma_r > 0$。

定義測試梯度投影：$\psi_j(x) = \nabla_\theta f(x;\theta)^T v_j$

定義交叉相關矩陣：$\Gamma_{jl} = \mathbb{E}_x[\psi_j(x)\psi_l(x)]$

噪聲傳播算子：$$M = \Sigma^{-1} \Gamma \Sigma^{-1}$$

$M$ 量化了訓練噪聲如何通過 Jacobian 的譜結構傳播到測試預測：

• $\Sigma^{-1}$ 放大小奇異值方向的噪聲
• $\Gamma$ 決定這些方向在測試點上是否「可見」
• $\operatorname{tr}(M)$ 是噪聲洩漏的總量

設定：插值條件 $f(x_i;\theta^*) = y_i$，噪聲 $y_i = g^*(x_i) + \xi_i$，$\xi_i \sim \text{subGaussian}(0, \sigma^2)$

結論（以機率 $\geq 1-\delta$）：

$$\text{MSE}_{\text{test}} \leq B^2_{\text{signal}} + \sigma^2 \cdot \operatorname{tr}(M) + C\sigma^2\|M\|_F\sqrt{\log(1/\delta)} + \delta^2_{\text{lin}}$$

Step 1. 分解測試預測為信號 + 噪聲：$f(x;\theta^*) - g^*(x) = S(x) + N(x)$

Step 2. 噪聲洩漏的期望：$\mathbb{E}_\xi[\mathbb{E}_x[N(x)^2]] = \sigma^2 \cdot \operatorname{tr}(M)$

Step 3. 集中性（Hanson-Wright）：$P[|Z - \mathbb{E}[Z]| > t] \leq 2\exp(-c\min(t^2/\|M\|_F^2, t/\|M\|_{\text{op}}))$

Step 4. 合併信號偏差 + 噪聲方差 + 集中餘項。

冪律假設：$\sigma_j \sim j^{-\alpha}$，$\rho_j \sim j^{-\beta}$

結論：

• $\beta > \alpha + 1/2$：benign — $\operatorname{tr}(M) < \infty$（噪聲收斂）
• $\beta < \alpha + 1/2$：catastrophic — $\operatorname{tr}(M) = \infty$（噪聲發散）
• $\beta = \alpha + 1/2$：tempered — 對數修正（logarithmic correction）

尾部噪聲洩漏：

$$L_{\text{tail}} = \sum_{j>k} \frac{\rho_j^2}{\sigma_j^2} \sim \sum_{j>k} j^{2(\alpha - \beta)}$$

此級數收斂 $\iff 2(\alpha - \beta) < -1 \iff \beta > \alpha + 1/2$。

當 $\beta = \alpha + 1/2$ 時，$j^{2(\alpha-\beta)} = j^{-1}$，級數為調和級數 $\sim \log(n)$，給出對數修正。

設定：Single-index model $f^*(x) = \varphi(w^{*T} x)$，$\varphi \in H^s$（Sobolev 平滑度 $s$）。

結論：

• NTK 誤差：$E_{\text{NTK}} = \Theta(n^{-2s/(2s+d)})$ — 受維度 $d$ 詛咒
• FL 誤差：$E_{\text{FL}} = \Theta(n^{-2s/(2s+1)})$ — 維度無關
• 改善比：$n^{2s(d-1)/((2s+1)(2s+d))}$

Step 1（NTK）：球諧特徵值 $\lambda_\ell \sim \ell^{-(d+1)}$，重數 $N(d,\ell) \sim \ell^{d-2}$。高維度下重數爆炸導致估計效率低落。

Step 2（FL）：Feature Learning 讓核函數坍縮到一維方向，重數從 $\ell^{d-2}$ 降為 $1$。

Step 3：指數差異 $\frac{2s}{2s+d}$ vs $\frac{2s}{2s+1}$，差距隨 $d$ 增大而擴大。

設定：Single-index model $f^*(x) = \varphi(w^{*T} x)$，$\varphi$ 為 CPL（連續分段線性），$\kappa = 1$（$\mu_1 \neq 0$，即信號在一階 Hermite 係數中可見）。

結論：從隨機初始化出發，GD 幾乎必然收斂到 $w_j \in \text{span}(w^*)$。

收斂速率：$\beta_j / \alpha_j = O(e^{-\gamma t / 2})$，其中橫向分量以指數速率衰減。

路線 A（景觀分析）：

Step 1. ReLU 方向獨立引理：對 CPL 激活函數，損失可分解為方向 $m = \cos(w, w^*)$ 與範數 $\|w\|$ 的函數。

Step 2（定理 5a）：所有全局最小值滿足 $w_j \in \text{span}(w^*)$，即 $m = \pm 1$。

Step 3（定理 5b）：所有非對齊臨界點（$m \neq \pm 1$）都是嚴格鞍點（Hessian 至少有一個嚴格負特徵值）。

Step 4（定理 5c）：GD 幾乎必然避開嚴格鞍點（Lee et al. 2016；或由 tame function theory 推出——損失為 definable function，鞍點的穩定流形為零測集）。

設定：2-layer ReLU teacher-student。Teacher: $f^*(x) = \sum_j a^*_j \operatorname{relu}(w^{*T}_j x)$，$w^*_j$ 正交。Student: $f_\theta = \frac{1}{\sqrt{p}} \sum_j a_j \operatorname{relu}(w_j^T x)$，$p \gg k$。Rich regime $\alpha \to 0$。

結論：

• $\sigma_i(J) \geq c\sqrt{n}$，對 $i \leq k(d+1)$
• $\sigma_i(J) \leq C\alpha$，對 $i > k(d+1)$
• 有效秩 $r_{\text{eff}} \leq k(d+1)$

Step 1（GF → k-sparse aligned）：梯度流使學生神經元的權重對齊到教師方向，僅 $k$ 個方向有顯著激活。

Step 2（active block rank = $k(d+1)$）：每個活躍神經元貢獻 $d+1$ 個自由度（$d$ 個方向分量 + 1 個幅度），活躍 block 的秩為 $k(d+1)$。

Step 3（dead block $\|K_{\text{dead}}\| = O(\alpha^2)$）：未對齊的「死」神經元對 Jacobian 的貢獻被 $\alpha$ 抑制，其核範數為 $O(\alpha^2)$。

Step 4（Weyl inequality）：由 Weyl 不等式，活躍 block 的大奇異值與死 block 的微小擾動之間形成清晰的譜間隙。

定義：$L^* = \min\{L : \beta > \alpha + \tfrac{1}{2}\}$，即使泛化界從 trivial 變為 non-trivial 的最小深度。

FC ReLU：$\alpha_0 = \frac{1}{d-1}$，$\beta_0 = \frac{2}{d-1}$。每層累積 $\beta_0$，需要 $L^* = \lceil(d-1)/2\rceil$ 層。

ResNet：skip connection 使 $\alpha$ 不隨深度累積，$L^*$ 與深度解耦，$L^* = 1$（常數）。

Transformer：softmax attention 提供 $+\tfrac{1}{2}\beta_0$ 的加成，$L^* \approx 1\text{-}4$。

FC ReLU 推導：

每層 ReLU 提供噪聲衰減率 $\beta_0 = 2/(d-1)$。$L$ 層後累積衰減為 $L \cdot \beta_0$。要求 $L \cdot \beta_0 > \alpha + 1/2$，其中 $\alpha = 1/(d-1)$。解得 $L > (d-1)/2$，故 $L^* = \lceil(d-1)/2\rceil$。

ResNet 推導：

skip connection $h_{l+1} = h_l + f_l(h_l)$ 使殘差分支的噪聲不會疊加到主路徑。$\alpha$ 保持為單層量級，不隨深度累積。因此 $\beta > \alpha + 1/2$ 的條件與深度 $L$ 無關，$L^*$ 為常數。

Transformer 推導：

softmax attention 的歸一化效應等同於額外的噪聲濾波器，為每層提供 $+1/2 \cdot \beta_0$ 的加成。等效衰減率為 $3/(2(d-1))$ per layer，故 $L^* \approx \lceil(d-1)/3\rceil$，在實際維度下約為 $1\text{-}4$ 層。

在 2-homogeneous ReLU 網路中，$\frac{d}{dt}(a_j^2 - \|w_j\|^2) = 0$。

證明：由 Euler 定理，2-homogeneous 函數滿足 $f(\lambda\theta) = \lambda^2 f(\theta)$，對 $\lambda$ 微分後代入 $\lambda=1$，得到 $a_j \dot{a}_j = w_j^T \dot{w}_j$，進而 $\frac{d}{dt}(a_j^2 - \|w_j\|^2) = 0$。

Matrix Bernstein bound：$\|\hat{J}^T\hat{J}/n - K_{\text{pop}}\|_{\text{op}}$ 隨 $n$ 增大以 $O(1/\sqrt{n})$ 速率收斂到 0。

具體地，以高機率 $\|\hat{J}^T\hat{J}/n - K_{\text{pop}}\|_{\text{op}} \leq C\sqrt{\frac{\log p}{n}}$。

Weyl 不等式上界：$\sigma_j(J_{\text{total}}) \leq C \cdot j^{-L\alpha_0}$。

2×2 反例：存在矩陣 $A, B$ 使得 $\sigma(AB) \neq \sigma(A) \cdot \sigma(B)$，乘積的奇異值可大於各因子奇異值的乘積。

Weight decay 嚴格降低 $\|\theta\|^2$，但 不一定降低 $\operatorname{tr}(J^T J)$。

反例：2-neuron、2-datapoint 的情境中，$\operatorname{tr}(J^T J)$ 可增加高達 49%。

ReLU 網路的損失函數是 definable（tame）函數：雖然不可微分，但其 Clarke subdifferential 在折角處仍提供下降方向。

梯度流幾乎必然避開所有非光滑臨界點，收斂到光滑臨界點。

Population gradient 中的信號項量級為 $d^{-\kappa/2}$，SGD 採樣噪聲量級為 $1/\sqrt{n}$。

要求信號 > 噪聲，即 $d^{-\kappa/2} > C/\sqrt{n}$，等價於 $n > C' \cdot d^\kappa$。

對任意非仿射光滑激活函數 $\varphi$，加入 $\lambda$-正則化後，在 Phase 2 中神經元方向 support 坍縮到 $w^*$。

$\lambda = 0$：神經元方向保持分散。$\lambda > 0$：方向逐漸收斂。

Phase 1 的時間尺度為 $T_1 = \Theta(d^\kappa)$，其中 $\kappa$ 是目標函數 $f^*$ 的資訊指數。

$\kappa = 1$：$T_1 \sim d$（線性增長），$\kappa = 2$：$T_1 \sim d^2$（二次增長）。

對正交 multi-index 模型 $f^*(x) = \sum_j g_j(\langle w_j^*, x\rangle)$，各方向 $w_j^*$ 依序在時間 $T_j$ 被學到。

$T_1 < T_2 < \cdots < T_r$，對齊度 $m_j(t) = |\langle \bar{w}_j(t), w_j^*\rangle|$ 依序從 0 升到 1。

當 $\sigma_{\min}(V^*) > c$ 時，可透過 SVD 將非正交問題分離為正交子問題。

當 $\sigma_{\min}(V^*)$ 接近 0 時（方向幾乎共線），一階方法失效，需要二階方法（如 Hessian-based）。

$\operatorname{tr}(M) = \sigma^2 \sum s_i^{-4}$。

$\gamma < 1$：$\operatorname{tr}(M)/n \to \sigma^2(1+\gamma)/(1-\gamma)^3$。

$\gamma = 1$：$s_{\min}\to 0$，$\operatorname{tr}(M)\to\infty$。

$\gamma > 1$：minimum-norm improves conditioning。

Phase I（memorization）：$\kappa(J)$ extreme，$\operatorname{tr}(M) = O(e^{cn})$。

Phase II（compression）：weight decay + L-homogeneity → $\operatorname{tr}(M)$ exponential decay。

Phase transition at $\kappa(J_t) \leq \kappa_{\mathrm{crit}}$。

純交互目標 $f^*(x) = g(\langle v_1^*, x\rangle \cdot \langle v_2^*, x\rangle)$：一階梯度 $\nabla_w \mathcal{L}$ 中不含 $v_i^*$ 的資訊（信號為零）。

Hessian $\nabla^2_w \mathcal{L}$ 的前 $p$ 個特徵向量可定位 $\{v_i^*\}$。以此初始化後，GD 在 $\tilde{O}(d^p)$ 步內收斂。

對深度 $L$ 的網路，定理 1 的泛化界仍成立：$R(f) \leq \hat{R}_n(f) + \sqrt{\operatorname{tr}(M)/n}$。

逼近誤差 $B^2 \leq C \cdot e^{-cL}$：深度每增加一層，逼近誤差指數下降。

Cross-Entropy 損失下，benign/catastrophic 過擬合的分界條件為 $\beta > \alpha + 1/2$，與 MSE 完全一致。

Neural Collapse 現象：最後一層特徵收斂到 $(K-1)$ 維正則單純形，有效秩 $r_{\text{eff}} = K - 1$。

噪聲算子 $M$ 的定義 $M_{jk} = \mathbb{E}[f(x)\phi_j(x)\phi_k(x)]$ 對任意輸入分佈成立，不需高斯假設。

當資料集中在 $d_M$ 維流形上時，泛化界中的 $d$ 可替換為 $d_M$，修正項為 $\sqrt{r_{\text{eff}}/n}$。