Elements of Numerical Optimization

많은 Statistical machine learning 방법론에서, 모델이 설정되고 평가기준이 선택되고 나면, 나머지 문제는 optimization로 생각할 수 있다.

이 포스트에선 optimization의 elements들에 대하여 살펴보자.

9.1. Unconstrained optimization

Rates of numerical convergence

일반적인 다항함수에서 처럼, 미분 몇 번 한다고 score function의 minima를 찾을 수 있다면 참 좋겠지만, 현실에서 그러한 일이 일어날 리 만무하다.

일반적으로, 딥러닝에서나 ML에서나 우리는 Score function의 개형을 잘 알 수 없기 때문에, 임의의 초기점부터 시작해 계속해서 score function의 값을 줄여가는 iterative 한 방법론들을 많이 사용한다.

이러한 상황에서, 이렇게 iterative 한 방법을 시도한다고 해서, 과연 최적점으로 수렴한다는 보장이 있을지, 그리고 수렴한다면 그 속도가 얼마인지는 민감한 문제가 아닐 수 없다.

• $x_k \to x^*$ linearly in case $||x_{k+1} - x^*|| \le c||x_k - x^*||$ for some 0 < c < 1
  
• $x_k \to x^*$ superlinearly in case $||x_{k+1} - x^*|| \le c_k||x_k - x^*||$ with $c_k = o(1)$
  
• $x_k \to x^*$ quadratically in case $||x_{k+1} - x^*|| \le c||x_k - x^*||^2$ for some c > 0
  

수렴속도는 linear < superlinear < quadratic 이다.

9.2 Algorithms for unconstrained optimization

• Gradient descent

  $x_{k+1} = x_k - \lambda \bigtriangledown f(x_k)$
  
  $\because f(x_k + tv) = f(x_k) + tv^T\bigtriangledown f(x_k) + \frac{1}{2}t^2v^T\bigtriangledown^2f(x_k + \alpha v)v$
  The rate of change of $f$ in the direction of v is $v^T\bigtriangledown f(x_k)$,
  
  $\min_{||v||=1} v^T\bigtriangledown f(x_k) = \frac{-||\bigtriangledown f||^2}{||\bigtriangledown f||}$ when $v = -\bigtriangledown f / |\bigtriangledown f|$

• Newton diretction : 2차항까지 근사한다

  $v_k = -(\bigtriangledown^2f(x_k))^{-1}\bigtriangledown f(x_k)$
  
  $\because f(x_k + v) \approx m_k(v) = f(x_k) + tv^T\bigtriangledown f(x_k) + \frac{1}{2}t^2v^T\bigtriangledown^2f(x_k)v$,
  $\frac{d}{dv}m_k(v) = 0$ implies $v_k = -(\bigtriangledown^2f(x_k))^{-1}\bigtriangledown f(x_k)$

두 방법론의 차이?

• Newton direction은 Hessian 행렬까지 사용하므로, 계산비용이 큰 대신 수렴속도가 훨씬 빠르다

• 일반 GD와 달리 Newton direction은 learning rate를 설정할 필요가 없다.
  
  
  

• Quasi-Newton Methods
  Newton Methods는 강력하지만, Hessian 행렬을 계산하는 것은 상당한 부담일 수 있다. Quasi-Newton은 헤시안을 계산하지 않고 iterative하게 근사하는 방법을 제시한다.
  기본적인 아이디어는 다음과 같음.

  $\bigtriangledown f(x_{k+1}) = \bigtriangledown f(x_{k}) + \bigtriangledown^2 f(x_{k+1})(x_{k+1} - x_k) + o(||x_{k+1} - x_k||)$
  $\therefore \bigtriangledown^2 f(x_{k+1})(x_{k+1} - x_k) \approx \bigtriangledown f(x_{k+1}) - \bigtriangledown f(x_{k})$
  의 공식을 이용한다.

• Conjugate gradient methods
  conjugate gradient methods에 기반한 방법도 요긴하게 쓸 수 있다.
  (공부중)

9.3 Constrained Optimization

다음과 같은 Constrained optimization 상황은 많은 상황에서 발생한다.

(Primal problem)
$min f(x)$ subject to
$g_i(x) \le 0, i = 1...m$
$h_i(x) = 0, i = 1,2,...m$

주어진 상황에 대한 Lagrangian은 다음과 같이 표현됨.

$L(x,\lambda,\mu) = f(x) + \sum_i \lambda_ig_i(x) + \sum_i \mu_ih_i(x)$

그리고 이에 대응되는 Dual function을 다음과 같이 정의한다

$l(\lambda, \mu) = \inf_{x \in D_F} L(x,\lambda,\mu)$
where $D_F$ is the intersection of domains of the objective functions and constraints

Dual이라는 단어를 한국말로는 쌍대라고 하는데, 단순히 이해하면 어떠한 문제(primal)을 풀기위해 이와 대응되는 다른 문제를 상정하여 풀이한다고 생각하면 된다.

우리는 이 때, F를 feasible set, 즉 primal problem에서 constraint를 만족하는 x의 공간이라고 둔다.

그렇다면, F위에서 다음이 성립한다.
$L(x,\lambda,\mu) = f(x) + \sum_{i=1}^m\lambda_ig_i(x) \le f(x)$

따라서, $p^\star$ : optimal value of primal function,
$d^\star$ : optimal value of dual function = $sup_{\lambda \ge 0, \mu} \;l(\lambda, \mu)$
이라고 할 때,

$d^\star \le p^\star$이 성립한다.
이를 Weak duality 라고 한다.

linear constraints의 경우에, dual problem은 objective functions로 표현이 가능하다. 다음 상황을 보자

primal problem :
Minimize $f(x)$ subject to
$Ax \le b, Cx = d$

Dual problem :
$l(\lambda, \mu) = inf_x(f(x) + \lambda^T(Ax-b) + \mu^T(Cx-d))$
$=inf_x(f(x)+(A^T\lambda + C^T\mu)x - b^T\lambda - d^T\mu))$
$=-sup_x((-A^T\lambda + C^T\mu)x - f(x)) -b^T\lambda -d^T\mu$
$=-f^*(-A^T\lambda + C^T\mu) -b^T\lambda -d^T\mu$

9.4 Strong duality

책에서는 다소 복잡하게 설명했지만, 나는 결론적으로

strong duality holds $\iff p^\star = d^\star$ 라고 이해했다.

Strong duality가 중요한 이유는, 만약 우리가 primal 문제를 풀기 힘들어서 dual problem을 푸는 상황을 생각할 때, dual problem의 해 $\lambda^*, \mu^*$를 구하면, dual function을 구할 때 $x^*$를 $\lambda, \mu$로 표현이 가능했으므로 이를 통해 구한 x는 primal problem의 solution $x^*$ 와 동일해지므로, dual problem을 사용하여 primal problem의 정확한 해를 구할 수 있게된다.

9.5 KKT conditions. (Karush-Kuhn-Tucker)

이렇게 strong duality가 중요하다는 것을 알았는데, 그렇다면 strong duality가 성립함을 알 수 있는 조건들이 무엇이 있을까?

Suppose the strong duality holds:
$f(x^\star) = l(\lambda^\star, \mu^\star)$
$=inf_{x \in domf}(f(x) + \lambda^{\star T}g(x) + \mu^{\star T}h(x)$
$\le f(x^\star) + \lambda^{\star T}g(x^\star) + \mu^{\star T}h(x^\star) \le f(x^\star)$ which implies

$\sum_{i=1}^m\lambda_i^\star g_i(x^\star) = 0$, 하지만 $lambda \ge 0, g(x^\star) \le 0$이므로,
$\lambda_i^\star g_i(x^\star) = 0$, for all $i$

이 조건과 $x^\star$이 Lagrangian의 최소점, 그리고 constraint의 만족여부를 통틀어서 우리는 KKT conditions라고 부른다.

- KKT Conditions

• $\bigtriangledown L(x^\star, \lambda^\star, \mu^\star) = 0$
• $g_i(x^\star) \le 0$
• $h_j(x^\star) = 0$
• $\lambda_i^\star \ge 0$
• $\lambda_i^\star g_i(x^\star) = 0$

KKT condition이 만족되는 상황들:

• f is convex, differentiable, each g is convex and differentiable and each h is affine.