온라인 볼록 최적화

오류 제보
최적설계 통계 수치해석 마지막 수정: 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 가 얼마인지, 그리고 비교 대상인 최고의 고정 결정이 실제로 쓸 만한지를 같이 보고해야 의미가 생긴다. 상한만 예쁜 알고리즘은 이 바닥에도 많다. ↩

이 문서가 문제를 푸는 데 도움이 됐나요? 한 번의 클릭이 다음 검수 순서를 정합니다.

의견을 반영할게요. 감사합니다.

다음으로 읽기 볼록 최적화 약 5분 더 탐색 →