镜像下降法

欧氏梯度默认各坐标用同一平方距离计价，但许多可行域并不服从这种几何。概率向量靠近边界时，加减一个固定坐标量容易产生负数；稀疏多面体的欧氏半径也可能随维数放大。镜像函数把原空间弯曲成合适的对偶坐标：线性化损失仍提供方向，而 Bregman 散度决定离旧点多远算“昂贵”。

更新式中散度的槽位不能交换。变量位于第一个槽 $D_{\psi }(x,x_k)$，旧点提供切平面锚；一般 Bregman 散度不对称，交换会产生另一算法。强凸性使散度至少控制平方范数，从而把线性损失的对偶范数界转成位移和 regret 界。镜像下降不是把梯度名字换掉，而是在不改变一阶信息的前提下选择更匹配约束的几何。

在概率单纯形 ${\mathrm{\Delta }}_n$ 的相对内部取关于 $\Vert \cdot {\Vert }_1$ 为 $1$-强凸的负熵

用 Lagrange 乘子处理 $\sum _i{x}_i=1$，更新得到乘法权重

取 $x_k=(1/2,1/2)$、$g_k=(1,0)$、${\eta }_k=\log 3$，未归一化权重为 $(1/6,1/2)$，归一化后恰为 $(1/4,3/4)$。两坐标保持非负且和为一，无需事后欧氏投影。若某初始坐标为零，负熵梯度在边界不有限，乘法更新也永远无法恢复该坐标；标准理论因而从相对内部开始，或采用适当广义定义。

镜像函数若不关于目标范数强凸，三点散度不能控制实际位移，标准率会失去常数。次问题若不能精确求解，也需记录误差。对非凸目标，线性化加 Bregman 稳定项仍可运行，但本页的凸 regret/最优性推论不成立。步长过大可能让函数值上升；镜像下降的基础分析常控制加权平均或 regret，而不是保证最后一点单调。

若 $\psi$ 关于 $\Vert \cdot \Vert$ 为 $1$-强凸且 $\Vert g_k{\Vert }_{\ast }\le G$，将三点不等式与 Young 不等式结合并求和，得到任意 $x\in C$ 的

若对所选比较器 $x$ 有正数 $D$ 满足 $D_{\psi }(x,x_0)\le D$，固定 $\eta =\sqrt{2D/(G^{2}T)}$ 时，固定凸目标的平均点误差为 $O(G\sqrt{D/T})$；在线版本把同一估计解释为平均 regret。在 $n$ 个坐标的单纯形上采用负熵并从 $x_0=(1/n,\dots ,1/n)$ 均匀初始化时，才有对所有比较器成立的 $D_{\psi }(x,x_0)\le \log n$；任意内点初始化不享有这个统一常数。

若选 $\psi (x)=\frac{1}{2}\Vert x{\Vert }_2^2$，$D_{\psi }$ 化为平方欧氏距离，子问题完成平方后得到投影梯度法公理库投影梯度法Projected gradient method · Gradient projection method在每次梯度步后投影回闭凸可行集以保持可行性的约束一阶算法。；因此后者只是在欧氏镜像映射下的严格特殊情形。负熵选择则产生指数权重，适用于在线学习与概率单纯形。实际选择镜像函数时还要同时检查定义域、强凸常数、对偶范数和子问题成本，缺一项都不能仅凭漂亮几何宣称更快。