Abstract: We consider a convex-concave primal-dual optimization
framework in which the coupling between primal and dual variables is
bilinear. This framework admits linearly constrained optimization
together with a variety of interesting problems in machine learning,
including (linear) empirical risk minimization with various
regularization terms. It also includes a formulation that we term
``generalized linear programming'' (GLP) in which regularization terms
and constraints are added to the traditional linear programming
formulation, provided they admit efficient prox operations. Problems
from differentially robust optimization (DRO), using either
f-divergence metrics or Wasserstein metrics, can be formulated as
GLPs.

We describe algorithms for our framework that take prox-gradient steps
alternately in the primal and dual variables, but incorporate such
additional features as coordinate descent, variance reduction, dual
averaging, importance sampling, and iterate averaging.  Our methods
can also exploit sparsity in the matrix that couples primal and dual
variables.  Our methods match or improve on the best known worst-case
complexity bounds in various settings. Computational experiments
indicate that our methods also have good practical performance.

The talk represents joint work with Ahmet Alacaoglu, Jelena
Diakonikolas, Chaobing Song, Eric Lin, and Volkan Cevher