Distributed Saddle-Point Problems: Lower Bounds, Near-Optimal and Robust Algorithms
This work addresses the problem of efficient distributed optimization for saddle-point problems, which is crucial for applications like distributed machine learning, but it appears incremental as it builds on existing methods with specific improvements.
The paper tackles distributed optimization of stochastic saddle-point problems by establishing lower bounds for centralized and decentralized methods and proposing a near-optimal federated algorithm called Extra Step Local SGD, achieving theoretical guarantees for strongly convex-strongly concave and non-convex-non-concave cases and demonstrating effectiveness in distributed GAN training.
This paper focuses on the distributed optimization of stochastic saddle point problems. The first part of the paper is devoted to lower bounds for the centralized and decentralized distributed methods for smooth (strongly) convex-(strongly) concave saddle point problems, as well as the near-optimal algorithms by which these bounds are achieved. Next, we present a new federated algorithm for centralized distributed saddle-point problems - Extra Step Local SGD. The theoretical analysis of the new method is carried out for strongly convex-strongly concave and non-convex-non-concave problems. In the experimental part of the paper, we show the effectiveness of our method in practice. In particular, we train GANs in a distributed manner.