12. Coordinate descent와 conjugate gradient — 좌표와 켤레방향

// CORE 6/7 — coordinate descent, conjugate gradient, preconditioning

모든 알고리즘이 전체 gradient나 Hessian을 한 번에 쓰지는 않습니다. Coordinate descent는 한 좌표씩 움직이고, conjugate gradient는 선형 시스템을 특별한 방향들로 빠르게 풉니다.

Coordinate Descent

Coordinate descent는 한 번에 하나의 좌표 또는 coordinate block만 최적화합니다.

$$x_i\leftarrow \arg\min_z f(x_1,\dots,x_{i-1},z,x_{i+1},\dots,x_n).$$

좌표별 subproblem이 싸게 풀리면 매우 효율적입니다. Lasso, matrix factorization, 일부 대규모 ML 문제에서 유용합니다.

좌표 선택 방식

방식	설명
cyclic	정해진 순서대로 좌표를 돈다
randomized	무작위 좌표를 선택한다
greedy	가장 많이 줄일 것 같은 좌표를 고른다
block	좌표 묶음을 함께 업데이트한다

좌표축이 문제 구조와 잘 맞으면 빠르지만, 변수들이 강하게 coupled되어 있으면 느려질 수 있습니다.

Conjugate Gradient

Conjugate gradient는 symmetric positive definite 선형 시스템을 푸는 iterative method입니다.

$$Ax=b.$$

동시에 다음 quadratic function을 최소화하는 문제로 볼 수 있습니다.

$$\min_x \frac{1}{2}x^\top Ax-b^\top x.$$

gradient는 $Ax-b$이고, 해에서는 gradient가 0입니다.

Conjugate direction

CG는 단순히 gradient 방향으로만 가지 않습니다. 서로 $A$-conjugate인 방향을 만듭니다.

$$p_i^\top A p_j=0\quad (i\ne j).$$

이 덕분에 한 방향에서 이미 최적화한 결과를 다음 방향이 망가뜨리지 않습니다. 정확한 산술에서는 $n$차원 문제를 최대 $n$번 안에 풉니다. 실제 floating-point에서는 오차 때문에 preconditioning이 중요합니다.

Preconditioning

preconditioning은 풀기 어려운 시스템을 더 잘 conditioned된 시스템으로 바꾸는 일입니다.

원래 문제:

$$Ax=b.$$

preconditioner $M$을 사용하면 대략 다음 형태를 풉니다.

$$M^{-1}Ax=M^{-1}b.$$

목표는 $M^{-1}A$의 condition number를 줄이는 것입니다. 좋은 preconditioner는 두 조건을 만족해야 합니다.

1. $A$를 잘 근사한다.
2. $Mz=r$을 푸는 비용이 싸다.

언제 쓰나

방법	잘 맞는 경우
coordinate descent	좌표별 최적화가 싸고 구조가 분리됨
conjugate gradient	큰 SPD 선형 시스템, Hessian-vector product 가능
preconditioned CG	condition number가 커서 CG가 느림

Newton-CG는 Newton step을 정확히 풀지 않고 CG로 근사해 대규모 문제에서 비용을 줄입니다.

다음: Expensive optimization