수학

MATH / 고급 13번

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

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

PALDYN Team48 MIN READ

가중치를 희소하게 만들고 싶은 팀이 있습니다. 구조적 가지치기를 앞두고, 또는 희소 오토인코더의 사전을 짧게 만들려고 손실에 λ∑j∣wj∣\lambda \sum_j \lvert w_j \rvert 를 더하고 평소처럼 SGD로 학습합니다. 학습이 끝나고 가중치 히스토그램을 보면 0 근처에 뾰족한 산이 서 있기는 한데, 정확히 0인 가중치는 하나도 없습니다. 10−410^{-4} 와 −10−4-10^{-4} 사이를 오가는 값들이 수천 개 있을 뿐이고, 결국 누군가 문턱을 손으로 정해 잘라 냅니다. 같은 팀이 옵티마이저를 Adam에서 AdamW로 바꾸자 같은 감쇠 계수로도 결과가 달라졌는데, 두 옵티마이저의 차이가 손실에 λ2∥w∥2\tfrac{\lambda}{2}\lVert w \rVert^2 를 넣느냐 갱신식 뒤에 ww 를 따로 줄이느냐뿐이라는 설명을 듣고 고개를 갸웃합니다. 둘 다 같은 항을 다루는데 왜 위치가 결과를 바꾸는가. 이 글의 첫 절반이 답하는 질문은 이 두 장면이 실은 같은 질문이라는 것입니다. 미분이 안 되거나 옵티마이저의 스케일링을 거치면 안 되는 항은 기울기로 밀지 말고 따로 「풀어서」 처리하라는 것, 그 따로 푸는 연산의 이름이 근접 연산자입니다.

지난 글에서 켤레함수로 문제를 뒤집어 보았고, 음의 엔트로피의 켤레가 로그-합-지수이며 그 기울기가 softmax라는 계산을 했습니다. 이 글의 후반부가 그 계산을 그대로 씁니다. 경사하강의 한 걸음은 「선형 근사 더하기 유클리드 거리의 제곱」을 최소화하는 것으로 읽히는데, 그 거리를 다른 것으로 바꾸면 다른 알고리즘이 나옵니다. 확률 단체 위에서 거리를 KL로 바꾸면 갱신이 곱셈과 정규화가 되고, KL 제약 최적 정책의 닫힌 해가 바로 그 한 걸음입니다. 이중 하강과 양성 과적합에서 한 줄로 지나간 거울 하강과 브레그만 발산이 여기서 제 자리를 찾습니다. 도구는 볼록해석에서 세운 하위미분과 최적성 조건 0∈∂f(x)0 \in \partial f(x), 그리고 경사하강법의 하강 보조정리 둘이면 충분합니다.

근접 연산자

정의와 최적성

닫힌 진볼록함수 f:Rd→R∪{+∞}f : \mathbb{R}^d \to \mathbb{R} \cup \{+\infty\} 와 양수 tt 가 있을 때, 점 vv 에서의

prox⁡tf(v)=arg⁡min⁡x{f(x)+12t∥x−v∥2}\operatorname{prox}_{tf}(v) = \arg\min_x \Big\{ f(x) + \frac{1}{2t}\lVert x - v \rVert^2 \Big\}

를 근접 연산자라 부릅니다. 괄호 안은 ff 를 줄이고 싶은 마음과 vv 에서 멀리 가고 싶지 않은 마음의 타협이고, tt 가 그 비율을 정합니다. tt 가 작으면 vv 근처에 머물고, 크면 ff 의 최소점 쪽으로 끌려갑니다. 볼록함수에 12t∥x−v∥2\tfrac{1}{2t}\lVert x - v\rVert^2 를 더하면 1/t1/t-강볼록이 되므로 최소점은 언제나 존재하고 하나뿐입니다. 그래서 ff 가 미분 불가능하거나 무한대를 값으로 가져도 근접 연산자는 잘 정의된 보통의 함수입니다.

최적성 조건은 볼록해석 글의 0∈∂(⋅)0 \in \partial(\cdot) 를 괄호 전체에 쓰면 나옵니다. 이차항은 미분 가능하니 합의 하위미분이 나뉘어

0∈∂f(x)+1t(x−v)⟺v−x∈t ∂f(x)0 \in \partial f(x) + \frac{1}{t}(x - v) \quad\Longleftrightarrow\quad v - x \in t\,\partial f(x)

입니다. x=prox⁡tf(v)x = \operatorname{prox}_{tf}(v) 는 「vv 에서 tt 배 하위기울기만큼 물러선 자리」이고, 기울기가 있는 곳이라면 x=v−t∇f(x)x = v - t\nabla f(x) 입니다. 경사하강 x=v−t∇f(v)x = v - t\nabla f(v) 와 견주면 기울기를 출발점이 아니라 도착점에서 잽니다. 그래서 근접 연산자를 암묵적 경사 단계 또는 후진 오일러 단계라고도 부르고, 연산자로 쓰면 prox⁡tf=(I+t ∂f)−1\operatorname{prox}_{tf} = (I + t\,\partial f)^{-1} 입니다. 도착점에서 기울기를 재는 단계는 tt 를 아무리 키워도 발산하지 않는다는 성질이 여기서 옵니다. 경사하강이 학습률 상한 2/L을 넘으면 튀어 나가는 것과 대조됩니다.

이 연산이 하는 일을 한 문장으로 말하면, 근접 연산자는 「ff 를 기울기로 따라가는 대신 작은 최적화 문제로 통째로 푼다」입니다. 그 작은 문제가 손으로 풀리는 ff 가 생각보다 많고, 다음 세 소절이 그 대표입니다.

사영

CC 가 닫힌 볼록집합일 때, CC 안에서 0이고 밖에서 +∞+\infty 인 함수를 지시함수 ιC\iota_C 라 부릅니다. 이것을 넣으면 괄호 안의 ff 는 「CC 밖으로 나가지 마라」라는 제약이 되고 남는 것은 거리뿐입니다.

prox⁡tιC(v)=arg⁡min⁡x∈C∥x−v∥2=ΠC(v)\operatorname{prox}_{t\iota_C}(v) = \arg\min_{x \in C} \lVert x - v \rVert^2 = \Pi_C(v)

곧 CC 위로의 유클리드 사영이고, tt 와 무관합니다. 상자 [0,1]d[0,1]^d 면 성분마다 0과 1 사이로 자르는 것이고, 반지름 rr 인 공이면 vv 가 밖에 있을 때 rv/∥v∥r v / \lVert v \rVert 로 줄이는 것입니다. 그래서 다음 절의 근접 경사법은 투영 경사법을 특수경우로 품습니다. 기울기로 한 걸음 가고, 제약 밖으로 나갔으면 되돌려 놓는 그 익숙한 절차가 g=ιCg = \iota_C 인 근접 경사법입니다. 최적성 조건 v−x∈∂ιC(x)v - x \in \partial \iota_C(x) 도 사영의 익숙한 성질로 읽힙니다. ∂ιC(x)\partial \iota_C(x) 는 xx 에서 CC 바깥을 향하는 법선 방향들의 모임, 곧 법선뿔이라, vv 에서 사영점으로 내린 선이 경계에 수직이라는 말입니다.

소프트 임계값

이제 첫머리의 L1입니다. f(x)=λ∣x∣f(x) = \lambda \lvert x \rvert 를 한 좌표에서 풀고, 문턱을 τ=λt\tau = \lambda t 로 씁니다. 풀 문제는

min⁡x  τ∣x∣+12(x−v)2\min_x \; \tau \lvert x \rvert + \tfrac12 (x - v)^2

이고, 하위미분 ∂∣x∣\partial \lvert x \rvert 는 x>0x > 0 에서 {1}\{1\}, x<0x < 0 에서 {−1}\{-1\}, x=0x = 0 에서 구간 [−1,1][-1, 1] 입니다. 최적성 조건 v−x∈τ ∂∣x∣v - x \in \tau\,\partial\lvert x \rvert 를 세 경우로 나눕니다.

  • x>0x > 0 이면 v−x=τv - x = \tau, 곧 x=v−τx = v - \tau 이고, 가정 x>0x > 0 과 맞으려면 v>τv > \tau 여야 합니다.
  • x<0x < 0 이면 v−x=−τv - x = -\tau, 곧 x=v+τx = v + \tau 이고, v<−τv < -\tau 여야 합니다.
  • x=0x = 0 이면 v∈[−τ,τ]v \in [-\tau, \tau] 이기만 하면 조건이 성립합니다.

세 경우가 vv 의 실수 전체를 겹치지 않게 덮고 해는 하나뿐이므로, 답은

Sτ(v)=sign⁡(v) max⁡(∣v∣−τ, 0)S_\tau(v) = \operatorname{sign}(v)\,\max(\lvert v \rvert - \tau,\, 0)

입니다. 이 함수를 소프트 임계값이라 부릅니다. 크기가 문턱보다 작은 입력은 정확히 0으로 보내고, 큰 입력은 문턱만큼 0 쪽으로 당깁니다. τ=1\tau = 1 이면 S1(2.5)=1.5S_1(2.5) = 1.5, S1(−0.6)=0S_1(-0.6) = 0 입니다. 벡터에서는 ∥x∥1\lVert x \rVert_1 이 좌표마다 나뉘고 거리 제곱도 나뉘므로 좌표마다 따로 적용하면 됩니다.

가로축 v, 세로축 S(v) 의 좌표평면. 문턱 τ = 1 에서 −1 과 1 사이 구간이 옅게 칠해져 있고 그 위에서 파란 그래프가 0 으로 납작하다. 구간 밖에서는 기울기 1 인 직선이 각각 1 과 −1 에서 출발한다. 보라 점선은 항등 직선 y = v 다. v = 2.5 에서 1.5 로 내려간 점과 v = −0.6 에서 0 으로 간 점이 찍혀 있다

첫머리의 수수께끼가 여기서 풀립니다. 부분기울기 SGD는 w←w−η(∇ℓ+λ sign⁡(w))w \leftarrow w - \eta(\nabla \ell + \lambda\,\operatorname{sign}(w)) 이고, 0 근처의 가중치는 한 걸음마다 ηλ\eta\lambda 만큼 반대쪽으로 넘어갑니다. 정확히 0에 내려앉을 확률은 0이고, 그래서 0을 사이에 두고 진동합니다. 소프트 임계값은 0 근처의 구간 전체를 0이라는 한 점으로 접어 넣으므로 정확한 0이 양의 확률로 나옵니다. 뒤의 코드에서 같은 문제를 두 방식으로 풀면 정확한 0의 수가 0개와 38개로 갈립니다.

특잇값 수축

행렬 XX 의 특잇값의 합 ∥X∥∗=∑iσi(X)\lVert X \rVert_* = \sum_i \sigma_i(X) 를 핵노름이라 부릅니다. 특잇값 벡터의 L1 노름이고, 낮은 계수를 바라는 문제에서 L1이 희소성에 하는 일을 계수에 대해 합니다. 그 근접 연산자는 V=Udiag⁡(s)W⊤V = U \operatorname{diag}(s) W^\top 로 특잇값 분해한 뒤

prox⁡τ∥⋅∥∗(V)=Udiag⁡(Sτ(s))W⊤\operatorname{prox}_{\tau\lVert\cdot\rVert_*}(V) = U \operatorname{diag}\big(S_\tau(s)\big) W^\top

입니다. 특잇값에만 소프트 임계값을 걸고 특이벡터는 그대로 두는 연산이라 특잇값 수축이라 부릅니다. 증명의 열쇠는 폰 노이만 대각합 부등식 ⟨X,V⟩≤∑iσi(X)σi(V)\langle X, V \rangle \le \sum_i \sigma_i(X)\sigma_i(V) 하나입니다. 목적식을 전개하면 τ∥X∥∗+12∥X∥F2−⟨X,V⟩+상수\tau\lVert X\rVert_* + \tfrac12\lVert X\rVert_F^2 - \langle X, V\rangle + \text{상수} 이고, 앞의 두 항은 XX 의 특잇값에만 기대므로 셋째 항이 가장 클 때, 곧 XX 가 VV 와 같은 특이벡터를 가질 때 목적식이 가장 작습니다. 특이벡터가 정해지면 남는 문제는 특잇값마다 따로 푸는 한 좌표 L1 문제라 답이 Sτ(si)S_\tau(s_i) 입니다. V=diag⁡(3,0.5)V = \operatorname{diag}(3, 0.5), τ=1\tau = 1 이면 결과는 diag⁡(2,0)\operatorname{diag}(2, 0) 이고 계수가 2에서 1로 내려갑니다. 행렬 완성과 저계수 어댑터의 계수를 줄이는 정규화가 이 한 줄로 구현됩니다.

모로 포락

후버 함수

근접 연산자에서 최소점 대신 최솟값을 꺼내면 새 함수가 나옵니다.

Mtf(v)=min⁡x{f(x)+12t∥x−v∥2}M_{tf}(v) = \min_x \Big\{ f(x) + \frac{1}{2t}\lVert x - v\rVert^2 \Big\}

이것을 ff 의 모로 포락이라 부릅니다. 모든 xx 에 대해 f(x)f(x) 에 포물선을 걸어 그 아래쪽 껍질을 취한 것이라, ff 보다 늘 작거나 같고 ff 의 뾰족한 자리를 반지름 tt 짜리 포물선으로 깎아 낸 모양이 됩니다. f(x)=∣x∣f(x) = \lvert x \rvert 에서 직접 계산해 봅니다. 최소점이 St(v)S_t(v) 이므로 대입하면, ∣v∣≤t\lvert v \rvert \le t 일 때는 최소점이 0이라 값이 v2/(2t)v^2/(2t) 이고, ∣v∣>t\lvert v\rvert > t 일 때는 최소점이 v−tsign⁡(v)v - t\operatorname{sign}(v) 라 값이 ∣v∣−t+t/2=∣v∣−t/2\lvert v\rvert - t + t/2 = \lvert v\rvert - t/2 입니다.

Mt∣⋅∣(v)={v2/(2t)∣v∣≤t∣v∣−t/2∣v∣>tM_{t\lvert\cdot\rvert}(v) = \begin{cases} v^2/(2t) & \lvert v\rvert \le t \\ \lvert v\rvert - t/2 & \lvert v\rvert > t \end{cases}

가운데는 포물선이고 바깥은 기울기 1짜리 직선인 이 함수가 회귀의 강건 손실로 오래 써 온 후버 함수입니다. 두 조각은 ∣v∣=t\lvert v\rvert = t 에서 값도 기울기도 맞아떨어집니다. t=1t = 1 이면 v=0.5v = 0.5 에서 0.125, v=2v = 2 에서 1.5이고, 원래 함수의 0.5와 2보다 각각 작습니다. 이상치에 덜 민감한 손실로 알려진 후버 손실이 사실은 절댓값을 근접 연산으로 매끄럽게 만든 것이었습니다.

가로축 v, 세로축 함숫값의 좌표평면. 보라 점선이 절댓값 |v| 의 V자이고, 파란 곡선이 t = 1 인 후버 함수다. −1 과 1 사이에서는 포물선 v²/2 이고 바깥에서는 |v| − 1/2 로 V자와 평행하게 0.5 아래에 있다. v = 0.5 의 0.125 와 v = 2 의 1.5 에 점이 있다

포락의 기울기

모로 포락은 ff 가 미분 불가능해도 언제나 미분 가능하고, 기울기가

∇Mtf(v)=1t(v−prox⁡tf(v))\nabla M_{tf}(v) = \frac{1}{t}\big(v - \operatorname{prox}_{tf}(v)\big)

입니다. 후버 함수로 확인하면 ∣v∣≤t\lvert v\rvert \le t 에서 v/tv/t, 바깥에서 sign⁡(v)\operatorname{sign}(v) 라 위 식과 맞습니다. 이 기울기가 1/t1/t-립시츠라는 것, 곧 모로 포락이 1/t1/t-매끄럽다는 것은 근접 연산자의 성질 하나에서 나옵니다. p=prox⁡(u)p = \operatorname{prox}(u), q=prox⁡(v)q = \operatorname{prox}(v) 라 하면 최적성 조건으로 (u−p)/t∈∂f(p)(u - p)/t \in \partial f(p), (v−q)/t∈∂f(q)(v - q)/t \in \partial f(q) 이고, 볼록함수의 하위미분은 단조라 ⟨(u−p)−(v−q), p−q⟩≥0\langle (u - p) - (v - q),\, p - q\rangle \ge 0 입니다. 정리하면

∥p−q∥2≤⟨p−q, u−v⟩\lVert p - q\rVert^2 \le \langle p - q,\, u - v\rangle

이고, 이 성질을 확고한 비팽창이라 부릅니다. 코시–슈바르츠를 붙이면 ∥p−q∥≤∥u−v∥\lVert p - q\rVert \le \lVert u - v\rVert 라 근접 연산자는 거리를 늘리지 않고, 같은 부등식에서 I−prox⁡I - \operatorname{prox} 도 확고히 비팽창이라 포락의 기울기가 1/t1/t-립시츠가 됩니다. 반복법의 수렴 증명이 기대는 것이 이 부등식입니다. 근접 연산자를 몇 번을 이어 붙여도 오차가 증폭되지 않습니다.

최소점이 바뀌지 않는다는 것도 중요합니다. MtfM_{tf} 의 최솟값과 최소점은 ff 의 것과 같습니다. 그래서 매끄럽지 않은 ff 를 최소화하는 대신 1/t1/t-매끄러운 MtfM_{tf} 에 경사하강을 학습률 tt 로 돌릴 수 있고, 그 한 걸음 v−t∇Mtf(v)v - t\nabla M_{tf}(v) 는 정확히 prox⁡tf(v)\operatorname{prox}_{tf}(v) 입니다. 근접점 반복법이 모로 포락 위의 경사하강이라는 이 관점이 매끄럽지 않은 문제를 매끄러운 이론으로 옮겨 오는 통로입니다.

모로 분해

지난 글의 켤레함수가 여기서 근접 연산자와 맞물립니다. t=1t = 1 일 때

v=prox⁡f(v)+prox⁡f∗(v)v = \operatorname{prox}_f(v) + \operatorname{prox}_{f^*}(v)

이 모든 vv 에서 성립하고, 이것을 모로 분해라 부릅니다. 증명은 최적성 조건과 지난 글의 펜첼–영 등식입니다. x=prox⁡f(v)x = \operatorname{prox}_f(v) 이면 y=v−x∈∂f(x)y = v - x \in \partial f(x) 이고, 이것은 x∈∂f∗(y)x \in \partial f^*(y) 와 같은 말이라 v−y=x∈∂f∗(y)v - y = x \in \partial f^*(y), 곧 y=prox⁡f∗(v)y = \operatorname{prox}_{f^*}(v) 입니다. 선형대수의 직교 분해 v=ΠWv+ΠW⊥vv = \Pi_W v + \Pi_{W^\perp} v 를 볼록함수로 일반화한 것입니다. 절댓값으로 확인하면 ∣⋅∣\lvert\cdot\rvert 의 켤레가 구간 [−1,1][-1,1] 의 지시함수이고 그 근접 연산자는 [−1,1][-1,1] 로 자르기라, v=S1(v)+clip⁡(v,−1,1)v = S_1(v) + \operatorname{clip}(v, -1, 1) 입니다. v=2.5v = 2.5 이면 1.5+11.5 + 1 이고 v=−0.6v = -0.6 이면 0+(−0.6)0 + (-0.6) 입니다. 한쪽 근접 연산자가 어려우면 켤레 쪽을 풀고 빼면 된다는 것이 실용적인 쓰임입니다.

근접 경사법

ISTA

이제 첫머리의 목적식을 그대로 씁니다. 매끄러운 데이터 항 ff 와 매끄럽지 않지만 근접 연산자가 쉬운 정규화 항 gg 의 합

F(x)=f(x)+g(x)F(x) = f(x) + g(x)

를 복합 목적식이라 부릅니다. ∇f\nabla f 가 LL-립시츠이면 경사하강 글의 하강 보조정리가 f(x)≤f(y)+⟨∇f(y),x−y⟩+L2∥x−y∥2f(x) \le f(y) + \langle \nabla f(y), x - y\rangle + \tfrac{L}{2}\lVert x - y\rVert^2 를 주고, 오른쪽은 ff 를 yy 에서 위로 덮는 포물면입니다. 매끄러운 부분만 이 포물면으로 갈아 끼우고 gg 는 그대로 둔 채 최소화하면

x+=arg⁡min⁡x{⟨∇f(y),x−y⟩+L2∥x−y∥2+g(x)}=prox⁡g/L(y−∇f(y)/L)\begin{aligned} x^+ &= \arg\min_x \Big\{ \langle \nabla f(y), x - y\rangle + \frac{L}{2}\lVert x - y\rVert^2 + g(x) \Big\} \\ &= \operatorname{prox}_{g/L}\big(y - \nabla f(y)/L\big) \end{aligned}

입니다. 둘째 줄은 첫 줄의 이차식을 완전제곱으로 묶은 것입니다. ff 로는 기울기 한 걸음, gg 로는 근접 한 걸음이라 이 반복을 근접 경사법이라 부르고, g=λ∥⋅∥1g = \lambda\lVert\cdot\rVert_1 이면 근접 단계가 소프트 임계값이라 ISTA(반복 소프트 임계값 알고리즘)라는 이름이 붙었습니다. 고정점 x=prox⁡g/L(x−∇f(x)/L)x = \operatorname{prox}_{g/L}(x - \nabla f(x)/L) 은 최적성 조건으로 풀면 0∈∇f(x)+∂g(x)0 \in \nabla f(x) + \partial g(x) 이고, 이것이 곧 FF 의 최적성 조건이라 ISTA가 멈추는 자리가 정확히 최소점입니다.

수렴률은 매끄러운 경사하강과 같습니다. 학습률 1/L1/L 에서 F(xk)−F∗≤L∥x0−x∗∥2/(2k)F(x_k) - F^* \le L\lVert x_0 - x^*\rVert^2/(2k) 이고, 매 걸음 FF 가 줄어든다는 것도 같습니다. 근접 단계가 gg 의 미분 불가능성을 통째로 흡수했기 때문에, 부분기울기법의 O(1/k)O(1/\sqrt{k}) 가 아니라 매끄러운 문제의 O(1/k)O(1/k) 가 그대로 살아남습니다. 매끄럽지 않은 항을 기울기로 밀지 않은 값이 수렴률로 돌아오는 셈입니다.

FISTA

모멘텀과 네스테로프의 가속을 근접 경사법에 붙인 것이 FISTA입니다. t1=1t_1 = 1, y1=x0y_1 = x_0 에서 시작해

xk=prox⁡g/L(yk−∇f(yk)/L)tk+1=12(1+1+4tk2)yk+1=xk+tk−1tk+1 (xk−xk−1)\begin{aligned} x_k &= \operatorname{prox}_{g/L}\big(y_k - \nabla f(y_k)/L\big) \\ t_{k+1} &= \tfrac12\Big(1 + \sqrt{1 + 4t_k^2}\Big) \\ y_{k+1} &= x_k + \frac{t_k - 1}{t_{k+1}}\,(x_k - x_{k-1}) \end{aligned}

을 반복합니다. 근접 단계를 현재 점이 아니라 지난 이동 방향으로 조금 더 밀어 놓은 점 yky_k 에서 합니다. tkt_k 는 1,1.618,2.194,…1, 1.618, 2.194, \dots 로 자라고, 밀어 주는 계수 (tk−1)/tk+1(t_k - 1)/t_{k+1} 은 0에서 출발해 1로 다가갑니다. 이렇게 하면 수렴률이

F(xk)−F∗≤2L∥x0−x∗∥2(k+1)2F(x_k) - F^* \le \frac{2L\lVert x_0 - x^*\rVert^2}{(k+1)^2}

으로 한 차수 올라갑니다. 증명 개요는 이렇습니다. 근접 경사 한 걸음 x+=T(y)x^+ = T(y) 에 대해 모든 zz 에서

F(x+)≤F(z)+L2(∥y−z∥2−∥x+−z∥2)F(x^+) \le F(z) + \frac{L}{2}\big(\lVert y - z\rVert^2 - \lVert x^+ - z\rVert^2\big)

가 성립합니다. 하강 보조정리와 근접 단계의 최적성 조건, ff 와 gg 의 볼록성을 차례로 쓰면 나오는 부등식입니다. 이것을 z=(1−1/tk+1)xk+x∗/tk+1z = (1 - 1/t_{k+1})x_k + x^*/t_{k+1} 에 쓰고 FF 의 볼록성으로 F(z)F(z) 를 쪼갠 뒤 양변에 tk+12t_{k+1}^2 을 곱합니다. 이때 tkt_k 의 점화식이 정확히 tk+12−tk+1=tk2t_{k+1}^2 - t_{k+1} = t_k^2 이 되도록 골라져 있어서, 오차 δk=F(xk)−F∗\delta_k = F(x_k) - F^* 와 보조 점 uk=tkxk−(tk−1)xk−1−x∗u_k = t_k x_k - (t_k - 1)x_{k-1} - x^* 로 만든 양

Ek=tk2 δk+L2∥uk∥2E_k = t_k^2\,\delta_k + \frac{L}{2}\lVert u_k\rVert^2

이 매 걸음 늘지 않습니다. 그러면 tk2δk≤E1≤L2∥x0−x∗∥2t_k^2 \delta_k \le E_1 \le \tfrac{L}{2}\lVert x_0 - x^*\rVert^2 이고, 귀납으로 tk≥(k+1)/2t_k \ge (k+1)/2 이니 위의 O(1/k2)O(1/k^2) 가 나옵니다. 이 차수는 1차 정보만 쓰는 방법의 하한과 같아 더 올릴 수 없습니다. 하한 쪽 계산은 고급 14번에서 다룹니다. 대가는 단조성입니다. ISTA와 달리 FISTA의 F(xk)F(x_k) 는 가끔 올라가고, 그래서 실무에서는 값이 오를 때 tkt_k 를 1로 되돌리는 재시작을 흔히 붙입니다.

ADMM

근접 연산자가 쉬운 항이 둘인데 둘의 합은 쉽지 않을 때가 있습니다. 예를 들어 ff 가 최소제곱이고 gg 가 L1이면 각자는 쉬운데 합의 근접 연산자는 닫힌 꼴이 없습니다. 이때 변수를 둘로 복제해 min⁡f(x)+g(z)\min f(x) + g(z), 제약 x=zx = z 로 쓰고 라그랑주 승수 yy 에 벌점 ρ2∥x−z∥2\tfrac{\rho}{2}\lVert x - z\rVert^2 을 더한

Lρ(x,z,y)=f(x)+g(z)+⟨y,x−z⟩+ρ2∥x−z∥2\mathcal{L}_\rho(x, z, y) = f(x) + g(z) + \langle y, x - z\rangle + \frac{\rho}{2}\lVert x - z\rVert^2

을 증강 라그랑지언이라 부릅니다. 이것을 xx 에 대해 한 번, zz 에 대해 한 번 최소화하고 승수를 제약 위반만큼 올리는 세 걸음이 ADMM(교대 방향 승수법)입니다. 승수를 u=y/ρu = y/\rho 로 줄여 쓰면 세 걸음이 전부 근접 연산자로 적힙니다.

x←prox⁡f/ρ(z−u)z←prox⁡g/ρ(x+u)u←u+x−z\begin{aligned} x &\leftarrow \operatorname{prox}_{f/\rho}(z - u) \\ z &\leftarrow \operatorname{prox}_{g/\rho}(x + u) \\ u &\leftarrow u + x - z \end{aligned}

셋째 걸음은 쌍대 변수의 경사상승이고, 지난 글의 쌍대 문제를 위로 올라가는 한 걸음입니다. 앞의 두 걸음이 서로 다른 기계에서 돌 수 있다는 것이 ADMM이 분산 학습과 대규모 볼록 문제에서 널리 쓰여 온 까닭이고, 수렴은 f,gf, g 가 볼록이기만 하면 ρ\rho 와 무관하게 보장됩니다. 다만 빠르기는 ρ\rho 에 민감하고, 정밀도가 높은 해가 필요하면 느립니다.

가중치 감쇠

이제 AdamW로 돌아갑니다. g(w)=λ2∥w∥2g(w) = \tfrac{\lambda}{2}\lVert w\rVert^2 의 근접 연산자는 최적성 조건 v−w=tλwv - w = t\lambda w 에서 바로 나와

prox⁡tg(v)=v1+tλ≈(1−tλ) v\operatorname{prox}_{tg}(v) = \frac{v}{1 + t\lambda} \approx (1 - t\lambda)\,v

입니다. 근사는 tλt\lambda 가 작을 때의 1차 전개입니다. Adam을 조립한 글에서 Adam의 방향은 d=m^/(v^+ϵ)d = \hat m/(\sqrt{\hat v} + \epsilon) 이었습니다. 감쇠 항을 손실에 넣으면 그 기울기 λw\lambda w 가 m^\hat m 에 섞여 들어가 좌표마다 v^\sqrt{\hat v} 로 나뉩니다. 기울기가 큰 좌표일수록 감쇠가 약해지는 셈이고, 이것은 정규화 항이 의도한 것과 다릅니다. 반대로 감쇠를 근접 단계로 떼어 내면 갱신은

w←prox⁡ηg(w−ηd)=w−ηd1+ηλw \leftarrow \operatorname{prox}_{\eta g}\big(w - \eta d\big) = \frac{w - \eta d}{1 + \eta\lambda}

이고, 1차까지 쓰면 w−ηd−ηλww - \eta d - \eta\lambda w 라 AdamW의 갱신식과 같습니다. 이렇게 감쇠를 프리컨디셔너 밖에서 근접 단계로 적용하는 것을 분리형 가중치 감쇠라 부릅니다. 손실의 매끄러운 부분은 Adam의 기하로, 정규화 항은 유클리드 근접 단계로, 각자 제 기하에서 처리한다는 것이 AdamW의 정당화입니다. 같은 구조에 g=λ∥⋅∥1g = \lambda\lVert\cdot\rVert_1 을 넣으면 Adam 한 걸음 뒤 소프트 임계값을 거는 희소 학습이 되고, 첫머리의 팀이 원한 정확한 0이 거기서 나옵니다.

브레그만 발산

발산의 정의

경사하강 한 걸음을 근접 연산자의 말로 다시 적으면

xk+1=arg⁡min⁡x{⟨∇f(xk),x⟩+12η∥x−xk∥2}x_{k+1} = \arg\min_x \Big\{ \langle \nabla f(x_k), x\rangle + \frac{1}{2\eta}\lVert x - x_k\rVert^2 \Big\}

입니다. 선형 근사를 따라 내려가되 유클리드 거리의 제곱으로 걸음을 묶어 둔 것입니다. 이 거리를 바꿔 끼우는 것이 후반부의 생각이고, 바꿔 끼울 후보를 만드는 공식이 이것입니다. 미분 가능한 강볼록함수 φ\varphi 에 대해

Dφ(x,y)=φ(x)−φ(y)−⟨∇φ(y), x−y⟩D_\varphi(x, y) = \varphi(x) - \varphi(y) - \langle \nabla\varphi(y),\, x - y\rangle

를 브레그만 발산이라 부릅니다. φ\varphi 와 그 yy 에서의 접평면 사이의 높이 차이를 xx 에서 잰 것이고, 볼록성 때문에 늘 0 이상이며 x=yx = y 일 때만 0입니다. φ(x)=12∥x∥2\varphi(x) = \tfrac12\lVert x\rVert^2 이면 Dφ(x,y)=12∥x−y∥2D_\varphi(x, y) = \tfrac12\lVert x - y\rVert^2 로 위의 유클리드 항이 그대로 나오니, 브레그만 발산은 거리 제곱을 일반화한 것입니다. 다만 대칭이 아니고 삼각 부등식도 성립하지 않아 거리가 아니라 발산이라 부릅니다.

음의 엔트로피와 KL

확률 단체 Δd={x≥0, ∑ixi=1}\Delta_d = \{x \ge 0,\ \sum_i x_i = 1\} 위에서 가장 중요한 선택은 음의 엔트로피 φ(x)=∑ixilog⁡xi\varphi(x) = \sum_i x_i \log x_i 입니다. 기울기가 ∇φ(y)i=log⁡yi+1\nabla\varphi(y)_i = \log y_i + 1 이니 정의에 넣으면

Dφ(x,y)=∑ixilog⁡xi−∑iyilog⁡yi−∑i(log⁡yi+1)(xi−yi)=∑ixilog⁡xiyi−∑ixi+∑iyi\begin{aligned} D_\varphi(x, y) &= \sum_i x_i\log x_i - \sum_i y_i\log y_i - \sum_i (\log y_i + 1)(x_i - y_i) \\ &= \sum_i x_i \log\frac{x_i}{y_i} - \sum_i x_i + \sum_i y_i \end{aligned}

입니다. 둘째 줄에서 yilog⁡yiy_i\log y_i 항이 서로 지워졌습니다. 두 점이 모두 단체 위에 있으면 뒤의 두 합이 1과 1이라 지워지고, 남는 것이 정확히 KL(x∥y)\mathrm{KL}(x \Vert y) 입니다. 단체 밖의 양수 벡터에서는 뒤 두 항이 남는데 이것을 일반화된 KL이라 부릅니다. KL이 비대칭인 것은 이 계산에서 바로 보입니다. 접평면을 yy 에서 그었으니 xx 와 yy 의 역할이 다릅니다.

이 발산이 단체에 잘 맞는 데에는 기하적인 이유가 있습니다. yy 의 한 좌표가 0에 다가가면 log⁡(xi/yi)\log(x_i/y_i) 가 무한대로 가므로, KL로 걸음을 묶으면 단체의 경계에 가까울수록 걸음이 저절로 짧아집니다. 유클리드 거리는 경계 근처에서도 똑같이 재기 때문에 사영으로 되돌려 놓아야 하지만, KL은 경계를 넘지 않게 하는 장벽을 기하 안에 품고 있습니다.

세 점 항등식

뒤의 수렴 분석이 기대는 항등식 하나를 적어 둡니다. 정의를 세 번 펼쳐 빼 보면

⟨∇φ(y)−∇φ(z), x−y⟩=Dφ(x,z)−Dφ(x,y)−Dφ(y,z)\langle \nabla\varphi(y) - \nabla\varphi(z),\, x - y\rangle = D_\varphi(x, z) - D_\varphi(x, y) - D_\varphi(y, z)

가 모든 x,y,zx, y, z 에서 성립합니다. φ=12∥⋅∥2\varphi = \tfrac12\lVert\cdot\rVert^2 이면 이것은 ∥x−z∥2=∥x−y∥2+∥y−z∥2+2⟨x−y,y−z⟩\lVert x - z\rVert^2 = \lVert x - y\rVert^2 + \lVert y - z\rVert^2 + 2\langle x - y, y - z\rangle 라는 코사인 법칙이고, 브레그만 발산에서도 그 법칙이 모양을 바꾸지 않고 살아남는다는 말입니다. 유클리드 경사하강의 수렴 증명은 이 법칙으로 ∥xk−x∗∥2\lVert x_k - x^*\rVert^2 이 얼마나 줄었는지를 쟀는데, 거울 하강에서는 같은 자리에 Dφ(x∗,xk)D_\varphi(x^*, x_k) 가 들어가고 증명의 나머지 줄은 그대로입니다.

거울 하강

거울 사상

유클리드 항을 브레그만 발산으로 바꾼 한 걸음

xk+1=arg⁡min⁡x{η ⟨gk,x⟩+Dφ(x,xk)}x_{k+1} = \arg\min_{x} \Big\{ \eta\,\langle g_k, x\rangle + D_\varphi(x, x_k) \Big\}

을 거울 하강이라 부릅니다. gkg_k 는 xkx_k 에서 잰 기울기 또는 하위기울기입니다. 제약이 없고 φ\varphi 가 매끄러우면 최적성 조건은 ηgk+∇φ(xk+1)−∇φ(xk)=0\eta g_k + \nabla\varphi(x_{k+1}) - \nabla\varphi(x_k) = 0, 곧

∇φ(xk+1)=∇φ(xk)−η gk\nabla\varphi(x_{k+1}) = \nabla\varphi(x_k) - \eta\,g_k

입니다. 이 식이 이름의 뜻을 말해 줍니다. ∇φ\nabla\varphi 는 원래 공간의 점을 기울기가 사는 공간, 곧 쌍대 공간으로 보내는 사상이고, 이것을 거울 사상이라 부릅니다. 거울 하강은 점을 거울 너머로 비춰 보내고, 거기서 평범한 경사 한 걸음을 디딘 뒤, 다시 비춰 돌아옵니다. 돌아오는 사상은 (∇φ)−1(\nabla\varphi)^{-1} 이고, 지난 글의 켤레 계산으로 이것이 ∇φ∗\nabla\varphi^* 입니다. 펜첼–영 부등식이 등호가 되는 짝이 y=∇φ(x)y = \nabla\varphi(x) 와 x=∇φ∗(y)x = \nabla\varphi^*(y) 였기 때문입니다.

왼쪽 상자는 원래 공간의 점 x_k, 오른쪽 상자는 쌍대 공간의 점 θ_k. 위쪽 화살표 ∇φ 가 x_k 를 θ_k 로 보내고, 오른쪽에서 θ_k 가 θ_k − η g_k 로 내려가는 경사 한 걸음이 있다. 아래쪽 화살표 ∇φ* 가 그것을 원래 공간의 x_{k+1} 로 돌려보낸다. 아래 줄에는 φ = ½‖x‖² 이면 두 사상이 항등이라 경사하강, φ = Σ x log x 이면 log 와 softmax 라 지수가중 갱신이라고 적혀 있다

φ=12∥x∥2\varphi = \tfrac12\lVert x\rVert^2 이면 거울 사상이 항등이라 거울 하강은 그냥 경사하강입니다. 경사하강은 유클리드 기하를 고른 거울 하강의 특수경우이고, 이것이 제목의 「기하를 바꿔서 내려가기」입니다. 어떤 φ\varphi 를 고르느냐는 문제의 정의역과 기울기의 크기를 어떤 노름으로 재는 것이 자연스러운가로 정합니다.

지수가중 갱신

단체 위에서 φ\varphi 를 음의 엔트로피로 고르면 무엇이 나오는지 끝까지 풉니다. 풀 문제는

min⁡x∈Δd  η⟨g,x⟩+∑ixilog⁡xixk,i\min_{x \in \Delta_d} \; \eta\langle g, x\rangle + \sum_i x_i\log\frac{x_i}{x_{k,i}}

입니다. 단체 위의 KL에서 −∑xi+∑xk,i-\sum x_i + \sum x_{k,i} 는 상수라 뺐습니다. 등식 제약 ∑ixi=1\sum_i x_i = 1 에 승수 ν\nu 를 붙이고, 부등식 xi≥0x_i \ge 0 은 일단 두고 풉니다. 라그랑지언을 xix_i 로 미분하면 ηgi+log⁡(xi/xk,i)+1+ν=0\eta g_i + \log(x_i/x_{k,i}) + 1 + \nu = 0 이고, 이것을 xix_i 에 대해 풀면

xi=xk,i e−ηgi e−1−νx_i = x_{k,i}\, e^{-\eta g_i}\, e^{-1-\nu}

입니다. ν\nu 는 합이 1이 되도록 정해지므로 e−1−ν=1/∑jxk,je−ηgje^{-1-\nu} = 1/\sum_j x_{k,j}e^{-\eta g_j} 이고, 결국

xk+1,i=xk,i e−ηgi∑jxk,j e−ηgjx_{k+1,i} = \frac{x_{k,i}\,e^{-\eta g_i}}{\sum_j x_{k,j}\,e^{-\eta g_j}}

입니다. 남은 확인은 둘입니다. 첫째, 이 해는 모든 좌표가 양수라 두고 풀었던 부등식 제약이 비활성이고, 그래서 그 승수는 0이라 KKT 조건이 전부 성립합니다. 둘째, 목적식은 선형 항과 강볼록인 KL의 합이라 강볼록이고, 볼록 문제에서 KKT 조건은 충분조건이니 이 점이 유일한 최소점입니다. 이것으로 증명이 끝납니다.

각 좌표에 기울기의 지수를 곱하고 다시 정규화하는 이 갱신을 지수가중 갱신이라 부르고, 전문가 조언 문제에서는 곱셈 가중치 방법, 부스팅에서는 AdaBoost의 표본 가중치 갱신으로 나타납니다. 로그를 취하면 log⁡xk+1=log⁡xk−ηg−상수\log x_{k+1} = \log x_k - \eta g - \text{상수} 라, 지난 글에서 본 대로 음의 엔트로피의 거울 사상이 로그이고 돌아오는 사상이 softmax입니다. 거울 너머에서는 로짓에 평범한 경사 한 걸음을 디디고, 돌아올 때 softmax를 씌우는 것입니다.

숫자로 세 걸음 따라갑니다. 네 좌표에 고정된 선형 비용 c=(0.3,0.5,0.1,0.7)c = (0.3, 0.5, 0.1, 0.7) 이 있고 균등 분포 (0.25,0.25,0.25,0.25)(0.25, 0.25, 0.25, 0.25) 에서 η=2\eta = 2 로 출발합니다. 곱할 인자는 e−0.6=0.549e^{-0.6} = 0.549, e−1=0.368e^{-1} = 0.368, e−0.2=0.819e^{-0.2} = 0.819, e−1.4=0.247e^{-1.4} = 0.247 이고 합이 1.982라, 첫 걸음 뒤 분포는 (0.277,0.186,0.413,0.124)(0.277, 0.186, 0.413, 0.124) 입니다. 같은 인자를 두 번 더 곱하면 셋째 걸음 뒤 (0.212,0.064,0.705,0.019)(0.212, 0.064, 0.705, 0.019) 가 되어 비용이 가장 작은 셋째 좌표로 질량이 몰립니다. 어느 좌표도 0이 되지 않고, 비용이 큰 좌표일수록 지수적으로 빨리 줄어듭니다.

네 좌표를 가로로 늘어놓고 좌표마다 걸음 0, 1, 2, 3 의 막대 네 개를 세운 막대그래프. 비용 c 는 좌표 아래에 0.3, 0.5, 0.1, 0.7 로 적혀 있다. 셋째 좌표의 막대는 0.25, 0.413, 0.574, 0.705 로 자라고 넷째 좌표는 0.25, 0.124, 0.052, 0.019 로 줄어든다

후회 경계

이 기하가 무엇을 버는지는 온라인 볼록 최적화에서 가장 선명합니다. 매 라운드 kk 에 단체 위의 점 xkx_k 를 내고 나서 볼록 손실 ℓk\ell_k 를 받습니다. 지나고 보니 가장 좋았던 고정점 x∗x^* 와의 누적 손실 차

RegretT=∑k=1Tℓk(xk)−∑k=1Tℓk(x∗)\mathrm{Regret}_T = \sum_{k=1}^T \ell_k(x_k) - \sum_{k=1}^T \ell_k(x^*)

를 후회라 부릅니다. 볼록성으로 각 항은 ⟨gk,xk−x∗⟩\langle g_k, x_k - x^*\rangle 이하이고, 세 점 항등식으로 이것을 Dφ(x∗,xk)−Dφ(x∗,xk+1)D_\varphi(x^*, x_k) - D_\varphi(x^*, x_{k+1}) 의 망원 합과 한 걸음의 크기로 나누면

RegretT≤Dφ(x∗,x1)η+η2∑k=1T∥gk∥∗2\mathrm{Regret}_T \le \frac{D_\varphi(x^*, x_1)}{\eta} + \frac{\eta}{2}\sum_{k=1}^T \lVert g_k\rVert_*^2

를 얻습니다. 여기서 φ\varphi 는 어떤 노름 ∥⋅∥\lVert\cdot\rVert 에 대해 1-강볼록이어야 하고 ∥⋅∥∗\lVert\cdot\rVert_* 는 그 쌍대 노름입니다. 음의 엔트로피는 핀스커 부등식 덕분에 단체 위에서 L1 노름에 대해 1-강볼록이고, 쌍대 노름은 L∞입니다. 균등 분포에서 출발하면 Dφ(x∗,x1)≤log⁡dD_\varphi(x^*, x_1) \le \log d 입니다. 기울기의 각 좌표가 GG 이하라 하고 η\eta 를 최적으로 고르면 후회가 G2Tlog⁡dG\sqrt{2T\log d} 이하입니다. 같은 문제를 유클리드 투영 경사법으로 풀면 기울기를 L2 노름으로 재야 해서 ∥g∥2≤Gd\lVert g\rVert_2 \le G\sqrt d 가 들어가고, 후회는 GTdG\sqrt{Td} 차수가 됩니다. 좌표가 백만 개이면 log⁡d≈13.8\log d \approx 13.8 과 d=106d = 10^6 의 차이라, 기하를 바꾼 값이 차원의 다항식에서 로그로의 이득으로 돌아옵니다.

KL 제약 정책

KL 제약 보상 최대화에서는 max⁡πEπ[r]−β KL(π∥πref)\max_\pi \mathbb{E}_\pi[r] - \beta\,\mathrm{KL}(\pi\Vert\pi_{\text{ref}}) 의 해가 π∗∝πrefexp⁡(r/β)\pi^* \propto \pi_{\text{ref}}\exp(r/\beta) 라는 것을 라그랑주 승수로 유도했습니다. 지수가중 갱신과 나란히 놓으면 같은 식입니다. 손실이 보상의 음수라 기울기가 g=−rg = -r 이고, 출발점이 πref\pi_{\text{ref}} 이며 학습률이 η=1/β\eta = 1/\beta 인 거울 하강 한 걸음이

πnew(a)∝πref(a) er(a)/β\pi_{\text{new}}(a) \propto \pi_{\text{ref}}(a)\,e^{r(a)/\beta}

이기 때문입니다. RLHF의 KL 정규화 목적식은 기준 정책에서 출발한 거울 하강의 정확히 한 걸음이고, β\beta 가 그 걸음의 크기를 정합니다. 이 관점에서 TRPO와 MDPO 계열이 정책 갱신의 크기를 KL로 재는 것은 우연이 아닙니다. 매 반복 πk+1∝πkexp⁡(ηAk)\pi_{k+1} \propto \pi_k\exp(\eta A_k) 꼴로 이점 함수 AkA_k 방향의 거울 하강을 하는 것이고, 앞의 후회 분석이 그대로 수렴 보장으로 옮겨 갑니다. 거꾸로 DPO가 닫힌 해에서 출발할 수 있었던 것도, 한 걸음짜리 거울 하강은 언제나 손으로 풀린다는 이 절의 계산 덕분입니다.

다시 희소 가중치로

코드로 확인하기

첫머리의 두 질문을 숫자로 확인합니다. 정답이 여덟 좌표에만 있는 200차원 라소 문제를 표본 60개로 만들고, ISTA와 FISTA를 같은 학습률 1/L1/L 로 돌린 뒤, 같은 문제를 부분기울기법으로도 풉니다. 마지막 몇 줄은 본문의 지수가중 갱신 세 걸음입니다.

import numpy as np

rng = np.random.default_rng(0)
n, p, k = 60, 200, 8
A = rng.standard_normal((n, p)) / np.sqrt(n)
x_true = np.zeros(p); x_true[:k] = rng.choice([-1, 1], k) * 2.0
b = A @ x_true + 0.05 * rng.standard_normal(n)
lam = 0.05
L = np.linalg.norm(A, 2) ** 2          # ∇f 의 립시츠 상수

def F(x):
    return 0.5 * np.sum((A @ x - b) ** 2) + lam * np.abs(x).sum()

def soft(v, t):
    return np.sign(v) * np.maximum(np.abs(v) - t, 0.0)

def ista(T):
    x = np.zeros(p)
    for _ in range(T):
        x = soft(x - A.T @ (A @ x - b) / L, lam / L)
    return x

def fista(T):
    x = y = np.zeros(p); t = 1.0
    for _ in range(T):
        x_new = soft(y - A.T @ (A @ y - b) / L, lam / L)
        t_new = (1 + np.sqrt(1 + 4 * t * t)) / 2
        y = x_new + (t - 1) / t_new * (x_new - x)
        x, t = x_new, t_new
    return x

F_star = F(fista(20000))
print(f"L = {L:.3f}")
for T in [10, 100, 1000]:
    xi, xf = ista(T), fista(T)
    print(f"T={T:5d}  ISTA gap {F(xi)-F_star:.2e}  FISTA gap {F(xf)-F_star:.2e}"
          f"  nonzeros {np.count_nonzero(xi):3d} / {np.count_nonzero(xf):3d}")

# 같은 문제를 부분기울기법으로: 정확한 0 이 몇 개나 나오는가
x = np.zeros(p)
for s in range(1000):
    g = A.T @ (A @ x - b) + lam * np.sign(x)
    x -= g / L
print("subgradient: exact zeros", np.sum(x == 0), " |x|<1e-3:", np.sum(np.abs(x) < 1e-3))

# 단체 위 거울 하강 = 지수가중 갱신
c = np.array([0.3, 0.5, 0.1, 0.7])      # 선형 비용 <c, w>
w = np.full(4, 0.25); eta = 2.0
for s in range(1, 4):
    w = w * np.exp(-eta * c); w /= w.sum()
    print(f"step {s}: w = {np.round(w, 3)}")
L = 7.382
T=   10  ISTA gap 5.15e-01  FISTA gap 4.09e-01  nonzeros 158 / 137
T=  100  ISTA gap 1.93e-01  FISTA gap 5.01e-04  nonzeros  88 /  38
T= 1000  ISTA gap 6.66e-07  FISTA gap 2.96e-11  nonzeros  38 /  38
subgradient: exact zeros 0  |x|<1e-3: 13
step 1: w = [0.277 0.186 0.413 0.124]
step 2: w = [0.258 0.116 0.574 0.052]
step 3: w = [0.212 0.064 0.705 0.019]

읽을 것은 셋입니다. 백 걸음에서 FISTA의 간극은 ISTA보다 세 자릿수 가까이 작고, 0이 아닌 좌표 수도 이미 최종값 38에 닿아 있습니다. 가속이 값뿐 아니라 희소 패턴을 찾는 속도도 앞당긴 것입니다. 부분기울기법은 천 걸음을 돌아도 정확한 0이 하나도 없고, 10−310^{-3} 보다 작은 좌표가 열세 개 있을 뿐입니다. 첫머리의 히스토그램이 이것이었습니다. 마지막 세 줄은 본문의 손계산과 소수 셋째 자리까지 같습니다.

연습

  1. 문턱이 τ=0.4\tau = 0.4 인 소프트 임계값을 벡터 v=(−1.7, 0.3, 0.9)v = (-1.7,\ 0.3,\ 0.9) 에 걸면 무엇이 나오나요.
    좌표마다 크기에서 0.4를 빼고 음수면 0으로 둡니다. −1.7-1.7 은 −1.3-1.3, 0.30.3 은 크기가 문턱보다 작아 00, 0.90.9 는 0.50.5 라 결과는 (−1.3, 0, 0.5)(-1.3,\ 0,\ 0.5) 입니다.
  2. 상자 [0,1]3[0, 1]^3 의 지시함수에 대한 근접 연산자를 v=(1.4, −0.2, 0.5)v = (1.4,\ -0.2,\ 0.5) 에 적용하고, 그 결과가 tt 에 기대는지 답하세요.
    지시함수의 근접 연산자는 사영이라 성분마다 0과 1 사이로 자릅니다. (1, 0, 0.5)(1,\ 0,\ 0.5) 이고, 사영은 tt 와 무관합니다.
  3. g(w)=12w2g(w) = \tfrac12 w^2 에 계수 tλ=0.1t\lambda = 0.1 을 건 근접 연산자를 v=2v = 2 에 적용한 값과, 그 1차 근사인 곱셈 감쇠 (1−tλ)v(1 - t\lambda)v 의 값을 각각 구하세요.
    근접 연산자는 v/(1+tλ)=2/1.1=1.818v/(1 + t\lambda) = 2/1.1 = 1.818 이고, 1차 근사는 0.9×2=1.80.9 \times 2 = 1.8 입니다. 차이 0.018은 tλt\lambda 의 제곱 차수입니다.
  4. 절댓값의 모로 포락을 t=0.5t = 0.5 로 만들 때 v=0.4v = 0.4 와 v=3v = 3 에서의 값을 구하세요.
    ∣v∣≤t\lvert v\rvert \le t 이면 v2/(2t)v^2/(2t) 라 0.16/1=0.160.16/1 = 0.16 이고, ∣v∣>t\lvert v\rvert > t 이면 ∣v∣−t/2\lvert v\rvert - t/2 라 3−0.25=2.753 - 0.25 = 2.75 입니다.
  5. 두 좌표의 단체에서 xk=(0.5, 0.5)x_k = (0.5,\ 0.5), 기울기 g=(1, 0)g = (1,\ 0), 학습률 η=log⁡3\eta = \log 3 으로 지수가중 갱신을 한 걸음 하면 어디로 가나요.
    인자가 e−log⁡3=1/3e^{-\log 3} = 1/3 과 1이라 정규화 전이 (1/6, 1/2)(1/6,\ 1/2), 합이 2/32/3 이므로 (0.25, 0.75)(0.25,\ 0.75) 입니다.
  6. 음의 엔트로피로 만든 브레그만 발산을 x=(0.5, 0.5)x = (0.5,\ 0.5), y=(0.25, 0.75)y = (0.25,\ 0.75) 에서 두 순서로 계산하고 대칭인지 확인하세요.
    단체 위라 KL과 같습니다. D(x,y)=0.5log⁡2+0.5log⁡(2/3)=0.5×(0.693−0.405)=0.144D(x, y) = 0.5\log 2 + 0.5\log(2/3) = 0.5 \times (0.693 - 0.405) = 0.144 이고, D(y,x)=0.25log⁡0.5+0.75log⁡1.5=−0.173+0.304=0.131D(y, x) = 0.25\log 0.5 + 0.75\log 1.5 = -0.173 + 0.304 = 0.131 이라 두 값이 다릅니다. 접평면을 긋는 점이 바뀌기 때문입니다.

첫머리의 히스토그램으로 돌아갑니다. 0 근처를 오가던 수천 개의 가중치는 L1 항을 기울기로 밀었기 때문이었고, 같은 항을 근접 연산자로 풀면 소프트 임계값이 0 근처의 구간을 통째로 0으로 접어 넣어 손으로 문턱을 정할 일이 사라집니다. Adam과 AdamW의 차이도 같은 말로 정리됩니다. 감쇠 항을 손실에 넣으면 Adam의 좌표별 스케일링을 거치고, 근접 단계로 떼어 내면 유클리드 기하에서 따로 처리되며, AdamW는 그 근접 단계를 1차까지 적은 것이었습니다. 후반부는 걸음을 묶는 거리 자체를 바꾸었습니다. 단체 위에서 KL로 걸음을 재면 갱신이 곱셈과 softmax가 되고, 후회가 차원의 제곱근이 아니라 로그로 자라며, RLHF의 KL 정규화 목적식이 그 한 걸음이었습니다.

이 글의 수렴률은 전부 기울기를 정확히 안다고 두고 얻은 것입니다. 실제 학습은 미니배치로 잰 잡음 섞인 기울기를 쓰고, 그때 학습률을 어떻게 줄여야 수렴이라는 말이 성립하는지, 1차 방법이 넘을 수 없는 하한이 무엇인지가 다음 글의 주제입니다.


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

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.13

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

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

고급50 MIN