镜像下降方法Mirror Descent

本篇在投影梯度下降法的基础上，引出Bregman散度的概念，并且介绍Mirror Descent方法

Review：投影梯度下降法

对于一个带约束的优化问题，我们已经有了投影梯度下降法

我们将其写为更加简洁的形式：

其中的投影过程，我们使用了二范数作为欧氏空间中对距离的度量

Bregman散度

然而对于不同的问题，其可行域有不同的结构，其目标函数可能有特殊的结构（可能是非欧的），因此我们使用二范数来度量距离可能就不大合适了，因此提出了Bregman散度：

对于可微的凸函数，Bregman散度

特殊地，当时，，因此我们可以知道，二范数也是一种Bregman散度。

对于不同的问题/可行域，可以通过选取适当的Bregman散度来作为距离的度量，达到两个目的：

1. 更加高效的计算投影
2. 使得距离的度量更加贴合实际问题

为什么说Bregman散度可以作为距离的度量，我们知道，梯度下降方法是一种first order method，我们使用的是如下的式子：

这其中我们有一个先验的假设就是线性逼近式与函数的差距可以用欧式距离来衡量，于是我们使用了一个二范数作为penalty（类似于岭回归），保证每一步的下降

当问题不满足上述的假设的时候，就不能使用二范数了，于是我们把上式推广为

使用Bregman散度作为penalty，在这种思想下我们就有了Mirror Descent

镜像下降方法 Mirror Descent

在投影方法中，使用Bregman散度代替二范数作为距离的度量：

这就是镜像梯度下降方法的迭代式，Bregman散度的使用指导我们寻找更好的收敛速度等算法性能。

其中对于”镜像“，笔者的理解如下：

对于Bregman散度的定义式：

进行变形得到：

可以看到，仍然可以看成是函数值与其线性近似之间的差异，但是只不过由换作了，我们可以认为是一个基函数，将原本的和映射到一个新的空间（镜像空间）中衡量距离。

如果选取合适的基函数，那么算法的改进是显著的，例如对于一个维空间里的单纯性，其中足够大（可能是几千维）。如果仍然使用欧氏距离，那么对于这个单纯形，浮点数的计算误差可能很大，无法准确反应差异。如果我们使用entropy函数作为距离的度量，则能更好的反应差异。

对Mirror Descent的联想

Mirror Descent是投影梯度下降方法的推广，投影梯度下降方法用于解决带约束的问题，那么是否可以把Mirror Descent用于带约束的智能体学习或者安全强化学习