Distributed Saddle-Point Problems Under Similarity

Abstract

We study solution methods for (strongly-)convex-(strongly)-concave Saddle-Point Problems (SPPs) over networks of two type - master/workers (thus centralized) architectures and meshed (thus 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 the SPP. We show that a given suboptimality $\epsilon >0$ is achieved over master/workers networks in $\Omega (\Delta \cdot \delta /\mu \cdot \log (1/\epsilon ))$ rounds of communications, where $\delta >0$ measures the degree of similarity of the local functions, $\mu$ is their strong convexity constant, and $\Delta$ is the diameter of the network. The lower communication complexity bound over meshed networks reads $\Omega (1/\sqrt{\rho }\cdot \delta /\mu \cdot \log (1/\epsilon ))$, where $\rho$ is the (normalized) eigengap of the gossip matrix used for the communication between neighbouring nodes. We then propose algorithms matching the lower bounds over either types of networks (up to log-factors). We assess the effectiveness of the proposed algorithms on a robust logistic regression problem.

arXiv commentAppears in: Advances in Neural Information Processing Systems 34 (NeurIPS 2021). Minor modifications with respect to the NeurIPS version. 35 pages, 3 algorithms, 4 figures, 1 table

References in corpus (12)

• Towards Deep Learning Models Resistant to Adversarial Attacks
• Communication Efficient Distributed Optimization using an Approximate Newton-type Method
• Optimal algorithms for smooth and strongly convex distributed optimization in networks
• Distributionally Robust Logistic Regression
• Communication Complexity of Distributed Convex Learning and Optimization
• AIDE: Fast and Communication Efficient Distributed Optimization
• A Decentralized Parallel Algorithm for Training Generative Adversarial Nets
• Multi-consensus Decentralized Accelerated Gradient Descent
• GIANT: Globally Improved Approximate Newton Method for Distributed Optimization
• Efficiently Solving MDPs with Stochastic Mirror Descent
• A Decentralized Proximal Point-type Method for Saddle Point Problems
• On Convergence of Distributed Approximate Newton Methods: Globalization, Sharper Bounds and Beyond

Cited by in corpus (5)

• Recent theoretical advances in decentralized distributed convex optimization
• Near-Optimal Decentralized Algorithms for Saddle Point Problems over Time-Varying Networks
• Local Methods with Adaptivity via Scaling
• Accelerated Stochastic ExtraGradient: Mixing Hessian and Gradient Similarity to Reduce Communication in Distributed and Federated Learning
• Local SGD for Near-Quadratic Problems: Improving Convergence under Unconstrained Noise Conditions