Online Mirror Descent 在線鏡像下降

鏡像梯度下降可以說是梯度下降的一種更廣義的形式漆枚，對比著梯度下降來總結(jié)一下在線鏡像下降算法。

1 Bregman Divergences

定義：對于在凸集 $D\subset R^n$ 上的函數(shù) $F:D\rightarrow R$ 是可微的且嚴(yán)格凸的鼓蜒，Bregman 散度定義為 $D_F:D\times D\rightarrow R_+$ ：

$D_F(x,y)=F(x)-F(y)-<\nabla F(y),x-y>$

Bregman Divergences

給出常用函數(shù)的Bregman散度：

2-范數(shù)

當(dāng) $F(x)=||x||_2^2$ 時(shí)蝗茁， $D_F (x,y)=||x-y||_2^2$

負(fù)熵函數(shù)

當(dāng) $F(x)=\sum\nolimits_{i=1}^n x_ilogx_i$ 時(shí)娜汁， $D_F(x-y)=\sum_{i=1}^n x_ilogx_i/y_i +\sum_{i=1}^n(y_i -x_i)$

如果對于集合增加限制條件，即 $D=\left\{ x:||x||_1 \land x\geq 0 \right\}$ 斧抱，可以理解為 $x,y$ 概率單純形或概率測度：滿足 $\sum\nolimits_{i=1}^nx_i= \sum\nolimits_{i=1}^ny_i=1$ 時(shí)常拓，負(fù)熵函數(shù)的Bregman Divergences為 $D_F(x-y)=\sum_{i=1}^n x_ilogx_i/y_i =D(x||y)$ 。

常用函數(shù)的Bregamn Divergences（I. Dhillon & J. Tropp, 2007）

2 Projected Gradient Descent

對于優(yōu)化問題

$\min_{x\in S\subset R^d} f(x)$

投影梯度下降的基本思想是：先沿著下降方向走一步辉浦，然后在判斷是否在可行域內(nèi)

$y^{k+1}=x^k-\alpha_k \nabla f(x^k)$ ? ?（下降）

$x^{k+1} =arg\min_{x\in S} ||x-y^{k+1}||_2^2$ ? ?（投影）

投影保證了每次產(chǎn)生的 $x^{k+1}$ 在可行域內(nèi)弄抬，且向凸集 $S$ 的投影是唯一的。

投影梯度下降算法的迭代格式如下：

$x^{t+1}=arg\min_{x\in S} \left\{ f(x^t)+<\nabla f(x^t),x-x^t>+\frac{1}{2\eta _t } ||x-x^t ||_2^2 \right\}$

等價(jià)于? $x^{t+1}=arg\min_{x\in S} \left\{ ||x-(x^t-\eta_t\nabla f(x^t)) ||_2^2 \right\}$

3 Online Mirror Descent

定義： $f:S\rightarrow R^d$ 上的凸函數(shù)宪郊， $\left\{ v_0,v_1, ...,v_n\right\}$ 滿足 $v_t\in \partial f(x_t)$ 掂恕，初始化 $x_0=arg\min_{x\in S} \varphi (x)$ ，則對于給定的 $x_t$ 弛槐，

$x_{t+1}=arg\min_{x\in S} D_\varphi (x,x_t)+\eta <v_t,x>$

將投影梯度下降算法迭代公式中的后面Proximity項(xiàng)換成Bregman Divergences就得到鏡像下降算法：

$x^{t+1}=arg\min_{x\in S} \left\{ f(x^t)+<\nabla f(x^t),x-x^t>+\frac{1}{2\eta _t } D_\varphi (x-x^t) \right\}$

等價(jià)于 $x^{t+1}=arg\min_{x\in S} \left\{ D_\varphi (x,x^t-\eta_t\nabla f(x^t)) \right\}$

特殊的懊亡，對于線性函數(shù) $f_t(w)=<w,z_t>$ ，通過Follow-the-Rgularization-Leader預(yù)測下一步：

$x_{t+1}=arg\min_{x\in S} R(x)+\sum_{i=1}^t <x,z_t> \\=arg\min_{x\in S} R(x)+\\=arg\min_{x\in S}-R(x)$

令 $g(\theta)=arg\max_{x\in S} <x,\theta>-R(x)$

于是對于線性函數(shù)的在線鏡像下降算法為：

對于線性函數(shù)的OMD算法（Shai Shalev 2011）

（1）當(dāng)正則項(xiàng) $R(x)=\frac{1}{2\eta}||x||^2_2$ 時(shí)乎串， $g(\theta)=arg\min_{x\in S} ||x-\eta \theta||_2= \eta \theta$

（2）當(dāng)正則項(xiàng) $R(x)=\frac{1}{\eta}\sum\nolimits_{i}x_ilogx_i$ 店枣， $g_i(\theta)=\frac{e^{\eta \theta_i}}{\sum_{j} e^{\eta \theta _i}}$

（3）當(dāng)正則項(xiàng) $R(x)=\frac{1}{2\eta(q-1)}||x||_q^2$ 時(shí)， $g_i(\theta)=\eta \frac{sign(\theta_i)|\theta_i|^{p-1}}{||\theta||_p^{p-2}}$

下面給出正則項(xiàng)為負(fù)熵函數(shù)的推導(dǎo)，其余類似：

關(guān)于負(fù)熵函數(shù)的OMD推導(dǎo)

參考文獻(xiàn)：

[1] Shalev-Shwartz S. Online learning and online convex optimization[J]. Foundations and trends in Machine Learning, 2011, 4(2): 107-194.

[2]?ELE 522: Large-Scale Optimization for Data Science

[3] CSE 599S:Entropy Optimality Lecture3: Online mirror descent and Density Approximation

最后編輯于：2020.09.24 21:08:11

?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者