国内有多少家做网站的企业,1688海外版,网站建设中主页源码,瑞安做微网站机器学习笔记之优化算法——梯度下降法在凸函数上的收敛性 引言回顾#xff1a;收敛速度#xff1a;次线性收敛二次上界引理 梯度下降法在凸函数上的收敛性收敛性定理介绍证明过程 引言
本节将介绍梯度下降法在凸函数上的收敛性。
回顾#xff1a;
收敛速度#xff1a;次… 机器学习笔记之优化算法——梯度下降法在凸函数上的收敛性 引言回顾收敛速度次线性收敛二次上界引理 梯度下降法在凸函数上的收敛性收敛性定理介绍证明过程 引言
本节将介绍梯度下降法在凸函数上的收敛性。
回顾
收敛速度次线性收敛
关于次线性收敛分为两种判别类型 R \mathcal R R-次线性收敛与 Q \mathcal Q Q-次线性收敛。而次线性收敛的特点是随着迭代次数的增加相邻迭代步骤产生的目标函数结果 f ( x k ) , f ( x k 1 ) f(x_k),f(x_{k1}) f(xk),f(xk1)其差异性几乎完全相同 lim k ⇒ ∞ ∣ ∣ x k 1 − x ∗ ∣ ∣ ∣ ∣ x k − x ∗ ∣ ∣ 1 \mathop{\lim}\limits_{k \Rightarrow \infty}\frac{||x_{k1} - x^*||}{||x_k - x^*||} 1 k⇒∞lim∣∣xk−x∗∣∣∣∣xk1−x∗∣∣1 例如如果数值解 x k x_k xk的目标函数结果 f ( x k ) f(x_k) f(xk)与目标函数最优解 f ∗ f^* f∗之间的差异性 ∣ ∣ f ( x k ) − f ∗ ∣ ∣ ||f(x_k) - f^*|| ∣∣f(xk)−f∗∣∣与迭代次数 k k k存在如下函数关系 G ( k ) \mathcal G(k) G(k) ∣ ∣ f ( x k ) − f ∗ ∣ ∣ ≤ G ( k ) 1 k ||f(x_k) - f^*|| \leq \mathcal G(k) \frac{1}{k} ∣∣f(xk)−f∗∣∣≤G(k)k1 当 k k k充分大时 f ( x k ) , f ( x k 1 ) f(x_k),f(x_{k1}) f(xk),f(xk1)与 f ∗ f^* f∗之间差异性的比值表示如下 lim k ⇒ ∞ ∣ ∣ f ( x k 1 ) − f ∗ ∣ ∣ ∣ ∣ f ( x k ) − f ∗ ∣ ∣ lim k ⇒ ∞ k k 1 1 \mathop{\lim}\limits_{k \Rightarrow \infty} \frac{||f(x_{k1}) - f^*||}{||f(x_k) - f^*||} \mathop{\lim}\limits_{k \Rightarrow \infty} \frac{k}{k1} 1 k⇒∞lim∣∣f(xk)−f∗∣∣∣∣f(xk1)−f∗∣∣k⇒∞limk1k1 也就是说虽然随着 k k k的增加 f ( x k ) f(x_k) f(xk)在减小;但相邻迭代结果 f ( x k ) , f ( x k 1 ) f(x_k),f(x_{k1}) f(xk),f(xk1)之间的差异性几乎可以忽略不计。那么称这种收敛速度为次线性收敛。 准确的说是 ⇒ 0 \Rightarrow 0 ⇒0的次线性收敛 lim k ⇒ ∞ { f ( x k ) } ⇒ lim k ⇒ ∞ G ( k ) 0 \mathop{\lim}\limits_{k \Rightarrow \infty} \{f(x_k)\} \Rightarrow \mathop{\lim}\limits_{k \Rightarrow \infty} \mathcal G(k) 0 k⇒∞lim{f(xk)}⇒k⇒∞limG(k)0
二次上界引理
关于二次上界引理的描述表示如下如果函数 f ( ⋅ ) f(\cdot) f(⋅)可微并对应梯度函数 ∇ f ( ⋅ ) \nabla f(\cdot) ∇f(⋅)满足利普希兹连续则函数 f ( ⋅ ) f(\cdot) f(⋅)存在二次上界。即 ∀ x , y ∈ R n ⇒ f ( y ) ≤ f ( x ) [ ∇ f ( x ) ] T ( y − x ) L 2 ∣ ∣ y − x ∣ ∣ 2 \forall x,y \in \mathbb R^n \Rightarrow f(y) \leq f(x) [\nabla f(x)]^T (y - x) \frac{\mathcal L}{2}||y - x||^2 ∀x,y∈Rn⇒f(y)≤f(x)[∇f(x)]T(y−x)2L∣∣y−x∣∣2 而二次上界引理的作用是可以通过该引理得到最优步长上界的最小值
假设 x x x固定令 ϕ ( y ) f ( x ) [ ∇ f ( x ) ] T ( y − x ) L 2 ∣ ∣ y − x ∣ ∣ 2 \begin{aligned}\phi(y) f(x) [\nabla f(x)]^T (y - x) \frac{\mathcal L}{2}||y - x||^2 \end{aligned} ϕ(y)f(x)[∇f(x)]T(y−x)2L∣∣y−x∣∣2通过选择合适的 y m i n y_{min} ymin使 ϕ ( y ) \phi(y) ϕ(y)达到最小值 y m i n arg min y ∈ R n ϕ ( y ) y_{min} \mathop{\arg\min}\limits_{y \in \mathbb R^n} \phi(y) yminy∈Rnargminϕ(y)令 ∇ ϕ ( y ) ≜ 0 \nabla \phi(y) \triangleq 0 ∇ϕ(y)≜0有 y m i n x 1 L ⋅ [ − ∇ f ( x ) ] y_{min} x \frac{1}{\mathcal L} \cdot [- \nabla f(x)] yminxL1⋅[−∇f(x)]其中 − ∇ f ( x ) - \nabla f(x) −∇f(x)即 P k \mathcal P_k Pk也就是最速下降方向而 1 L \begin{aligned}\frac{1}{\mathcal L}\end{aligned} L1则是最优步长的上确界 f ( y ) ≤ ϕ ( y m i n ) min y ∈ R n ϕ ( y ) f(y) \leq \phi(y_{min}) \mathop{\min}\limits_{y \in \mathbb R^n} \phi(y) f(y)≤ϕ(ymin)y∈Rnminϕ(y) 也就是说 在没有二次上界引理的约束下步长 α k \alpha_k αk的选择在其定义域内没有约束 ( 0 , ∞ ) (0, \infty) (0,∞)经过二次上界引理的约束后步长 α k \alpha_k αk的选择从原始的 ( 0 , ∞ ) (0,\infty) (0,∞)约束至 ( 0 , 1 L ] \begin{aligned}\left(0,\frac{1}{\mathcal L}\right]\end{aligned} (0,L1]。
延伸关于区间 ( 0 , 1 L ] \begin{aligned}\left(0,\frac{1}{\mathcal L}\right]\end{aligned} (0,L1]可以模糊地认为满足 Armijo \text{Armijo} Armijo准则。关于步长变量 α \alpha α的函数 ϕ ( α ) f ( x k 1 ) \phi(\alpha) f(x_{k1}) ϕ(α)f(xk1)中当 α ∈ ( 0 , 1 L ] \alpha \in \begin{aligned}\left(0,\frac{1}{\mathcal L}\right]\end{aligned} α∈(0,L1]时等价于存在一条直线 L ( α ) \mathcal L(\alpha) L(α)以该直线作为划分边界对应 α \alpha α的范围正好是 ( 0 , 1 L ] \begin{aligned}\left(0,\frac{1}{\mathcal L}\right]\end{aligned} (0,L1] 吐槽实际上用这张图是不太合理的因为下面的图对应的 f ( ⋅ ) f(\cdot) f(⋅)更加复杂二次上界约束的范围仅仅在下面 α \alpha α轴的绿色实线部分但很明显在该函数中存在更优质的 α \alpha α结果。
梯度下降法在凸函数上的收敛性
收敛性定理介绍
梯度下降法在凸函数上的收敛性定理表示如下
条件 函数 f ( ⋅ ) f(\cdot) f(⋅)向下有界在定义域内可微并且 f ( ⋅ ) f(\cdot) f(⋅)是凸函数关于 f ( ⋅ ) f(\cdot) f(⋅)的梯度函数 ∇ f ( ⋅ ) \nabla f(\cdot) ∇f(⋅)满足利普希兹连续梯度下降法迭代过程中步长 α k ( k 1 , 2 , 3 , ⋯ ) \alpha_k(k1,2,3,\cdots) αk(k1,2,3,⋯)有明确的约束范围 α k ∈ ( 0 , 1 L ] \begin{aligned}\alpha_k \in \left(0,\frac{1}{\mathcal L} \right]\end{aligned} αk∈(0,L1] 结论数值解序列 { x k } k 0 ∞ \{x_{k}\}_{k0}^{\infty} {xk}k0∞对应的目标函数结果 { f ( x k ) } k 0 ∞ \{f(x_k)\}_{k0}^{\infty} {f(xk)}k0∞以 O ( 1 k ) \begin{aligned}\mathcal O \left(\frac{1}{k}\right)\end{aligned} O(k1)收敛于目标函数最优解 f ∗ f^* f∗。 其中 O ( 1 k ) \begin{aligned}\mathcal O \left(\frac{1}{k}\right)\end{aligned} O(k1)表示以 G ( k ) C ⋅ 1 k \begin{aligned}\mathcal G(k) \mathcal C \cdot \frac{1}{k}\end{aligned} G(k)C⋅k1的次线性收敛级别的收敛速度( C \mathcal C C为常数)。
证明过程
根据二次上界引理依然将 x x x设为上一次迭代的数值解 x i − 1 x_{i-1} xi−1对应的 y y y为当前迭代步骤的数值解 x i x_i xi。由于是梯度下降法因而在线搜索方法的基础上将方向 P i \mathcal P_i Pi表示为最速下降方向 ∇ f ( x i − 1 ) \nabla f(x_{i-1}) ∇f(xi−1)步长依然使用步长变量 α \alpha α进行表示 y − x x i − x i − 1 − ∇ f ( x i − 1 ) ⋅ α y - x x_i - x_{i - 1} -\nabla f(x_{i-1}) \cdot \alpha y−xxi−xi−1−∇f(xi−1)⋅α 将二次上界不等式进行相应替换 将上式代入~ f ( x i ) ≤ f ( x i − 1 ) [ ∇ f ( x i − 1 ) ] T [ − ∇ f ( x i − 1 ) ⋅ α ] L 2 ∣ ∣ − ∇ f ( x i − 1 ) ⋅ α ∣ ∣ 2 f(x_i) \leq f(x_{i-1}) [\nabla f(x_{i-1})]^T [-\nabla f(x_{i-1}) \cdot \alpha] \frac{\mathcal L}{2} ||-\nabla f(x_{i-1}) \cdot \alpha||^2 f(xi)≤f(xi−1)[∇f(xi−1)]T[−∇f(xi−1)⋅α]2L∣∣−∇f(xi−1)⋅α∣∣2 观察不等式右侧可以继续化简
将内积写作 ∣ ∣ ⋅ ∣ ∣ 2 ||\cdot||^2 ∣∣⋅∣∣2的形式。 ∣ ∣ − ∇ f ( x i − 1 ) ⋅ α ∣ ∣ 2 ∣ ∣ ∇ f ( x i − 1 ) ⋅ α ∣ ∣ 2 ||- \nabla f(x_{i-1}) \cdot \alpha||^2 ||\nabla f(x_{i-1}) \cdot \alpha||^2 ∣∣−∇f(xi−1)⋅α∣∣2∣∣∇f(xi−1)⋅α∣∣2,这里消掉一个负号;由于 α ∈ ( 0 , 1 L ] \begin{aligned}\alpha \in \left(0,\frac{1}{\mathcal L}\right]\end{aligned} α∈(0,L1],是一个标量直接将其提到范数外侧。 I r i g h t f ( x i − 1 ) − α ⋅ ∣ ∣ ∇ f ( x i − 1 ) ∣ ∣ 2 L 2 ⋅ α 2 ⋅ ∣ ∣ ∇ f ( x i − 1 ) ∣ ∣ 2 \mathcal I_{right} f(x_{i-1}) - \alpha \cdot ||\nabla f(x_{i-1})||^2 \frac{\mathcal L}{2} \cdot \alpha^2 \cdot ||\nabla f(x_{i-1})||^2 Irightf(xi−1)−α⋅∣∣∇f(xi−1)∣∣22L⋅α2⋅∣∣∇f(xi−1)∣∣2
由 α ≤ 1 L \begin{aligned}\alpha \leq \frac{1}{\mathcal L}\end{aligned} α≤L1可知 L ≤ 1 α \begin{aligned}\mathcal L \leq \frac{1}{\alpha} \end{aligned} L≤α1。将该式代入到上式中 消掉分母中的 α \alpha α并于前面的项结合。 I r i g h t ≤ f ( x i − 1 ) − α ⋅ ∣ ∣ ∇ f ( x i − 1 ) ∣ ∣ 2 1 2 α ⋅ α 2 ⋅ ∣ ∣ ∇ f ( x i − 1 ) ∣ ∣ 2 f ( x i − 1 ) − α 2 ⋅ ∣ ∣ ∇ f ( x i − 1 ) ∣ ∣ 2 \begin{aligned} \mathcal I_{right} \leq f(x_{i-1}) - \alpha \cdot ||\nabla f(x_{i-1})||^2 \frac{1}{2 \alpha} \cdot \alpha^2 \cdot ||\nabla f(x_{i-1})||^2 \\ f(x_{i-1}) - \frac{\alpha}{2} \cdot ||\nabla f(x_{i-1})||^2 \end{aligned} Iright≤f(xi−1)−α⋅∣∣∇f(xi−1)∣∣22α1⋅α2⋅∣∣∇f(xi−1)∣∣2f(xi−1)−2α⋅∣∣∇f(xi−1)∣∣2 基于梯度下降法使用二次上界引理可以得到 f ( x i − 1 ) f(x_{i-1}) f(xi−1)与 f ( x i ) f(x_i) f(xi)之间存在如下关联关系 f ( x i ) ≤ f ( x i − 1 ) − α 2 ⋅ ∣ ∣ ∇ f ( x i − 1 ) ∣ ∣ 2 i 1 , 2 , 3 , ⋯ f(x_i) \leq f(x_{i-1}) - \frac{\alpha}{2} \cdot ||\nabla f(x_{i-1})||^2\quad i1,2,3,\cdots f(xi)≤f(xi−1)−2α⋅∣∣∇f(xi−1)∣∣2i1,2,3,⋯ 根据凸函数的性质必然有函数 f ( ⋅ ) f(\cdot) f(⋅)任一位置的切线 f ( ⋅ ) f(\cdot) f(⋅)均在该切线上方。见下图 由于条件: f ( ⋅ ) f(\cdot) f(⋅)向下有界,因此该函数必然’开口向上‘。 其中红色点 ( x ∗ , f ∗ ) (x^*,f^*) (x∗,f∗)表示最优点以上一次迭代产生的 x i − 1 x_{i-1} xi−1为切点做一条切线必然有 x ∗ x^* x∗在该切线函数上的函数值 f ′ ≤ f ∗ f \leq f^* f′≤f∗。 f ′ f f′表示如下 f ′ f ( x i − 1 ) − [ ∇ f ( x i − 1 ) ] T ( x i − 1 − x ∗ ) ≤ f ∗ f f(x_{i-1}) - [\nabla f(x_{i-1})]^T (x_{i-1} - x^*) \leq f^* f′f(xi−1)−[∇f(xi−1)]T(xi−1−x∗)≤f∗ 移项从而有 f ( x i − 1 ) ≤ f ∗ [ ∇ f ( x i − 1 ) ] T ( x i − 1 − x ∗ ) f(x_{i-1}) \leq f^* [\nabla f(x_{i-1})]^T (x_{i-1} - x^*) f(xi−1)≤f∗[∇f(xi−1)]T(xi−1−x∗) 将上式代入有 I r i g h t ≤ f ∗ [ ∇ f ( x i − 1 ) ] T ( x i − 1 − x ∗ ) ⏟ 替换 f ( x i − 1 ) − α 2 ⋅ ∣ ∣ ∇ f ( x i − 1 ) ∣ ∣ 2 \mathcal I_{right} \leq \underbrace{f^* [\nabla f(x_{i-1})]^T (x_{i-1} - x^*)}_{替换f(x_{i-1})}- \frac{\alpha}{2} \cdot ||\nabla f(x_{i-1})||^2 Iright≤替换f(xi−1) f∗[∇f(xi−1)]T(xi−1−x∗)−2α⋅∣∣∇f(xi−1)∣∣2 为了凑平方项将上式调整至如下形式 将 − α 2 \begin{aligned}-\frac{\alpha}{2}\end{aligned} −2α凑出 α 2 \alpha^2 α2,其他项跟随变化。 I r i g h t ≤ − 1 2 α { α 2 ∣ ∣ ∇ f ( x i − 1 ) ∣ ∣ 2 − 2 α ⋅ [ ∇ f ( x i − 1 ) ] T ( x i − 1 − x ∗ ) } \mathcal I_{right} \leq -\frac{1}{2 \alpha} \left\{\alpha^2 ||\nabla f(x_{i-1})||^2 - 2\alpha \cdot [\nabla f(x_{i-1})]^T(x_{i-1} - x^*)\right\} Iright≤−2α1{α2∣∣∇f(xi−1)∣∣2−2α⋅[∇f(xi−1)]T(xi−1−x∗)} 对大括号内的项进行配方 I r i g h t ≤ f ∗ − 1 2 α { α 2 ∣ ∣ ∇ f ( x i − 1 ) ∣ ∣ 2 − 2 α ⋅ [ ∇ f ( x i − 1 ) ] T ( x i − 1 − x ∗ ) ∣ ∣ x i − 1 − x ∗ ∣ ∣ 2 ⏟ 平方项 − ∣ ∣ x i − 1 − x ∗ ∣ ∣ 2 } f ∗ − 1 2 α [ ∣ ∣ α ⋅ ∇ f ( x i − 1 ) − ( x i − 1 − x ∗ ) ∣ ∣ 2 − ∣ ∣ x i − 1 − x ∗ ∣ ∣ 2 ] \begin{aligned} \mathcal I_{right} \leq f^* - \frac{1}{2 \alpha} \left\{\underbrace{\alpha^2 ||\nabla f(x_{i-1})||^2 - 2\alpha \cdot [\nabla f(x_{i-1})]^T(x_{i-1} - x^*) ||x_{i-1} - x^*||^2 }_{平方项}- ||x_{i-1} - x^*||^2\right\} \\ f^* - \frac{1}{2\alpha} \left [||\alpha \cdot \nabla f(x_{i-1}) - (x_{i-1} - x^*)||^2 - ||x_{i-1} - x^*||^2\right] \end{aligned} Iright≤f∗−2α1⎩ ⎨ ⎧平方项 α2∣∣∇f(xi−1)∣∣2−2α⋅[∇f(xi−1)]T(xi−1−x∗)∣∣xi−1−x∗∣∣2−∣∣xi−1−x∗∣∣2⎭ ⎬ ⎫f∗−2α1[∣∣α⋅∇f(xi−1)−(xi−1−x∗)∣∣2−∣∣xi−1−x∗∣∣2] 观察中括号内第一项 ∣ ∣ α ⋅ ∇ f ( x i − 1 ) − ( x i − 1 − x ∗ ) ∣ ∣ 2 ||\alpha \cdot \nabla f(x_{i-1}) - (x_{i-1} - x^*)||^2 ∣∣α⋅∇f(xi−1)−(xi−1−x∗)∣∣2由于是范数的平方项因而在范数内部添加一个负号不会影响其值的变化 ∣ ∣ α ⋅ ∇ f ( x i − 1 ) − ( x i − 1 − x ∗ ) ∣ ∣ 2 ∣ ∣ x i − 1 − α ⋅ ∇ f ( x i − 1 ) − x ∗ ∣ ∣ 2 ||\alpha \cdot \nabla f(x_{i-1}) - (x_{i-1} - x^*)||^2 ||x_{i-1} - \alpha \cdot \nabla f(x_{i-1}) - x^*||^2 ∣∣α⋅∇f(xi−1)−(xi−1−x∗)∣∣2∣∣xi−1−α⋅∇f(xi−1)−x∗∣∣2 从迭代角度观察 x i − 1 − α ⋅ ∇ f ( x i − 1 ) x i x_{i-1} - \alpha \cdot \nabla f(x_{i-1}) x_{i} xi−1−α⋅∇f(xi−1)xi从而上式可继续化简为 提一个负号调换一下位置。 { ∣ ∣ α ⋅ ∇ f ( x i − 1 ) − ( x i − 1 − x ∗ ) ∣ ∣ 2 ∣ ∣ x i − x ∗ ∣ ∣ 2 I r i g h t ≤ f ∗ − 1 2 α [ ∣ ∣ x i − x ∗ ∣ ∣ 2 − ∣ ∣ x i − 1 − x ∗ ∣ ∣ 2 ] f ∗ 1 2 α [ ∣ ∣ x i − 1 − x ∗ ∣ ∣ 2 − ∣ ∣ x i − x ∗ ∣ ∣ 2 ] \begin{cases} ||\alpha \cdot \nabla f(x_{i-1}) - (x_{i-1} - x^*)||^2 ||x_i - x^*||^2 \\ \quad \\ \begin{aligned} \mathcal I_{right} \leq f^* - \frac{1}{2\alpha} \left[||x_i - x^*||^2 - ||x_{i-1} - x^*||^2\right] \\ f^* \frac{1}{2\alpha} \left[||x_{i-1} - x^*||^2 - ||x_i - x^*||^2\right] \end{aligned} \end{cases} ⎩ ⎨ ⎧∣∣α⋅∇f(xi−1)−(xi−1−x∗)∣∣2∣∣xi−x∗∣∣2Iright≤f∗−2α1[∣∣xi−x∗∣∣2−∣∣xi−1−x∗∣∣2]f∗2α1[∣∣xi−1−x∗∣∣2−∣∣xi−x∗∣∣2]
至此可以得到如下不等式结果 f ( x i ) − f ∗ ≤ 1 2 α ( ∣ ∣ x i − 1 − x ∗ ∣ ∣ 2 − ∣ ∣ x i − x ∗ ∣ ∣ 2 ) f(x_i) - f^* \leq \frac{1}{2\alpha}(||x_{i-1} - x^*||^2 - ||x_i - x^*||^2) f(xi)−f∗≤2α1(∣∣xi−1−x∗∣∣2−∣∣xi−x∗∣∣2) 观察不等式左侧描述的意义是当前迭代步骤的目标函数结果 f ( x i ) f(x_i) f(xi)与最优解 f ∗ f^* f∗之间的偏差。从初始化数值解 x 0 x_0 x0开始我们会得到一系列的不等式结果 { f ( x 1 ) − f ∗ ≤ 1 2 α ( ∣ ∣ x 0 − x ∗ ∣ ∣ 2 − ∣ ∣ x 1 − x ∗ ∣ ∣ 2 ) f ( x 2 ) − f ∗ ≤ 1 2 α ( ∣ ∣ x 1 − x ∗ ∣ ∣ 2 − ∣ ∣ x 2 − x ∗ ∣ ∣ 2 ) ⋮ f ( x k ) − f ∗ ≤ 1 2 α ( ∣ ∣ x k − 1 − x ∗ ∣ ∣ 2 − ∣ ∣ x k − x ∗ ∣ ∣ 2 ) \begin{cases} \begin{aligned} f(x_1) - f^* \leq \frac{1}{2\alpha} (||x_0 - x^*||^2 - ||x_1 - x^*||^2) \\ f(x_2) - f^* \leq \frac{1}{2\alpha} (||x_1 - x^*||^2 - ||x_2 - x^*||^2) \\ \vdots \\ f(x_k) - f^* \leq \frac{1}{2\alpha} (||x_{k-1} - x^*||^2 - ||x_k - x^*||^2) \end{aligned} \end{cases} ⎩ ⎨ ⎧f(x1)−f∗f(x2)−f∗f(xk)−f∗≤2α1(∣∣x0−x∗∣∣2−∣∣x1−x∗∣∣2)≤2α1(∣∣x1−x∗∣∣2−∣∣x2−x∗∣∣2)⋮≤2α1(∣∣xk−1−x∗∣∣2−∣∣xk−x∗∣∣2) 将这些不等式对应位置相加有
等式右侧的中间项都被消掉了~因为 ∣ ∣ x k − x ∗ ∣ ∣ 2 ≥ 0 ||x_k - x^*||^2 \geq 0 ∣∣xk−x∗∣∣2≥0恒成立从而消掉含变量的项。 ∑ i 1 k [ f ( x i ) − f ∗ ] ≤ 1 2 α ( ∣ ∣ ∣ x 0 − x ∗ ∣ ∣ 2 − ∣ ∣ x k − x ∗ ∣ ∣ 2 ) ≤ 1 2 α ∣ ∣ x 0 − x ∗ ∣ ∣ 2 \sum_{i1}^k [f(x_i) - f^*] \leq \frac{1}{2\alpha}(|||x_0 - x^*||^2 - ||x_k - x^*||^2) \leq \frac{1}{2 \alpha} ||x_0 - x^*||^2 i1∑k[f(xi)−f∗]≤2α1(∣∣∣x0−x∗∣∣2−∣∣xk−x∗∣∣2)≤2α1∣∣x0−x∗∣∣2
关于我们要证的 ∣ ∣ f ( x k ) − f ∗ ∣ ∣ ||f(x_k) - f^*|| ∣∣f(xk)−f∗∣∣可以表示为如下形式
由于优化问题的收敛性必然有 f ( x k ) ≤ f ( x k − 1 ) ≤ ⋯ ≤ f ( x 1 ) f(x_{k}) \leq f(x_{k-1})\leq \cdots\leq f(x_1) f(xk)≤f(xk−1)≤⋯≤f(x1),从而每一项: ∣ ∣ f ( x k ) − f ∗ ∣ ∣ ≤ ∣ ∣ f ( x k − 1 ) − f ∗ ∣ ∣ ≤ ⋯ ≤ ∣ ∣ f ( x 1 ) − f ∗ ∣ ∣ ||f(x_k) - f^*|| \leq ||f(x_{k-1}) - f^*|| \leq \cdots \leq ||f(x_1) - f^*|| ∣∣f(xk)−f∗∣∣≤∣∣f(xk−1)−f∗∣∣≤⋯≤∣∣f(x1)−f∗∣∣,从而有: ∑ i 1 k [ f ( x k ) − f ∗ ] ≤ ∑ i 1 k [ f ( x i ) − f ∗ ] \begin{aligned}\sum_{i1}^k[f(x_k) - f^*] \leq \sum_{i1}^{k} [f(x_i) - f^*]\end{aligned} i1∑k[f(xk)−f∗]≤i1∑k[f(xi)−f∗]。将上式结果带入~ f ( x k ) − f ∗ 1 k ∑ i 1 k [ f ( x k ) − f ∗ ] ≤ 1 k ∑ i 1 k [ f ( x i ) − f ∗ ] ≤ 1 k [ 1 2 α ∣ ∣ x 0 − x ∗ ∣ ∣ 2 ] f(x_k) - f^* \frac{1}{k} \sum_{i1}^{k}[f(x_k) - f^*] \leq \frac{1}{k} \sum_{i1}^{k}[f(x_i) - f^*] \leq \frac{1}{k} \left[\frac{1}{2\alpha}||x_0 - x^*||^2\right] f(xk)−f∗k1i1∑k[f(xk)−f∗]≤k1i1∑k[f(xi)−f∗]≤k1[2α1∣∣x0−x∗∣∣2]
观察 [ 1 2 α ∣ ∣ x 0 − x ∗ ∣ ∣ 2 ] \begin{aligned}\left[\frac{1}{2\alpha}||x_0 - x^*||^2\right]\end{aligned} [2α1∣∣x0−x∗∣∣2]中 α ∈ ( 0 , 1 L ] \begin{aligned}\alpha \in \left(0,\frac{1}{\mathcal L} \right] \end{aligned} α∈(0,L1] x 0 , x ∗ x_0,x^* x0,x∗都是确定的常数因而该项可视作常数 C \mathcal C C。最终有 f ( x k ) − f ∗ ≤ 1 k ⋅ C f(x_k) - f^* \leq \frac{1}{k} \cdot \mathcal C f(xk)−f∗≤k1⋅C 我们可以令 G ( k ) 1 k ⋅ C \begin{aligned}\mathcal G(k) \frac{1}{k} \cdot \mathcal C\end{aligned} G(k)k1⋅C可以看出它就是一个级别为 1 k \begin{aligned}\frac{1}{k}\end{aligned} k1的次线性收敛。
相关参考 【优化算法】梯度下降法-凸函数的收敛性
