SGD 為何收斂到好解？

SGD 迭代：\(\theta_{t+1} = \theta_t - \eta \nabla\ell_{z_t}(\theta_t)\)，\(z_t \sim \text{Uniform}(\{1,\ldots,n\})\)

梯度噪聲方差：\(\Sigma(\theta) = \frac{1}{n}\sum_i [\ell'_i(\theta)]^2 - [L'(\theta)]^2\)

收斂的三層定義：

• (C1) 優化收斂：\(L(\theta_t) \to L^*\) a.s.
• (C2) 分佈收斂：\(\theta_t \to^d \mu_\eta\)（某穩態測度）
• (C3) 吸收收斂：\(\theta_t \to \theta^*\) a.s.

好解的四種定義（reparameterization-invariant）：

• (G1) 低噪聲比：\(\Sigma(\theta^*)/H(\theta^*)\) 在所有極小值中較小
• (G2) 低 Jacobian 複雜度：\(C(\theta^*) = \|J\|_F/\sqrt{n}\) 小（插值域）
• (G3) 穩定解：leave-one-out 穩定性 \(\beta\) 小
• (G4) 泛化解：\(L_{\text{test}} - L_{\text{train}} \le \varepsilon\) 小

核心關聯：SGD 偏好 (G1)/(G2)，而 (G1)→(G3)→(G4)，(G2)→(G4)。

\(d\theta = -\nabla L(\theta)\,dt + \sqrt{\tau\,\Sigma(\theta)}\,dW_t\)，其中 \(\tau = \eta/B\)

在插值解 \(\theta^*\) 附近：\(\delta_{t+1} = (I - \eta J_{z_t}J_{z_t}^\top)\delta_t\)

其中 \(J_i = \nabla_\theta f_{\theta^*}(x_i)\)，\(h_i = \|J_i\|^2\)

1. FPE（Itô）：\(\partial p/\partial t = \partial_\theta[L'p] + (\tau/2)\partial_\theta^2[\Sigma p]\)
2. 穩態 \(\partial p/\partial t = 0\)，定義機率流 \(J = -L'p - (\tau/2)(\Sigma p)'\)
3. \(dJ/d\theta = 0 \Rightarrow J = \text{const}\)
4. 邊界條件 \(p \to 0\) 當 \(|\theta|\to\infty\) → \(J \equiv 0\)
5. 展開：\(L'p + (\tau/2)[\Sigma'p + \Sigma p'] = 0\)
6. \(p'/p = -2L'/(\tau\Sigma) - \Sigma'/\Sigma\)
7. 右側 \(= -\frac{d}{d\theta}\left[\frac{2}{\tau}\int \frac{L'}{\Sigma}d\theta + \ln\Sigma\right]\)
8. 積分：\(\ln p = -\frac{2}{\tau}\int \frac{L'}{\Sigma}d\theta - \ln\Sigma + C\)
9. 取指數：\(p(\theta) = \frac{1}{Z}\cdot\frac{1}{\Sigma(\theta)}\cdot\exp\!\left(-\frac{2}{\tau}\int^\theta \frac{L'(s)}{\Sigma(s)}ds\right)\)
10. 歸一化 \(Z < \infty\) 由 coercive + bounded \(\Sigma\) 保證 ∎

1. 由 Part I，\(p(\theta_k) \propto (1/\Sigma_k)\exp(-(2/\tau)\int^{\theta_k} L'/\Sigma\,d\theta)\)
2. 取比值，\((1/\Sigma)\) 因子比為 \(\Sigma_B/\Sigma_A\)
3. 指數差 \(= (2/\tau)\int_{\theta_A}^{\theta_B} L'/\Sigma\,d\theta\)
4. 對稱情形下 \(L'/\Sigma\) 是反對稱函數，積分 = 0
5. \(p(\theta_A)/p(\theta_B) = \Sigma_B/\Sigma_A > 1\) ∎

1. \(\theta^*\) 是 \(L\) 的極小值，\(L'(\theta^*) = 0\)
2. 移除第 \(j\) 個樣本：\(L'_{-j}(\theta^*) = -\ell'_j(\theta^*)/(n-1)\)
3. \(L''_{-j}(\theta^*) = (nH - \ell''_j)/(n-1) \equiv H_{-j}\)
4. 隱函數定理：\(\theta^*_{-j} - \theta^* \approx \ell'_j(\theta^*)/((n-1)H_{-j})\)
5. LOO 損失差：\(\ell_j(\theta^*_{-j}) - \ell_j(\theta^*) \approx [\ell'_j(\theta^*)]^2/((n-1)H_{-j})\)
6. 平均：\(\frac{1}{n}\sum_j \frac{[\ell'_j]^2}{(n-1)H_{-j}} \approx \frac{\Sigma(\theta^*)}{(n-1)H}\)
7. 識別：\(\frac{1}{n}\sum_j [\ell'_j(\theta^*)]^2 = \Sigma(\theta^*)\)（因 \(L'(\theta^*)=0\)）
8. 泛化間隙 \(\approx L_{\text{test}} - L_{\text{train}} \approx \Sigma/(H(n-1))\)
9. 由 (A6)：\(\text{Gap}(\theta_A) < \text{Gap}(\theta_B)\) ∎

1. 正交假設下，\(A_i = I - \eta J_i J_i^\top\) 在正交基下解耦
2. 每坐標獨立：\((\xi_{t+1})_k = (1-\eta h_k)(\xi_t)_k\)（當 \(z_t=k\)）
3. \(\ln|(\xi_T)_k| = \ln|(\xi_0)_k| + \sum_t X_t^{(k)}\)，\(X_t^{(k)}\) iid
4. 強大數定律：\((1/T)\sum X_t \to \lambda_k = (1/n)\ln|1-\eta h_k|\)
5. \(\eta h_{k^*} > 2 \Rightarrow |1-\eta h_{k^*}|>1 \Rightarrow \lambda_{k^*}>0 \Rightarrow |\xi_T|\to\infty\) a.s. ∎

同 Part A 但符號相反：\(\eta h_k < 2 \Rightarrow |1-\eta h_k|<1 \Rightarrow \lambda_k<0 \Rightarrow |\xi_T|\to 0\) a.s. ∎

1. Taylor：\(f_\theta(x_i) - f_{\theta^*}(x_i) = J_i^\top\delta + r_i(\delta)\)，\(|r_i|\le B_2\rho^2/2\)
2. Rademacher 分解：\(\hat{R} \le E_\sigma[\sup_{\|\delta\|\le\rho} \frac{1}{n}\sum \sigma_i J_i^\top\delta] + B_2\rho^2/2\)
3. 線性部分：\(\sup = (\rho/n)\|\sum \sigma_i J_i\|\)
4. Jensen：\(E[\|\sum \sigma_i J_i\|] \le \sqrt{\sum h_i} = \sqrt{n}\cdot C\)
5. 合併：\(\hat{R} \le \rho C/\sqrt{n} + B_2\rho^2/2\) ∎

設 \(\theta = g(\varphi)\) 是光滑雙射，\(\varphi^* = g^{-1}(\theta^*)\)。

\(\tilde{H} = L''(g(\varphi^*)) \cdot [g'(\varphi^*)]^2 = H \cdot (g')^2\)

\(\tilde{\Sigma} = E_i[(\ell'_i(g(\varphi^*)))^2] \cdot [g'(\varphi^*)]^2 = \Sigma \cdot (g')^2\)

故 \(\tilde{\Sigma}/\tilde{H} = \Sigma \cdot (g')^2 / (H \cdot (g')^2) = \Sigma/H\) ∎

推論：Flatness（\(H\) 小）和 Simplicity（\(\Sigma\) 小）都可被 reparameterization 改變而不影響泛化。但 \(\Sigma/H\) 不變 → 泛化間隙 \(\approx \Sigma/(H(n-1))\) 是內在幾何量。

多維推廣：\(\text{tr}(H^{-1}\Sigma)\) 也是不變的（Jacobian 的 \((J^\top)^2\) 在分子分母抵消）。

1. \(w_0 = 0 \in \text{row}(X)\)
2. SGD 增量 \(= -\eta(w^\top x_{z_t} - y_{z_t})x_{z_t} \in \text{row}(X)\)
3. 歸納：\(w_t \in \text{row}(X)\) 對所有 \(t\)
4. \(\text{row}(X)\) 中唯一的插值解是 \(X^\dagger y\)
5. 凸損失上 SGD 收斂定理 → \(w_t \to X^\dagger y\) ∎

意義：這是代數性質，與噪聲無關。在非線性模型中 SGD 與 GD 的隱式偏差可能不同。

成立條件：\(\text{curl}(\Sigma^{-1}\nabla L) = 0\)，即 \(\partial_i[\Sigma^{-1}\nabla L]_j = \partial_j[\Sigma^{-1}\nabla L]_i\) 對所有 \(i \ne j\)。

特殊情況（自動成立）：

• \(\Sigma = \sigma^2(\theta)I\) 且 \(\sigma^2 = h(L)\) → 自動保守
• \(\Sigma\) 常數且 \([\Sigma^{-1}, H] = 0\) → 保守
• 一維 → 自動成立（無橫向分量）

破缺時：穩態仍為 \(p \sim \exp(-V/\tau)\)，但 \(V\) 是 Freidlin-Wentzell 準勢，需解 Hamilton-Jacobi 方程。

2D 具體例子：\(\nabla L = (\theta_1, \theta_2)\)，\(\Sigma = \text{diag}(1+\theta_2^2, 1)\)。

Detailed balance 破缺：\(\partial_{\theta_2}[\theta_1/(1+\theta_2^2)] = -2\theta_1\theta_2/(1+\theta_2^2)^2 \ne 0 = \partial_{\theta_1}[\theta_2]\)。

準勢近似：\(V \approx \theta_1^2 + \theta_2^2 - \frac{1}{2}\theta_1^2\theta_2^2 + O(|\theta|^6)\)。修正項使噪聲大的方向準勢降低。

必要條件：\(V_{\text{eff}}\) 的全局最小值落在好解集 \(G\) 中。

證明：穩態在 \(\tau \to 0\) 時集中在 \(V_{\text{eff}}\) 全局最小值上。若最小值不在 \(G\) 中 → 穩態集中在壞解 → 矛盾。

充分條件：\(V_{\text{eff}}\) 全局最小唯一在 \(G\) 中，能隙 \(\Delta > 0\)，\(\tau \ll \Delta\)。

結論：\(P(\text{好解}) \ge 1 - (K-1)\exp(-2\Delta/\tau)\)

近似充分條件：所有 \(V_{\text{eff}}\) 值 \(\le V_{\text{eff}}^{\min} + \delta\) 的極小值都近似好（\(\text{Gap} \le \varepsilon + \varepsilon'\)）。

結論：\(P(\text{Gap} \le \varepsilon + \varepsilon') \ge 1 - \gamma\)，其中 \(\gamma \sim Ke^{-2\delta/\tau}\)

η 增大：非插值域離散修正 \(V_{\text{eff}}^{(\eta)} = V_{\text{eff}} - (\eta/2)\ln\Sigma\)；插值域 \(M_\eta = \{\theta^*: h_{\max} < 2/\eta\}\) 縮小。

B 增大：\(\tau = \eta/B\) 減小 → 分佈更集中在 \(V_{\text{eff}}\) 最小值。

過參數化（d > n）：插值流形 \(M\) 上 \(\Sigma = 0\)，有效漂移 \(v_{\text{eff}} = -(\tau/2)\nabla_\parallel\ln\det\Sigma_\perp\)。

曲率（Hessian 譜）：多維泛化間隙 \(\text{tr}(H^{-1}\Sigma) = \sum_i \sigma_i^2/\lambda_i\)。

\(V_{\text{eff}}(g\cdot\theta) = V_{\text{eff}}(\theta)\) 對 \(g \in G\)（函數不變性）。

物理解權重：\(p_{\text{phys}}([\theta]) = |G/G_\theta| \cdot p(\theta)\)（軌道計數）。

穩定化子小的解（高對稱破缺）得到更大權重。效應量級 \(O(\tau)\)，\(\tau\to 0\) 時可忽略。