22-04 Properties and variants

Some variants

일부 변종 conditional gradient 방법들을 살펴보자:
• Line search: \(γk=2/(k+1),k=1,2,3,...\)를 고정하는 대신 각 \(k = 1, 2, 3, . . .\) 스텝 사이즈에 대한 exact line search를 사용한다.

\[γ_k = \arg\min_{γ∈[0,1]} f\Bigl( x^{(k−1)} + γ\bigl(s^{(k−1)} − x^{(k−1)} \bigr) \Bigr)\]

그리고 백트레킹을 사용 할 수도 있다.

• Fully corrective: 아래 식에 따라 직접 업데이트 한다.

\[x^{(k)} = \arg\min_y f(y) \: \text{ subject to } y ∈ conv\{ x^{(0)}, s^{(0)}, . . . s^{(k−1)} \}\]

이 방식은 훨씬 더 나은 진전을 이룰 수 있지만, Cost가 높다.

Another variant: away steps

좀 더 빠른 이해를 위해, [Fig 3]의 최소화 문제를 살펴 보자. 여기서 최적 해는 (0,0)이다. 그리고 conditional descent 방법은 초기 점 (0,1) 때문에 움직이기 어렵게 된다. 그러나 away step 이동으로 인해 Conditional gradient descent는 가능성 있는 지점으로 이동 할 뿐만 아니라 가능성이 없는 지점에서 벗어나게 된다.

atoms \(A\) 집합에 대한 Convex hull \(C = conv(A)\)를 가정해 보자

\(A\)에 속한 element의 convex combination으로 \(x∈C\)를 명시적으로 나타낼 수 있다.

\[x = \sum_{a∈A} λ_a(x)a\]

Away steps에서의 Conditional gradient:
\(\text{1. choose } x^{(0)} = a^{(0)} ∈ A\)
\(\text{2. for } k = 1, 2, 3, . . .\)
\(\qquad s^{(k−1)} ∈ \arg\min_{a∈A} ∇f(x^{(k−1)})^Ta,\) \(\qquad a^{(k−1)} ∈ \arg\max_{a∈A, λa(x(k−1))>0} ∇f(x^{(k−1)})^Ta\) \(\qquad \text{choose } v = s^{(k−1)} − x^{(k−1)} or \quad v = x^{(k−1)} − a^{(k−1)}\) \(\qquad x^{(k)} = x^{(k−1)} + γ_kv\)
\(\text{3. end for}\)

Linear convergence

다음의 제약 조건이 없는 문제를 고려해 보자.

\[\min_x f(x) \: \text{ subject to } x ∈ \mathbb{R}^n\]

여기서 \(f\) is µ-strongly convex이고 \(∇f\) 는 L-Lipschitz이다.

\(t_k = 1/L\) 에 대해서 gradient descent \(x^{(k+1)} = x^{(k)} − t_k∇f(x^{(k)})\)를 반복하면서, 다음을 만족시킨다.

\[f(x^{(k)}) − f^{\star} ≤ \Bigl( 1 −\frac{µ}{L} \Bigr)^k \bigl( f(x^{(0)}) − f^{\star} \bigr)\]

이제 아래의 제약 조건이 있는 문제도 고려해 보자.

\[\min_x f(x) \: \text{ subject to } x ∈ conv(A) ⊆ \mathbb{R}^n\]

[Theorem (Lacoste-Julien & Jaggi 2013)]

\(f\)가 µ-strongly convex이고, \(∇f\)는 L-Lipschitz 하며 \(A ⊆ \mathbb{R}^n\)는 유한 이라고 가정할 때

적절한 \(γ_k\)에 대해, conditional gradient 알고리즘에 의해 생성 된 반복 스텝은 다음을 항상 만족한다.

\(f(x^{(k)}) − f^{\star} ≤ (1 − r)^{k/2}(f(x^{(0)}) − f^{\star}) \text { for } r = \frac{µ}{L}·\frac{Φ(A)^2}{4\text{diam}(A)^2}\) \(\text{where }Φ(A) = \min_{F ∈faces(conv(A))} dist(F, conv(A \ F))\)

만약 polytope가 평면이면, \(Φ\)는 작고 알고리즘은 천천히 수렴한다.

Path following

다음 주어진 norm constrained 문제를 살펴보자

\[\min_x f(x) \: \text{ subject to } \| x \| ≤ t\]

Frank-Wolfe 알고리즘은 path following에 사용할 수 있다. 다시말해, (대략적인) 솔루션 경로 \(\hat{x}(t), t ≥ 0\)를 생성할 수 있다는 의미 이다.

\(t_0 = 0\)와 \(x^{\star}(0) = 0\)에서 시작하여 매개변수 \(\epsilon, m > 0\)을 수정한 다음 \(k=1,2,3,...\)에 대해 반복한다.

• \(t_k = t_{k−1} + \frac{(1 − 1/m)\epsilon}{\| ∇f(\hat{x}(t_k−1))\|\_{∗}}\)를 계산하고, 모든 \(t ∈ (t_{k−1}, t_k)\)에 대해 \(\hat{x}(t) = \hat{x}(t_{k−1})\)를 설정한다.

• \(t = t_k\) 에서 Frank-Wolfe를 실행하여 \(\hat{x}(t_k)\)를 계산하고 duality gap이 \(≤ \frac{\epsilon}{m}\) 인 경우 종료 한다.

이것은 기존의 전략을 단순화 시킨 방법이다. [Giesen et al. (2012)]

이 path following 전략을 통해, 방문하는 모든 $t$에 대해 다음을 보장할 수 있다.

\[f(\hat{x}(t)) − f(x^{\star}(t)) ≤ \epsilon\]

즉, 모든 \(t\)에 대해서 \(\epsilon\)에 의해 균일하게 경계가 정해진 suboptimality gap의 경로를 생성한다.

아래의 수식에서 보듯 Frank-Wolfe duality gap을 다음과 같이 재정의 할 수 있다.

\[g_t(x) = \max_{\|s\|≤1} ∇f(x)^T(x − s) = ∇f(x)^Tx + t\|∇f(x)\|_{∗}\]

이것은$t$에 대한 선형 함수이다. 따라서 \(g_t(x) ≤ = \frac{\epsilon}{m}\)이면, 다음 수식에 의해서 \(t^+ = t + (1 − 1/m)\epsilon/\|∇f(x)\|_{∗}\)까지 \(t\)를 증가 시킬 수 있다.

\[g_t+ (x) = ∇f(x)^Tx + t\|∇f(x)\|_{∗} + \epsilon − \epsilon/m ≤ \epsilon\]

즉, duality gap은 동일한 \(x\)에 대해 \(t\)와 \(t^+\) 사이에서 \(≤ \epsilon\)로 유지된다.