非均匀随机梯度的采样预算

形式陈述

固定 $f(x)=n^{-1}\sum_{i=1}^n f_i(x)$ ，每个 $f_i$ 凸，允许按索引查询一个选定次梯度 $a_i(x)\in\partial f_i(x)$ 。当前点 $x_t$ 与概率向量 $p_t$ 都由本轮查询前的历史 $\mathcal F_t$ 决定。抽 $I_t$ ，满足 $\Pr(I_t=i\mid\mathcal F_t)=p_{t,i}>0$ ，并返回

v_t=\frac{a_{I_t}(x_t)}{np_{t,I_t}}.\tag{1}

各分量可微时，这是随机梯度 oracle的一种实现。本文还允许次梯度，其优化保证由同样的投影次梯度距离证明或复合镜像接口得到。有限求和直接给

\mathbb E[v_t\mid\mathcal F_t]=\bar a(x_t):=\frac1n\sum_i a_i(x_t)\in\partial f(x_t), \qquad \mathbb E[\|v_t\|_*^2\mid\mathcal F_t] =\frac1{n^2}\sum_i\frac{\|a_i(x_t)\|_*^2}{p_{t,i}}.\tag{2}

第二式对任意范数都成立，因范数齐次。在欧氏范数下，中心化方差还等于式(2)右侧减 $\|\bar a(x_t)\|_2^2$ ；一般非欧氏范数不能这样相减。本页优化的是式(2)的二阶矩，不把欧氏方差恒等式推广到任意范数。

若有对整个允许轨道有效的确定包络 $G_i\ge\|a_i(x)\|_*$ ，定义

M(p)=\frac1{n^2}\sum_i\frac{G_i^2}{p_i}. \tag{3}

当所有 $G_i>0$ 时，固定调用次数下最小化此上界的分布为

p_i^{\rm env}=\frac{G_i}{\sum_jG_j}, \qquad M_* =\frac{(\sum_iG_i)^2}{n^2}.\tag{4}

输出概率表、包络依据、抽样及重加权规则、所用步长和预算。包络无效、概率为零而该项可能非零、或实际分布不等于记录值时，不能输出式(3)的认证。

直觉

频繁读取可能贡献大的分量，可以减少它在稀有出现时需要的放大倍数。但无偏性与低方差是两件事：任何严格正的历史可测 $p_t$ 都保留式(1)的均值，只有与实际梯度规模匹配的分布才可能改善波动。

“按当前梯度范数最优抽样”若需要先计算所有 $n$ 项梯度，就已经花了一次整梯度预算。可验证包络提供可复用的替代；它最小化的是上界，不保证在每一个当前点都最小化真实方差。根据旧查询更新分布仍可无偏，但旧梯度大小不自动是新点的上界。

三个梯度规模与对应采样概率将不等大的原分量变成相同的重加权方向；下方另列非等价的分量费用 — 二阶矩最小与费用最小是不同预算

旧重要性采样已有静态标量积分的理想提议；这里新增的是自适应迭代前可预测性、范数包络、支持下限以及优化调用预算。SVRG已有同索引差分的无偏修正；它的方差随误差消失机制没有被本页普通分量 oracle 取代。

例子与边界

三个二次分量：采样如何真正改变下一步

在 $C=[0,2]$ 上取 $f_i(x)=a_i(x-1)^2/2$ ， $a=(1,1,8)$ ，从 $x_0=0$ 开始。平均目标为 $f(x)=5(x-1)^2/3$ ，最优点1。合法包络 $G=(1,1,8)$ 来自 $|x-1|\le1$ ；无界参数域上没有这份全程界。

均匀抽样时 $M=22$ ；式(4)给 $p=(1/10,1/10,4/5)$ 和 $M=100/9$ 。在任何当前点，重新加权的方向都恰为 $v=10(x-1)/3$ ，所以这个特殊共线模型的真实方差为零。它仍有非零二阶矩，反映真实梯度尚未消失。

取 $\eta=3/20$ ，第一步必到 $x_1=1/2$ 。均匀抽样的第一步却以概率 $2/3$ 到 $3/20$ 、以概率 $1/3$ 到 $6/5$ ；其均值同样为 $1/2$ 。两种第一步的期望目标差分别为 $5/12$ 和 $33/40$ 。相同平均点不能消除随机输出的目标损失。

若只使用通用投影 SGD 界， $B=|x_0-x^*|^2/2=1/2$ ，固定 $T$ 并配平步长，则更新前平均的期望差不超过 $\sqrt{M/T}$ 。要求不超过0.1，均匀方案的充分预算是2200次，包络方案是1112次。这个保守证明未利用本例方向逐点相同的额外结构；实际轨迹可更快，但不能把实际速度写成一般定理。

同样的分量有不同费用

设三个查询费用是 $c=(1,1,25)$ 。固定运行 $T$ 轮，预期工作量为 $T C(p)$ ，其中 $C(p)=\sum_i c_ip_i$ 。若比较大预算下由式(3)产生的“二阶矩乘预期每轮费用”，三种选择为

分布	$M(p)$	$C(p)$	$M(p)C(p)$
均匀	22	9	198
调用数最优 $(1/10,1/10,4/5)$	$100/9$	$101/5$	$2020/9$
乘积最优 $(5/18,5/18,4/9)$	$84/5$	$35/3$	196

调用数最优者更频繁读取昂贵分量，工作量乘积反而大于均匀方案。第三行来自 $p_i\propto G_i/\sqrt{c_i}$ ，推导见下节。它最小化所列上界乘积；并非证明任意实际运行时间、缓存策略或并行平台都由它最优。

尤其，按固定总费用“钱用完就停”会产生随机停时与不同输出长度，本页的固定 $T$ 平均证明没有分析它。严格路径费用可先用 $T\max_i c_i$ 预留；若只报 $TC(p)$ ，必须标明是期望费用。初始化包络、构造采样表及维护表的费用另计。

支持遗漏和包络错误

若 $f_1(x)=0,f_2(x)=(x-1)^2/2$ ，却因初始看到第一项为零就一直设置 $p_2=0$ ，从0可永远不动，而平均目标在0的误差为1/4。只有证明某分量梯度在全部相关点恒零，才可省去它；一次观察为零不够。

光滑常数 $L_i$ 加上 $\|x\|\le R$ 只能推出

\|\nabla f_i(x)\|_*\le\|\nabla f_i(0)\|_*+L_iR

（这里 $L_i$ 的范数配对须明确），不能无条件去掉第一项。例如 $f_i(x)=x^2/2+100x$ 在 $x=0$ 梯度为100，虽然 $L_i=1$ 。包络必须由具体函数和域证明，而非只复制曲率名称。

推论与应用

为什么式(4)最优，以及下限如何改变答案

由Cauchy–Schwarz 不等式，

\left(\sum_iG_i\right)^2 =\left(\sum_i\frac{G_i}{\sqrt{p_i}}\sqrt{p_i}\right)^2 \le\sum_i\frac{G_i^2}{p_i}.

所有 $G_i>0$ 时等号条件恰为 $p_i\propto G_i$ ，给出式(4)。若某些 $G_i=0$ 、仍要求所有概率严格正，无下限问题可能只有下确界而无取得最小值的正分布。全零时整个 oracle 为零，应直接按零方向处理。

实际可预设探索下限 $p_i\ge\rho/n$ ， $0<\rho<1$ 。有非零包络时，KKT 条件给出唯一的概率表

p_i=\max\{\rho/n,G_i/c\},\qquad \sum_i\max\{\rho/n,G_i/c\}=1.\tag{5}

证明是对 $G_i^2/p_i$ 写站立式：未触及下限的项满足 $-G_i^2/p_i^2+\nu=0$ ，故 $p_i=G_i/\sqrt\nu$ ；触及下限的项由互补条件固定。令 $c=\sqrt\nu$ ，连续单调方程可二分求解。它的算法容差应同时检查概率和与下限，不能把未归一化数表直接送入抽样器。 $\rho=1$ 时只有均匀分布。

例如 $G=(0,1,3),n=3,\rho=3/10$ ，零项占下限 $1/10$ ，其余按1:3分配，得 $(1/10,9/40,27/40)$ ， $M=160/81$ 。任意满足下限的分布都有 $M(p)\le\sum_iG_i^2/(n\rho)$ ；这是安全兜底，并非最优常数。

从采样表转成优化与费用证明

把式(3)代入投影 SGD 的距离势，或代入复合镜像的式(3)，可得

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

这是先证 oracle，再用相应算法的望远镜；没有把修改采样当成自动改变收缩定理。若每轮 $p_t$ 改变，只要抽样前可测且 $M(p_t)\le\overline M$ 几乎处处，就可把 $M(p)$ 换成 $\overline M$ 。若只有各轮确定上界 $M_t$ ，第二项换成 $\eta\sum_tM_t/(2T)$ 。

对正费用 $c_i$ ，再次用 Cauchy–Schwarz，

\left(\sum_i\frac{G_i^2}{p_i}\right) \left(\sum_i c_ip_i\right) \ge\left(\sum_iG_i\sqrt{c_i}\right)^2.

等号要求 $p_i\propto G_i/\sqrt{c_i}$ ，证明费用乘积的最优候选。零包络和探索下限需另做受约束优化，不能直接沿用这个等号分布。固定 $T$ 时式(6)和 $TC(p)$ 都严格有效；以二者近似消去 $T$ 还涉及取整及初始费用，应保留这些实际项。

固定表可用累计概率二分采样，每次 $O(\log n)$ ；别名表初始化 $O(n)$ 后每次 $O(1)$ ，但重建表仍要付费。查询一个分量也可能输出 $d$ 维稠密向量，重加权与外层更新不是必然常数时间。

自测与答案

二分量梯度为 $(-1,3)$ ，取 $p=(1/4,3/4)$ ，加权方向及欧氏方差是多少？答案：方向为 $-2,2$ ，均值1，二阶矩4，方差3；均匀抽样方差4。相反符号使其不能像同向例那样变成零方差。
用过去的梯度估计来选择正概率表，是否一定有偏？答案：不是；只要实际抽样条件分布与记录的 $p_t$ 一致，式(1)仍无偏。但过去大小不是自动有效的包络，低方差及式(6)中的数值常数需另证。

参考资料

Peilin Zhao、Tong Zhang，Stochastic Optimization with Importance Sampling for Regularized Loss Minimization，ICML 2015，§3.1.1、式(4)–(6)，梯度范数及包络分配。本文独立区分一般范数二阶矩与欧氏方差，并保留非零参考梯度项
Stephen Boyd、Lieven Vandenberghe，Convex Optimization，§5.5.3 的 KKT 充分条件；式(5)及费用乘积在本文完整推导

形式陈述 ​

三个二次分量：采样如何真正改变下一步 ​

同样的分量有不同费用 ​

支持遗漏和包络错误 ​

为什么式(4)最优，以及下限如何改变答案 ​

从采样表转成优化与费用证明 ​

自测与答案 ​

反向链接