Let $g(w)$ be a differentiable convex function. Frank-Wolfe algorithm over a convex set $C \in \mathbb{R}^n$ is defined so as to find the local minimum of the function:

$$ s_{t+1}=\arg\min_{s \in C} \langle s, \nabla g(w_t) \rangle \tag{1} $$ $$ w_{t+1} = (1-\eta_t)w_{t}+\eta_ts_t \tag{2} $$

where $\eta_t$ is the step size and is in $[0,1]$ and $t=1,2,\cdots,T$.

The intuition behind the the first step of Frank-Wolfe algorithm is that we find the closest vector to the negative gradient (by closest I mean the projection of $s_{t+1}$ onto $-\nabla g(w_t)$ is maximum). The intuition behind the second step arises from the fact that we start off from $s_1$ which is in $C$ and chose $w_{1}$ so as to be in $C$ using the convex combination.

I have drawn the following picture to better understanding.

enter image description here

Note: If $C$ was a polytope, then $s_1$ is at the vertex of the polytpoe because $(1)$ became Linear Programming.

My questions are:

1- Why this works?

2- What is the proof of convergence?

3- When $-\nabla g(w_t)$ is not in $C$, why $s_{t+1}$ is on the boundary of $C$?

  • 2
    $\begingroup$ This blog post has a section on convergence theory of the FW algorithm that may help answer your question. $\endgroup$ – David M. Feb 3 '19 at 2:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.