IQ Lab
← all posts
AI 2026.04.28 · 14 min read Advanced

볼록 최적화는 머신러닝을 어떻게 설명하는가

Logistic Regression의 수렴 보장부터 SVM 쌍대성, L1 희소성의 기하학, 비볼록 딥러닝의 역설, 그리고 온라인 학습의 Regret 경계까지 — 볼록 최적화라는 하나의 렌즈로 추적한다.

📚 Convex Optimization Deep Dive 7 / 7
  1. 01 볼록 집합이 최적화에 황금 티켓을 부여하는 이유
  2. 02 볼록 함수의 세 가지 얼굴 — Jensen, Epigraph, Gradient
  3. 03 볼록 최적화는 왜 ML의 기반인가
  4. 04 Lagrangian 쌍대성은 왜 SVM을 가능하게 하는가
  5. 05 경사하강법은 얼마나 빠른가 — 수렴 이론의 전체 지도
  6. 06 Proximal Operator는 왜 경사하강법의 일반화인가
  7. 07 볼록 최적화는 머신러닝을 어떻게 설명하는가

머신러닝 교과서는 알고리즘을 나열한다. 그런데 왜 어떤 알고리즘은 “전역 최적해가 보장된다”고 하고, 어떤 알고리즘은 “경험적으로 잘 된다”고만 말하는가? 그 경계를 긋는 것이 볼록성(convexity)이다. Logistic Regression부터 SVM, Lasso, 딥러닝, 온라인 학습까지 — 이 챕터들은 모두 하나의 질문을 다른 각도에서 묻는다. “이 문제는 볼록인가, 아닌가? 그래서 무엇이 보장되는가?”

볼록성이 보장하는 것

Logistic Regression의 손실함수는 볼록이다. 이것이 왜 중요한가? 볼록함수는 극솟값이 곧 전역 최솟값이다. 경사 하강법이 어디서 시작하든 같은 지점에 도달한다.

증명의 핵심은 헤시안(Hessian)이다. 로지스틱 손실 ℓ(w)=1n∑i=1nlog⁡(1+exp⁡(−yiw⊤xi))\ell(w) = \frac{1}{n}\sum_{i=1}^n \log(1 + \exp(-y_i w^\top x_i))의 헤시안은 다음과 같다.

∇2ℓ(w)=1nX⊤DX\nabla^2 \ell(w) = \frac{1}{n} X^\top D X

여기서 D=diag(pi(1−pi))D = \text{diag}(p_i(1-p_i))이고 pi=σ(yiw⊤xi)∈(0,1)p_i = \sigma(y_i w^\top x_i) \in (0,1)이므로 모든 대각 원소가 양수다. X⊤DXX^\top D X는 반정부호(PSD)이므로 헤시안이 ⪰0\succeq 0 — 볼록이 증명된다.

명제 1 · L2 정규화된 Logistic Regression은 강볼록이다

f(w)=ℓ(w)+λ2∥w∥2f(w) = \ell(w) + \frac{\lambda}{2}\|w\|^2에 대해, ∇2f(w)=1nX⊤DX+λI⪰λI\nabla^2 f(w) = \frac{1}{n}X^\top DX + \lambda I \succeq \lambda I이다. 따라서 λ>0\lambda > 0이면 ff는 강볼록(strongly convex)이고, 유일한 전역 최솟값이 존재한다.

▷ 증명

∇2ℓ(w)⪰0\nabla^2 \ell(w) \succeq 0이고 λI≻0\lambda I \succ 0이므로 합은 ⪰λI\succeq \lambda I이다. 강볼록 함수는 coercive하므로 (∥w∥→∞\|w\| \to \infty일 때 f→∞f \to \infty) 최솟값이 존재하고, 강볼록에 의해 유일하다. ∎

∎

L2 정규화는 단순히 과적합을 막는 것이 아니다. 헤시안에 λI\lambda I를 더해 강볼록성을 보장함으로써, 경사 하강법의 수렴을 수치적으로 안정화한다.

SVM: 쌍대성이 드러내는 구조

SVM은 볼록 최적화의 교과서적 응용이다. Soft-margin SVM의 프라이멀(primal) 문제는 볼록 이차 계획법(QP)이다. 그런데 라그랑주 쌍대(dual)로 변환하면 훨씬 더 많은 것이 보인다.

쌍대 문제:

max⁡α{∑iαi−12∑i,jαiαjyiyjxi⊤xj}s.t.0≤αi≤C,∑iαiyi=0\max_\alpha \left\{ \sum_i \alpha_i - \frac{1}{2}\sum_{i,j} \alpha_i \alpha_j y_i y_j x_i^\top x_j \right\} \quad \text{s.t.} \quad 0 \leq \alpha_i \leq C, \quad \sum_i \alpha_i y_i = 0

이 문제의 목적함수 행렬 Q=YXX⊤Y=(YX)(YX)⊤Q = YXX^\top Y = (YX)(YX)^\top는 반정부호 — 쌍대 문제도 볼록 QP다. 강쌍대성(strong duality)이 성립하므로 프라이멀과 쌍대의 최적값이 같다.

KKT 조건에서 결정적인 사실이 나온다. αi>0\alpha_i > 0인 데이터만 결정 경계에 기여한다 — 이것이 support vector다. 나머지는 존재하지 않는 것과 같다. 또한 내적 xi⊤xjx_i^\top x_j 자리에 커널 K(xi,xj)K(x_i, x_j)를 대입하면, 암묵적으로 고차원 특징 공간에서 선형 분류를 하게 된다. Mercer 조건은 이 커널이 유효한 내적에 대응함을 — 즉 그람 행렬이 반정부호임을 — 보장하여 쌍대의 볼록성을 유지한다.

L1 vs L2: 마름모와 구의 기하학

Ridge(L2)와 Lasso(L1)의 차이는 계산적 편의가 아니라 기하에서 온다.

제약 형태로 쓰면 두 문제의 차이가 명확해진다. L2 제약 집합은 구(sphere) {∥w∥2≤r}\{\|w\|_2 \leq r\}이고, L1 제약 집합은 마름모(diamond) {∥w∥1≤r}\{\|w\|_1 \leq r\}이다. 손실함수의 등고선이 바깥에서 조여들 때, 구와 처음 만나는 점은 “표면 어디나” 가능하다 — 대부분 모든 좌표가 non-zero다. 마름모와 처음 만나는 점은 꼭짓점(vertex) 근처이고, 꼭짓점은 정확히 wj=0w_j = 0인 축 위에 있다.

이것이 Lasso sparsity의 기원이다. 수식으로는 KKT 조건의 부분미분(subdifferential)이 wj=0w_j = 0을 유지하는 조건을 설명한다.

✎ 트레이드오프: Ridge vs Lasso

Ridge는 폐쇄해(closed-form)가 존재하고 상관된 변수를 균등하게 처리하지만 sparsity가 없다. Lasso는 자동 변수 선택을 하고 n≪pn \ll p 고차원에서 일관된 모델 선택이 가능하지만, 반복 알고리즘이 필요하고 상관 변수 중 어느 것을 택할지 불안정하다. Elastic Net은 두 페널티를 혼합해 이 트레이드오프를 완화한다.

특이값 분해로 보면 Ridge의 축소 비율은 σj2σj2+λ∈(0,1)\frac{\sigma_j^2}{\sigma_j^2 + \lambda} \in (0,1) — 모든 성분을 연속으로 축소한다. Lasso는 임계값 이하를 정확히 0으로 만든다 — 불연속적 축소.

비볼록 딥러닝은 왜 동작하는가

신경망은 비볼록이다. 그런데 경사 하강법이 잘 작동한다. 이 역설의 현대적 설명은 두 축이다.

첫째, **과모수화(over-parameterization)**다. 파라미터 수 p≫np \gg n이면 손실을 0으로 만드는 ww가 풍부하게 존재하고, 이 최솟값들이 저손실 경로(low-loss path)로 연결되어 있다. 국소 극솟값이 “덫”처럼 작동하지 않는다.

둘째, **Neural Tangent Kernel(NTK)**이다. 무한 폭(width →∞\to \infty) 극한에서 NTK 행렬

Kij=∇θf(xi;θ0)⊤∇θf(xj;θ0)K_{ij} = \nabla_\theta f(x_i;\theta_0)^\top \nabla_\theta f(x_j;\theta_0)

이 학습 내내 상수로 유지된다. 그러면 학습 역학은

dy^idt=−∑jKij(yj−y^j)\frac{d\hat{y}_i}{dt} = -\sum_j K_{ij}(y_j - \hat{y}_j)

로 선형 ODE가 되고, 손실이 e−λmin⁡(K)⋅te^{-\lambda_{\min}(K) \cdot t} 속도로 지수 감소한다. 무한 폭 극한에서 신경망은 커널 회귀와 동치다.

물론 NTK는 부분적 설명이다. 유한 폭, 유한 학습률, 배치 노이즈 — 실제 신경망은 NTK가 가정하는 조건에서 벗어난다. 이론이 실천을 따라가는 중이다.

Online Convex Optimization과 Regret

지금까지는 손실함수가 고정된 설정이었다. 온라인 학습에서는 매 라운드 tt마다 새로운 ftf_t가 등장한다 — 미리 알 수 없다.

Regret은 온라인 알고리즘의 누적 손실과 최적 고정 해의 차이다.

Regret(T)=∑t=1Tft(xt)−min⁡x∗∈C∑t=1Tft(x∗)\text{Regret}(T) = \sum_{t=1}^T f_t(x_t) - \min_{x^* \in C} \sum_{t=1}^T f_t(x^*)

Online Gradient Descent(OGD)는 xt+1=ΠC(xt−ηgt)x_{t+1} = \Pi_C(x_t - \eta g_t)로 업데이트한다. Descent Lemma와 볼록성을 결합하면 다음이 나온다.

∑t=1T(ft(xt)−ft(x∗))≤∥x1−x∗∥22η+ηTG22\sum_{t=1}^T (f_t(x_t) - f_t(x^*)) \leq \frac{\|x_1 - x^*\|^2}{2\eta} + \frac{\eta T G^2}{2}

η=D/(GT)\eta = D/(G\sqrt{T})로 최적화하면 Regret(T)≤DGT\text{Regret}(T) \leq DG\sqrt{T} — O(√T) 경계다. 평균 후회가 O(1/T)→0O(1/\sqrt{T}) \to 0으로 수렴한다.

✎ 트레이드오프: OGD vs AdaGrad

OGD는 균등 학습률로 O(√T) Regret을 달성한다. AdaGrad는 좌표별 누적 제곱 그레디언트로 학습률을 조정해, 희소 그레디언트 환경에서 효율적으로 동작한다 — 자주 나타나는 특징은 학습률을 줄이고, 드문 특징은 유지한다. 단, AdaGrad는 학습률이 단조 감소해 비정상(non-stationary) 문제에서는 성능이 저하될 수 있다. RMSprop과 Adam은 이 한계를 지수 이동 평균으로 완화한다.

정리

  • 볼록성 = 수렴 보장이다. Logistic Regression과 SVM 쌍대가 전역 최적해를 보장하는 이유는 헤시안이 PSD이거나 쌍대가 볼록 QP이기 때문이다.
  • L1과 L2의 차이는 기하다. 마름모의 꼭짓점 구조가 sparsity를 만든다. 페널티 형태의 차이는 결과적으로 제약 집합의 모양 차이다.
  • 딥러닝은 비볼록이지만, 과모수화와 NTK가 부분적으로 그 성
# convex-optimization # machine-learning # svm # regularization # online-learning