이 글에서는 논문 www.di.ens.fr/~ataylor/share/PESTO_CDC_2017.pdf를 정리한다.
(지금 보니까 저 논문은 toolkit 소개고, 아이디어 자체는 arxiv.org/pdf/1502.05666.pdf를 보는 게 더 좋을 것 같다)
보통 우리는 문제가 주어지면
- 이를 해결하는 알고리즘을 설계하고
- 최악의 경우에 어떻게 작동하는지 분석
한다. 만약 PS를 하는 사람이라면 답을 정확하게 구하는 알고리즘을 설계한 후, 최악의 경우의 시간복잡도를 분석할 것이다.
비슷하게, 최적화에서는 보통 답을 iterative 하게 근사하는 알고리즘을 설계한 후, 최악의 경우의 수렴성을 분석한다.
이 논문은 "최악의 경우의 수렴성"을 분석하는 자동화된 toolkit을 제시하는 논문이다. toolkit 링크는 여기다. Matlab으로 작성되어 있다.
toolkit의 기본 작동 원리를 알기 위해서, 작은 문제를 하나 풀어보자.
문제 (Informal) : $\mu$-strongly convex, $L$-smooth function $F$가 있다. $F$를 최소화하는 문제를 풀고자 한다. Initial point $x_0$에서 Gradient Descent를 적용하여 $x_1 = x_0 - \gamma \nabla F(x_0)$를 얻었을 때, $||\nabla F(x_1)||$의 크기를 얼마나 잘 줄일 수 있을까? 최악의 경우를 비교하여, 최선의 $\gamma$를 구할 수 있을까?
- $\mu$-strongly convex, $L$-smooth의 의미는 이 글과 이 글에서 매우 잘 정리되어 있다.
- $\mu$-strongly convex, $L$-smooth function의 집합을 $\mathcal{F}_{\mu, L}$이라고 쓴다.
이 문제를 엄밀하게 서술하려면, 이를 최적화 문제 형태로 서술해야 한다. $$\begin{equation*} \begin{aligned} \text{maximize} \quad & ||\nabla F(x_1)||^2 \\ \text{subject to} \quad & F \in \mathcal{F}_{\mu, L} \\ \quad & x_1 = x_0 - \gamma \nabla F(x_0) \end{aligned} \end{equation*}$$ 그런데 이렇게만 쓰면 답이 $\infty$인 것이 뻔하므로, 추가적인 제약조건이 필요하다. 예를 들어, $|| \nabla F(x_0) ||^2$의 크기에 제약조건을 걸 수 있다. 그러면 $$\begin{equation*} \begin{aligned} \text{maximize} \quad & ||\nabla F(x_1)||^2 \\ \text{subject to} \quad & F \in \mathcal{F}_{\mu, L} \\ \quad & x_1 = x_0 - \gamma \nabla F(x_0) \\ \quad & ||\nabla F(x_0)||^2 \le R^2 \end{aligned} \end{equation*}$$ 라는 최적화 문제를 얻는다. 그런데 $F \in \mathcal{F}_{\mu, L}$가 변수라는 점이 문제 해결을 어렵게 한다.
여기서 멋진 아이디어가 사용된다. 먼저, 우리가 $F$라는 함수에 접근하는 점은 $x_0, x_1$ 두 곳이다.
그러니 사실 우리는 $f_i = F(x_i)$, $g_i = \nabla F(x_i)$의 값에만 관심을 가져도 충분하다. 이제 최적화 문제를 쓰면 $$\begin{equation*} \begin{aligned} \text{maximize} \quad & ||g_1||^2 \\ \text{subject to} \quad & \exists F \in \mathcal{F}_{\mu, L} \text{ s.t. } F(x_i) = f_i, \nabla F(x_i) = g_i \\ \quad & x_1 = x_0 - \gamma g_0, \text{ } ||g_0||^2 \le R^2 \end{aligned} \end{equation*}$$의 형태가 된다. 그러니, 우리가 관심을 갖게 되는 문제는
- 언제 $F(x_i) = f_i$, $\nabla F(x_i) = g_i$를 만족하는 $F \in \mathcal{F}_{\mu, L}$이 존재할까?
가 된다. 이런 문제는 Lagrange Interpolation의 향기가 나고, 실제로 Interpolation이라고 불린다.
그리고 $F \in \mathcal{F}_{\mu, L}$로 interpolation이 되는 조건은 이 논문에서 이미 증명이 되었다.
결론은 각 $i \neq j$에 대하여 부등식 $$f_i \ge f_j + \langle g_j, x_i - x_j \rangle + \frac{1}{2(1-\mu / L)} \left( \frac{1}{L} ||g_i - g_j||^2 + \mu ||x_i - x_j||^2 - 2 \frac{\mu}{L} \langle g_j - g_i, x_j - x_i \rangle \right)$$이 성립하는 것이, 원하는 interpolation 조건을 만족하는 $F \in \mathcal{F}_{\mu, L}$이 존재할 필요충분조건이라는 것이다.
이제 최적화 문제의 constraint 첫 줄을 interpolation 조건으로 교체할 수 있다. 또한, $x_1 = x_0 - \gamma g_0$를 대입하여 $x_1$ 변수를 제거할 수 있다.
남은 문제를 바라보면 다루고 있는 변수가
- $f_0$, $f_1$ : 이 값들은 constraint에서 그냥 혼자 있는 값들이다.
- $g_0, g_1, x_0$ : 이 값들은 objective나 constraint나 무조건 다른 값과 내적이 되어있다.
이 성질 때문에, 문제를 Semidefinite Programming (SDP) 형태로 바꿀 수 있다. Gram Matrix $$G = \left[ \begin{matrix} \langle x_0, x_0 \rangle & \langle g_0, x_0 \rangle & \langle g_1, x_0 \rangle \\ \langle x_0, g_0 \rangle & \langle g_0, g_0 \rangle & \langle g_1, g_0 \rangle \\ \langle x_0, g_1 \rangle & \langle g_0, g_1 \rangle & \langle g_1, g_1 \rangle \end{matrix} \right]$$를 생각하자. Gram Matrix의 성질에 의하여, 다음이 성립한다.
- $G$는 Positive Semidefinite이며, 특히 풀고 있는 문제가 $\mathbb{R}^d$ 위의 문제면 rank가 최대 $d$.
- Positive Semidefinite이며 rank가 최대 $d$인 행렬이 주어지면, 이를 Gram Matrix로 보고 vector $x_0, g_0, g_1$을 복원할 수 있음.
그러므로 우리의 모든 문제를 $f_0$, $f_1$과 $G$에 대한 문제로 볼 수 있으며, $G$에 대해 명시할 조건은 $G$가 Positive Semidefinite이라는 점과 rank가 $d$ 이하라는 점이다. 하지만 우리의 관심사는 일반적인 $d$에 대한 것이므로, rank 조건은 제거해도 무방하다. (당장 $d \ge 3$이기만 해도 rank 조건이 무의미하다)
이제 남은 문제를 보면 진짜 단순한 Semidefinite Programming 문제고, 이는 standard solver로 해결할 수 있다.
논문에 의하면, 이렇게 SDP로 문제를 변형하여 해결할 수 있는 경우는 다음을 포함한다.
- Class of Functions : Smooth Convex, Strongly Convex, Bounded Subgradients, Bounded Domains, Non-Convex Smooth 등
- Methods : First-Order Methods : Subgradient, Proximal Operator 등
- Performance Measure (objective 설정) : $||x_n - x_{*}||^2$, $||\nabla F(x_n)||^2$, $F(x_n) - F(x_{*})$ 등
- Initial Condition : Performance Measure와 동일함. 물론, $x_n$ 대신 initial point $x_0$에 대한 조건.
그리고 이 toolkit은 이러한 경우 대부분을 지원한다고 한다. 갖고 놀기 좋은 것 같은데, 아직 쓰는 법은 모른다 ㅎㅎ;
궁금한 점은 이 toolkit으로 답을 $\mu$, $L$에 대한 수식으로 얻으려면 수식이 변수로 들어가있는 Symbolic한 SDP를 해결해야 할텐데, 이건 대체 어떻게 한 건지 궁금하다. toolkit 보면 수식으로 답을 얻어주는 것 같은데... 관련 논문 읽어봐도 아이디어는 알겠으나 이 점이 계속 헷갈린다. 더 공부하는 걸로.
UPD : 직접 돌려본 결과, 수치적으로 계산해준다. 그냥 예시에 답이 이렇게 나와야 한다고 주석으로 써있는 것..
arxiv.org/pdf/1502.05666.pdf 논문의 추가적인 내용은
- Interpolation 관련 엄밀한 증명
- SDP로 문제를 변환하는 것과, 해당 문제의 성질에 대한 엄밀한 증명
- SDP로 변환된 문제의 Lagrangian Dual을 생각하여, Upper Bound를 계산
- 특히, Slater Condition을 이용하여 "웬만하면" Duality Gap이 없음을 증명
- Performance Estimation Problem의 여러 응용 : 이걸로 문제를 많이 해결/제시하는 것 같다