Theory of Optimization: Frank-Wolfe Algorithm

In this post, we describe a new geometry dependent algorithm that relies on different set of assumptions. The algorithm is called conditional gradient descent, aka Frank-Wolfe.

Frank-Wolfe

Algorithm

Frank-Wolfe algorithm solves the following convex optimization problem

for $f$ such that $\nabla f(x)$ is `Lipschitz’ in a certain sense. The algorithm reduces the problem into a sequence of linear optimization problems.

Frank-Wolfe algorithm has the following procedure:

1. Initial point $x^{(0)}\in\mathbb R^n$, step size $h>0$.
2. For $k=0,1,\dots$ do
3. Compute $y^{(k)} = \arg\min_{y\in\mathcal D}\langle y, \nabla f(x^{(k)})\rangle$.
4. $x^{(k+1)} \leftarrow (1-h_k)x^{(k)} + h_ky^{(k)}$ with $h_k = \frac{2}{k+2}$.

Analysis

We have the following theorem for Frank-Wolfe algorithm.

Given a convex function $f$ on a convex set $\mathcal D$ and a constant $C_f$ such that

$$f((1-h)x + hy)\le f(x) + h\langle \nabla f(x), y-x\rangle + \frac{1}{2}C_f h^2$$

for any $x,y\in\mathcal D$ and $h\in [0,1]$, we have

$$f(x^{(k)}) - f(x^*) \le \frac{2C_f}{k+2}.$$

Proof: By the definition of $C_f$, we have

Note that from the convexity of $f$ and the definition of $y^{(k)}$, we have

Hence, we have

Let $\epsilon_k = f(x^{(k)}) - f(x^*)$, we have

Note that $\epsilon_0 = f^{(0)} - f(x^*) \le \frac{1}{2}C_f$, we can prove the theorem by induction.

⬜

Note that if $\nabla f(x)$ is L-Lipschitz with respect to $||\cdot||$, over the domain $\mathcal D$, then $C_f \le L\cdot diam_{||\cdot||}(\mathcal D)^2$.

Sparsity Analysis

For the domain $\mathcal D$ is a simplex, the step $y^{(k)}$ is always a vertex of the simplex, and hence, each step of Frank-Wolfe increases the sparsity by at most $1$. We can think that the convergence result of Frank Wolfe proves that there is an approximate sparse solution of the optimization problem.

Given a polytope $\mathcal P = conv(v_i)$ lies inside an unit ball. For any $u\in\mathcal P$, there are $k = O(\frac{1}{\epsilon^2} )$ vertices $v_1,\dots, v_k$ of $\mathcal P$ such that

$$||\sum_{i=1}^k\lambda_i v_i -u||_2 \le \epsilon,$$

for some $\sum_i \lambda_i = 1, \lambda_i \ge 0$.

Proof: Run Frank-Wolfe algorithm with $f(x) = ||x-u||_2^2$. Note that $f$ is 1-Lipschitz with respect to $||x||_2$ and that the diameter of $\mathcal P$ is bounded by $1$. Hence, we have $C_f \le 1$.

Therefore, Frank-Wolfe algorithm shows that

Since $f(u) = 0$, we have $||x^{(k)} - u||^2 \le \frac{4}{k+2}$, and this gives the result.

⬜