Research map / Optimization / Distributed and compressed
Near-Optimal Distributed Minimax Optimization under the Second-Order Similarity
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.
Proposes SVOGS, a variance-reduced optimistic gradient sliding method with mini-batch client sampling for distributed convex-concave minimax problems under second-order similarity, achieving near-optimal communication rounds, communication complexity, and local gradient complexity.
Problem
Distributed convex-concave (and strongly-convex-strongly-concave) minimax optimization with a server and n-1 clients under second-order similarity; prior methods either require full participation (high communication cost) or partial participation (more communication rounds).
Approach
Combines optimistic gradient sliding (server solves quadratically regularized subproblems) with SVRG-style variance-reduced optimistic gradient estimates computed from mini-batch client sampling of size about sqrt(n), so each round costs O(sqrt(n)) communication and gradient calls while keeping rounds at O(delta D^2/eps).
Key results
- SVOGS achieves O(delta D^2/eps) communication rounds and O(n + sqrt(n) delta D^2/eps) communication complexity in the convex-concave case, matching the stated lower bounds up to log factors on local gradient calls.
- For strongly-convex-strongly-concave problems, SVOGS attains O(delta/mu log(1/eps)) communication rounds, nearly tight.
- On robust linear regression with a9a and n=500 nodes, SVOGS outperforms EG, SMMDS, EGS and TPAPP in local gradient complexity and needs fewer rounds than EG and TPAPP.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use mini-batch client sampling and variance reduction with momentum | SVOGS · Convex-concave minimax, expected duality gap | communication complexity: $\fO(n+\sqrt{n}\delta D^2 /\varepsilon)$ vs. full-participation methods' $\fO(n\delta D^2/\varepsilon)$ | Helped |
| Use mini-batch client sampling and variance reduction with momentum | SVOGS · Robust linear regression on a9a | local gradient complexity | Helped |
| Use mini-batch client sampling and variance reduction with momentum | SVOGS · Robust linear regression on a9a | communication rounds | Helped |
| Use mini-batch client sampling and variance reduction with momentum | SVOGS · Robust linear regression on a9a | communication complexity | Helped |
Limitations
- Analysis restricted to convex-concave and strongly-convex-strongly-concave settings; nonconvex case left to future work.
- Gradient-mapping guarantee for convex-concave case relies on regularization and extra log factors; TPAPP comparisons require additional boundedness assumptions.
Experimental setup
Datasets: a9a (LIBSVM)
Benchmarks: a9a robust linear regression minimax
Metrics: communication rounds communication complexity local gradient complexity duality gap
Baselines: EG SMMDS EGS TPAPP OMASHA
Builds on: gradient sliding optimistic gradient descent ascent extra-gradient SMMDS EGS TPAPP
Closest papers by meaning
- Jointly Improving the Sample and Communication Complexities in Decentralized Stochastic Minimax Optimization (AAAI 2024 · similarity 0.89)
- Distributed Online Convex Optimization with Compressed Communication: Optimal Regret and Applications (NeurIPS 2026 · similarity 0.88)
- Scalable Distributed Stochastic Optimization via Bidirectional Compression: Beyond Pessimistic Limits (NeurIPS 2026 · similarity 0.88)
- Towards Faster Decentralized Stochastic Optimization with Communication Compression (ICLR 2025 · similarity 0.88)
- Accelerated Methods with Compressed Communications for Distributed Optimization Problems Under Data Similarity (AAAI 2025 · similarity 0.88)
- Improving the Worst-Case Bidirectional Communication Complexity for Nonconvex Distributed Optimization under Function Similarity (NeurIPS 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.