最优化算法-5-Smoothness和Strong convexity

初吻献给了奶头 · 发表于 2024-7-15 18:34

本系列文章是对Youtube 《Optimization Algorithms》课程的学习笔记和总结
课程地址：https://www.youtube.com/playlist?list=PLXsmhnDvpjORzPelSDs0LSDrfJcqyLlZc
文章封面由DALL.E-2创作生成

这一节介绍了 \beta -smooth和 \alpha -strongly convex的两个概念，这两个概念对于后续推导优化算法的收敛速度具有重要的感化。
1 Smoothness的定义

这里介绍\beta -smooth的概念。
如果一个函数 f 被称为 \beta -smooth的，那么它的梯度是以参数 \beta 具有lipschitz持续性的
也就是说，如果 f 是\beta -smooth的，那么有： ||\nabla f(x)-\nabla f(y)||_2\leq \beta ||x-y||_2
基于上述概念，我们首先可以论证下述的命题成立：
命题1：如果 f(x) 是 \beta -smooth，那么 \frac{\beta}{2}||x||_2^2-f(x) 是凸函数。
证明：
按照西涯先生：最优化算法-2-凸集和凸函数文章里提到的凸函数的定义可知，要证明 g(x)=\frac{\beta}{2}||x||_2^2-f(x) 是凸函数，只需要证明 g(x) 的梯度是单调的，也就是证明 \langle\nabla g(x)-\nabla g(y),x-y\rangle \geq 0
由于 \nabla g(x)=\beta x -\nabla f(x) ，那么带入上述方程可得（操作了Cauchy-Schwarz不等式）：
\langle\nabla g(x)-\nabla g(y),x-y\rangle\\ =\beta\langle x-y,x-y\rangle-\langle\nabla f(x)-\nabla f(y),x-y\rangle\\ \geq \beta ||x-y||_2^2-||\nabla f(x)-\nabla f(y)||_2\cdot||x-y||_2\\ =(\beta ||x-y||_2 - ||\nabla f(x)-\nabla f(y)||_2)\cdot||x-y||_2\\ \geq 0
至此，我们证明了这个命题。
基于上述命题，可以衍生出一系列结论：
结论1：
由于g(x)=\frac{\beta}{2}||x||_2^2-f(x)是凸函数，按照凸函数的定义，其符合 g(y) \geq f(x) + \langle \nabla g(x), y-x \rangle ，进一步地，把 g(x) 代入，可以推导出如下关系：
f(y)\leq f(x) + \langle \nabla f(x), y-x\rangle + \frac{\beta}{2} ||x-y||^2_2

上述公式具有显著的几何含义，在 x 点附近的函数值 f 的上界，受到一个二次函数的约束。
这也就意味，函数 f 的上升速度是有限的，尤其是当 \beta 很小的时候，意味着函数相对斗劲平坦

结论2：
由于g(x)=\frac{\beta}{2}||x||_2^2-f(x)是凸函数，按照凸函数的定义，其符合 \nabla ^2g(x)\geq 0 ，进一步地，把 g(x) 代入，可以推导出如下关系：
如果一个函数 f 是 \beta -smooth，那么 \nabla^2 f(x) \leq \beta I 。
<hr/>2 Strongly convexity的定义

这里介绍 \alpha -strongly convex的概念。
如果一个函数 f 被称为 \alpha -strongly convex，那么： g(x) = f(x) - \frac{\alpha}{2} ||x||_2^2 是凸函数。
基于上述定义，可以衍生出一系列结论：（推导过程和 \alpha -smooth类似）
结论1：
如果一个函数 f 是 \alpha -strongly convex，那么 f(y) \geq f(x) + \langle \nabla f(x), y-x\rangle + \frac{\alpha}{2}||y-x||_2^2

注意到，上述不等式同样有很强烈的几何意义，它意味着在 x 点附近的函数值 f 的下界，受到一个二次函数的约束。

结论2：
如果一个函数 f 是 \alpha -strongly convex，那么 \nabla^2 f(x) \geq \alpha I
<hr/>3 Smooth和Strongly convex函数所满足的其他性质

这一部门，将会给出若干个和 \beta -smooth函数、以及 \alpha -strongly convex函数相关的命题。
命题1：对于 \beta -smooth函数来说，梯度下降法必然可以让方针函数变小。
证明：如果函数 f 是 \beta -smooth函数，且梯度下降法的迭代公式为： x^{+}=x-\eta\nabla f(x) ，那么存在如下关系：
f(x^{+}) \leq f(x) + \langle \nabla f(x), -\eta\nabla f(x)\rangle + \frac{\beta}{2} ||-\eta\nabla f(x)||^2_2=f(x)-\eta(1-\eta\frac{\beta}{2})||\nabla f(x)||_2^2
所以，如果拔取 \eta < \frac{2}{\beta} ，比如 \eta=\frac{1}{\beta} ，就可以保证 f(x^{+}) \leq f(x) - \frac{1}{2\beta}||\nabla f(x)||_2^2

命题2：如果函数 f 是 \beta -smooth函数，那么存在： \frac{1}{2\beta} ||\nabla f(x)||_2^2 \leq f(x)-f(x^{*}) \leq \frac{\beta}{2} ||x-x^{*}||_2^2 ，此中 x^* 是 \min~f(x) 的最优解
证明：操作的仍然是 f(y)\leq f(x) + \langle \nabla f(x), y-x\rangle + \frac{\beta}{2} ||x-y||^2_2 这个性质。

命题3： (co-coercivity性质) 如果函数 f 是 \beta -smooth 函数且是凸函数，那么存在 \langle \nabla f(x)-\nabla f(y), x-y\rangle \leq \frac{1}{\beta} ||\nabla f(x)-\nabla f(y)||_2^2
证明：这个证明斗劲巧妙，法式省略

命题4：如果函数 f 是 \alpha -strongly convex函数，那么存在： \frac{\alpha}{2} ||x-x^{*}||_2^2 \leq f(x)-f(x^{*}) \leq \frac{1}{2\alpha} ||\nabla f(x)||_2^2 ，此中 x^* 是 \min~f(x) 的最优解
证明：操作的仍然是 f(y) \geq f(x) + \langle \nabla f(x), y-x\rangle + \frac{\alpha}{2}||y-x||_2^2 这条性质。

命题5： (coercivity性质) 如果函数 f 是 \alpha -strongly convex函数，那么存在 \langle \nabla f(x)-\nabla f(y), x-y\rangle \geq \alpha ||\nabla f(x)-\nabla f(y)||_2^2
证明：这个证明斗劲巧妙，法式省略

		自动登录	找回密码
密码			立即注册