On the Complexity of a Practical Primal-Dual Coordinate Method
This work provides theoretical guarantees for a practical algorithm used in machine learning optimization, though it appears incremental as it builds on existing primal-dual coordinate methods.
The paper analyzes the computational complexity of the PURE-CD algorithm for convex-concave min-max problems with bilinear coupling, showing that its complexity bounds match or improve upon the best-known results for both dense and sparse strongly-convex-strongly-concave problems.
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.