20211112 第90篇

arxiv。org/pdf/2111。06328。pdf

作者：Zaiwei Chen， Shancong Mou， Siva Theja Maguluri

Affiliation： Georgia Institute of Technology

本文屬於最佳化方向。我們知道，在大規模最佳化問題和一眾機器學習任務中，我們最常用到的最佳化演算法就是SGD，如果從一個大類來看，這樣的方法屬於 stochastic approximation （SA），它具備如下的一般形式：

X_{k+1}^{\alpha}=X_k^{\alpha} + \alpha (F(X_k^{\alpha})+\omega_k)

其中，

\omega_k

是 noise（即stochastic的部分），在沒有噪聲的情況下，我們透過不停地迭代，最終希望找到一個滿足

F(x)=0

的點。由於本文研究的是常數步長條件下的SGD，所以在這一設定下

F(x)=-c\nabla f(x)

，這篇文章研究的是SGD型別演算法在收斂的過程中的 trajectory，假設最終演算法收斂到

x^*

，那麼作者們希望描述的是

(X_k^{\alpha}-x^*)/g(\alpha)

在

k

趨於無窮時的分佈，從而可以對這一演算法（或者說dynamics）的極限分佈有一個清晰的認識，這裡我們需要一個 scaler

g(\alpha)

，因為它可能與 noise level 有關。於是，作者們希望能有一個合適的 scaler function

g(\alpha)

，從而建立一個 centered scaled iterate

Y_k^{\alpha}:=(X_k^{\alpha}-x^*)/g(\alpha)

到一個與

k

無關的隨機變數

Y^{\alpha}

的弱收斂，進一步，我們讓步長

\alpha\rightarrow 0

，再建立一個

Y^{\alpha}

向

Y

的弱收斂。清晰起見，我引用一張文章裡的原圖。

【簡讀】Stationary Behavior of Constant Stepsize SGD-type Algorithms: An Asymptotic Characterization

圖片摘自原文

本文的貢獻就在於實現瞭如上圖所示的兩步收斂。

（1） 作者們提出了一套新的框架，可以在下面的三種情形下確定隨機變數

Y

所對應的分佈。

SGD， 目標函式光滑並且強凸 （strongly convex）

Linear stochastic approximation with Hurwitz matrix

Stochastic Approximation solving a contractive operator（壓縮對映）

最終的隨便變數

Y

是一個均值為0的 Gaussian distribution，其 covariance matrix 滿足一個特定的 Lyapunov equation。其中，scaler function

g(\alpha)=\sqrt{\alpha}

。

（2） 對於更一般的 stochastic approximation 框架，作者們發現 scaler function 並不一定是

g(\alpha)=\sqrt{\alpha}

而且極限分佈也並不一定符合高斯分佈。作者們提出了 scaler function 所需要滿足的必要條件：

\lim_{\alpha\rightarrow 0} \frac{\alpha}{g(\alpha)}=0

並且

\lim_{\alpha\rightarrow 0} \frac{g(\alpha)F(yg(\alpha)+x^*)}{\alpha}

不恆為0或恆為無窮。這相當於給了我們的 scaler function 一個上限和下限。