随机几何：方向、输出与概率的三份账 ​

形式陈述 ​

终点是一份能被他人复算的随机优化报告：给出目标、几何、oracle、条件矩、实际输出与完整费用，再说明它认证的是期望还是高概率。本页给出任务及核对答案；下载标准库复算器可检查数字，但不替代模型假设或一般证明。

短核心链为镜像几何理路镜像下降法Mirror descent method · Bregman gradient method用强凸镜像映射生成的 Bregman 几何执行线性化损失更新的约束一阶算法。 → 随机复合更新理路随机复合镜像下降Stochastic composite mirror descent · 随机复合 Bregman 更新在非欧氏几何中分开随机次梯度和精确结构项，证明更新前平均的有限预算界，并计算熵正则单纯形的真实更新。 → 采样预算理路非均匀随机梯度的采样预算Importance-sampled stochastic gradient · 方差感知分量采样为有限和梯度选择可预测的抽样分布，优化可验证的二阶矩上界，并区分调用次数、概率下限和非等价的工作量预算。。已会 Bregman 三点式的读者从第二站开始。条件历史不清时补条件期望理路条件期望Conditional expectation以信息分组的加权平均建立条件期望直觉，再连接测度定义、最小均方预测、塔式性质和可计算反例。；采样最优性用到Cauchy–Schwarz理路Cauchy–Schwarz 不等式Cauchy–Schwarz inequality · 柯西–施瓦茨不等式内积的绝对值不超过两向量范数之积，且等号精确刻画线性相关。和KKT理路KKT 条件Karush–Kuhn–Tucker conditions · KKT conditions用可行性、乘子符号、互补松弛与驻点方程刻画约束最优性的条件。，不必先学整个随机优化器列表。

两条可选深入分支各有独立出口：要求重尾下固定预算95%保证，读Freedman理路标量 Freedman 不等式Scalar Freedman inequality · 可预测方差鞅尾界用有界鞅差及可预测条件方差控制预算内的全时间越界，证明指数过程并给出适应门控与分层方差预算的实际计算。与裁剪镜像理路裁剪随机镜像的高概率保证Clipped stochastic mirror descent · 原始矩裁剪优化证书在有界可行域和原始条件p阶矩下，用两个方差敏感鞅预算共同控制裁剪更新与目标误差，给出固定预算高概率证书。；需要减少昂贵 prox 次数，读随机近端理路随机近端梯度Stochastic proximal gradient · Stochastic forward-backward method对光滑项使用历史条件无偏梯度，对结构项精确做prox，以噪声方差和平均输出建立固定预算保证。、FISTA理路FISTA 复合加速法FISTA · Fast iterative shrinkage-thresholding algorithm以近端主点、外推查询点和递推权重组成复合凸加速，并用势函数而非逐轮下降证明函数值速率。与批量近端加速理路批量随机近端加速的噪声预算Batched accelerated stochastic proximal gradient · 带权批量 FISTA以放大的安全曲率吸收随机位移，证明加速势中的加权噪声和，再分配批量大小以分别认证近端次数与样本梯度成本。。两条分支不互为必修，也不把原有欧氏随机近端重新计算为新知识。

直觉 ​

选择几何决定什么是“大梯度”；选择采样决定这个大梯度出现多频繁；选择平均或最后主点决定最终证明覆盖哪个输出。改变其中一个，另外两份账通常也要重新核对。

概率预算还独立于这三项。一个二阶矩最优分布可以降低期望误差，却不自动提供95%证书；一份重尾高概率证明可以合法，却因常数保守需要很多查询。合格报告应同时让这些结论可见。

例子与边界 ​

核心任务一：熵几何与目标熵正则 ​

在 ${\mathrm{\Delta }}_2$ 上取镜像 $\psi (x)=\sum _i{x}_i\log x_i$，目标 $F(x)=x_1\log 3+\sum _i{x}_i\log x_i$。从 $(1/2,1/2)$ 开始，步长1；oracle 每轮独立等概率取 $(\log 9,0)$、$(0,0)$。若两轮依次看到前者、后者，求两主点、更新前平均、真实目标差，并写出通用期望界的参数。

答案：由于目标结构项也含负熵，更新是

$$x_{t+1,i}\propto \sqrt{x_{t,i}}\exp (-v_{t,i}/2),$$

不是未带结构项的 $x_{t,i}{e}^{-v_{t,i}}$。故

$$x_1=(1/4,3/4),x_2=(1/(1+\sqrt{3}),\sqrt{3}/(1+\sqrt{3})),{\overline{x}}_2=(3/8,5/8).$$

最优点 $(1/4,3/4)$，$F^{\ast }=-\log \left(4/3\right)$，输出的目标差为

$$\frac{3}{8}\log \left(3/2\right)+\frac{5}{8}\log \left(5/6\right)\approx 0.0380984425.$$

通用参数可取 $B=\log 2,G=\log 9,H=0$；$H$ 为零是因为均匀初值最小化结构熵，不是因为所有结构项都可以删去。这条具体路径用了2次随机向量调用和2次 Bregman 子问题。不能把它的误差当成所有路径的最大值。

迁移题：把目标熵正则系数改成 $\lambda =2$，镜像仍不变。首轮看到 $(\log 9,0)$，答案变为

$$x_{1,1}=\frac{1}{1+9^{1/3}}.$$

目标与更新同时改变；若只改镜像而声称目标最优点也变了，就是混淆稳定项与目标项。

核心任务二：选择分量，而不改变原目标 ​

在 $[0,2]$ 上取 $f_i(x)=a_i(x-1{)}^2/2$，$a=(1,1,8)$。采用固定分量包络，给出按调用数最优分布、正确方向、第一步和0.1期望精度的通用充分预算；再把费用改成 $(1,1,25)$。

答案：$G=(1,1,8)$，$p=(1/10,1/10,4/5)$。任意索引都给 $a_i(x-1)/(3p_i)=10(x-1)/3$。从0用步长 $3/20$，首点必为1/2。其目标差为 $5/12$；均匀采样的首点为 $3/20$ 或 $6/5$，期望差 $33/40$。在这个特殊模型，正确分布直接消除了分量方差。

通用包络界仍按 $M=100/9$ 给 $T=1112$；均匀 $M=22$ 给2200。它们返回更新前平均，且步长需按各自 $M,T$ 配平。只使用首步的 $\eta =3/20$ 然后把上述预算照搬，缺少步长条件。

费用改变后，均匀分布的 $MC=198$，调用数最优分布为 $2020/9\approx 224.444$。$p_i\propto G_i/\sqrt{c_i}$ 给 $(5/18,5/18,4/9)$，$M=84/5,C=35/3,MC=196$。因此更少分量调用不必代表更少工作。三个值都只属于固定轮数下的期望费用比较；按实际费用耗尽而停止需另证。

再改包络为 $(0,1,3)$，要求每项概率至少1/10。答案为 $(1/10,9/40,27/40)$，二阶矩上界 $160/81$。第一项占探索下限，其余按1:3分配。一次观测为零与证明其梯度在全域为零不同，不能据前者永远禁止访问。

可选任务三：把原始重尾矩变成95%优化保证 ​

已知 $p=3/2,M=1,B=\log 2,D=2,H=0$，固定一百万次调用、总失败概率0.05。按裁剪页取 $\ell =\log 40$、$\tau =(T/\ell {)}^{2/3}$。请重算平方和预算、步长及五份误差，指出两个鞅各控制什么。

答案：$\tau \approx 4188.614171$、$v\approx 64.719504$，

$$S=Tv+\sqrt{2T{\tau }^{2}v\ell }+2{\tau }^2\ell /3\approx 199393039.655,\eta =\sqrt{2\log 2/S}\approx 0.0000833820813.$$

五项为0.0083129033、0.0083129033、0.0309025855、0.0437028555、0.0412034473，总界0.1324346950。第一份鞅认证 $\sum \Vert c_t{\Vert }_{\ast }^2$，第二份认证 $\sum ⟨E_t{c}_t-c_t,x_t-x^{\ast }⟩$；各用失败概率0.025。裁剪偏差是单独的确定上界，不靠无偏性消失。

一个实际符合“无二阶矩”条件的模型是 $g=(Y,0)$，$Y$ 为尺度 $3/14$、尾指数 $7/4$ 的 Pareto 变量。$EY=1/2$，$E{Y}^{3/2}=7(3/14{)}^{3/2}\approx 0.694365<1$，而 $E{Y}^2=\mathrm{\infty }$。在两坐标单纯形上线性目标仍可由上述固定预算保证覆盖。

边界题：如果只给 $E\Vert g_t-E_t{g}_t{\Vert }_{\ast }^{3/2}\le 1$，能否照用相同数字？答案：不能。确定梯度100的中心噪声为零，却不满足原始矩上界1；要另给真实梯度上界并转换矩，或换用已证明的中心矩算法。无界域的局部化、任意停止也未由本题认证。

可选任务四：prox很贵，如何分配批量 ​

取 $g(x)=(x-1{)}^2/2,h(x)=|x|/2,x_0=0$，单次噪声为独立公平符号；$L=1$，使用 $K=2$ 的加速近端。三批噪声分别为 $(-1)$、$(-1,+1)$、$(-1,+1,+1)$。求第三点和完整费用，再设计 $L=R=\sigma =1,\epsilon =0.1$ 的通用预算。

答案：$x_1=3/4,x_2=5/8$，$\beta =(t_2-1)/t_3\approx 0.281753525$，

$$y_3=5/8-\beta /8,x_3=19/48-\beta /16\approx 0.3782237380.$$

这条路径的目标差约0.0074147290；总调用6，prox3。64条等概率路径的目标差均值约0.0565284807，使用实际 $R=1/2$ 的定理上界约0.4585695388。一个实现值、完整分布平均与最坏期望上界三者不能相互替代。

通用预算取 $T=8$，权重约为

$$1,1.618034,2.193527,2.749791,3.294880,3.832601,4.365079,4.893622.$$

恒等式 $\sum t_k=t_T^2$ 使安全批量简化为 $b_k=\lceil 10t_k\rceil$，得到

$$b=(10,17,22,28,33,39,44,49),N=242.$$

确定项约0.0417579531，带权噪声项约0.0494860922，总界0.0912440453，小于0.1。费用包含8次精确 prox、242次样本梯度与流式累加。若可用样本只有241，计划应报告预算不足，不能把最后一批少做一个却保留242查询方案的账本。

迁移题：保持 $T=8$，把噪声标准差改为2。安全连续批量系数应从10变成40，再向上取整；倍数来自方差变四倍，不是标准差变两倍。若噪声为零，直接每轮一项，仍需8次 prox；若同批只是重复旧噪声，不能享有除以 $b_k$ 的方差缩减。

推论与应用 ​

证明重建：从原始矩到两个方差预算 ​

请不直接引用最后的优化界，重新列出两个鞅差、各自的单步上界、可预测方差总额，以及每份失败概率。为什么不能只集中方向噪声？

答案：令 $W_t=\Vert c_t{\Vert }_{\ast }^2$。裁剪的逐点界给 $E_t{W}_t\le v$、$W_t\le {\tau }^2$，所以 $W_t-E_t{W}_t\le {\tau }^2$，且条件方差不超过 $E_t{W}_t^2\le {\tau }^{2}v$。第一份 Freedman 的总预算是 $T{\tau }^{2}v$。第二份令 $Z_t=⟨E_t{c}_t-c_t,x_t-x^{\ast }⟩$；其幅度至多 $2D\tau$，标量方差不超过 $E_t⟨c_t,x_t-x^{\ast }{⟩}^2\le D^{2}v$，总预算为 $T{D}^{2}v$。每份使用 $\delta /2$，并集界给共同事件。

优化望远镜仍含 $\eta \sum W_t/(2T)$，所以漏掉第一份集中就不能把这个随机平方和换成确定数 $S$。此外还要加偏差 $D{M}^p{\tau }^{1-p}$ 和结构首尾上界 $H/T$；两个中心化鞅都没有支付这两项。

结构迁移：同批样本共享一份冲击 ​

把加速例的单个批内噪声改成 ${\zeta }_{k,j}=A_k+E_{k,j}$。条件于旧历史，$A_k$ 与本批所有 $E_{k,j}$ 独立且均值零，方差分别为 $a^2,s^2$；残差 $E_{k,j}$ 彼此独立，而同批共享一个 $A_k$。求批平均的方差，并判断原批量安排是否仍认证同一精度。

答案：批均值为 $A_k+b_k^{-1}\sum _j{E}_{k,j}$，交叉项为零，所以

$$\mathrm{Var}({\overline{\zeta }}_k\mid {\mathcal{F}}_{k-1})=a^2+s^2/b_k.$$

它不是 $(a^2+s^2)/b_k$。把这一真实方差代入加速势，噪声项变为

$$\frac{1}{2L{t}_T^2}\sum _k{t}_k^2(a^2+s^2/b_k).$$

以 $a^2=s^2=1/2$、单样本总方差仍为1、原8轮批量为例，噪声项约为0.9072708602，已经超过目标0.1；加上确定项后总界约0.9490288133，具体数字可由权重表复算。共同冲击随 $b_k$ 增大不会消失，故原242调用计划没有所声称的认证。可改变采样协议，使每个样本有独立冲击；或者保留模型但重新分配外轮和误差预算。仅复制记录并声称批量更大不能修复它。

复算器能做和不能做什么 ​

下载文件仅依赖 Python 标准库，不读取网络或私人数据，也不实际训练优化器。运行 python foundations-stochastic-geometry-checker.py examples 可重算分数表、熵目标差及64路径枚举；使用 accelerated --epsilon 0.1 生成批量；使用 clipped 计算默认重尾预算。参数帮助由 --help 给出。成功算术的进程退出码为0，预算不足为1，无效输入或精度未解决为2；先输出 JSON 状态再退出，便于脚本识别失败。

采样表用精确分数；含对数、平方根的示例是浮点算术。批量计划用两档 Decimal 精度核对整数计划，若不一致返回 precision_unresolved；即使一致，也明确标记不是区间算术证书。它不通过有限观察验证条件矩、全程包络或直径，亦不把小数计算等同于原理证明。

accelerated --max-oracle 241 返回 budget_exhausted；极小精度请求超过允许外轮数时，在遍历巨大计划前也返回预算不足。输入负精度、非法失败概率或非有限数字会报告无效输入。把这些状态改名为“收敛”会抹去任务最关键的信息。

最后的报告检查 ​

• 原始矩、中心矩、对偶范数和可行域上界分别是什么，依据在哪里
• 概率表何时确定，是否严格覆盖所需分量，分母是否使用实际概率
• 输出是更新前平均、更新后平均，还是最后加速主点
• 调用、子问题、包络初始化、表维护及独立证书是否分别计费
• 声明属于期望、固定预算高概率，还是实际点的可行 gap

泛化与统计恢复仍需额外条件。这里的优化误差可以交给近似 ERM 的误差分解理路近似 ERM 与优化误差approximate ERM · optimization error刻画训练目标未被精确最小化时，经验次优量如何进入总体超额风险。，但先要使概率含义一致：期望0.1不能直接代入一个要求95%事件成立的风险界。

参考资料 ​

• 本页四个新知识页包含完整证明、明确条件、原始来源和迁移边界
• Bubeck 2015 的随机镜像与小批量、Zhao–Zhang 2015 的重要性梯度、Tropp 2011 的标量 Freedman，以及 Schmidt–Le Roux–Bach 2011 的加速误差分析提供来源校准；本单元的具体变体与常数均在对应正文独立展开