随机复合镜像下降 | Codeboy's Blog

形式陈述

求解 $\min_{x\in C}F(x)=f(x)+h(x)$ 。 $C$ 为闭凸集， $f$ 凸且在所需点有有限次梯度； $h$ 为 proper 闭凸结构项，允许编码额外约束。最优点 $x^*$ 存在。沿用镜像下降的定义域约定： $\psi$ 在镜像内域可微，并在有效可行域上关于范数 $\|\cdot\|$ 为1-强凸； $D_\psi(u,x)$ 的第二槽必须可微，第一槽允许边界延拓。初始点 $x_0$ 事先固定，属于 $C\cap\operatorname{dom}h$ 及镜像可微区域。所有子问题取得解，迭代点仍在可微区域及 $\operatorname{dom}h$ 内。

历史 $\mathcal F_t$ 包含当前点 $x_t$ 。本轮 oracle 返回 $v_t$ ，要求

s_t:=\mathbb E[v_t\mid\mathcal F_t]\in\partial f(x_t), \qquad \mathbb E[\|v_t\|_*^2\mid\mathcal F_t]\le G^2.\tag{1}

这里是整个随机次梯度的二阶矩，不是中心化噪声方差。条件期望相对于全部旧历史；仅有各轮边际无偏不够。假设有关随机量可积、更新可测。给定固定预算 $T\ge1$ 、固定 $\eta>0$ ，执行

x_{t+1}=\arg\min_{x\in C} \{\eta\langle v_t,x\rangle+\eta h(x)+D_\psi(x,x_t)\}, \qquad \bar x_T=\frac1T\sum_{t=0}^{T-1}x_t.\tag{2}

输出更新前平均点、实际 oracle 次数、精确 Bregman 子问题次数、参数及保证类型。若有已知上界 $B\ge D_\psi(x^*,x_0)$ ，以及已知有限常数 $h_{\min}\le h(x)$ 对有效可行域成立，记 $H=h(x_0)-h_{\min}\ge0$ ，则

\mathbb E[F(\bar x_T)-F^*] \le\frac{B}{\eta T}+\frac{\eta G^2}{2}+\frac HT.\tag{3}

$B,G>0$ 时取 $\eta=\sqrt{2B/(G^2T)}$ ，前两项合为 $G\sqrt{2B/T}$ 。退化情况使用未优化式，不把零步长代入分母。本结论不要求 $f$ 光滑，也不把 $h$ 的次梯度并入随机 oracle。

直觉

随机项决定本轮向哪边移动，结构项在新点精确计价，镜像几何决定移动成本。三者的职责不同。用负熵作镜像，并不表示优化目标已经含熵正则；只有式(2)中另写的 $h$ 才改变目标。

复合更新还有一个容易漏掉的时间错位：随机次梯度在 $x_t$ 查询，结构项却在 $x_{t+1}$ 评价。把两者直接当作同一个点的 $F$ 会遗漏首尾差 $h(x_0)-h(x_T)$ 。式(3)用 $H$ 为这项付账，因此明确返回 $x_0,\ldots,x_{T-1}$ 的平均。

熵镜像在对数几率中把旧状态和随机方向组合，熵正则再使旧对数几率收缩；图中同时标明更新前平均 — 随机方向、结构项与平均输出的不同位置

随机近端梯度使用光滑项的中心化方差、欧氏 prox 和更新后平均。本页使用可能不光滑的 $f$ 、原始对偶二阶矩与非欧氏 Bregman 子问题。即使欧氏情形的某次更新恰好相同，两页的假设、输出及保证也不能互换。

例子与边界

两坐标熵正则：算更新，也算输出

在概率单纯形 $\Delta_2$ 取 $\psi(x)=\sum_i x_i\log x_i$ 、 $h(x)=\lambda\sum_i x_i\log x_i$ ， $0\log0=0$ 。负熵关于 $\ell_1$ 为1-强凸，其对偶范数为 $\ell_\infty$ 。 $\lambda\ge0$ 且 $x_0$ 各坐标为正时，拉格朗日一阶条件给

x_{t+1,i}= \frac{x_{t,i}^{1/(1+\eta\lambda)} \exp[-\eta v_{t,i}/(1+\eta\lambda)]} {\sum_jx_{t,j}^{1/(1+\eta\lambda)} \exp[-\eta v_{t,j}/(1+\eta\lambda)]}.\tag{4}

取 $\lambda=\eta=1$ 、 $x_0=(1/2,1/2)$ ，oracle 每轮独立等概率返回 $(\log9,0)$ 或 $(0,0)$ 。它的条件均值是 $(\log3,0)$ ，因此 $f(x)=x_1\log3$ 。可取 $G=\log9$ 、 $B=\log2$ ； $h(x_0)=h_{\min}=-\log2$ ，故 $H=0$ 。

若前两次返回依次为 $(\log9,0)$ 、 $(0,0)$ ，则

x_1=(1/4,3/4),\qquad x_2=\left(\frac1{1+\sqrt3},\frac{\sqrt3}{1+\sqrt3}\right), \qquad \bar x_2=(3/8,5/8).

最后一个状态 $x_2$ 不进入两轮的更新前平均。目标最优点恰为 $x^*=(1/4,3/4)$ ， $F^*=-\log(4/3)$ ；直接展开得到 $F(x)-F^*=\operatorname{KL}(x\|x^*)$ ，所以该条路径的输出误差是

\frac38\log\frac32+\frac58\log\frac56\approx0.03809844.

这是某条路径的实际目标差；式(3)是重复运行的期望上界。一步输出 $\bar x_1=x_0$ ，并非新点。即使另看新点， $\mathbb Ex_1=(3/8,5/8)$ 也不等于先把 oracle 平均后做式(4)所得的 $(1/(1+\sqrt3),\sqrt3/(1+\sqrt3))$ 。无偏方向经过非线性映射后不能仍称无偏点。

维数优势究竟来自哪里

在 $d$ 维单纯形均匀初始化，若 $\|v_t\|_\infty\le M$ ，熵镜像给 $B\le\log d$ 、 $G\le M$ 。 $H=0$ 时，式(3)为 $M\sqrt{2\log d/T}$ 。采用欧氏镜像且仍只有相同的逐坐标信息，则 $G_2\le\sqrt dM$ 、 $B_2\le(1-1/d)/2$ ，相应界为 $M\sqrt{(d-1)/T}$ 。

例如 $d=1000,M=1,T=10000$ ，两界约为0.03717与0.31607。比较使用相同的信息和相同查询次数；是否节省运行时间，还取决于两个子问题的实现。不能把 $\ell_\infty$ 的小常数直接填入欧氏证明。

若初始某坐标为零，乘法形式无法恢复它。例如线性损失的最优顶点恰在这个坐标上，算法可以永远错过最优解。若 $h$ 无有效下界，则 $H$ 未定义，不能把首尾项静默删掉；若只能近似解式(2)，残差必须另进证明。

推论与应用

完整的一步式和望远镜证明

对子问题的最优性使用 Bregman 三点恒等式，任取有效比较器 $u$ ，有

\eta[\langle v_t,x_{t+1}-u\rangle+h(x_{t+1})-h(u)] \le D_\psi(u,x_t)-D_\psi(u,x_{t+1})-D_\psi(x_{t+1},x_t).

将线性项改成 $x_t-u$ ，由强凸性及对偶范数 Young 不等式，新增位移项与负散度之和至多 $\eta^2\|v_t\|_*^2/2$ 。再加上 $\eta[h(x_t)-h(x_{t+1})]$ ，并用凸性 $f(x_t)-f(u)\le\langle s_t,x_t-u\rangle$ ，得到

\begin{aligned} \eta[F(x_t)-F(u)]\le{}&D_\psi(u,x_t)-D_\psi(u,x_{t+1}) +\frac{\eta^2}2\|v_t\|_*^2\\ &+\eta[h(x_t)-h(x_{t+1})] +\eta\langle s_t-v_t,x_t-u\rangle. \end{aligned}\tag{5}

最后的内积只含历史可测的 $x_t-u$ ，其条件期望为零。取 $u=x^*$ ，对 $T$ 轮求和：Bregman 势与 $h$ 首尾项分别消去；丢掉终端非负散度，以 $H$ 控制剩余结构项。再用Jensen 不等式把平均函数值转为平均点的函数值，除以 $\eta T$ 就是式(3)。证明没有假设每轮目标下降，也没有处理任意停时。

采样与费用接口

固定有限和可用非均匀分量采样生成满足式(1)的方向；关键是其二阶矩必须按本页对偶范数计算。每轮通常有一次分量调用、一次 Bregman 子问题和 $O(d)$ 的平均累加；式(4)的全向量表示需要 $O(d)$ 算术及指数运算，不能因只抽一个数据分量便称为常数时间。

只有有限 $p$ 阶矩而无二阶矩时，可改读裁剪镜像的高概率预算。它会承认裁剪偏差并另证噪声集中；式(3)本身没有提供那个结论。

自测与答案

在式(4)令 $\lambda=0$ ，哪一项消失？答案：旧坐标的幂变回1，得到通常的乘法权重；镜像几何仍在，目标熵正则才消失。
若 $B=2,G=3,H=1,T=200$ ，最优固定步长及期望界是多少？答案： $\eta=1/(15\sqrt2)$ ，界 $3/\sqrt{50}+1/200\approx0.42926407$ 。把 $H/T$ 漏掉会报出更小但未被此证明支持的数。

参考资料

Sébastien Bubeck，Convex Optimization: Algorithms and Complexity，2015 v2，§§4.2–4.3、§6.1 Theorem 6.1，镜像几何与随机 oracle；本文另保留复合结构项的首尾差并完整证明
Peilin Zhao、Tong Zhang，Stochastic Optimization with Importance Sampling for Regularized Loss Minimization，ICML 2015，§3.1 的 proximal stochastic mirror descent。本文给出固定步长、更新前平均的自包含保守界，不挪用其他输出的常数

形式陈述 ​

两坐标熵正则：算更新，也算输出 ​

维数优势究竟来自哪里 ​

完整的一步式和望远镜证明 ​

采样与费用接口 ​

自测与答案 ​