Distributed Saddle-Point Problems Under Similarity

We study solution methods for saddle point problems over networks of two type: master/workers (centralized) architectures and meshed (decentralized) networks. The local functions at each node are assumed to be similar, due to statistical data similarity or otherwise. We establish lower complexity bounds for a fairly general class of algorithms solving saddle point problems. We show that in such a setup, the number of communications can be significantly reduced and in some cases does not depend on the properties of the functions at all. We then propose optimal algorithms matching the lower bounds over either types of networks.