수학

MATH / 고급 15번

프리컨디셔닝의 이론: Adam에서 K-FAC·Shampoo·Muon까지 한 줄로

갱신 −ηP⁻¹∇를 노름의 최급강하로 읽고 헤세·가우스–뉴턴·피셔·경험적 피셔의 관계를 정리한 뒤, 준뉴턴과 3차 정규화, K-FAC의 크로네커 인수분해와 그 독립 가정, Shampoo의 −1/4 지수, Muon의 스펙트럴 노름 유도를 차례로 세워 이들이 어디서 일치하는지 보입니다.

PALDYN Team41 MIN READ

사전학습 팀이 다음 모델의 옵티마이저를 고르고 있습니다. 기준은 AdamW이고, 후보로 Muon·Shampoo·SOAP이 올라와 있습니다. 논문마다 같은 손실에 도달하는 토큰 수가 몇 할 줄었다는 표가 붙어 있는데, 코드를 열어 보면 네 옵티마이저가 하는 일이 겉으로는 전혀 닮지 않았습니다. AdamW는 원소마다 제곱평균의 제곱근으로 나눕니다. Shampoo는 기울기 행렬의 왼쪽과 오른쪽에 4제곱근의 역행렬을 하나씩 곱합니다. Muon은 기울기 행렬을 다섯 번의 다항식 반복에 넣어 특잇값을 전부 1로 만듭니다. 오래된 K-FAC은 층마다 작은 행렬 둘의 역행렬을 곱합니다. 팀의 한 사람이 묻습니다. 이것들이 각자 무엇을 근사하고 무엇을 가정하는지 한 그림에 놓을 수 없느냐고요. 그래야 어떤 모델에서 어떤 것이 깨질지 미리 짐작할 수 있습니다.

지난 글에서는 기울기를 그대로 쓰는 SGD가 무엇으로 수렴하는지를 보았습니다. 이 글은 기울기 앞에 행렬 하나를 곱하는 모든 방법을 한 줄로 세웁니다. 그 행렬을 프리컨디셔너라 부릅니다. 뉴턴법과 2차 방법에서 근사의 이름들을 나열했다면, 여기서는 각 근사가 어디서 나오고 어떤 가정 위에 서는지를 유도합니다. 도구는 직교와 사영, 특잇값 분해, 그리고 볼록해석의 쌍대 노름입니다.

프리컨디셔너

일반형

양의 정부호 행렬 PP 로 갱신

Δθ=−η P−1∇L(θ)\Delta\theta = -\eta\,P^{-1}\nabla L(\theta)

를 하는 방법을 모두 프리컨디셔닝된 경사하강이라 부릅니다. P=IP = I 이면 경사하강이고, PP 가 헤세이면 뉴턴법입니다. 이 갱신은 한 가지 최적화 문제의 답입니다. 손실의 1차 근사에 걸음의 크기 벌점을 더한

min⁡Δ ∇L⊤Δ+12η Δ⊤P Δ\min_{\Delta}\ \nabla L^\top \Delta + \frac{1}{2\eta}\,\Delta^\top P\,\Delta

를 미분해 0으로 두면 ∇L+1ηPΔ=0\nabla L + \tfrac{1}{\eta}P\Delta = 0 이고, 그 해가 위의 갱신입니다. 벌점의 Δ⊤PΔ\Delta^\top P \Delta 는 노름 ∥Δ∥P=Δ⊤PΔ\lVert \Delta \rVert_P = \sqrt{\Delta^\top P\Delta} 의 제곱입니다. 그래서 프리컨디셔너를 고르는 일은 「걸음의 길이를 어떤 자로 잴 것인가」를 고르는 일이고, 갱신은 그 자로 잰 최급강하, 곧 같은 길이의 걸음 가운데 1차 근사를 가장 많이 줄이는 방향입니다. 이 문장 하나가 이 글의 뼈대입니다. 뒤의 옵티마이저들은 전부 「어떤 자를 쓰는가」로 갈립니다.

아핀 불변성

좌표를 바꾸어 보면 자의 선택이 결과를 바꾼다는 것이 드러납니다. 가역 행렬 AA 로 θ=Aϕ\theta = A\phi 라 두고 같은 손실을 L~(ϕ)=L(Aϕ)\tilde{L}(\phi) = L(A\phi) 로 적으면, 연쇄법칙으로 ∇L~=A⊤∇L\nabla\tilde{L} = A^\top\nabla L 이고 ∇2L~=A⊤HA\nabla^2\tilde{L} = A^\top H A 입니다. 새 좌표에서 뉴턴 걸음을 하고 원래 좌표로 돌려 보면

A Δϕ=−A (A⊤HA)−1A⊤∇L=−H−1∇LA\,\Delta\phi = -A\,(A^\top H A)^{-1}A^\top\nabla L = -H^{-1}\nabla L

로 원래 좌표의 뉴턴 걸음과 같습니다. 이 성질을 아핀 불변성이라 부릅니다. 경사하강은 그렇지 않습니다. 새 좌표의 걸음 −ηA⊤∇L-\eta A^\top\nabla L 을 돌려 보내면 −ηAA⊤∇L-\eta AA^\top\nabla L 이 되어, 좌표를 고르는 사람의 선택이 궤적을 바꿉니다. 일반적으로 프리컨디셔너가 P~=A⊤PA\tilde{P} = A^\top P A 처럼 헤세와 같은 방식으로 변환될 때만 불변이 성립합니다.

대각 프리컨디셔너는 좌표축 방향의 늘림 A=diag⁡(⋅)A = \operatorname{diag}(\cdot) 에 대해서만 불변입니다. Adam이 파라미터마다 스케일이 달라도 잘 버티는 것은 이 덕분입니다. 하지만 회전에는 불변이 아니어서, 곡률의 주축이 좌표축과 어긋나면 대각이 잡을 수 있는 정보가 사라집니다. 아래 그림이 그 차이입니다. 축에 맞춘 타원에서는 대각이 곧 헤세라 한 걸음에 끝나지만, 같은 타원을 30도 돌리면 대각 프리컨디셔너가 경사하강보다도 느려집니다. 글 끝의 실험에서 경사하강이 93걸음, 대각이 133걸음이었고 뉴턴은 회전과 무관하게 한 걸음이었습니다.

회전한 이차함수에서 세 프리컨디셔너

조건수

프리컨디셔닝의 이득은 조건수로 잽니다. 조건수는 최대 고윳값과 최소 고윳값의 비이고, 이차함수에서 경사하강의 반복 수는 이 값에 비례합니다. ψ=P1/2θ\psi = P^{1/2}\theta 로 좌표를 바꾸면 프리컨디셔닝된 경사하강이 ψ\psi 좌표의 보통 경사하강이 되고, 그 좌표의 헤세는 P−1/2HP−1/2P^{-1/2}HP^{-1/2} 입니다. 그래서 수렴 속도를 정하는 것은 κ(H)\kappa(H) 가 아니라

κ(P−1/2HP−1/2)\kappa\big(P^{-1/2}HP^{-1/2}\big)

입니다. P=HP = H 이면 이 값이 1이고 한 걸음에 끝납니다. 좋은 프리컨디셔너란 이 조건수를 1에 가깝게 만들면서 P−1∇LP^{-1}\nabla L 을 싸게 계산할 수 있는 행렬입니다. 두 요구가 서로 당기므로, 뒤의 모든 방법은 「헤세에 얼마나 가깝게」와 「얼마나 싸게」 사이의 어느 한 점입니다.

곡률 행렬

뉴턴과 헤세

헤세를 그대로 쓰면 두 가지 문제가 생깁니다. 첫째, 신경망의 헤세는 양의 정부호가 아닙니다. 음의 고윳값 방향에서 −H−1∇L-H^{-1}\nabla L 은 손실을 올리는 쪽을 가리키고, 안장점 근처에서는 뉴턴법이 안장점으로 끌려갑니다. 둘째, 파라미터가 dd 개면 저장이 d2d^2, 역행렬이 d3d^3 입니다. 그래서 실무의 2차 방법은 헤세 대신 양의 반정부호가 보장된 다른 곡률 행렬을 쓰고, 그것을 다시 구조로 덜어 냅니다. 이 절은 앞의 일, 뒤의 두 절은 뒤의 일입니다.

가우스–뉴턴

손실이 출력 z=f(x;θ)z = f(x;\theta) 를 거쳐 ℓ(z,y)\ell(z, y) 로 계산된다고 합시다. 연쇄법칙으로 두 번 미분하면

∇θ2ℓ=J⊤Hℓ J+∑k∂ℓ∂zk ∇θ2zk\nabla^2_\theta \ell = J^\top H_\ell\, J + \sum_k \frac{\partial \ell}{\partial z_k}\,\nabla^2_\theta z_k

입니다. JJ 는 출력의 파라미터에 대한 야코비안이고 HℓH_\ell 은 손실의 출력에 대한 헤세입니다. 둘째 항은 잔차 ∂ℓ/∂z\partial\ell/\partial z 에 네트워크 자체의 2차 도함수를 곱한 것이라, 잔차가 작아지면 작아집니다. 이 항을 버린 G=J⊤HℓJG = J^\top H_\ell J 가 일반화 가우스–뉴턴 행렬입니다. ℓ\ell 이 출력에 대해 볼록이면 Hℓ⪰0H_\ell \succeq 0 이므로 GG 는 언제나 양의 반정부호입니다. 헤세의 첫 번째 문제가 여기서 풀립니다.

피셔와 경험적 피셔

손실이 음의 로그가능도 ℓ=−log⁡p(y∣z)\ell = -\log p(y \mid z) 이고 pp 가 zz 를 자연 모수로 하는 지수족이면, HℓH_\ell 은 충분통계량의 공분산이 되고 레이블과 무관해집니다. 그래서 가우스–뉴턴 행렬이

F=Ex Ey∼p(⋅∣x;θ)[∇θlog⁡p ∇θlog⁡p⊤]F = \mathbb{E}_{x}\,\mathbb{E}_{y \sim p(\cdot\mid x;\theta)}\big[\nabla_\theta\log p\ \nabla_\theta\log p^\top\big]

와 같아지는데, 이것이 피셔 정보 행렬입니다. 회귀의 제곱오차와 분류의 소프트맥스 교차 엔트로피가 모두 이 경우라, 실무에서는 가우스–뉴턴과 피셔를 같은 것으로 써도 됩니다. 중요한 것은 안쪽 기댓값의 yy 가 모델에서 뽑은 레이블이라는 점입니다.

이 yy 를 데이터의 실제 레이블로 바꾸어 기울기의 바깥곱을 평균낸 것이 경험적 피셔입니다. 계산은 그대로 쓰던 기울기의 제곱이라 공짜에 가깝지만, 피셔와 다른 것입니다. 1차원 선형 회귀에서 노이즈 분산을 1로 두면 피셔는 ∑ixi2\sum_i x_i^2 이고 경험적 피셔는 ∑iri2xi2\sum_i r_i^2 x_i^2 입니다. rir_i 는 잔차입니다. 잘 맞는 모델의 해 근처에서는 E[r2]=1\mathbb{E}[r^2] = 1 이라 둘이 기댓값으로 같지만, 학습 초반에는 잔차가 큰 표본에 곡률을 몰아 주어 걸음을 왜곡합니다.

곡률 행렬 넷과 근사의 갈래

Adam의 2차 모멘트는 이 사슬의 맨 끝에 있습니다. 미니배치 기울기의 제곱을 지수이동평균한 것이므로 경험적 피셔의 대각에 가깝고, 그 제곱근으로 나눕니다. 피셔의 역이 아니라 역제곱근을 쓰는 이유는 곡률을 맞추려는 것이 아니라 Adagrad의 후회 경계에서 나온 선택이기 때문이고, 이 지수는 뒤의 Shampoo에서 다시 나옵니다.

준뉴턴과 신뢰영역

시컨트 조건

곡률 행렬을 직접 만들지 않고 지나온 기울기에서 배우는 길이 준뉴턴법입니다. 한 걸음 sk=θk+1−θks_k = \theta_{k+1} - \theta_k 동안 기울기가 yk=∇Lk+1−∇Lky_k = \nabla L_{k+1} - \nabla L_k 만큼 바뀌었다면, 헤세의 근사 Bk+1B_{k+1} 은 적어도 그 방향에서 맞아야 합니다.

Bk+1 sk=ykB_{k+1}\,s_k = y_k

이 등식이 시컨트 조건입니다. 조건이 dd 개뿐이라 행렬을 정하기에 모자라므로, 조건을 만족하는 행렬 가운데 직전 근사에 가장 가까운 것을 고릅니다. 역행렬 쪽에서 그 답을 적은 것이 BFGS 갱신이고, ρ=1/(yk⊤sk)\rho = 1/(y_k^\top s_k) 라 두면

Hk+1=(I−ρ skyk⊤) Hk (I−ρ yksk⊤)+ρ sksk⊤H_{k+1} = (I - \rho\, s_k y_k^\top)\,H_k\,(I - \rho\, y_k s_k^\top) + \rho\, s_k s_k^\top

입니다. 양의 정부호가 유지되려면 yk⊤sk>0y_k^\top s_k > 0, 곧 걸음 방향의 곡률이 양수여야 합니다. BFGS가 근사하는 것은 헤세 전체가 아니라 「지나온 방향들에서의 헤세」입니다.

저장 비용

HkH_k 를 그대로 들고 있으면 저장이 d2d^2 이라 파라미터가 십억 개면 불가능합니다. L-BFGS는 최근 mm 쌍의 (s,y)(s, y) 만 들고 위 갱신을 곱셈의 사슬로 펼쳐 Hk∇LH_k\nabla L 을 O(md)O(md) 에 계산합니다. 저장은 2md2md 입니다. 문제는 미니배치에서 생깁니다. yky_k 가 서로 다른 미니배치의 기울기 차이라면 그 안의 대부분이 곡률이 아니라 잡음입니다. 같은 미니배치에서 두 번 기울기를 재면 비용이 두 배가 됩니다. 확률적 설정에서 L-BFGS가 잘 안 쓰이는 이유가 이것이고, 뒤의 방법들이 지나온 방향이 아니라 기울기의 통계에서 곡률을 만드는 이유이기도 합니다.

신뢰영역

헤세가 양의 정부호가 아닐 때 걸음을 다루는 고전적인 방법이 신뢰영역입니다. 2차 모형 m(p)=∇L⊤p+12p⊤Bpm(p) = \nabla L^\top p + \tfrac{1}{2}p^\top B p 를 반지름 Δ\Delta 의 공 안에서만 믿고 최소화합니다. 답은 어떤 λ≥0\lambda \ge 0 에 대해

(B+λI) p=−∇L,B+λI⪰0,λ (Δ−∥p∥)=0(B + \lambda I)\,p = -\nabla L, \qquad B + \lambda I \succeq 0, \qquad \lambda\,(\Delta - \lVert p \rVert) = 0

을 만족합니다. 음의 곡률이 있으면 λ\lambda 가 그 크기 이상으로 올라가 행렬을 양의 반정부호로 밀어 올리고, 걸음은 공의 경계에 닿습니다. 실제 감소량과 모형이 예측한 감소량의 비를 보고 Δ\Delta 를 늘이거나 줄입니다. 옵티마이저의 ε\varepsilon 이나 K-FAC의 감쇠 항이 바로 이 λ\lambda 의 자리입니다.

3차 정규화

신뢰영역의 공 대신 3차 벌점을 붙인 것이 네스테로프와 폴랴크의 3차 정규화입니다.

m(p)=∇L⊤p+12p⊤Hp+M6∥p∥3m(p) = \nabla L^\top p + \frac{1}{2}p^\top H p + \frac{M}{6}\lVert p \rVert^3

헤세가 ρ\rho-립시츠이고 M≥ρM \ge \rho 이면 테일러 정리로 L(θ+p)≤L(θ)+m(p)L(\theta + p) \le L(\theta) + m(p) 가 언제나 성립합니다. 모형이 손실의 전역 상계이므로 모형을 줄이면 손실이 반드시 줄어듭니다. 안장점에서 이 성질이 힘을 씁니다. 기울기가 0이고 헤세의 최소 고윳값이 −γ-\gamma 인 점에서, 그 고유벡터 방향으로 길이 ss 만큼 가면 모형 값이 −γ2s2+M6s3-\tfrac{\gamma}{2}s^2 + \tfrac{M}{6}s^3 입니다. 이를 최소화하는 s=2γ/Ms = 2\gamma/M 에서 감소량이

γ2⋅4γ2M2−M6⋅8γ3M3=23⋅γ3M2\frac{\gamma}{2}\cdot\frac{4\gamma^2}{M^2} - \frac{M}{6}\cdot\frac{8\gamma^3}{M^3} = \frac{2}{3}\cdot\frac{\gamma^3}{M^2}

이라, 기울기가 0이어도 손실이 확실히 줄어듭니다. 경사하강은 같은 점에서 움직이지 않습니다. 그 결과 3차 정규화는 ∥∇L∥≤ε\lVert\nabla L\rVert \le \varepsilon 이고 λmin⁡(H)≥−ρε\lambda_{\min}(H) \ge -\sqrt{\rho\varepsilon} 인 2차 정상점을 O(ε−3/2)O(\varepsilon^{-3/2}) 번 안에 찾습니다. 1차 정상점만 보장하는 경사하강의 O(ε−2)O(\varepsilon^{-2}) 보다 빠르면서 보장도 강합니다. 대가는 매 걸음 부분문제를 푸는 비용이라 대규모 학습에 바로 쓰이지는 않지만, 「음의 곡률을 아는 방법은 안장점을 정해진 시간 안에 빠져나온다」는 기준을 세운 결과입니다.

K-FAC

층의 피셔 블록

이제 구조로 덜어 내는 근사입니다. K-FAC은 두 겹의 가정을 겁니다. 첫째, 서로 다른 층 사이의 피셔 블록을 0으로 둡니다. 둘째, 층 하나의 블록을 크로네커 곱으로 인수분해합니다. 둘째 가정을 유도합니다.

선형층 s=Was = Wa 를 생각합니다. a∈Rna \in \mathbb{R}^n 은 입력 활성, W∈Rm×nW \in \mathbb{R}^{m\times n} 이고, 역전파로 들어온 출력 쪽 기울기를 g=∂ℓ/∂s∈Rmg = \partial\ell/\partial s \in \mathbb{R}^m 이라 둡니다. 피셔를 쓰려면 이 gg 는 모델에서 뽑은 레이블로 계산합니다. 가중치의 기울기는 바깥곱 ∇Wℓ=g a⊤\nabla_W\ell = g\,a^\top 이고, 열을 차례로 쌓는 벡터화에서는

vec⁡(g a⊤)=a⊗g\operatorname{vec}(g\,a^\top) = a \otimes g

입니다. 크로네커 곱 a⊗ga \otimes g 는 aa 의 성분마다 벡터 gg 를 통째로 곱해 이어 붙인 길이 mnmn 의 벡터입니다. 그러면 층 하나의 피셔 블록은 크로네커 곱의 성질 (a⊗g)(a⊗g)⊤=(aa⊤)⊗(gg⊤)(a\otimes g)(a\otimes g)^\top = (aa^\top)\otimes(gg^\top) 로

FW=E[(aa⊤)⊗(gg⊤)]F_W = \mathbb{E}\big[(a a^\top) \otimes (g g^\top)\big]

입니다. 크기가 mn×mnmn \times mn 이라 m=n=4096m = n = 4096 이면 칸이 2.8×10142.8\times10^{14} 개입니다.

크로네커 인수분해

K-FAC은 기댓값을 두 인자로 나눕니다.

FW≈E[aa⊤]⊗E[gg⊤]=A⊗GF_W \approx \mathbb{E}[a a^\top] \otimes \mathbb{E}[g g^\top] = A \otimes G

AA 는 n×nn\times n, GG 는 m×mm\times m 입니다. 크로네커 곱의 역은 역의 크로네커 곱이고, (B⊗C)vec⁡(X)=vec⁡(CXB⊤)(B\otimes C)\operatorname{vec}(X) = \operatorname{vec}(CXB^\top) 이므로 프리컨디셔닝된 기울기는

(A⊗G)−1vec⁡(∇Wℓ)=vec⁡(G−1 ∇Wℓ A−1)(A\otimes G)^{-1}\operatorname{vec}(\nabla_W\ell) = \operatorname{vec}\big(G^{-1}\,\nabla_W\ell\,A^{-1}\big)

입니다. mn×mnmn\times mn 행렬의 역 대신 n×nn\times n 과 m×mm\times m 의 역 둘이면 되고, 비용이 O(m3n3)O(m^3n^3) 에서 O(m3+n3)O(m^3 + n^3) 으로, 저장이 (mn)2(mn)^2 에서 m2+n2m^2 + n^2 로 떨어집니다. 앞의 4096 층이면 2.8×10142.8\times10^{14} 칸이 3.4×1073.4\times10^7 칸이 됩니다.

피셔 블록의 크로네커 인수분해

독립 가정

이 근사가 정확해지는 조건은 분명합니다. aa⊤a a^\top 과 gg⊤g g^\top 이 서로 상관이 없으면, 특히 aa 와 gg 가 독립이면 곱의 기댓값이 기댓값의 곱이 되어 등호가 성립합니다. 마지막 선형층에 가우스 출력을 두고 레이블을 모델에서 뽑으면 gg 는 y^−ysample\hat{y} - y_{\text{sample}} 이라 입력과 독립인 잡음이고, 근사가 정확합니다. 글 끝의 실험에서 이 경우의 상대오차가 표본 오차 수준인 0.008이었습니다. 반대로 gg 의 크기가 입력에 묶여 있으면, 예컨대 잔차가 활성의 크기에 비례하면 같은 실험에서 상대오차가 0.64로 뛰었습니다. 깊은 층에서는 gg 가 위쪽 층의 활성과 가중치를 거쳐 오므로 aa 와 엮여 있고, 독립 가정은 근사입니다.

정리하면 K-FAC이 딛는 가정은 셋입니다. 층 사이의 상관을 무시하는 블록 대각, 층 안에서 활성과 출력 기울기의 2차 통계가 따로 논다는 인수분해, 그리고 레이블을 모델에서 뽑는 피셔를 쓴다는 것입니다. 셋째를 경험적 피셔로 바꾸면 앞 절의 왜곡이 그대로 들어옵니다. 합성곱과 어텐션에는 위치와 헤드에 걸친 추가 가정이 붙어야 같은 꼴이 나옵니다.

감쇠와 비용

실제 구현은 역행렬 앞에 감쇠를 넣습니다. 신뢰영역의 λI\lambda I 를 A⊗GA\otimes G 에 더하면 크로네커 꼴이 깨지므로, 대신 (A+πλI)⊗(G+π−1λI)(A + \pi\sqrt{\lambda}I)\otimes(G + \pi^{-1}\sqrt{\lambda}I) 처럼 인자마다 나누어 더합니다. π\pi 는 두 인자의 크기를 맞추는 비율입니다. 인자 행렬은 매 걸음 지수이동평균으로 갱신하고, 역행렬은 수십에서 수백 걸음마다 한 번 계산해 그 비용을 나누어 냅니다. 이 「통계는 자주, 역행렬은 가끔」의 구조는 다음 절의 Shampoo도 그대로 씁니다.

Shampoo

행·열 프리컨디셔너

Shampoo는 같은 크로네커 구조를 다른 출발점에서 얻습니다. 출발점은 전체 행렬 Adagrad입니다. 기울기 벡터 gtg_t 의 바깥곱을 누적한 ∑tgtgt⊤\sum_t g_t g_t^\top 의 제곱근으로 나누는 방법인데, 크기가 d×dd\times d 라 쓸 수 없습니다. Shampoo는 층의 기울기 행렬 Gt∈Rm×nG_t \in \mathbb{R}^{m\times n} 에서 행 쪽과 열 쪽 통계를 따로 모읍니다.

Lt=∑s≤tGsGs⊤∈Rm×m,Rt=∑s≤tGs⊤Gs∈Rn×nL_t = \sum_{s\le t} G_s G_s^\top \in \mathbb{R}^{m\times m}, \qquad R_t = \sum_{s\le t} G_s^\top G_s \in \mathbb{R}^{n\times n}

그리고 갱신을

W←W−η Lt−1/4 Gt Rt−1/4W \leftarrow W - \eta\, L_t^{-1/4}\, G_t\, R_t^{-1/4}

로 합니다. K-FAC과 생김새가 같지만 들어가는 것이 다릅니다. K-FAC의 두 인자는 활성과 출력 기울기라는 다른 신호에서 오고, Shampoo의 두 인자는 같은 기울기 행렬을 양쪽에서 곱해 만듭니다.

지수 −1/4

지수가 −1/2-1/2 가 아니라 −1/4-1/4 인 이유가 이 방법의 핵심입니다. 랭크가 rr 이하인 행렬 GG 에 대해, 열을 쌓는 벡터화로

vec⁡(G)vec⁡(G)⊤⪯r (G⊤G)1/2⊗(GG⊤)1/2\operatorname{vec}(G)\operatorname{vec}(G)^\top \preceq r\,(G^\top G)^{1/2} \otimes (GG^\top)^{1/2}

가 성립합니다. 왼쪽은 전체 행렬 Adagrad가 쓰는 바깥곱이고 오른쪽은 행·열 통계만으로 만든 크로네커 곱입니다. 이것을 시간에 대해 더하고 안도의 부등식(크로네커 곱의 제곱근이 합에 대해 오목하다는 성질)을 쓰면 ∑tgtgt⊤⪯r Rt1/2⊗Lt1/2\sum_t g_tg_t^\top \preceq r\,R_t^{1/2}\otimes L_t^{1/2} 이고, 제곱근도 순서를 지키므로

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

입니다. 전체 행렬 Adagrad의 프리컨디셔너를 그보다 큰 크로네커 행렬로 바꾸면 걸음이 조금 작아질 뿐 후회 경계가 상수배로 유지됩니다. 그 행렬로 나누면 앞의 벡터화 공식으로 Lt−1/4GtRt−1/4L_t^{-1/4}G_tR_t^{-1/4} 가 나옵니다. 지수 1/41/4 는 Adagrad의 제곱근 하나와 행·열 두 인자에 나누어 준 제곱근 하나가 겹친 것입니다.

행렬 제곱근 계산

L−1/4L^{-1/4} 은 고윳값 분해 L=QΛQ⊤L = Q\Lambda Q^\top 로 QΛ−1/4Q⊤Q\Lambda^{-1/4}Q^\top 을 만들어 얻습니다. 비용이 O(m3)O(m^3) 라 K-FAC처럼 수십에서 수백 걸음마다 다시 계산하고, 그 사이에는 묵은 값을 씁니다. 수치 문제가 둘 있습니다. 작은 고윳값에 −1/4-1/4 제곱을 하면 값이 폭발하므로 L+εIL + \varepsilon I 로 받치고, 그 ε\varepsilon 이 다시 감쇠의 자리입니다. 그리고 반정밀도에서는 고윳값 분해가 불안정해 통계와 분해를 단정밀도 이상으로 들고 있어야 합니다. 분해 대신 역 pp 제곱근을 직접 수렴시키는 결합 뉴턴 반복을 쓰기도 합니다. SOAP은 여기서 한 걸음 더 갑니다. LL 과 RR 의 고유벡터로 기울기를 회전시킨 좌표에서 Adam을 돌리고 다시 돌려놓습니다. 앞의 아핀 불변성 이야기로 읽으면, 대각 프리컨디셔너가 회전에 약하다는 약점을 Shampoo가 찾은 좌표계로 옮겨 가서 피하는 것입니다.

Muon

스펙트럴 노름 최급강하

첫 절의 문장을 다시 씁니다. 갱신은 어떤 자로 잰 최급강하입니다. 벡터의 ℓ∞\ell_\infty 노름을 자로 쓰면, 반지름 η\eta 의 상자 안에서 ∇L⊤Δ\nabla L^\top\Delta 를 가장 작게 만드는 것은 각 좌표를 반대 부호의 끝으로 보내는

Δ=−η sign⁡(∇L)\Delta = -\eta\,\operatorname{sign}(\nabla L)

입니다. 행렬 WW 에는 스펙트럴 노름, 곧 최대 특잇값을 자로 쓸 수 있습니다. 행렬이 벡터를 가장 많이 늘리는 배율이라, 층의 출력이 한 걸음에 얼마나 바뀌는지를 직접 잽니다. 기울기 행렬을 G=UΣV⊤G = U\Sigma V^\top 로 분해하면

⟨G,Δ⟩=tr⁡(G⊤Δ)=∑iσi ui⊤Δ vi≥−∑iσi ∥Δ∥2\langle G, \Delta\rangle = \operatorname{tr}(G^\top\Delta) = \sum_i \sigma_i\,u_i^\top\Delta\, v_i \ge -\sum_i\sigma_i\,\lVert\Delta\rVert_2

입니다. 각 ui⊤Δviu_i^\top\Delta v_i 가 스펙트럴 노름 이상으로 작아질 수 없기 때문입니다. 등호는 Δ=−η UV⊤\Delta = -\eta\,UV^\top 에서 성립하고, 그때 값이 −η∑iσi-\eta\sum_i\sigma_i, 곧 핵노름에 −η-\eta 를 곱한 것입니다. 스펙트럴 노름의 쌍대가 핵노름이라는 사실을 그대로 읽은 것입니다. 그래서 스펙트럴 노름 아래의 최급강하는 기울기의 특잇값을 전부 1로 바꾼 UV⊤UV^\top 방향입니다. Muon은 모멘텀으로 평균낸 기울기 행렬에 이 연산을 하고, 그 결과에 행렬 모양에 맞춘 상수를 곱해 갱신합니다. 기울기의 큰 특잇값 방향과 작은 특잇값 방향이 같은 크기로 움직이므로, 소수의 지배적 방향이 갱신을 독차지하는 일이 사라집니다.

노름의 공과 최급강하 방향

뉴턴–슐츠 반복

UV⊤UV^\top 을 매 걸음 특잇값 분해로 구하면 비쌉니다. Muon은 행렬 곱만으로 이 값에 다가가는 뉴턴–슐츠 반복을 씁니다. 가장 단순한 3차 꼴은

Xk+1=32Xk−12XkXk⊤XkX_{k+1} = \tfrac{3}{2}X_k - \tfrac{1}{2}X_kX_k^\top X_k

입니다. Xk=UΣkV⊤X_k = U\Sigma_kV^\top 이면 XkXk⊤Xk=UΣk3V⊤X_kX_k^\top X_k = U\Sigma_k^3V^\top 이므로 반복은 특잇벡터를 그대로 두고 특잇값만 s↦32s−12s3s \mapsto \tfrac{3}{2}s - \tfrac{1}{2}s^3 으로 옮깁니다. 이 다항식의 고정점이 s=1s = 1 이라, 프로베니우스 노름으로 나누어 특잇값을 1 아래로 맞춘 뒤 반복하면 특잇값이 1로 모이고 행렬은 UV⊤UV^\top 으로 갑니다. 글 끝의 실험에서 5×35\times3 행렬의 특잇값이 네 번 만에 (1, 0.9999, 0.6975)(1,\ 0.9999,\ 0.6975), 여덟 번 만에 (1, 1, 1)(1,\ 1,\ 1) 이 되었습니다. 실제 Muon은 작은 특잇값을 더 빨리 끌어올리는 5차 다항식을 다섯 번 돌립니다. 이 반복이 언제 수렴하고 정확히 1로 가지 않아도 되는 이유는 다음 글이 계산합니다.

세 방법의 극한

이제 네 옵티마이저가 어디서 만나는지 셈할 수 있습니다.

  • Adam에서 두 지수이동평균을 끄고(β1=β2=0\beta_1 = \beta_2 = 0) ε\varepsilon 을 0으로 두면 갱신이 g/g2=sign⁡(g)g/\sqrt{g^2} = \operatorname{sign}(g) 입니다. ℓ∞\ell_\infty 최급강하입니다.
  • Shampoo에서 누적을 끄면 L=GG⊤L = GG^\top, R=G⊤GR = G^\top G 이고, 분해를 넣으면 (GG⊤)−1/4G(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 입니다. 모멘텀 없는 Muon과 같습니다.
  • 표본 하나의 기울기 G=g a⊤G = g\,a^\top 로 Shampoo의 통계를 만들면 GG⊤=∥a∥2 gg⊤GG^\top = \lVert a\rVert^2\,gg^\top 이고 G⊤G=∥g∥2 aa⊤G^\top G = \lVert g\rVert^2\,aa^\top 입니다. 스칼라 가중치를 빼면 K-FAC의 두 인자 그대로이고, 남는 차이는 지수 −1/4-1/4 와 −1-1, 그리고 레이블의 출처입니다.
옵티마이저 걸음을 재는 자 곡률의 출처 구조
SGD ℓ2\ell_2 없음 단위 행렬
Adam 대각 v\sqrt{v}, 극한에서 ℓ∞\ell_\infty 경험적 피셔의 대각 대각
K-FAC 피셔 피셔 층별 크로네커, 지수 −1-1
Shampoo 누적 기울기의 행·열 기울기의 2차 통계 층별 크로네커, 지수 −1/4-1/4
Muon 스펙트럴 노름 현재 기울기 하나 누적 없는 행·열

표를 세로로 읽으면 처음의 질문에 답이 나옵니다. 네 옵티마이저는 「어떤 곡률 행렬에서 출발해 어떤 구조로 덜어 내고 어떤 지수를 쓰는가」의 서로 다른 칸입니다. K-FAC은 피셔를 정직하게 근사하려다 독립 가정을 지고, Shampoo는 Adagrad의 경계를 지키려다 지수가 −1/4-1/4 이 되며, Muon은 누적을 버리는 대신 노름의 기하를 고릅니다.

다시 옵티마이저 비교로

코드로 확인하기

본문의 주장 넷을 숫자로 확인합니다. 회전한 이차함수에서 세 프리컨디셔너의 걸음 수, K-FAC 근사가 독립일 때와 아닐 때의 오차, 누적 없는 Shampoo와 극분해의 일치와 스펙트럴 최급강하의 최적성, 그리고 뉴턴–슐츠 반복의 특잇값입니다.

import numpy as np
rng = np.random.default_rng(0)

# 1) 회전한 나쁜 이차함수에서 세 프리컨디셔너
def steps_to(H, P_inv, eta, tol=1e-8, x0=(-0.6, 0.7), max_steps=100_000):
    x = np.array(x0)
    for k in range(max_steps):
        if 0.5 * x @ H @ x < tol:
            return k
        x = x - eta * P_inv @ (H @ x)
    return max_steps
for deg in [0, 30]:
    c, s = np.cos(np.radians(deg)), np.sin(np.radians(deg))
    R = np.array([[c, -s], [s, c]])
    H = R @ np.diag([20.0, 1.0]) @ R.T
    gd = steps_to(H, np.eye(2), 1.8 / 20)                  # 학습률 1.8/L
    Dh = np.diag(np.diag(H) ** -0.5)                       # 대각의 −1/2 제곱
    jac = steps_to(H, Dh @ Dh, 1 / np.linalg.eigvalsh(Dh @ H @ Dh)[-1])
    newton = steps_to(H, np.linalg.inv(H), 1.0)
    print(f"회전 {deg:2d}도: GD {gd:5d}걸음  대각 {jac:5d}걸음  뉴턴 {newton}걸음")

# 2) K-FAC: 층 하나의 피셔 블록과 크로네커 근사
n_in, n_out, N = 4, 3, 200_000
Ca = np.diag([3.0, 1.0, 0.5, 0.2])
a = rng.standard_normal((N, n_in)) @ np.sqrt(Ca)
W = rng.standard_normal((n_out, n_in))
def kfac_error(g):
    v = np.einsum('ni,nj->nij', a, g).reshape(N, -1)      # vec(g aᵀ) = a ⊗ g
    F = v.T @ v / N
    A, G = a.T @ a / N, g.T @ g / N
    return np.linalg.norm(F - np.kron(A, G)) / np.linalg.norm(F)
g_indep = rng.standard_normal((N, n_out))                 # 모델에서 뽑은 라벨의 잔차
g_dep = (a @ W.T) * rng.standard_normal((N, 1))           # 크기가 입력에 묶인 잔차
print(f"K-FAC 상대오차: 독립 {kfac_error(g_indep):.3f}   의존 {kfac_error(g_dep):.3f}")

# 3) 누적 없는 Shampoo = 극분해의 직교 인자 = 스펙트럴 최급강하
def mpow(S, p, eps=1e-12):
    w, Q = np.linalg.eigh(S)
    w = np.where(w > eps, w, np.inf if p < 0 else 0.0)
    return (Q * w ** p) @ Q.T
G = rng.standard_normal((5, 3))
U, sv, Vt = np.linalg.svd(G, full_matrices=False)
shampoo = mpow(G @ G.T, -0.25) @ G @ mpow(G.T @ G, -0.25)
print("Shampoo(β=0) − UVᵀ 최대 오차", np.abs(shampoo - U @ Vt).max())
print("<G, −UVᵀ> =", round(np.sum(G * -(U @ Vt)), 4), "  −핵노름 =", round(-sv.sum(), 4))
best = min(np.sum(G * D / np.linalg.norm(D, 2)) for D in rng.standard_normal((20000, 5, 3)))
print("무작위 방향 2만 개 중 최솟값", round(best, 4))

# 4) 뉴턴–슐츠 3차 반복: 특잇값이 1로
X = G / np.linalg.norm(G)
for k in range(1, 9):
    X = 1.5 * X - 0.5 * X @ X.T @ X
    if k in (2, 4, 8):
        print(f"반복 {k}: 특잇값 {np.round(np.linalg.svd(X, compute_uv=False), 4)}")
회전  0도: GD    91걸음  대각     1걸음  뉴턴 1걸음
회전 30도: GD    93걸음  대각   133걸음  뉴턴 1걸음
K-FAC 상대오차: 독립 0.008   의존 0.641
Shampoo(β=0) − UVᵀ 최대 오차 1.5543122344752192e-15
<G, −UVᵀ> = -4.7249   −핵노름 = -4.7249
무작위 방향 2만 개 중 최솟값 -3.6281
반복 2: 특잇값 [0.9953 0.9281 0.3541]
반복 4: 특잇값 [1.     0.9999 0.6975]
반복 8: 특잇값 [1. 1. 1.]

읽을 것은 넷입니다. 첫째, 축에 맞춘 타원에서 한 걸음이던 대각 프리컨디셔너가 30도 회전 하나로 133걸음이 되어 경사하강보다 느려졌고, 뉴턴은 두 경우 모두 한 걸음입니다. 아핀 불변성의 유무가 이 차이입니다. 둘째, K-FAC의 상대오차는 독립일 때 표본 오차 수준이고 의존할 때 0.64입니다. 근사의 질은 인수분해 자체가 아니라 그 밑의 독립 가정이 정합니다. 셋째, 누적 없는 Shampoo는 기계 정밀도까지 UV⊤UV^\top 과 같고, 그 방향의 내적은 핵노름에 −1-1 을 곱한 값과 일치합니다. 스펙트럴 노름이 1인 무작위 방향 2만 개 가운데 가장 좋은 것도 −3.63-3.63 에 그쳐 −4.72-4.72 에 못 미칩니다. 넷째, 뉴턴–슐츠 반복은 큰 특잇값부터 1에 붙고 가장 작은 것이 마지막에 따라옵니다.

연습

  1. 좌표를 θ=Aϕ\theta = A\phi, A=diag⁡(2, 1)A = \operatorname{diag}(2,\ 1) 로 바꾸고 새 좌표에서 학습률 0.1로 경사하강을 한 걸음 하면, 원래 좌표에서 본 걸음은 무엇인가요. 원래 좌표의 기울기는 (1, 1)(1,\ 1) 입니다.
    새 좌표의 걸음은 −0.1A⊤∇L=(−0.2, −0.1)-0.1A^\top\nabla L = (-0.2,\ -0.1) 이고, 원래 좌표로 돌리면 AA 를 곱해 (−0.4, −0.1)(-0.4,\ -0.1) 입니다. 원래 좌표의 경사하강 걸음 (−0.1, −0.1)(-0.1,\ -0.1) 과 다르고, 그 차이가 AA⊤AA^\top 입니다.
  2. 1차원 선형 회귀에서 노이즈 분산이 1이고 입력이 x=(1, 2, 1)x = (1,\ 2,\ 1), 잔차가 r=(2, 1, −1)r = (2,\ 1,\ -1) 입니다. 피셔와 경험적 피셔를 각각 구하세요.
    피셔는 ∑xi2=1+4+1=6\sum x_i^2 = 1 + 4 + 1 = 6 이고, 경험적 피셔는 ∑ri2xi2=4+4+1=9\sum r_i^2x_i^2 = 4 + 4 + 1 = 9 입니다. 잔차가 큰 첫 표본 때문에 경험적 피셔가 1.5배 큽니다.
  3. A=diag⁡(2, 4)A = \operatorname{diag}(2,\ 4), G=diag⁡(1, 0.5)G = \operatorname{diag}(1,\ 0.5), ∇Wℓ=(2412)\nabla_W\ell = \begin{pmatrix} 2 & 4 \\ 1 & 2 \end{pmatrix} 일 때 K-FAC으로 프리컨디셔닝된 기울기 행렬을 구하세요.
    G−1∇Wℓ A−1=diag⁡(1, 2)(2412)diag⁡(0.5, 0.25)G^{-1}\nabla_W\ell\,A^{-1} = \operatorname{diag}(1,\ 2)\begin{pmatrix} 2 & 4 \\ 1 & 2\end{pmatrix}\operatorname{diag}(0.5,\ 0.25) 입니다. 왼쪽을 먼저 곱하면 (2424)\begin{pmatrix} 2 & 4 \\ 2 & 4\end{pmatrix}, 오른쪽까지 곱하면 (1111)\begin{pmatrix} 1 & 1 \\ 1 & 1\end{pmatrix} 입니다.
  4. 출력 1024, 입력 4096인 선형층에서 정확한 피셔 블록의 칸 수와 K-FAC 두 인자의 칸 수를 비교하세요.
    mn=4,194,304mn = 4{,}194{,}304 라 블록은 (mn)2≈1.76×1013(mn)^2 \approx 1.76\times10^{13} 칸입니다. 인자는 40962+10242=16,777,216+1,048,576=17,825,7924096^2 + 1024^2 = 16{,}777{,}216 + 1{,}048{,}576 = 17{,}825{,}792, 약 1.8×1071.8\times10^7 칸입니다.
  5. G=(0210)G = \begin{pmatrix} 0 & 2 \\ 1 & 0\end{pmatrix} 에 누적 없는 Shampoo 갱신 방향 (GG⊤)−1/4G(G⊤G)−1/4(GG^\top)^{-1/4}G(G^\top G)^{-1/4} 를 계산하세요.
    GG⊤=diag⁡(4, 1)GG^\top = \operatorname{diag}(4,\ 1), G⊤G=diag⁡(1, 4)G^\top G = \operatorname{diag}(1,\ 4) 이라 두 인자는 diag⁡(1/2, 1)\operatorname{diag}(1/\sqrt{2},\ 1) 과 diag⁡(1, 1/2)\operatorname{diag}(1,\ 1/\sqrt{2}) 입니다. 곱하면 오른쪽 위 성분이 2/2×1/2=12/\sqrt{2}\times1/\sqrt{2} = 1 이 되어 (0110)\begin{pmatrix} 0 & 1 \\ 1 & 0\end{pmatrix} 이고, 특잇값이 둘 다 1인 행렬입니다.
  6. 기울기 (0.3, −2, 0.01)(0.3,\ -2,\ 0.01) 에 대해 반지름 0.1의 ℓ∞\ell_\infty 공과 ℓ2\ell_2 공에서 각각 최급강하 걸음을 구하세요.
    ℓ∞\ell_\infty 는 −0.1sign⁡(g)=(−0.1, 0.1, −0.1)-0.1\operatorname{sign}(g) = (-0.1,\ 0.1,\ -0.1) 입니다. ℓ2\ell_2 는 ∥g∥=2.0225\lVert g\rVert = 2.0225 라 −0.1g/∥g∥=(−0.0148, 0.0989, −0.0005)-0.1g/\lVert g\rVert = (-0.0148,\ 0.0989,\ -0.0005) 입니다. 부호 하강은 0.01짜리 좌표도 다른 좌표와 같은 크기로 움직입니다.
  7. 기울기가 0이고 헤세의 최소 고윳값이 −0.3-0.3 인 점에서 M=1.2M = 1.2 의 3차 정규화가 고르는 걸음 길이와 보장하는 감소량을 구하세요.
    걸음 길이는 2γ/M=0.6/1.2=0.52\gamma/M = 0.6/1.2 = 0.5 이고 감소량은 23γ3/M2=23×0.027/1.44=0.0125\tfrac{2}{3}\gamma^3/M^2 = \tfrac{2}{3}\times0.027/1.44 = 0.0125 입니다.
  8. 3차 뉴턴–슐츠 반복을 한 번 하면 특잇값 0.5와 1.2는 각각 얼마가 되나요.
    s↦1.5s−0.5s3s \mapsto 1.5s - 0.5s^3 이라 0.50.5 는 0.75−0.0625=0.68750.75 - 0.0625 = 0.6875 로 1에 다가가고, 1.21.2 는 1.8−0.864=0.9361.8 - 0.864 = 0.936 으로 1 위에서 1 아래로 넘어옵니다.

처음의 질문으로 돌아갑니다. 네 옵티마이저의 생김새가 달라 보였던 것은 같은 갱신 −ηP−1∇L-\eta P^{-1}\nabla L 에서 PP 의 세 가지 선택이 달랐기 때문입니다. 어느 곡률 행렬에서 출발하는가, 그것을 어떤 구조로 덜어 내는가, 몇 제곱을 쓰는가입니다. AdamW는 경험적 피셔의 대각을 제곱근으로 쓰므로 축에 맞지 않는 곡률에 약하고, K-FAC은 피셔를 쓰되 활성과 출력 기울기가 따로 논다는 가정을 집니다. Shampoo는 같은 크로네커 구조를 Adagrad의 경계에서 얻어 지수가 −1/4-1/4 이 되었고, Muon은 그 Shampoo의 누적을 끈 극한이자 스펙트럴 노름의 최급강하였습니다. 팀이 미리 짐작할 수 있는 것도 이 칸에서 나옵니다. 층의 곡률이 축에 맞지 않을수록 대각보다 행·열 구조가 이기고, 활성과 기울기가 강하게 엮인 층일수록 K-FAC의 근사가 흔들립니다.

Muon의 UV⊤UV^\top 은 특잇값이 전부 1인 행렬, 곧 직교 열을 가진 행렬입니다. 그런 행렬들이 이루는 집합은 평평한 공간이 아니라 휘어진 다양체이고, 그 위에서 내려가는 법이 다음 글의 주제입니다.


읽어주셔서 감사합니다. 😊

LATEST

수학의 최신 글

수학2026.11.13

근접 연산자와 거울 하강: 기하를 바꿔서 내려가기

L1·핵노름·가중치 감쇠를 근접 연산자 하나로 묶어 소프트 임계값을 유도하고 ISTA·FISTA·ADMM을 세운 뒤, 브레그만 발산으로 기하를 바꿔 단체 위 거울 하강이 지수가중 갱신이 되는 것과 KL 제약 최적 정책이 그 한 걸음이라는 것을 보입니다.

고급48 MIN
수학2026.11.13

르장드르–펜첼 변환과 쌍대성: 문제를 뒤집어 푸는 법

켤레함수를 접선의 절편으로 세우고 펜첼–영 부등식·이중 켤레·쌍대 노름을 증명한 뒤, 음의 엔트로피의 켤레가 log-sum-exp이고 그 기울기가 softmax라는 계산으로 KL 정규화 정책의 닫힌 해를 다시 얻습니다. 라그랑주 쌍대, 약쌍대·강쌍대, 쌍대 간극까지 다룹니다.

고급48 MIN
수학2026.11.13

볼록해석: 하위기울기, 강볼록성, 매끄러움의 쌍대

미분이 없는 점에서 기울기를 대신하는 하위미분을 세우고 최적성 조건 0 ∈ ∂f를 증명합니다. L1과 ReLU가 0에서 갖는 것, 클라크 미분과 자동미분의 선택, 강볼록성과 L-매끄러움이 켤레에서 자리를 바꾼다는 쌍대까지 다룹니다.

고급50 MIN