23-02 Example: linear regression
Linear regression 문제를 다음과 같이 정의해보겠다.
Coordinate descent를 통해
실험: 수렴속도 비교 - GD vs AGD vs 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의 시간복잡도가
- Gradient descent update:
, 연산에 의해 시간복잡도는 flops가 된다.