Mirror-Prox 方法

一次镜像最优性，接两次不同反馈 ​

子问题的一阶方向条件理路一阶最优性条件First-order optimality condition · Variational inequality optimality condition以梯度和所有可行方向的非负内积充要刻画可微凸问题的全局极小点。与Bregman三点恒等式给出：若 $p=P_z(a)$，则对所有 $u\in C$，

即使比较点 $u$在约束边界，式(3)仍可用；可微性只在锚点及实际子问题解处调用。

一轮简记 $z,w,q=z_{k+1}$。对校正步应用式(3)，再对预测步取比较点 $q$，得到

对偶范数的基本配对界将交叉项控制为 $\gamma L\Vert w-z\Vert \Vert w-q\Vert$。强凸性保证两份被减去的散度至少分别为相应平方范数的一半，故在 $\gamma L\le 1$ 时，交叉项全部由它们支付。于是

固定 $u$，由单调性可将左边的 $F(w)$换成 $F(u)$作为下界。对轮次求和、除以 $\gamma N$，再对 $u$取上确界，即得式(2)。这份支付机制利用了场的Lipschitz差，而不是给每次场值本身设一个上界。

两个概率向量的完整预测与校正 ​

考虑行方最小化、列方最大化的矩阵博弈

对应场 $F(p,q)=(Mq,-M^{\mathsf{T}}p)$单调：两个交叉内积相消。选乘积范数

由于 $|M_{ij}|\le 1$，有 $\Vert Mv{\Vert }_{\mathrm{\infty }}\le \Vert v{\Vert }_1$，所以可取 $L=1$。镜像函数为两个负熵之和，散度是两个以自然对数计算的KL之和；由负熵镜像的强凸性理路镜像下降法Mirror descent method · Bregman gradient method用强凸镜像映射生成的 Bregman 几何执行线性化损失更新的约束一阶算法。，它关于上述乘积范数为1-强凸。

在每个单纯形上，镜像子问题返回

从 $p_0=(3/4,1/4),q_0=(1/2,1/2)$出发，取 $\gamma =\log 2<1$。初始反馈为 $(0,0;-1/2,1/2)$，因此预测点为

预测反馈变成 $(1/3,-1/3;-1/2,1/2)$。再从原来的 $p_0,q_0$校正，得到

若把第二次的 $p_0$擅自换成 $w_{p,0}$，第一轮恰好看不出差别，因为两者此时相同；列方若改用 $w_{q,0}$则会再次乘权，已经不等于上式。必须逐槽检查完整算法，不能靠一个坐标的巧合验证实现。

真正能计算的鞍点间隙 ​

鞍点为均匀策略对，值为零。对任意候选 $(p,q)$，全局鞍点间隙为

双线性结构使它也恰好等于该VI的Minty间隙。最坏初始Bregman距离由两个顶点取得：$\mathrm{\Theta }=\log 4+\log 2=\log 8$，所以式(2)为 $3/N$。

第一轮预测点间隙为 $5/6$，两轮平均预测点间隙约为 $0.7141545637$，三轮约为 $0.5004984598$；对应统一上界为 $3,1.5,1$。实际间隙可以远小于保证。若目标是按此界认证不超过 $0.01$，需300轮、600次完整场调用和600次乘积镜像子问题。

初始零权重、尺度与随机误差 ​

负熵梯度在零坐标不有限，本页从内部初始化。即使程序强行沿用乘法公式，初始为零的坐标也永远为零。例如行方始终被锁在 $(1,0)$时，上述博弈间隙至少为一，不能逼近均匀鞍点。

若镜像函数仅为 $\alpha$-强凸，应相应使用 $\gamma L\le \alpha$，或先把镜像函数归一化；若场整体放大十倍，Lipschitz常数也放大十倍。仅调整名义步长而不核对范数与尺度，不能保留同一个预算。

紧集本身也不保证任意镜像半径有限，尤其要检查生成函数在比较点处的延拓。带噪反馈、近似子问题或离开可微域，都增加了式(4)之外的误差项；本页不将确定性精确公式冒称随机保证。

两查询换来的保证与计算成本 ​

已有镜像下降理路镜像下降法Mirror descent method · Bregman gradient method用强凸镜像映射生成的 Bregman 几何执行线性化损失更新的约束一阶算法。对一般有界次梯度使用一次查询，典型平均目标界为 $O(N^{-1/2})$。本方法用两次查询利用单调Lipschitz结构，获得 $O(N^{-1})$间隙。输入假设和输出量都不同，不能只比较幂次就宣布对任意目标都更快。

若 $\psi (z)=\Vert z{\Vert }_2^2/2$，两次子问题分别为欧氏投影，得到外梯度法理路外梯度法Extragradient method · Korpelevich method在同一原锚点上先预测再校正，用两次场求值和投影处理单调旋转，证明有限维点收敛及平均预测点的有界域间隙率。。本页在步长端点仍证明平均界；外梯度页为整列收敛采用严格不等式，两个结论的边界不应混写。

一般每轮有两次场调用、两次镜像子问题和 $O(d)$状态更新。上述 $m\times n$ 矩阵博弈每次场调用计算 $Mq$及$M^{\mathsf{T}}p$，稠密成本 $O(mn)$，两组归一化成本 $O(m+n)$；保存运行平均另需 $O(m+n)$空间。指数权重实现可先减去共同最大对数权重，避免上溢；舍入和下溢误差若需要严格认证，须另行纳入数值误差预算。