Frank-Wolfe

The Frank-Wolfe (FW) or Conditional Gradient algorithm is a family of first-order algorithms for constrained optimization. They seek to solve problems of the form:

$$\min_{x\in \mathcal{C}} f(x), $$

where $\mathcal{C}$ is a non-empty convex and compact set, and the objective function $f$ is differentiable, and often smooth. The gist is the following:

  • Given a current iterate $x_t$,
  • Minimize the linear approximation (i.e. the $1^\text{st}$ order Taylor expansion) of $f$ over $\mathcal C$ ; this minimum is attained on $s_t$, an extremal point of $\mathcal C$;
  • Update the iterate as a convex combination: $x_{t+1} = x_t + \gamma_t (s_t - x_t)$ for a given step-size $\gamma_t$.

It has many variants with different advantages, which can often be combined. My work has focused on two specific problems:

  • Designing an (almost) hyper-parameter free adaptive step-size scheme, i.e. choosing $\gamma_t$.
  • Designing a batch-wise stochastic variant of the algorithm, reducing overall complexity of the algorithm.
Geoffrey Négiar
Geoffrey Négiar
PhD Student

I’m a PhD student at UC Berkeley’s BAIR lab. My research focuses on optimization for machine learning, NLP and modeling in the presence of uncertainty.

Related