Soptq

Soptq

Probably a full-stack, mainly focusing on Distributed System / Consensus / Privacy-preserving Tech etc. Decentralization is a trend, privacy must be protected.
twitter
github
bilibili
主页归档

如何计算深度学习优化方法的收敛率

#deep-learning58
AI 翻译
这篇文章通过AI由英语翻译成中文。查看原文
AI 生成的摘要
这段文字讲述了深度学习中的收敛率和优化算法中的Lipschitz连续性的概念。Lipschitz连续性表示函数变化受到一定限制，对于优化算法的收敛性和效率非常重要。作者还讨论了梯度的Lipschitz连续性和强凸性的数学表达式，并介绍了随机梯度下降（SGD）的收敛率计算。

收敛率是什么？#

我们小学三年级学的数值分析告诉我们，如果函数 f(x)f(x) 是收敛的，即 lim⁡k→∞∣∣xk−x∗∣∣=0\lim_{k \rightarrow\infty}\vert\vert x_k - x^* \vert\vert = 0 ，其中 lim⁡k→∞f(xk)=x∗\lim_{k \rightarrow\infty}f(x_k) = x^*，那么有：

lim⁡k→∞∣∣xk+1−x∗∣∣∣∣xk−x∗∣∣=a\lim_{k \rightarrow\infty} \frac{\vert\vert x_{k+1} - x^*\vert\vert}{\vert\vert x_k-x^*\vert\vert} = a

其中， aa 就是 f(x)f(x) 的收敛率。

基本理论#

SGD 基础#

在深度学习的问题当中，我们一般是去解决这样的问题：

min⁡xf(x)=∑i=1nfi(x)\min_{x}f(x) = \sum_{i=1}^{n}f_i(x)

其中，f(x)f(x) 是模型， ii 是每一个样本， xx 是我们要优化的参数， nn 是所有的样本。

然后在利用 SGD 对模型进行更新的时候，一般是这样更新的：

xt+1=xt−μ∇fixtx_{t+1} = x_{t} - \mu \nabla f_i{x_t}

这个应该大家都可以理解吧，就是一个梯度更新公式。

LL-Lipschitz 和 μ\mu-Strongly Convex#

在深度学习领域，我们看 10,000 篇跟优化沾边的论文，9,900 篇都要在证明前加一句：

... Let ff be LL-smooth and μ\mu-strongly convex …

一切都是那么的理所当然，就只有一个问题 —— ** 这两个东西到底是什么呢？** 还有很多辣鸡养成了看到这两个词就跳过这段文字的条件反射（比如我）。是时候来直面恐惧了！

μ\mu-Strongly Convex#

首先，μ\mu-Strongly Convex 表示的是函数 f(x)f(x) 是强凸的，数学表达为：

f(x2)≥f(x1)+∇f(x1)T(x2−x1)+μ2∣∣x2−x1∣∣2f(x_2) \ge f(x_1) + \nabla f(x_1)^{T}(x_2 - x_1) + \frac{\mu}{2}\vert\vert x_2 - x_1 \vert\vert ^2

其中 x1,x2∈Qx_1, x_2 \in Q，QQ 是 f(x)f(x) 的定义域，我们知道，一个凸函数的定义如下：

f(x2)≥f(x1)+∇f(x1)T(x2−x1)f(x_2) \ge f(x_1) + \nabla f(x_1)^{T}(x_2 - x_1)

这个式子的直观表示就是对于任意 x1x_1 在 f(x)f(x) 上的切线 f′(x1)f^{'}(x_1) ，有 f(x)≤f′(x1)f(x) \le f^{'}(x_1)。

而我们的强凸的数学表达式其实比凸多了一个二项式 μ2∣∣x2−x1∣∣2\frac{\mu}{2}\vert\vert x_2 - x_1 \vert\vert ^2。因为在凸函数中，我们只限定了函数必须在切线以上，但没有说以上多少。也就是说函数可以无限贴近切线，使得这样的函数在优化中不可行。所以我们相当于给凸「度」限定了下界，使得优化可以被量化。

详细证明的话可以参看这片文章。

LL-Lipschitz#

对于 LL-Lipschitz，有一篇知乎专栏我觉得讲的很好，大家有时间可以去看一下。没有时间的话我在下面也会把我的理解大概说一下。

Lipschitz Continus 是说，如果对于函数 f(x)f(x) 来说，就是指对于所有的 x1,x2∈Qx_1, x_2 \in Q，QQ 是 f(x)f(x) 的定义域，满足条件

∣∣f(x1)−f(x2)∣∣≤L∣∣x1−x2∣∣\vert\vert f(x_1) - f(x_2)\vert\vert \le L\vert\vert x_1-x_2 \vert\vert

非常直观的，上面这个公式表达的意思就是 ∣∣f′(x)∣∣≤L\vert\vert f^{'}(x) \vert\vert \le L ，所以 f(x)f(x) 的函数取值是被限定到一个范围内的。

除了 Lipschitz Continus 以外，还有 Lipschitz Continus Gradient 和 Lipschitz Continus Hessian。 Lipschitz Continus Gradient 是对于函数 f(x)f(x) 的梯度 / 导数来说的。换句话说，如果 f′(x)f^{'}(x) 满足 Lipschitz Continus，则 f(x)f(x) 满足 Lipschitz Continus Gradient。 Lipschitz Continus Hessian 同理，若 f′′(x)f^{''}(x) 满足 Lipschitz Continus，则 f(x)f(x) 满足 Lipschitz Continus Hessian。

我们在深度学习中常用的是 Lipschitz Continus Gradient (LL-Smooth)。所以我们主要要理解它的数学表达：

∣f(x2)−f(x1)−⟨f′(x2),x2−x1⟩≤L2∣∣x2−x1∣∣2 \vert f(x_2) - f(x_1) - \langle f^{'}(x_2), x_2-x_1 \rangle \le \frac{L}{2}\vert\vert x_2-x_1 \vert\vert ^2

直观上理解它和我们理解强凸非常相似，即我们对 f(x)f(x) 的变化趋势做了一个限制。我们把绝对值打开这个限制会体现得更清楚一点：

{f(x2)≤f(x1)+⟨f′(x2),x2−x1⟩+L2∣∣x2−x1∣∣2f(x2)≥f(x1)+⟨f′(x2),x2−x1⟩+L2∣∣x2−x1∣∣2\left\{\begin{array}{lr} f(x_2) \le f(x_1) + \langle f^{'}(x_2), x_2-x_1 \rangle + \frac{L}{2}\vert\vert x_2-x_1 \vert\vert ^2&\\f(x_2) \ge f(x_1) + \langle f^{'}(x_2), x_2-x_1 \rangle + \frac{L}{2}\vert\vert x_2-x_1 \vert\vert ^2&\end{array}\right.

详细证明可以参看这篇文章。

SGD 的收敛率#

那我们来小试牛刀，计算一下 SGD 的收敛率吧。

首先 LL-Smooth 的条件先摆出来：

f(xt+σ)≤f(xt)+∇f(xt)Tσ+L2∣∣σ∣∣2f(x_{t}+\sigma) \le f(x_{t}) + \nabla f(x_{t})^{T}\sigma + \frac{L}{2}\vert\vert\sigma\vert\vert ^2

其中 σ=xt+1−xt=−μ∇fixt\sigma = x_{t+1} - x_{t} = - \mu \nabla f_i{x_t} 。我们把 σ\sigma 带入上式有：

f(xt+σ)=f(xt−μ∇fixt)=f(xt+1)≤f(xt)−μ∇f(xt)T∇fi(xt)+μ2L2∣∣∇fi(xt)∣∣2\begin{aligned}f(x_t + \sigma) &= f(x_t - \mu \nabla f_i{x_t}) \\ &= f(x_{t+1})\\&\le f(x_{t}) - \mu \nabla f(x_t)^{T} \nabla f_{i}(x_t) + \frac{\mu ^2 L}{2} \vert\vert \nabla f_{i}(x_{t}) \vert\vert ^2\end{aligned}

然后我们对上式两边 ii 取期望有：

Ei(f(xt+1))≤f(xt)−μ∇f(xt)TEi(∇fi(xt))+μ2L2Ei∣∣∇fi(xt)∣∣2\mathbb{E}_{i}(f(x_{t+1})) \le f(x_{t}) - \mu \nabla f(x_t)^{T} \mathbb{E}_{i}(\nabla f_{i}(x_t)) + \frac{\mu ^2 L}{2} \mathbb{E}_{i}\vert\vert \nabla f_{i}(x_{t}) \vert\vert ^2

可以看到我们有四个期望，第一个和第二个期望我们暂时不动，第三个期望 Ei(∇fi(xt))\mathbb{E}_{i}(\nabla f_{i}(x_t)) 有：

Ei(∇fi(xt))=1n∑i=1n∇fi(xt)=∇f(xi)\begin{aligned}\mathbb{E}_{i}(\nabla f_{i}(x_t)) &= \frac{1}{n}\sum_{i=1}^{n}\nabla f_i(x_t) \\ &= \nabla f(x_i)\end{aligned}

第四项期望 Ei∣∣∇fi(xt)∣∣2\mathbb{E}_{i}\vert\vert \nabla f_{i}(x_{t}) \vert\vert ^2 稍微复杂一点，我们要通过定义方差来求。

我们假设梯度的方差 Var=1n∑i=1n∣∣∇fi(xt)−∇f(xt)∣∣2Var = \frac{1}{n}\sum_{i=1}^{n}\vert\vert\nabla f_i(x_t) - \nabla f(x_t) \vert\vert ^2，我们把这个方差展开有：

Var=1n∑i=1n∣∣∇fi(xt)−∇f(xt)∣∣2=1n[∑i=1n∣∣∇fi(xt)∣∣2]+1n[∑i=1n∣∣∇f(xt)∣∣2]−2n[∑i=1n⟨∇fi(xt),∇f(xt)⟩]=∣∣∇f(xt)∣∣2+1n[∑i=1n∣∣∇f(xt)∣∣2]−2∣∣∇f(xt)∣∣2=1n∑i=1n∣∣∇f(xt)∣∣2−∣∣∇f(xt)∣∣2\begin{aligned}Var &= \frac{1}{n}\sum_{i=1}^{n}\vert\vert\nabla f_i(x_t) - \nabla f(x_t) \vert\vert ^2 \\ &= \frac{1}{n}[\sum_{i=1}^{n}\vert\vert \nabla f_i(x_t)\vert\vert ^2] + \frac{1}{n}[\sum_{i=1}^{n}\vert\vert\nabla f(x_t)\vert\vert ^2] - \frac{2}{n}[\sum_{i=1}^n\langle\nabla f_i(x_t), \nabla f(x_t)\rangle] \\ &=\vert\vert \nabla f(x_t)\vert\vert ^2 + \frac{1}{n}[\sum_{i=1}^{n}\vert\vert\nabla f(x_t)\vert\vert ^2] - 2\vert\vert \nabla f(x_t)\vert\vert ^2 \\ &= \frac{1}{n}\sum_{i=1}^{n}\vert\vert\nabla f(x_t)\vert\vert ^2 - \vert\vert \nabla f(x_t)\vert\vert ^2\end{aligned}

所以对于 Ei∣∣∇fi(xt)∣∣2\mathbb{E}_{i}\vert\vert \nabla f_{i}(x_{t}) \vert\vert ^2 有：

Ei∣∣∇fi(xt)∣∣2=1n∑i=1n∣∣∇fi(xt)∣∣2=Var+∣∣∇f(xt)∣∣2\mathbb{E}_{i}\vert\vert \nabla f_{i}(x_{t}) \vert\vert ^2 = \frac{1}{n}\sum_{i=1}^{n}\vert\vert\nabla f_{i}(x_{t})\vert\vert ^2 = Var + \vert\vert \nabla f(x_t)\vert\vert ^2

于是，我们把上面算出的两个单项期望带入整体有：

E(f(xt+1))≤E(f(xt))−μ∇f(xt)T∇f(xi)+μ2L2(Var+∣∣∇f(xt)∣∣2)=E(f(xt))−(μ−μ2L2)∣∣∇f(xt)∣∣2+μ2L2Var\begin{aligned}\mathbb{E}(f(x_{t+1})) &\le \mathbb{E}(f(x_{t})) - \mu \nabla f(x_t)^{T} \nabla f(x_i) + \frac{\mu ^2 L}{2}(Var + \vert\vert \nabla f(x_t)\vert\vert ^2)\\&=\mathbb{E}(f(x_t))-(\mu-\frac{\mu^2L}{2})\vert\vert \nabla f(x_t)\vert\vert ^2 + \frac{\mu^2L}{2}Var\end{aligned}

接下来，我们还有 λ\lambda-Strong Convex （这里用 λ\lambda 是为了避免和例子中学习率搞混） 的数学表达如下：

f(x)≥f(x0)+∇f(x0)T(x−x0)+λ2∣∣x−x0∣∣2f(x) \ge f(x_0) + \nabla f(x_0)^T (x-x_0) + \frac{\lambda}{2}\vert\vert x - x_0 \vert\vert ^2

我们令 x=x∗,x0=xx = x^*, x_0 = x 有，把加减组合成一个和的平方有：

f(x∗)≥f(x)+∇f(x)T(x∗−x)+λ2∣∣x∗−x∣∣2=f(x)+12λ∣∣∇f(x)+λ(x∗−x)∣∣2−12λ∣∣∇f(x)∣∣2≥f(x)−12λ∣∣∇f(x)∣∣2\begin{aligned}f(x^*) &\ge f(x) + \nabla f(x)^T (x^*-x) + \frac{\lambda}{2}\vert\vert x^* - x \vert\vert ^2\\ &=f(x) + \frac{1}{2\lambda}\vert\vert\nabla f(x) + \lambda (x^*-x)\vert\vert ^2 - \frac{1}{2\lambda}\vert\vert\nabla f(x)\vert\vert ^2\\ &\ge f(x) - \frac{1}{2\lambda}\vert\vert\nabla f(x)\vert\vert ^2\end{aligned}

所以有：

∣∣∇f(x)∣∣2≥2λ(f(x)−f(x∗))\vert\vert\nabla f(x)\vert\vert ^2 \ge 2\lambda (f(x) - f(x^*))

我们把上式带入期望的不等式有：

E(f(xt+1))≤E(f(xt))−2λ(μ−μ2L2)(f(xt)−f(x∗))+μ2L2Var\mathbb{E}(f(x_{t+1})) \le \mathbb{E}(f(x_t))-2\lambda(\mu-\frac{\mu^2L}{2})(f(x_t) - f(x^*)) + \frac{\mu^2L}{2}Var

最后，令 μ=1L\mu = \frac{1}{L}，有：

E[f(xt+1)−f(x∗)f(xt)−f(x∗)]=(1−σL)+H\mathbb{E}[\frac{f(x_{t+1}) - f(x^*)}{f(x_{t}) - f(x^*)}] = (1-\frac{\sigma}{L}) + H

其中 HH 是 SGD 相对于 GD 带来的干扰。

加载中...
此文章数据所有权由区块链加密技术和智能合约保障仅归创作者所有。