為什麼要分析收斂率

前面介紹了 SGD 與 mini-batch SGD 的實務用法，但一個關鍵問題還沒回答：它們到底能收斂多快？跟全梯度下降差在哪？ 本節用命題 2 與命題 3，把兩者的收斂率並排比較，並特別指出固定學習率下 SGD 的「停滯現象」。

命題 2：全梯度下降的收斂率

考慮凸且可微的函數 $f(\cdot)$，梯度 $L$-smooth，$f^{*}$ 為最小值、$\boldsymbol{w}^{*}$ 為最小化點。從初始點 $\boldsymbol{w}^{(0)}$ 出發，經 $t$ 次全梯度下降迭代後（式 (31)）：

$$f\left(\boldsymbol{w}^{(t+1)}\right)-f^{*} \leq \frac{2 L\left\|\boldsymbol{w}^{(0)}-\boldsymbol{w}^{*}\right\|_{2}^{2}}{t+1}=\mathcal{O}\left(\frac{1}{t}\right) .$$

重點：當 $t \rightarrow \infty$，誤差趨近 0——全梯度下降能精確收斂到最優解。

命題 3：SGD 的收斂率（取決於步長）

設 $f(\boldsymbol{w})=\sum_{i=1}^{n} f_{i}(\boldsymbol{w})$ 有下界，各 $f_i$ 可微，梯度 $L$-smooth，且對某常數 $\beta$ 有 $\mathbb{E}\left[\left\|\nabla f_{i}\left(\boldsymbol{w}_{k}\right)\right\|_{2}^{2} \mid \boldsymbol{w}_{k}\right] \leq \beta^{2}$。SGD 的收斂率取決於步長 $\eta^{(\tau)}$ 的選擇：

若各 $f_i$ 額外滿足 $\mu$-strongly convex，則：

固定步長的停滯：$\mathcal{O}(\eta)$ 鄰域

式 (34) 與 (36) 揭示了一個實務上極重要的現象。以固定步長 $\eta$ 為例，當 $t \rightarrow \infty$：

$$\lim _{t \rightarrow \infty} f\left(\boldsymbol{w}^{(t+1)}\right)-f^{*} \leq \lim _{t \rightarrow \infty} \mathcal{O}\left(\frac{1}{t}+\eta\right)=\mathcal{O}(\eta)$$

也就是說，SGD 永遠無法精確到達最優解，而是在最優點附近一個 $\mathcal{O}(\eta)$ 大小的鄰域內停滯（stagnate）。步長越大，停滯區域越大。

相比之下，全梯度下降：

$$\lim _{t \rightarrow \infty} f\left(\boldsymbol{w}^{(t+1)}\right)-f^{*} \leq \lim _{t \rightarrow \infty} \mathcal{O}\left(\frac{1}{t}\right)=0$$

能精確收斂到 $f^{*}$。

取捨：精度 vs 計算成本

SGD 雖然不如全梯度精確，但每次迭代的計算成本遠低——尤其當資料量 $n$ 非常大時，只算一個（或一小批）樣本的梯度，遠比遍歷全部 $n$ 筆快得多。這就是深度學習幾乎預設用 SGD 的根本原因。

另外，SGD 收斂時無法取得全梯度來做收斂檢查，通常改為監控單一樣本上的梯度范數，或搭配動量、線搜索等技巧改善表現。

教授祕笈：SGD 收斂分析——醉漢下山，固定步幅永遠在 η 寬的帶子裡晃

同學，這一站不是再教你「怎麼做 SGD」（那是 KP-7、KP-8），而是回答一個更狠的問題：它到底能不能走到谷底？走多快？ 主線比喻就一個——醉漢下山。全梯度下降是清醒嚮導，每次把整座山看完再走一步；SGD 是醉漢，每次只隨便踩一顆小石頭當方向。清醒嚮導能精確走到谷底；醉漢若步幅永遠固定成 $\eta$，就算到了谷底附近，每步仍跨 $\eta$ 那麼遠——永遠在一條 $\eta$ 寬的帶子裡晃，進不了真正的最低點。

先把任務講成一句人話

一句話：全梯度能精確收斂到最優；SGD 用固定步長時，長期誤差上界卡在跟 $\eta$ 一樣寬的帶子上——想更準，就得把步子變小（或讓步長遞減）。

鷹架式：先直覺，再符號

先忘掉符號。想像谷底有一個點 $f^{*}$，你現在的高度減去谷底高度，就是「還差多少」。

清醒嚮導（全梯度）每走一步，這個差距大致按 $1/t$ 縮小——走越久，差距越接近 0。醉漢（SGD）的方向帶雜訊，收斂速度取決於步幅怎麼選：步幅慢慢縮小，長期還能把差距磨向 0；步幅固定，雜訊永遠有那麼大，差距就卡在 $\mathcal{O}(\eta)$ 停不下來。這叫停滯（stagnate）。

為什麼實務還是用 SGD？因為清醒嚮導每次都要把 $n$ 筆資料全算一遍，資料一大就走不動；醉漢每次只看一筆（或一小批），單步便宜到能換很多次晃。

符號逐個拆（命題 2、命題 3，式 (31)–(36)）

命題 2 假設 $f$ 凸、可微、梯度 $L$-smooth（斜率不會突然變太陡），$f^{*}$ 是最小值、$\boldsymbol{w}^{*}$ 是最低點。從 $\boldsymbol{w}^{(0)}$ 出發，全梯度走 $t$ 步之後（式 (31)）：

$$f\left(\boldsymbol{w}^{(t+1)}\right)-f^{*} \leq \frac{2 L\left\|\boldsymbol{w}^{(0)}-\boldsymbol{w}^{*}\right\|_{2}^{2}}{t+1}=\mathcal{O}\left(\frac{1}{t}\right).$$

$t\to\infty$ 時右邊趨近 0——精確收斂。

命題 3 把 $f(\boldsymbol{w})=\sum_{i=1}^{n} f_{i}(\boldsymbol{w})$ 拆成各樣本，並假設單樣本梯度的均方有上界 $\beta^{2}$。SGD 的收斂率看步長 $\eta^{(\tau)}$：

一般凸情況：

• $\eta^{(\tau)}=1/\tau$：$\mathcal{O}(1/\log t)$（式 (32)）——能趨近 0，但慢得像在爬對數。
• $\eta^{(\tau)}=1/\sqrt{\tau}$：$\mathcal{O}(\log t/\sqrt{t})$（式 (33)）——也能趨近 0。
• $\eta^{(\tau)}=\eta$ 固定：$\mathcal{O}(1/t+\eta)$（式 (34)）——$1/t$ 會消失，留下 $\eta$ 這條帶子。

若各 $f_{i}$ 再滿足 $\mu$-strongly convex（谷底比較「尖而有彈性」，走偏會被彈回來）：

• $\eta^{(\tau)}=1/(\mu\tau)$：$\mathcal{O}(1/t)$（式 (35)）——速率追上全梯度。
• $\eta^{(\tau)}=\eta$ 固定：$\mathcal{O}\bigl((1-\mu/L)^{t}+\eta\bigr)$（式 (36)）——指數項會消失，還是留下 $\eta$。

真的算一遍：帶子有多寬

把「大 $O$ 的形狀」做成玩具數字，方便看出長期行為。全梯度用式 (31) 的形狀，取 $2L\|\boldsymbol{w}^{(0)}-\boldsymbol{w}^{*}\|_{2}^{2}=10$，所以上界是 $10/(t+1)$。SGD 固定步長用式 (34) 的形狀 $10/t+\eta$。強凸固定步長另取 $\mu/L=0.1$，所以收縮因子是 $0.9^{t}$，再加上 $\eta=0.05$。

看最後一列：清醒嚮導的上界被磨成 0；醉漢不管走多久，帶子寬度就是 $\eta$。$\eta=0.5$ 的帶子是 $\eta=0.05$ 的十倍——步子跨越大，谷底附近晃得越兇。

強凸那欄更刺眼：$t=99$ 時指數項 $0.9^{99}$ 已經小到可以忽略，後面幾乎整列都停在 $0.05$。不是還沒走完，是步幅本身不准你再靠近。

先留一個反轉

很多人會以為：「固定 $\eta$ 沒關係，多跑幾個訓練輪次就好，誤差反正是 $1/t$，時間會把它洗掉。」式 (34)、(36) 把這句話打臉——$1/t$ 或 $(1-\mu/L)^{t}$ 確實會消失，但 $\eta$ 不會消失。你把訓練從 100 步拉到 100 萬步，帶子還是那麼寬。想更準，不是加時間，是縮小 $\eta$，或改用遞減步長讓 $1/t$ 項主導、長期誤差趨近 0。

換個場景，自己找出同一條路

把「下山」換成「直升機降落」。固定油門等於只能在某個高度盤旋，盤得再久也貼不了跑道——那個高度就是 $\eta$。遞減步長 $1/\sqrt{\tau}$ 才是慢慢收油門。

自己算一題（答案先不公布）：若改用玩具上界 $20/t+\eta$，固定 $\eta=0.02$，分別看 $t=50$、$t=500$、$t\to\infty$ 時上界是多少？遞減步長那條「跑道」會不會落到 0？

大家最容易在這裡搞混

第一，「SGD 比全梯度更準」。錯。SGD 贏的是每步計算便宜，輸的是精度：固定步長永遠卡在 $\mathcal{O}(\eta)$ 鄰域。第二，「強凸就能精確到達 $f^{*}$」。錯。強凸只讓瞬態項從 $1/t$ 變成指數衰減，式 (36) 的 $+\eta$ 還在；要趨近 0，仍得讓步長遞減（例如式 (35) 的 $1/(\mu\tau)$）。

跨知識點掛勾

KP-2 的全梯度更新，這裡用命題 2 量化成 $\mathcal{O}(1/t)$。KP-7、KP-8 教你怎麼做 SGD／mini-batch，這裡告訴你「做完之後還差多遠」。KP-10 起會把「一個全局 $\eta$」拆成各維度自己的有效步長——因為你已經知道，步長選太大，帶子就太寬。

換句話重述

全梯度像清醒嚮導，誤差 $\mathcal{O}(1/t)\to 0$；SGD 像醉漢，固定步長時長期卡在 $\eta$ 寬的帶子裡晃。遞減步長才能把帶子收掉；SGD 的真正賣點是單步便宜，不是更準。

一句話收尾： 固定 $\eta$，醉漢永遠在 $\eta$ 寬的帶子裡晃；想落地，就得把步子變小。