Momentum and NAG

文章目录

Momentum

Momentum的迭代公式为:
vt=γvt1+ηθJ(θ)θ=θvt v_t = \gamma v_{t-1} + \eta \nabla_\theta J(\theta) \\ \theta=\theta-v_t vt​=γvt−1​+η∇θ​J(θ)θ=θ−vt​
其中J()J(\cdot)J(⋅)一般为损失函数。我们知道,一般的梯度下降,是没有γvt1\gamma v_{t-1}γvt−1​这一项的,有了这一项之后,θ\thetaθ的更新和前一次更新的路径有关,使得每一次更新的方向不会出现剧烈变化,所以这种方法在函数分布呈梭子状的时候非常有效。
Momentum and NAG
先来看看这个函数利用梯度下降的效果吧。

import matplotlib.pyplot as plt
import numpy as np


"""
z = x^2 + 50 y ^2
2x
100y
"""

partial_x = lambda x: 2 * x
partial_y = lambda y: 100 * y
partial = lambda x: np.array([partial_x(x[0]),
                              partial_y(x[1])])
f = lambda x: x[0] ** 2 + 50 * x[1] ** 2




class Decent:
    def __init__(self, function):
        self.__function = function

    @property
    def function(self):
        return self.__function

    def __call__(self, x, grad, alpha=0.4, beta=0.7):
        t = 1
        fx = self.function(x)
        dist = - grad @ grad
        while True:
            dx = x - t * grad
            fdx = self.function(dx)
            if fdx <= fx + alpha * t * dist:
                break
            else:
                t *= beta
        return dx


grad_decent = Decent(f)

x = np.array([30., 15.])
process = []
while True:
    grad = partial(x)
    if np.sqrt(grad @ grad) < 1e-7:
        break
    else:
        process.append(x)
        x = grad_decent(x, grad)

process = np.array(process)
print(len(process))
x = np.linspace(-40, 40, 1000)
y = np.linspace(-20, 20, 500)
fig, ax= plt.subplots()
X, Y = np.meshgrid(x, y)
ax.contour(X, Y, f([X, Y]), colors='black')
ax.plot(process[:, 0], process[:, 1])
plt.show()

Momentum and NAG
怎么说呢,有点震荡?289步1e-7的误差


x = np.array([30., 15.])
process = []
v = 0
gamma = 0.7
eta = 0.016
while True:
    grad = partial(x)
    v = gamma * v + eta * grad
    if np.sqrt(grad @ grad) < 1e-7:
        break
    else:
        process.append(x)
        x = x - v

Momentum and NAG
用117步,话说,这个参数是不是难调啊,感觉一般η\etaη很小啊。

还有一个很赞的分析,在博客:
路遥知马力-Momentum
Momentum and NAG

Nesterov accelerated gradient

比Momentum更快:揭开Nesterov Accelerated Gradient的真面目

NGD的迭代公式是:
vt=γvt1+ηθJ(θγvt1)θ=θvt v_t = \gamma v_{t-1} + \eta \nabla_\theta J(\theta - \gamma v_{t-1}) \\ \theta = \theta-v_t vt​=γvt−1​+η∇θ​J(θ−γvt−1​)θ=θ−vt​
和上面的区别就是,第ttt步更新,我们关心的是下一步(一个近似)的梯度,而不是当前点的梯度,我之前以为这是有一个搜索的过程的,但是实际上没有,所以真的是这个式子具有前瞻性?或许真的和上面博客里说的那样,因为后面的部分可以看成一个二阶导的近似。

x = np.array([30., 15.])
process = []
v = 0
gamma = 0.7
eta = 0.013
while True:
    grad = partial(x-gamma*v)
    v = gamma * v + eta * grad
    if np.sqrt(grad @ grad) < 1e-7:
        break
    else:
        process.append(x)
        x = x - v

Momentum and NAG

感觉没有momentum好用啊

NESTEROV 的另外一个方法?

在那个overview里面,引用的是

文献链接

但是里面的方面感觉不是NGD啊,不过的确是一种下降方法,所以讲一下吧。

假设f(x)f(x)f(x)满足其一阶导函数一致连续的凸函数,比如用以下条件表示:
f(x)f(y)Lxy,x,yE \|f&#x27;(x)-f&#x27;(y)\| \le L\|x-y\|, \forall x, y \in E ∥f′(x)−f′(y)∥≤L∥x−y∥,∀x,y∈E
由此可以推得(不晓得这个0.5哪来的,虽然有点像二阶泰勒展式,但是呢,凸函数好像没有这性质吧,去掉0.5就可以直接证出来了,而且这个0.5对证明没有什么大的影响吧,因为只要让L=0.5L就可以了啊):
f(y)f(x)+&lt;f(x),yx&gt;+0.5Lyx2(2) f(y) \le f(x) + &lt;f&#x27;(x), y-x&gt;+0.5L\|y-x\|^2 \quad (2) f(y)≤f(x)+<f′(x),y−x>+0.5L∥y−x∥2(2)

为了解决min{f(x)xE}\min \{f(x)|x\in E\}min{f(x)∣x∈E},且最优解XX^*X∗非空的情况,我们可以:

  1. 首先选择一个点y0Ey_0 \in Ey0​∈E,并令
    k=0,a0=1,x1=y0,α1=y0z/f(y0)f(z) k=0, a_0=1, x_{-1}=y_0, \alpha_{-1}=\|y_0-z\|/\|f&#x27;(y_0)-f&#x27;(z)\| k=0,a0​=1,x−1​=y0​,α−1​=∥y0​−z∥/∥f′(y0​)−f′(z)∥
    其中zzz是E中不同于y0y_0y0​的任意点,且f(y0)f(z)f&#x27;(y_0) \ne f&#x27;(z)f′(y0​)̸​=f′(z)
  2. 第k 步:
    a) 计算最小的iii满足:
    f(yk)f(yk2iαk1f(yk))2i1αk1f(yk)2(4) f(y_k)-f(y_k-2^{-i}\alpha_{k-1}f&#x27;(y_k))\ge2^{-i-1} \alpha_{k-1} \|f&#x27;(y_k)\|^2 \quad (4) f(yk​)−f(yk​−2−iαk−1​f′(yk​))≥2−i−1αk−1​∥f′(yk​)∥2(4)
    b) 令
    αk=2iαk1,xk=ykαkf(yk)ak+1=(1+4ak2+1)/2yk+1=xk+(ak1)(xkxk1)/ak+1. \alpha_k = 2^{-i}\alpha_{k-1}, x_k = y_k - \alpha_k f&#x27;(y_k) \\ a_{k+1} = (1+ \sqrt{4a_k^2 + 1})/2 \\ y_{k+1} = x_k + (a_k - 1)(x_k - x_{k-1}) / a_{k+1} . αk​=2−iαk−1​,xk​=yk​−αk​f′(yk​)ak+1​=(1+4ak2​+1​)/2yk+1​=xk​+(ak​−1)(xk​−xk−1​)/ak+1​.

作者证明了这个方法的收敛率是O(1/k2)O(1/k^2)O(1/k2)的。
即在满足上面提到的假设,且利用上面给出的方法所求,可以证明,对于任意的k0k\ge 0k≥0:
f(xk)fC/(k+2)2 f(x_k) - f^* \le C / (k+2)^2 f(xk​)−f∗≤C/(k+2)2
其中C=4Ly0x2C = 4L\|y_0 - x^*\|^2C=4L∥y0​−x∗∥2并且f=f(x),xXf^*=f(x^*), x^* \in X^*f∗=f(x∗),x∗∈X∗。
还有一些关于收敛步长的分析就不贴了。

证明:

yk(α)αf(yk)y_k(\alpha) - \alpha f&#x27;(y_k)yk​(α)−αf′(yk​), 可以得到(通过(2)):
f(yk)f(yk(α))0.5α(2αL)f(yk)2 f(y_k) - f(y_k (\alpha)) \ge 0.5 \alpha (2 - \alpha L) \|f&#x27;(y_k)\|^2 f(yk​)−f(yk​(α))≥0.5α(2−αL)∥f′(yk​)∥2
结果就是, 只要2iαk1L12^{-i} \alpha_{k-1} \le L^{-1}2−iαk−1​≤L−1,不等式(4)就成立,也就是说αk0.5L1k0\alpha_k \ge 0.5L^{-1}, \forall k \ge 0αk​≥0.5L−1,∀k≥0, 否则2iαk1&gt;L12^{-i} \alpha_{k-1} &gt; L^{-1}2−iαk−1​>L−1。
pl=(ak1)(xk1xk)p_l = (a_k-1)(x_{k-1}-x_k)pl​=(ak​−1)(xk−1​−xk​),则yk+1=xkpk/ak+1y_{k+1}=x_k - p_k / a_{k+1}yk+1​=xk​−pk​/ak+1​,于是:
pk+1xk+1=pkxk+ak+1αk+1f(yk+1) p_{k+1} - x_{k+1} = p_k - x_k + a_{k+1} \alpha_{k+1} f&#x27;(y_{k+1}) pk+1​−xk+1​=pk​−xk​+ak+1​αk+1​f′(yk+1​)
于是:
pk+1xk+1+x2=pkxk+x2+2(ak+11)αk+1&lt;f(yk+1,pk&gt;+2ak+1αk+1&lt;f(yk+1,xyk+1&gt;+ak+12αk+12f(yk+1)2 \begin{array}{ll} \|p_{k+1}-x_{k+1}+x^*\|^2 &amp;= \|p_k - x_k + x^*\|^2 + 2(a_{k+1}-1)\alpha_{k+1} &lt;f&#x27;(y_{k+1}, p_k&gt; \\ &amp; + 2a_{k+1} \alpha_{k+1} &lt;f&#x27;(y_{k+1}, x^* - y_{k+1}&gt; + a_{k+1}^2 \alpha_{k+1}^2 \|f&#x27;(y_{k+1})\|^2 \end{array} ∥pk+1​−xk+1​+x∗∥2​=∥pk​−xk​+x∗∥2+2(ak+1​−1)αk+1​<f′(yk+1​,pk​>+2ak+1​αk+1​<f′(yk+1​,x∗−yk+1​>+ak+12​αk+12​∥f′(yk+1​)∥2​
利用不等式(4)和f(x)f(x)f(x)的凸性,可得:
&lt;f(yk+1),yk+1x&gt;f(xk+1)f+0.5αk+1f(yk+1)2(5)0.5αk+1f(yk+1)2f(yk+1)f(xk+1)f(xk)f(xk+1)ak+11&lt;f(yk+1,pk&gt;(6) \begin{array}{ll} &lt;f&#x27;(y_{k+1}), y_{k+1} - x^*&gt; &amp;\ge f(x_{k+1}) - f^* + 0.5 \alpha_{k+1} \|f&#x27;(y_{k+1})\|^2 (5)\\ 0.5 \alpha_{k+1} \|f&#x27;(y_{k+1})\|^2 &amp;\le f(y_{k+1}) - f(x_{k+1}) \le f(x_k) - f(x_{k+1}) \\ &amp; \quad -a_{k+1}^{-1} &lt;f&#x27;(y_{k+1}, p_k&gt; (6) \end{array} <f′(yk+1​),yk+1​−x∗>0.5αk+1​∥f′(yk+1​)∥2​≥f(xk+1​)−f∗+0.5αk+1​∥f′(yk+1​)∥2(5)≤f(yk+1​)−f(xk+1​)≤f(xk​)−f(xk+1​)−ak+1−1​<f′(yk+1​,pk​>(6)​
其中第一个不等式,先利用凸函数得性质:
ff(yk+1)+&lt;f(yk+1),xyk+1) f^* \ge f(y_{k+1}) + &lt;f&#x27;(y_{k+1}), x^*-y_{k+1}) f∗≥f(yk+1​)+<f′(yk+1​),x∗−yk+1​)
再利用不等式(4):
f(yk+1)f(xk+1)0.5αk+1f(yk+1)2 f(y_{k+1}) - f(x_{k+1}) \ge 0.5 \alpha_{k+1}\|f&#x27;(y_{k+1})\|^2 f(yk+1​)−f(xk+1​)≥0.5αk+1​∥f′(yk+1​)∥2
代入这俩个不等式可得:
pk+1xk+1+x2pkxk+x22(ak+11)αk+1&lt;f(yk+1),pk&gt;2ak+1αk+1(f(xk+1f)+(ak+12ak+1)αk+12f(yk+1)22ak+1αk+1(f(xk+1)f)+2(ak+12ak+1)αk+1(f(xk)f(xk+1))=2αk+1ak2(f(xk)f)2αk+1ak+12(f(xk+1f)2αkak2(f(xk)f)2αk+1ak+12(f(xk+1)f) \begin{array}{ll} &amp; \|p_{k+1} - x_{k+1}+x^*\|^2 - \|p_k - x_k + x^*\|^2 \le 2(a_{k+1}-1)\alpha_{k+1}&lt;f&#x27;(y_{k+1}), p_k&gt; \\ &amp; \quad -2a_{k+1}\alpha_{k+1} (f(x_{k+1} - f^*) + (a_{k+1}^2 - a_{k+1})\alpha_{k+1}^2 \|f&#x27;(y_{k+1})\|^2 \\ &amp; \quad \le -2a_{k+1} \alpha_{k+1} (f (x_{k+1}) - f^*) + 2(a_{k+1}^2 - a_{k+1}) \alpha_{k+1}(f(x_k)-f(x_{k+1})) \\ &amp; \quad = 2\alpha_{k+1} a_k^2 (f(x_k)-f^*) - 2\alpha_{k+1} a_{k+1}^2 (f(x_{k+1}) - f^*) \\ &amp; \quad \le 2\alpha_k a_k^2 (f(x_k)-f^*) - 2\alpha_{k+1} a_{k+1}^2 (f(x_{k+1}) -f^*) \end{array} ​∥pk+1​−xk+1​+x∗∥2−∥pk​−xk​+x∗∥2≤2(ak+1​−1)αk+1​<f′(yk+1​),pk​>−2ak+1​αk+1​(f(xk+1​−f∗)+(ak+12​−ak+1​)αk+12​∥f′(yk+1​)∥2≤−2ak+1​αk+1​(f(xk+1​)−f∗)+2(ak+12​−ak+1​)αk+1​(f(xk​)−f(xk+1​))=2αk+1​ak2​(f(xk​)−f∗)−2αk+1​ak+12​(f(xk+1​)−f∗)≤2αk​ak2​(f(xk​)−f∗)−2αk+1​ak+12​(f(xk+1​)−f∗)​
其中第一个不等式用到了(5), 第二个不等式用到了(6), 等式用到了ak+12ak+1=ak2a_{k+1}^2-a_{k+1}=a_k^2ak+12​−ak+1​=ak2​,最后一步用到了αkαk+1\alpha_k \le \alpha_{k+1}αk​≤αk+1​且f(xk)ff(x_k) \ge f^*f(xk​)≥f∗。

因此:
2αk+1ak+12(f(xk+1)f)2αk+1ak+12(f(xk+1)f)+pk+1xk+1+x22αkak(f(xk)f)+pkxk+x22α0a02(f(x0)f)+p0x0+x2y0x2. \begin{array}{ll} &amp; 2\alpha_{k+1}a_{k+1}^2 ( f(x_{k+1}) - f^*) \le 2\alpha_{k+1} a_{k+1}^2 (f(x_{k+1})-f^*) + \|p_{k+1}-x_{k+1} + x^*\|^2 \\ &amp; \le 2 \alpha_k a_k (f(x_k)-f^*) + \|p_k -x_k + x^*\|^2 \\ &amp; \le 2\alpha_0 a_0^2 (f(x_0) - f^*) + \|p_0 - x_0 + x^*\|^2 \le \|y_0-x^*\|^2. \end{array} ​2αk+1​ak+12​(f(xk+1​)−f∗)≤2αk+1​ak+12​(f(xk+1​)−f∗)+∥pk+1​−xk+1​+x∗∥2≤2αk​ak​(f(xk​)−f∗)+∥pk​−xk​+x∗∥2≤2α0​a02​(f(x0​)−f∗)+∥p0​−x0​+x∗∥2≤∥y0​−x∗∥2.​
最后一个不等式成立是因为p0=0,x0=y0p_0 = 0, x_0=y_0p0​=0,x0​=y0​,左边第一项大于等于0.
αk0.5L1,ak+1ak+0.51+0.5(k+1)\alpha_k \ge 0.5L^{-1}, a_{k+1}\ge a_k + 0.5 \ge 1 + 0.5(k+1)αk​≥0.5L−1,ak+1​≥ak​+0.5≥1+0.5(k+1),所以:
f(xk+1)fC/(k+3)2 f(x_{k+1}) - f^* \le C/(k+3)^2 f(xk+1​)−f∗≤C/(k+3)2
证毕。


class Decent:
    def __init__(self, function, grad):
        self.__function = function
        self.__grad = grad
        self.process = []

    @property
    def function(self):
        return self.__function

    @property
    def grad(self):
        return self.__grad

    def __call__(self, y, z):
        def find_i(y, alpha):
            i = 0
            fy = self.function(y)
            fdy = self.grad(y)
            fdynorm = fdy @ fdy
            while True:
                temp = self.function(y - 2 ** (-i) * alpha * fdy)
                if fy - temp > 2 ** (-i -1) * alpha * fdynorm:
                    return i, fdy
                else:
                    i += 1
        a = 1
        x = y
        fdy = self.grad(y)
        fdz = self.grad(z)
        alpha = np.sqrt((y-z) @ (y-z) /
                        (fdy-fdz) @ (fdy - fdz))
        k = 0
        while True:
            k += 1
            self.process.append(x)
            i, fdy = find_i(y, alpha)
            if np.sqrt(fdy @ fdy) < 1:
                print(k)
                return x
            alpha = 2 ** (-i) * alpha
            x_old = np.array(x, dtype=float)
            x = y - alpha * fdy
            a_old = a
            a = (1 + np.sqrt(4 * a ** 2 + 1)) / 2
            y = x + (a_old - 1) * (x - x_old) / a







grad_decent = Decent(f, partial)

x = np.array([30., 15.])
z = np.array([200., 10.])
grad_decent(x, z)
process = np.array(grad_decent.process)
x = np.linspace(-40, 40, 1000)
y = np.linspace(-20, 20, 500)
X, Y = np.meshgrid(x, y)
fig, ax = plt.subplots()
ax.contour(X, Y, f([X, Y]), colors="black")
ax.scatter(process[:, 0], process[:, 1])
ax.plot(process[:, 0], process[:, 1])
plt.show()




Momentum and NAG

用了30步就能到达上面的情况,不过呢,如果想让f(x)1e7\|f&#x27;(x)\|\le 1e-7∥f′(x)∥≤1e−7得1000多步,主要是因为会来回振荡。

上一篇:苹果Mac白噪音软件:Noise Machine


下一篇:自适应波束合成