Timezone: »

 
Spotlight
On Frank-Wolfe and Equilibrium Computation
Jacob D Abernethy · Jun-Kun Wang

Tue Dec 05 03:40 PM -- 03:45 PM (PST) @ Hall A
in Algorithms, Optimization »

We consider the Frank-Wolfe method for constrained convex optimization, a first-order projection-free procedure. We show that this algorithm can be recast in a different light, emerging as a special case of a particular meta-algorithm for computing equilibria (saddle points) of convex-concave zero-sum games. This equilibrium computation trick relies on the existence of no-regret online learning to both generate a sequence of iterates but also to provide a proof of convergence through vanishing regret. We show that our stated equivalence has several nice properties, particularly that it exhibits a modularity that gives rise to various old and new algorithms. We explore a few such resulting methods, and provide experimental results to demonstrate correctness and efficiency.

Author Information

Jacob D Abernethy (University of Michigan)
Jun-Kun Wang (Georgia Institute of Technology)

Related Events (a corresponding poster, oral, or spotlight)

More from the Same Authors