View abstract

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).

View abstract PDF