返回论文笔记资料库
arXiv 2018ICML 2018优化器论文笔记

Shampoo

护发之前

原始论文

Shampoo: Preconditioned Stochastic Tensor Optimization

论文作者

Vineet Gupta · Tomer Koren · Yoram Singer

发表版本
ICML 2018会议
arXiv 首次提交
arXiv:1802.09568
引用此论文 · BibTeX

引用信息对应所链接的论文版本,作者为原论文作者。

@misc{optimizersshampoo2018,
  title = {{Shampoo: Preconditioned Stochastic Tensor Optimization}},
  author = {Vineet Gupta and Tomer Koren and Yoram Singer},
  year = {2018},
  eprint = {1802.09568},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1802.09568}
}
本页内容

这篇论文的名字,藏在第 2 页的一个脚注里,「We call it Shampoo because it has to do with preconditioning.」

conditioner 是护发素,preconditioning 就是「护发之前」,那当然是洗发水。致谢里还特别感谢 Roy Frostig 想出了这个名字。

玩笑归玩笑,论文要处理的是一个很实际的麻烦。优化器如果想看清楚参数之间怎么互相牵动,就得维护一个「参数数量平方」大小的矩阵;Google Brain 的 Vineet Gupta、Tomer Koren 与 Princeton 的 Yoram Singer 想找一个办法,让这个矩阵不用真的存下来。

定义问题

预条件在做什么

最朴素的梯度下降,每个参数都用同一个学习率往梯度的反方向走。预条件方法在走之前,先拿一个矩阵乘一下梯度:

wt+1=wt−η Ht−1gtw_{t+1} = w_t - \eta\, H_t^{-1} g_t

HtH_t 如果是对角矩阵,效果就是每个参数各自缩放步长,Adam、AdaGrad 都属于这一类。HtH_t 如果是完整的矩阵,它还能把梯度「转个方向」。当损失地形是一条斜着的狭长山谷,两个参数必须一起动才能沿谷底前进,对角矩阵只能分别缩放两个坐标轴,完整矩阵才能把那条斜谷转正。

full-matrix AdaGrad 太大了

AdaGrad 有一个完整矩阵的版本,预条件是累积梯度外积的平方根:

Ht=(∑s=1tgsgs⊤)1/2H_t = \Big(\sum_{s=1}^{t} g_s g_s^\top\Big)^{1/2}

理论性质比对角版好,但没人用得起。拿一个 1024×10241024 \times 1024 的全连接层来算,展平后有 220≈1052^{20} \approx 105 万个参数,HtH_t 就是 220×2202^{20}\times 2^{20},约 1.1×10121.1\times10^{12} 个元素,单精度要 4 TB 以上;每次还要对它开根号再求逆,计算量是 O(m3n3)O(m^3n^3)。

当时的出路有几条。对角近似便宜,但参数之间的相关性全部丢掉;sketch 或其他估计方法,作者评为「seldom practical at large scale」。K-FAC 也用 Kronecker 分解,但它近似的是 Fisher 矩阵,要从模型的预测分布采样,还依赖前馈网络的反向传播结构,换一个架构就得重新推导。

神经网络的参数本来就是矩阵与张量。全连接层是 m×nm\times n,卷积核是四维。这篇的问题是,能不能保留这个形状,用几个小矩阵去近似那个巨大的预条件?

解决问题

左右各一个

在矩阵情形下,Shampoo 为一个 m×nm\times n 的权重矩阵维护两个预条件,左边 m×mm\times m、右边 n×nn\times n(Algorithm 1):

Lt=Lt−1+GtGt⊤Rt=Rt−1+Gt⊤GtWt+1=Wt−η Lt−1/4 Gt Rt−1/4\begin{aligned} L_t &= L_{t-1} + G_t G_t^\top \\ R_t &= R_{t-1} + G_t^\top G_t \\ W_{t+1} &= W_t - \eta\, L_t^{-1/4}\, G_t\, R_t^{-1/4} \end{aligned}

初始值是 L0=ϵImL_0=\epsilon I_m、R0=ϵInR_0=\epsilon I_n。GtGt⊤G_tG_t^\top 累积的是各「行」之间的相关性,对全连接层来说是输出单元之间;Gt⊤GtG_t^\top G_t 累积的是各「列」之间,也就是输入特征之间。更新时,梯度从左边乘一次、右边乘一次。

同样那个 1024×10241024\times1024 的层,LL 与 RR 加起来是 2×220≈2102\times 2^{20}\approx 210 万个元素,单精度 8 MB。内存从 m2n2m^2n^2 降到 m2+n2m^2+n^2,算矩阵次方的成本从 O(m3n3)O(m^3n^3) 降到 O(m3+n3)O(m^3+n^3)。

这两个小矩阵其实就是一个大矩阵的伪装。论文的 Lemma 4 给出 Kronecker 积的恒等式,把 L−1/4GR−1/4L^{-1/4} G R^{-1/4} 展平后,等于 (L1/4⊗R1/4)−1\big(L^{1/4}\otimes R^{1/4}\big)^{-1} 乘上展平的梯度。所以 Shampoo 等于在用一个 mn×mnmn\times mn 的预条件 Ht=Lt1/4⊗Rt1/4H_t = L_t^{1/4}\otimes R_t^{1/4},只是这个矩阵从头到尾都没有被组装出来。

写成代码,一个矩阵参数的更新就这几行:

python
import torch

def matrix_power(A, p):
    """对称正定矩阵的 p 次方:特征分解后只对特征值取次方"""
    lam, Q = torch.linalg.eigh(A)
    return Q @ torch.diag(lam ** p) @ Q.T

class ShampooMatrix:
    """Algorithm 1:为一个 m×n 的权重矩阵做 Shampoo"""
    def __init__(self, m, n, lr, eps=1e-4):
        self.L = eps * torch.eye(m)   # L_0 = εI_m
        self.R = eps * torch.eye(n)   # R_0 = εI_n
        self.lr = lr

    @torch.no_grad()
    def step(self, W, G):
        self.L += G @ G.T             # 累积 m×m 的左统计量
        self.R += G.T @ G             # 累积 n×n 的右统计量
        W -= self.lr * matrix_power(self.L, -0.25) @ G @ matrix_power(self.R, -0.25)

论文自己的实现用的是 TensorFlow,矩阵次方用 SVD 算,做法相同。

为什么是 1/4

AdaGrad 开根号,所以指数应该是 −1/2-1/2 才对?Shampoo 用的却是 −1/4-1/4,而且左右各一次。

答案在 Lemma 8。假设每一步的梯度矩阵秩不超过 rr,作者证明:

ϵImn+1r∑tgtgt⊤  ⪯  (ϵIm+∑tGtGt⊤)1/2⊗(ϵIn+∑tGt⊤Gt)1/2\epsilon I_{mn} + \frac{1}{r}\sum_t g_t g_t^\top \;\preceq\; \Big(\epsilon I_m + \sum_t G_tG_t^\top\Big)^{1/2} \otimes \Big(\epsilon I_n + \sum_t G_t^\top G_t\Big)^{1/2}

左边是 full AdaGrad 的统计量。证明分两步。先分别证出 1rgg⊤⪯Im⊗G⊤G\frac1r gg^\top \preceq I_m\otimes G^\top G 和 1rgg⊤⪯GG⊤⊗In\frac1r gg^\top \preceq GG^\top\otimes I_n,也就是左右各有一个上界;再用矩阵几何平均的单调性,把两个上界各取 1/21/2 次方相乘。第一个 1/21/2 就是从这里来的。

AdaGrad 的预条件还要对统计量开一次根号。开根号在半正定矩阵上保持顺序,两边同取 1/21/2 次方,就得到

(∑tgtgt⊤)1/2⪯r (Lt1/4⊗Rt1/4)\Big(\sum_t g_tg_t^\top\Big)^{1/2} \preceq \sqrt{r}\,\big(L_t^{1/4}\otimes R_t^{1/4}\big)

所以 1/4=1/2×1/21/4 = 1/2\times 1/2,一半来自几何平均,一半来自 AdaGrad 的平方根。Shampoo 的 HtH_t 是一个盖在 full AdaGrad 预条件上方的 Kronecker 结构矩阵。作者特别指出,full-matrix 预条件中最影响预条件效果的那些小特征值,不会因为这个近似而消失。

论文另外给了一个直觉,这个指数让整体步长以 O(1/t)O(1/\sqrt{t}) 衰减,正是随机优化中常见的速率。梯度大小稳定时,LtL_t 和 RtR_t 大致随步数 tt 线性增长,L−1/4L^{-1/4} 和 R−1/4R^{-1/4} 各贡献 t−1/4t^{-1/4},合起来刚好是 t−1/2t^{-1/2}。

这个 1/41/4 是证明里上界的产物。后来的实现把指数开放成可调,常改用 1/21/2,讨论部分再回来看。

张量版本

卷积核是四维的。Shampoo 的一般形式(Algorithm 2)为张量的每一维 ii 维护一个 ni×nin_i\times n_i 的预条件 HtiH^i_t,统计量是把梯度沿其他所有维收缩后得到的矩阵;更新时逐维乘上 (Hti)−1/2k(H^i_t)^{-1/2k},kk 是张量的阶数。矩阵 k=2k=2,回到 −1/4-1/4。

原论文 Figure 1:一个 3×4×5 的梯度张量 G(黄色立方体),三个方向各配一个预条件矩阵,分别是蓝色的 L、红色的 U 与绿色的 R,每个矩阵只负责一维。
原论文 Figure 1(Gupta 等人),取自 PDF 第 2 页,arXiv 许可,学术引用。

拿论文 CIFAR-100 实验里最大的卷积核 (256,3,3,256)(256, 3, 3, 256) 来算,它有 589,824 个参数,full AdaGrad 的预条件约 3.5×10113.5\times10^{11} 个元素;Shampoo 只需要四个矩阵,2562+32+32+2562=131,090256^2+3^2+3^2+256^2 = 131{,}090 个元素,指数是 −1/8-1/8。

收敛保证与它的条件

理论在在线凸优化框架下证明(Theorem 7)。梯度秩不超过 rr 时,regret 上界是

∑t=1Tft(Wt)−∑t=1Tft(W⋆)≤2r D Tr(LT1/4) Tr(RT1/4)\sum_{t=1}^{T} f_t(W_t) - \sum_{t=1}^{T} f_t(W^\star) \le \sqrt{2r}\,D\,\mathrm{Tr}\big(L_T^{1/4}\big)\,\mathrm{Tr}\big(R_T^{1/4}\big)

DD 是迭代过程中 WtW_t 与最优解距离的最大值。若梯度的谱范数不超过 1,两个 trace 各以 T1/4T^{1/4} 增长,总 regret 是 O(T)O(\sqrt{T}),在在线凸优化里已经是最好的速率。张量版本(Theorem 10)同理,rr 换成各维秩的几何平均。

条件要读清楚。损失必须是凸的;DD 可能随 TT 变大,要让它有界,得在每一步把 WtW_t 投影回一个球里,而这个投影要用 (Lt,Rt)(L_t, R_t) 诱导的范数,计算很贵,作者便在算法里省略了它,接受一个「slightly looser」的界。深度网络不是凸的,这组证明是算法的出处和动机,实验才是它在神经网络上的证据。

落地时的妥协

实现上有两个取舍。每个参数张量各自处理,整体是 block-diagonal 的预条件,不同层之间的相关性直接忽略。某一维太大时(实验中的阈值约 1200),那一维自动改用对角版本(附录 A 的 Algorithm 3),只存对角元素。另外,实验时再加两个启发式调整,矩阵根每 20 到 100 步才重算一次,以及系数 0.9 的梯度动量;作者说前者对准确率「almost no impact」。

讨论

实验规模很小

所有实验的批量大小都是 128,预条件用整个 batch 的平均梯度更新。图像分类用 CIFAR-10 上 2.4M 参数的 32 层 ResNet 和 1.65M 参数的小型 Inception,CIFAR-100 上 13.5M 参数、不含 BatchNorm 的 55 层 ResNet;每个优化器在 0.01 到 10 之间扫 10 个学习率。这部分论文只画了训练损失曲线,没有测试准确率的对照表。

语言模型是 LM1B 上 9.8M 参数的 Attention 模型,最大的张量是 (2000,256)(2000, 256)。

原论文 Figure 4:LM1B 上 Attention 模型的测试 log-perplexity 对训练步数,横轴到 5×10^5 步。红色 Shampoo 从一开始就最低,最后约 4.18;绿色 AdaGrad 慢慢降到约 4.24;黑色 Momentum 停在约 4.37;蓝色 Adam 停在约 4.5。
原论文 Figure 4(Gupta 等人),取自 PDF 第 14 页,arXiv 许可,学术引用。

红线从第一个点开始就在最下面,到 50 万步时约 4.18,绿色的 AdaGrad 约 4.24,黑色的 Momentum 约 4.37,蓝色的 Adam 很早就停在 4.5 附近。

这张图的比较条件不对称。Shampoo 直接用默认学习率 η=1.0\eta=1.0,其他方法「explored various different settings」,但论文没有列出 Adam 扫过哪些值。Adam 在 Attention 模型上落后 AdaGrad 一大截,本文的推论是,这和后来 Transformer 普遍用 Adam 训练的经验不太一致,差距很可能来自调参的不对称,读这张图时要把这一点考虑进去。

每一步多花多少

论文用一张每秒步数的表回应「矩阵运算会不会太慢」(Tesla K40,批量 128):

实验SGDShampoo比值
ResNet-32(C10)2.1842.15198%
Inception(C10)3.6383.50696%
ResNet-55(C100)1.2101.249103%
Attention(LM1B)4.9193.50971%

整理自原论文 Table 1,比值为本文计算;Adam、AdaGrad 的数字与 SGD 相近,表中省略。

卷积网络上几乎没差,ResNet-55 甚至比 SGD 快一点。LM1B 的每秒步数只剩 SGD 的 71%,论文没有分析原因;这个模型最大的张量是 (2000,256)(2000, 256),按实验用的约 1200 阈值,2000 那一维会改走对角版本。这组数字是在模型只有几百万参数、根每 20 到 100 步算一次的条件下测的。

后来的 Shampoo

2018 年的原版离大规模训练还很远。后面两个版本做的主要是工程。

Anil 等人(2020)的 Distributed Shampoo。 作者群包含原论文的三位作者,论文题名是〈Scalable Second Order Optimization for Deep Learning〉。他们发现真实模型的 Lt,RtL_t,R_t 条件数极大,矩阵根必须用双精度算,这在 TPU 上很贵。改动包括:

  1. 加速器每一步只累积统计量,逆 pp 次方根每 NN 步送到主机的 CPU 上异步计算,分摊到所有核心,不阻塞训练循环;
  2. 用 coupled Newton 迭代取代 SVD 算逆根,搭配 warm start;
  3. embedding、softmax 这类维度上百万的层只做单边预条件,大型全连接层切成区块各自预条件;
  4. 预条件每几百步才更新一次;
  5. grafting,方向取 Shampoo,步长大小取一个调好的一阶方法(例如对角 AdaGrad),每层各自嫁接;
  6. 指数改成可调的超参数,统计量改用指数移动平均。

结果是 WMT'14 英译法的 Transformer 步数减半,墙钟时间少 45%(约 12 小时降到 6.7 小时)。

Shi 等人(2023)的 PyTorch 版。 Meta 团队针对 GPU 的数据并行训练重写了一版。每个 worker 只负责一部分参数区块的预条件,算完再用 AllGather 收齐方向,每一步的墙钟时间比对角方法最多多 10%。矩阵根改用 torch.linalg.eigh,他们发现单精度通常够用;小维度合并、大维度切块,ImageNet 实验的区块上限设为 2048;grafting、偏差修正、decoupled weight decay、Nesterov 一应俱全。在 ImageNet 的 ResNet-50 上,Shampoo 用 60 个 epoch 达到 SGD-Nesterov 90 个 epoch 的验证准确率,总墙钟时间快 1.35 倍。

AlgoPerf 2024。 MLCommons 在 2024 年 8 月公布第一届 AlgoPerf 训练算法竞赛的结果,外部调参组冠军就是这份 PyTorch Distributed Shampoo,得分 0.78,平均比 NAdamW 基线快约 28%。赛后分析论文的细节更值得看。八个工作负载里,它只在 Criteo 1TB 和 ViT 两项最快;WMT 花的时间是最快提交的两倍以上;ResNet 则没能在时间预算内稳定达标。它赢在几乎每一项都稳定地不差。

同一年的 Gemini 1.5 技术报告也写到,1.5 Flash「is trained with higher-order preconditioned methods」,引用了 AdaGrad 等文献,没有点名是哪一个方法。

1/4 还是 1/2

指数的问题后来有了答案。Anil 等人在附录写到,把指数当成超参数有时效果更好,他们的自编码器实验用的就是 L−1/2GR−1/2L^{-1/2}GR^{-1/2};Shi 等人的实现则建议,以全连接层为主的网络可以把指数覆盖成 p=2p=2,同样是 −1/2-1/2,或把原本的指数乘上 1.82 倍。Morwani 等人(2024)给出了解释,L⊗RL\otimes R 恰好等于「求 full AdaGrad 统计量的最佳 Kronecker 近似」做一步幂迭代的结果,而且很接近最佳近似。既然 L⊗RL\otimes R 本身就在近似 ∑gg⊤\sum gg^\top,要模仿 AdaGrad 的 −1/2-1/2 次方,左右各取 −1/2-1/2 才对。以 Morwani 等人(2024)的结果回头看,本文把原论文的 1/41/4 概括为一个不够紧的上界带出来的指数。

1/41/4 也没有白费。把累积拿掉,只看当下这一步的梯度 G=UΣV⊤G = U\Sigma V^\top:

(GG⊤)−1/4 G (G⊤G)−1/4=UΣ−1/2U⊤  UΣV⊤  VΣ−1/2V⊤=UV⊤(GG^\top)^{-1/4}\,G\,(G^\top G)^{-1/4} = U\Sigma^{-1/2}U^\top\; U\Sigma V^\top\; V\Sigma^{-1/2}V^\top = UV^\top

所有奇异值都被压成 1,这就是 Muon 的正交化更新。Shampoo 的第一步,统计量里只有一个梯度,ε 很小时走的方向就是 −UV⊤-UV^\top;用上面的代码对一个 6×46\times4 的随机梯度走一步,结果和 −UV⊤-UV^\top 只差 ε 造成的偏移,大多在 10−410^{-4} 量级。Keller Jordan 在 2024 年 12 月介绍 Muon 的文章里也写到,去掉累积的 Shampoo 再加上动量就是 Muon,差别在 Shampoo 要算逆四次根,Muon 用 Newton–Schulz 迭代便宜地近似。

结论

Shampoo 用两个小矩阵的 Kronecker 积,近似 full-matrix AdaGrad 那个存不下的预条件,内存从 m2n2m^2n^2 降到 m2+n2m^2+n^2,并在凸设定下证明了 O(T)O(\sqrt{T}) 的 regret。论文的实验只到千万参数,主要证明了「每一步没有慢太多」。

如果今天要试,直接用 Meta 的 Distributed Shampoo,从 grafting 用 Adam、指数 −1/2-1/2、预条件每几十步更新一次开始调,并先测好你的模型里最大那一维让每一步慢了多少。原版的代码留着理解算法就好。

论文第 12 页写着「We plan to implement Shampoo in PyTorch in the near future」。后来拿下 AlgoPerf 冠军的,正是 Meta 团队在五年后写成的 PyTorch 版。