12.2. 볼록성¶

Colab에서 노트북 열기

SageMaker Studio Lab에서 노트북 열기

---

볼록성(convexity)은 최적화 알고리즘을 설계하는 데 핵심적인 역할을 한다. 이는 주로 그러한 맥락에서 알고리즘을 분석하고 시험하기가 훨씬 쉽기 때문이다. 다시 말해, 알고리즘이 볼록한 설정에서조차 성능이 나쁘다면, 다른 경우에서 훌륭한 결과를 기대하기는 어렵다. 더 나아가 딥러닝의 최적화 문제는 일반적으로 비볼록(nonconvex)이지만, 국소 최소점 근처에서는 종종 볼록 문제의 몇몇 성질을 보이기도 한다. 이는 (Izmailov et al., 2018)과 같은 흥미로운 새로운 최적화 변형으로 이어질 수 있다.

%matplotlib inline
import numpy as np
import torch
from mpl_toolkits import mplot3d
from d2l import torch as d2l

%matplotlib inline
from mpl_toolkits import mplot3d
from mxnet import np, npx
from d2l import mxnet as d2l

npx.set_np()

%matplotlib inline
import numpy as np
import tensorflow as tf
from mpl_toolkits import mplot3d
from d2l import tensorflow as d2l

12.2.1. 정의¶

볼록 분석을 하기 전에, _볼록 집합_과 _볼록 함수_를 정의할 필요가 있다. 이들은 머신러닝에 흔히 적용되는 수학적 도구로 이어진다.

12.2.1.1. 볼록 집합¶

집합은 볼록성의 기초이다. 간단히 말해, 벡터공간의 한 집합 $X$ 가 볼록(convex) 이려면, 임의의 $a,b\in X$ 에 대해 $a$ 와 $b$ 를 잇는 선분이 또한 $X$ 안에 포함되어야 한다. 수학적으로는 모든 $\lambda\in[0,1]$ 에 대해 다음이 성립함을 뜻한다.

(12.2.1)¶

$\lambda a+(1-\lambda)b\in X \text{ whenever } a,b\in X.$

이는 다소 추상적으로 들릴 수 있다. 그림 12.2.1을 생각해보자. 첫 번째 집합은 그 안에 포함되지 않는 선분이 존재하므로 볼록이 아니다. 반면 나머지 두 집합은 그런 문제가 없다.

그림 12.2.1 첫 번째 집합은 비볼록이고 나머지 두 집합은 볼록이다.¶

정의만으로는 그것을 가지고 무엇인가를 할 수 없다면 그다지 유용하지 않다. 여기서는 그림 12.2.2에 보인 것처럼 교집합을 살펴볼 수 있다. $X$ 와 $Y$ 가 볼록 집합이라고 가정하자. 그러면 $X\cap Y$ 역시 볼록이다. 이를 보이기 위해 임의의 $a,b\in X\cap Y$ 를 생각하자. $X$ 와 $Y$ 가 볼록이므로 $a$ 와 $b$ 를 잇는 선분은 $X$ 와 $Y$ 둘 다에 포함된다. 따라서 그 선분은 $X\cap Y$ 에도 포함되어야 하며, 이로써 정리가 증명된다.

그림 12.2.2 두 볼록 집합의 교집합은 볼록이다.¶

이 결과는 약간의 노력으로 강화할 수 있다. 볼록 집합 $X_i$ 들이 주어지면 그 교집합 $\cap_i X_i$ 는 볼록이다. 반대로(역)는 성립하지 않음을 보이려면, 서로소인 두 집합 $X\cap Y=\emptyset$ 을 생각하자. 이제 $a\in X$ 와 $b\in Y$ 를 택한다. $X\cap Y=\emptyset$ 라고 가정했으므로 그림 12.2.3에서 $a$ 와 $b$ 를 연결하는 선분에는 $X$ 에도 $Y$ 에도 속하지 않는 부분이 반드시 포함된다. 따라서 그 선분은 $X\cup Y$ 에도 속하지 않게 되며, 일반적으로 볼록 집합의 합집합은 볼록일 필요가 없다는 것이 증명된다.

그림 12.2.3 두 볼록 집합의 합집합은 볼록일 필요가 없다.¶

일반적으로 딥러닝의 문제는 볼록 집합 위에서 정의된다. 예를 들어, 실수 $d$ 차원 벡터의 집합인 $\mathbb{R}^d$ 는 볼록 집합이다(결국 $\mathbb{R}^d$ 의 임의의 두 점을 잇는 선분은 $\mathbb{R}^d$ 안에 머문다). 어떤 경우에는 길이가 제한된 변수로 작업하기도 하는데, 예컨대 $\{x\mid x\in\mathbb{R}^d \text{ and } \lVert x\rVert\le r\}$ 로 정의되는 반지름 $r$ 의 공(ball)과 같은 경우다.

12.2.1.2. 볼록 함수¶

이제 볼록 집합을 정의했으니 볼록 함수 $f$ 를 도입할 수 있다. 볼록 집합 $X$ 가 주어졌을 때, 함수 $f:X\to\mathbb{R}$ 가 모든 $x,x'\in X$ 와 모든 $\lambda\in[0,1]$ 에 대해 다음을 만족하면 $f$ 는 볼록 이다.

(12.2.2)¶

$\lambda f(x)+(1-\lambda)f(x')\ge f(\lambda x+(1-\lambda)x').$

이를 설명하기 위해 몇몇 함수를 그려보고 어떤 것이 요구조건을 만족하는지 확인해보자. 아래에서는 볼록/비볼록 함수를 몇 개 정의한다.

f = lambda x: 0.5 * x**2  # Convex
g = lambda x: torch.cos(np.pi * x)  # Nonconvex
h = lambda x: torch.exp(0.5 * x)  # Convex

x, segment = torch.arange(-2, 2, 0.01), torch.tensor([-1.5, 1])
d2l.use_svg_display()
_, axes = d2l.plt.subplots(1, 3, figsize=(9, 3))
for ax, func in zip(axes, [f, g, h]):
    d2l.plot([x, segment], [func(x), func(segment)], axes=ax)

f = lambda x: 0.5 * x**2  # Convex
g = lambda x: np.cos(np.pi * x)  # Nonconvex
h = lambda x: np.exp(0.5 * x)  # Convex

x, segment = np.arange(-2, 2, 0.01), np.array([-1.5, 1])
d2l.use_svg_display()
_, axes = d2l.plt.subplots(1, 3, figsize=(9, 3))
for ax, func in zip(axes, [f, g, h]):
    d2l.plot([x, segment], [func(x), func(segment)], axes=ax)

f = lambda x: 0.5 * x**2  # Convex
g = lambda x: tf.cos(np.pi * x)  # Nonconvex
h = lambda x: tf.exp(0.5 * x)  # Convex

x, segment = tf.range(-2, 2, 0.01), tf.constant([-1.5, 1])
d2l.use_svg_display()
_, axes = d2l.plt.subplots(1, 3, figsize=(9, 3))
for ax, func in zip(axes, [f, g, h]):
    d2l.plot([x, segment], [func(x), func(segment)], axes=ax)

예상대로 코사인 함수는 비볼록 이고, 포물선과 지수 함수는 볼록이다. 조건이 의미를 가지려면 $X$ 가 볼록 집합이어야 한다는 점에 유의하자. 그렇지 않으면 $f(\lambda x+(1-\lambda)x')$ 의 값이 잘 정의되지 않을 수도 있다.

12.2.1.3. 젠센 부등식¶

볼록 함수 $f$ 가 주어지면, 가장 유용한 수학 도구 중 하나가 젠센 부등식(Jensen’s inequality) 이다. 이는 볼록성의 정의를 일반화한 것이다.

(12.2.3)¶

$\sum_i \alpha_i f(x_i)\ge f\Big(\sum_i \alpha_i x_i\Big) \text{ and } \mathbb{E}_X[f(X)]\ge f(\mathbb{E}_X[X]),$

여기서 $\alpha_i$ 는 음이 아닌 실수이며 $\sum_i \alpha_i=1$ 이고, $X$ 는 확률변수다. 즉, 볼록 함수의 기댓값은 기댓값에 대한 볼록 함수값보다 작지 않다. 그리고 후자는 보통 더 단순한 표현이다. 첫 번째 부등식을 증명하려면 합에서 한 항씩 차례대로 볼록성의 정의를 반복 적용하면 된다.

젠센 부등식의 흔한 응용 중 하나는 더 복잡한 식을 더 단순한 식으로 상계하는 것이다. 예를 들어 부분적으로 관측된 확률변수의 로그우도(log-likelihood)에 적용할 수 있다. 즉, 다음을 사용한다.

(12.2.4)¶

$\mathbb{E}_{Y\sim P(Y)}[-\log P(X\mid Y)]\ge -\log P(X),$

왜냐하면 $\int P(Y)P(X\mid Y)dY=P(X)$ 이기 때문이다. 이는 변분(variational) 방법에서 사용할 수 있다. 여기서 $Y$ 는 보통 관측되지 않은 확률변수이며, $P(Y)$ 는 그것이 어떻게 분포할지에 대한 최선의 추정이고, $P(X)$ 는 $Y$ 를 적분으로 제거한 분포다. 예를 들어 군집화(clustering)에서는 $Y$ 가 군집 레이블이고 $P(X\mid Y)$ 는 군집 레이블을 적용했을 때의 생성 모델이 될 수 있다.

12.2.2. 성질¶

볼록 함수는 많은 유용한 성질을 가진다. 아래에서는 흔히 쓰이는 몇 가지를 설명한다.

12.2.2.1. 국소 최소는 전역 최소¶

무엇보다도, 볼록 함수의 국소 최소점은 전역 최소점이기도 하다. 이는 다음과 같이 모순법으로 증명할 수 있다.

볼록 집합 $X$ 위에 정의된 볼록 함수 $f$ 를 생각하자. $x^*\in X$ 가 국소 최소라고 가정하자. 즉, 작은 양수 $p$ 가 존재하여 $0<|x-x^*|\le p$ 를 만족하는 $x\in X$ 에 대해 $f(x^*)<f(x)$ 가 성립한다.

이제 국소 최소 $x^*$ 가 $f$ 의 전역 최소가 아니라고 가정하자. 그러면 $f(x')<f(x^*)$ 를 만족하는 $x'\in X$ 가 존재한다. 또한 $\lambda=1-\frac{p}{|x^*-x'|}$ 와 같이 $\lambda\in[0,1)$ 인 $\lambda$ 가 존재하여 $0<|\lambda x^*+(1-\lambda)x'-x^*|\le p$ 를 만족한다.

하지만 볼록 함수의 정의에 의해 다음이 성립한다.

(12.2.5)¶

$f(\lambda x^*+(1-\lambda)x')\le \lambda f(x^*)+(1-\lambda)f(x')<\lambda f(x^*)+(1-\lambda)f(x^*)=f(x^*),$

이는 $x^*$ 가 국소 최소라는 가정과 모순이다. 따라서 $f(x')<f(x^*)$ 인 $x'\in X$ 는 존재할 수 없다. 즉, 국소 최소 $x^*$ 는 전역 최소이기도 하다.

예를 들어 볼록 함수 $f(x)=(x-1)^2$ 는 $x=1$ 에서 국소 최소를 가지며, 이는 전역 최소이기도 하다.

f = lambda x: (x - 1) ** 2
d2l.set_figsize()
d2l.plot([x, segment], [f(x), f(segment)], 'x', 'f(x)')

f = lambda x: (x - 1) ** 2
d2l.set_figsize()
d2l.plot([x, segment], [f(x), f(segment)], 'x', 'f(x)')

f = lambda x: (x - 1) ** 2
d2l.set_figsize()
d2l.plot([x, segment], [f(x), f(segment)], 'x', 'f(x)')

볼록 함수에서 국소 최소가 전역 최소이기도 하다는 사실은 매우 편리하다. 이는 함수를 최소화할 때 “막히는” 일이 없다는 뜻이다. 다만 이것이 전역 최소가 반드시 하나만 존재한다거나, 아예 존재하지 않는 경우가 없다는 뜻은 아니다. 예를 들어 함수 $f(x)=\max(|x|-1,0)$ 는 구간 $[-1,1]$ 전반에서 최소값을 갖는다. 반대로 함수 $f(x)=\exp(x)$ 는 $\mathbb{R}$ 에서 최소값을 갖지 않는다. $x\to-\infty$ 일 때 0으로 점근하지만, $f(x)=0$ 을 만족하는 $x$ 는 존재하지 않는다.

12.2.2.2. 볼록 함수의 하부 집합은 볼록¶

볼록 집합은 볼록 함수의 하부 집합(below set) 을 통해 편리하게 정의할 수 있다. 구체적으로, 볼록 집합 $X$ 위에 정의된 볼록 함수 $f$ 가 주어졌을 때, 임의의 하부 집합

(12.2.6)¶

$S_b=\mathrm{def}\{x\mid x\in X \text{ and } f(x)\le b\}$

는 볼록이다.

이를 빠르게 증명해보자. 임의의 $x,x'\in S_b$ 에 대해, $\lambda\in[0,1]$ 이면 $\lambda x+(1-\lambda)x'\in S_b$ 임을 보이면 된다. $f(x)\le b$ 그리고 $f(x')\le b$ 이므로, 볼록성의 정의에 의해

(12.2.7)¶

$f(\lambda x+(1-\lambda)x')\le \lambda f(x)+(1-\lambda)f(x')\le b.$

12.2.2.3. 볼록성과 2차 도함수¶

함수 $f:\mathbb{R}^n\to\mathbb{R}$ 의 2차 도함수가 존재한다면, $f$ 가 볼록인지 여부를 확인하기는 매우 쉽다. $f$ 의 헤시안(Hessian)이 양의 준정부호(positive semidefinite)인지 확인하면 된다: $\nabla^2 f\succeq 0$, 즉 헤시안 행렬 $\nabla^2 f$ 를 $H$ 로 쓸 때 모든 $x\in\mathbb{R}^n$ 에 대해 $x^\top H x\ge 0$ 이면 된다. 예를 들어 함수 $f(x)=\frac{1}{2}\lVert x\rVert^2$ 는 $\nabla^2 f=1$ 이므로 볼록인데, 이는 헤시안이 항등행렬임을 의미한다.

형식적으로, 2번 미분 가능한 1차원 함수 $f:\mathbb{R}\to\mathbb{R}$ 는 2차 도함수 $f''\ge 0$ 일 때 그리고 그때에만 볼록이다. 2번 미분 가능한 다차원 함수 $f:\mathbb{R}^n\to\mathbb{R}$ 는 헤시안 $\nabla^2 f\succeq 0$ 일 때 그리고 그때에만 볼록이다.

먼저 1차원 경우를 증명해야 한다. $f$ 가 볼록이면 $f''\ge 0$ 임을 보이기 위해 다음 사실을 사용한다.

(12.2.8)¶

$\frac{1}{2}f(x+\epsilon)+\frac{1}{2}f(x-\epsilon)\ge f\Big(\frac{x+\epsilon}{2}+\frac{x-\epsilon}{2}\Big)=f(x).$

2차 도함수는 유한차분의 극한으로 주어지므로, 다음이 성립한다.

(12.2.9)¶

$f''(x)=\lim_{\epsilon\to 0} \frac{f(x+\epsilon)+f(x-\epsilon)-2f(x)}{\epsilon^2}\ge 0.$

이제 $f''\ge 0$ 이면 $f$ 가 볼록임을 보이자. $f''\ge 0$ 이면 $f'$ 는 단조 비감소 함수가 된다. $\mathbb{R}$ 의 세 점 $a<x<b$ 를 잡고, $x=(1-\lambda)a+\lambda b$ 및 $\lambda\in(0,1)$ 라고 하자. 평균값 정리에 의해 $\alpha\in[a,x]$, $\beta\in[x,b]$ 가 존재하여

(12.2.10)¶

$f'(\alpha)=\frac{f(x)-f(a)}{x-a} \text{ and } f'(\beta)=\frac{f(b)-f(x)}{b-x}.$

단조성에 의해 $f'(\beta)\ge f'(\alpha)$ 이므로

(12.2.11)¶

$\frac{x-a}{b-a}f(b)+\frac{b-x}{b-a}f(a)\ge f(x).$

$x=(1-\lambda)a+\lambda b$ 이므로 다음을 얻는다.

(12.2.12)¶

$\lambda f(b)+(1-\lambda)f(a)\ge f((1-\lambda)a+\lambda b),$

즉 볼록성이 증명된다.

둘째로, 다차원 경우를 증명하기 전에 보조정리(lemma)가 필요하다. $f:\mathbb{R}^n\to\mathbb{R}$ 가 볼록일 필요충분조건은 모든 $x,y\in\mathbb{R}^n$ 에 대해

(12.2.13)¶

$g(z)=\mathrm{def}\ f(zx+(1-z)y)\text{ where } z\in[0,1]$

가 볼록인 것이다.

$f$ 가 볼록이면 $g$ 가 볼록임을 보이려면, 모든 $a,b,\lambda\in[0,1]$ (따라서 $0\le \lambda a+(1-\lambda)b\le 1$)에 대해 다음을 보이면 된다.

(12.2.14)¶

$g(\lambda a+(1-\lambda)b)=f((\lambda a+(1-\lambda)b)x+(1-\lambda a-(1-\lambda)b)y)=f(\lambda(ax+(1-a)y)+(1-\lambda)(bx+(1-b)y))\le \lambda f(ax+(1-a)y)+(1-\lambda)f(bx+(1-b)y)=\lambda g(a)+(1-\lambda)g(b).$

역을 증명하려면 모든 $\lambda\in[0,1]$ 에 대해 다음을 보이면 된다.

(12.2.15)¶

$f(\lambda x+(1-\lambda)y)=g(\lambda\cdot 1+(1-\lambda)\cdot 0)\le \lambda g(1)+(1-\lambda)g(0)=\lambda f(x)+(1-\lambda)f(y).$

마지막으로 위 보조정리와 1차원 결과를 사용하면 다차원 경우는 다음과 같이 증명된다. 다차원 함수 $f:\mathbb{R}^n\to\mathbb{R}$ 는 모든 $x,y\in\mathbb{R}^n$ 에 대해 $g(z)=\mathrm{def}\ f(zx+(1-z)y)$ (여기서 $z\in[0,1]$)가 볼록일 때 그리고 그때에만 볼록이다. 1차원 결과에 의해, 이는 모든 $x,y\in\mathbb{R}^n$ 에 대해 $g''=(x-y)^\top H(x-y)\ge 0$ (여기서 $H=\mathrm{def}\nabla^2 f$)일 때 그리고 그때에만 성립한다. 이는 양의 준정부호 행렬의 정의에 의해 $H\succeq 0$ 와 동치다.

12.2.3. 제약¶

볼록 최적화의 장점 중 하나는 제약을 효율적으로 다룰 수 있다는 점이다. 즉, 다음 형태의 제약 최적화(constrained optimization) 문제를 풀 수 있게 해준다.

(12.2.16)¶

$\text{minimize}~_x\ f(x)\ \text{subject to } c_i(x)\le 0 \text{ for all } i\in\{1,\ldots,n\},$

여기서 $f$ 는 목적함수이고 $c_i$ 는 제약 함수다. 이것이 의미하는 바를 보기 위해 $c_1(x)=\lVert x\rVert^2-1$ 인 경우를 생각하자. 이때 파라미터 $x$ 는 단위 공(unit ball) 안으로 제한된다. 두 번째 제약이 $c_2(x)=v^\top x+b$ 라면, 이는 모든 $x$ 가 어떤 반공간(half-space)에 놓인다는 뜻이다. 두 제약을 동시에 만족시키는 것은 공의 한 조각(slice)을 선택하는 것과 같다.

12.2.3.1. 라그랑지안¶

일반적으로 제약 최적화 문제를 푸는 것은 어렵다. 이를 다루는 한 가지 방법은 물리학에서 유래하며, 비교적 단순한 직관을 따른다. 상자 안의 공을 상상해보자. 공은 가장 낮은 곳으로 굴러가며, 중력에 의한 힘은 상자 벽이 공에 가할 수 있는 힘과 균형을 이룬다. 요컨대 목적함수의 기울기(즉 중력)는 제약함수의 기울기에 의해 상쇄된다(공이 상자 안에 있어야 하므로 벽이 “되밀어” 준다). 또한 어떤 제약은 활성화(active)되지 않을 수도 있다. 공이 닿지 않는 벽은 공에 어떤 힘도 가할 수 없다.

Lagrangian $L$ 의 유도는 건너뛰고, 위의 추론은 다음의 안장점(saddle point) 최적화 문제로 표현될 수 있다.

(12.2.17)¶

$L(x,\alpha_1,\ldots,\alpha_n)=f(x)+\sum_{i=1}^n \alpha_i c_i(x)\text{ where } \alpha_i\ge 0.$

여기서 변수 $\alpha_i$ ($i=1,\ldots,n$)는 제약이 제대로 강제되도록 하는 이른바 라그랑주 승수(Lagrange multipliers) 이다. 이들은 모든 $i$ 에 대해 $c_i(x)\le 0$ 을 만족시키기에 충분히 클 정도로 선택된다. 예를 들어 어떤 $x$ 에 대해 $c_i(x)<0$ 가 자연스럽게 성립한다면, $\alpha_i=0$ 을 택하게 된다. 또한 이는 안장점 최적화 문제로서, 모든 $\alpha_i$ 에 대해 $L$ 을 최대화 하는 동시에 $x$ 에 대해 최소화 하고자 한다. $L(x,\alpha_1,\ldots,\alpha_n)$ 라는 함수 형태에 도달하는 방법을 설명하는 풍부한 문헌이 존재한다. 여기서는 $L$ 의 안장점이 원래의 제약 최적화 문제가 최적으로 풀리는 지점이라는 사실만 알면 충분하다.

12.2.3.2. 페널티¶

제약 최적화 문제를 적어도 근사적으로 만족시키는 한 가지 방법은 라그랑지안 $L$ 을 변형하는 것이다. $c_i(x)\le 0$ 를 정확히 만족시키는 대신, 목적함수 $f(x)$ 에 $\alpha_i c_i(x)$ 를 단순히 더한다. 이는 제약이 과도하게 위반되지 않도록 해준다.

사실 우리는 이 요령을 계속 사용해왔다. 섹션 3.7의 가중치 감쇠(weight decay)를 생각해보자. 거기서는 $w$ 가 너무 커지지 않도록 목적함수에 $\frac{\lambda}{2}\lVert w\rVert^2$ 를 더한다. 제약 최적화 관점에서 보면, 이는 어떤 반지름 $r$ 에 대해 $\lVert w\rVert^2-r^2\le 0$ 이 되도록 보장하는 셈이다. $\lambda$ 값을 조절하면 $w$ 의 크기를 변화시킬 수 있다.

일반적으로 페널티를 추가하는 것은 제약을 근사적으로 만족시키는 좋은 방법이다. 실제로는 이것이 정확한 만족보다 훨씬 견고한 경우가 많다. 또한 비볼록 문제에서는, 볼록 경우에서 정확한 접근을 매력적으로 만드는 많은 성질(예: 최적성)이 더 이상 성립하지 않는다.

12.2.3.3. 사영(프로젝션)¶

제약을 만족시키기 위한 또 다른 전략은 사영(projection)이다. 역시 이전에 이를 본 적이 있는데, 예컨대 섹션 9.5에서 그래디언트 클리핑을 다룰 때다. 거기서는 다음을 통해 그래디언트의 길이가 $\theta$ 로 제한되도록 했다.

(12.2.18)¶

$g\leftarrow g\cdot \min(1,\theta/\lVert g\rVert).$

이는 $g$ 를 반지름 $\theta$ 인 공에 사영한 것임이 드러난다. 더 일반적으로, 볼록 집합 $X$ 위의 사영은 다음과 같이 정의된다.

(12.2.19)¶

$\mathrm{Proj}_X(x)=\arg\min_{x'\in X}\ \lVert x-x'\rVert,$

즉 $x$ 에서 $X$ 안의 점들 중 가장 가까운 점이다.

그림 12.2.4 볼록 사영.¶

사영의 수학적 정의는 다소 추상적으로 들릴 수 있다. 그림 12.2.4는 이를 좀 더 명확히 설명한다. 여기에는 원과 마름모 두 개의 볼록 집합이 있다. 두 집합 안에 있는 점(노란색)은 사영을 해도 바뀌지 않는다. 두 집합 밖에 있는 점(검은색)은 원래 점(검은색)에서 가장 가까운 집합 내부의 점(빨간색)으로 사영된다. $\ell_2$ 공의 경우 방향은 유지되지만, 마름모의 경우에서 볼 수 있듯 일반적으로 항상 그런 것은 아니다.

볼록 사영의 한 가지 용도는 희소(sparse) 가중치 벡터를 계산하는 것이다. 이 경우 가중치 벡터를 $\ell_1$ 공에 사영하는데, 이는 그림 12.2.4의 마름모 경우를 일반화한 것이다.

12.2.4. 요약¶

딥러닝 맥락에서 볼록 함수의 주요 목적은 최적화 알고리즘을 동기화하고, 그것들을 자세히 이해하도록 돕는 것이다. 다음에서는 경사하강법과 확률적 경사하강법이 이러한 관점에서 어떻게 도출될 수 있는지 보게 될 것이다.

• 볼록 집합들의 교집합은 볼록이다. 합집합은 그렇지 않다.
• 볼록 함수의 기댓값은 기댓값의 볼록 함수값보다 작지 않다(젠센 부등식).
• 2번 미분 가능한 함수는, 그 헤시안(2차 도함수들로 이루어진 행렬)이 양의 준정부호일 때 그리고 그때에만 볼록이다.
• 볼록 제약은 라그랑지안을 통해 추가할 수 있다. 실무에서는 대개 목적함수에 페널티로 단순히 더한다.
• 사영은 원래 점과 가장 가까운 볼록 집합 내의 점으로 매핑한다.

12.2.5. 연습문제¶

1. 집합의 볼록성을 확인하기 위해, 집합 내부의 점들 사이에 모든 선분을 그려서 그 선분이 집합에 포함되는지 확인한다고 하자.

   1. 경계(boundary) 위의 점들만 확인해도 충분함을 증명하라.
   2. 집합의 꼭짓점(vertices)만 확인해도 충분함을 증명하라.

2. $B_p[r]=\mathrm{def}\{x\mid x\in\mathbb{R}^d \text{ and } \lVert x\rVert_p\le r\}$ 를 $p$-노름을 사용한 반지름 $r$ 의 공이라 하자. 모든 $p\ge 1$ 에 대해 $B_p[r]$ 가 볼록임을 증명하라.

3. 볼록 함수 $f$ 와 $g$ 가 주어졌을 때, $\max(f,g)$ 도 볼록임을 보여라. 또한 $\min(f,g)$ 는 볼록이 아님을 증명하라.

4. 소프트맥스 함수의 정규화 항이 볼록임을 증명하라. 보다 구체적으로 $f(x)=\log\sum_i \exp(x_i)$ 의 볼록성을 증명하라.

5. 선형 부분공간, 즉 $X=\{x\mid Wx=b\}$ 가 볼록 집합임을 증명하라.

6. $b=0$ 인 선형 부분공간의 경우, 사영 $\mathrm{Proj}_X$ 를 어떤 행렬 $M$ 에 대해 $Mx$ 로 쓸 수 있음을 증명하라.

7. 2번 미분 가능한 볼록 함수 $f$ 에 대해, 어떤 $\xi\in[0,\epsilon]$ 가 존재하여 $f(x+\epsilon)=f(x)+\epsilon f'(x)+\frac{1}{2}\epsilon^2 f''(x+\xi)$ 로 쓸 수 있음을 보여라.

8. 볼록 집합 $X$ 와 두 벡터 $x$, $y$ 가 주어졌을 때, 사영이 거리를 증가시키지 않음을 증명하라. 즉, $\lVert x-y\rVert\ge \lVert \mathrm{Proj}_X(x)-\mathrm{Proj}_X(y)\rVert$ 임을 보여라.

---

목차

• 볼록성
  • 1. 정의
    • 1.1. 볼록 집합
    • 1.2. 볼록 함수
    • 1.3. 젠센 부등식
  • 2. 성질
    • 2.1. 국소 최소는 전역 최소
    • 2.2. 볼록 함수의 하부 집합은 볼록
    • 2.3. 볼록성과 2차 도함수
  • 3. 제약
    • 3.1. 라그랑지안
    • 3.2. 페널티
    • 3.3. 사영(프로젝션)
  • 4. 요약
  • 5. 연습문제