23-02 Example: linear regression

Linear regression 문제를 다음과 같이 정의해보겠다.

$\underset{\beta }{min}\frac{1}{2}\Vert y-X\beta {\Vert }_2^2,$ $\text{given }y\in {\mathbb{R}}^n\text{ and }X\in {\mathbb{R}}^{n\times p}\text{ with columns }{X}_1,\dots ,X_p.$

${\beta }_j,j\ne i$가 고정된 값일때, 주어진 목적함수를 최소화시키는 ${\beta }_i$를 구해보자. ($-i$는 $i$를 제외한 나머지 항을 의미한다. - $X$의 경우 $i$번째 column을 제외한 나머지 column.)

Coordinate descent를 통해 ${\beta }_i$ for $i=1,2,\dots ,p,1,2,\dots$를 반복하며 업데이트 한다.

실험: 수렴속도 비교 - GD vs AGD vs CD

아래 그래프는 $n=100,p=20$인 linear regression 문제에 대해 coordinate descent, gradient descent, accelerated gradient descent의 수렴속도를 비교하여 보여준다. (가로축의 k는 한 step (GD, AGD) 또는 한 cycle (CD)을 나타낸다.)

위 결과에 의하면 coordinate descent는 first-order method의 optimal인 AGD보다도 월등히 좋은 수렴속도를 보인다. 어째서 이런 현상이 발생할 수 있는 것일까? 결론부터 말하자면, coordinate descent는 first-order method보다 더 많은 정보를 활용하므로 AGD를 훌쩍 상회하는 성능을 내는 것이 가능하다. Coordinate descent는 한 cycle 내에서 각 step마다 이전 step에서 갱신된 최신 정보를 이용하기 때문이다. (즉, CD는 first-order method가 아니다.)

Q. 그렇다면 위 실험에서 CD의 한 cycle을 GD의 한 step과 비교한 것은 공정한 것일까?

A. 그렇다. 앞서 소개한 CD의 업데이트 식을 한 step의 시간복잡도가 $O(n)$인 형태로 변형시킬 수 있다. 그렇다면 CD에 대한 한 cycle의 시간복잡도는 $O(np)$가 되며 GD의 한 step과 같은 시간복잡도를 가지게 된다.

• Gradient descent update: $\beta \leftarrow \beta +t{X}^T(y-X\beta )$, $X\beta$ 연산에 의해 시간복잡도는 $O(np)$ flops가 된다.