23-02 Example: linear regression

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

minβ12yXβ22, given yRn and XRn×p with columns X1,,Xp.

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

0=if(β)=XiT(Xβy)=XiT(Xiβi+Xiβiy)βi=XiT(yXiβi)XiTXi

Coordinate descent를 통해 βi for i=1,2,,p,1,2,를 반복하며 업데이트 한다.

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

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

[Fig1] GD vs AGD vs CD [3]

[Fig1] GD vs AGD vs CD [3]


위 결과에 의하면 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: ββ+tXT(yXβ), Xβ 연산에 의해 시간복잡도는 O(np) flops가 된다.