Session II.2 - Continuous Optimization
Friday, June 16, 18:00 ~ 18:30
On the Complexity of a Simple Primal-Dual Coordinate Method
Ahmet Alacaoglu
University of Wisconsin-Madison, USA - This email address is being protected from spambots. You need JavaScript enabled to view it.
We focus on an algorithm called "primal-dual algorithm with random extrapolation and coordinate descent (PURE-CD)", which has been shown to obtain good practical performance for solving convex-concave min-max problems with bilinear coupling. Such problems arise in many machine learning contexts, including linear empirical risk minimization, matrix games, and image processing. We prove complexity bounds for PURE-CD that either match or improve the best-known complexities for dense and sparse (strongly)-convex-(strongly)-concave problems with bilinear coupling in the literature.
Joint work with Volkan Cevher (EPFL) and Stephen J. Wright (University of Wisconsin-Madison).