在线镜像下降

更新规则 ​

在线凸优化中，决策集 $K$ 是凸集。第 $t$ 轮先选 $x_t\in K$，再见凸损失 $f_t$ 及一个次梯度 $g_t\in \partial f_t(x_t)$。选择可微势函数 $\psi$，其相对范数 $\Vert \cdot \Vert$ 是 $\alpha$-强凸的；对应 Bregman 散度为

$$D_{\psi }(x,y)=\psi (x)-\psi (y)-⟨\mathrm{\nabla }\psi (y),x-y⟩.$$

在线镜像下降使用显式更新

$$x_{t+1}=\arg \underset{x\in K}{min}\{\eta ⟨g_t,x⟩+D_{\psi }(x,x_t)\}.$$

线性项要求沿负梯度移动，Bregman 项则按所选几何惩罚离开 $x_t$。$D_{\psi }$ 一般不对称，更新中的参数顺序不能交换。

一步不等式与遗憾推导 ​

最优性条件对任意比较器 $u\in K$ 给出

$$⟨\eta g_t+\mathrm{\nabla }\psi (x_{t+1})-\mathrm{\nabla }\psi (x_t),u-x_{t+1}⟩\ge 0.$$

结合 Bregman 三点恒等式公理库Bregman 散度Bregman divergence凸函数值高于其一阶切平面的余量，用来度量与生成函数几何相适配的偏离。，并把 $x_t-u=(x_t-x_{t+1})+(x_{t+1}-u)$ 分开，可得

$$\eta ⟨g_t,x_t-u⟩\le D_{\psi }(u,x_t)-D_{\psi }(u,x_{t+1})+\eta ⟨g_t,x_t-x_{t+1}⟩-D_{\psi }(x_{t+1},x_t).$$

强凸性给 $D_{\psi }(x_{t+1},x_t)\ge \frac{\alpha }{2}\Vert x_{t+1}-x_t{\Vert }^2$；对偶范数 Hölder 不等式与配方再把最后两项控制为 ${\eta }^2\Vert g_t{\Vert }_{\ast }^2/(2\alpha )$。由凸性 $f_t(x_t)-f_t(u)\le ⟨g_t,x_t-u⟩$，对 $t$ 求和后 Bregman 项望远镜消去：

$${\mathrm{Regret}}_T(u)\le \frac{D_{\psi }(u,x_1)}{\eta }+\frac{\eta }{2\alpha }\sum _{t=1}^T\Vert g_t{\Vert }_{\ast }^2.$$

若 $D_{\psi }(u,x_1)\le B$、$\Vert g_t{\Vert }_{\ast }\le G$，取 $\eta =\sqrt{2\alpha B/(G^{2}T)}$，得到 $G\sqrt{2BT/\alpha }$。

两个具体例子：欧氏球与概率单纯形 ​

在欧氏空间取 $\psi (x)=\frac{1}{2}\Vert x{\Vert }_2^2$，$D_{\psi }(x,y)=\frac{1}{2}\Vert x-y{\Vert }_2^2$，更新就是投影在线梯度下降。这里 primal 与 dual 范数都是 ${\ell }_2$。

在概率单纯形 ${\mathrm{\Delta }}_n$ 上取负熵 $\psi (p)=\sum _i{p}_i\log p_i$，Bregman 散度是 $\mathrm{KL}(p\Vert q)$。一阶条件给

$$p_{t+1,i}\propto p_{t,i}{e}^{-\eta g_{t,i}},$$

即 exponentiated-gradient/乘法更新。以均匀 $p_1$ 开始有 $D_{\psi }(u,p_1)\le \log n$，梯度由 ${\ell }_{\mathrm{\infty }}$ 控制时得到 $O(G\sqrt{T\log n})$ 遗憾，比在单纯形上硬用欧氏直径更贴合坐标结构。

边界 ​

势函数必须与决策域匹配。负熵在零坐标处梯度发散，通常从相对内部初始化，并由乘法更新保持正坐标；若约束把解压到边界，需用次梯度/Legendre 型势函数的精确定义。Bregman 投影也未必有闭式，计算它的代价属于算法实现而非遗憾公式自动免除的部分。

强凸范数与梯度对偶范数必须成对：用 ${\ell }_1$ 强凸性却把梯度按 ${\ell }_2$ 代入会破坏一步界。OMD 与 FTRL 常能导出相似更新，但一个围绕当前点做 Bregman 近端步，一个重解累计线性化加正则的目标；不能仅凭最终公式相近就视为同一定义。

参考资料

• Arkadi Nemirovski and David Yudin, Problem Complexity and Method Efficiency in Optimization.
• Shai Shalev-Shwartz, “Online Learning and Online Convex Optimization,” 2012.