Research map / Optimization / Distributed and compressed
Communication-Efficient Gradient Descent-Accent Methods for Distributed Variational Inequalities: Unified Analysis and Local Updates
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Gives a unified analysis of local/communication-efficient gradient descent-ascent methods (ProxSkip-VIP and its federated variants) for distributed non-monotone variational inequalities, achieving communication acceleration over local GDA/SGDA without bounded heterogeneity.
Problem
Communication-efficient local training for distributed/federated variational inequality problems (VIPs) and minimax optimization on heterogeneous data, where existing local GDA/SGDA methods lack communication acceleration and rely on bounded heterogeneity/variance.
Approach
Adapts the ProxSkip randomized prox-skipping with a control variate to general regularized VIPs under a general stochastic estimator assumption (covering SGDA, GDA, and loopless SVRG), and applies it to the consensus reformulation so local steps replace most communication rounds.
Key results
- ProxSkip-(S)GDA-FL achieves communication complexity O(sqrt(kappa) ln(1/eps)) versus O(kappa^2 ln(1/eps)) for vanilla GDA in the deterministic strongly monotone smooth setting, per the paper's claims.
- ProxSkip-L-SVRGDA-FL achieves iteration complexity O(hat-ell/mu ln(1/eps)) and communication complexity O(sqrt(hat-ell/mu) ln(1/eps)) in the finite-sum setting.
- In experiments on quadratic games and robust least squares, the proposed methods reach the solution in fewer communication rounds than Local SGDA/GDA and Local EG variants, with the variance-reduced variant converging linearly to the exact solution.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use ProxSkip communication skipping instead of communication every iteration | GDA/SGDA for federated minimax · Strongly-convex-strongly-concave federated minimax | communication complexity: \mathcal{O}\autopar{\max\autobigpar{\kappa^2, \frac{\sigma_*^2}{\mu^2\eps}}\ln\frac{1}{\eps}} -> \mathcal{O}\autopar{\sq | Helped |
| Add loopless SVRG variance reduction | ProxSkip-GDA/SGDA-FL · Strongly-convex-strongly-concave federated minimax | communication complexity: \mathcal{O}\autopar{\sqrt{\max\autobigpar{\kappa^2, \frac{\sigma_*^2}{\mu^2\epsilon}}}\ln\frac{1}{\eps}} -> \mathcal{O}\ | Helped |
| Use ProxSkip-L-SVRGDA-FL instead of Local (S)GDA | Federated minimax methods · Strongly-monotone quadratic games | communication rounds to convergence | Helped |
| Use ProxSkip-GDA/SGDA-FL instead of Local EG or Local GDA | Federated minimax methods · Robust Least Square (California Housing) | communication rounds to convergence | Helped |
| Use ProxSkip-L-SVRGDA-FL | Federated minimax methods · Strongly-monotone quadratic games | convergence to exact solution | Helped |
| Use ProxSkip-SGDA-FL rather than Local SGDA | Federated minimax optimization · Federated minimax problems | communication complexity | Helped |
| Use ProxSkip-L-SVRGDA-FL rather than existing FL algorithms | Federated minimax optimization · Federated minimax problems | iteration and communication complexities | Helped |
Surprising findings
- Local EG with its current analysis converges only to a neighborhood even in the deterministic setting due to bounded heterogeneity requirements.
Limitations
- Analysis assumes quasi-strong monotonicity and star-cocoercivity, and unbiased estimators; the stochastic analysis uses expected co-coercivity or a specific finite-sum assumption.
- Experiments are small-scale synthetic quadratic games and a single robust least squares dataset, with no large-scale federated learning evaluation.
Experimental setup
Datasets: California Housing (scikit-learn)
Benchmarks: strongly-monotone quadratic games robust least squares (California Housing)
Metrics: relative error ||x_k - x*||^2 / ||x_0 - x*||^2 versus commun
Baselines: Local SGDA Local SEG FedGDA-GT GDA/SGDA (distributed) Extragradient
Builds on: ProxSkip Local SGDA L-SVRG expected co-coercivity analysis of SGDA
Closest papers by meaning
- Similarity, Compression and Local Steps: Three Pillars of Efficient Communications for Distributed Variational Inequalities (NeurIPS 2023 · similarity 0.90)
- Distributed Methods with Compressed Communication for Solving Variational Inequalities, with Theoretical Guarantees (NeurIPS 2022 · similarity 0.89)
- Accelerated Dual Method for Distributed Optimization: An Inexact-Gradient View of Local Updates (ICML 2026 · similarity 0.89)
- Faster Rates For Federated Variational Inequalities (NeurIPS 2026 · similarity 0.89)
- Federated Optimization with Doubly Regularized Drift Correction (ICML 2024 · similarity 0.88)
- SILVER: Single-loop variance reduction and application to federated learning (ICML 2024 · similarity 0.87)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.