Near-Optimal Decentralized Algorithms for Saddle Point Problems over Time-Varying Networks
arXiv:2107.05957 · doi:10.1007/978-3-030-91059-4_18
Abstract
Decentralized optimization methods have been in the focus of optimization community due to their scalability, increasing popularity of parallel algorithms and many applications. In this work, we study saddle point problems of sum type, where the summands are held by separate computational entities connected by a network. The network topology may change from time to time, which models real-world network malfunctions. We obtain lower complexity bounds for algorithms in this setup and develop near-optimal methods which meet the lower bounds.
References in corpus (14)
- Communication-Efficient Learning of Deep Networks from Decentralized Data
- Optimal algorithms for smooth and strongly convex distributed optimization in networks
- Distributionally Robust Logistic Regression
- A Unified Theory of Decentralized SGD with Changing Topology and Local Updates
- A Decentralized Parallel Algorithm for Training Generative Adversarial Nets
- Multi-consensus Decentralized Accelerated Gradient Descent
- Efficiently Solving MDPs with Stochastic Mirror Descent
- Optimal Distributed Optimization on Slowly Time-Varying Graphs
- Projected Gradient Method for Decentralized Optimization over Time-Varying Networks
- A Decentralized Proximal Point-type Method for Saddle Point Problems
- ADOM: Accelerated Decentralized Optimization Method for Time-Varying Networks
- Accelerated Gradient Tracking over Time-varying Graphs for Decentralized Optimization
- Distributed Saddle-Point Problems Under Similarity
- Lower Bounds and Optimal Algorithms for Smooth and Strongly Convex Decentralized Optimization Over Time-Varying Networks