镜像下降法

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

图示取 $C=D=U={\mathbb{R}}^n$，且 $\psi$ 可微并强凸；此时凸共轭的梯度满足 $\mathrm{\nabla }{\psi }^{\ast }=(\mathrm{\nabla }\psi {)}^{-1}$。一般约束集上的更新仍须求解前面的 Bregman 极小化子问题，不能只用这条全空间逆映射代替。

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

本例的 $\log$ 均为自然对数。取 $D=[0,\mathrm{\infty }{)}^n$、$U=(0,\mathrm{\infty }{)}^n$，负熵在零坐标处按 $0\log 0=0$ 延拓。约束集为闭概率单纯形 $C={\mathrm{\Delta }}_n$，其与 $U$ 的交正是相对内部；负熵在 $C$ 上关于 $\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$，取正整数 $T$，将三点不等式与 Young 不等式结合并求和，得到任意 $x\in C$ 的

若对所选比较器 $x$ 有正数 $B$ 满足 $D_{\psi }(x,x_0)\le B$，取正的有效上界 $G>0$，固定 $\eta =\sqrt{2B/(G^{2}T)}$。对固定凸目标，令 ${\overline{x}}_T=T^{-1}\sum _{k=0}^{T-1}{x}_k$，凸性与上述估计给出目标值差

这控制平均点的目标值，不直接控制 $\Vert {\overline{x}}_T-x\Vert$。在线版本若 $g_k\in \partial f_k(x_k)$，同一估计控制 $T^{-1}\sum _k(f_k(x_k)-f_k(x))$，即平均 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 }$ 化为平方欧氏距离，在 $f$ 可微且选 $g_k=\mathrm{\nabla }f(x_k)$ 时，子问题完成平方后得到投影梯度法理路投影梯度法Projected gradient method · Gradient projection method在每次梯度步后投影回闭凸可行集以保持可行性的约束一阶算法。；对不可微凸 $f$ 则是投影次梯度更新；因此后者只是在欧氏镜像映射下的严格特殊情形。欧氏情形可取 $D=U={\mathbb{R}}^n$，所以迭代点位于 $C$ 的边界也不妨碍镜像函数可微。例如 $C=[0,\mathrm{\infty })$、$f(x)=2x$、$x_0=1$、${\eta }_0=1$ 时，平方欧氏镜像更新得到 $x_1=0$；它在约束边界，却仍在 $U$ 中。负熵选择则产生指数权重，适用于在线学习与概率单纯形。实际选择镜像函数时还要同时检查定义域、强凸常数、对偶范数和子问题成本，缺一项都不能仅凭漂亮几何宣称更快。

随机复合镜像下降理路随机复合镜像下降Stochastic composite mirror descent · 随机复合 Bregman 更新在非欧氏几何中分开随机次梯度和精确结构项，证明更新前平均的有限预算界，并计算熵正则单纯形的真实更新。保留这里的几何，再把条件无偏次梯度与新点结构项放在不同槽位。它完整保留结构项首尾差，证明更新前平均的期望界，并计算目标熵正则与镜像熵同时出现时的幂次更新；只有镜像几何并不表示目标已被正则化。