  We prove complexity bounds for the 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. Our complexity bounds either match or improve the best-known
results in the literature for both dense and sparse
(strongly)-convex-(strongly)-concave problems.
