On the Complexity of a Practical Primal-Dual Coordinate Method. (arXiv:2201.07684v1 [math.OC])

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.

arxiv complexity math