SGD：先說清楚衡量什麼SGD rates need a stated metric

IDL115 · CH03 · KP09 · 22/44

非凸看駐點，凸或強凸才可談相應的最優損失差。 / Stationarity and objective gaps are different metrics.

一般平滑非凸Smooth nonconvex setting

一般平滑非凸下，使用加權平均梯度平方作為駐點指標。 / Use an averaged stationarity measure.

\mathcal G_T:=\frac{\sum_{k<T}\eta_k\mathbb E\|\nabla f(w_k)\|^2}{\sum_{k<T}\eta_k}

代入排程得下列量級；非凸時應讀為駐點指標。 / These orders can describe stationarity.

\begin{aligned}\eta_k\propto1/(k+1)&:\ O(1/\log T)\\\eta_k\propto1/\sqrt{k+1}&:\ O(\log T/\sqrt T)\\\eta_k=\eta&:\ O(1/(\eta T)+\eta)\end{aligned}

在對應條件、排程及輸出選擇下可取得 O(1/T) 最優值差。 / Suitable strong-convexity results improve the rate.

\eta_k\propto1/(\mu(k+1)):\ O(1/T)\quad\text{(35)}