LG Aimers | Convex Optimization (볼록 최적화)

 

1) Optimization Using Gradien Descent

2) Constrained Optimization and Lagrange Multipliers

3) Convex Sets and Functions

4) Convex Optimization 

 

최적화는 기계학습 이용에 중요

모델의 좋은 파라미터는 특정 Optimization 문제의 Solution이 되는 경우가 많음 

 

 

 

Optimization 종류

• Unconstrained Optimization
• Constrained Optimization
• Convex optimization

 

함수 최적화 Point는 Gradient와 관련 있음

▶  $f'(x) =0$ Point가 함수의 Minimum

 

 

 

📌 Gradient Descent를 이용한 최적화 

Unconstrained Optimization & Gradient Algorithms

 

min $f(x),  f(x) : \mathbb{R^n} \mapsto  \mathbb{R},   f \in C^1$

 

f는 R차원 Vector를 어떤 Singular R로 Mapping하는 함수

 

▶ Unconstrained Optimization, 즉 x에 대한 조건이 없을 때 적용할 수 있는 알고리즘

 

 

🔎 Gradient - type Algorithms

 

f 함수를 최소화하기 위한 Iterative Algorithm (재귀형 알고리즘)

• $x_{k+1} = x_k + \gamma_kd_k,  k = 0, 1, 2, ...$ 

▶$x_0$는 Random 정의

▶ $\gamma_k$는 Stepsize라고 부르는 Scaler 값

▶ $d_k$는 방향성을 나타내는 Direction 

 

 

Lemma. (보조정리)

d가 $\triangledown f(x) · d < 0$ (= 어떤 Gradient와 내적 값이 0이 된다면)

Stepsize $\alpha$ 를 잘 정하면 업데이트했을 때, 현재 값보다 더 낮아지는 $\alpha$가 존재

 

 

∴ Gradient 반대 방향 & $\gamma_k$ Stepsize Control, 함수 최소화하는 업데이트 값 구할 수 있음

 

▶ 함수의 Local Optima로 수렴

 

 

 

🔎 Steepest gradient descent (=gradient descent)

 

$d_k = -\triangledown f(x_k)^T$

 

▶  방향을 Gradient의 반대 방향 (= 내적해서 0이 되는 방향)으로 선택하는 것

 

 

 

Taxonomy

 

Objective Function은 Data로부터 정해지는 경우가 많음

 

$min L(\theta)$

▶ $\theta$는 Model의 Parameter

▶ L은 Model의 Loss 함수 

 

L function을 얼마큼의 데이터로 정의하느냐에 따라 

• Batch gradient descent 
• Mini-batch gradient descent 
• Stochastic gradient descent

 

업데이트 방식

 

Gradient 방향만 고려하는 Standard Gradient Descent 말고

adaptive하게 방향도 새로 정하는 방식도 존재 (e.g. Momentum)  

 

 

Stochastic Gradient Descent (SGD)

 

$L(\theta) = \sum_{i=1}^n L_n(\theta)$ 

 

Loss 함수는 Data point에 대한 Loss의 Summation 형태로 표현되는 경우가 많음 

 

 

Gradient update

 

Parameter를 Gradient와 반대 방향으로 업데이트 

$\theta_{k+1} = \theta_k - \gamma_k\triangledown L(\theta_k)^T = \theta_k - \gamma_k \sum^N_{n=1} \triangledown L_n(\theta_k)^T$

 

▶ $\gamma_k$는 Stepsize

▶ gradient가 각각의 Gradient의 Summation으로 표현

 

 

만약 N이 엄청 클 경우, 업데이트 시마다 Summation을 매번 계산해야 하므로 계산량이 많음

 

1. Batch gradient : 모든 Data point를 고려해서 계산하는 방식

$\sum^N_{n=1} \triangledown L_n(\theta_k)^T$

 

2. Mini-batch gradient : Data point n개 中 특정 subset을 구해서 subset에 있는 gradient만 계산

$\sum_{n\in \mathcal{K}} \triangledown L_n(\theta_k)^T $

$\mathcal{K}, |\mathcal{K}| < n$ 

 

3. Stochastic Gradient : Subset을 구한 Gradient의 Expectation이 Full Batch Gradient와 동일

Mini-batch 방식이 Origianl batch gradient를 근사할 수 있게 업데이트하는 방식

 

Stochastic Gradient 방식

 

 

Adaptivity for Better Convergence : Momentum

 

Gradient Descent는 Stepsize 설정에 따라 Convergence Speed(수렴 속도)가 달라짐

 

▶ 너무 작으면 업데이트 속도가 느림

▶ 너무 크면 overshoot 발생으로 수렴 X

 

 

Gradient 변형 방식 : Momentum

 

$x_{k+1} = x_k - \gamma_i \triangledown f(x_k)^T + \alpha \Delta x_k,  \alpha \in [0,1]$

 

▶ $\Delta x_k= x_k -x_{k-1}$ , 전에 업데이트했던 방향 

▶ 다음 업데이트 시, 전에 업데이트한 방향 고려

▶ 과거의 정보들을 향후 업데이트에 반영하면 수렴을 가속화할 수 있음 

 

 

📌 Constrained Optimization and Lagrange Multipliers

x에 대한 특정 조건이 있다면, gradient descent 알고리즘 바로 적용이 어려움

 

e.g.

f(x) 최소화 문제

제약 조건

▶ $g_i(x) \le 0$ (Inequality constraints)

▶ $h_j(x) = 0$ (Equality constraints)

 

f함수의 Gradient 고민하여 업데이트하면 조건 불만족되는 경우 발생

 

 

x : Optimization Variable $p^x$ : Optimal value$x^*$ : Optimizer ($p^x$를 만족한 x)

 

 

Q. Constrained Optimization을 Unconstrained Opimization 문제처럼 쉽게 풀 수 없을까?

 

 

Problem Solving via Langrange Multipliers

 

🔎 Lagrangian

 

$\mathcal{L}(x, \lambda, \nu) = f(x) + \sum_{i=1}^m \lambda_ig_i(x) + \sum_{i=1}^p \nu_i h_i(x)$

 

▶  Origianl objective : f(x)

▶  Lagrange Multiplier (dual variables) : $\lambda = (\lambda_i : i = 1, \cdots, m) \ge 0$, $\nu = (\nu_1, \cdots, \nu_p)$

$\lambda$는 항상 0보다 커야 함, $\nu$는 별도 제약 없음

 

🔎 Lagrange dual functin 

 

$\mathcal{D}(\lambda, \nu) =$ inf $\mathcal{L}(x, \lambda, \nu)$

 

Lagrange function의 $\lambda$와 $\nu$를 고정했을 때 x에 대한 Infimum 값

 

 

✅ Original Optimization : x에 대한 함수

✅ Lagrange Dual Function : $\lambda, \nu$에 대한 함수 

▶ $\lambda, \nu$는 Constraint 조건마다 정의

 

 

 

Lower Bound on the Optimal Value

 

Lagrange Dual Function은 Optimal Value의 Lower bound

 

Theorem.

$\mathcal{D}(\lambda, \nu) \preceq p^x$, $\forall\lambda \succeq, \nu$

 

▶어떤 $\lambda, \nu$에 대해서도 origianl optimal value보다 Lower bound

 

Proof.

어떤 feasible $\tilde{x}$ 에 대해서도 (= Optimization 조건을 만족 = $g(x)\le 0$, $h(x)=0$)

 

$\mathcal{L}(\tilde{x},\lambda, \nu) = f(\tilde{x}) + \sum_{i=1}^m \lambda_i g_i(\tilde{x}) + \sum_{i=1}^p \nu_i h_i(\tilde{x}) \le f(\tilde{x})$

 

▶$\lambda$는 0보다 크고 g(x)는 0보다 작음

▶ h(x) = 0이므로 뒤에 있는 시그마 값은 날아감

 

$f(\tilde{x})$에 0보다 작은 값을 더해주므로 결괏값이 $f(\tilde{x})$보다 작거나 같아지게 됨 

 

 

 

∴ 어떤 feasilbe x에 대해서도 f(x)보다 Lagrangian 함수가 작음

▶ Lagrange Dual function은 Lagrangian에 infimum을 취하는 것이기 때문에  더 작음 

 

 

∴ 어떤 feasilbe x에 대해서도 f(x)보다 Lagrange Dual 함수가 작음

 

$\mathcal{D}(\lambda, \nu) \le p^*$

 

 

 

 

Q. Lower bound를 Maximization 한다면?

A. 그래도 Optimization의 Lower bound가 됨

 

 

Q. Lower bound를 찾는 최적의 solution

A. Langrangian Dual Problem

 

 

Original Optimization ▶ x에 대한 Optimization

Dual problem ▶ $\lambda, \nu$ 에 대한 Optimization

 

 

✅ Dual 문제는 항상 Convex Optimization 

▶ Dual Function이 항상 $\lambda, \nu$에 대한 Concave 함수가 됨 

▶ Dual 문제가 Primal 문제보다 쉽고 Primal 문제의 Lower bound를 제공 ($d^* < p*$)

 

 

Weak Duality

 

Primal Optimization & Dual Optimization 관계 설명

 

$d^* \le p^*$

 

▶ duality gap : $p* -d*$

 

 

 

📌 Convex Sets and Functions

 

Convex Optimization

 

f(x) 최소화 문제

x 조건 : $x \in X$

 

▶ f(x)는 Convex function, $X$는 Convex Set

 

✔️문제 풀이 여부는 Linearity(선형 여부)가 아닌 f와 조건들의 Convex 여부로 달라짐

 

 

 

Convex Set

Convex Set O

 

Convex Set X

Convex Set X

 

사진 출처 : https://ratsgo.github.io/convex%20optimization/2017/12/25/convexset/

Convex Sets · ratsgo's blog

 

 

set에서 Point $x_1, x_2$를 잡고 그 둘을 가르는 선분을 그었을 때, 선분이 항상 Set 안에 포함되어 있는 경우

 

 

 

Convex Functions

 

▶ $\theta = \frac {1}{2}$ 로 가정

 

어떤 Point x, y에 대해서도

 

$f(\frac{x+y}{2}) \le \frac{1}{2}f(x) + \frac{1}{2}f(y)$ 성립

 

 

 

Strictly convex 

$\le$ 가 아닌 < 만 성립할 때 

 

 

 

concave

f에 음수를 취했을 때 $-f$가 convex면 concave라고 부름

 

▶ convex 함수는 볼록함수, concave 함수는 오목함수 

 

 

 

Affine function

ax + b (=linear function)

 

▶convex & concave 모두 만족

 

 

 

Jensen's inequality

random variable(X)이 주어져있을 때, 

$f(\mathbb{E}[X]) \le \mathbb{E}[f(X)]$

 

 

 

 

Conditions of Convex Functions (1)

 

🔎 First-order condition.

Gradient 정보 이용 Convex 함수 정의 

 

Convex 함수는 접선 그으면 접선보다 함수가 항상 위에 있다

$f(y) -f(x) \ge \triangledown f(x)^T(y-x)$

 

 

e.g.  $f(y) = y^2$

 

 

만약 $\triangledown f(x)=0$이라면

 

▶ 항상 $f(y)\le f(x)$, f(x)가 global minimizer

 

 

∴ 함수 minimization point와 gradient zero point($\triangledown f(x)$)가 동치

▶ gradient는 local 정보인데 local optimum과 global optimum이 일치 

 

 

 

Conditions of Convex Functions (2)

 

🔎 Second-order condition.

 

f를 두 번 미분한 Hassian Matrix가 Positive Semidefinite Matrix인 경우, 함수가 Convex

 

$\triangledown^2 f(x)^2 \succeq 0$

 

▶ Hassian Matrix에 해당하는 Eigenvalue가 항상 0보다 크면 함수가 Convex 하다 

 

 

 

• Log 함수는 Concave / 음수 취하면 Convex 함수 
• 어떤 함수의 최댓값을 취한 것들은 Convex 함수
• Log Summation 함수는 Convex 함수

 

 

Convexity-Preserving Operations

 

• Convex 함수들 선형결합 시($f= \sum_{i=1}^n w_if,_i)$ 그것도 Convex 함수
• f(x) convex 일 경우, 선형 Transformation 후($g(x) = f(Ax +b)$ f를 취해도 Convex
• $f_1, f_2$ 가 Convex 하면 $f(x) = max{f_1(x), f_2(x)}$도 Convex
• h와 g가 Convex & h가 nondecresing 이면 h와 g의 Composition도($f(x)=h(g(x))$) Convex 

 

 

 

Point-wise Supremum

 

if )  f(x, y)가 y가 주어져있을 때, 항상 Convex라면 y에 대한 최소상계를 취한 함수도 Convex

 

$g(x) = \sup_{y\in \mathcal{A}} f(x,y)$

 

 

if) f(x, y)가 y가 고정되어 있을 때, Concave라면 y에 대한 최대하계를 취한 함수도 Concave

 

$g(x) = \inf_{y\in \mathcal{A}} f(x,y)$

 

 

 

e.g.  Dual Function은 항상 Concave

 

$\mathcal{D}(\lambda, \nu) = \inf_x \mathcal{L} (x, \lambda, \nu)$

 

▶ Lagrange Dual 함수는 $\lambda, \nu$ 에 대한 선형함수 

▶  x를 고정했을 때, 함수는 Concave 함수가 되기도 하고 Convex 함수가 되기도 함.

 

 

∴ Concave 함수 최대화 문제는 Convex Optimization

 

 

📌 Convex Optimization

 

Standard Convex Optimization

 

Convex function을 Convext Set을 주고 Constraint를 주고 하는 Optimization

 

f(x) 최소화 문제 

 

조건

▶ $g_i(x)$ 는 Convex Set

▶ $a_i^T x$는 Convex 조건

 

 

 

Strong Duality

 

Dual Problem Optimum과 Primal Proble Optimum이 동치

 

$d^* = p^*$

 

▶ Convex Optimization 이 풀기 쉬운 이유 

 

 

 

KKT Condition

 

$x^*$ : Primal Optimization Solution

$\lambda^* , \nu^*$ : Dual Optimization Solution

 

 

$x^*$ 와 $\lambda^*$가 조건을 만족하면, KKT Condition 만족

 

🔎 Karush-Kuhn-Tucker optimality condition 

$g_i(x^*) \le 0$, $h_i(x^*) = 0$, $\lambda_i^* \succeq 0$

 

$\lambda_i^* g_i(x^*) = 0$

 

• 어떤 Optimization Problem도 KKT Condition이 Optimality의 필요조건
• Convex Optimization의 경우, KKT가 Sufficient Condition (If and only if 조건)

 

 

$\triangledown f(x^*) + \sum_{i=1}^m \lambda_i^* \triangledown g_i(x^*) + \sum^p_{i=1} \nu_i^* \triangledown h_i(x^*) =0$

 

Lagrangian Function Gradient가 0이 되어야 하는 조건

 

▶  위 조건을 만족하는 $\lambda^*$ 와 $x^*$가 Primal & Dual Optimum

 

 

 

Linear Programming

 

Objective가 Linear & Constraint도 Linear 한 경우, Dual Problem도 Linear 형태 

 

 

▶ Convex Optimization 형태이므로 Primal Solution = Dual Solution

 

 

 

Quadratic Programming

 

2차 함수 최소화 경우에도 Primal Problem & Dual Problem 동치 이용