Frank-Wolfe Splitting via Augmented Lagrangian Method

People

Abstract

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 (FWAL) 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 (AL), 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 FWAL over general convex compact sets and a linear convergence rate over polytopes.

Paper

Proceedings of the 21st International Conference on Artificial Intelligence and Statistics (AISTATS), 2018.
(ORAL, TOP 5% of submitted papers)


Code

Code

Acknowledgements

We thank an anonymous reviewer for valuable comments which enabled us to improve the proofs. This research was partially supported by the Canada Excellence Research Chair in “Data Science for Realtime Decision-making”, by the NSERC Discovery Grant RGPIN-2017-06936 and by the European Union's Horizon 2020 research and innovation program under the Marie Sk{\l}odorowska-Curie grant agreement 748900.

Copyright Notice

The documents contained in these directories are included by the contributing authors as a means to ensure timely dissemination of scholarly and technical work on a non-commercial basis. Copyright and all rights therein are maintained by the authors or by other copyright holders, notwithstanding that they have offered their works here electronically. It is understood that all persons copying this information will adhere to the terms and constraints invoked by each author's copyright.