Accelerated Gradient Methods

References: Boris T. Polyak, “Some Methods of Speeding Up the Convergence of Iteration Methods,” 1964; Yurii Nesterov, Introductory Lectures on Convex Optimization, Springer, 2004, Ch. 2; Sébastien Bubeck, Convex Optimization: Algorithms and Complexity, 2015, Secs. 3.5 and 3.7.

이 장에서는 first-order method에서 acceleration이 무엇을 의미하는지부터 정의한다. Acceleration은 단순히 momentum term을 추가하거나 특정 예제에서 더 빨리 움직이는 현상이 아니라, 동일한 oracle 비용 아래 함수 class 전체에 대한 worst-case convergence rate 또는 iteration complexity를 개선하는 성질이다. 이를 기준으로 Heavy-Ball method의 quadratic acceleration, Nesterov method의 optimal worst-case rate, potential-function proof, strong convexity와 restart의 역할을 분석한다.

별도의 언급이 없으면 $f:\mathbb{R}^n\rightarrow\mathbb{R}$는 convex이고 $L$-smooth하며, minimizer $x^{\star}$가 존재한다고 가정한다. $f^{\star}=f(x^{\star})$로 쓰고, strongly convex case에서는 $f$가 추가로 $\mu$-strongly convex이며 $\kappa=L/\mu$라 둔다.

Definition of Acceleration

First-order oracle는 질의점 $x$가 주어졌을 때 $f(x)$와 $\nabla f(x)$를 반환한다. 알고리즘 $\mathcal{A}$가 $k$번의 oracle call 이후 생성한 점을 $x_k^{\mathcal{A}}$라 하자. 함수 class $\mathcal{F}$와 초기 거리 $R>0$에 대한 worst-case residual을

로 정의한다. 두 알고리즘이 iteration마다 같은 수의 first-order oracle call을 사용한다고 하자.

Definition: accelerated method

기준 알고리즘 $\mathcal{A}$와 비교 알고리즘 $\mathcal{B}$에 대해

이면 $\mathcal{B}$가 $\mathcal{A}$를 worst-case rate의 의미에서 accelerate한다고 한다. 동일한 정확도 $\varepsilon$을 달성하는 데 필요한 oracle call 수

를 비교하여 acceleration을 정의할 수도 있다.

Smooth convex class에서는 gradient descent의 $\mathcal{O}(1/k)$ rate를 $\mathcal{O}(1/k^2)$로 개선하는 것이 acceleration이다. Smooth strongly convex class에서는 두 방법이 모두 linear convergence를 가지므로 수렴 차수만으로는 차이가 드러나지 않는다. 이 경우

와 같이 condition number dependence가 개선되는 것을 acceleration이라 한다.

따라서 momentum은 iteration의 형태이고 acceleration은 convergence guarantee이다. Momentum term을 갖는 모든 방법이 accelerated method인 것은 아니며, 한 문제에서 iteration 수가 줄었다는 관찰만으로 함수 class에 대한 acceleration이 증명되지는 않는다. 또한 여기서 말하는 acceleration은 수치해석의 convergence order를 linear에서 superlinear로 바꾸는 개념과도 다르다.

Why Acceleration Is Needed

고정 step size $1/L$을 사용하는 gradient descent는 convex smooth objective에서

의 수렴속도를 갖는다. Strongly convex objective에서는

이므로, 목적함수 오차를 $\varepsilon$ 이하로 만들기 위해

번의 iteration이 필요하다. $\kappa$가 크면 작은-curvature direction의 오차가 느리게 감소한다. Acceleration의 목적은 각 iteration에서 한 번의 gradient evaluation을 유지하면서 과거 이동량을 결합하여 이 condition-number dependence를 $\kappa$에서 $\sqrt{\kappa}$로 줄이는 것이다.

일반적인 momentum iteration은

의 형태를 갖는다. Heavy-Ball method는 $\widetilde{x}_k=x_k$에서 gradient를 계산하고, Nesterov method는 momentum으로 먼저 얻은 extrapolated point에서 gradient를 계산한다. 이 작은 차이가 일반적인 smooth convex function에 대한 수렴 보장에서 결정적이다.

First-Order Oracle Complexity

Acceleration의 기준은 gradient descent보다 빠르다는 사실에 그치지 않는다. Standard first-order black-box model에서는 충분히 높은 차원의 문제에 대해 다음 lower bound가 알려져 있다.

• Convex하고 $L$-smooth한 함수 class에서는 임의의 deterministic first-order method에 대해 worst-case objective error가 $\Omega(LR^2/(k+1)^2)$보다 빠르게 감소할 수 없다.
• $\mu$-strongly convex하고 $L$-smooth한 함수 class에서는 $\varepsilon$ 정확도에 $\Omega(\sqrt{\kappa}\log(1/\varepsilon))$번의 first-order oracle call이 필요하다.

Lower-bound proof는 알고리즘이 $k$번의 oracle call로 탐색할 수 있는 subspace 밖에 아직 드러나지 않은 curvature direction을 남기는 resisting-oracle quadratic을 구성한다. 이 장에서는 그 구성 자체를 증명하지 않고, lower bound와 일치하는 upper bound를 직접 증명한다. 따라서 뒤에서 얻는

와

는 이 oracle model에서 order-optimal하다. 즉 acceleration은 gradient descent의 분석을 더 날카롭게 한 결과가 아니라, first-order information으로 달성 가능한 최적 차수까지 알고리즘 자체를 개선한 결과이다.

Heavy-Ball Method

Polyak의 Heavy-Ball method는

로 정의된다. $x_k-x_{k-1}$는 직전 iteration의 이동 방향이며, $\beta$는 그 이동량을 얼마나 유지할지를 결정한다. $\beta=0$이면 fixed-step gradient descent가 된다.

Why a positive-definite quadratic?

Heavy-Ball method를 처음부터 일반 nonlinear function에서 분석하면 gradient와 Hessian이 iteration마다 달라져 momentum의 효과를 정확히 분리하기 어렵다. 반면 positive-definite quadratic에서는 Hessian이 하나의 고정 행렬이고, 각 eigendirection의 움직임이 서로 독립적인 scalar recurrence가 된다. 따라서 step size와 momentum이 각 curvature mode를 얼마나 빠르게 감쇠시키는지 정확히 계산할 수 있다.

여기서 quadratic problem을 먼저 보는 목적은 모든 strongly convex function을 quadratic으로 가정하려는 것이 아니다. Heavy-Ball acceleration의 spectral mechanism을 가장 명확하게 확인하고, 동시에 그 보장이 일반 nonlinear function으로 자동 확장되지 않는 이유를 밝히기 위한 것이다.

일반적인 positive-definite quadratic objective는

로 쓸 수 있다. Gradient는

이고, $Q\succ0$이므로 유일한 minimizer $x^{\star}$는

를 만족한다. 따라서

이며, complete the square를 적용하면

이다. 상수 $f^{\star}$는 minimizer와 iteration에 영향을 주지 않으므로 이후에는 중심이 이동된 형태

만 분석한다.

추가로

라 가정한다. 이는 $Q$의 모든 eigenvalue가 $[\mu,L]$에 있다는 뜻이며, 이 quadratic function이 $\mu$-strongly convex이고 $L$-smooth하다는 조건과 정확히 일치한다. 따라서 condition number는 $\kappa=L/\mu$이다.

Derivation of the error recurrence

최적점으로부터의 오차를

로 정의한다. 앞에서 구한 gradient 식에 의해 $\nabla f(x_k)=Qe_k$이다. Heavy-Ball update의 양변에서 $x^{\star}$를 빼면

세 번째 줄에서는 momentum difference에 같은 $x^{\star}$를 더하고 뺐다. 이 때문에 $x_k-x_{k-1}=e_k-e_{k-1}$가 된다. Momentum이 이전 오차 $e_{k-1}$까지 포함하므로 gradient descent의 일차 recurrence와 달리 Heavy-Ball은 이차 recurrence를 만든다.

이제 $Q=U\Lambda U^T$를 eigendecomposition하고

라 두자. $U$는 orthogonal matrix이므로 오차 반복식의 양변에 $U^T$를 곱하면

를 얻는다. 따라서 eigenvalue $\lambda\in[\mu,L]$에 대응하는 한 성분은 다른 성분과 독립적으로

를 만족한다.

이 scalar recurrence의 해를 $(z_k)_{\lambda}=r^k d$의 형태로 놓고 대입하면

이고, $r^{k-1}d$를 소거하여 characteristic equation

을 얻는다. 두 characteristic root의 modulus가 $1$보다 작으면 해당 curvature mode가 감쇠한다. 따라서 Heavy-Ball의 수렴성은 모든 $\lambda\in[\mu,L]$에 대해 두 root가 unit disk 안에 있도록 $\alpha$와 $\beta$를 선택하는 문제로 바뀐다.

Theorem: quadratic problem에서 Heavy-Ball의 accelerated spectral rate

다음 parameter를 선택하자.

그리고

라 두자. 그러면 모든 eigendirection에서 characteristic root의 크기는 $\rho_{\mathrm{HB}}$ 이하이고,

Proof

$\rho=\rho_{\mathrm{HB}}$라 쓰면 $\beta_{\mathrm{HB}}=\rho^2$이다. Characteristic polynomial의 linear coefficient를

라 두자. Parameter 정의를 직접 대입하면

$a(\lambda)$는 $\lambda$에 대한 affine function이므로 모든 $\lambda\in[\mu,L]$에 대해

이다. 따라서 characteristic equation은

가 된다. $\lvert a(\lambda)\rvert<2\rho$이면 두 root는 complex conjugate이고 root의 곱이 $\rho^2$이므로 각각의 modulus는 $\rho$이다. $\lambda=\mu$와 $\lambda=L$에서는 각각 $r=\rho$와 $r=-\rho$가 repeated root이다. 따라서 모든 eigendirection의 spectral radius가 $\rho$ 이하이다.

각 성분은 root의 거듭제곱의 선형결합이며 repeated root에서는 $k\rho^k$ 형태의 항이 추가될 수 있다. 그러나 $\lim_{k\rightarrow\infty}k^{1/k}=1$이므로 모든 성분에 대해 asymptotic root factor가 $\rho$ 이하이고, 유한차원 norm의 동치성에 의해 주장한 결과를 얻는다. $\square$

Gradient descent의 optimal fixed-step spectral factor는

인 반면 Heavy-Ball은 $\rho_{\mathrm{HB}}=(\sqrt{\kappa}-1)/(\sqrt{\kappa}+1)$을 얻는다. 따라서 quadratic problem에서는 필요한 iteration 수가 $\mathcal{O}(\kappa\log(1/\varepsilon))$에서 $\mathcal{O}(\sqrt{\kappa}\log(1/\varepsilon))$로 감소한다.

이 결론의 범위는 중요하다. 위 parameter와 spectral proof는 Hessian이 고정된 positive-definite quadratic objective에 대한 결과이다. 일반적인 $L$-smooth, $\mu$-strongly convex function에서는 Hessian이 위치에 따라 변하므로 같은 scalar recurrence로 분해되지 않는다. 따라서 quadratic-optimal Heavy-Ball parameter만으로 동일한 전역 수렴률을 바로 주장할 수 없다.

Gradient Step의 Three-Point Inequality

Nesterov acceleration의 분석에는 단순한 descent inequality보다 강한 비교 부등식이 필요하다.

Lemma: gradient step의 three-point inequality

$f$가 convex이고 $L$-smooth하다고 하자. 임의의 $y\in\mathbb{R}^n$에서

로 gradient step을 정의하면, 모든 $u\in\mathbb{R}^n$에 대해

가 성립한다.

Proof

$g=\nabla f(y)$라 하자. Descent Lemma와 $x^+-y=-g/L$로부터

Convexity에 의해 $f(y)\leq f(u)+g^T(y-u)$이므로

한편 $x^+=y-g/L$을 사용하면

두 식을 결합하면 결과를 얻는다. $\square$

이 부등식은 새 함수값을 임의의 비교점 $u$에서의 함수값과 두 squared distance의 차이로 제어한다. Nesterov method에서는 $u$를 $x_{k-1}$과 $x^{\star}$의 특별한 convex combination으로 선택하여 함수값 오차와 거리 오차가 하나의 potential로 telescope되게 만든다.

Nesterov Acceleration for Smooth Convex Functions

$t_0=0$, $t_1=1$, $y_1=x_0$로 초기화한다. $k\geq1$에서 다음 iteration을 수행한다.

$x_k$는 gradient step으로 얻은 primary sequence이고 $y_k$는 gradient를 계산하는 extrapolated sequence이다. Scalar recurrence에서

이 성립한다. 또한

이므로 induction에 의해

이다.

분석을 위해 $\Delta_k=f(x_k)-f^{\star}$라 두고

를 정의한다.

Theorem: smooth convex objective에서 $\mathcal{O}(1/k^2)$ convergence

위 Nesterov iteration에 대해 모든 $k\geq1$에서

Proof

Three-point inequality에서 $y=y_k$, $x^+=x_k$로 두고 비교점을

로 선택한다. Convexity에 의해

이므로

$k\geq2$에서 extrapolation 식을 정리하면

$k=1$에서도 $t_1=1$과 $y_1=x_0$에 의해 좌변은 $z_0$이다. 따라서 모든 $k\geq1$에서

앞의 함수값 부등식에 $2t_k^2/L$을 곱하면

$t_k(t_k-1)=t_{k-1}^2$이므로 potential

은 감소한다. 이 부등식을 반복하고 $t_0=0$을 사용하면

$\lVert z_k\rVert^2\geq0$이므로

마지막으로 $t_k\geq(k+1)/2$를 대입하면 두 번째 부등식을 얻는다. $\square$

따라서 $f(x_k)-f^{\star}\leq\varepsilon$을 얻기 위한 iteration complexity는

이다. Gradient descent의 $\mathcal{O}(1/\varepsilon)$ dependence와 비교하면 Nesterov acceleration은 이를 $\mathcal{O}(1/\sqrt{\varepsilon})$로 개선한다.

Potential $\mathcal{E}_k$가 감소한다는 사실은 $f(x_k)$ 자체가 매 iteration에서 감소한다는 뜻이 아니다. Momentum 때문에 목적함수 값이나 반복점은 진동할 수 있으며, 수렴 증명은 함수값 오차와 보조 거리항을 결합한 potential의 감소에 의존한다.

Restarted Acceleration under Strong Convexity

Strongly convex 전용 momentum coefficient를 사용하지 않더라도 convex Nesterov method를 주기적으로 restart하면 accelerated linear convergence를 얻을 수 있다. Restart란 한 block의 마지막 점을 다음 block의 초기점으로 사용하면서 momentum state를 초기화하는 것이다.

Theorem: periodic restart의 accelerated linear convergence

$f$가 $\mu$-strongly convex이고 $L$-smooth하다고 하자. Convex Nesterov method를

번 수행한 뒤 momentum을 초기화한다. $s$번째 restart point를 $\widehat{x}_s$라 하면

따라서 전체 iteration complexity는

이다.

Proof

한 block의 초기점을 $\widehat{x}_s$라 하자. Convex Nesterov rate를 $m$번 적용하면

Strong convexity에 의해

이므로

$m+1\geq\sqrt{8\kappa}$이면 contraction factor가 $1/2$ 이하이다. 이 부등식을 $s$번 반복하면 첫 번째 결과를 얻는다. $s\geq\log_2((f(\widehat{x}_0)-f^{\star})/\varepsilon)$개의 block이면 충분하고 각 block은 $m=\mathcal{O}(\sqrt{\kappa})$ iteration을 사용하므로 전체 complexity도 따라온다. $\square$

Periodic restart는 $\mu$를 알아야 block length를 정할 수 있지만, strongly convex acceleration이 반드시 하나의 고정 momentum formula에만 의존하지는 않는다는 사실을 보여준다. 핵심은 $\mathcal{O}(1/k^2)$ 감소와 strong-convexity error bound를 반복적으로 결합하는 것이다.

Nesterov Acceleration for Strongly Convex Functions

$f$가 $\mu$-strongly convex이고 $L$-smooth하다고 하자. 다음 상수를 둔다.

수렴 증명을 위해 $x_0=v_0$로 초기화한 다음 세 sequence를 사용한다.

이 표현은 분석을 위한 것이며, $v_k$를 제거하면 $y_0=x_0$와

을 얻는다. 즉 Nesterov method는 먼저 $y_k$에서 gradient step을 수행한 후, 새 primary iterate의 이동량으로 다음 extrapolated point를 만든다. Heavy-Ball이 $x_k$에서 gradient를 계산한 뒤 같은 $x_k$에 momentum을 더하는 것과 순서가 다르다.

Theorem: strongly convex objective에서 accelerated linear convergence

다음 potential을 정의하자.

그러면

이고, 따라서

Proof

$g_k=\nabla f(y_k)$라 하고

라 두자. $v_k$ update에서

이므로

한편 Descent Lemma와 $x_{k+1}=y_k-g_k/L$에 의해

$q^2=\mu/L$이므로 두 식의 gradient-norm 항은 서로 소거된다.

Strong convexity를 $x_k$와 $x^{\star}$에 각각 적용하면

첫 번째 부등식에 $1-q$, 두 번째 부등식에 $q$를 곱한 뒤 더하면

$y_k=(x_k+qv_k)/(1+q)$를 정리하면

이므로 위 부등식의 inner-product 항은 $qg_k^Tw_k$이다. 따라서 함수값 부등식과 $v_{k+1}$의 거리 부등식을 더할 때 이 항도 소거된다.

마지막으로 convex-combination norm identity에 의해

따라서

지금까지의 부등식을 결합하면

이를 반복하고 $f(x_k)-f^{\star}\leq\mathcal{V}_k$를 사용하면 주장한 수렴률을 얻는다. $\square$

$v_0=x_0$이고 strong convexity에 의해

이므로 $\mathcal{V}_0\leq2(f(x_0)-f^{\star})$이다. 따라서 더 단순한 bound

도 얻는다. $1-t\leq e^{-t}$를 사용하면

따라서 $\varepsilon$ 정확도에 필요한 iteration 수는

이다.

Parameter Knowledge and Scope

가속 수렴률은 parameter 선택 및 함수 class와 분리할 수 없다.

• Step size $1/L$은 smoothness constant의 valid upper bound를 요구한다. $L$을 과소평가하면 quadratic upper model과 three-point inequality에 기반한 증명이 성립하지 않을 수 있다.
• Convex Nesterov method의 $t_k$ recurrence는 $\mu$를 사용하지 않지만, strongly convex constant momentum은 $\beta=(\sqrt{\kappa}-1)/(\sqrt{\kappa}+1)$을 계산하기 위해 $\mu$와 $L$을 요구한다.
• $L$을 모르면 accelerated backtracking으로 local upper-model condition을 검사할 수 있다. $\mu$를 모르면 convex scheme을 restart하여 strong-convexity growth를 활용할 수 있다.
• Accelerated sequence는 일반적으로 monotone하지 않다. 함수값의 일시적 증가나 iterate의 진동은 수렴 실패를 의미하지 않으며, 증명에서 감소하는 양은 $f(x_k)$가 아니라 $\mathcal{E}_k$ 또는 $\mathcal{V}_k$이다.
• 이 장의 rate는 exact deterministic gradient에 대한 결과이다. Gradient error가 있는 경우 momentum이 오차를 누적할 수 있으므로 같은 potential bound를 별도 분석 없이 사용할 수 없다.

따라서 알고리즘 이름만으로 accelerated rate가 보장되는 것은 아니다. 함수 class, oracle model, parameter rule, initialization, 그리고 어떤 residual을 측정하는지가 정리의 일부이다.

Heavy-Ball and Nesterov Acceleration

Heavy-Ball과 Nesterov method는 모두 이전 이동량을 사용하지만 수렴 논리는 다르다. Heavy-Ball의 accelerated factor는 quadratic objective의 eigendirection별 recurrence를 통해 얻는다. Nesterov method는 extrapolated point에서 gradient를 계산하도록 iteration을 설계하고, 함수값 오차와 보조 거리항을 결합한 potential이 telescope하거나 contract하도록 만든다. 이 구조 때문에 Nesterov acceleration은 일반적인 smooth convex 및 smooth strongly convex function class에 대해 명시적인 worst-case rate를 제공한다.

Summary

Acceleration은 momentum의 존재가 아니라 동일한 first-order oracle 비용에서 함수 class의 worst-case rate 또는 condition-number dependence가 개선되는 성질이다. Smooth convex class의 $\mathcal{O}(1/k^2)$ rate와 smooth strongly convex class의 $\mathcal{O}(\sqrt{\kappa}\log(1/\varepsilon))$ complexity는 standard first-order oracle lower bound와 일치한다.

Heavy-Ball method는 positive-definite quadratic problem에서 각 eigendirection을 이차 recurrence로 분해하며, 최적 parameter에서 $(\sqrt{\kappa}-1)/(\sqrt{\kappa}+1)$의 asymptotic spectral factor를 갖는다. 그러나 이 분석은 Hessian이 고정된 quadratic 구조에 의존하므로 일반 smooth strongly convex function에 자동으로 확장되지 않는다.

Nesterov acceleration의 핵심은 함수값 오차와 거리 오차가 함께 감소하도록 extrapolation coefficient를 선택하는 데 있다. Smooth convex case에서는 $t_k^2-t_k=t_{k-1}^2$ 관계가 potential을 telescope하게 만들고, strongly convex case에서는 $q=1/\sqrt{\kappa}$가 potential을 contract하게 한다. Convex scheme을 $\mathcal{O}(\sqrt{\kappa})$ iteration마다 restart해도 같은 accelerated complexity를 얻을 수 있다. 목적함수 값은 매 iteration에서 단조 감소할 필요가 없으며, parameter와 oracle 가정이 달라지면 potential proof도 다시 확인해야 한다.