Similarity, Compression and Local Steps: Three Pillars of Efficient Communications for Distributed Variational Inequalities

• URL: http://arxiv.org/abs/2302.07615v2
• Date: Sat, 30 Mar 2024 15:00:07 GMT
• Title: Similarity, Compression and Local Steps: Three Pillars of Efficient Communications for Distributed Variational Inequalities
• Authors: Aleksandr Beznosikov, Martin Takáč, Alexander Gasnikov,
• Abstract summary: Variational inequalities are used in various applications ranging from equilibrium search to adversarial learning. Most distributed approaches have a bottleneck - the cost of communications. The three main techniques to reduce the total number of communication rounds and the cost of one such round are the similarity of local functions, compression of transmitted information, and local updates. The methods presented in this paper have the best theoretical guarantees of communication complexity and are significantly ahead of other methods for distributed variational inequalities.
• Score: 91.12425544503395
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Variational inequalities are a broad and flexible class of problems that includes minimization, saddle point, and fixed point problems as special cases. Therefore, variational inequalities are used in various applications ranging from equilibrium search to adversarial learning. With the increasing size of data and models, today's instances demand parallel and distributed computing for real-world machine learning problems, most of which can be represented as variational inequalities. Meanwhile, most distributed approaches have a significant bottleneck - the cost of communications. The three main techniques to reduce the total number of communication rounds and the cost of one such round are the similarity of local functions, compression of transmitted information, and local updates. In this paper, we combine all these approaches. Such a triple synergy did not exist before for variational inequalities and saddle problems, nor even for minimization problems. The methods presented in this paper have the best theoretical guarantees of communication complexity and are significantly ahead of other methods for distributed variational inequalities. The theoretical results are confirmed by adversarial learning experiments on synthetic and real datasets.

Related papers

• Communication-Efficient Gradient Descent-Accent Methods for Distributed Variational Inequalities: Unified Analysis and Local Updates [28.700663352789395]
  We provide a unified convergence analysis of communication-efficient local training methods for distributed variational inequality problems (VIPs) Our approach is based on a general key assumption on the estimates that allows us to propose and analyze several novel local training algorithms. We present the first local descent-accent algorithms with provable improved communication complexity for solving distributed variational inequalities on heterogeneous data.
  arXiv  Detail & Related papers  (2023-06-08T10:58:46Z)
• SARAH-based Variance-reduced Algorithm for Stochastic Finite-sum Cocoercive Variational Inequalities [137.6408511310322]
  We consider the problem of finite-sum cocoercive variational inequalities. For strongly monotone problems it is possible to achieve linear convergence to a solution using this method.
  arXiv  Detail & Related papers  (2022-10-12T08:04:48Z)
• Compression and Data Similarity: Combination of Two Techniques for Communication-Efficient Solving of Distributed Variational Inequalities [137.6408511310322]
  In this paper we consider a combination of two popular approaches: compression and data similarity. We show that this synergy can be more effective than each of the approaches separately in solving distributed smooth strongly monotonic variational inequalities.
  arXiv  Detail & Related papers  (2022-06-19T16:38:56Z)
• Distributed Newton-Type Methods with Communication Compression and Bernoulli Aggregation [11.870393751095083]
  We study ommunication compression and aggregation mechanisms for curvature information. New 3PC mechanisms, such as adaptive thresholding and Bernoulli aggregation, require reduced communication and occasional Hessian computations. For all our methods, we derive fast condition-number-independent local linear and/or superlinear convergence rates.
  arXiv  Detail & Related papers  (2022-06-07T21:12:21Z)
• Optimal Algorithms for Decentralized Stochastic Variational Inequalities [113.43047601775453]
  This work concentrates on the decentralized setting, which is increasingly important but not well understood. We present lower bounds for both communication and local iterations and construct optimal algorithms that match these lower bounds. Our algorithms are the best among the available not only in the decentralized case, but also in the deterministic and non-distributed literature.
  arXiv  Detail & Related papers  (2022-02-06T13:14:02Z)
• Distributed Methods with Compressed Communication for Solving Variational Inequalities, with Theoretical Guarantees [115.08148491584997]
  We present the first theoretically grounded distributed methods for solving variational inequalities and saddle point problems using compressed communication: MASHA1 and MASHA2. New algorithms support bidirectional compressions, and also can be modified for setting with batches and for federated learning with partial participation of clients.
  arXiv  Detail & Related papers  (2021-10-07T10:04:32Z)
• Fundamental Limits and Tradeoffs in Invariant Representation Learning [99.2368462915979]
  Many machine learning applications involve learning representations that achieve two competing goals. Minimax game-theoretic formulation represents a fundamental tradeoff between accuracy and invariance. We provide an information-theoretic analysis of this general and important problem under both classification and regression settings.
  arXiv  Detail & Related papers  (2020-12-19T15:24:04Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.