Timezone: »

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

Tue Dec 05 06:30 PM -- 10:30 PM (PST) @ Pacific Ballroom #164
in Posters Tue »

We consider the Frank-Wolfe (FW) method for constrained convex optimization, and we show that this classical technique can be interpreted from a different perspective: FW emerges as the computation of an equilibrium (saddle point) of a special convex-concave zero sum game. This saddle-point 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, as 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.

Keywords: Online Learning · Convex Optimization · Game Theory and Computational Economics
[ Paper] 

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