前言
本文我们介绍优化算法收敛、收敛速度、条件数等概念。
优化算法的收敛速度
我们先来聊聊优化问题的收敛。
1.优化问题的收敛
考虑一个优化问题:
$$ \begin{aligned} \min \ & f(\boldsymbol{x}) \\ where:\ & \boldsymbol{x}\in\mathcal{D} \end{aligned}\tag{*} $$
由于我们的重点并不是约束条件,所以这里直接将$f$定义域与约束条件综合而成$\mathcal{D}$,显然(*)此时成为了一个无约束优化问题,可行域即为$\mathcal{D}$。设(*)的一个最优解为$\boldsymbol{x}^*$,其最优值为$f(\boldsymbol{x}^*)$。在很多时候,解析地求解(*)的最优解往往是不可能的,所以我们转而寻找一种迭代算法来逼近$\boldsymbol{x}^*$。设有迭代次数$\tau$,$\tau$时刻的解为:$\boldsymbol{x}^{(\tau)}$,值为$f(\boldsymbol{x}^{(\tau)})$。在迭代过程:$\tau=0,1,\cdots,\infty$中产生了两个序列:$\{\boldsymbol{x}^{(\tau)}\}$与$\{f(\boldsymbol{x}^{(\tau)}) \}$。于是,我们有如下定义:
定义1:优化算法收敛(Informal)
设有某个优化算法产生的序列$\{\boldsymbol{x}^{(\tau)}\}$与$\{f(\boldsymbol{x}^{(\tau)}) \}$,若对于任意给定的正数$\epsilon$,均存在$N\in\mathbb{N}$使得$\|\boldsymbol{x}^{(N)}-\boldsymbol{x}^* \|<\epsilon$或者$\|f(\boldsymbol{x}^{(N)})-f(\boldsymbol{x}^*) \|<\epsilon$,则称该算法是收敛的。也即$\{\boldsymbol{x}^{(\tau)}\}$收敛至$\boldsymbol{x}^*$或者$\{f(\boldsymbol{x}^{(\tau)}) \}$收敛至$f(\boldsymbol{x}^*)$。下文中我们说优化算法都是指收敛的优化算法。
现在我们有收敛的概念了,那么自然会引出一个新的问题:如果有两个都收敛的算法,也就是说它们都能求解(*),此时如何刻画哪个算法更好呢?这便是我们所要介绍的收敛速度(Rate of convergence)的概念。
2.茴香豆的四种写法
我们现在要考察的是某个优化算法的收敛速度,不妨把目光放在两个收敛序列$\{\boldsymbol{x}^{(\tau)}\}$与$\{f(\boldsymbol{x}^{(\tau)}) \}$上来。现在考察序列$\{\boldsymbol{x}^{(\tau)}-\boldsymbol{x}^*\}$与$\{f(\boldsymbol{x}^{(\tau)}) -f(\boldsymbol{x}^*)\}$,显然二者都是收敛至0的,而且大致上来看是单调递减的(下文假设其是递减的)。所谓收敛速度,我们可以从字面上理解为序列收敛至其极限值的速度,考虑到其递减性,故而一个想法便是考察:
$$ \lim _{\tau \rightarrow \infty} \frac{\left\|\boldsymbol{x}^{(\tau+1)}-\boldsymbol{x}^{*}\right\|}{\left\|\boldsymbol{x}^{(\tau)}-\boldsymbol{x}^{*}\right\|}\tag{1} $$
显然(1)式所示的极限是存在的且小于等于1。容易知道,该极限值刻画了解逼近最优解的速度,而且极限值越小,则逼近速度越快,我们此时可以称收敛速度越快。我们暂且称其为用极限刻画的收敛速度。
那么我们已经获得了一个收敛速度的定义,但是(1)式理解起来不直观,而且考虑无穷远处的比值不论数学上是否好分析,在实践中总之是没有太大意义的。在计算资源有限的情况下我们无从验证(1)所示的极限值是否正确,那么有没有能更好指导实践的定义呢?
既然无穷远处的事情没有必要分析,那么我们就从近处考虑,我们转而考察算法何时取得一个足够好的解(satisfying solution)。我们没办法也没必要观测到$\tau\to\infty$的情况,只需观测到$\|f(\boldsymbol{x}^{(\tau)})-f(\boldsymbol{x}^*)\|<\epsilon$即可,我们称满足该条件的为一个足够好的解($\epsilon$-精度解),对于某个算法而言,获得一个足够好的解所需的迭代数是有一个下界的,而且该下界是一个关于$\epsilon$的函数,我们可以写为:$\tau(\epsilon)$。由于这种定义研究的是迭代次数,我们称之为用复杂度刻画的收敛速度。
我们在第二种定义中是固定了$\epsilon$而去求解$\tau(\epsilon)$,那么从另一方面来说,我们也可以固定$\tau$,去研究$\epsilon(\tau)$,此时的收敛速度的含义为在确定的迭代数下,算法能取得一个精度为多少的解。我们记$\epsilon(\tau)=\|f(\boldsymbol{x}^{(\tau)})-f(\boldsymbol{x}^*) \|$,显然$\epsilon(\tau)$有一个以$\tau$为函数的上界。我们称这种定义为用精度刻画的收敛速度。
综上所述,我们现在有了三种刻画收敛速度的方法,接下来我们详细研究一下。
3.用极限刻画的收敛速度
由上一部分可知,(1)式所示的极限必存在且小于1,记其值为$c$:
$$ \lim _{\tau \rightarrow \infty} \frac{\left\|\boldsymbol{x}^{(\tau+1)}-\boldsymbol{x}^{*}\right\|}{\left\|\boldsymbol{x}^{(\tau)}-\boldsymbol{x}^{*}\right\|}=c\tag{2} $$
根据$c$的取值,我们定义:
- 若$c=1$,称序列$\{\boldsymbol{x}^{(\tau)}\}$(或者算法)次线性收敛(sublinear convergence)
- 若$0<c<1$,称序列$\{\boldsymbol{x}^{(\tau)}\}$线性收敛(linear convergence)
- 若$c=0$,称序列$\{\boldsymbol{x}^{(\tau)}\}$超线性收敛(superlinear convergence)
而进一步地,若$\{\boldsymbol{x}^{(\tau)}\}$是超线性收敛的,则说明$\left\|\boldsymbol{x}^{(\tau+1)}-\boldsymbol{x}^{*}\right\|$是$\left\|\boldsymbol{x}^{(\tau)}-\boldsymbol{x}^{*}\right\|$的一个高阶无穷小,则进一步地,若对于$p>1$,极限:
$$ \lim _{\tau \rightarrow \infty} \frac{\left\|\boldsymbol{x}^{(\tau+1)}-\boldsymbol{x}^{*}\right\|}{\left\|\boldsymbol{x}^{(\tau)}-\boldsymbol{x}^{*}\right\|^p}\tag{3} $$
存在,则称$\{\boldsymbol{x}^{(\tau)}\}$以$p$阶收敛。例如,在$p=2$时称为二阶收敛(quadratic convergence),$p=3$时称为三阶收敛(cubic convergence)等等。
我们在第二部分分析到,$c$越小则收敛越快。我们以一个例子直观地比较一下各种收敛速度。考察以下序列:
- $\{a^{(\tau)}=\tau^{-1} \}$,它是次线性收敛的
- $\{b^{(\tau)}=\tau^{-2} \}$,它也是次线性收敛的
- $\{c^{(\tau)}=2^{-\tau} \}$,它是线性收敛的
- $\{d^{(\tau)}=2^{-2^{\tau}}=1/2^{2^\tau} \}$,它是二次收敛的
我们以$\tau$为横坐标,值的对数为纵坐标作图:
从图中可以看出,线性收敛指在对数图中呈现直线的形式,而多项式形式的$\frac{1}{\sqrt\tau}$,$\frac{1}{\tau}$之类的都是次线性收敛。所以,用极限刻画的收敛速度只是定性地将收敛速度划分了几个大致的段,我们需要一种更加精细的刻画方法。
4.用精度刻画的收敛速度
在第二部分中我们介绍了用精度刻画的收敛速度,即研究:
$$ \epsilon({\tau})=\|f(\boldsymbol{x}^{(\tau)})-f(\boldsymbol{x}^*) \|\tag{4} $$
的上界。由于上界是一个关于$\tau$的函数,则我们可以引入刻画算法复杂度的Landau记号:假如存在正实数$M$与实数$x_0$使得对于任意${\displaystyle x\geq x_{0}}$有${\displaystyle |f(x)|\leq \ M|g(x)|}$,则我们记${\displaystyle f(x)=O(g(x))}$。对于上文提到的四个序列,用精度刻画其收敛速度即为:
- $\{a^{(\tau)}=\tau^{-1} \}$,它是次线性收敛的,$\epsilon(\tau)=O(\frac{1}{\tau})$
- $\{b^{(\tau)}=\tau^{-2} \}$,它也是次线性收敛的,$\epsilon(\tau)=O(\frac{1}{\tau^2})$
- $\{c^{(\tau)}=2^{-\tau} \}$,它是线性收敛的,$\epsilon(\tau)=O(\frac{1}{e^\tau})$
- $\{d^{(\tau)}=1/2^{2^\tau} \}$,它是二次收敛的,$\epsilon(\tau)=O(\frac{1}{e^{e^\tau}})$
由于他们的极限值为0,所以可以很轻松地得出用精度刻画的收敛速度。值得注意的是,对于线性收敛与超线性收敛的情况,我们通常将指数的底数换成$e$。
5.用复杂度刻画的收敛速度
最后,我们来研究用复杂度刻画的收敛速度,即给定$\epsilon>0$,研究$\tau(\epsilon)$的下界。其中:
$$ \forall \tau\geq\tau(\epsilon),\|f(\boldsymbol{x}^{(\tau)})-f(\boldsymbol{x}^*)\|\leq\epsilon\tag{5} $$
我们同样引入刻画下界的Landau记号:假如存在正实数$m$与实数$x_0$使得对于任意${\displaystyle x\geq x_{0}}$有${\displaystyle |f(x)|\geq \ m|g(x)|}$,则我们记${\displaystyle f(x)=\Omega(g(x))}$。对于上文提到的四个序列,用复杂度刻画其收敛速度即为:
- $\{a^{(\tau)}=\tau^{-1} \}$,它是次线性收敛的,$\epsilon(\tau)=O(\frac{1}{\tau})$,$ \tau(\epsilon)=\Omega(\frac{1}{\epsilon})$
- $\{b^{(\tau)}=\tau^{-2} \}$,它也是次线性收敛的,$\epsilon(\tau)=O(\frac{1}{\tau^2})$,$ \tau(\epsilon)=\Omega(\frac{1}{\sqrt\epsilon})$
- $\{c^{(\tau)}=2^{-\tau} \}$,它是线性收敛的,$\epsilon(\tau)=O(\frac{1}{e^\tau})$,$\tau(\epsilon)=\Omega(\log\frac{1}{\epsilon})$
- $\{d^{(\tau)}=1/2^{2^\tau} \}$,它是二次收敛的,$\epsilon(\tau)=O(\frac{1}{e^{e^\tau}})$,$\tau(\epsilon)=\Omega(\log \log\frac{1}{\epsilon})$
6.殊途同归
至此,我们已经介绍完了收敛速度的所有内容了。可能有的读者会比较迷惑,我们在第二部分与式(2)(3)(4)(5)中,不是用极限刻画$\{\boldsymbol{x}^{(\tau)}\}$的收敛速度,用复杂度、精度刻画$\{f(\boldsymbol{x}^{(\tau)}) \}$的收敛速度吗?为什么在四个序列的例子中我们能混用呢?事实上,在很多问题中,分析出$\|\boldsymbol{x}^{(\tau)}-\boldsymbol{x}^* \|$与$\|f(\boldsymbol{x}^{(\tau)})-f(\boldsymbol{x}^*) \|$中任意一个都很不容易,在说明清楚的情况下使用任意一种收敛速度的表述都是可以的。
此外就表述习惯而言,基于精度的表述中迭代次数有的论文使用的是$t$或者$k$,与这里的$\tau$是一样的;还有就是基于复杂度的表述大部分学者都直接用$O$来刻画下界,严格而言是不准确的。但是基本上都用$\epsilon$表示精度,据这一点区分就好。
条件数
在《凸性、强凸性与L-光滑》一文中我们介绍了强凸性与Lipschitz光滑性:
定义2:条件数
设某优化问题的目标函数$f$既是$\mu$-强凸的,又是$L$-光滑的,则称:
$$ \kappa=\frac L\mu\geq 1 $$
为该优化问题的条件数,显然这也是$f$的Hessian矩阵$\boldsymbol{H}$最大特征值上界与最小特征值下界之比。若$\kappa$较大,我们称优化问题(或目标函数)是病态的,反之若$\kappa$较小,则称优化问题(或目标函数)是良态的。容易知道,条件数等于函数梯度最大变化速度 / 梯度最小变化速度,其反映了梯度变化的范围。所以,在基于梯度的优化方法中,$\kappa$越小则收敛性能越好,反之则越差。
考虑二元函数的等高线,条件数越大则等高线越扁、越长,而条件数越小则越接近正圆。
至此,我们已经做好了分析优化算法的理论准备。接下来,我们首先分析Vanilla Gradient Descent。