미러 하강

편집 역사 토론
최적설계 수치해석 통계 마지막 수정: 2026-08-09 04:39:08

1. 개요[편집]

미러 하강
Mirror Descent
제안Nemirovski & Yudin (1979/1983)
근접 재해석Beck & Teboulle (2003)
거울 사상강볼록 함수 ψ, 원시↔쌍대 대응 ∇ψ
근접항유클리드 제곱거리 → 브레그만 발산 Dψ
대표 사례ψ=½‖x‖² → 투영 경사법 / ψ=음의 엔트로피 → 지수 가중 갱신
심플렉스 수렴률O(√(log n / T)) — 차원 의존성이 n에서 log n으로

미러 하강(mirror descent)은 경사하강법의 근접항(proximity term)을 유클리드 제곱거리에서 브레그만 발산으로 갈아 끼운 1차 최적화 기법이다. 볼록집합 C\mathcal{C} 위에서 min⁡f(x)\min f(x) 를 풀 때 갱신식은 다음 한 줄이다.

xk+1  =  arg⁡min⁡x∈C  { ⟨gk, x⟩  +  1η Dψ(x, xk)},gk∈∂f(xk)x_{k+1} \;=\; \arg\min_{x\in\mathcal{C}}\;\Big\{\,\langle g_k,\,x\rangle \;+\; \frac{1}{\eta}\,D_\psi(x,\,x_k)\Big\}, \qquad g_k \in \partial f(x_k)

여기서 ψ\psi 는 거울 사상(mirror map)이라 불리는 강볼록 함수이고, DψD_\psi 는 그것이 생성하는 브레그만 발산이다. ψ(x)=12∥x∥22\psi(x)=\tfrac12\lVert x\rVert_2^2 로 두면 DψD_\psi 가 제곱거리가 되어 평범한 투영 경사하강법이 그대로 복원된다. 미러 하강의 요점은 ψ\psi 를 문제의 기하에 맞춰 고르면 수렴률의 차원 의존성 자체가 바뀐다는 것이다.

네미로프스키와 유딘이 1979년(영역본 1983) 최적화 복잡도 이론을 다루면서 제안했고, 원래 논증은 “경사는 원시공간이 아니라 쌍대공간에 사는 벡터인데 왜 원시점에 그냥 빼는가”라는 형식적 위화감에서 출발했다. 지금 널리 쓰이는 위의 근접 형태 재해석은 벡과 테불(2003)이 정리한 것이다.1

2. 경사를 어디에 더할 것인가[편집]

x←x−ηgx \leftarrow x - \eta g 라는 익숙한 식을 곱씹어 보면 이상한 데가 있다. xx 는 정의역의 점이고 g=∇f(x)g=\nabla f(x) 는 선형범함수, 즉 쌍대공간의 원소다. 단위가 다른 둘을 그냥 빼고 있는 것. 유클리드 공간에서는 내적이 둘을 동일시해 주기 때문에 아무 문제가 없지만, 정의역이 확률 심플렉스처럼 유클리드 구조와 궁합이 안 맞는 집합이면 이 동일시가 손해를 만든다.

미러 하강은 그래서 세 단계로 움직인다.

  1. 거울로 보낸다: θk=∇ψ(xk)\theta_k = \nabla\psi(x_k) 로 원시점을 쌍대공간으로 옮긴다.
  2. 쌍대공간에서 경사 스텝: θk+1=θk−η gk\theta_{k+1} = \theta_k - \eta\, g_k. 여기서는 두 벡터의 단위가 같으니 정당하다.
  3. 거울에서 돌아온다: yk+1=(∇ψ)−1(θk+1)y_{k+1}=(\nabla\psi)^{-1}(\theta_{k+1}) 을 취하고, 그 점이 C\mathcal{C} 밖이면 브레그만 투영 xk+1=arg⁡min⁡x∈CDψ(x,yk+1)x_{k+1}=\arg\min_{x\in\mathcal{C}}D_\psi(x,y_{k+1}) 로 끌어들인다.

∇ψ\nabla\psi 가 원시↔쌍대를 잇는 가역 사상이라는 것은 르장드르-펜셸 변환의 언어 그대로다((∇ψ)−1=∇ψ∗(\nabla\psi)^{-1}=\nabla\psi^*). “거울”이라는 이름은 이 왕복에서 왔다.

3. 두 개의 정석 사례[편집]

유클리드 거울 ψ(x)=12∥x∥22\psi(x)=\tfrac12\lVert x\rVert_2^2. ∇ψ=id\nabla\psi=\mathrm{id} 라서 위 세 단계가 전부 자명해지고, 남는 것은 xk+1=ΠC(xk−ηgk)x_{k+1}=\Pi_\mathcal{C}(x_k-\eta g_k) — 투영 경사하강법이다. 미러 하강은 경사하강법의 일반화가 맞다.

엔트로피 거울 ψ(x)=∑ixilog⁡xi\psi(x)=\sum_i x_i\log x_i, 정의역은 확률 심플렉스 Δn={x≥0, ∑xi=1}\Delta_n=\{x\ge0,\ \sum x_i=1\}. 이때 DψD_\psi 는 쿨백-라이블러 발산이고, ∇ψ=1+log⁡x\nabla\psi = 1+\log x 이므로 쌍대 스텝이 로그 위에서 일어난다. 정규화까지 정리하면 갱신은 곱셈이 된다.

xk+1,i  =  xk,i exp⁡(−η gk,i)∑jxk,j exp⁡(−η gk,j)x_{k+1,i} \;=\; \frac{x_{k,i}\,\exp(-\eta\, g_{k,i})}{\sum_{j} x_{k,j}\,\exp(-\eta\, g_{k,j})}

지수 가중 갱신(exponentiated gradient), 혹은 온라인 학습 쪽 이름으로 곱셈 가중치 갱신(multiplicative weights)이다. 투영이 분모의 정규화 한 번으로 끝난다는 점도 실용적으로 크다 — 유클리드 심플렉스 투영은 정렬이 필요한 O(nlog⁡n)O(n\log n) 연산인데, 여기서는 합 한 번이다. 소프트맥스 함수가 튀어나오는 것도 우연이 아니고, 이 갱신은 지수족의 자연모수 좌표에서 본 직선 이동이다.

4. 수렴률 — 이게 전부인 이유[편집]

ψ\psi 가 노름 ∥⋅∥\lVert\cdot\rVert 에 대해 σ\sigma-강볼록이고 부분경사가 쌍대노름으로 ∥g∥∗≤L\lVert g\rVert_*\le L 로 유계이면, R2=Dψ(x∗,x1)R^2 = D_\psi(x^*,x_1) 에 대해

min⁡k≤Tf(xk)−f(x∗)  ≤  R2ηT+ηL22σ    → η⋆     LR2σT\min_{k\le T} f(x_k) - f(x^*) \;\le\; \frac{R^{2}}{\eta T} + \frac{\eta L^{2}}{2\sigma} \;\;\xrightarrow[\ \eta^\star\ ]{}\;\; L R\sqrt{\frac{2}{\sigma T}}

이 부등식의 핵심은 LL 과 RR 이 서로 짝지어진 노름으로 측정된다는 점이다. 심플렉스 위에서 두 선택을 비교해 보자. 경사 성분이 ∥g∥∞≤G\lVert g\rVert_\infty \le G 로 유계라고 하자.

거울 사상강볼록 기준 노름R²유효 L수렴률
유클리드 ½‖x‖²ℓ₂≤ 1‖g‖₂ ≤ G√nO(G √(n/T))
음의 엔트로피ℓ₁ (핀스커 부등식으로 σ=1)≤ log n‖g‖∞ ≤ GO(G √(log n / T))

차원 의존성이 n\sqrt{n} 에서 log⁡n\sqrt{\log n} 으로 떨어진다. n=106n=10^6 이면 1000배 대 3.7배의 차이다. 알고리즘의 비용은 사실상 같은데(둘 다 반복당 O(n)O(n)) 필요한 반복 수가 이만큼 갈리는 것이라, “기하를 고르는 것”이 공짜 점심에 가장 가까운 사례로 자주 인용된다. 심플렉스 위 1차 방법의 하한이 Θ(log⁡n/T)\Theta(\sqrt{\log n/T}) 이므로 엔트로피 거울은 상수배를 빼면 최적이기도 하다.2

주의할 점도 있다. 엔트로피 거울은 ψ\psi 가 심플렉스 경계에서 ∇ψ→−∞\nabla\psi\to-\infty 로 폭발하므로 좌표가 0에 붙으면 다시는 못 살아난다. 유한 정밀도에서 언더플로로 좌표가 죽는 사고가 실제로 나서, 구현은 대개 로그 영역에서 누적하고 log-sum-exp로 정규화한다.3

5. 사촌들 — 쌍대 평균화, 온라인 학습, 자연경사[편집]

쌍대 평균화(dual averaging, 네스테로프 2009)는 3단계 중 2번을 “직전 경사 한 개”가 아니라 누적 경사 전체에 대해 수행하는 변형이다. ∇ψ(yk+1)=−η∑j≤kgj\nabla\psi(y_{k+1}) = -\eta\sum_{j\le k} g_j 로 두는 셈이라, 게으른(lazy) 미러 하강이라고도 부른다. 스텝 크기 스케줄에 더 둔감하고 정규화항이 있는 복합 문제에서 다루기 쉬워, 희소해를 정말 0으로 만들어야 하는 상황에서 선호된다. 확률적 경사하강법의 적응 스텝 계열(대각 전처리를 학습하는 부류) 역시 “매 반복 거울 사상을 바꾸는 미러 하강”으로 유도된다.

온라인 학습과의 관계는 사실 같은 정리를 두 번 쓰는 것에 가깝다. 온라인 볼록 최적화에서 nn 명의 전문가 조언을 가중 평균할 때 쓰는 헤지 알고리즘/가중 다수결은 심플렉스 위 엔트로피 미러 하강 그 자체이고, 후회(regret) 상한 O(Tlog⁡n)O(\sqrt{T\log n}) 은 위 표의 두 번째 줄을 TT 배 한 것이다. 이 곱셈 가중치 갱신은 부스팅, 선형계획법·반정부호 계획법의 근사 해법, 게임 이론의 균형 계산까지 같은 뼈대로 재사용된다.4 연속시간 극한을 취하면 진화 게임의 복제자 방정식이 나온다는 것도 이 계열의 유명한 사실.

**자연경사법**과의 관계는 지수족에서 정확해진다. 로그 분배함수 A(η)A(\eta) 를 거울 사상으로 쓰면 ∇2ψ=∇2A\nabla^2\psi = \nabla^2 A 가 곧 피셔 정보행렬이고, 이때 자연모수 좌표에서의 미러 하강은 평균모수 좌표에서의 자연경사 갱신과 (스텝이 작은 극한에서) 일치한다. 둘 다 “유클리드가 아닌 계량을 쓴다”는 같은 동기의 서로 다른 구현이며, 미러 하강 쪽이 유한 스텝에서도 정의역 제약을 자동으로 지킨다는 장점이 있다.

**근접 경사법**과는 형제 관계다. 근접 경사법은 근접항을 유클리드로 두고 비매끄러운 항 g(x)g(x) 를 근접 연산자로 정확히 처리하는 반면, 미러 하강은 근접항의 기하를 바꾼다. 둘을 합친 복합 미러 하강(composite mirror descent)이 실무 기본형이다.

6. 관련 문서[편집]

7. Footnotes[편집]

  1. 원논문의 서술은 지금 교과서보다 훨씬 추상적이라 처음 읽으면 “그래서 뭘 하라는 거지” 싶다. 벡-테불이 “그냥 근접항을 브레그만으로 바꾼 것”이라고 번역해 준 뒤에야 대중화됐다. 좋은 재해석 하나가 인용 수 만 단위를 만든다는 교훈. ↩

  2. 그렇다고 아무 데나 엔트로피 거울을 쓰면 손해다. 정의역이 ℓ2\ell_2 공이고 경사가 ℓ2\ell_2 로 유계인 문제에서는 유클리드 쪽이 최적이다. 요령은 “정의역의 모양과 경사의 크기를 재는 노름을 짝지어 고른다”는 것뿐이고, 이 짝짓기를 틀리면 미러 하강은 그냥 느린 경사하강법이 된다. ↩

  3. 심플렉스 좌표가 0으로 죽는 사고는 실전에서 꽤 자주 난다. 특히 경사가 큰 초반에 η\eta 를 크게 잡으면 한 스텝에 한 좌표만 남는 광경을 볼 수 있다. 대책은 로그 영역 누적, 그리고 초반 스텝을 줄이는 것. ↩

  4. 곱셈 가중치 갱신은 학습이론·게임이론·근사알고리즘·양자정보에서 각각 따로 발견됐다. 아로라-하잔-케일의 서베이가 “이거 다 같은 알고리즘입니다”라고 정리하기 전까지, 분야마다 다른 이름으로 같은 증명을 반복해서 썼다. ↩