SGD 上界：從一步下降到加總Deriving an averaged stationarity bound

IDL115 · CH03 · KP09 · 24/44

把每步的期望下降加起來，便能看出步長與噪聲的角色。 / Sum one-step expected progress.

定理前提Assumptions

f 為 L-smooth 且有下界，gₖ 無偏且條件二階矩有界。 / Assume unbiased gradients and bounded second moments.

\mathbb E[g_k\mid w_k]=\nabla f(w_k),\quad\mathbb E[\|g_k\|^2\mid w_k]\le\beta^2

將 wₖ₊₁=wₖ−ηₖgₖ 代入下降引理，再取期望。 / Apply smoothness and take expectations.

\mathbb E f(w_{k+1})\le\mathbb E f(w_k)-\eta_k\mathbb E\|\nabla f(w_k)\|^2+\tfrac L2\eta_k^2\beta^2

Gₜ 定義在前一頁；右側分成初始差與累積噪聲。 / Separate initial gap and accumulated noise.

\mathcal G_T\le\frac{2(f(w_0)-f_{\inf})+L\beta^2\sum_{k<T}\eta_k^2}{2\sum_{k<T}\eta_k}