수학

MATH / 중급 51번

뉴턴법과 2차 방법: 왜 안 쓰는가, 요즘은 무엇을 근사하는가

뉴턴 갱신 −H⁻¹∇f를 2차 테일러 근사에서 유도하고, 이차수렴이 실제로 무엇을 뜻하는지 계산으로 봅니다. 그런 다음 7B 모델에서 헤세가 196엑사바이트라는 비용을 계산하고, 헤세를 만들지 않고 헤세-벡터 곱만으로 2차 정보를 쓰는 길, 그리고 Adam·K-FAC·Shampoo·Muon이 각각 그 행렬의 어느 부분을 남긴 것인지 정리합니다.

PALDYN Team53 MIN READ

큰 언어모델 학습에 Shampoo나 Muon 같은 옵티마이저를 썼다는 이야기가 늘었습니다. 소개하는 글에는 "2차 방법이 돌아왔다"는 말이 붙어 있는데, 정작 교과서는 오래전부터 "뉴턴법은 딥러닝에 쓸 수 없다"고 적어 두었습니다. 둘 다 맞는 말이려면 돌아온 것이 뉴턴법 자체는 아니어야 합니다.

이 글은 원본이 무엇인지부터 유도하고, 그것이 왜 그대로는 못 쓰이는지를 숫자로 계산한 다음, 원본을 고쳐 쓰는 고전적인 장치들과 요즘 방법들이 그 원본의 어느 부분을 남긴 것인지를 한 표에 정리합니다.

지난 글까지 세 편은 전부 1차 정보만 썼습니다. 곡률은 학습률 상한 2/L2/L 의 LL 로만 등장했고 그마저 우리가 알 수 없는 값이었습니다. 이제 그 곡률을 직접 다뤄 봅니다.

뉴턴 갱신의 유도

2차 근사의 최소점

경사하강법은 함수를 1차까지만 근사합니다 — 지금 자리의 기울기를 재고 그 반대로 갑니다. 얼마나 갈지는 아무도 안 알려 주므로 학습률이라는 손잡이가 필요합니다. 2차까지 근사하면 그 손잡이가 사라집니다.

테일러 전개와 곡률에서 본 대로 xx 근처에서

f(x+d)≈f(x)+∇f(x)Td+12 dTHdf(x+d) \approx f(x) + \nabla f(x)^{\mathsf T} d + \tfrac12\,d^{\mathsf T} H d

이고 HH 는 2차 편미분을 모은 헤세 행렬입니다. 우변은 dd 에 대한 이차식이므로 최소점을 바로 구할 수 있습니다. dd 로 미분해서 0으로 두면

∇f(x)+Hd=0  ⟹  d=−H−1∇f(x)\nabla f(x) + Hd = 0 \;\Longrightarrow\; d = -H^{-1}\nabla f(x)

이것이 뉴턴 갱신입니다. 근사한 포물면의 바닥까지 곧장 가라는 뜻이고, 걸음의 길이를 곡률이 정하므로 학습률이 없습니다. 기울기는 "어느 쪽이 내리막인가"를, 헤세는 "그 내리막이 얼마나 빨리 평평해지는가"를 알려 주고, 뉴턴 갱신은 둘을 합쳐 "바닥이 어디인가"를 계산합니다.

이차함수에서 뉴턴법과 경사하강법의 경로

함수가 애초에 이차함수라면 근사가 곧 원함수이므로 한 스텝에 최소점에 닿습니다. 그림의 경사하강법은 두 방향의 곡률이 10배 다른 골짜기에서 최선의 학습률로도 아홉 스텝 뒤에 아직 도착하지 못했습니다. H−1H^{-1} 이 하는 일이 정확히 그 곡률 차이를 지우는 것입니다 — 지난 세 편에서 학습률·모멘텀·v^\sqrt{\hat v} 로 조금씩 흉내 내려 했던 그 일입니다.

이차수렴

일반 함수에서도 최소점 가까이 가면 매우 빠릅니다. 1차원에서 오차를 ek=xk−x∗e_k = x_k - x^* 라 두고 전개하면

ek+1≈f′′′(x∗)2f′′(x∗) ek2e_{k+1} \approx \frac{f'''(x^*)}{2f''(x^*)}\,e_k^2

로 오차가 제곱됩니다. 맞는 자릿수가 매 스텝 두 배가 된다는 뜻이고, 이것을 이차수렴이라고 합니다. 2\sqrt2 를 f(x)=x2−2f(x)=x^2-2 의 뉴턴법으로 구하면 이렇습니다.

스텝 xkx_k 오차
0 1.5000000000000000 8.6×10−28.6\times10^{-2}
1 1.4166666666666667 2.5×10−32.5\times10^{-3}
2 1.4142156862745099 2.1×10−62.1\times10^{-6}
3 1.4142135623746899 1.6×10−121.6\times10^{-12}
4 1.4142135623730951 0 (배정밀도 한계)

네 스텝에 16자리가 맞습니다. 경사하강법은 같은 정확도에 수천 스텝이 듭니다. 다만 위 식의 "≈"에는 단서가 붙어 있습니다 — eke_k 가 충분히 작아서 세제곱 이상의 항을 버려도 될 때만 성립합니다. 출발점이 멀면 이 표 같은 일은 일어나지 않고, 오히려 멀어질 수도 있습니다. 그 이야기는 아래 「스텝을 줄이는 두 장치」에서 숫자로 봅니다.

아핀 불변성

뉴턴법에는 학습률이 없다는 것 말고도 경사하강법과 갈리는 성질이 하나 더 있습니다. 좌표를 바꿔 같은 문제를 다시 적어 보면 드러납니다. 가역 행렬 AA 로 x=Azx = Az 라 두고 g(z)=f(Az)g(z) = f(Az) 를 최소화한다고 합시다. 연쇄법칙으로

∇g(z)=AT∇f(x),∇2g(z)=ATHA\nabla g(z) = A^{\mathsf T}\nabla f(x), \qquad \nabla^2 g(z) = A^{\mathsf T} H A

이므로 zz 좌표에서의 뉴턴 갱신은

Δz=−(ATHA)−1AT∇f=−A−1H−1A−TAT∇f=−A−1H−1∇f\Delta z = -(A^{\mathsf T} H A)^{-1} A^{\mathsf T}\nabla f = -A^{-1}H^{-1}A^{-\mathsf T}A^{\mathsf T}\nabla f = -A^{-1}H^{-1}\nabla f

이고, 이것을 xx 로 되돌리면 Δx=A Δz=−H−1∇f\Delta x = A\,\Delta z = -H^{-1}\nabla f 입니다. 어느 좌표에서 계산해도 같은 점에 도착한다는 뜻이고, 이렇게 좌표를 선형변환(과 평행이동)해 다시 적어도 방법이 지나는 점들이 그대로인 성질을 아핀 불변성이라고 합니다.

경사하강법은 그렇지 않습니다. 같은 계산을 하면 Δz=−ηAT∇f\Delta z = -\eta A^{\mathsf T}\nabla f 이고 xx 로 되돌린 걸음은 Δx=−ηAAT∇f\Delta x = -\eta AA^{\mathsf T}\nabla f 라, AA 가 바뀌면 걸음의 방향도 길이도 바뀝니다. 파라미터 하나의 단위를 1000배로 바꾸기만 해도 학습률을 다시 골라야 하는 이유가 이것입니다. 뉴턴법은 그 스케일 조정을 H−1H^{-1} 이 스스로 해 주므로 손볼 손잡이가 처음부터 없습니다.

조건수

헤세의 가장 큰 고윳값과 가장 작은 고윳값의 비, 곧 가장 가파른 방향의 곡률이 가장 완만한 방향의 몇 배인지를 조건수 κ\kappa 라고 부릅니다. 경사하강법의 속도는 이 값에 묶여 있습니다. 위 그림의 골짜기는 κ=10\kappa = 10 이고, 최선의 학습률에서도 오차가 스텝마다 (κ−1)/(κ+1)=9/11(\kappa-1)/(\kappa+1) = 9/11 배로만 줄어 아홉 스텝 뒤에도 처음 오차의 16%가 남습니다.

"뉴턴법은 조건수에 둔감하다"는 말의 정확한 뜻이 아핀 불변성입니다. A=H−1/2A = H^{-1/2} 로 고르면 zz 좌표의 헤세는 ATHA=IA^{\mathsf T}HA = I 가 되어 조건수가 1인 둥근 그릇이 됩니다. 그런데 뉴턴법은 길쭉한 그릇에서도 둥근 그릇에서도 같은 점들을 지나므로, 그 수렴 모양이 κ\kappa 에 따라 달라질 수가 없습니다. 둔감하다는 것이 "조건수가 커도 조금만 느려진다"는 뜻이 아니라 "조건수가 수렴 경로에 아예 안 들어간다"는 뜻입니다.

단서가 하나 있습니다. 이것은 정확한 산술에서의 이야기입니다. 컴퓨터가 Hd=−∇fHd = -\nabla f 를 풀 때는 조건수만큼 자릿수를 잃으므로, κ\kappa 가 101210^{12} 쯤 되면 배정밀도에서도 뉴턴 방향 자체가 잡음으로 덮입니다. 조건수는 수렴 속도에서 빠져나갔을 뿐 연립방정식을 푸는 단계로 자리를 옮긴 것입니다.

저장과 역행렬의 비용

저장

이렇게 좋은데 왜 안 쓰는 걸까요. nn 개 파라미터에 대해 HH 는 n×nn \times n 행렬이고 항목이 n2n^2 개입니다. 7B 모델이면 4.9×10194.9\times10^{19} 개, float32로 196엑사바이트입니다. 세상의 저장장치를 다 모아도 담지 못합니다.

대칭이라 절반만 들어도 98엑사바이트이고, 16비트로 줄여도 그 절반입니다. 상수배를 아무리 줄여도 n2n^2 앞에서는 자릿수가 안 바뀝니다.

역행렬

H−1∇fH^{-1}\nabla f 를 구하려면 연립방정식을 풀어야 하고, 직접 풀면 O(n3)O(n^3) 연산입니다. (7×109)3=3.4×1029(7\times10^9)^3 = 3.4\times10^{29} 이고, 초당 101510^{15} 연산을 하는 가속기 한 대로 천만 년입니다. 그것도 한 스텝에 그렇습니다.

파라미터 수에 따른 프리컨디셔너 메모리

그래디언트에 곱해 걸음의 방향과 크기를 고치는 행렬을 프리컨디셔너라고 부르고, 뉴턴법에서는 H−1H^{-1} 이 그 자리에 있습니다. 같은 그래프에서 대각선만 드는 Adam은 8n8n 바이트, 7B에 56GB입니다. 두 곡선의 기울기가 다르다는 것 — 하나는 nn 에, 하나는 n2n^2 에 비례한다는 것 — 이 이 이야기의 전부입니다. 모델이 커질수록 격차가 벌어지므로 "언젠가 하드웨어가 좋아지면"이라는 답은 없습니다.

양정치가 아닌 헤세

비용 말고 문제가 하나 더 있습니다. 모든 방향의 곡률, 곧 모든 고윳값이 양수인 대칭 행렬을 양정치라 하고 0까지 허용하면 양반정치라 하는데, HH 는 양정치가 아닐 수 있습니다. 어떤 방향의 곡률이 음수이면 그 방향의 H−1H^{-1} 성분도 음수라 뉴턴 방향이 손실을 올리는 쪽을 가리킵니다.

f(x,y)=x2−12y2f(x,y) = x^2 - \tfrac12 y^2 로 확인해 봅니다. H=diag⁡(2,−1)H = \operatorname{diag}(2,-1) 이고, 점 (1,2)(1,2) 에서 ∇f=(2,−2)\nabla f = (2,-2) 입니다. 뉴턴 방향은 d=−H−1∇f=(−1,−2)d = -H^{-1}\nabla f = (-1,-2) 로 원점을 가리키고, ∇fTd=−2+4=2>0\nabla f^{\mathsf T}d = -2 + 4 = 2 > 0 이라 그 방향으로 조금만 가도 함숫값이 올라갑니다. 실제로 f(1,2)=−1f(1,2) = -1 인데 도착점 f(0,0)=0f(0,0) = 0 입니다. 원점은 최소점이 아니라 안장점입니다 — 뉴턴법은 "근사한 이차식의 정류점"으로 가는 방법이라 최소점과 안장점을 구별하지 않고, 안장점 근처에서는 오히려 그리로 빨려 들어갑니다. 딥러닝의 손실면은 안장점이 흔한 곳이라 이 성질이 특히 나쁩니다.

이 방향을 숫자 하나 λ\lambda 로 고치는 방법이 있고, 그것이 다음 절의 두 번째 장치입니다. 같은 예를 거기서 다시 씁니다.

피셔 정보 행렬

다른 길은 HH 자체를 버리고 언제나 양반정치인 대체물을 쓰는 것입니다. 가장 흔한 것이 피셔 정보 행렬입니다.

F=E ⁣[∇θlog⁡pθ(y) ∇θlog⁡pθ(y)T]F = E\!\left[\nabla_\theta \log p_\theta(y)\,\nabla_\theta \log p_\theta(y)^{\mathsf T}\right]

바깥곱의 기댓값이라 정의상 양반정치입니다 — 아무 vv 에 대해 vTFv=E[(vT∇log⁡p)2]≥0v^{\mathsf T}Fv = E[(v^{\mathsf T}\nabla\log p)^2] \ge 0 이기 때문입니다. 그리고 로그가능도의 헤세와 부호만 바꾼 것의 기댓값과 같아서 최소점 근처에서는 HH 와 거의 같습니다. 아래에 나올 방법들이 근사하는 것은 대개 HH 가 아니라 이 FF 입니다. FF 가 언제 HH 의 어느 부분과 정확히 같아지는지는 「헤세-벡터 곱」 절에서 가우스-뉴턴과 함께 봅니다.

스텝을 줄이는 두 장치

arctan의 발산

비용을 잠시 잊고 뉴턴법을 그대로 쓸 수 있는 작은 문제에서도 실패가 일어납니다. 1차원 함수

f(x)=xarctan⁡x−12ln⁡(1+x2)f(x) = x\arctan x - \tfrac12\ln(1+x^2)

를 봅시다. 미분하면 f′(x)=arctan⁡xf'(x) = \arctan x, 한 번 더 하면 f′′(x)=1/(1+x2)f''(x) = 1/(1+x^2) 로 어디서나 양수입니다. 최소점이 원점 하나뿐인 볼록함수이고, 헤세가 음수가 되는 문제도 없습니다. 뉴턴 갱신은

xk+1=xk−arctan⁡(xk) (1+xk2)x_{k+1} = x_k - \arctan(x_k)\,(1+x_k^2)

입니다. x0=1x_0 = 1 에서 시작하면 −0.571, 0.117, −0.00106, 7.96×10−10-0.571,\ 0.117,\ -0.00106,\ 7.96\times10^{-10} 으로 이차수렴의 모습 그대로 원점에 닿습니다. 그런데 x0=1.5x_0 = 1.5 에서 시작하면 −1.694, 2.321, −5.114, 32.3, −1575-1.694,\ 2.321,\ -5.114,\ 32.3,\ -1575 로 부호를 바꾸며 멀어집니다.

arctan 위에서 뉴턴 스텝이 발산하는 모습

경계는 x1=−x0x_1 = -x_0 이 되는 점, 곧 arctan⁡(x)(1+x2)=2x\arctan(x)(1+x^2) = 2x 의 해이고 계산하면 x0≈1.3917x_0 \approx 1.3917 입니다. 정확히 그 점에서 시작하면 ±1.3917\pm1.3917 두 점을 영원히 오가고, 조금만 안쪽이면 천천히 감겨 들어가며(x0=1.39x_0 = 1.39 는 다섯 스텝 뒤에도 −1.18-1.18), 조금만 바깥이면 천천히 풀려 나갑니다.

무엇이 잘못됐는지는 x0=1.5x_0 = 1.5 에서 근사한 이차식을 보면 압니다. 그 자리의 곡률은 f′′(1.5)=0.308f''(1.5) = 0.308 로 작아서, 2차 근사는 바닥이 3.19만큼 왼쪽에 있고 함숫값이 0.885에서 −0.685-0.685 까지 내려간다고 예측합니다. 실제로 그 자리에 가 보면 함숫값은 1.081로 오히려 올랐습니다. 멀리서는 곡률이 거기서만 납작하고 바닥 근처에서는 가파른데, 2차 근사는 지금 자리의 곡률이 어디서나 같다고 가정하기 때문입니다. 출발점이 멀면 2차 근사가 거짓말을 하고, 뉴턴법은 그 거짓말을 곧이곧대로 믿고 끝까지 갑니다.

감쇠 뉴턴과 선탐색

첫 번째 장치는 방향은 뉴턴에게 맡기고 길이만 믿지 않는 것입니다.

x←x−α H−1∇f(x),0<α≤1x \leftarrow x - \alpha\,H^{-1}\nabla f(x), \qquad 0 < \alpha \le 1

이렇게 뉴턴 방향을 따라가되 α\alpha 로 걸음을 줄이는 방법을 감쇠 뉴턴이라 하고, 그 방향의 직선 위에서 α\alpha 를 고르는 절차를 선탐색이라고 합니다. 가장 흔한 선탐색은 α=1\alpha = 1 에서 시작해 다음 한 줄 조건이 맞을 때까지 반으로 줄이는 것입니다.

f(x+αd)≤f(x)+c α ∇f(x)Td,c=10−4f(x + \alpha d) \le f(x) + c\,\alpha\,\nabla f(x)^{\mathsf T} d, \qquad c = 10^{-4}

우변은 1차 근사가 약속한 감소량의 cc 배이고, 이 조건을 아르미호 조건이라고 합니다. "적어도 기울기가 약속한 것의 아주 작은 몫만큼은 실제로 내려가라"는 요구라서, 함숫값을 올리는 걸음은 반드시 걸러집니다.

import math
f  = lambda x: x * math.atan(x) - 0.5 * math.log(1 + x * x)
df = lambda x: math.atan(x)
d2 = lambda x: 1 / (1 + x * x)

def newton(x, damped, steps=6):
    out = []
    for _ in range(steps):
        d, a = -df(x) / d2(x), 1.0
        while damped and f(x + a * d) > f(x) + 1e-4 * a * df(x) * d:
            a /= 2                                  # 아르미호 조건을 넘을 때까지 반으로
        x = x + a * d
        out.append(f"{x:.3g}(α={a:g})" if damped else f"{x:.4g}")
    return " → ".join(out)

print("순수 뉴턴:", newton(1.5, False))
print("감쇠 뉴턴:", newton(1.5, True, 4))

# 순수 뉴턴: -1.694 → 2.321 → -5.114 → 32.3 → -1575 → 3.895e+06
# 감쇠 뉴턴: -0.097(α=0.5) → 0.000608(α=1) → -1.5e-10(α=1) → 0(α=1)

같은 출발점 1.5에서 첫 스텝만 α=0.5\alpha = 0.5 로 줄었고, 그다음부터는 α=1\alpha = 1 이 그대로 통과합니다. 이것이 감쇠 뉴턴의 좋은 점입니다 — 멀리서는 걸음을 줄여 발산을 막고, 가까워지면 원래의 뉴턴 스텝으로 돌아가 이차수렴을 그대로 누립니다. 더 멀리 x0=10x_0 = 10 에서 시작해도 처음 네 스텝은 α\alpha 가 1/8, 1/8, 1/4, 1/4로 줄고 다섯 번째부터 1이 됩니다.

신뢰영역과 λ

두 번째 장치는 길이를 먼저 정하고 방향을 고칩니다. 2차 근사를 믿을 수 있는 반경을 ∥d∥≤Δ\|d\| \le \Delta 로 정해 두고 그 안에서만 근사의 최소점을 찾는 것이고, 그 반경 안의 영역을 신뢰영역이라고 합니다. 이 제약 문제를 라그랑주 승수로 풀면 답이

d(λ)=−(H+λI)−1∇f,λ≥0d(\lambda) = -(H + \lambda I)^{-1}\nabla f, \qquad \lambda \ge 0

꼴로 나옵니다. 반경 안에 뉴턴 스텝이 들어가면 λ=0\lambda = 0 이고, 반경이 작을수록 λ\lambda 가 커집니다. 양쪽 끝을 보면 뜻이 분명합니다. λ=0\lambda = 0 이면 뉴턴 갱신 그대로입니다. λ\lambda 가 HH 의 고윳값보다 훨씬 크면 (H+λI)−1≈I/λ(H+\lambda I)^{-1} \approx I/\lambda 라서 d≈−∇f/λd \approx -\nabla f/\lambda, 곧 학습률이 1/λ1/\lambda 인 경사하강법입니다.

첫 그림의 골짜기 f=12(10x2+y2)f = \tfrac12(10x^2 + y^2), 출발점 (1,5)(1,5), 기울기 (10,5)(10,5) 에서 λ\lambda 를 바꿔 가며 계산하면 다음과 같습니다.

λ\lambda d(λ)d(\lambda) 방향
0 (−1, −5)(-1,\ -5) 최소점을 곧장
1 (−0.91, −2.5)(-0.91,\ -2.5)
3 (−0.77, −1.25)(-0.77,\ -1.25)
10 (−0.5, −0.45)(-0.5,\ -0.45)
100 (−0.091, −0.050)(-0.091,\ -0.050)
→∞\to\infty −∇f/λ∝(−10, −5)-\nabla f/\lambda \propto (-10,\ -5) 경사하강

λ에 따라 갱신 방향이 뉴턴에서 경사하강으로 도는 부채꼴

λ\lambda 하나가 두 방법 사이를 연속으로 미끄러지게 해 주는 손잡이입니다. 실제 알고리즘은 이 손잡이를 스텝마다 자동으로 돌립니다 — 근사가 예측한 감소량과 실제 감소량의 비를 재서, 비가 1에 가까우면 근사를 믿고 λ\lambda 를 줄이고(뉴턴 쪽으로), 비가 작거나 음수면 λ\lambda 를 키웁니다(경사하강 쪽으로). arctan 예에서 x0=1.5x_0 = 1.5 의 첫 스텝은 예측 감소량 1.57에 실제는 −0.196-0.196 이라 비가 음수이므로, 신뢰영역 방법이라면 그 스텝을 버리고 λ\lambda 를 키워 다시 계산합니다.

음의 고윳값 보정

λ\lambda 에는 길이를 줄이는 것 말고 일이 하나 더 있습니다. HH 의 고윳값이 μi\mu_i 이면 H+λIH + \lambda I 의 고윳값은 같은 고유벡터에서 μi+λ\mu_i + \lambda 입니다. 대각선에 같은 수를 더하면 스펙트럼 전체가 그만큼 위로 밀리기 때문입니다. 그래서 λ>−μmin⁡\lambda > -\mu_{\min} 으로 고르면 음의 고윳값이 전부 양수가 되어 H+λIH + \lambda I 는 양정치가 됩니다.

앞 절의 안장점 예로 돌아가면 H=diag⁡(2,−1)H = \operatorname{diag}(2,-1) 의 가장 작은 고윳값이 −1-1 이므로 λ>1\lambda > 1 이 필요합니다. λ=2\lambda = 2 로 두면 H+2I=diag⁡(4,1)H + 2I = \operatorname{diag}(4,1) 이고

d=−(H+2I)−1∇f=−(24, −21)=(−0.5, 2)d = -(H+2I)^{-1}\nabla f = -\left(\tfrac{2}{4},\ \tfrac{-2}{1}\right) = (-0.5,\ 2)

입니다. ∇fTd=−1−4=−5<0\nabla f^{\mathsf T}d = -1 - 4 = -5 < 0 으로 이번에는 내리막이고, yy 성분이 2에서 4로 커지는 쪽 — 안장점에서 멀어지는 쪽 — 을 가리킵니다. 뉴턴 방향 (−1,−2)(-1,-2) 가 안장점으로 빨려 들어가던 그 성분의 부호가 뒤집힌 것입니다. λ\lambda 하나가 걸음 길이와 양정치성을 함께 고칩니다.

헤세-벡터 곱

두 번 미분하기

이 장치들은 전부 작은 문제에서의 이야기였습니다. 큰 모델로 돌아가면 HH 를 통째로 드는 것이 문제였지, 2차 정보 자체가 문제였던 것은 아닙니다. 실제로 필요한 것은 행렬이 아니라 그 행렬을 벡터에 곱한 결과 HvHv 뿐인 경우가 많습니다. 그리고 그것은 HH 없이 얻을 수 있습니다.

Hv=∇x ⁣(∇f(x)Tv)Hv = \nabla_x\!\left(\nabla f(x)^{\mathsf T} v\right)

괄호 안은 스칼라 하나입니다. 그래디언트를 구하고, 고정된 vv 와 내적해 스칼라를 만들고, 그것을 다시 미분하면 됩니다. 자동미분으로 역전파를 두 번 하는 비용이고 메모리는 O(n)O(n) 입니다. 유한차분으로도 됩니다.

Hv≈∇f(x+εv)−∇f(x)εHv \approx \frac{\nabla f(x+\varepsilon v) - \nabla f(x)}{\varepsilon}

헤세를 만드는 길과 만들지 않는 길

켤레기울기법

HvHv 만 있으면 Hd=−∇fHd = -\nabla f 를 켤레기울기법으로 풀 수 있습니다 — 행렬을 벡터에 곱하는 연산만으로 연립방정식을 푸는 반복법입니다. 이렇게 뉴턴 방향을 구하는 방식을 Hessian-free 방법이라고 부릅니다.

import numpy as np
rng = np.random.default_rng(0)
n, m, lam = 200, 400, 1e-3
A = rng.normal(0, 1, (m, n)) / np.sqrt(n)

def grad(x):
    s = 1 / (1 + np.exp(-A @ x))
    return A.T @ s / m + lam * x

def hess(x):                                   # 비교용으로만 만든다
    s = 1 / (1 + np.exp(-A @ x))
    return (A.T * (s * (1 - s))) @ A / m + lam * np.eye(n)

x = rng.normal(0, 1, n)
v = rng.normal(0, 1, n); v /= np.linalg.norm(v)
exact = hess(x) @ v
for eps in (1e-1, 1e-3, 1e-5, 1e-7, 1e-9):
    ap = (grad(x + eps * v) - grad(x)) / eps
    print(f"ε={eps:<7} 상대오차 {np.linalg.norm(ap - exact) / np.linalg.norm(exact):.2e}")

hvp = lambda u: (grad(x + 1e-5 * u) - grad(x)) / 1e-5      # 헤세를 만들지 않는다
g = grad(x)
d = np.zeros(n); r = -g.copy(); p = r.copy()
ex = np.linalg.solve(hess(x), -g)
for k in range(1, 31):
    Hp = hvp(p)
    a = (r @ r) / (p @ Hp)
    d = d + a * p
    rn = r - a * Hp
    p = rn + (rn @ rn) / (r @ r) * p
    r = rn
    if k in (1, 3, 10, 30):
        print(f"CG {k:>2}회  뉴턴 방향과의 상대오차 {np.linalg.norm(d - ex) / np.linalg.norm(ex):.2e}")

# ε=0.1     상대오차 7.58e-04
# ε=0.001   상대오차 7.57e-06
# ε=1e-05   상대오차 7.56e-08
# ε=1e-07   상대오차 6.91e-08
# ε=1e-09   상대오차 8.01e-06
# CG  1회  뉴턴 방향과의 상대오차 3.43e-01
# CG  3회  뉴턴 방향과의 상대오차 3.76e-02
# CG 10회  뉴턴 방향과의 상대오차 1.09e-05
# CG 30회  뉴턴 방향과의 상대오차 2.62e-07

두 가지를 볼 수 있습니다. 첫째, 유한차분의 ε\varepsilon 에는 최적값이 있습니다 — 너무 크면 근사가 거칠고 너무 작으면 두 그래디언트의 차이가 반올림 오차에 묻힙니다. 여기서는 10−510^{-5} 근처가 가장 좋고 양쪽으로 갈수록 나빠집니다.

둘째, 파라미터가 200개인데 켤레기울기법 10회면 뉴턴 방향을 소수점 다섯 자리까지 맞춥니다. nn 번이 아니라 몇십 번이면 충분하다는 것이 이 방법이 성립하는 이유입니다.

같은 HvHv 로 행렬 거듭제곱과 파워 반복의 방법을 쓰면 HH 의 최대 고윳값도 잽니다. 그 값이 곧 학습률 상한 2/λmax⁡2/\lambda_{\max} 를 정하므로, 헤세를 만들지 않고도 "지금 학습률이 안전한가"를 확인할 수 있습니다.

그런데 켤레기울기법에는 조건이 하나 붙습니다. 행렬이 양정치여야 합니다. 위 코드는 로지스틱 회귀라 헤세가 양정치였지만, 신경망의 헤세는 음의 고윳값을 갖기 쉽고 그러면 반복 중에 pTHp≤0p^{\mathsf T}Hp \le 0 이 나와 분모가 무너집니다. 그래서 실제로 곱하는 행렬은 다른 것입니다.

가우스-뉴턴과 GGN

제곱오차 손실 L(θ)=12∥r(θ)∥2L(\theta) = \tfrac12\|r(\theta)\|^2 에서 시작합니다. rr 은 잔차 벡터이고, 그 야코비안을 J=∂r/∂θJ = \partial r/\partial\theta 라 하면

∇L=JTr,∇2L=JTJ+∑iri ∇2ri\nabla L = J^{\mathsf T} r, \qquad \nabla^2 L = J^{\mathsf T}J + \sum_i r_i\,\nabla^2 r_i

입니다. 둘째 항을 버리고 JTJJ^{\mathsf T}J 만 헤세 자리에 쓰는 방법을 가우스-뉴턴이라고 합니다. 버린 항은 잔차 rir_i 가 곱해져 있어 데이터에 잘 맞을수록 작아지고, 남긴 항은 아무 vv 에 대해 vTJTJv=∥Jv∥2≥0v^{\mathsf T}J^{\mathsf T}Jv = \|Jv\|^2 \ge 0 이라 정의상 양반정치입니다. 계산이 싸지는 것과 음의 곡률이 사라지는 것이 한 번에 일어납니다. 여기에 앞 절의 λI\lambda I 를 더한 (JTJ+λI)−1(J^{\mathsf T}J + \lambda I)^{-1} 이 곡선 맞춤에서 오래 써 온 레벤버그-마쿼트 방법입니다.

신경망으로 일반화하면 이렇습니다. 출력(로짓) z(θ)z(\theta) 와 그 위의 손실 ℓ(z)\ell(z) 로 나눠 적으면

∇2L=JT ∇z2ℓ J+∑i∂ℓ∂zi ∇2zi\nabla^2 L = J^{\mathsf T}\,\nabla_z^2\ell\,J + \sum_i \frac{\partial\ell}{\partial z_i}\,\nabla^2 z_i

이고, 여기서 J=∂z/∂θJ = \partial z/\partial\theta 입니다. 앞 항만 남긴 G=JT ∇z2ℓ JG = J^{\mathsf T}\,\nabla_z^2\ell\,J 를 GGN(일반화 가우스-뉴턴)이라고 부릅니다. 버린 뒤 항이 네트워크 자체의 굽음이고, 남긴 앞 항은 손실의 굽음을 야코비안으로 옮겨 온 것입니다. ℓ\ell 이 zz 에 대해 볼록하면 — 교차엔트로피도 제곱오차도 그렇습니다 — 가운데 행렬이 양반정치라 GG 도 양반정치입니다. GvGv 는 JvJv 를 전진 모드로, JT(⋅)J^{\mathsf T}(\cdot) 를 역전파로 한 번씩 구하면 되므로 행렬 없이 HvHv 와 비슷한 비용에 얻고, 켤레기울기법이 무너지지 않습니다. 대규모 Hessian-free 학습이 실제로 곱한 것이 이 GvGv 였습니다.

피셔와 GGN의 일치

앞에서 미뤄 둔 질문, 피셔 정보 FF 가 헤세의 어느 부분과 같은가에 이제 답할 수 있습니다. 두 손실에서 FF 와 GG 는 정확히 같습니다.

  • 제곱오차 — ℓ=12∥z−y∥2\ell = \tfrac12\|z-y\|^2 이면 ∇z2ℓ=I\nabla_z^2\ell = I 라 G=JTJG = J^{\mathsf T}J 입니다. 같은 손실을 가우스 분포 y∼N(z,I)y \sim \mathcal N(z, I) 의 음의 로그가능도로 읽으면 점수가 JT(y−z)J^{\mathsf T}(y-z) 이고 E[(y−z)(y−z)T]=IE[(y-z)(y-z)^{\mathsf T}] = I 이므로 F=JTJF = J^{\mathsf T}J 입니다.
  • 교차엔트로피 — 소프트맥스 확률 pp 에 대해 ∇z2ℓ=diag⁡(p)−ppT\nabla_z^2\ell = \operatorname{diag}(p) - pp^{\mathsf T} 이고, 정답 yy 의 점수는 JT(ey−p)J^{\mathsf T}(e_y - p) 입니다. yy 를 모델의 분포 pp 에서 뽑아 평균하면 E[(ey−p)(ey−p)T]=diag⁡(p)−ppTE[(e_y-p)(e_y-p)^{\mathsf T}] = \operatorname{diag}(p) - pp^{\mathsf T} 로 같은 행렬이 나옵니다.

p=(0.7,0.2,0.1)p = (0.7, 0.2, 0.1) 이면 가운데 행렬은 대각이 (0.21,0.16,0.09)(0.21, 0.16, 0.09), 비대각이 −0.14,−0.07,−0.02-0.14, -0.07, -0.02 이고 각 행의 합이 0입니다. (1,1,1)(1,1,1) 방향의 고윳값이 0이라는 뜻이고, 로짓에 같은 수를 더해도 소프트맥스가 안 바뀌는 성질이 그대로 곡률 0으로 나타난 것입니다.

단서는 yy 를 어디서 뽑느냐입니다. 모델 자신의 분포에서 뽑아야 F=GF = G 가 되고, 데이터의 정답 라벨로 바깥곱을 평균한 "경험적 피셔"는 일반적으로 다릅니다. 언어모델의 손실이 교차엔트로피이므로, 아래의 K-FAC이 근사하는 FF 는 곧 GGN이고 헤세에서 네트워크의 굽음을 뺀 나머지입니다.

준뉴턴법과 L-BFGS

할선 조건

여기까지는 HvHv 든 GvGv 든 곡률을 매 스텝 새로 쟀습니다. 다른 길은 곡률을 재지 않고 지나온 길에서 짐작하는 것입니다. 스텝마다

sk=θk+1−θk,yk=∇f(θk+1)−∇f(θk)s_k = \theta_{k+1} - \theta_k, \qquad y_k = \nabla f(\theta_{k+1}) - \nabla f(\theta_k)

한 쌍이 생깁니다. 함수가 이차함수라면 yk=Hsky_k = Hs_k 가 정확히 성립하므로, 이 쌍은 sks_k 방향의 곡률을 공짜로 알려 줍니다. 그래서 헤세의 근사 BB 를 들고 다니다가 새 쌍이 올 때마다 Bk+1sk=ykB_{k+1}s_k = y_k 를 만족하도록 고칩니다. 이 요구를 할선 조건이라 하고, 헤세를 직접 계산하는 대신 할선 조건을 지키며 근사를 고쳐 쌓는 방법들을 준뉴턴법이라고 부릅니다. 1차원에서 B=y/sB = y/s 는 두 점을 잇는 할선의 기울기라 이름이 거기서 왔습니다.

준뉴턴법 중 가장 널리 쓰이는 BFGS는 역행렬을 직접 고칩니다. ρ=1/(yTs)\rho = 1/(y^{\mathsf T}s) 로

Hk+1−1=(I−ρ syT) Hk−1 (I−ρ ysT)+ρ ssTH_{k+1}^{-1} = (I - \rho\,s y^{\mathsf T})\,H_k^{-1}\,(I - \rho\,y s^{\mathsf T}) + \rho\,s s^{\mathsf T}

입니다. 계수 2짜리 고침이라 한 스텝에 O(n2)O(n^2) 이고, 역행렬을 새로 구하는 O(n3)O(n^3) 이 사라집니다. 대신 이차수렴은 못 얻고, 최소점 근처에서 오차가 매 스텝 이전 오차보다 빠르게 — 비율이 0으로 가는 방식으로 — 줄어드는 초선형 수렴을 얻습니다.

곡률 조건

할선 조건 양변에 sTs^{\mathsf T} 를 곱하면 sTBk+1s=sTys^{\mathsf T}B_{k+1}s = s^{\mathsf T}y 입니다. Bk+1B_{k+1} 이 양정치이려면 좌변이 양수여야 하므로 sTy>0s^{\mathsf T}y > 0 이 반드시 필요하고, 이것을 곡률 조건이라고 합니다. 이차함수에서는 sTy=sTHss^{\mathsf T}y = s^{\mathsf T}Hs 로 ss 방향의 곡률 그 자체입니다. 거꾸로 BFGS는 이전 근사가 양정치이고 이 조건이 맞으면 새 근사도 양정치로 남습니다 — 뉴턴법에서 따로 고쳐야 했던 양정치성이 여기서는 한 줄 조건으로 지켜집니다.

이 조건은 선탐색이 보장해 줍니다. 아르미호 조건에 "도착점에서는 기울기가 충분히 덜 가팔라야 한다"는 ∇f(x+αd)Td≥c2∇f(x)Td\nabla f(x+\alpha d)^{\mathsf T}d \ge c_2\nabla f(x)^{\mathsf T}d (c2<1c_2 < 1) 를 더한 것이 울프 조건이고, 이것이 맞으면

sTy=α(∇f(x+αd)−∇f(x))Td≥α (c2−1) ∇f(x)Td>0s^{\mathsf T}y = \alpha\big(\nabla f(x+\alpha d) - \nabla f(x)\big)^{\mathsf T}d \ge \alpha\,(c_2 - 1)\,\nabla f(x)^{\mathsf T}d > 0

입니다. 마지막 부등호는 dd 가 내리막이라 ∇fTd<0\nabla f^{\mathsf T}d < 0 이고 c2−1<0c_2 - 1 < 0 이기 때문입니다. 두 음수의 곱이 양수입니다.

L-BFGS의 메모리

BFGS도 H−1H^{-1} 을 n×nn\times n 으로 들고 있으니 7B에서는 처음의 196엑사바이트로 돌아갑니다. L-BFGS는 행렬을 아예 만들지 않고 최근 kk 쌍의 (s,y)(s, y) 만 들고 있다가, 위 고침 공식을 kk 번 펼친 것을 벡터에 직접 적용합니다. 흔히 이력 길이를 mm 으로 적지만 아래 표의 층 크기 m×nm\times n 과 겹치지 않게 여기서는 kk 로 씁니다. 최신 쌍부터 거꾸로 내적을 빼 나가는 루프 하나, 오래된 쌍부터 다시 더해 오는 루프 하나로 H−1∇fH^{-1}\nabla f 의 근사를 얻는데, 이 절차를 두 겹 루프라 부르고 비용은 약 4kn4kn 번의 곱셈-덧셈입니다.

메모리는 ss 와 yy 가 각각 kk 개라 2kn2kn 개의 수입니다. 7B 모델에 흔히 쓰는 k=10k = 10 을 넣으면

2×10×7×109=1.4×1011 개2 \times 10 \times 7\times10^9 = 1.4\times10^{11}\ \text{개}

입니다. 1,400억 개라는 이 수는 개수이지 바이트가 아니므로, 바이트로 바꾸려면 수 하나의 크기를 곱해야 합니다. float32(4바이트)로 담으면 560GB, 고전적인 구현들이 쓰는 float64(8바이트)로는 1.12TB입니다. Adam의 상태 두 벌이 float32로 56GB였으니 그 열 배이고, 파라미터와 그래디언트는 따로입니다. 엑사바이트에서 기가바이트로 내려온 것은 큰 진전이지만 여전히 Adam보다 한 자릿수 무겁습니다.

잡음

그런데 딥러닝에서 L-BFGS를 안 쓰는 진짜 이유는 메모리가 아닙니다. kk 를 줄이면 메모리는 얼마든지 줄일 수 있습니다. 문제는 yy 입니다. 미니배치 학습에서 y=∇fB2(θ+s)−∇fB1(θ)y = \nabla f_{B_2}(\theta+s) - \nabla f_{B_1}(\theta) 는 서로 다른 배치로 구한 두 그래디언트의 차이라, 그 안에 곡률 HsHs 와 함께 두 배치의 잡음 차이가 들어갑니다. 곡률 항은 ∥s∥\|s\| 에 비례해 작아지는데 잡음 항은 ss 와 무관하므로, 걸음이 작을수록 yy 는 곡률이 아니라 잡음을 담습니다.

앞의 로지스틱 회귀를 데이터 4,000개로 늘려 직접 재 봅니다. 길이 0.01짜리 무작위 걸음 ss 천 개에 대해 sTy/sTss^{\mathsf T}y/s^{\mathsf T}s — 그 방향의 곡률 추정치 — 를 세 방식으로 구합니다.

import numpy as np
rng = np.random.default_rng(0)
n, m, lam = 200, 4000, 1e-3
A = rng.normal(0, 1, (m, n))
y = (rng.random(m) < 0.5).astype(float)

def grad(x, idx):
    p = 1 / (1 + np.exp(-A[idx] @ x))
    return A[idx].T @ (p - y[idx]) / len(idx) + lam * x

x = rng.normal(0, 1, n) / np.sqrt(n)
batch = lambda: rng.choice(m, 64, replace=False)
cases = {"전체 데이터": lambda: (np.arange(m),) * 2,
         "배치 64, 같은 배치": lambda: (batch(),) * 2,
         "배치 64, 다른 배치": lambda: (batch(), batch())}
for name, pick in cases.items():
    c = []
    for _ in range(1000):
        s = rng.normal(0, 1, n); s *= 1e-2 / np.linalg.norm(s)
        i1, i2 = pick()
        yv = grad(x + s, i2) - grad(x, i1)
        c.append(s @ yv / (s @ s))
    c = np.array(c)
    print(f"{name}: 곡률 중앙값 {np.median(c):.3f}, "
          f"범위 [{c.min():.2f}, {c.max():.2f}], 음수 {np.mean(c <= 0):.1%}")

# 전체 데이터: 곡률 중앙값 0.204, 범위 [0.19, 0.22], 음수 0.0%
# 배치 64, 같은 배치: 곡률 중앙값 0.201, 범위 [0.11, 0.34], 음수 0.0%
# 배치 64, 다른 배치: 곡률 중앙값 -0.381, 범위 [-33.99, 35.25], 음수 50.8%

전체 데이터로 재면 곡률이 0.19~0.22 사이에 고르게 모입니다. 배치마다 다른 그래디언트로 재면 범위가 −34-34 에서 3535 로 백 배 넘게 벌어지고, 절반이 곡률 조건을 어깁니다. 볼록한 문제인데도 그렇습니다. 그런 쌍을 받아들이면 근사가 양정치를 잃고, 걸러 내면 쓸 쌍이 절반으로 줄며, 남은 쌍도 크기가 엉터리입니다. 두 그래디언트를 같은 배치로 구하면 부호는 지켜지지만, 그 대가로 스텝마다 그래디언트를 한 번 더 계산해야 하고 그 배치 하나의 곡률만 담깁니다. 선탐색도 같은 이유로 무너집니다 — 아르미호 조건이 견주는 함숫값부터 배치마다 흔들리기 때문입니다.

그래서 L-BFGS가 실제로 쓰이는 자리는 그래디언트가 깨끗한 곳입니다. 전체 데이터를 한 번에 보는 로지스틱 회귀(scikit-learn의 기본 풀이법이 lbfgs입니다), 파라미터가 적은 미세 문제, 그림 한 장을 최적화하는 스타일 변환 같은 곳입니다.

요즘 방법들이 남기는 칸

대각선과 직교화

Hessian-free 방법도 스텝마다 켤레기울기 수십 회가 들어 대규모 학습에는 비쌉니다. 그래서 실제로 쓰이는 길은 FF 를 통째로 다루지 말고 구조를 가정해 싸게 만드는 것입니다. 어느 칸을 버리느냐가 방법을 가릅니다.

여러 방법이 곡률 행렬의 어느 부분을 남기는가

Adam은 대각선만 남깁니다. v^t\hat v_t 가 성분별 E[g2]E[g^2] 이고 그것은 FF 의 대각 성분이니, Adam의 프리컨디셔너는 diag⁡(F)−1/2\operatorname{diag}(F)^{-1/2} 입니다. 지수가 −1-1 이 아니라 −1/2-1/2 인 것이 눈에 띄는데, 뉴턴법이라면 −1-1 이어야 합니다. 제곱근만 쓰는 쪽이 추정이 틀렸을 때 덜 위험하고 실제로 잘 도는 것이 관행이 된 이유입니다. 정확히는 Adam이 모으는 것이 미니배치 그래디언트의 제곱이라 앞 절에서 말한 경험적 피셔의 대각선에 가깝습니다.

Muon은 반대쪽 끝까지 갑니다. 그래디언트 행렬을 특이값분해해서 특잇값을 전부 1로 바꾼 것, 곧 UVTUV^{\mathsf T} 를 갱신 방향으로 씁니다. 이것은 (GGT)−1/2G(GG^{\mathsf T})^{-1/2}G 와 같고, 실제로는 SVD를 하지 않고 뉴턴-슐츠 반복이라는 행렬 곱셈 몇 번으로 얻습니다. 방향만 남기고 크기는 전부 지운다는 점에서 Adam이 성분마다 하던 정규화를 행렬 전체에 대해 하는 것입니다.

크로네커 구조

K-FAC은 층 하나의 FF 를 크로네커 곱으로 근사합니다. 층의 입력 aa 와 출력 쪽 그래디언트 ss 로 ∇WL=s aT\nabla_W L = s\,a^{\mathsf T} 이므로(여기의 ss 는 준뉴턴법의 걸음과는 다른 기호입니다)

F층=E ⁣[(saT)⊗(saT)]≈E[aaT]⊗E[ssT]=A⊗GF_{\text{층}} = E\!\left[(s a^{\mathsf T})\otimes(s a^{\mathsf T})\right] \approx E[aa^{\mathsf T}]\otimes E[ss^{\mathsf T}] = A \otimes G

로 두는 것입니다(두 기댓값이 독립이라는 가정이 들어갑니다). 크로네커 곱의 역은 각각의 역의 크로네커 곱, 즉 (A⊗G)−1=A−1⊗G−1(A\otimes G)^{-1} = A^{-1}\otimes G^{-1} 이므로 m×nm \times n 짜리 층에서 (mn)3(mn)^3 대신 m3+n3m^3 + n^3 만 듭니다. 앞 절에서 본 대로 교차엔트로피에서는 이 FF 가 GGN이므로, K-FAC은 가우스-뉴턴 행렬을 층마다 두 조각으로 쪼갠 것이기도 합니다. 실제 구현은 AA 와 GG 에 λI\lambda I 를 더해 뒤집는데, 신뢰영역의 그 λ\lambda 가 여기서도 같은 일을 합니다.

Shampoo는 가중치를 행렬 WW 그대로 두고 좌우에서 각각 프리컨디셔너를 곱합니다. 그래디언트 GG 에 대해 L=∑GGTL = \sum GG^{\mathsf T}, R=∑GTGR = \sum G^{\mathsf T}G 를 모아 두고 L−1/4GR−1/4L^{-1/4} G R^{-1/4} 를 갱신 방향으로 씁니다. 행 방향과 열 방향의 스케일을 따로 고치는 것이라 대각선보다는 촘촘하고 전체보다는 훨씬 쌉니다.

비용 비교

L-BFGS까지 넣어 한 층의 비용을 나란히 놓으면 이렇습니다. L-BFGS는 원래 파라미터 전체에 걸쳐 도는 방법이지만, 그 메모리와 연산 중 m×nm\times n 층 하나의 몫을 적었습니다.

방법 근사하는 것 층당 추가 메모리 층당 추가 연산
SGD 없음 0 0
Adam diag⁡(F)−1/2\operatorname{diag}(F)^{-1/2} 2mn2mn O(mn)O(mn)
Shampoo 행·열 방향 L−1/4, R−1/4L^{-1/4},\,R^{-1/4} m2+n2m^2+n^2 O(m3+n3)O(m^3+n^3), 드물게
K-FAC F≈A⊗GF \approx A\otimes G m2+n2m^2+n^2 O(m3+n3)O(m^3+n^3), 드물게
Muon (GGT)−1/2G(GG^{\mathsf T})^{-1/2}G mnmn (모멘텀) 행렬 곱 5~6회
L-BFGS 최근 kk 쌍 (s,y)(s,y) 로 만든 H−1H^{-1} 2k mn2k\,mn O(k mn)O(k\,mn), 매 스텝
뉴턴 H−1H^{-1} (mn)2(mn)^2 O((mn)3)O((mn)^3)

Shampoo와 K-FAC이 m3m^3 을 감당할 수 있는 것은 매 스텝 하지 않기 때문입니다. 곡률 통계는 천천히 변하므로 프리컨디셔너를 수백 스텝에 한 번만 다시 계산하고 그 사이에는 재사용합니다. L-BFGS 줄은 메모리가 k=10k = 10 에서 Adam의 열 배이고, 연산은 세제곱이 없는 대신 두 겹 루프를 매 스텝 돌아야 합니다. 표만 보면 L-BFGS가 K-FAC보다 싸 보이는 층도 있지만, 표에 안 적힌 칸 — 잡음에 얼마나 버티는가 — 에서 갈립니다.

이력과 구조

표의 방법들은 곡률을 어디서 얻느냐로 두 갈래로 나뉩니다. 준뉴턴법은 이력에서 얻습니다 — 연이은 두 스텝의 그래디언트 차이로 곡률을 짐작합니다. K-FAC과 Shampoo는 구조에서 얻습니다 — 한 층 안의 행·열 통계 aaTaa^{\mathsf T}, ssTss^{\mathsf T}, GGTGG^{\mathsf T} 를 모아 곡률의 모양을 가정합니다.

두 갈래가 잡음 앞에서 갈리는 이유가 여기 있습니다. 이력은 차이를 내서 곡률을 얻으므로, 두 그래디언트에 섞인 잡음이 차이에서 지워지지 않고 오히려 남습니다. 구조는 바깥곱을 여러 스텝에 걸쳐 평균 내서 얻으므로, 잡음이 평균에서 줄어듭니다. 앞의 실험에서 다른 배치로 재면 절반이 음수였던 곡률이, 바깥곱의 지수이동평균에서는 정의상 음수가 될 수 없습니다. 미니배치로 학습하는 큰 모델에서 살아남은 2차 방법이 전부 구조 쪽인 이유입니다.

"2차 방법이 돌아왔다"의 정확한 뜻이 이제 보입니다. 돌아온 것은 H−1H^{-1} 이 아니라 한 층 안에서 행·열 구조를 이용한 값싼 프리컨디셔너이고, 그 값어치는 이차수렴이 아니라 같은 스텝 수로 더 나아가는 것입니다. 감쇠와 λ\lambda 로 걸음을 다스리던 고전적인 장치들도 그 안에 λI\lambda I 를 더하는 모습으로 남아 있습니다. Shampoo나 Muon으로 언어모델을 학습했다는 소식은 뉴턴법이 딥러닝에 들어왔다는 뜻이 아니라, 뉴턴법에서 미니배치 잡음을 견디는 부분만 골라 낸 결과입니다.

정리

유도와 비용

  • 뉴턴 갱신 d=−H−1∇fd = -H^{-1}\nabla f 는 2차 테일러 근사의 최소점으로 곧장 가는 방향이다. 걸음의 길이를 곡률이 정하므로 학습률이 없고, 이차함수에서는 한 스텝에 도착한다.
  • 최소점 근처에서 오차가 제곱되는 이차수렴이라 2\sqrt2 를 네 스텝에 16자리까지 맞춘다.
  • 좌표를 x=Azx = Az 로 바꿔도 같은 점들을 지나는 아핀 불변성이 있고, "조건수에 둔감하다"는 그 뜻이다. 경사하강법은 Δx=−ηAAT∇f\Delta x = -\eta AA^{\mathsf T}\nabla f 라 좌표마다 학습률을 다시 골라야 한다.
  • 그런데 HH 는 n2n^2 개 항목이다. 7B 모델이면 196엑사바이트, 역행렬은 3.4×10293.4\times10^{29} 연산이다. 게다가 양정치가 아닐 수 있어 안장점으로 끌린다.

근사의 갈래

  • 볼록함수 f′=arctan⁡xf' = \arctan x 에서도 ∣x0∣>1.39|x_0| > 1.39 면 뉴턴법이 발산한다. 감쇠 뉴턴과 아르미호 선탐색은 첫 스텝만 α=0.5\alpha = 0.5 로 줄여 이를 막고, 신뢰영역의 (H+λI)−1(H+\lambda I)^{-1} 은 λ\lambda 하나로 뉴턴과 경사하강 사이를 미끄러지며 음의 고윳값도 위로 민다.
  • Hv=∇(∇fTv)Hv = \nabla(\nabla f^{\mathsf T}v) 로 메모리 O(n)O(n) 에 헤세-벡터 곱을 얻고, 켤레기울기법과 묶으면 200차원 문제에서 10회면 뉴턴 방향에 소수점 다섯 자리까지 닿는다. 신경망에서는 양반정치인 GGN을 곱하고, 교차엔트로피와 제곱오차에서 GGN은 피셔와 같다.
  • 준뉴턴법은 (s,y)(s, y) 쌍으로 H−1H^{-1} 을 고쳐 쌓고 곡률 조건 sTy>0s^{\mathsf T}y > 0 이 양정치를 지킨다. L-BFGS는 2kn2kn 개를 들어 7B·k=10k=10 이면 float32로 560GB이지만, 정말 막는 것은 미니배치 잡음이다 — 다른 배치로 잰 곡률의 절반이 음수였다.
  • 요즘 방법들은 FF 의 어느 칸을 버릴지로 갈린다 — Adam은 대각선만, K-FAC은 크로네커 두 조각, Shampoo는 행·열 방향 두 개, Muon은 그래디언트 행렬의 특잇값을 전부 1로. 전부 한 층 안의 구조에서 곡률을 얻고, 평균을 내므로 잡음을 견딘다.

여기까지가 최적화입니다. 지금까지 손실 L(θ)L(\theta) 는 언제나 "데이터에 대한 평균"이었고, 그 데이터는 우리와 무관하게 주어져 있었습니다. 그런데 「좋은 답을 내게 한다」 같은 목표는 그렇게 적히지 않습니다 — 평가할 답을 모델이 스스로 만들어 내고, 따라서 기댓값을 취하는 분포 자체가 θ\theta 에 의존합니다. 다음 글에서 그 목적식을 세우고, 그 한 가지 차이가 왜 그래디언트를 기댓값 안으로 그냥 넣을 수 없게 만드는지 봅니다.


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

LATEST

수학의 최신 글

수학2026.11.17

다양체 위의 최적화: 직교 제약과 Muon의 직교화가 하는 일

차트·접공간·리만 계량·측지선·후퇴로 다양체를 세우고, 스티펠·그라스만·양정치 행렬·확률 단체의 접공간과 사영을 계산한 뒤, 리만 그래디언트가 유클리드 그래디언트의 접공간 사영임을 증명하고 극분해 후퇴와 뉴턴–슐츠 반복의 수렴 조건을 다룹니다.

고급46 MIN
수학2026.11.17

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

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

고급41 MIN
수학2026.11.17

확률적 근사와 SGD의 연속 극한: 수렴한다는 말의 정확한 뜻

로빈스–먼로 조건과 마팅게일 잡음으로 SGD의 수렴을 정확히 정의하고, 볼록·강볼록·PL·비볼록에서의 수렴률과 오라클 하한을 계산한 뒤, SGD를 확률미분방정식으로 읽어 학습률/배치가 온도가 되는 관점과 안정성의 가장자리를 다룹니다.

고급48 MIN