[LG Aimers] Module 2.2(Mathematics for ML) : Convex Optimization

AI Fundamentals/LG Aimers 3기

Jae. 2023. 7. 6. 23:07

728x90

1. Optimization

Machine Learning model을 학습한다고 했을 때, Optimization 문제로 구성됨
- Model의 좋은 Parameter를 찾는 과정
- 특정 Optimization 문제의 solution이 되는 경우가 많음

Optimization의 종류
- Unconstrained Optimization (제약식이 존재하지 X)
- Constrained Optimization (제약식이 존재 O)
- Convex Optimization

Optimization Model의 구성요소
- 외부의 data인 parameter를 이용하여 구성한 Optimization model을 통해 모든 Constraints를 만족하는 decision variable들 중에 objective function을 최대화 / 최소화 시키는 decision variable의 값을 구하기
  - Decision Variables : 의사결정변수
  - Objective Function : 목적함수
  - Constraints : 제약식
  - Parameters : 상수(Const)
  - Feasible Solution : 모든 constraints를 만족하는 의사결정 변수들의 조합
  - Feasible Set : 모든 feasible solution들의 집합
  - Optimal Solution : feasible solution 중에서 objective function을 최대화 / 최소화하는 solution

2. Optimization using gradient descent

$d_{k}$를 gradient와 반대방향으로 아무렇게나 잡고, step size $\gamma _{k}$를 잘 조정하기만 하면 항상 이 함수 $f(x)$를 최소화하는 다음 update된 값 $x_{k+1}$을 구할 수 있음
Steepest gradient descent : $\nabla f(x) \cdot d <0$ 을 만족하는 d 중에 $\nabla f(x)$의 반대방향으로 d를 선택하는 것이 steepest GD라 한다

Objective Function은 어떤 data로부터 정해지는 경우가 많음
- L : loss function
- $theta$ : parameter
$L$이라는 function을 얼마만큼의 data로 정의하느냐에 따라 구분됨
- Batch gradient descent (entire n)
- Mini-batch gradient descent (k < n data)
- Stochastic gradient descent (k < n data with unbiased gradient estimation)

Stochastic Gradient Descent
- Loss function : Data point에 대한 loss의 summation으로 표시
- 현재 parameter를 gradient와 반대 방향으로 업데이트
- $\Theta _{k+1} = \Theta _{k} - \gamma _{k} \nabla L(\Theta _{k})^{T} = \Theta_{k}- \gamma_{k}\sum_{n=1}^{N}\nabla L_{n}(\Theta_{k})^{T}$

Step Size $\gamma$ : 적당하게 설정해야 함
- 너무 작게 설정 : update가 천천히 일어남
- 너무 크게 설정 : overshooting이 일어남 (converge하지 않음)

Momentum with Gradient Descent
- $x_{k+1} = x_{k} - \gamma_{i} \nabla f(x_{k})^{T} + \alpha \Delta x_{k}$
- update 항 뒤에 추가항을 추가 : $\alpha \Delta x_{k}$
- $\Delta x_{k} = x_{k} - x_{k-1}$ : 그 전에 update 했던 방향
- 그 다음 방향으로 update할 때도 그 전에 update 했던 방향을 고려하자는 의미

3. Constrained Optimization and Lagrange Multipliers

Constrained Optimization ($f(\tilde{x})$, constraints) -> Unconstrained Optimizations($L(\tilde{x}, \lambda, \nu$))
Primal 문제를 푸는 것보다 Dual 문제를 푸는 것이 더 쉽다

$\lambda, \nu$ : Lagrange multiplier
- all $\lambda \geq 0$, $\nu$는 제약 조건 없음
- constraint에 해당하는 조건마다 $\lambda, \nu$가 정의됨

Lagrange dual function
- $\lambda, \nu$를 고정했을 때 x에 대한 lnfimum(하한)값을 칭함
- original optimization 문제는 x에 대한 함수, lagrange dual 함수는 $\lambda, \nu$에 대한 함수

Feasible $\tilde{x}$ : 모든 constraints 를 만족하는 solution
- $g_{i}(\tilde{x}) \leq 0$, $h_{i}(\tilde{x}) = 0$

Best lower bound 찾기
- maximize $D(\lambda, \nu)$
- $\lambda, \nu$ 에 대한 optmization
Dual optimization은 항상 Convex optimization이 됨
- convex optimization은 항상 풀 수 있다!
- $D(\lambda, \nu)$ 가 always concave function이 된다

4. Convex Set and Functions

convex optimization
- f(x)라는 함수를 minimize
- $x \in X$ : constraint
- f(x) : convex function
- X: convex set
- convex function을 convex set을 constraint로 주고 하는 optimization

Convex function : 아래로 볼록인 함수
- 두점을 잇는 임의의 line segment가 always function보다 위에 존재
- affine functions(ex.linear function)들은 concave & convex 동시에 만족
- strictly convex : 등호 제거 (직선 구간 존재 X)
- 함수를 minimize 하는 point와 $\nabla f(x) = 0$인 point와 동치

Conditions
- first - order condition : 접선이 always 직선 아래 존재
- second - order condition : Hessian Matrix가 PSD
- 위의 두 정의는 서로 동치이다

5. Convex Optimization

Strong Duality
- $d^{\ast} = p^{\ast}$
- KKT conditions
KKT Conditions
- $x^{\ast}$ : Primal optimization solution
- $\lambda^{\ast}, \nu^{\ast}$ : Dual optimization solution
- 어떠한 optimization problem 경우에도 KKT가 필요조건
- convex optimization의 경우 KKT가 충분조건도 됨 : 필요충분조건
  - 어떤 $ x, \lambda, \nu$가 해당 조건을 만족한다면 Primal, Dual의 optimum이 된다

728x90