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

闲鱼技术01

Motivation

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

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

Proximal Point View

Gradient Descent的 等价于：


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


Q可以理解为各个坐标方向被scale差别很大，因此如果我们能够把  改成 ，对坐标轴进行rescale一下，会更适合这个问题。
Example 2. Probability Simplex.
考虑一个概率单纯性问题：




如果将泛化为KL散度，更能够反映  这种概率之间的距离。
所谓的Mirror Descent把 用一个更广泛的  来替代。(是Bregman Divergence，下面讨论其定义与性质）。
MD的迭代过程变为：


Bregman Divergence

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


我们既然用Bregmen Divergence来反映  之间的距离，那么就要考虑三个问题：
1. Bregman Divergence能够刻画距离吗，比如 的时候，  是否等于0。
2. Bregmen Divergence是凸的吗？如果不是凸的，那么 将不是凸优化问题。
3. Bregman Divergance既然是泛化的，那么是否可以推导出Gradient Descent、Example 1、Example2这些具体情况？
下面回答第一个问题。由于凸的，因此 等号在 处取。
对于第二个问题， 在固定z的情况下，关于x是凸的。而 是凸的（因为是线性函数所以凸），由此 是凸函数 。
对第三个问题：
如果取 ， ，对应的就是Gradient Descent。
如果取，，对应的就是Example 1的泛化。
如果取 ， ，对应的就是Example 2的泛化。
基于上面讨论，Mirror Descent在处处可导的情况下：


如果有不可导的地方，就用次梯度来代替梯度。
Mirror Space View

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

• 把primal space的  通过mirror map映射到dual space中，记为 。
  
• 在dual space上做梯度下降： 。
  
• 在把 映射回primal space，记为  。
  
• 如果优化问题具有约束集，将  投影到约束集中，记为  。
  

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

• Map to dual space：
  
• Gradient in dual space：
  
• Map back to primal space：
  
• Project into constraint：
  

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

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

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














由于等式都是等价了，因此也可以反过来通过（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

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