灵感来源
当我们求一个凸且可微的函数在凸集可行域内的最小值，也就是求以下优化问题时：
如果函数本身比较复杂，不妨用梯度下降，一点点逼近最优。每一次逼近的位置，可以是一个近似的更简单函数的最优值。比如，当前点邻域内的二阶泰勒展开：
或者，把最后一项简化得更清cū爽cāo些，变成:
这样得到的更新策略就是牛顿法。
可以看到，简化后的近似取代了原来二阶导和夹角余弦平方的乘积，变成了一个可调节的参数。这一项二范数也可以看做是一阶泰勒展开和函数本身之间差距的近似补偿，决定了近似函数的曲率。
当衡量两个分布之间的距离时，最后一项用欧氏距离就显得不合时宜了。似乎可以考虑那些probability divergence metrics， 比如-divergence, KL divergence，Total variation distance等。
形式初现
当当当！此时我们引入mirror descent的关键——Bregman divergence function。它便是欧氏距离的拓展，帮助数值优化问题找到更合适的近似函数。
Bregman divergence function长这样：
其中是可微且凸的函数。
于是，mirror descent的更新公式就是：
每一次迭代，先解无凸集约束优化问题，再以Bregman divergence为距离度量把无约束最优决策投影到上得到
。这种用Bregman divergence度量距离而不是用欧氏距离来度量的投影方法，叫做Bregman Projection。
参数选择与对应解
当是2范数时，D就是欧式距离。所以欧式距离是Bregman divergence的特殊情形。D也可以有其他情形：如当
是马氏距离时，D也是马氏距离；当
是负熵（negative entropy，
,
）时，D是KL散度；
是无约束负熵，D是广义KL散度
。
不难通过计算证明，对于马氏距离来说，它的迭代公式有显式解：
KL散度的迭代公式也有显式解，通常这种形式的解叫做 exponentiated gradient descent或者entropic descent：
事实上，mirror descent的迭代公式有另一种写法：
其中是
的Bregman Projection，
。
为什么叫mirror呢？
因为当是
时，
其中是
的Fenchel共轭函数。
通过
得到了
,
又通过
投影到了更新的
上。
找合适的有三个要点：
- 拟合局部曲率
- 拟合可行域的几何形状
- Bregman Projection 计算方便（inexpensive）
Bregman divergence也有一些特点：
- 非负
- 对于函数的第一个自变量而言（也就是每次迭代待优化的那个）是凸的
- 一般不对称，
步长与收敛性
通过一些数值实验，我们会发现这个可调节参数的大小对梯度下降的收敛性举足轻重，如果它不合适的话容易发散。毕竟，它的存在要使得近似函数和函数本身足够接近才算精准。
那么理论上呢？
观察D，我们会发现类似于三角不等式的three-point property，如式(10)所示。它是收敛性的保证。
由于投影在凸集上，类似于余弦定理，根据是钝角，我们可以得到
等号在是仿射平面的时候取到。
根据凸性，当前位置的函数值离最优值相差不超过：
最后能够得到这样的结论：
如果在
上凸且Lipschitz连续（
），
是
-强凸，那么：
收敛性的证明详见斯坦福EE364b的幻灯片
根据(12)，定义，
时有：
如此，给和
调参的思路就有迹可循啦。
网友评论