返回論文筆記資料庫
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 版。