Nesterov's Estimate Sequence

빠르게 Nesterov's Estimate Sequence를 정리한다. 출처는 "Introductory Lectures on Convex Optimization"

 

정의 : $\{\phi_k(x)\}$와 $\{\lambda_k\}$, $\lambda_k \ge 0$이 함수 $f(x)$의 estimate sequence라는 것은, $\lambda_k \rightarrow 0$이고 임의의 $x \in \mathbb{R}^n$과 $k \ge 0$에 대하여 $$\phi_k(x) \le (1-\lambda_k) f(x) + \lambda_k \phi_0(x)$$ 라는 것이다. 이 경우, 만약 적당한 수열 $\{x_k\}$가 있어 $$f(x_k) \le \phi_k^{*} \equiv \min_{x \in \mathbb{R}^n} \phi_k(x)$$ 가 성립한다면, $$f(x_k) \le \phi_k(x_{*}) \le (1-\lambda_k) f_{*} + \lambda_k \phi_0(x_{*})$$ 가 되어 이를 정리하면 결과적으로 $$f(x_k) - f_{*} \le \lambda_k (\phi_0(x_{*}) - f_{*})$$ 를 얻는다. 그러니 $x_k$를 잘 잡고, $\lambda_k$가 빠르게 $0$으로 수렴하기만 하면 된다.

 

이제 estimate sequence를 하나 만들어보자. $f \in \mathcal{F}_{\mu, L}$이라 가정한다. 즉, $f$는 $\mu$-strongly convex, $L$-smooth function.

$\phi_0$를 임의의 함수, $\{y_k\}$를 임의의 $\mathbb{R}^n$ 위 수열, $\{\alpha_k\}$를 $\alpha_k \in (0, 1)$과 $\sum_{k} \alpha_k \rightarrow \infty$를 만족하는 수열이라 하자. $\lambda_0 = 1$이라 하자.

 

이제 $\{\phi_k\}$와 $\{\lambda_k\}$를 다음과 같이 재귀적으로 정의한다. $$\begin{equation*} \begin{aligned} \lambda_{k+1} &= (1 - \alpha_k) \lambda_k \\ \phi_{k+1}(x) & = (1-\alpha_k)\phi_k(x) + \alpha_k(f(y_k) + \langle \nabla f(y_k), x - y_k \rangle + \frac{\mu}{2} ||x-y_k||^2) \end{aligned} \end{equation*}$$

이는 estimate sequence가 된다. 증명은 $\phi_{k+1}(x) \le (1-\alpha_k) \phi_k(x) + \alpha_k f(x)$임을 활용하여 귀납법. 특히, $\sum_k \alpha_k \rightarrow \infty$ 조건에서 $\lambda_k \rightarrow 0$이 나온다. 이렇게 되면 estimate sequence의 큰 family를 하나 얻었으니, 여기서 입맛에 맞게 $\lambda_k$가 빠르게 감소하도록 $\{\alpha_k\}$와 $\{y_k\}$를 잘 잡아주면 되겠다.

 

$\phi_0$도 잡아줘야 하는데, 뒤에 계속해서 quadratic function과 섞어먹고 있으니, $\phi_0$도 quadratic하게 잡자.

$\phi_0 = \phi_0^{*} + \frac{\gamma_0}{2} ||x-v_0||^2$이라고 정의하면, $\phi_k$가 전부 quadratic function이 된다. 귀찮은 계산을 하면, $$\begin{equation*} \begin{aligned} \gamma_{k+1} &= (1-\alpha_k) \gamma_k + \alpha_k \mu \\ v_{k+1} &= \frac{1}{\gamma_{k+1}} \left( (1-\alpha_k) \gamma_k v_k + \alpha_k \mu y_k - \alpha_k \nabla f(y_k) \right) \\ \phi_{k+1}^{*} &= (1-\alpha_k) \phi_k^{*} + \alpha_k f(y_k) - \frac{\alpha^2_k}{2 \gamma_{k+1}} ||\nabla f(y_k)||^2 \\ & + \frac{\alpha_k(1-\alpha_k) \gamma_k}{\gamma_{k+1}} \left( \frac{\mu}{2} ||y_k - v_k||^2 + \langle \nabla f(y_k), v_k - y_k \rangle \right) \end{aligned} \end{equation*}$$ 라 하면 $\phi_k(x) = \phi_k^{*} + \frac{\gamma_k}{2} ||x - v_k||^2$이 된다.

 

이 framework에 속하는 알고리즘에서 계산하기 가장 어렵게 생긴 것은 $x_k$를 설정하는 단계이다. 첫 $x_0$야 $\lambda_0 = 1$ 조건에서 아무렇게나 잡아도 충분하니, $x_k$에서 $x_{k+1}$로 쉽게 넘어가는 방법이 있으면 좋을 것 같다. $\phi_k^{*} \ge f(x_k)$를 가정하자. 위 식과 $f$의 convexity를 활용하면, $$\begin{equation*} \begin{aligned} \phi_{k+1}^{*} & \ge (1-\alpha_k) f(x_k) + \alpha_k f(y_k) - \frac{\alpha_k^2}{2\gamma_{k+1}} ||\nabla f(y_k)||^2 + \frac{\alpha_k (1-\alpha_k) \gamma_k}{\gamma_{k+1}} \langle \nabla f(y_k), v_k - y_k \rangle \\ & \ge f(y_k) - \frac{\alpha_k^2}{2\gamma_{k+1}} ||\nabla f(y_k)||^2 + (1-\alpha_k) \langle \nabla f(y_k), x_k - y_k + \frac{\alpha_k \gamma_k}{\gamma_{k+1}} (v_k - y_k) \rangle \end{aligned} \end{equation*}$$ 그러니 우리는 $$f(y_k) - \frac{\alpha_k^2}{2\gamma_{k+1}} ||\nabla f(y_k)||^2 + (1-\alpha_k) \langle \nabla f(y_k), x_k - y_k + \frac{\alpha_k \gamma_k}{\gamma_{k+1}} (v_k - y_k) \ge f(x_{k+1})$$ 인 $x_{k+1}$이 잡기 쉬운 값이었으면 좋겠다. 그런데 우리는 이미 강력한 Descent Lemma, 즉 $$f \left(x - \frac{1}{L} \nabla f(x) \right) \le f(x) - \frac{1}{2L} || \nabla f(x)||^2$$ 이라는 식을 알고 있으니, 이를 위 부등식에 끼워맞추면 좋겠다는 생각을 할 수 있다. 이러면 필요한 식이 $$\frac{\alpha_k^2}{2 \gamma_{k+1}} = \frac{1}{2L}, \quad x_k - y_k + \frac{\alpha_k \gamma_k}{\gamma_{k+1}} (v_k - y_k) = 0, \quad x_{k+1} = y_k - \frac{1}{L} \nabla f(y_k)$$

 

이를 모두 순서에 맞게 잘 합치면, 다음과 같은 iteration을 얻는다. $\gamma_0 > 0$과 $x_0$를 임의로 잡고, $v_0 = x_0$라 하자.

$$\begin{equation*} \begin{aligned} \alpha_k \in (0, 1) &: L\alpha_k^2 = (1-\alpha_k) \gamma_k + \alpha_k \mu \\ \gamma_{k+1} &= (1-\alpha_k)\gamma_k + \alpha_k \mu \\ y_k &= \frac{\alpha_k \gamma_k v_k + \gamma_{k+1} x_k}{\gamma_k + \alpha_k \mu} \\  x_{k+1} &= y_k - \frac{1}{L} \nabla f(y_k) \\  v_{k+1} &= \frac{1}{\gamma_{k+1}} \left( (1-\alpha_k)y_k v_k + \alpha_k \mu y_k - \alpha_k \nabla f(y_k) \right) \end{aligned} \end{equation*}$$ 를 반복한다. 여기서 $\gamma_0 = L$을 주고 $\lambda_k$의 값에 대한 bound를 열심히 계산하면, 이 방법이 acceleration을 보임을 확인할 수 있다. 

 

이제 복잡한 식을 간단하게 하기 위해서 열심히 식 조작을 하면 

$$\begin{equation*} \begin{aligned} v_{k+1} &= x_k + \frac{1}{\alpha_k} (x_{k+1} - x_k) \\ \alpha_{k+1}^2 &= (1-\alpha_{k+1}) \alpha_k^2 + \alpha_{k+1} \cdot \mu /L \\ \beta_k &= \frac{\alpha_k (1-\alpha_k)}{\alpha_k^2 + \alpha_{k+1}} \\ y_{k+1} &= x_{k+1} + \beta_k (x_{k+1} - x_k) \end{aligned} \end{equation*}$$ 을 얻는다. 결국 모든 식이 다 사라지고 남는 것은 $\alpha_k, x_k, y_k$ 뿐이다. 결과는 $$\begin{equation*} \begin{aligned} x_{k+1} &= y_k - \frac{1}{L} \nabla f(y_k) \\ \alpha_{k+1}^2 &=  (1-\alpha_{k+1})\alpha_k^2 + \alpha_{k+1} \cdot \mu / L \\ \beta_k &= \frac{\alpha_k (1-\alpha_k)}{\alpha_k^2 + \alpha_{k+1}} \\ y_{k+1} &= x_{k+1} + \beta_k (x_{k+1} - x_k) \end{aligned} \end{equation*}$$ 특히 $\alpha_0 \ge \sqrt{\mu/L}$이면 acceleration이 일어난다. 또한, $\alpha_0 = \sqrt{\mu/L}$이면 $\alpha, \beta$의 값이 고정되어 fixed momentum인 경우가 나타난다.

물론 아예 $\alpha_0 = \sqrt{\mu / L}$로 잡아버리면 $\mu = 0$인 경우에 위험하므로 주의하자. 이렇게 해서 유도 과정이 끝난다.

 

다음에 기회가 되면 여기서 아이디어를 일부 얻어간 Catalyst에 대해 알아보고자 한다.