7. Continuous Optimization

7. Continuous Optimization

[출처] https://neos-guide.org/content/optimization-taxonomy

Continuous Optimization은 이번 장에서 2개로 제약조건이 없는 경우와 있는 경우로 나누어 생각한다. 우리의 목적함수는 미분가능하다고 가정하기 때문에, 최적값을 찾는데 도움을 주는 gradient에 접근할 수 있다. convention으로 ML에서의 목적함수는 최소화하는 것이다. 제약이 없는 최적화에서는 여기까지가 필요한 개념은 여기까지이지만, 제약조건이 있는 경우에는 다른 개념을 도입한다. 또한 제약잇는 최적화의 특별한 경우인 컨벡스 최적화를 배운다. 컨벡스 함수에 대해서는 모든 극소값(local minima)들은 전역 최솟값(global minimum)이다.

cf) local minimum / maximum (value)

A, D, F, G, K 도 극값이다.

https://ko.wikipedia.org/wiki/극값

cf) Stationary point

f’(x) = 0 인 경우 stationary point(정류/정상점): f’(x) = 0

• 극대: f’’(x) < 0 → concave (concave down)

• 극소: f’’(x) > 0 → convex (concave up)

• 변곡(inflection point): f’’(x)=0 or undefined

http://230nsc1.phy-astr.gsu.edu/hbase/Math/maxmin.html

cf) Critical Point(임계): f’(x) = 0 or Undefined

https://www.mrfelling.com/docs/hfb/studentnotes-blank-hfb-unit12.pdf

Optimization Using Gradient Descent

---

미분 가능하고, closed-form으로 극솟값을 구할 수 없는 함수$f: \mathbb{R}^{D} \to \mathbb{R}$ 의 함수의 최솟값을 찾기 위해, 1차 최적화 (fisrt-order optimizaiton)알고리즘인 Gradient Descent를 적용할 수 있다.

이는 xi에서 negative gradient 방향으로 $-((\nabla{f})(x_{i}))^{T}$의 방향으로 이동하면 f(xi)가 가장 빨리 감소한다는 사실을 이용한다. 움직이는 크기 Step size를 $\gamma_i$라고 하면, Gradient Descent의 알고리즘을 아래와 같이 표현할 수 있다.

• step-size

  step-size, lr의 선택은 경사하강법에서 중요함. → 다양한 learning rate scheduler

• 예시. 7.1

  

  다른 방법에 비해 비교적 점근 수렴 속도는 낮음. 다음과 같이 한쪽은 길고, 한쪽은 깊은 형태의 함수(poorly conditioned convex problem)에서는 아래와 같이 지그재그로 움직여 경사하강법은 느릴 수 있음.

  

• 예시 7.1

  선형회귀 문제(선형연립방정식)문제를 Gradient Descent로 풀수 있지만, 이는 Analytic solution이 존재한다.

  

  이 때, 경사하강법의 수렴속도는 condition number에 의존한다. condition number는 A행렬의 최대 특이값 / 최소 특이값(singular value) 이며, 가장 구부러진 방향과 덜 구부러진 방향의 비율을 측정한다.

  보통 Ax = b를 바로 풀기보다는 보다 계산하기 쉬운 형태로 precondition의 역행렬 $\boldsymbol{P}^{-1}$을 앞에 붙여, $\boldsymbol{{P}^{-1}(Ax-b)=0}$ 계산한다.

• Gradient Descent with momentum

  

  $\alpha \in [0,1]$

  이전 반복에서 무슨 일이 일어났는지에 대한 추가항 $\alpha \Delta{x_{i}}$을 도입한다. 이동평균을 이용한 방법으로, 진동을 안화하고 gradient update를 smooth하게 한다. SGD와 같이 gradient를 근사할 때는 모멘텀항이 잡음이 있는 gradient의 추정을 평균화하기 대문에 유용하다.

• Stochastic Gradient Descent

  SGD는 Gradient Descent의 확률적 근사(Stochastic Approximation)이다. 확률적이라는 것은 gradient를 정확하게 알지 못하고 대신 잡음이 많은 많은 근사치만 알고 있다는 것을 의미한다. Gradinet의 근사치의 확률분포를 제한함으로써 이론적으로, SGD가 수렴할 것을 보장한다.

  머신러닝에서, 각 데이터 포인트 마다의 손실을 아래 7.13 처럼 표현하고, Negative Log-Likeligood를 7.14처럼 표현할 수 있다.

  

  일반적인 경사하강법(배치 경사하강법)은 전체 데이터 셋에 대하여 아래와 같이 업데이트 한다.

  

  하지만, 훈련 셋이 크거나 공식이 간단하지 않은 경우, gradient의 합계를 평가하는 것은 비용이 큰 계산이다.

  $\Sigma_{n=1}^{N}(\nabla L_{n}(\boldsymbol{\theta_{i}}))$의 항에서, N개의 데이터 포인트의 gradient에 대해 랜덤하게 부분집합을 선택해 mini-batch gradient descent를 수행해 계산량을 줄일 수 있다.

  $\Sigma_{n=1}^{N}(\nabla L_{n}(\boldsymbol{\theta_{i}}))$항은 true gradient의 기댓값의 불편추정량이기 때문에 이것이 가능하며 다른 불편추정량이어도 된다. (unbiased empirical estimate of the expected value)

  배치 크기에 대해서는 학습속도와 gradient 근사 성능에 대한 trade-off가 있을 것이다.

Constrained Optimization and Lagrange Multipliers

---

• 제약조건이 있는 최적화에 대한 시각화:

  제약조건이 없는 경우 빨간 점이 f(x)의 최솟값이고, 제약조건이 x1, x2의 절댓값이 1 이하인 경우에는 빨간 별이 f(x)의 최솟값이다.

  

• 제약조건이 없는 형태로의 변경 예시

  

  위처럼 목적함수와 제약 조건이 있는 경우, f와 gi함수들이 convex하지 않을 수 있다는 것을 확인하고 다음 절에서 convex optimization에 대해 확인해보자.

  실용적이지는 않지만, 위 제약조건과 목적함수를 제약조건이 없는 형태로 변경을 아래와 같이 할 수 있다. 무한 계단함수(infinite step function)이자 지시함수(indicator function)인 1(z)를 사용한다.

  

  하지만, 이런 무한 계단함수는 최적화하기 어려워, 계단함수를 라그랑주 승수(Lagrange multiplier)라는 선형함수로 대체한다.

• Primal Problem & (Lagrangian) Dual Problem

  

  위와 같은 제약조건이 있는 문제를 Primal problem이라 하며, 이를 풀기 위해 라그랑지안 승수와 제약조건을 함께 표현해 라그랑지 함수를 아래와 같이 쓸 수 있다.

  (cf. Primal Problem은 보통 등식 제약조건을 포함해 뮤와 람다 2개의 lagrange multiplier/dual variable) 를 도입하며, 부등식 제약 조건의 lagrange multiplier는 0이상의 양의 실수(벡터)로 본다. MML에서는 부등식 제약조건만 고려)

  

  일반적으로 최적화에서의 Duality란 primal variable x를 다른 최적화 문제 dual variable $\lambda$로 바꾸는 것이다. 여기서는 Lagrangian Duality를 소개하고 이후에 7.3.3에서는 Legendre-Fenchel duality를 배운다.

  • Dual problem으로 변환해서 푸는 것이란 (혁펜하임 유튜브)

    ref. https://www.youtube.com/watch?v=rOTtOQ8vz8o&list=PL_iJu012NOxeMJ5TPPW1JZKec7rhjKXUy&index=15

    Inequality 제약이 있는 최적화 문제를 Duality problem으로 풀기

    equality 제약이 있을 때, 크게 필요조건으로 푸는 방법과 duality problem으로 푸는 방법이 있었다. (cf. 필요조건으로 푸는 방법은 제약조건이 없는 최적화 문제에서 f’(x)=0으로 극소를 푸는 방법을 말함)

    KKT조건(필요조건)으로 푸는 방법은 라그랑지안 함수의 미분해서 0이 x, 람다, 뮤을 구하고 feasibility를 확인하고, 어떤 x가 가장 작은지 확인해야 하는 번거로움이 있다.

    알고리즘으로 접근하는 Interior point method라는 방법이 편하긴 하다.

    • Primal Problem & Primal Optimal

      아래와 같은 문제를 Primal Problem이라 하며, 이 때의 optimal solution x*를 primal optimal (point)이라 한다.

      

    • Duality 이용하는 방법

      

      $\mu \ge 0$, 에서

      $\nabla_{x}L = 0$을 이용해 $arg\min_{x} L$을 찾은 Lagrangian Dual Function q(x)로

      $\nabla_{\mu, \lambda} q(\mu, \lambda) = 0$을 통해 $arg\max_{\mu,\lambda}$ q를 찾는 방법이 duality를 활용해 푸는 방법이다.

      • Lagrangian Dual Function, $q(\mu, \lambda)$

        $\begin{matrix} q(\mu, \lambda) &\triangleq& \min_{x} f(x) + \lambda h(x) + \mu g(x) \\&\le& f(x^{*}) + \lambda h(x^{*}) + \mu g(x^{*})\\&\le& f(x^{*}) \end{matrix}$

        라그랑지안 듀얼 함수는 위와 같이 정의하며, 아래 2가지 특징이 있다.

        1. $f(x^{*}) + \lambda h(x^{*}) + \mu g(x^{*})$보다 작은 이유는 primal optimal은 gi(x)≤ 0, h(x)=0이라는 제약조건 아래에 구했기 때문에, 제약조건을 고려하지 않고 라그랑지안 함수를 최적화 한것은 더 작다.
        2. $\lambda h(x^{*}) + \mu g(x^{*})$에서 제약조건에 의해, h(x*)=0이고, mu ≥ 0 g(x*)는 음수이기 때문에 $q(\mu, \lambda)$는 f(x*)보다 작다.
      • Primal Optimal Value, f*

        $f(x^{*})$, f에 primal optimal (point)의 결과. f*로도 표현

      • Dual Optimal Value, q*

        라그랑지안 듀얼함수의 최댓값 $\max_{\mu \ge 0\ , \lambda } q(\mu^{*}, \lambda^{*} )$. q*로도 표현

        그랑지안의 b번 특성인 모든 $\mu \ge 0\ , \lambda$ 에 대해 $q(\mu, \lambda) \le f(x^{*})$가 만족하니 아래와 같이 생각할 수 있다.

        $q(\mu, \lambda) \le \max_{\mu \ge 0\ , \lambda } q(\mu^{*}, \lambda^{*} ) \le f(x^{*})$

        

      • Lagrangian Dual Problem (Dual Problem)

        $\max_{\mu \ge 0\ , \lambda } q(\mu, \lambda) \\ \ \ s.t \ \ \ \ \mu \ge 0$

      • Weak Duality: q* ≤ f*

        Strong Duality: q* = f*

        Duality gap: f* - q*

      → 결론적으로 Dual Problem으로 푸는 것이 primal problem을 푸는 것보다 간단하므로

      $q(\mu, \lambda) = f(x)$를 만족하는 $\mu^{*}, \lambda^{*}, x^{*}$를 찾는 다면 그것이 optimal solution이 된다.

      $q(\mu, \lambda) = f(x)$를 만족하는 해가 없더라도, Duality Gap이 가장 작은 best lower bound이다.

  

  라그랑지안 함수가 위의 아래부분과 같을 때, dual 문제로 바꾼다는 것은 제약조건 없이 x에 대하여 최적화한 라그랑지안 함수 D를 람다에 대하여 최대화 하는 문제로 바꾸는 것이다. 라그랑지안 함수의 f와 g가 미분가능하다면, L’(x)=0을 이용해 라그랑지안 dual 함수를 찾는다.

  • Primal 문제에서의 전제
    1. Minimax Inequality

       

    2. Weak Duality

       Weal Duality는 duality value ≤ optimal duality value ≤ optimal primal value ≤ primal value에서 optimal duality value ≤ optimal primal value를 증명할 때 사용된다.

       무한계단함수를 지시함수로 놓은 J(x)와 라그랑지안 함수를 비교해보자.

       

       따라서, 라그랑지 승수 ≥ 0 인 라그랑지 함수는 J(x)의 하한(lower bound)임을 알 수 있으며 J(x)를 푼 뒤, x에 대해 최소화 하는 것과 Duality 문제로 바꿔 푼다는 것은 아래와 같다.

       

       

  • Equality Constraint가 있는 경우, 등식제약조건을 아래와 같이 생각할 수 있다.

    

Convex Optimization

---

global optimality를 보장하는 방법을 알아보자.

• Convex Optimization Problem

  

  함수 f와 g가 convex 함수이고, h(x)=0이 convex set인 경우 convex optimization 문제라고 한다. (h는 affine 함수인 경우)

  컨벡스 최적화 문제에서는 optimal dual value가 optimal primal value인 strong duality를 갖는다.

  • convex set

    convex set은 convex set 내의 어떤 두 원소를 선으로 이었을 때의 직선이 convex 집합에 있는 경우를 convex set이라고 한다.

    

    

  • convex function

    convex 함수란 convex 함수 위에 어떤 두 점을 이었을 때의 직선이 함수 위에 있는 경우 convex 함수라고 한다. concave는 직선이 함수의 아래에 있는 경우이다. 7.30은 옌센의 부등식이라고도 한다.

    

    

    함수의 위쪽에 해당하는 영역의 집합을 Epigraph라 하는데, 어떤 함수의 epigraph가 convex집합이면, 그 함수는 convex function이고, 역도 성립한다. (cf. https://wikidocs.net/17206)

    • 미분을 통한 convex확인

      함수 f가 미분이 가능하다면, f가 convex 함수이기 위한 필요충분조건은 모든 x, y에 대해 아래와 같이 명시 할 수 있다.

      

      함수 f가 2번 미분가능하다면, f가 convex 함수이기 위한 필요충분조건은 f의 헤시안 행렬 $\nabla^{2}_{x} f(x)$가 PSD(positive-semidefinite) 행렬인 경우 이다.

      ex) negative enropy가 [2,4]에서 convex인지 확인

      $f(x) = x\log_{2}x$

      

      

      f(4) ≥ f(2) + f’(2)(2)

    • Non-negative Weighted sum과 convex

      어떤 집합이나 함수가 convex인지 practical하게 확인하기 위해 convexity를 유지하는 연산인지 확인한다. 세부사항은 다르지만, 벡터공간의 closure 아이디어와 유사하다.

      

• Linear Programming (선형계획법)

  f(x)와 제약조건이 모두 선형인 경우를 보면, 아래와 같은 문제를 선형계획법이라 한다.

  

  이 때의 라그랑지안 함수는 아래와 같으며, 라그랑지안 승수는 $0\le \boldsymbol\lambda \in \mathbb{R}^{m}$ 이다.

  

  이를 아래와 같이 x에 대해 묶고, x로의 미분 L’(x,람다)=0이라 놓으면 아래와 같다.

  

  x앞의 계수가 0일 때, 최소이므로, 듀얼함수인 min L(x,mu)는 라그랑지안 함수의 뒷 부분만 남고, 변환한 Dual problem은 아래와 같다.

  

  Primal problem은 d개의 변수와 m개의 제약조건에 대한 최적화이고, Dual program m개의 변수에 대한 최적화 이므로 어떤 것이 더 큰지에 따라 어떤 문제를 풀지 결정할 수 있다.

  ex. 7.5

  

• Quadratic Programming (이차계획법)
  • Quadratic program

    

    $\boldsymbol{Q}\in \mathbb{R}^{d \times d}$이며, symmetric positive definite하기 때문에, 목적함수는 convex이다.

    d개의 변수와, m개의 선형 제약식이 있다.

    이 때의 라그랑지안 함수는 아래와 같으며, x로의 미분 L’(x, mu)=0은 그 아래와 같다.

    

    Q가 가역행렬이라면, 라그랑지안의 최소가 되는 x, Dual function, Dual problem을 아래와 같이 나타낼 수 있다.

    

    SVM을 학습할 이차계획법을 사용한다.

• Legendre-Fenchel Transform and Convex Conjugate

  Convex set은 supporting hyperplanes에 의해 표현할 수 있다는 유용한 사실이 있다. support hyperplane은 convex set을 지나고, 한 쪽에만(하나의 half space에만) convex set이 있는 hyperplane이다.

  support hyperplane은 convex set의 한점의 접선(tangent line)일 수 있으며 한점의 gradient일 수 있고 이것으로 convex set을 표현할 수 있으며, 르장드르 변환(Legendre transform)은 이러한 컨셉을 구체화한 것이다.

  cf. half space: https://convex-optimization-for-all.github.io/contents/chapter02/2021/02/11/02_02_01_Convex_sets_examples/

  ref. https://en.wikipedia.org/wiki/Supporting_hyperplane

  

  비직관적이지만, 가장 일반적인 정의로 시작하고 관련된 특별한 경우를 통해 직관을 얻어보자.

  르장드르 펜첼 변환(Legendre-Fenchel tranformation)은 convex이며, 미분가능한 함수 f(x)에서 $s(x) = \nabla_{x}f(x)$에 대한 함수로 변환하는 것이다. 함수 f에 대한 변환이 변수 x나 x점에서 계산된(evaluated) 것이 아닌 것에 주의하자. 르장드르 펜첼 변환은 convex conjugate로도 알려져 있으며, Duality와도 관련이 깊다.

  • convex conjugate

    

    cf. sup는 상한으로 (0, 1)의 상한은 1이지만 최댓값은 정해지지 않는다.

    이 때, 함수 f는 convex이거나 미분이 불가능해도 된다. 모든 노름에 대해 가능하지면, 유한차원에서의 dot product를 기준으로 설명한다.

    

    $\underset{x_0}{\inf} (-sx_{0} +f(x_{0}))$

    

    f(x) = x^2의 예시는 아주 특별히 좋은 케이스였다. 상한이 필요 없고, 함수와 legendre transform은 일대일 대응한다.

    미분가능한 convex 함수에 대해 $x_{0}$에서의 접선(tangent)는 $f(x_{0})$을 지나기 때문에 아래 와같이 표현할 수 있다.

    $f(x_{0})= sx_{0} +c$

    우리는 컨벡스함수를 gradient $\nabla_{x}f(x)$로 표현하고 싶으며 여기서 $s = \nabla_{x}f(x)$ 이다. 위 식을 다시 -c로 표현하면 아래와 같다

    $-c = sx_{0} - f(x_{0})$

    이 때, $-c$ 는 $x_{0}$와 s에 따라 변화하며, 우리는 이를 s에 관한 함수로 볼 수있다.

    $f^{*}(s) := sx_{0}- f(x_{0})$

    위 식과 convex conjugate(7.4)의 정의를 비교하면, 상한에 대한 표현이 필요없는 특별한 경우임을 알 수 있다.

    convex conjugate는 다음과 같은 2가지 특징이 있다. convex function의 legendre transform을 2번 하면 다시 원래 함수로 돌아온다. f(x)의 기울기는 s이며, $f^{*}(x)$의 기울기는 x이다. 아래 예시들은 convex conjugate를 ML에서 어떻게 사용하는지 보여준다.

  • Example 7.7

    아래 와 같은 이차 함수를 생각해보자.

    

    K가 positive definite matrix라면, primal variable이 $\boldsymbol{y}$이고, dual variable을 $\boldsymbol{\alpha}$로 놓는다. 정의7.4 에 따른 위 이차함수의 convex conjugate는 아래와 같다.

    

    convex conjugate이 미분가능하기 때문에, 미분을 이용해 최대값을 찾을 수 있다.

    

    gradient가 0인 지점에서, $\boldsymbol{y} = {{1}\over{\lambda}}\boldsymbol{K \alpha}$ 를 얻을 수 있고 이를 7.60식에 대입하면 아래처럼 convex conjugate를 표현할 수 있다.

    

  • Example 7.8

    머신러닝에서 종종 함수의 덧셈을 사용한다. 예를 들어, 학습데이터의 목적함수는 각 샘플의 loss의 합으로 표현한다. 여기서는 loss의 합계의 convex conjugate를 살펴보자.

    $\mathcal{L}(t) = \Sigma_{i=1}^{n} l_{i}(t_{i})$일 때의 convex conjugate는 아래와 같다.

    

• Legendre-Frenchel transform & Dual problem

  convex optimization 문제는 primal 문제의 해와 dual 문제의 해가 같은 strong duality를 갖는다. Legendre-Frenchel 변환은 dual 문제를 도출하는데 사용할 수 있다. 또한, convex 함수인 경우, 상한(supremum)은 유일(unique)하다.

  Convex 최적화로 표현될 수 있는 ML문제에서 convex conjugate는 유용한 것으로 밝혀졌다. 특히, 각 샘플마다 적용하는 convex 손실에서, conjugate loss는 dual 문제로 쉽게 바꿀 수 있다.

  • Example 7.9

    $f(\boldsymbol{y})$와 $g(\boldsymbol{y})$는 convex함수이고, $\boldsymbol{A}$는 $\boldsymbol{Ax=y}$를 만족하는 알맞는 차원의 행렬이다.

    

    위의 문제에서, 제약조건 $\boldsymbol{Ax=y}$에 대해 라그랑지안 승수 $\boldsymbol{u}$를 도입하면 아래와 같다.

    

    $f(\boldsymbol{y})$와 $g(\boldsymbol{y})$는 convex함수이기 때문에 min과 max를 바꿀 수 있다. dot product를 분배하고 x와 y에 대해 묶어보면 아래와 같다.

    

    convex conjugate의 정의와 dot product는 symmetric ( <a,b> = <b,a>)하기 때문에 아래와 같으며, 7.68로 convex conjugate을 표현할 수 있다.

    

Further Reading

---

Gradient Descent 방법은 2가지 과제가 있다.

1. 1차 미분 알고리즘(fisrt-order algorithm)이기 때문에, 목적함수 표면의 곡률(curvature of the surface) 정보를 이용하지 않음

   momentum 방법이 이를 가속하기 위한 일반적인 방법일 수 있다. (Nesterov, 2018).

   Conjugate Gradient방법은 이전 방향을 고려해 이러한 문제를 방지하고자 했다. (Shewchuk, 1994)

   뉴턴법(Newton’s method)와 같은 2차 미분 방법은 곡률에 대한 정보를 제공하기 위해 헤시안을 사용한다. step size 선택이나 모멘텀과 같은 아이디어는 목적함수의 곡률을 고려해 이루어진다.

   L-BFGS와 같은 Quasi Newton 방법은 헤시안을 근사를 통해 헤시안의 계산량을 줄이는 방법이다.(Nocedal and Wright, 2006).

   하강하는 방향을 계산하기 위해 다른 metric을 사용하는 mirror descent나 natural gradient와 같은 방법도 존재한다. (Beck and Teboulle, 2003), (Toussaint, 2012).

2. 미분 가능하지 않은 함수를 다루는 것

   경사하강법은 함수에 뽀족한(kink) 지점들이 있다면, 잘 정의 되지 않는다. 이러한 경우에는 subgradient method를 사용할 수 있다. (Shor, 1985)

   

   ref) https://math.mit.edu/~djk/calculus_beginners/chapter09/section03.html

   미분이 불가능한 함수에 대한 최적화 알고리즘은 Bertsekas (1999)을 참고해라.

   이외에 Luenberger (1969) and Bonnans et al. (2006). Bubeck (2015).를 추천한다.