# PRECISION: Decentralized Constrained Min-Max Learning with Low Communication and Sample Complexities

arXiv: https://arxiv.org/abs/2303.02532 · HTML: https://mlsanity.com/paper/2303.02532/

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- Builds on 21 of its 67 references that are in the map.
- First posted on arXiv 5 Mar 2023.

## Builds on (most cited first, 21 of 21)

- [Can Decentralized Algorithms Outperform Centralized Algorithms? A Case Study for Decentralized Parallel Stochastic Gradient Descent](https://mlsanity.com/paper/1705.09056/) (2017)
- [On Gradient Descent Ascent for Nonconvex-Concave Minimax Problems](https://mlsanity.com/paper/1906.00331/) (2019)
- [A Unified Analysis of Extra-gradient and Optimistic Gradient Methods for Saddle Point Problems: Proximal Point Approach](https://mlsanity.com/paper/1901.08511/) (2019)
- [To be Robust or to be Fair: Towards Fairness in Adversarial Training](https://mlsanity.com/paper/2010.06121/) (2020)
- [Network Topology and Communication-Computation Tradeoffs in Decentralized Optimization](https://mlsanity.com/paper/1709.08765/) (2017)
- [Near-Optimal Algorithms for Minimax Optimization](https://mlsanity.com/paper/2002.02417/) (2020)
- [Stochastic Recursive Gradient Descent Ascent for Stochastic Nonconvex-Strongly-Concave Minimax Problems](https://mlsanity.com/paper/2001.03724/) (2020)
- [Collaborative Deep Learning in Fixed Topology Networks](https://mlsanity.com/paper/1706.07880/) (2017)
- [An improved convergence analysis for decentralized online stochastic non-convex optimization](https://mlsanity.com/paper/2008.04195/) (2020)
- [A Decentralized Parallel Algorithm for Training Generative Adversarial Nets](https://mlsanity.com/paper/1910.12999/) (2019)
- [Multi-Agent Reinforcement Learning via Double Averaging Primal-Dual Optimization](https://mlsanity.com/paper/1806.00877/) (2018)
- [R'enyi Fair Inference](https://mlsanity.com/paper/1906.12005/) (2019)
- [Fairness GAN](https://mlsanity.com/paper/1805.09910/) (2018)
- [Single-Timescale Stochastic Nonconvex-Concave Optimization for Smooth Nonlinear TD Learning](https://mlsanity.com/paper/2008.10103/) (2020)
- [Distributed Nonconvex Constrained Optimization over Time-Varying Digraphs](https://mlsanity.com/paper/1809.01106/) (2018)
- [A Decentralized Proximal Point-type Method for Saddle Point Problems](https://mlsanity.com/paper/1910.14380/) (2019)
- [Gradient Free Minimax Optimization: Variance Reduction and Faster Convergence](https://mlsanity.com/paper/2006.09361/) (2020)
- [Dictionary Learning over Distributed Models](https://mlsanity.com/paper/1402.1515/) (2014)
- [Distributed Stochastic Multi-Task Learning with Graph Regularization](https://mlsanity.com/paper/1802.03830/) (2018)
- [Distributed Linear Model Clustering over Networks: A Tree-Based Fused-Lasso ADMM Approach](https://mlsanity.com/paper/1905.11549/) (2019)
- [On the Divergence of Decentralized Non-Convex Optimization](https://mlsanity.com/paper/2006.11662/) (2020)

## Built on by (most cited first, 5 of 5)

- [Solving a Class of Non-Convex Minimax Optimization in Federated Learning](https://mlsanity.com/paper/2310.03613/) (2023)
- [Robust Decentralized Learning with Local Updates and Gradient Tracking](https://mlsanity.com/paper/2405.00965/) (2024)
- [Variance-reduced accelerated methods for decentralized stochastic double-regularized nonconvex strongly-concave minimax problems](https://mlsanity.com/paper/2307.07113/) (2023)
- [Fast Decentralized Gradient Tracking for Federated Minimax Optimization with Local Updates](https://mlsanity.com/paper/2405.04566/) (2024)
- [Decoupled SGDA for Games with Intermittent Strategy Communication](https://mlsanity.com/paper/2501.14652/) (2025)

## Abstract (arXiv)

Recently, min-max optimization problems have received increasing attention due to their wide range of applications in machine learning (ML). However, most existing min-max solution techniques are either single-machine or distributed algorithms coordinated by a central server. In this paper, we focus on the decentralized min-max optimization for learning with domain constraints, where multiple agents collectively solve a nonconvex-strongly-concave min-max saddle point problem without coordination from any server. Decentralized min-max optimization problems with domain constraints underpins many important ML applications, including multi-agent ML fairness assurance, and policy evaluations in multi-agent reinforcement learning. We propose an algorithm called PRECISION (proximal gradient-tracking and stochastic recursive variance reduction) that enjoys a convergence rate of O(1/T), where T is the maximum number of iterations. To further reduce sample complexity, we propose PRECISION^+ with an adaptive batch size technique. We show that the fast O(1/T) convergence of PRECISION and PRECISION^+ to an ε-stationary point imply O(ε-2) communication complexity and O(m√nε-2) sample complexity, where m is the number of agents and n is the size of dataset at each agent. To our knowledge, this is the first work that achieves O(ε-2) in both sample and communication complexities in decentralized min-max learning with domain constraints. Our experiments also corroborate the theoretical results.