Seminar

Boosting Frank-Wolfe by chasing gradients - and - Complexity of Linear Minimizationand Projection on Some Sets

Cyrille Combettes ( Toulouse School of Economics, France)

November 25, 2021, 11:00–12:15

Toulouse

Room A6

MAD-Stat. Seminar

Abstract

The Frank-Wolfe algorithm is a simple projection-free algorithm for constrained optimization, and it has been successfully applied to a variety of real-world problems. Its main drawback however lies in its speed of convergence, which can be excessively slow due to naive descent directions. In this talk, we present a overview of the Frank-Wolfe algorithm and describe its fundamental properties. Then, we propose a scheme to speed it up. It consists in finding descent directions better aligned with the negative gradient directions, while still preserving the projection-free property. Although the idea is reasonably natural, it produces very significant results which we demonstrate through a convergence analysis and a series of computational experiments.