온라인 볼록 최적화

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

1. 개요[편집]

온라인 볼록 최적화
Online Convex Optimization (OCO)
구조매 라운드 xt ∈ K 를 먼저 내고, 그다음 볼록 손실 ft 가 공개됨
성능 척도후회(regret) RT — 사후 최적 고정점 대비 손실 차
기본 알고리즘온라인 경사하강(Zinkevich 2003) — O(√T)
강볼록일 때O(log T)
전문가 문제지수가중(헤지) — O(√(T log N))
파생AdaGrad, FTRL, 온라인-배치 변환

온라인 볼록 최적화(OCO)는 최적화를 함수 하나의 최소화가 아니라 반복 게임으로 다시 쓴 틀이다. 라운드 t=1,…,Tt = 1,\dots,T 마다 학습자가 볼록집합 K\mathcal{K} 에서 결정 xtx_t 를 먼저 내놓고, 그다음에야 상대(자연 또는 적대자)가 볼록 손실함수 ftf_t 를 공개하며, 학습자는 ft(xt)f_t(x_t) 를 물어낸다. 다음 라운드에 쓸 정보는 지금까지 본 f1,…,ftf_1,\dots,f_t 뿐이다.

이 틀에서 “수렴”이라는 말은 의미가 없다. 목표가 매 라운드 바뀌고, 심지어 적대자가 학습자의 알고리즘을 알고 최악의 손실을 고를 수도 있기 때문이다. 대신 쓰는 척도가 후회(regret)다.

RT  =  ∑t=1Tft(xt)  −  min⁡x∈K∑t=1Tft(x)R_T \;=\; \sum_{t=1}^{T} f_t(x_t) \;-\; \min_{x \in \mathcal{K}} \sum_{t=1}^{T} f_t(x)

“모든 게 끝난 뒤 최고의 고정 결정 하나를 알았더라면 얼마나 덜 손해였을까.” 목표는 RTR_T 를 TT 보다 느리게, 즉 부분선형(sublinear)으로 묶는 것이다. RT/T→0R_T/T \to 0 이면 라운드당 평균 손실이 사후 최적과 같아지므로 이를 무후회(no-regret)라 부른다. 놀라운 것은, 상대가 완전히 적대적이어도 볼록성만 있으면 무후회가 가능하다는 사실이다.1

2. 왜 이렇게 정의하는가[편집]

세 가지 설계 결정이 이 틀의 성격을 만든다.

  • 비교 대상이 고정점이다. 매 라운드의 사후 최적 ∑tmin⁡xft(x)\sum_t \min_x f_t(x) 와 비교하면 아무도 못 이긴다(적대자가 매번 다른 곳에 최솟값을 두면 끝). 고정된 하나의 xx 와 비교하는 것이 의미 있는 최약 벤치마크다. 비교 대상을 “천천히 움직이는 결정열”로 넓힌 것이 동적 후회(dynamic regret)이며, 그쪽은 비교열의 총 이동량에 비례하는 항이 추가로 붙는다.
  • 손실이 볼록이어야 한다. 볼록성이 없으면 적대자가 학습자를 임의로 괴롭힐 수 있다.
  • 선형 손실이 최악이다. 볼록성에서 ft(xt)−ft(x)≤⟨gt, xt−x⟩f_t(x_t) - f_t(x) \le \langle g_t,\, x_t - x\rangle (gt∈∂ft(xt)g_t \in \partial f_t(x_t))이므로, 임의의 볼록 손실 문제의 후회는 선형 손실 f~t(x)=⟨gt,x⟩\tilde f_t(x) = \langle g_t, x\rangle 문제의 후회로 상계된다. 그래서 OCO 이론은 대부분 선형 손실만 분석한다. 이 한 줄이 이 분야 증명의 절반을 없앤다.

3. 온라인 경사하강 — 징케비치[편집]

가장 단순한 알고리즘은 그냥 경사하강이다.

xt+1=ΠK(xt−ηt gt),gt∈∂ft(xt)x_{t+1} = \Pi_{\mathcal{K}}\bigl(x_t - \eta_t\, g_t\bigr), \qquad g_t \in \partial f_t(x_t)

바뀐 것은 매 스텝 다른 함수의 경사를 쓴다는 점뿐이다. 징케비치(2003)가 보인 것은, K\mathcal{K} 의 지름이 DD 이고 ∥gt∥≤G\|g_t\| \le G 일 때 ηt=D/(Gt)\eta_t = D/(G\sqrt{t}) 로 두면

RT  =  O(GDT)R_T \;=\; O\bigl(G D \sqrt{T}\bigr)

라는 것이다. 증명은 세 줄짜리 표준 논법이다. ∥xt+1−x⋆∥2≤∥xt−x⋆∥2−2ηt⟨gt,xt−x⋆⟩+ηt2G2\|x_{t+1}-x^\star\|^2 \le \|x_t - x^\star\|^2 - 2\eta_t\langle g_t, x_t - x^\star\rangle + \eta_t^2 G^2 를 정리해 ⟨gt,xt−x⋆⟩\langle g_t, x_t-x^\star\rangle 를 뽑아내고, tt 에 대해 더하면 거리 항이 망원급수로 접히고 스텝 항만 남는다. 비평활 최적화의 부분경사법 해석과 거의 같은 뼈대인데, 여기서는 함수가 매번 바뀌어도 논법이 그대로 산다는 것이 요점이다.

강볼록이면 크게 좋아진다. 모든 ftf_t 가 α\alpha-강볼록이면 ηt=1/(αt)\eta_t = 1/(\alpha t) 에서

RT  =  O ⁣(G2α log⁡T)R_T \;=\; O\!\left(\frac{G^2}{\alpha}\,\log T\right)

T\sqrt{T} 에서 log⁡T\log T 로 떨어진다. 지수 오목(exp-concave) 손실에서도 온라인 뉴턴 스텝(Online Newton Step)이 O(log⁡T)O(\log T) 를 내는데, 이쪽은 이차 정보를 누적한 행렬로 전처리하는 방식이라 차원 dd 가 상수배로 붙는다.

하한도 짝이 맞는다. 손실을 무작위 부호 선형함수로 두면 어떤 알고리즘도 Ω(GDT)\Omega(GD\sqrt{T}) 를 피할 수 없고, 강볼록에서는 Ω(log⁡T)\Omega(\log T) 가 하한이다. 온라인 경사하강은 상수배를 빼면 최적이다.

4. 안정성이 후회를 만든다 — FTL의 실패와 FTRL[편집]

가장 자연스러운 발상은 “지금까지 본 손실의 합을 최소화하는 점을 내라”는 Follow-the-Leader(FTL)다. 그런데 이게 선형 손실에서 처참하게 실패한다. K=[−1,1]\mathcal{K} = [-1,1] 에서 ft(x)=gtxf_t(x) = g_t x 를 g1=−12g_1 = -\tfrac12, 이후 gtg_t 를 +1,−1,+1,…+1, -1, +1, \dots 로 번갈아 주면, FTL은 매 라운드 누적합의 반대 끝점으로 튀면서 항상 틀린 쪽을 고른다. 후회가 Θ(T)\Theta(T), 즉 무후회가 아니다.

병의 원인은 불안정성이다. 누적 손실의 최소점이 한 라운드 만에 정의역 끝에서 끝으로 이동한다. 처방은 하나 — 움직이지 못하게 붙잡는 정규화항을 넣는다. 이것이 FTRL(Follow-the-Regularized-Leader)이다.

xt=arg⁡min⁡x∈K{∑s<tfs(x)+1η R(x)}x_{t} = \arg\min_{x \in \mathcal{K}} \left\{ \sum_{s < t} f_s(x) + \frac{1}{\eta}\,R(x) \right\}

RR 이 강볼록이면 인접한 두 해가 크게 못 벌어지고, 후회 상한이 “정규화항의 크기 + 스텝별 이동량”의 합으로 깔끔하게 나온다. R(x)=12∥x∥22R(x) = \tfrac12\|x\|_2^2 면 (선형 손실에서) 온라인 경사하강과 사실상 같은 알고리즘이 되고, RR 을 음의 엔트로피로 두면 아래의 지수가중이 나온다. 여기서 후회 = 정규화 강도 + 불안정성이라는 교환이 명시적으로 보인다 — η\eta 를 키우면 잘 따라가지만 출렁이고, 줄이면 안정적이지만 굼뜨다. T\sqrt{T} 는 그 균형점에서 나오는 숫자다.

정규화항의 기하를 유클리드 밖으로 바꾸는 것이 **미러 하강**의 온라인 판본(온라인 미러 하강, OMD)이며, 선형 손실에서 “게으른” OMD와 FTRL은 같은 알고리즘이다. 근접항이 브레그만 발산으로 바뀌면서 수렴률의 차원 의존성이 통째로 달라지는 이야기는 그쪽 문서에 있다.

5. 전문가 문제와 지수가중[편집]

OCO의 원형이자 가장 오래된 사례. NN 명의 전문가가 매 라운드 조언을 내고, 학습자는 가중치 wt∈ΔNw_t \in \Delta_N(확률 심플렉스)로 그들을 섞는다. 손실이 [0,1][0,1] 범위의 벡터 ℓt\ell_t 로 주어질 때 손실은 ⟨wt,ℓt⟩\langle w_t, \ell_t\rangle — 결정변수에 대해 선형이다. 여기에 음의 엔트로피 정규화를 쓴 FTRL이 지수가중(exponential weights), 온라인 학습 쪽 이름으로 헤지(Hedge)다.

wt+1,i  =  wt,i exp⁡(−η ℓt,i)∑jwt,j exp⁡(−η ℓt,j)w_{t+1,i} \;=\; \frac{w_{t,i}\,\exp(-\eta\,\ell_{t,i})}{\sum_j w_{t,j}\,\exp(-\eta\,\ell_{t,j})}

표준 상한은 RT≤ln⁡Nη+ηT8R_T \le \frac{\ln N}{\eta} + \frac{\eta T}{8} 이고, η=8ln⁡N/T\eta = \sqrt{8\ln N / T} 로 최적화하면

RT  ≤  12 Tln⁡NR_T \;\le\; \sqrt{\tfrac{1}{2}\,T \ln N}

전문가 수에 로그로만 의존한다. 백만 명을 후보로 두어도 ln⁡106≈3.7\sqrt{\ln 10^6} \approx 3.7 배 값을 더 낼 뿐이다. 이 하나로 “가능한 모델을 전부 후보에 넣고 온라인으로 고른다”는 전략이 정당화된다. 같은 차수의 하한도 알려져 있어 이 상한은 상수까지 거의 최적이다. 곱셈 형태의 이 갱신은 부스팅, 근사 알고리즘, 게임 이론의 균형 계산에서 각각 독립적으로 재발견된 유서 깊은 물건이다(헤지 알고리즘 참고).

6. AdaGrad — 적응적 스텝의 출처[편집]

딥러닝 옵티마이저의 조상 격인 AdaGrad(Duchi–Hazan–Singer, 2011)는 OCO 이론에서 태어났다. 발상은 “정규화항을 고정하지 말고 지금까지 본 경사에 맞춰 매 라운드 갱신하자”이다. 좌표별 누적 제곱합 Gt,i=∑s≤tgs,i2G_{t,i} = \sum_{s\le t} g_{s,i}^2 로

xt+1,i=xt,i−ηGt,i+ϵ gt,ix_{t+1,i} = x_{t,i} - \frac{\eta}{\sqrt{G_{t,i}} + \epsilon}\, g_{t,i}

를 쓰면, 후회 상한이 좌표별 경사 크기의 합 ∑i∥g1:T,i∥2\sum_i \|g_{1:T,i}\|_2 에 비례하는 형태로 나온다. 자주 크게 흔들리는 좌표는 스텝을 줄이고, 드물게 등장하는 좌표는 크게 밟는다. 텍스트 분류처럼 특징이 희소한 문제에서 이 상한은 최악경우 T\sqrt{T} 상한보다 훨씬 작아질 수 있고, 그게 AdaGrad가 처음 이겼던 무대다. 이후 누적합을 지수이동평균으로 바꾼 RMSProp·Adam 계열이 실무를 접수했지만, 원래의 정당화는 배치 학습의 수렴 정리가 아니라 이 적응적 후회 상한이었다는 점은 기억해 둘 만하다. 확률적 경사하강법·경사하강법 문서의 서술과 이어 읽으면 계보가 보인다.2

7. 온라인-배치 변환[편집]

OCO가 순수 온라인 문제를 넘어 중요한 이유는 이 정리 하나 때문이다. 데이터 ztz_t 가 분포 D\mathcal{D} 에서 독립 추출되고 ft(x)=F(x;zt)f_t(x) = F(x; z_t) 라 하자. 목표는 기대 위험 Fˉ(x)=Ez[F(x;z)]\bar{F}(x) = \mathbb{E}_z[F(x;z)] 의 최소화, 즉 확률적 볼록 최적화다. 온라인 알고리즘을 그대로 돌리고 반복점들의 평균 xˉT=1T∑txt\bar{x}_T = \frac1T\sum_t x_t 를 내놓으면

E[Fˉ(xˉT)]−min⁡xFˉ(x)  ≤  E[RT]T\mathbb{E}\bigl[\bar{F}(\bar{x}_T)\bigr] - \min_x \bar{F}(x) \;\le\; \frac{\mathbb{E}[R_T]}{T}

가 성립한다. 증명의 핵심은 두 개다 — xtx_t 가 ztz_t 와 독립이므로 E[ft(xt)]=E[Fˉ(xt)]\mathbb{E}[f_t(x_t)] = \mathbb{E}[\bar F(x_t)] 이고, Fˉ\bar F 가 볼록이므로 옌센 부등식으로 평균점의 값이 값들의 평균 이하다. 결과적으로

  • 일반 볼록: O(1/T)O(1/\sqrt{T}) — SGD의 표준 수렴률이 정확히 이것이다.
  • 강볼록: O(log⁡T/T)O(\log T / T), 다듬으면 O(1/T)O(1/T).

즉 SGD의 수렴 정리를 따로 증명할 필요가 없다. 온라인에서 적대자를 상대로 얻은 후회 상한을 TT 로 나누면 확률적 설정의 수렴률이 그대로 나온다. 적대적 가정이 i.i.d. 가정보다 훨씬 강하므로, 이 변환은 “더 어려운 문제를 풀어 놓고 쉬운 문제의 답을 공짜로 받는” 구조다. 다만 대가도 명확하다 — 최악경우를 상정한 상한이라 i.i.d. 문제에서 실제로 얻을 수 있는 최선(분산에 적응하는 상한)보다 보수적일 때가 많다.

8. 변형과 쓰임[편집]

  • 밴딧 피드백. ftf_t 전체가 아니라 값 ft(xt)f_t(x_t) 하나만 볼 수 있는 설정. 경사를 무작위 탐색으로 추정해야 하므로 후회가 T2/3T^{2/3} 나 T\sqrt{T} 로 나빠지고 차원 의존성이 커진다. 다중 슬롯머신 문제가 손실이 선형이고 정의역이 심플렉스인 특수 사례다.
  • 게임과 균형. 두 명이 서로에게 무후회 알고리즘으로 대응하면, 평균 전략쌍이 영합 게임의 미니맥스 균형으로 수렴한다. 일반합 게임에서는 조대 상관균형(coarse correlated equilibrium)으로 간다. 쌍대성의 미니맥스 정리를 알고리즘적으로 증명하는 표준 경로가 이것이다.
  • 포트폴리오 선택. 매일 자산 배분을 정하고 그날의 수익률을 보는 구조가 그대로 OCO다. 커버의 유니버설 포트폴리오가 사후 최적 고정 비율 포트폴리오 대비 O(log⁡T)O(\log T) 후회를 낸다는 고전적 결과가 있다.
  • 제어·시뮬레이션 루프. 매 스텝 모델이 조금씩 바뀌는 적응 제어를 “동적 후회 최소화”로 다시 쓰는 최근 계열이 있다. 시스템이 시간에 따라 변할 때 정상성 가정을 요구하지 않는다는 것이 이 관점의 장점이다.

9. 실무 감각[편집]

  • 후회 상한의 상수에는 DD(정의역 지름)와 GG(경사 노름 상계)가 반드시 들어간다. 정의역을 유계로 잡지 않으면 이론이 아무 말도 못 한다. 실무에서 가중치 노름 제약이나 투영이 붙는 이유는 정규화 취향이 아니라 이 때문이다.
  • η∝1/t\eta \propto 1/\sqrt{t} 스케줄은 TT 를 몰라도 되는 표준 처방이다. TT 를 알면 상수 스텝 D/(GT)D/(G\sqrt{T}) 가 상수배 낫다.
  • 후회가 부분선형이라고 매 라운드 성능이 좋다는 뜻은 아니다. 후회는 누적 척도라 초반에 크게 손해 보고 나중에 만회하는 알고리즘도 좋은 상한을 받는다. 손실이 실제 비용인 시스템(광고 입찰, 실기 제어)에서는 이 차이가 그대로 돈과 사고로 나타난다.
  • 비교 대상이 “고정된 하나의 결정”이라는 점을 잊으면 상한을 과대해석하게 된다. 환경이 크게 변하는 문제에서는 최고의 고정 결정 자체가 나쁘고, 그 나쁜 기준을 따라잡아 봐야 소용이 없다.3

10. 관련 문서[편집]

11. Footnotes[편집]

  1. 처음 배우면 “적대자가 내 알고리즘을 알고 있는데 어떻게 이기냐”는 반발이 온다. 답은 “이기는 게 아니라 안 지는 것”이다. 무후회는 상대를 이긴다는 보장이 전혀 아니고, “사후에 돌아봐도 다른 고정 전략을 썼으면 나았겠다는 말을 못 하게 만든다”는 보장일 뿐이다. 벤치마크가 약하다는 비판은 이 분야의 오래된 단골 안건이다. ↩

  2. AdaGrad 논문과 거의 동시에 매마한이 FTRL-Proximal 계열을 발표했고, 구글의 광고 클릭 예측 시스템이 그 변형을 실제로 굴리면서 “정규화로 진짜 0을 만드는” 온라인 희소 학습이 산업 표준이 됐다. 딥러닝이 이 계보를 가져다 쓰기 전에 이미 광고가 먼저 쓰고 있었다. ↩

  3. 그래서 실무 보고서에서 “후회가 O(T)O(\sqrt{T}) 로 묶입니다”라는 문장은 절반짜리 정보다. 그 상한의 상수 GDGD 가 얼마인지, 그리고 비교 대상인 최고의 고정 결정이 실제로 쓸 만한지를 같이 보고해야 의미가 생긴다. 상한만 예쁜 알고리즘은 이 바닥에도 많다. ↩