0x00 Preface

本篇分析确定性一阶优化方法。基本定义见 Part 11。默认使用欧氏范数，并区分梯度下降与非光滑问题中的次梯度法。

光滑部分讨论无约束问题；非光滑部分允许闭凸可行集 $\mathcal C$，并用投影保证迭代留在可行集内。设最优解 $w^{\ast}$ 存在，$f^{\ast}=f(w^{\ast})$。

0x01 Definition of Convergence

需要先说明衡量什么误差：

  • 函数值误差：$f(w_T)-f^{\ast}$。
  • 到最优解的距离：$\Vert w_T-w^{\ast}\Vert^2$；有多个最优解时，也可以讨论到最优解集合的距离。
  • 非凸问题中的驻点指标：$\min_{0\le t<T}\Vert\nabla f(w_t)\Vert^2$，或梯度平方的平均值。

不同指标之间不能任意互换。梯度范数小不代表找到了全局最优解，也不单独保证迭代序列收敛到某个点。

线性收敛通常指误差上界为 $Cq^T$，$0<q<1$；$O(1/T)$ 和 $O(1/\sqrt T)$ 属于次线性收敛。对于正误差序列 $e_t$，Q-超线性收敛指 $e_{t+1}/e_t\to0$，Q-二次收敛要求最终有 $e_{t+1}\le Ce_t^2$。不使用 $\log\log e_t$ 描述二次收敛，因为 $e_t<1$ 时这个实数表达式没有定义。

下面的复杂度均指保证相应误差不超过 $\epsilon$ 的迭代次数；常数依赖目标函数和起始点。

0x02 Smooth Strongly Convex with GD

defination

若 $f$ 为 $L$-光滑、$\mu$-强凸，采用固定步长 $0<\eta\le1/L$，则
$$ f(w_T)-f^*\le(1-\eta\mu)^T(f(w_0)-f^*). $$

由下降引理和更新 $w_{t+1}=w_t-\eta\nabla f(w_t)$：

$$ \begin{aligned} f(w_{t+1})-f(w_t) &\le-\eta\left(1-\frac{L\eta}{2}\right)\|\nabla f(w_t)\|^2\\ &\le-\frac\eta2\|\nabla f(w_t)\|^2 \le-\eta\mu(f(w_t)-f^*). \end{aligned} $$

最后一步使用 PL 不等式。移项得到单步递推，再归纳 $T$ 次即可。

当 $\eta=1/L$、$\mu<L$ 时，令 $E_0=f(w_0)-f^{\ast}$，有 $f(w_T)-f^{\ast}\le e^{-\mu T/L}E_0$，所以 $T\ge(L/\mu)\log(E_0/\epsilon)$ 足够。条件数为 $L/\mu$；这个结果是线性收敛。若 $\mu=L$，上述递推在一步后已给出零误差。

0x03 Smooth Convex with GD

defination

若 $f$ 凸且 $L$-光滑，采用 $\eta=1/L$，则对 $T\ge1$，
$$ f(w_T)-f^*\le\frac{L\|w_0-w^*\|^2}{2T}. $$

记 $R_t=\Vert w_t-w^{\ast}\Vert$。由凸性和更新的距离恒等式，

$$ f(w_t)-f^*\le\langle\nabla f(w_t),w_t-w^*\rangle =\frac{R_t^2-R_{t+1}^2}{2\eta}+\frac\eta2\|\nabla f(w_t)\|^2. $$

加上下降引理，在 $\eta=1/L$ 时梯度平方项抵消：

$$ f(w_{t+1})-f^*\le\frac L2(R_t^2-R_{t+1}^2). $$

从 $t=0$ 到 $T-1$ 求和，得到 $\sum_{t=0}^{T-1}(f(w_{t+1})-f^{\ast})\le LR_0^2/2$。由于此步长下函数值单调不增，左侧至少为 $T(f(w_T)-f^{\ast})$，结论成立。迭代复杂度为 $O(LR_0^2/\epsilon)$，属于次线性收敛。

0x04 Non-smooth Convex with Subgradient Method

设 $f$ 凸，采用

$$ w_{t+1}=\Pi_{\mathcal C}(w_t-\eta_tg_t),\qquad g_t\in\partial f(w_t),\quad\|g_t\|\le G. $$

$\Pi_{\mathcal C}$ 为欧氏投影；无约束情况下去掉投影即可。只要求所选次梯度有界，不把这个条件误称为光滑性。

Fixed Step Size for a Given Horizon

令 $R=\Vert w_0-w^{\ast}\Vert>0$。预先给定 $T\ge1$，取固定步长 $\eta=R/(G\sqrt T)$，则

$$ \min_{0\le t<T}(f(w_t)-f^*)\le\frac{GR}{\sqrt T}. $$

若只知道初始距离的上界，可以用该上界设置步长；若起点已最优，直接停止。

投影不增加到 $w^{\ast}\in\mathcal C$ 的距离，故

$$ R_{t+1}^2\le R_t^2-2\eta(f(w_t)-f^*)+\eta^2G^2. $$

累加后除以 $2\eta T$：

$$ \min_{0\le t<T}(f(w_t)-f^*) \le\frac{R^2}{2\eta T}+\frac{\eta G^2}{2} =\frac{GR}{\sqrt T}. $$

因此 $T\ge G^2R^2/\epsilon^2$ 足够。此结论约束最佳迭代点；由 Jensen，不加权平均点也满足同一函数值界，但不保证最后一个点有同一界。

Polyak Step Size

若已知 $f^{\ast}$，且尚未达到最优，可取

$$ \eta_t=\frac{f(w_t)-f^*}{\|g_t\|^2}. $$

凸性给出的是不等式 $\langle g_t,w_t-w^{\ast}\rangle\ge f(w_t)-f^{\ast}$。代入距离递推得到

$$ R_{t+1}^2\le R_t^2-\frac{(f(w_t)-f^*)^2}{\|g_t\|^2}. $$

累加并使用 $\Vert g_t\Vert\le G$，有 $\sum_{t=0}^{T-1}(f(w_t)-f^{\ast})^2\le G^2R^2$，于是最佳函数值误差同样不超过 $GR/\sqrt T$。若 $g_t=0$，凸性意味着该点已最优；此时不计算含零分母的步长。实际问题常不知道 $f^{\ast}$，因此这是有额外信息要求的步长规则。

0x05 Smooth Non-convex with GD

假设 $f$ 为 $L$-光滑且有有限下界 $f_{\inf}$。取 $\eta=1/L$，下降引理给出

$$ f(w_{t+1})\le f(w_t)-\frac1{2L}\|\nabla f(w_t)\|^2. $$

从 $t=0$ 到 $T-1$ 累加：

$$ \frac1T\sum_{t=0}^{T-1}\|\nabla f(w_t)\|^2 \le\frac{2L(f(w_0)-f_{\inf})}{T}. $$

最佳梯度平方也不超过这个界。达到 $\Vert\nabla f\Vert^2\le\epsilon$ 需要 $O(1/\epsilon)$ 次迭代；若目标是 $\Vert\nabla f\Vert\le\epsilon$，则为 $O(1/\epsilon^2)$。这不是全局最优值误差保证。

0x06 Strongly Convex and Non-smooth with Subgradient Method

设 $f$ 在闭凸可行集 $\mathcal C$ 上 $\mu$-强凸，最优解在 $\mathcal C$ 中取得，沿投影次梯度迭代有 $\Vert g_t\Vert\le G$。这里不要求全空间上同时强凸且函数值 Lipschitz。

取 $\eta_t=2/(\mu(t+2))$，对 $T\ge1$，有

$$ \min_{0\le t<T}(f(w_t)-f^*)\le\frac{2G^2}{\mu(T+1)}. $$

证明：强凸的次梯度不等式与投影给出

$$ R_{t+1}^2\le(1-\mu\eta_t)R_t^2-2\eta_t(f(w_t)-f^*)+\eta_t^2G^2. $$

代入步长，移项：

$$ f(w_t)-f^*\le\frac\mu4\left[tR_t^2-(t+2)R_{t+1}^2\right]+\frac{G^2}{\mu(t+2)}. $$

乘以 $t+1$ 后累加，距离项望远镜消去，得到

$$ \begin{aligned} \sum_{t=0}^{T-1}(t+1)(f(w_t)-f^*) &\le-\frac\mu4T(T+1)R_T^2 +\frac{G^2}{\mu}\sum_{t=0}^{T-1}\frac{t+1}{t+2}\\ &\le\frac{TG^2}{\mu}. \end{aligned} $$

除以 $\sum_{t=0}^{T-1}(t+1)=T(T+1)/2$ 即得结论。使用相同权重的平均点也满足该函数值界。其速率是 $O(1/T)$，仍为次线性。

0x07 Conclusion

条件与方法本文保证的指标误差上界的阶
光滑强凸，GD最后迭代点的函数值误差$O((1-\mu/L)^T)$
光滑凸，GD最后迭代点的函数值误差$O(1/T)$
非光滑凸，次梯度法最佳点或平均点的函数值误差$O(1/\sqrt T)$
光滑非凸，GD平均梯度平方$O(1/T)$
非光滑强凸，投影次梯度法最佳点或加权平均点的函数值误差$O(1/T)$

这些结论分别依赖上文的步长、下界、最优解存在性或次梯度界，不能只按“凸/非凸”标签套用。一般非光滑非凸问题需要另外的算法和驻点概念。

Reference

Sources: 2 3 4 5.

  1. Part 1 ↩︎

  2. Boyd, S., Subgradient Methods. ↩︎

  3. Boyd, S. and Vandenberghe, L., Convex Optimization, Chapter 9. ↩︎

  4. Beck, A., First-Order Methods in Optimization. ↩︎

  5. Nesterov, Y., Introductory Lectures on Convex Optimization: A Basic Course. ↩︎