AdaGrad 对角自适应梯度法

形式陈述

AdaGrad用已经观察到的梯度调整后续更新的尺度。下面固定可完全展开的对角、盒约束版本。设决策集

C=\prod_{i=1}^d[\ell_i,r_i],\qquad -\infty<\ell_i\le r_i<\infty,

坐标宽度 $D_i=r_i-\ell_i$ 。在在线凸优化协议中，先选择 $x_t\in C$ ，再看到本轮凸损失 $f_t$ 及一个有限次梯度 $g_t\in\partial f_t(x_t)$ 。给定 $x_1\in C$ 、 $\eta>0$ 和正的平滑常数 $\delta>0$ ，初始化 $s_{0,i}=0$ ；每轮执行

s_{t,i}=s_{t-1,i}+g_{t,i}^2,\qquad a_{t,i}=\sqrt{\delta^2+s_{t,i}},

x_{t+1,i}=\operatorname{clip}_{[\ell_i,r_i]} \left(x_{t,i}-\eta\frac{g_{t,i}}{a_{t,i}}\right).\tag{1}

这里的 $\delta$ 是分母平滑常数，不是失败概率。本页采用平方根内部加 $\delta^2$ 的约定；软件中也常见根号外加常数，二者的数值轨迹与精确界应分别计算。

每轮使用一个当前梯度，累计 $T$ 轮共 $T$ 次查询；更新累积平方、缩放和盒投影需 $O(d)$ 算术、 $O(d)$ 状态。若 $D_i=0$ ，该坐标始终固定；若某坐标梯度一直为零，其分母仍为 $\delta$ ，不会发生 $0/0$ 。梯度、平方和或更新出现非有限数时应报告数值失败。

适用于每一条已观察路径的保证

对任意固定比较器 $u\in C$ ，式(1)满足

\sum_{t=1}^T[f_t(x_t)-f_t(u)] \le\sum_{i=1}^d\left[ \frac{D_i^2a_{T,i}}{2\eta}+\eta(a_{T,i}-\delta)\right].\tag{2}

无需假设损失或梯度独立，也不需要在运行前知道梯度幅度或预算 $T$ 。如果某个坐标宽度为零，它对真正遗憾的贡献为零，可以直接从右侧和中删去；保留它只得到更松的上界。

若 $D_i\le D$ ， $D>0$ ，取 $\eta=D/\sqrt2$ ，可简化为

\operatorname{Reg}_T\le\sqrt2D\sum_i\sqrt{\delta^2+\sum_{t=1}^Tg_{t,i}^2}.\tag{3}

若整个盒只有一个点，所有遗憾为零，直接返回该点即可，不使用含正宽度的调参公式。

直觉

每个坐标有自己的历史刻度。经常出现大梯度的方向，其分母增长快，后续单次移动变小；长期很少出现的方向保留较大的有效步长。因此方法会根据实际坐标活动分配移动幅度。

这并不意味着所有坐标上的小梯度都应无限放大。正的 $\delta$ 控制初期尺度，盒投影限制可行移动。若坐标系发生旋转，哪些分量看起来稀疏也会变化；对角AdaGrad依赖所选坐标，并不是一个对任意旋转都不变的几何规则。

例子与边界

时变尺度不能直接望远镜消去

固定一个坐标，简记 $a_t=a_{t,i}$ 、 $z_t=x_{t,i}-u_i$ 。区间投影不增到可行比较器的距离，故

g_{t,i}z_t\le\frac{a_t}{2\eta}(z_t^2-z_{t+1}^2) +\frac{\eta g_{t,i}^2}{2a_t}.\tag{4}

求和时 $a_t$ 随时间变化，必须保留额外项：

\sum_{t=1}^T a_t(z_t^2-z_{t+1}^2) =a_1z_1^2+\sum_{t=2}^T(a_t-a_{t-1})z_t^2-a_Tz_{T+1}^2 \le D_i^2a_T.

因为 $a_t$ 单调不减，且 $|z_t|\le D_i$ 。另一方面， $a_t^2-a_{t-1}^2=g_{t,i}^2$ 、 $a_0=\delta$ ，所以

\frac{g_{t,i}^2}{a_t} =(a_t-a_{t-1})\frac{a_t+a_{t-1}}{a_t} \le2(a_t-a_{t-1}).

第二项真正望远镜求和为 $2(a_T-\delta)$ 。将这两条界代入式(4)，再对坐标求和；凸次梯度不等式 $f_t(x_t)-f_t(u)\le\langle g_t,x_t-u\rangle$ 给出式(2)。这说明改变尺度的代价已被实际计入，而不是把固定步长证明换个符号。

两次更新和一条稀疏预算比较

取二维盒 $[-2,2]^2$ 、 $x_1=(0,0)$ 、 $\eta=\delta=1$ ，两轮线性损失的梯度为 $g_1=(3,0)$ 、 $g_2=(0,4)$ 。第一轮累积平方 $(9,0)$ ，分母 $(\sqrt{10},1)$ ，故

x_2=(-3/\sqrt{10},0).

第二轮累积平方 $(9,16)$ ，分母 $(\sqrt{10},\sqrt{17})$ ，故

x_3=(-3/\sqrt{10},-4/\sqrt{17}).

两步都在盒内，无需截断。累计在线损失为0；最优固定比较器 $(-2,-2)$ 的两轮总损失为 $-14$ ，实际遗憾为14。式(2)给上界 $9(\sqrt{10}+\sqrt{17})-2\approx63.57$ ，说明它是保证而非逐例等式。

再比较相同100次查询、相同100维盒 $[-1,1]^{100}$ 。若每轮梯度都为第一个单位向量 $e_1$ ，取 $D=2,\delta=0.001$ ，式(3)给

2\sqrt2[\sqrt{100.000001}+99\cdot0.001]\approx28.56.

使用整个盒的欧氏直径 $20$ 和每步梯度范数1，普通固定步长OGD的已知预算界为 $20\sqrt{100}=200$ 。这里对角界利用了只有一个坐标活动，而不是从100维付相同的几何费用。

如果100轮依次各触发一个不同坐标，同一AdaGrad上界约为282.84，比这个OGD界更松。所谓稀疏优势要看整个时间序列的坐标能量分布；单独每轮只有一个非零分量，不足以保证严格改善。一般地，Cauchy–Schwarz给 $\sum_i\sqrt{\sum_tg_{t,i}^2}\le\sqrt{d\sum_t\|g_t\|^2}$ ，表明集中与分散的两种极端。

当前梯度参与缩放，会改变条件期望

在一个点上，让随机梯度以概率 $3/4$ 取 $-1$ 、以概率 $1/4$ 取3，其条件均值为0。若历史平方和为0、 $\delta=1$ ，本轮缩放方向的条件均值为

\frac34\frac{-1}{\sqrt2}+\frac14\frac3{\sqrt{10}} =\frac34(1/\sqrt{10}-1/\sqrt2)<0.

因此“原梯度无偏”不意味着“按当前梯度调步长后的方向仍无偏”。这不推翻式(2)：它先对每条路径控制 $\sum\langle g_t,x_t-u\rangle$ ，并未在证明中把随机有效步长提出条件期望。

推论与应用

从在线保证到随机优化

若 $f_t(x)=\ell(x,Z_t)$ ，每个损失对 $x$ 凸， $Z_t$ 为新鲜IID样本，并且 $x_t$ 只使用过去，则Online-to-Batch转换将式(2)的期望右侧除以 $T$ ，变成平均输出 $\bar x=T^{-1}\sum_{t=1}^Tx_t$ 的期望总体超额风险界。更新时使用本轮梯度计算 $a_t$ 没有破坏这个步骤，因为被评价的是看本轮样本之前的 $x_t$ 。

例如有确定条件界 $E[g_{t,i}^2\mid\text{过去}]\le G_i^2$ ，平方根的凹性给

E\sqrt{\delta^2+\sum_tg_{t,i}^2}\le\sqrt{\delta^2+TG_i^2},

故式(3)转成

E[F(\bar x)-F(u)]\le\frac{\sqrt2D}{T}\sum_i\sqrt{\delta^2+TG_i^2}.

比较器 $u$ 固定且相关损失可积；若最优点存在可取它。重复使用固定训练集时，应改为条件于该数据的经验目标，不能把同一个证明直接称作总体泛化界。

本页的保证需要凸损失、有限坐标范围和准确的盒投影。无约束深度网络、指数遗忘二阶矩的Adam、额外动量以及任意矩阵预条件，都改变了分析对象。它们不是式(1)的同义实现。

参考资料

John Duchi、Elad Hazan、Yoram Singer，Adaptive Subgradient Methods for Online Learning and Stochastic Optimization，JMLR 12，2011，§3、Algorithm 1与Theorem 5，逐坐标自适应几何及路径式界。本文为盒约束、根号内平滑的对角版本，自行完整推导式(2)而不混用不同正则化约定的常数

形式陈述 ​

适用于每一条已观察路径的保证 ​

时变尺度不能直接望远镜消去 ​

两次更新和一条稀疏预算比较 ​

当前梯度参与缩放，会改变条件期望 ​