Decentralized Multi-Task Stochastic Optimization With Compressed Communications

• URL: http://arxiv.org/abs/2112.12373v1
• Date: Thu, 23 Dec 2021 05:54:42 GMT
• Title: Decentralized Multi-Task Stochastic Optimization With Compressed Communications
• Authors: Navjot Singh, Xuanyu Cao, Suhas Diggavi, Tamer Basar
• Abstract summary: The paper develops algorithms and obtains performance bounds for two different models of local information availability at the nodes. We show that deviation from the global minimum value and violations of the constraints are upper-bounded by $mathcalO(T-frac12)$ and $mathcalO(T-frac14)$.
• Score: 22.31884634659446
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We consider a multi-agent network where each node has a stochastic (local) cost function that depends on the decision variable of that node and a random variable, and further the decision variables of neighboring nodes are pairwise constrained. There is an aggregate objective function for the network, composed additively of the expected values of the local cost functions at the nodes, and the overall goal of the network is to obtain the minimizing solution to this aggregate objective function subject to all the pairwise constraints. This is to be achieved at the node level using decentralized information and local computation, with exchanges of only compressed information allowed by neighboring nodes. The paper develops algorithms and obtains performance bounds for two different models of local information availability at the nodes: (i) sample feedback, where each node has direct access to samples of the local random variable to evaluate its local cost, and (ii) bandit feedback, where samples of the random variables are not available, but only the values of the local cost functions at two random points close to the decision are available to each node. For both models, with compressed communication between neighbors, we have developed decentralized saddle-point algorithms that deliver performances no different (in order sense) from those without communication compression; specifically, we show that deviation from the global minimum value and violations of the constraints are upper-bounded by $\mathcal{O}(T^{-\frac{1}{2}})$ and $\mathcal{O}(T^{-\frac{1}{4}})$, respectively, where $T$ is the number of iterations. Numerical examples provided in the paper corroborate these bounds and demonstrate the communication efficiency of the proposed method.

Related papers

• Decentralized Multi-Task Online Convex Optimization Under Random Link Failures [5.513958040574729]
  We develop a robust decentralized saddle-point algorithm against random link failures with heterogeneous probabilities. We extend our algorithm and analysis to the two-point bandit feedback scenario.
  arXiv  Detail & Related papers  (2024-01-04T00:57:33Z)
• Online Centralized Non-parametric Change-point Detection via Graph-based Likelihood-ratio Estimation [77.81487285123147]
  Consider each node of a graph to be generating a data stream that is synchronized and observed at near real-time. At a change-point $tau$, a change occurs at a subset of nodes $C$, which affects the probability distribution of their associated node streams. We propose a novel kernel-based method to both detect $tau$ and localize $C$, based on the direct estimation of the likelihood-ratio between the post-change and the pre-change distributions of the node streams.
  arXiv  Detail & Related papers  (2023-01-08T10:15:24Z)
• Pick your Neighbor: Local Gauss-Southwell Rule for Fast Asynchronous Decentralized Optimization [37.85806148420504]
  In decentralized optimization environments, each agent $i$ in a network of $n$ optimization nodes possesses a private function $f_i$. We introduce an optimization-aware selection rule that chooses the neighbor with the highest dual cost improvement. We show that the proposed set-wise GS rule achieves a speedup by a factor of up to the maximum degree in the network.
  arXiv  Detail & Related papers  (2022-07-15T15:37:03Z)
• Push--Pull with Device Sampling [8.344476599818826]
  We consider decentralized optimization problems in which a number of agents collaborate to minimize the average of their local functions by exchanging over an underlying communication graph. We propose an algorithm that combines gradient tracking and variance reduction over the entire network. Our theoretical analysis shows that the algorithm converges linearly, when the local objective functions are strongly convex.
  arXiv  Detail & Related papers  (2022-06-08T18:18:18Z)
• Neural Inverse Kinematics [72.85330210991508]
  Inverse kinematic (IK) methods recover the parameters of the joints, given the desired position of selected elements in the kinematic chain. We propose a neural IK method that employs the hierarchical structure of the problem to sequentially sample valid joint angles conditioned on the desired position.
  arXiv  Detail & Related papers  (2022-05-22T14:44:07Z)
• Acceleration in Distributed Optimization Under Similarity [72.54787082152278]
  We study distributed (strongly convex) optimization problems over a network of agents, with no centralized nodes. An $varepsilon$-solution is achieved in $tildemathcalrhoObig(sqrtfracbeta/mu (1-)log1/varepsilonbig)$ number of communications steps. This rate matches (up to poly-log factors) for the first time lower complexity communication bounds of distributed gossip-algorithms applied to the class of problems of interest.
  arXiv  Detail & Related papers  (2021-10-24T04:03:00Z)
• Two-Bit Aggregation for Communication Efficient and Differentially Private Federated Learning [79.66767935077925]
  In federated learning (FL), a machine learning model is trained on multiple nodes in a decentralized manner, while keeping the data local and not shared with other nodes. The information sent from the nodes to the server may reveal some details about each node's local data, thus raising privacy concerns. A novel two-bit aggregation algorithm is proposed with guaranteed differential privacy and reduced uplink communication overhead.
  arXiv  Detail & Related papers  (2021-10-06T19:03:58Z)
• STEM: A Stochastic Two-Sided Momentum Algorithm Achieving Near-Optimal Sample and Communication Complexities for Federated Learning [58.6792963686231]
  Federated Learning (FL) refers to the paradigm where multiple worker nodes (WNs) build a joint model by using local data. It is not clear how to choose the WNs' minimum update directions, the first minibatch sizes, and the local update frequency. We show that there is a trade-off curve between local update frequencies and local mini sizes, on which the above complexities can be maintained.
  arXiv  Detail & Related papers  (2021-06-19T06:13:45Z)
• A hybrid variance-reduced method for decentralized stochastic non-convex optimization [15.447966950703947]
  textttGTHSGD algorithm specialized local hybrid gradient implements the network to track the global gradient. textttGTHSGD achieves a network complexity of$O(n-1)$ when the required error tolerance$epsilon$ is small enough.
  arXiv  Detail & Related papers  (2021-02-12T20:13:05Z)
• Coded Stochastic ADMM for Decentralized Consensus Optimization with Edge Computing [113.52575069030192]
  Big data, including applications with high security requirements, are often collected and stored on multiple heterogeneous devices, such as mobile devices, drones and vehicles. Due to the limitations of communication costs and security requirements, it is of paramount importance to extract information in a decentralized manner instead of aggregating data to a fusion center. We consider the problem of learning model parameters in a multi-agent system with data locally processed via distributed edge nodes. A class of mini-batch alternating direction method of multipliers (ADMM) algorithms is explored to develop the distributed learning model.
  arXiv  Detail & Related papers  (2020-10-02T10:41:59Z)
• Fully Asynchronous Policy Evaluation in Distributed Reinforcement Learning over Networks [14.636457985379746]
  This paper proposes a emphfully asynchronous scheme for the policy evaluation problem of distributed reinforcement learning (DisRL) over directed peer-to-peer networks. Without waiting for any other node of the network, each node can locally update its value function at any time by using (possibly delayed) information from its neighbors.
  arXiv  Detail & Related papers  (2020-03-01T08:12:08Z)

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.