가속: 왜 조건수의 제곱근인가
조건수 100 그릇에서 지난 스텝을 더하는 비율을 바꿔 보면, 학습률 0.018에서 계수 0.8이 63스텝으로 가장 빨랐고 0.9는 131스텝, 경사하강은 381스텝이었다. 그 비교는 학습률을 0.018 하나로 묶어 두었는데, 학습률과 모멘텀 계수를 함께 가장 좋게 선택하면 얼마나 빨라질까? 조건수가 100에서 10000으로 커지면 모멘텀에 필요한 스텝 수는 어떻게 바뀔까? 경사하강은 학습률을 아무리 잘 선택해도 스텝 수가 조건수에 비례했다. 스텝 수의 표에서 모멘텀이 몇 배를 벌어 주는지는 보이지만, 그 배수가 어디서 오는지는 아직 모른다.
역사: 폴랴크가 보인 것과 넘을 수 없는 하한
폴랴크의 1964년 논문이 남긴 것은 공을 굴리자는 생각보다 그 수렴 속도의 계산이었다. 2차 함수, 그리고 최소점 근처에서 2차 함수처럼 보이는 매끄러운 함수에서, 학습률과 모멘텀 계수를 적절하게 선택하면 같은 정확도에 닿는 스텝 수가 경사하강의 약 √κ(카파)분의 1로 준다. 반세기 뒤 이 방법을 딥러닝으로 다시 끌어들인 서츠케버와 동료들(2013)도 폴랴크의 업적을 「최소점 근처에서 √κ분의 1의 스텝」으로 요약했다(κ는 최소점에서 곡률의 조건수).
그러면 더 영리한 방법으로 √κ보다 더 줄일 수는 없을까? 아르카디 네미롭스키(Arkadi Nemirovski)와 다비드 유딘(David Yudin)은 1979년 러시아어로 낸 책에서 이 물음에 거꾸로 답했다. 그 책은 1983년 『최적화에서 문제의 복잡도와 방법의 효율(Problem Complexity and Method Efficiency in Optimization)』이라는 제목으로 영어로 옮겨졌다. 함수에 대해 그래디언트만 물어볼 수 있는 방법이라면 어떤 것이든, 최악의 함수를 만나면 √κ에 비례하는 스텝보다 줄일 수 없다는 하한이다. 그래디언트만 쓰는 방법에게 √κ에 비례하는 스텝 수는 넘을 수 없는 하한이고, 2차 함수 위의 무거운 공은 그 하한에 이미 닿아 있었다.


하한이라는 건 방법들을 다 돌려 봤더니 √κ보다 빨라지는 게 없었다는 거죠? 지금이면 옵티마이저 수십 개를 같은 그릇에 돌려 보면 확인되겠네요.

수십 개를 돌려 보고 「어떤 방법이든」이라고 말할 수 있을까요? 내일 누가 새 옵티마이저를 내놓으면요?

아… 돌려 본 것들 얘기밖에 못 하네요. 몇 개를 돌려도 마찬가지고요.

그럼 방법을 하나씩 보는 대신, 그래디언트만 물어보는 방법이라면 무엇이든 골탕 먹이는 함수를 만들어야 했겠네요. 그게 「최악의 함수」라는 거예요?

그래요. 컴퓨터가 아무리 빨라져도 대신 해 줄 수 없고, 증명으로만 할 수 있는 일이에요. 게다가 그 책은 러시아어로 나와서 영어판이 나오기까지 4년이 걸렸어요.

그런데 무거운 공은 그 하한에 이미 닿아 있었다면서요. 학습률과 계수 두 숫자만 선택한 방법이 어떻게 하필 √κ에서 멈추는 거예요?
한 방향만 떼어 보기
왜 하필 √κ인지는 방향 하나만 떼어 보면 알 수 있다. 그릇 ½(θ₁² + 100θ₂²)처럼 방향들이 서로 섞이지 않으면 무거운 공도 방향마다 따로 움직이기 때문이다. 조건수 100 그릇의 완만한 방향, 곧 곡률 λ = 1에 학습률 η = 1/L = 0.01을 쓰는 1차원 문제를 선택했다. 경사하강이 가장 오래 기어가는 바로 그 방향이다. 출발점 x₀ = 1에서 모멘텀 계수 넷으로 걸어 보면(이후 줄곧 |x| < 0.01이 되는 스텝 수):
| β | x₁₀ | x₂₀ | x₄₀ | 늘 0.01 안 | 가장 깊이 넘어간 자리 |
|---|---|---|---|---|---|
| 0 | 0.904 | 0.818 | 0.669 | 459스텝 | 넘어가지 않음 |
| 0.5 | 0.832 | 0.677 | 0.448 | 225스텝 | 넘어가지 않음 |
| 0.81 | 0.697 | 0.365 | 0.074 | 63스텝 | 넘어가지 않음 |
| 0.95 | 0.566 | −0.111 | −0.308 | 170스텝 | −0.440 |
0.81까지는 한쪽에서 점점 빨리 다가가고, 0.95에서는 바닥을 지나 −0.44까지 넘어갔다가 출렁이며 돌아온다. 넘어가지 않는 가장 큰 계수 근처가 가장 빠르다.
이 1차원 스텝을 식으로 보자. 곡률 λ인 방향에서 그래디언트는 λx이므로 한 줄로 합친 업데이트는 xₖ₊₁ = (1 + β − ηλ)xₖ − βxₖ₋₁이다. 지금 자리와 바로 앞 자리 둘로 다음 자리가 정해진다. 경사하강이라면 스텝마다 같은 배율이 곱해졌으니, 여기서도 xₖ = rᵏ 형태를 넣어 보면 배율 r이 다음 2차 방정식을 풀어야 한다.
근이 둘이므로 스텝은 두 배율의 섞임이고, 둘 가운데 큰 것이 수렴 속도(스텝마다 거리가 줄어드는 비율)를 정한다. 표의 네 계수에서 근은 β = 0이면 0.99 하나, 0.5면 0.9796과 0.5104, 0.81이면 0.9와 0.9로 겹치고, 0.95면 0.97 ± 0.0954i라는 복소수 한 쌍이다. 복소수 배율은 스텝마다 크기만큼 줄면서 돌아가는 것이라, 0.95에서 바닥을 지나 출렁인 것이 이것이다.
이 절의 핵심은 2차 방정식의 두 근을 곱하면 상수항 β가 된다는 데서 나온다. 근이 복소수 한 쌍이면 두 근의 크기가 같으므로 두 근의 크기는 둘 다 √β이고, 곡률 λ가 얼마이든 상관없다. 실제로 β = 0.81로 두고 ηλ를 0.01, 0.1, 0.5, 1, 2, 3, 3.5로 바꿔도 근의 크기는 모두 0.9다. 근이 복소수가 되는 범위는 (1 − √β)² < ηλ < (1 + √β)², 이 경우 0.01에서 3.61 사이다(3.7이면 근 하나가 1.2331로 커져 터진다). 곡률이 361배 차이 나는 방향들이 모두 스텝마다 똑같이 0.9배씩 준다.

그러면 할 일은 하나다. 그릇의 모든 곡률, 곧 가장 작은 μ부터 가장 큰 L까지가 복소수 범위에 들게 η와 β를 선택하고, 그 안에서 √β를 되도록 작게 하면 된다. 범위의 양 끝을 ημ = (1 − √β)², ηL = (1 + √β)²에 일치시키고 두 식의 제곱근을 빼고 더하면 다음을 얻는다. 폴랴크가 선택한 값이다.
조건수 100이면 η = 4/121 = 0.03306, β = (9/11)² = 0.6694이고, 한 스텝 배율은 곡률 1, 10, 50, 100인 방향 모두 9/11 = 0.818이다. 경사하강은 가장 좋은 학습률 2/(L + μ)를 선택해도 가장 나쁜 방향의 배율이 (κ − 1)/(κ + 1) = 1 − 2/(κ + 1) = 0.980이었다. 1과 배율의 차이가 2/(κ + 1)에서 2/(√κ + 1)로 바뀌었고, 거리를 1/1000로 줄이는 스텝 수는 1과 배율의 차이에 반비례하므로 κ에 비례하던 것이 √κ에 비례하게 된다. 이렇게 그래디언트만 쓰면서 스텝 수를 조건수 대신 조건수의 제곱근에 비례하게 줄이는 일을 가속 (조건수의 제곱근만큼 빨라지기 / acceleration)이라 한다. 출발 (1, 1)에서 바닥 0.001 안에 들기까지:
| 조건수 κ | 경사하강(가장 좋은 η) | 무거운 공(폴랴크의 η, β) | 비 | √κ |
|---|---|---|---|---|
| 10 | 37 | 16 | 2.3 | 3.2 |
| 100 | 363 | 58 | 6.3 | 10 |
| 1,000 | 3,628 | 204 | 17.8 | 31.6 |
| 10,000 | 36,272 | 708 | 51.2 | 100 |
조건수가 10에서 10000으로 천 배 커질 때 경사하강의 스텝은 약 980배, 무거운 공은 약 44배 늘었다(√1000 ≈ 32). 폴랴크의 값에서는 곡률이 μ, L인 두 방향의 근이 각각 겹쳐 거리가 k × rᵏ 형태로 줄기 때문에, 배율만으로 추정한 것보다 스텝이 조금 더 든다.


갈색 선에서 곡률 1인 방향과 곡률 100인 방향은 한 스텝에 각각 얼마나 남죠?

둘 다 0.818이요. 회색 선은 양 끝이 0.980이었고요. 그런데 무거운 공한테 곡률 50인 방향이 어디 있는지 알려 준 적이 없는데, 어떻게 그 방향도 0.818이에요?

같은 그릇을 뉴턴법으로 건널 때는 무엇을 알아야 했죠?

방향마다의 곡률이요. 헤시안으로 나눠서 모든 방향의 배율을 0으로 만들었어요. 무거운 공이 아는 건… 가장 큰 곡률과 가장 작은 곡률, 두 숫자뿐이고요.

두 숫자만 알고 그 사이 방향들까지 다 맞춘 거야?

응, 근의 크기는 곡률과 상관없이 √β였잖아. 가장 작은 곡률과 가장 큰 곡률만 복소수 범위에 넣으면 그 사이 방향은 저절로 같은 배율이 돼. 곡률을 방향마다 구하지 않고도 구한 것처럼 고르게 줄인 거야. 헤시안 없이 빨라진 게 이거였어.
무거운 공은 이렇게 곡률을 직접 계산하지 않고 그 효과를 흉내 내는 첫 방법이다.
ML에서: 곡률을 흉내 낸다
서츠케버와 동료들은 모멘텀이 2차 방법과 닮은 점을 이렇게 적었다. 곡률이 낮은 방향은 정의상 그래디언트가 천천히 바뀌므로 그 방향의 내리막이 여러 스텝 이어지고, 모멘텀은 그것을 쌓아 키운다. 2차 방법도 곡률이 낮은 방향의 스텝을 키우지만, 쌓는 대신 방향마다 곡률의 역수를 곱한다. 신경망의 헤시안은 10¹⁶ 칸이라 역수를 곱할 수 없으니, 쌓아서 키우는 모멘텀이 실제로 쓸 수 있는 방법이다.
다만 이 절의 계산에는 두 가지 단서가 붙는데, 하나는 그래디언트를 정확히 안다는 가정이다. 미니배치(한 스텝에 쓰는 데이터 묶음)로 추정한 그래디언트에는 노이즈가 섞이는데, 서츠케버와 동료들도 이론이 말하는 최소점 근처에서의 가속 이득은 노이즈가 있으면 사라진다고 적었다. 그들은 대신 바닥에 이르기 전, 내리막의 방향이 여러 스텝 이어지는 앞 단계에서 모멘텀이 크게 돕는다고 보았다. 다른 하나는 μ와 L를 알아야 한다는 것인데, 신경망에서는 두 숫자를 미리 아는 일이 없어서 0.9 같은 값을 실험으로 선택한다.
문제 4. 자동차의 충격 흡수기
자동차 바퀴의 충격 흡수기를 10 cm 눌렀다 놓는다(처음 속도 0). 1초마다 바퀴의 자리 x는 「x − 0.04x + β × (x − 1초 전의 x)」로 바뀐다고 하자(용수철이 0.04x만큼 되돌리고, 지난 움직임의 β배가 이어짐). (가) β = 0.3, 0.64, 0.9일 때 바퀴가 이후 줄곧 0.1 cm 안에 머무는 것은 몇 초부터인가? (나) 어느 β가 가장 빠르고, 그 β는 어디서 나오는가? (풀어 본 뒤 위젯 2의 「문제 4 불러오기」로 확인해 보자.)


지난 움직임을 많이 이어 갈수록 빨리 돌아오겠죠. 0.9가 제일 빠를 거예요. 돌려 보면… 처음 다섯 초는 9.6, 8.86, 7.83, 6.6, 5.22로 셋 중에 제일 빨리 내려와요.

0.1 cm 안에 머무르기 시작하는 때는요?

0.9는 84초예요. 0이 되는 자리를 지나 반대로 4.36 cm까지 튀어 오르고 몇 번 출렁여요. 0.3은 77초, 0.64는 30초. 0.64가 제일 빠르네요.

0.3은 반대로 넘어가지는 않는데 9.6, 9.1, 8.58, …로 느릿느릿 와. 스텝마다 곱해지는 배율이 1에 가까운가 봐. 2차 방정식의 근을 구해 볼게. 큰 근이 0.9413이네.

0.9는? 그건 출렁였잖아.

0.9는 근이 복소수라 크기가 √0.9 = 0.9487이야. 0.3보다도 1에 가까워. 그리고 0.64는… 두 근이 0.8로 겹치네.

두 근이 겹치는 0.64는 어떤 식에서 나오죠?

근이 겹친다는 건 판별식이 0이라는 거니까… 근이 실수에서 복소수로 넘어가는 경계 (1 − √β)² = 0.04, 곧 √β = 0.8이에요.

그 경계보다 작으면, 또 크면 각각 어떻게 되죠?

작으면 큰 근이 √β보다 커서 느리고, 크면 근의 크기가 √β 그대로 커져서 느려요. 경계가 가장 빨라요. 미분방정식 시간에 배운 임계 감쇠예요. 감쇠가 모자라면 출렁이고, 넘치면 느리게 기어 오고요.

실제 자동차도 그렇게 조정한다고 들었어요. 출렁이지 않는 범위에서 가장 빨리 멈추게.

위젯 2에서 문제 4 설정을 불러와 β를 0.3에서 0.9까지 옮겨 가며, 두 근이 어디서 겹치는지 확인해 보세요.

문제 5. 조건수를 잘못 추정하면
조건수 100 그릇 ½(θ₁² + 100θ₂²)에서 가장 큰 곡률 L = 100은 안다고 하자. 조건수를 10, 50, 200, 1000으로 잘못 추정해 μ = L/(추정한 κ)로 놓고 폴랴크의 η, β를 쓰면 손실의 바닥(원점)까지 거리 0.001 안에 들기까지 몇 스텝이 걸리는가(출발 (1, 1))? 바로 추정했을 때는 58스텝이다. 크게 추정하는 쪽과 작게 추정하는 쪽 가운데 어느 쪽이 덜 위험한가?


추정한 조건수마다 돌려 볼게요. 10으로 추정하면 β = 0.2699라서 완만한 방향의 근이 0.968이고, 213스텝이 걸려요. 58의 거의 네 배예요. 50으로 추정하면 85스텝이고요.

크게 추정한 쪽은 200이면 85, 1000이면 204스텝이야. 1000이라고 열 배 크게 추정해도 204인데, 10이라고 열 배 작게 추정하면 213이네. 비슷한데?

스텝 수는 비슷해요. 그런데 두 경우에 완만한 방향의 근이 실수인가요, 복소수인가요?

작게 추정하면 실제 가장 작은 곡률 μ = 1이 추정한 범위보다 아래에 있네요. 그럼 그 방향은 복소수 범위 밖으로 밀려나서 근이 실수가 되고, 경사하강처럼 한쪽에서 기어 와요.

크게 추정하면요?

모든 방향이 복소수 범위 안이라 근의 크기가 √β = 0.9387로 같고, 출렁이면서 와요.

스텝 수는 213이랑 204로 비슷한데, 실수냐 복소수냐가 그렇게 중요해?

기어 오는 쪽은 √κ의 이득을 잃은 거고, 출렁이는 쪽은 이득은 그대로인데 √(추정한 κ)만큼 걷는 거야. 추정한 조건수가 실제와 가까울수록 좋긴 하지만 2배 틀려도 58이 85가 될 뿐이고.

실무에서 모멘텀을 0.9나 0.99처럼 좀 크게 잡는 게 그래서 덜 위험한 쪽이구나. 출렁이는 손실 곡선은 그 대가고요. 이사할 때 상자를 넉넉하게 사 두면 몇 개 남을 뿐인데, 모자라게 사면 짐을 다 못 싸서 이사가 멈추는 거랑 비슷하네요.
문제 6. 모멘텀을 켜면 학습률의 벼랑은 어디로
조건수 100 그릇(L = 100, 출발 손실 50.5)을 50스텝 돌린 뒤의 손실로 학습률 찾기를 한다. (가) 경사하강(β = 0)에서 η = 0.019, 0.021의 50스텝 뒤 손실은? (나) β = 0.9를 켜고 같은 일을 하면 손실이 처음보다 커지는 학습률은 어디인가? (다) 가파른 방향 하나의 근으로 그 경계를 식으로 구하라.


문제 2에서 벽 사이를 오가는 방향은 모멘텀을 켜면 스텝이 오히려 절반쯤으로 줄었잖아. 학습률의 벼랑을 정하는 건 가파른 방향이고 그 방향이 오가니까, 벼랑은 뒤로 밀릴 것 같아.

(가)부터 돌려 볼게. 경사하강은 0.019에서 0.0748이고 0.021에서 68만 9천으로 터져. 벼랑이 2/L = 0.02에 있으니 맞고. 모멘텀을 켜면 0.021에서 0.53으로 멀쩡해. 0.03에서 0.809, 0.037에서 2.56, 0.039에서 5.26 × 10¹⁴이야.

0.037과 0.039 사이에서 터지네. 거의 두 배 뒤로 밀렸어. 그 경계를 식으로도 구하고 싶은데, 어디서 시작하지?

경사하강에서 터질 때는 한 스텝 배율이 어떻게 됐었죠?

−1보다 작아졌어요. 아, 그럼 근 하나가 −1을 지나는 자리를 찾으면 되겠네요. r = −1을 2차 방정식에 넣으면 1 + (1 + β − ηλ) + β = 0, 곧 ηλ = 2(1 + β)예요.

경계 ηλ = 2(1 + β)에 β = 0.9를 넣으면요?

η < 3.8/L = 0.038이에요. 0.037은 안쪽이고 0.039는 바깥이라 실험과 맞아요. ηL = 3.7이면 가파른 방향의 근이 크기 0.9487인 복소수인데, 3.9면 1.3162로 터져요. 경사하강의 「2/L보다 작게」가 모멘텀에서는 「2(1 + β)/L보다 작게」로 넓어지는 거예요.