Chebyshev Acceleration

github.com/rkm0959/rkm0959_implements/tree/main/Chebyshev%20Acceleration

 

매우 최근에 올라온 Acceleration에 대한 Survey Paper arxiv.org/abs/2101.09545을 읽는다. 이 글은 2장을 정리한다.

일단은 관심가는 부분만 읽을 예정인데, 아마 3장을 제일 마지막에 읽을 것 같다. 사전지식이 부족한 경우 이 자료 참고.

Acceleration Survey Paper + OSPEP + Proximal Algorithms Survey Paper 이렇게 읽으면 지식이 좀 쌓이지 않을까 생각중이다..

모든 정리의 번호는 Survey Paper와 같은 번호를 사용한다. 단순히 정리 블로그니까 논문 표현을 그대로 가져다 쓰는 일도 많을 것이다.

 

이 글에서는 unconstrained quadratic minimization 문제, 즉 $f(x) = \frac{1}{2} x^T Hx - b^Tx$를 최소화하는 문제를 다룬다. 물론 $H$는 symmetric.

이 문제의 optimal point는 $x^{*} = H^{-1}b$임이 자명하다. 즉, 이 문제는 결국 linear system의 해를 빠르게 구하는 문제와 같다.

 

보통 이러한 minimization 문제를 만나면, 많은 사람들이 Gradient Descent를 생각할 것이다. 

즉, initial point $x_0$와 step-size $\gamma$를 잡고, $x_{i+1} = x_i - \gamma \nabla f(x_i)$를 반복하는 것이다.

이 식을 정리하면 $x_{i+1} = (I - \gamma H) x_i + \gamma b$를 얻고, $x^{*}$의 식을 이용하면 $$x_{k+1} - x^{*} = (I - \gamma H) (x_k - x^{*})$$ 를 얻는다. 이제 우리의 목표는 $I - \gamma H$의 matrix norm을 최소화하는 것이다. 우리는 일반적으로 2-norm, 즉 Spectral Norm을 생각한다.

 

이제 잠시 $H$로 가능한 행렬의 범위를 좁혀, 적당한 $\mu, L > 0$에 대해 $\mu I \le H \le L I$가 성립한다고 가정하자.

그러면 우리는 $\gamma$를 선택하는 과정에서 worst-case convergence를 최선으로 하기 위해서 $$\max_{\mu I \le H \le LI} ||I - \gamma H||_2$$ 를 최소화할 필요가 있다. 이 문제는 결국 $\text{max}(|1-\mu \gamma|, |L \gamma - 1|)$를 최소화하는 것이다. 그러니 $\displaystyle \gamma = \frac{2}{\mu + L}$를 잡을 수 있다.

 

특히 이 경우 $\displaystyle ||I - \gamma H||_2 \le \frac{L - \mu}{L + \mu} = \frac{\kappa - 1}{\kappa + 1}$이고 ($\kappa = L / \mu$는 condition number) $$||x_k - x^{*}||_2 \le \left( \frac{\kappa - 1}{\kappa + 1} \right)^{k} ||x_0 - x^{*}||_2$$ 를 얻는다. 이것이 Gradient Descent의 수렴 속도가 되겠다. 이를 더 빠르게 하는 것이 우리의 목표다.

 

이번에는 조금 더 넓은 class의 알고리즘을 생각해보자. $x_{k+1}$을 $x_k$에 $\nabla f(x_k)$의 상수배를 더한 것만 고려하지 말고, 아예 $$x_{k+1} \in x_0 + \text{span} \{ \nabla f(x_0), \cdots , \nabla f(x_k) \}$$ 를 고려하자. 이 경우, 단순한 수학적 귀납법으로 다음을 보일 수 있다.

 

Proposition 2.1. : 위와 같은 방식으로 $x_k$를 계산한 경우, 다항식 $P_k$가 있어 $\text{deg}(P_k) \le k$, $P_k(0) = 1$이고 $$x_k - x^{*} = P_k(H)(x_0 - x^{*})$$ 이제 우리는 앞선 사고방식을 그대로 따라가면 $$\displaystyle \max_{\mu I \le H \le LI} ||P_k(H)||_2$$ 를 최소화하고 상수항이 $1$인 $k$차 이하 다항식 $P_k$를 찾아야 한다. 그런데 $H$가 symmetric이므로, 이 문제는 사실 $$\max_{\mu \le \lambda \le L} |P_k(\lambda)|$$ 를 최소화하는 것과 같다. 이제 짬이 좀 찬 독자들은 Chebyshev라는 단어가 왜 나왔는지 알 것이다. 저런 문제에서 최적의 다항식이 Chebyshev Polynomial이기 때문이다. 이들은 $[-1, 1]$ 위에서 최적이기 때문에, $[\mu, L]$을 $[-1, 1]$로 shift 하는 처리 작업이 필요하다. 즉, $$t : x \rightarrow \frac{2x - (L + \mu)}{L - \mu}$$ 의 처리를 하자. 또한, $P_k(0)=1$이라는 조건이 있으니 이것도 처리해야 한다. 결과적으로 우리는 $$C_k^{[\mu, L]}(x) = \frac{T_k(t(x))}{T_k(t(0))}$$ 라는 다항식을 정의할 수 있다. 이제 목표는 $$x_k - x^{*} = C_k^{[\mu, L]}(H) (x_0 - x^{*})$$ 가 성립하도록 효율적인 iteration을 설계하는 것이다. 이를 위해서는 $C_k^{[\mu, L]}$에 대한 점화식이 필수적이다. 결과적으로, $$\delta_0 = -1, \quad \delta_k = \frac{L - \mu}{2(L + \mu) - \delta_{k-1}(L - \mu)}$$ $$C_0^{[\mu, L]}(x) = 1, \quad C_1^{[\mu, L]}(x) = 1 - \frac{2}{L + \mu}x, \quad C_k^{[\mu, L]}(x) = \frac{2\delta_k (L+\mu - 2x)}{L - \mu} C_{k-1}^{[\mu, L]}(x) + \left( 1 - \frac{2\delta_k (L+\mu)}{L - \mu} \right) C_{k-2}^{[\mu, L]}(x)$$ 가 성립함을 보일 수 있다. Chebyshev Polynomial의 점화식을 가지고 열심히 계산하면 될 것으로 예상한다.

이제 이를 $x_k - x^{*} = C_k^{[\mu, H]}(x_0 - x^{*})$에 집어넣고 $\nabla f(x_k) = Hx_k - b = H(x_k - x^{*})$를 이용하면, iteration $$x_k = \frac{2\delta_k}{L-\mu} ((L+\mu) x_{k-1} - 2 \nabla f(x_{k-1})) + \left( 1 - \frac{2\delta_k (L + \mu)}{L - \mu} \right) x_{k-2}$$ 를 얻는다. 이 iteration에 대해서 몇 가지 고찰을 해보자. 이 식은 $$x_k = x_{k-1} - \frac{4 \delta_k}{L - \mu} \nabla f(x_{k-1}) + \left( 1  - \frac{2\delta_k (L+\mu)}{L - \mu} \right)(x_{k-2} - x_{k-1})$$ 이라 쓸 수 있다. 결국 Gradient Descent Term (step size는 변화함) + Momentum Term (변화함) 으로 볼 수 있다.

특히, $\delta_k$의 극한을 취하면 $\displaystyle \frac{\sqrt{L}-\sqrt{\mu}}{\sqrt{L} + \sqrt{\mu}}$로 수렴함을 알 수 있으며, 이 값을 iteration에 그대로 대입하면 Heavy Ball Method를 얻는다고 한다.

 

이제 이 새로운 iteration의 수렴 속도를 알아보자. 결국 $\lambda \in [\mu, L]$에 대하여 $$|C_k^{[\mu, L]}(\lambda)| \le \frac{1}{|T_k(t(0))|}$$ 이 성립하고, 여기서 $\displaystyle \xi = \frac{\sqrt{\kappa}+ 1}{\sqrt{\kappa} - 1}$라 하면 위 식의 우변이 정확하게 $\displaystyle \frac{2}{\xi^k + \xi^{-k}}$와 같음을 알 수 있다. 그러니 이를 그대로 대입하여 $$||x_k - x^{*} ||_2 \le \frac{2}{\xi^k + \xi^{-k}} ||x_0 - x^{*}||_2$$ 를 얻는다. 이제 이를 기존의 Gradient Descent와 비교할 일만 남았다. 이를 위해서는 원하는 정확도를 위해서 iteration이 얼마나 필요한지 보면 된다.

 

Corollary 2.2. : 고정된 $\mu, L$에 대하여, $||x_k - x^{*}||_2 \le \epsilon$을 얻기 위하여 필요한 $k$의 값은

• 기존 Gradient Descent의 경우 $\displaystyle k \ge 2 \kappa  \log (||x_0-x^{*}||_2 / \epsilon)$
• 새로운 Chebyshev Method의 경우 $\displaystyle k \ge 2 \sqrt{\kappa} \log(2 ||x_0-x^{*}||_2 / \epsilon)$

그러니 Chebyshev Method의 강력함을 알 수 있다. 특히 $\kappa$가 큰 경우 더욱 강력한 힘을 발휘한다.