On the Complexity of a Practical Primal-Dual Coordinate Method

The various methods that have been proposed for (1.1) have favorable complexity guarantees in certain special cases. The plethora of methods and results makes it difficult for both theoreticians and practitioners to choose the method best suited to particular instances of (1.1). In this paper, we focus on improving the theory for an existing method, the PURE-CD algorithm described in [2]. We show that this method achieves or improves best-known complexity results for interesting special cases of (1.1). The state-of-the-art results are currently dispersed around different methods. 1