2020-04-29

Strong convexity and implications

在讨论无约束凸优化问题(1)的时候，我们会假设 $f:R^n\to R$ 是一个凸二次可微的函数。考虑一个起始点 $x_0$ ，记 $S=\left\{x \in \operatorname{dom} f | f(x) \leq f(x^{(0)})\right\}\tag{0}$ 显然 $S$ 是一个闭集。此外，我们设 $p^*=\inf f(x)=f(x^*)$ 为最优值。

有时候，我们还会给目标函数加上两个更强的条件。

strong convexity

简而言之，在闭集 $S$ 上， $f$ 的Heisen矩阵的特征值有下确界 $m>0$ 。如果这个条件被满足，由Taylor展开： $f(y)=f(x)+\nabla f(x)^{T}(y-x)+\frac{1}{2}(y-x)^{T} \nabla^{2} f(z)(y-x) \tag{1}$
其中 $z$ 是线段 $[x,y]$ 上的一点。

继而，我们有：
$f(y) \geq f(x)+\nabla f(x)^{T}(y-x)+\frac{m}{2}\|y-x\|_{2}^{2}\tag{2}$
这给出了函数的一个更好的下界。

另一个条件，在闭集 $S$ 上， $f$ 的Heisen矩阵的特征值有上确界 $M$ （因为闭集，保证了上确界存在）。通过式(1)，我们可以得到类似式(2)的结论： $f(y) \leq f(x)+\nabla f(x)^{T}(y-x)+\frac{M}{2}\|y-x\|_{2}^{2}\tag{3}$
这其实就给出了函数的一个上界。

综合这两个条件： $m I \preceq \nabla^{2} f(x) \preceq M I \quad ,\forall x \in S \tag{4}$

接下来我们来推导，加上这两个条件，有什么用。

注意到(2)式的右边是一个关于 $y$ 的凸函数，在 $\tilde{y}=x-\frac{1}{m}\nabla f$ 时最小，从而：

上式说明，当 $\nabla f$ 模长很小很小的时候， $f(x)$ 跟最优值 $p^*$ 的距离也很小很小。虽然这个结论看起来很显然，但是我们从数学的角度证明了它！ $\|\nabla f(x)\|_{2} \leq(2 m \epsilon)^{1 / 2} \Longrightarrow f(x)-p^{\star} \leq \epsilon\tag{5}$ 利用(5)式，我们可以通过梯度的模长，来控制与最优解之间的距离。

类似的推导能得到更强的结论：

对于第二种情况：

$\nabla^{2} f(x) \preceq M I \Rightarrow p^{\star} \leq f(x)-\frac{1}{2 M}\|\nabla f(x)\|_{2}^{2}\tag{6}$

总结一下，在一个闭集 $S$ 上，理想情况下，凸函数的Heisen矩阵的特征值是“可控的”，我们从数学上推导出当某处的梯度模长很接近0的时候，其实离最优解和最优值不远了，这个“接近”的程度可以由估计式给出。尽管大部分时候我们没有办法确定 $m$ 和 $M$ ，但是只要梯度足够小，还是可以保证非常接近最优解的。

2020-04-29

Strong convexity and implications

推荐阅读更多精彩内容