Frank-Wolfe Splitting via Augmented Lagrangian Method
  Minimizing a function over an intersection of convex sets is an important
task in optimization that is often much more challenging than minimizing it
over each individual constraint set. While traditional methods such as
Frank-Wolfe (FW) or proximal gradient descent assume access to a linear or
quadratic oracle on the intersection, splitting techniques take advantage of
the structure of each sets, and only require access to the oracle on the
individual constraints. In this work, we develop and analyze the Frank-Wolfe
Augmented Lagrangian (FW-AL) algorithm, a method for minimizing a smooth
function over convex compact sets related by a "linear consistency" constraint
that only requires access to a linear minimization oracle over the individual
constraints. It is based on the Augmented Lagrangian Method (ALM), also known
as Method of Multipliers, but unlike most existing splitting methods, it only
requires access to linear (instead of quadratic) minimization oracles. We use
recent advances in the analysis of Frank-Wolfe and the alternating direction
method of multipliers algorithms to prove a sublinear convergence rate for
FW-AL over general convex compact sets and a linear convergence rate for
polytopes.
