볼록성 (Convexity)

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

핵심 요약: 볼록 함수(Convex Function) = 그릇 모양(어디서 시작해도 바닥에 도달), 비볼록(Non-Convex) = 산맥(골짜기가 여러 개). 선형 회귀(Linear Regression), SVM은 볼록이라 전역 최적(Global Minimum)이 보장되고, 신경망(Neural Network)은 비볼록이지만 실무에서 잘 동작한다 — 그 이유를 이해하는 것이 핵심이다.

개요

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

머신러닝에서:

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

탄생 배경

볼록 최적화의 체계적 이론은 Stephen Boyd와 Lieven Vandenberghe가 2004년에 출판한 “Convex Optimization”에서 집대성되었다. 이 교과서는 볼록 최적화가 공학, 경제학, 통계학 전반에서 얼마나 광범위하게 활용되는지를 보여주었고, “볼록 문제로 변환할 수 있으면 효율적으로 풀 수 있다”는 핵심 메시지를 전파했다. SVM, 로지스틱 회귀, LASSO 등 전통적 ML 알고리즘의 이론적 기반이 바로 이 볼록 최적화 프레임워크이다.

그러나 2010년대 들어 딥러닝이 부상하면서, ML 연구자들은 거대한 역설에 직면했다: 신경망의 손실 함수는 고도로 비볼록인데, 왜 실무에서 잘 학습되는가?

이 질문에 중요한 단서를 제공한 것이 Dauphin et al.(2014)의 연구이다. 이들은 “Identifying and Attacking the Saddle Point Problem in High-dimensional Non-convex Optimization”이라는 논문에서, 고차원 공간에서는 지역 최소(local minima)보다 안장점(saddle points)이 압도적으로 많다는 사실을 이론적·실험적으로 보였다. 직관적으로 설명하면, 100만 차원 공간의 임계점(기울기=0)에서 모든 방향이 “위”(양의 곡률)일 확률은 $0.5^{1,000,000}$ 에 가깝다. 즉, 진정한 지역 최소는 사실상 존재하지 않으며, 대부분의 정체는 안장점에서 발생한다.

비유: 볼록 함수는 그릇 모양이다 — 공을 어디서 놓아도 결국 바닥(전역 최소)으로 굴러간다. 반면 비볼록 함수는 산맥과 같다 — 계곡(지역 최소)이 여러 개 있고, 능선(안장점)도 있으며, 어디서 출발하느냐에 따라 도달하는 계곡이 달라진다. 다만 딥러닝의 산맥은 특별한 성질이 있어서, 대부분의 계곡이 비슷한 깊이를 가진다.

핵심 개념

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 정규화	예	정규화 항도 볼록

숫자로 이해하기

볼록(Convex)과 비볼록(Non-Convex)의 차이를 구체적으로 비교해 보자.

1. 볼록 함수: $f(x) = x^2$

$x = -3$ 에서 시작 -> 기울기(Gradient) = $-6$ -> 오른쪽으로 이동
$x = 5$ 에서 시작 -> 기울기 = $10$ -> 왼쪽으로 이동
어디서 시작해도 $x = 0$ (전역 최소, Global Minimum)에 도달

2. 비볼록 함수: $f(x) = x^4 - 8x^2 + 5$

지역 최소(Local Minimum)가 $x \approx -2$ 와 $x \approx 2$ 에 존재
$x = -1$ 에서 시작하면 $x \approx -2$ (지역 최소)에 갇힘
$x = 3$ 에서 시작하면 $x \approx 2$ (전역 최소)에 도달
초기값(Initialization)에 따라 결과가 달라진다

왜 중요한가? 선형 회귀(Linear Regression)의 MSE는 볼록이라 어떤 초기값에서도 같은 최적해를 찾는다. 하지만 신경망(Neural Network)은 비볼록이라 초기화(Initialization), 학습률(Learning Rate), 옵티마이저(Optimizer) 선택이 결과에 큰 영향을 미친다.

2. 볼록 최적화 (Convex Optimization)

선형 회귀

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

로지스틱 회귀

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

SVM

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

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

신경망의 손실 곡면

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

신경망의 손실 곡면 다이어그램

비볼록의 도전

현상	설명	문제
지역 최소 (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 손실 함수의 볼록성 분류

ML 손실 함수의 볼록성 분류 다이어그램 주의할 점: 볼록한 손실 함수라도 모델의 파라미터화에 의해 비볼록이 될 수 있다.

예: Cross-entropy loss 자체는 볼록이지만, 신경망의 비선형 계층을 통과하면 가중치에 대해 비볼록이 된다.
반대로, 커널 트릭(kernel trick)은 비선형 매핑을 사용하면서도 쌍대 공간에서 볼록성을 유지한다.

볼록 vs 비볼록 최적화 전략

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

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

언제 사용하는가

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

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

실전 사례

딥러닝이 비볼록인데도 잘 학습되는 이유: 과매개변수화와 SGD 노이즈의 역할

딥러닝 모델이 비볼록 손실 곡면에서 효과적으로 학습되는 현상은 이론과 실무 사이의 가장 흥미로운 간극 중 하나이다. 실제 대규모 신경망 학습에서 관찰되는 핵심 메커니즘 두 가지를 살펴보자.

1. 과매개변수화(Overparameterization)의 효과

현대 딥러닝 모델은 훈련 데이터 수보다 훨씬 많은 파라미터를 가진다(예: GPT-3는 1,750억 개 파라미터로 3,000억 토큰을 학습). 전통적 통계학에서는 이것이 심각한 과적합(overfitting)을 유발해야 하지만, 실제로는 오히려 최적화를 쉽게 만든다.

이유는 파라미터 공간이 충분히 크면, 손실 곡면의 지역 최소들이 낮은 손실의 연결 경로(connected path)로 이어지기 때문이다. 즉, “나쁜 곳에 갇히는” 상황이 구조적으로 줄어든다. Draxler et al.(2018)은 독립적으로 학습된 두 신경망의 해(solution)가 손실 장벽 없이 연결될 수 있음을 실험적으로 보여주었다.

2. SGD 노이즈의 암묵적 정규화 역할

미니배치 SGD의 확률적 기울기는 본질적으로 노이즈를 포함한다. 이 노이즈는 단순한 부작용이 아니라, 날카로운 최소(sharp minima)를 탈출하고 평탄한 최소(flat minima)에 수렴하도록 유도하는 암묵적 정규화(implicit regularization) 효과를 가진다.

실무에서 이 효과가 극적으로 나타난 사례가 있다. 대규모 분산 학습에서 배치 크기를 극도로 키운(예: 8,192 → 65,536) 팀들이 SGD 노이즈가 줄어들면서 일반화 성능이 급락하는 현상을 경험했다. 이를 해결하기 위해 LARS/LAMB 같은 레이어별 적응적 학습률이나, 학습률 워밍업이 필수적으로 도입되었다.

실무 교훈:

모델이 “너무 크다”는 걱정보다는 적절한 정규화에 집중하라
배치 크기를 키울 때는 반드시 학습률 스케일링과 워밍업을 함께 적용하라
볼록 최적화 이론만으로 딥러닝을 이해하려 하면 안 된다 — 비볼록이지만 잘 행동하는(well-behaved) 손실 곡면의 성질을 이해해야 한다

흔한 오해와 함정

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”