裁剪随机镜像的高概率保证

形式陈述

沿用随机复合镜像的凸目标 $F=f+h$ 、1-强凸镜像、精确子问题及更新前平均。已知 $B\ge D_\psi(x^*,x_0)$ 、已知正数 $D>0$ 上界控制有效域直径，且 $H=h(x_0)-h_{\min}\ge0$ 。本页用有限原始矩替代二阶矩：给定全部旧历史 $\mathcal F_t$ ，原始 oracle $g_t$ 满足

s_t:=\mathbb E[g_t\mid\mathcal F_t]\in\partial f(x_t), \qquad \mathbb E[\|g_t\|_*^p\mid\mathcal F_t]\le M^p, \quad 1<p\le2,\ M>0.\tag{1}

这里约束 $g_t$ 本身，不是 $g_t-s_t$ 的中心矩。事先固定 $T\ge1$ 、 $0<\delta<1$ 、阈值 $\tau>0$ 与步长 $\eta>0$ ；裁剪后执行

c_t=g_t\min\{1,\tau/\|g_t\|_*\},\qquad x_{t+1}=\arg\min_{x\in C}\{\eta\langle c_t,x\rangle+\eta h(x)+D_\psi(x,x_t)\}.\tag{2}

零向量规定仍为零。裁剪在与镜像配对的对偶范数中做。令

\ell=\log(2/\delta),\quad v=M^p\tau^{2-p},\qquad S=Tv+\sqrt{2T\tau^2v\ell}+\frac23\tau^2\ell.\tag{3}

返回 $\bar x_T=T^{-1}\sum_{t=0}^{T-1}x_t$ 。本页证明以至少 $1-\delta$ 的概率，

\begin{aligned} F(\bar x_T)-F^*\le{}&\frac{B}{\eta T}+\frac{\eta S}{2T}+\frac HT +DM^p\tau^{1-p}\\ &+D\sqrt{\frac{2v\ell}{T}}+\frac{4D\tau\ell}{3T}. \end{aligned}\tag{4}

这是模型下的固定预算高概率误差上界。它不要求原始二阶矩存在，但要求式(1)的有效上界、有限域直径和精确可行更新；不是仅由输出点计算出来的对偶 gap。

直觉

裁剪把每次更新限制住，却同时改变平均方向。证明必须为三个来源付款：裁剪偏差、沿当前误差方向的随机波动、以及镜像势中出现的随机梯度平方和。

只对最后一项噪声做集中还不够。如果把 $\sum\|c_t\|_*^2$ 直接换成它的期望，就仍把一个随机量当成确定上界。式(3)先给这份平方和单独分配失败概率，再给方向噪声分配另一半。两份事件交集才支持式(4)。

原始梯度经裁剪分成偏差、平方和及方向噪声三份账；两个鞅分别占用一半失败概率 — 裁剪并不消除偏差，两份随机账本分别集中

旧SGD已经证明原始 $p$ 阶矩下的裁剪期望界。这里新增的是非欧氏复合更新上的两份条件方差控制，以及显式 $\log(2/\delta)$ 概率预算；不能把期望结论直接更名为95%保证。

例子与边界

一百万次调用，证书由哪些数构成

取单纯形负熵几何的合法上界 $B=\log2,D=2,H=0$ ， $p=3/2,M=1$ ，固定 $T=10^6,\delta=0.05$ 。选择

\tau=M(T/\ell)^{1/p},\qquad \eta=\sqrt{2B/S}.

有 $\ell=\log40\approx3.688879454$ ， $\tau\approx4188.614171$ 、 $v\approx64.719504$ 、 $S\approx199393039.655$ ，步长约 $0.0000833820813$ 。式(4)的五个非零项依次为

来源	上界
初始 Bregman 势	0.0083129033
裁剪平方和	0.0083129033
裁剪偏差	0.0309025855
方向噪声的方差项	0.0437028555
方向噪声的幅度项	0.0412034473

总和约0.1324346950，因此可报告“在所列模型条件下，固定一百万次调用后的平均输出，以至少95%的概率目标差不超过0.132435”。这不是模拟得到的通过率，也没有宣称一百万为最小充分预算。每轮还要一次 Bregman 子问题；若它很贵，查询数不是全部费用。

例如在 $\Delta_2$ 上取 $h=0$ 、线性目标的真次梯度 $(1/2,0)$ ，就有最优顶点、 $B=\log2,D=2$ 。令原始 oracle 为 $(Y,0)$ ， $Y\ge0$ 为满足 $EY=1/2,EY^{3/2}\le1$ 的重尾变量，便落入本模型。可取 Pareto 尾指数 $7/4$ 、尺度 $3/14$ ：其均值为1/2， $3/2$ 阶矩为 $7(3/14)^{3/2}<1$ ，二阶矩却无穷。以上预算因此覆盖一个真正没有二阶矩的模型。

单次更新仍然可以手算

同样在两坐标单纯形， $h=0,x_0=(1/2,1/2)$ ，本次取 $\tau=\log3,\eta=1$ 。如果原始 oracle 恰为 $(100,0)$ ，按 $\ell_\infty$ 裁后是 $(\log3,0)$ ，更新到 $(1/4,3/4)$ ；若下次原始返回 $(0,\log9)$ ，裁后是 $(0,\log3)$ ，更新回均匀点。两轮更新前平均为 $(3/8,5/8)$ 。

这条轨迹展示阈值与输出位置，并未给这两个指定观察值赋予概率。要给它套式(4)，仍需另外指定满足式(1)的完整条件分布，不能从两条观测反推有效的 $M$ 。

哪些条件不能省略

仅有中心矩上界不提供式(1)。例如确定方向恒为100，中心噪声所有矩均为零，但原始 $p$ 阶矩是 $100^p$ ；以中心尺度 $M=1$ 填入式(3)就是错账。若另证 $\|s_t\|_*\le L_f$ ，则由 $(a+b)^p\le2^{p-1}(a^p+b^p)$ ，中心矩上界 $\sigma^p$ 可转换为原始上界 $M^p=2^{p-1}(L_f^p+\sigma^p)$ ；这可能很保守，却需要明确补充梯度规模。

无界域上 $\|x_t-x^*\|$ 不能用固定 $D$ 控制，方向鞅的幅度与方差账本就失效。需要局部化或另一算法，本页未完成那个分支。改变 $T,\tau$ 或根据途中效果选最有利预算，也不是当前固定参数证明自动允许的停止规则。

推论与应用

先做逐点裁剪计算

写 $r=\|g_t\|_*$ 。由 $r\mathbf1_{r>\tau}\le r^p\tau^{1-p}$ 及 $\min(r,\tau)^2\le r^p\tau^{2-p}$ ，

\|\mathbb E[c_t\mid\mathcal F_t]-s_t\|_*\le M^p\tau^{1-p}, \qquad \mathbb E[\|c_t\|_*^2\mid\mathcal F_t]\le v.\tag{5}

令 $W_t=\|c_t\|_*^2$ ， $0\le W_t\le\tau^2$ 。中心化鞅差 $W_t-\mathbb E_tW_t$ 上界为 $\tau^2$ ，条件方差至多 $\mathbb E_tW_t^2\le\tau^2v$ 。对标量 Freedman使用确定方差预算 $T\tau^2v$ 、单步上界 $\tau^2$ 、失败概率 $\delta/2$ ，得到

\sum_{t=0}^{T-1}W_t\le S.\tag{6}

这里 $\mathbb E_t$ 简记给定 $\mathcal F_t$ 的条件期望。定义第二组标量鞅差

Z_t=\langle\mathbb E_tc_t-c_t,x_t-x^*\rangle.

它条件均值为零，绝对值至多 $2D\tau$ ；条件方差等于标量内积的条件方差，因而

\mathbb E_tZ_t^2\le\mathbb E_t\langle c_t,x_t-x^*\rangle^2 \le D^2v.

这一步只对实标量中心化，没有假定一般范数享有 Hilbert 方差分解。再以失败概率 $\delta/2$ 使用 Freedman，得

\sum_tZ_t\le D\sqrt{2Tv\ell}+\frac43D\tau\ell.\tag{7}

两个事件如何接上优化望远镜

复合镜像的一步式对实际输入 $c_t$ 逐路径成立。真实次梯度与输入之差拆为

s_t-c_t=(s_t-\mathbb E_tc_t)+(\mathbb E_tc_t-c_t).

第一项由式(5)及直径界给每轮至多 $DM^p\tau^{1-p}$ ；第二项就是 $Z_t$ 。把一步式求和、保留结构首尾差，再由凸性处理平均输出，得到逐路径不等式

F(\bar x_T)-F^*\le \frac{B}{\eta T}+\frac{\eta}{2T}\sum_tW_t+\frac HT +DM^p\tau^{1-p}+\frac1T\sum_tZ_t.

由并集界，式(6)和式(7)同时成立的概率至少 $1-\delta$ ；代入便证明式(4)。不要求两份事件彼此独立，也不要求梯度跨轮独立，只要求已写出的条件矩。

若令 $\tau=M(T/\ell)^{1/p}$ ，则 $\tau^2\ell=Tv$ ，故 $S=(5/3+\sqrt2)Tv$ 。 $B>0$ 时最优固定步长为 $\sqrt{2B/S}$ ，得到更紧凑的界

F(\bar x_T)-F^*\le M\left(\frac\ell T\right)^{(p-1)/p} \left[\sqrt{\frac{2B(5/3+\sqrt2)}\ell} +D\left(\frac73+\sqrt2\right)\right]+\frac HT.\tag{8}

它显示失败概率通过对数进入，矩越接近1，预算改善越慢。 $p=2$ 时恢复平方根阶；本页常数保守，不主张最优。 $B=0$ 时直接采用任意正步长的式(4)，避免零步长除法。

自测与答案

为什么只证明式(7)不能推出式(4)？答案：镜像势还含随机平方和，必须同时控制式(6)；用其期望代替会遗漏失败事件。
两份事件各给95%保证，合并是否仍是95%？答案：无额外信息时只能保证90%。本页各用97.5%，所以合并得到95%；这正是 $\ell=\log40$ 的来源。

参考资料

Joel A. Tropp，Freedman's Inequality for Matrix Martingales，2011，§1.2 Theorem 1.1 的标量形式。本文分别列出两个鞅差的幅度与条件方差，再使用该尾界
Ta Duy Nguyen、Thien Hang Nguyen、Alina Ene、Huy L. Nguyen，High Probability Convergence of Clipped-SGD Under Heavy-tailed Noise，2023 v2（4月3日），§2 的中心矩 oracle 用于界定更一般问题；本页证明的是有界域、原始矩版本，不引用该文结论来补足未证的局部化

形式陈述 ​

一百万次调用，证书由哪些数构成 ​

单次更新仍然可以手算 ​

哪些条件不能省略 ​

先做逐点裁剪计算 ​

两个事件如何接上优化望远镜 ​

自测与答案 ​