볼록성 (Convexity)¶

난이도: 중급~고급
선수 지식: 미적분, 선형대수, 경사 하강법 기초
관련 문서: 경사 하강법 변형 | 손실 함수 | 선형 모델 | SVM

개요¶

볼록성(Convexity)은 최적화 문제의 난이도를 결정하는 핵심 속성이다. 볼록 함수의 모든 지역 최소(local minimum)는 전역 최소(global minimum)이므로, 볼록 최적화 문제는 확실하게 최적해를 찾을 수 있다.

머신러닝에서: - 볼록 문제: 선형 회귀, 로지스틱 회귀, SVM --> 전역 최적 보장 - 비볼록 문제: 신경망 --> 전역 최적 보장 없음, 하지만 실무에서 잘 동작

핵심 개념¶

1. 볼록 함수 (Convex Functions)¶

정의¶

함수 \(f\)가 볼록이란, 정의역 내 임의의 \(x\), \(y\)와 \(\lambda \in [0, 1]\)에 대해:

\[f(\lambda x + (1-\lambda)y) \le \lambda f(x) + (1-\lambda)f(y)\]

기하학적 의미: 함수 위의 임의의 두 점을 잇는 선분이 항상 함수 위에 있다 ("그릇 모양").

핵심 성질¶

모든 지역 최소 = 전역 최소
적절한 최적화를 사용하면 전역 최적해를 보장
기울기가 0인 점 = 전역 최소 (엄격 볼록이면 유일)

볼록 손실의 예¶

손실	볼록?	비고
MSE (선형 모델)	예	닫힌 형태 해 존재
Log Loss (로지스틱 회귀)	예	닫힌 형태 해 없지만 전역 최적 보장
Hinge Loss	예	SVM
L1, L2 정규화	예	정규화 항도 볼록

2. 볼록 최적화 (Convex Optimization)¶

선형 회귀¶

MSE 손실은 볼록 --> 정규 방정식으로 닫힌 형태 해 존재
경사 하강법으로도 반드시 전역 최적에 수렴

로지스틱 회귀¶

Log Loss는 볼록 --> 닫힌 형태 해는 없지만, 경사 하강법/Newton 방법으로 전역 최적 보장

SVM¶

쌍대 형태(dual form)에서 볼록 이차 프로그램(convex QP)
커널 SVM도 쌍대 공간에서 볼록

3. 비볼록 최적화 (Non-Convex Optimization)¶

신경망의 손실 곡면¶

신경망의 손실 함수는 고도로 비볼록이다:

graph TD
    subgraph "볼록 (그릇 모양)"
        A1["하나의 최소점<br/>어디서 시작해도 도달"]
    end
    subgraph "비볼록 (울퉁불퉁)"
        A2["지역 최소<br/>안장점<br/>고원<br/>골짜기"]
    end

비볼록의 도전¶

현상	설명	문제
지역 최소 (Local Minima)	전역 최소가 아닌 최소점	차선의 해에 갇힘
안장점 (Saddle Points)	기울기 0이지만 최소 아님	학습 정체
고원 (Plateaus)	기울기가 거의 0인 넓은 영역	매우 느린 학습
골짜기 (Ravines)	좁은 곡선 형태의 최소	진동, 느린 수렴

왜 비볼록인데 잘 동작하는가?¶

이것은 현대 딥러닝의 가장 중요한 질문 중 하나이다:

고차원에서 안장점이 지역 최소보다 훨씬 많다 (Dauphin et al., 2014)
무작위 함수에서 차원이 높을수록 모든 방향이 "위"인 점(지역 최소)의 확률은 기하급수적으로 감소
많은 지역 최소가 전역 최소와 비슷한 손실을 가짐 (경험적)
"나쁜" 지역 최소는 드물고, "좋은" 지역 최소가 풍부
SGD의 노이즈가 얕은 지역 최소를 탈출하게 함
미니배치의 확률적 기울기가 암묵적 탐색 역할
과매개변수화(overparameterization)가 좋은 손실 곡면을 만듦
파라미터가 충분히 많으면 최소들이 연결된 매끄러운 경로 존재
로터리 티켓 가설 (Lottery Ticket Hypothesis)
큰 네트워크 안에 효과적으로 학습되는 서브네트워크가 존재

4. 손실 곡면의 성질¶

날카로움 vs 평탄함 (Sharpness vs Flatness)¶

속성	날카로운 최소	평탄한 최소
곡률	높음	낮음
일반화	나쁨 (경향)	좋음 (경향)
도달 방법	큰 배치, 큰 학습률	작은 배치, SGD

Hochreiter & Schmidhuber (1997): 평탄한 최소가 더 나은 일반화

모드 연결성 (Mode Connectivity)¶

서로 다른 최소들이 낮은 손실의 경로로 연결될 수 있음
같은 초기화에서 출발한 해는 선형 경로로도 연결 가능 (linear mode connectivity)

SAM (Sharpness-Aware Minimization)¶

평탄한 최소를 명시적으로 탐색하는 최적화 방법:

\[\min_{\mathbf{w}} \max_{\|\epsilon\| \le \rho} L(\mathbf{w} + \epsilon)\]

최악의 근방 변동에서의 손실을 최소화 --> 평탄한 영역 선호.

5. 강볼록성 (Strong Convexity)¶

정의¶

\[f(y) \ge f(x) + \nabla f(x)^T(y-x) + \frac{\mu}{2}\|y-x\|^2\]

볼록보다 더 강한 조건: 함수가 이차 하한을 가짐.

의미¶

유일한 최소 보장
더 빠른 수렴: GD로 \(O(\rho^t)\) 지수적 수렴 (vs 볼록의 \(O(1/t)\))

L2 정규화의 역할¶

손실 함수에 L2 정규화 \(\lambda\|\mathbf{w}\|^2\)를 더하면 강볼록이 됨:

\[L_{\text{reg}}(\mathbf{w}) = L(\mathbf{w}) + \lambda\|\mathbf{w}\|^2\]

원래 \(L\)이 볼록이기만 하면 정규화 후 강볼록
유일한 최소, 빠른 수렴, 안정적 학습 보장

수렴 속도 비교¶

조건	GD 수렴	SGD 수렴
볼록	\(O(1/t)\)	\(O(1/\sqrt{t})\)
강볼록	\(O(\rho^t)\) 지수적	\(O(1/t)\)

상세 내용¶

볼록성 판정 조건 (Convexity Conditions)¶

함수의 볼록성을 판정하는 데에는 1차 조건과 2차 조건이 사용된다.

1차 조건 (First-Order Condition)¶

미분 가능한 함수 \(f\)가 볼록일 필요충분조건:

\[f(y) \ge f(x) + \nabla f(x)^T(y - x), \quad \forall x, y\]

직관: 함수의 임의의 점에서의 접선(tangent line)이 항상 함수 아래에 있다. 즉, 1차 테일러 근사가 항상 전역 하한(global lower bound)이 된다.

2차 조건 (Second-Order Condition)¶

두 번 미분 가능한 함수 \(f\)가 볼록일 필요충분조건:

\[\nabla^2 f(x) \succeq 0 \quad \forall x\]

즉, 헤시안 행렬(Hessian matrix)이 모든 점에서 양반정치(positive semi-definite)이어야 한다.

강볼록: \(\nabla^2 f(x) \succeq \mu I\) (\(\mu > 0\)), 헤시안의 최소 고유값이 \(\mu\) 이상
엄격 볼록(strictly convex): \(\nabla^2 f(x) \succ 0\) (양정치, positive definite)

예시: - \(f(x) = x^2\): \(f''(x) = 2 > 0\) → 강볼록 - \(f(x) = |x|\): 미분 불가능한 점이 있지만 볼록 (1차 조건으로 판정) - \(f(\mathbf{w}) = \|\mathbf{Xw} - \mathbf{y}\|^2\): 헤시안 = \(2\mathbf{X}^T\mathbf{X} \succeq 0\) → 볼록

KKT 조건 (Karush-Kuhn-Tucker Conditions)¶

제약이 있는 볼록 최적화 문제의 최적성 조건이다.

일반 형태:

\[\min_x f(x) \quad \text{s.t.} \quad g_i(x) \le 0, \quad h_j(x) = 0\]

KKT 조건 (4가지):

정상성 (Stationarity): \(\nabla f(x^*) + \sum_i \mu_i \nabla g_i(x^*) + \sum_j \lambda_j \nabla h_j(x^*) = 0\)
원시 실행가능성 (Primal Feasibility): \(g_i(x^*) \le 0, \quad h_j(x^*) = 0\)
쌍대 실행가능성 (Dual Feasibility): \(\mu_i \ge 0\)
상보 여유 (Complementary Slackness): \(\mu_i g_i(x^*) = 0\)

ML에서의 적용: - SVM: KKT 조건의 상보 여유가 서포트 벡터를 정의한다. \(\mu_i > 0\)인 데이터 포인트만 서포트 벡터이다. - L1 정규화 (Lasso): KKT 조건이 왜 일부 가중치가 정확히 0이 되는지(희소성) 설명한다. - 제약 기반 공정성 (Fairness): 공정성 제약을 부등식으로 표현한 최적화에 KKT 적용

볼록 문제에서 KKT 조건은 전역 최적의 필요충분조건이다 (슬레이터 조건 등 약한 정규성 조건 하에서).

ML 손실 함수의 볼록성 분류¶

flowchart TD
    TITLE["ML 손실 함수의 볼록성"] --> CONVEX["✅ 볼록 손실"]
    TITLE --> NONCONVEX["❌ 비볼록 손실"]

    CONVEX --> C1["MSE<br/>(선형 회귀)"]
    CONVEX --> C2["Log Loss<br/>(로지스틱 회귀)"]
    CONVEX --> C3["Hinge Loss<br/>(SVM)"]
    CONVEX --> C4["Huber Loss"]
    CONVEX --> C5["L1 / L2 정규화"]

    NONCONVEX --> NC1["신경망 손실<br/>(비선형 활성화 때문)"]
    NONCONVEX --> NC2["행렬 분해<br/>(Matrix Factorization)"]
    NONCONVEX --> NC3["EM 알고리즘의<br/>목적 함수"]
    NONCONVEX --> NC4["0-1 Loss<br/>(비연속)"]

    CONVEX -.- NOTE1["전역 최적 보장<br/>수렴 속도 분석 가능"]
    NONCONVEX -.- NOTE2["좋은 지역 최소를<br/>찾는 전략 필요"]

    style CONVEX fill:#27ae60,color:#fff
    style NONCONVEX fill:#e74c3c,color:#fff

주의할 점: 볼록한 손실 함수라도 모델의 파라미터화에 의해 비볼록이 될 수 있다. - 예: Cross-entropy loss 자체는 볼록이지만, 신경망의 비선형 계층을 통과하면 가중치에 대해 비볼록이 된다. - 반대로, 커널 트릭(kernel trick)은 비선형 매핑을 사용하면서도 쌍대 공간에서 볼록성을 유지한다.

볼록 vs 비볼록 최적화 전략¶

볼록성 여부에 따라 최적화 접근이 근본적으로 달라진다.

측면	볼록 최적화	비볼록 최적화
전역 최적 보장	예	아니오
초기화 중요성	낮음 (어디서든 수렴)	매우 높음
학습률	상대적으로 관대	민감, 스케줄링 필요
적합한 옵티마이저	GD, Newton, L-BFGS	SGD+모멘텀, Adam, SAM
수렴 판정	기울기 \(\approx 0\) → 전역 최적	기울기 \(\approx 0\) → 안장점일 수 있음
정규화 효과	볼록성 유지/강화	손실 곡면 변형, 평탄한 최소 유도

언제 사용하는가¶

볼록성은 알고리즘이 아니라 문제의 성질이다:

상황	활용
모델 선택 시	볼록 모델은 전역 최적 보장 (디버깅 용이)
최적화 방법 선택	볼록: 단순 GD도 충분. 비볼록: Adam, 모멘텀 등 필요
정규화 설계	L1, L2 정규화는 볼록성 유지/강화
수렴 분석	볼록/강볼록에 따라 수렴 보장 수준이 다름
신경망 최적화 이해	왜 비볼록인데 동작하는지의 이론적 배경

흔한 오해와 함정¶

1. "비볼록 문제는 풀 수 없다"¶

이론적으로 전역 최적이 보장되지 않을 뿐, 실무에서는 SGD/Adam이 충분히 좋은 해를 찾는다. 딥러닝의 성공이 이를 증명.

2. "지역 최소에 갇히는 것이 주요 문제이다"¶

고차원에서는 안장점이 더 큰 문제이다. 지역 최소가 드물고, 존재하더라도 대부분 전역 최소와 비슷한 손실을 가짐.

3. "볼록 모델은 항상 충분하다"¶

볼록 모델은 표현력이 제한적이다. 복잡한 비선형 관계는 비볼록 모델(신경망)이 필요.

4. "L2 정규화는 단순히 과적합 방지이다"¶

L2 정규화는 목적 함수를 강볼록으로 만들어 수렴을 보장하고 해를 유일하게 하는 수학적 효과도 있다.

다른 주제와의 연결¶

경사 하강법 변형: 볼록/비볼록에 따른 옵티마이저 선택
손실 함수: 손실의 볼록성이 최적화 난이도 결정
선형 모델: 볼록 최적화의 대표적 사례
SVM: 볼록 QP
정규화 이론: L2가 강볼록성을 부여

자주 묻는 면접 질문¶

볼록 함수의 정의와 ML에서의 중요성은?
임의의 두 점을 잇는 선분이 함수 위에 있는 함수. 모든 지역 최소가 전역 최소이므로 최적화가 보장됨.
신경망이 비볼록인데 왜 잘 학습되는가?
고차원 안장점이 지역 최소보다 많고, SGD 노이즈가 탈출을 돕고, 과매개변수화가 좋은 곡면을 만들기 때문.
날카로운 최소 vs 평탄한 최소의 차이와 일반화 관계는?
평탄한 최소는 파라미터의 작은 변동에 덜 민감하여 일반화가 나은 경향. 작은 배치 + SGD가 평탄한 최소에 수렴하는 경향.
L2 정규화가 최적화에 미치는 영향은? (과적합 방지 외에)
목적 함수를 강볼록으로 만들어 유일한 최소를 보장하고 수렴 속도를 향상.

용어 정리¶

영어	한국어
Convex Function	볼록 함수
Non-Convex	비볼록
Local Minimum	지역 최소
Global Minimum	전역 최소
Saddle Point	안장점
Plateau	고원 (평탄 영역)
Strong Convexity	강볼록성
Loss Landscape	손실 곡면
Sharpness	날카로움
Flatness	평탄함
Mode Connectivity	모드 연결성

참고 자료¶

Boyd & Vandenberghe (2004) - Convex Optimization
Dauphin et al. (2014) - "Identifying and Attacking the Saddle Point Problem in High-dimensional Non-convex Optimization"
Hochreiter & Schmidhuber (1997) - "Flat Minima"
Foret et al. (2021) - "Sharpness-Aware Minimization for Efficiently Improving Generalization" (SAM)
Li et al. (2018) - "Visualizing the Loss Landscape of Neural Nets"
Draxler et al. (2018) - "Essentially No Barriers in Neural Network Energy Landscape"