【凸优化算法】两种视角看待Mirror Descent

闲鱼技术01 · 发表于 2022-3-1 09:52

Motivation

Mirror Descent是对Gradient Descent的扩展。因此他的Motivation来源于Gradient Descent：

Gradient Descent假设了f是关于二范数L-Lipschitz的，收敛速度受到L大小影响。那么如果f是其他范数Lipschitz的，可能直接用Gradient就不那么合适了。例如f是无穷范数L-Lipschitz的，则可以推出f是关于二范数 $\sqrt nL$ -Lipschitz的。如果n非常大时，Gradient Descent收敛速度很慢。
Gradient Descent的公式是 $x_{t+1} = x_t + \eta_t \nabla f(x_t)$ 。如果从更抽象的角度，所在的是primal space，而是在dual space。Gradient Descent相当于对primal space和dual space中的向量直接线性组合了。在带二范数的primal space中（也就是通常的情况）可以直接组合，因为2-norm的自对偶的。但是在其他范数下，不那么合理了。
还有一种最简单的Motivation，请看下面的Proximal Point View。

Proximal Point View

Gradient Descent的 $x^{t+1} = x^t + \eta_t \nabla f(x^t)$ 等价于：

$x^{t+1} = \arg\min_{x} (f(x^t) + \nabla f(x^t)(x- x^t) + \frac{1}{2 \eta}||x-x^t||^2) \\$
其中， $f(x^t) + \nabla f(x^t)(x- x^t)$ 是  在  处的线性近似项（linear approximation），我们希望  小，所以也希望这个线性近似项尽可能小。我们又希望 $x^{t+1}、x^t$ 能尽可能接近一点，否则线性近似效果是不好的。所以想到引入了一个regularizer，想把  往  方向拉近一点。这就是引入 $\frac{1}{2 \eta}||x-x^t||^2$ （proximity term）的作用。
引入的  表征的是2-norm，反映的是欧几里得空间。为了处理非欧空间、其他范数，我们还需要做一个泛化。我们不妨看两个例子：
Example 1. Quadratic Minimization
对于一个条件数很大的QP问题：

$\min \frac{1}{2} (x-x^*)^TQ(x- x^*) , \ with \ \mathop{\kappa}=\frac{\max_i Q_{i,i}}{\min_i Q_{i,i}} \gg 1\\$
Q可以理解为各个坐标方向被scale差别很大，因此如果我们能够把  改成 $\frac{1}{2 \eta}(x-x^t)^TQ(x-x^t)$ ，对坐标轴进行rescale一下，会更适合这个问题。
Example 2. Probability Simplex.
考虑一个概率单纯性问题：

$\min_{x\in \triangle} f(x) \\$

$with \ \ \triangle := \{ x \in R^n_+: \textbf{1}^Tx = 1 \}\\$
如果将泛化为KL散度，更能够反映  这种概率之间的距离。
所谓的Mirror Descent把 $\frac{1}{2}||x-x^t||^2$ 用一个更广泛的  来替代。(是Bregman Divergence，下面讨论其定义与性质）。
MD的迭代过程变为：

$x^{t+1} = \arg\min_{x} (f(x^t) + \nabla f(x^t)(x- x^t) + \frac{1}{\eta_t}D_{\varphi}(x,x^t))\\$
Bregman Divergence

定义. 是由严格凸、可导的  生成的：

$D_{\varphi}(x,z) := \varphi(x) - \varphi(z) - \langle \nabla \varphi(z),x-z \rangle \\$
我们既然用Bregmen Divergence来反映  之间的距离，那么就要考虑三个问题：
1. Bregman Divergence能够刻画距离吗，比如 $x=x_t$ 的时候，  是否等于0。
2. Bregmen Divergence是凸的吗？如果不是凸的，那么 $\arg\min_{x} (f(x^t) + \nabla f(x^t)(x- x^t) + \frac{1}{\eta_t}D_{\varphi}(x,x^t))$ 将不是凸优化问题。
3. Bregman Divergance既然是泛化的，那么是否可以推导出Gradient Descent、Example 1、Example2这些具体情况？
下面回答第一个问题。由于凸的，因此 $D_{\varphi}(x,z) := \varphi(x) - \varphi(z) - \langle \nabla \varphi(z),x-z \rangle \ge 0$ 等号在 $x =z$ 处取。
对于第二个问题， $D_{\varphi}(x,z)$ 在固定z的情况下，关于x是凸的。而 $\nabla f(x^t)(x- x^t)$ 是凸的（因为是线性函数所以凸），由此 $f(x^t) + \nabla f(x^t)(x- x^t) + \frac{1}{\eta_t}D_{\varphi}(x,x^t)$ 是凸函数 $(\eta_t >0)$ 。
对第三个问题：
如果取 $\varphi(x) = \frac{1}{2} || x||^2$ ， $D_{\varphi}(x,x^t) = \frac{1}{2}|| x-x^t||^2$ ，对应的就是Gradient Descent。
如果取 $\varphi(x) = \frac{1}{2} x^TQx$ ， $D_{\varphi}(x,x^t) = \frac{1}{2}(x-x^t)^TQ(x-x^t)$ ，对应的就是Example 1的泛化。
如果取 $\varphi(x) =$ $\sum_{i=1}^n x_i \log x_i$ ， $D_{\varphi}(x,x^t) = -\sum_{i=1}^n x_i \log \frac{x^t_i}{x_i}$ ，对应的就是Example 2的泛化。
基于上面讨论，Mirror Descent在处处可导的情况下：

$x^{t+1} \gets \arg\min_{x \in K} (\eta_t \langle \nabla f(x_t), x\rangle + D_{\varphi}(x, x^{t})) \\ \tag{1}$
如果有不可导的地方，就用次梯度来代替梯度。
Mirror Space View

前面在Motivation中谈到了primal space和dual space。一般认为，  所在的是primal space，而  所在的是dual space。
Nemirovski and Yudin的思路是：

把primal space的通过mirror map映射到dual space中，记为 $\theta^t$ 。
在dual space上做梯度下降： $\theta^{t+1} = \theta^t - \eta_t \nabla f(x^t)$ 。
在把 $\theta^{t+1}$ 映射回primal space，记为。
如果优化问题具有约束集，将投影到约束集中，记为。

那这里的mirror map是什么呢？mirror map就是上一节中生成Bregman Divergence 的 $\varphi(x,z)$ 的梯度。
由此，Nemirovski and Yudin的思路写成算法（2）就是：

Map to dual space：
Gradient in dual space： $\theta^{t+1} \gets \theta^t - \eta_t \nabla f(x^t)$
Map back to primal space：
Project into constraint： $x^{t+1} \gets \arg \min_{x \in K} D_{\varphi}(x,\bar{x}^{t+1})$

我们对上面这个算法讨论两点：

步骤三中的一定可逆吗？或者说，这步的能求出来吗？
算法（2）和Proximal Point View中的算法（1）是同一个吗？

回答第一个问题，对于一般的凸函数  ，很有可能无法求。因此我们要求  是bijection的。即满足下面两个条件：
(i)  在约束集K中是凸的，且处处可导。
(ii) 的对偶空间是 $R^n$ ，即 $\{ \nabla \varphi(x):x \in K \} = R^n$ 。
Remark. （i）保证了  。（ii）保证了  可解。
回答第二个问题。我们从算法（2）来推导出算法（1）：

$x^{t+1} = \arg \min_{x \in K} D_{\varphi}(x,\bar{x}^{t+1}) \\$

$= \arg \min_{x \in K} \varphi(x) - \varphi(\bar{x}^{t+1}) - \langle \nabla \varphi(\bar{x}^{t+1}), x - \bar{x}^{t+1} \rangle \quad \quad (Definition \ of \ Bregmen \ Divergence)\\$

$= \arg \min_{x \in K} \varphi(x)- \langle \nabla \varphi(\bar{x}^{t+1}), x \rangle$

$= \arg \min_{x \in K} \varphi(x)- \langle \nabla \varphi(x^t) - \eta_t \nabla f(x^t), x \rangle$

$= \arg \min_{x \in K} \langle \eta_t \nabla f(x^t), x \rangle + \varphi(x)- \langle \nabla \varphi(x^t) , x \rangle$

$= \arg \min_{x \in K} \langle \eta_t \nabla f(x^t), x \rangle + \varphi(x) - \varphi(x^t)- \langle \nabla \varphi(x^t) , x -x^t\rangle$

$= \arg \min_{x \in K} \langle \eta_t \nabla f(x^t), x \rangle +D_{\varphi}(x,x^t)$
由于等式都是等价了，因此也可以反过来通过（2）来推导出（1）。
至此Proximal Point View和Mirror Space View的结论是identical的。
读书笔记小结

这篇读书笔记主要讨论Proximal Point View和Mirror Space View两个视角下的Mirror Descent。
Mirror Descent的收敛性分析主要使用的Three Point theorem、Pythagotean theorem，得到一个关于Online Optimization的收敛结论，这个证明比较麻烦，笔记就不写了。
最后是我的一点感慨。Mirror Space View理解起来比较困难。本人的知识储备限制，里面涉及的很多例如Dual Norm, conjugate function、linear functional，这些东西虽然公式都能看懂，但是我还是感觉好抽象。感觉我还是不能站在一个更高的角度取思考这些问题，还要继续思考，继续啃书。

yukamu · 发表于 2022-3-1 09:59

想问一下大神这个Mirror Space的观点可以指导新的算法设计吗？还是说仅仅是为了数学证明?

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