A Decentralized Adaptive Momentum Method for Solving a Class of Min-Max Optimization Problems

Abstract

Min-max saddle point games have recently been intensely studied, due to their wide range of applications, including training Generative Adversarial Networks (GANs). However, most of the recent efforts for solving them are limited to special regimes such as convex-concave games. Further, it is customarily assumed that the underlying optimization problem is solved either by a single machine or in the case of multiple machines connected in centralized fashion, wherein each one communicates with a central node. The latter approach becomes challenging, when the underlying communications network has low bandwidth. In addition, privacy considerations may dictate that certain nodes can communicate with a subset of other nodes. Hence, it is of interest to develop methods that solve min-max games in a decentralized manner. To that end, we develop a decentralized adaptive momentum (ADAM)-type algorithm for solving min-max optimization problem under the condition that the objective function satisfies a Minty Variational Inequality condition, which is a generalization to convex-concave case. The proposed method overcomes shortcomings of recent non-adaptive gradient-based decentralized algorithms for min-max optimization problems that do not perform well in practice and require careful tuning. In this paper, we obtain non-asymptotic rates of convergence of the proposed algorithm (coined DADAM${}^3$) for finding a (stochastic) first-order Nash equilibrium point and subsequently evaluate its performance on training GANs. The extensive empirical evaluation shows that DADAM${}^3$ outperforms recently developed methods, including decentralized optimistic stochastic gradient for solving such min-max problems.

References in corpus (38)

• Adam: A Method for Stochastic Optimization
• ADADELTA: An Adaptive Learning Rate Method
• GANs Trained by a Two Time-Scale Update Rule Converge to a Local Nash Equilibrium
• Self-Attention Generative Adversarial Networks
• Conditional Image Synthesis With Auxiliary Classifier GANs
• On the Convergence of Adam and Beyond
• Diffusion Adaptation Strategies for Distributed Optimization and Learning over Networks
• Distributed Optimal Power Flow for Smart Microgrids
• Distributed Learning in Wireless Sensor Networks
• A Note on the Inception Score
• D${}^2$: Decentralized Training over Decentralized Data
• AdaGrad stepsizes: Sharp convergence over nonconvex landscapes
• Distributed Mean Estimation with Limited Communication
• A Unified Analysis of Extra-gradient and Optimistic Gradient Methods for Saddle Point Problems: Proximal Point Approach
• Adaptive Bound Optimization for Online Convex Optimization
• Solving a Class of Non-Convex Min-Max Games Using Iterative First Order Methods
• Hybrid Block Successive Approximation for One-Sided Non-Convex Min-Max Problems: Algorithms and Applications
• Non-convex Min-Max Optimization: Applications, Challenges, and Recent Theoretical Advances
• Optimistic mirror descent in saddle-point problems: Going the extra (gradient) mile
• On the Convergence Proof of AMSGrad and a New Version
• On the Convergence of Adaptive Gradient Methods for Nonconvex Optimization
• What is Local Optimality in Nonconvex-Nonconcave Minimax Optimization?
• An Alternative View: When Does SGD Escape Local Minima?
• Understanding GANs: the LQG Setting
• A Decentralized Parallel Algorithm for Training Generative Adversarial Nets
• Global Convergence and Variance-Reduced Optimization for a Class of Nonconvex-Nonconcave Minimax Problems
• GANs May Have No Nash Equilibria
• SGD Converges to Global Minimum in Deep Learning via Star-convex Path
• Frank-Wolfe Algorithms for Saddle Point Problems
• Towards Better Understanding of Adaptive Gradient Algorithms in Generative Adversarial Nets
• First-order Convergence Theory for Weakly-Convex-Weakly-Concave Min-max Problems
• DADAM: A Consensus-based Distributed Adaptive Gradient Method for Online Optimization
• A Decentralized Proximal Point-type Method for Saddle Point Problems
• UniXGrad: A Universal, Adaptive Algorithm with Optimal Guarantees for Constrained Optimization
• Creative GANs for generating poems, lyrics, and metaphors
• Adaptive First-and Zeroth-order Methods for Weakly Convex Stochastic Optimization Problems
• Efficient Algorithms for Estimating the Parameters of Mixed Linear Regression Models
• Improving Efficiency in Large-Scale Decentralized Distributed Training

Cited by in corpus (1)

• Accelerated Stochastic ExtraGradient: Mixing Hessian and Gradient Similarity to Reduce Communication in Distributed and Federated Learning