More Like this

1. Distributed Stochastic Optimization with Gradient Tracking over Time- Varying Directed Networks

   https://doi.org/10.1109/IEEECONF59524.2023.10477004  

   Anh_Nguyen, Duong Thuy; Nguyen, Duong Tung; Nedic, Angelia (October 2023, IEEE)

   We study a distributed method called SAB–TV, which employs gradient tracking to collaboratively minimize the strongly-convex sum of smooth local cost functions for networked agents communicating over a time-varying directed graph. Each agent, assumed to have access to a stochastic first order oracle for obtaining an unbiased estimate of the gradient of its local cost function, maintains an auxiliary variable to asymptotically track the stochastic gradient of the global cost. The optimal decision and gradient tracking are updated over time through limited information exchange with local neighbors using row- and column-stochastic weights, guaranteeing both consensus and optimality. With a sufficiently small constant step-size, we demonstrate that, in expectation, SAB–TV converges linearly to a neighborhood of the optimal solution. Numerical simulations illustrate the effectiveness of the proposed algorithm. 

   more » « less
2. Dynamic size counting in population protocols

   David Doty and Mahsa Eftekhari (January 2022, SAND 2022: 1st Symposium on Algorithmic Foundations of Dynamic Networks)

   James Aspnes and Othon Michail (Ed.)

   The population protocol model describes a network of anonymous agents that interact asynchronously in pairs chosen at random. Each agent starts in the same initial state s. We introduce the *dynamic size counting* problem: approximately counting the number of agents in the presence of an adversary who at any time can remove any number of agents or add any number of new agents in state s. A valid solution requires that after each addition/removal event, resulting in population size n, with high probability each agent "quickly" computes the same constant-factor estimate of the value log2n (how quickly is called the *convergence* time), which remains the output of every agent for as long as possible (the *holding* time). Since the adversary can remove agents, the holding time is necessarily finite: even after the adversary stops altering the population, it is impossible to *stabilize* to an output that never again changes. We first show that a protocol solves the dynamic size counting problem if and only if it solves the *loosely-stabilizing counting* problem: that of estimating logn in a *fixed-size* population, but where the adversary can initialize each agent in an arbitrary state, with the same convergence time and holding time. We then show a protocol solving the loosely-stabilizing counting problem with the following guarantees: if the population size is n, M is the largest initial estimate of logn, and s is the maximum integer initially stored in any field of the agents' memory, we have expected convergence time O(logn+logM), expected polynomial holding time, and expected memory usage of O(log2(s)+(loglogn)2) bits. Interpreted as a dynamic size counting protocol, when changing from population size nprev to nnext, the convergence time is O(lognnext+loglognprev). 

   more » « less
3. An Asynchronous Multi-Agent Actor-Critic Algorithm for Distributed Reinforcement Learning

   Lin, Yixuan; Luo, Yuehan; Zhang, Kaiqing; Yang, Zhuoran; Wang, Zhaoran; Basar, Tamer; Sandhu, Romeil; Liu, Ji (January 2019, NeurIPS Optimization Foundations for Reinforcement Learning Workshop)

   This paper studies a distributed reinforcement learning problem in which a network of multiple agents aim to cooperatively maximize the globally averaged return through communication with only local neighbors. An asynchronous multi-agent actor-critic algorithm is proposed for possibly unidirectional communication relationships depicted by a directed graph. Each agent independently updates its variables at “event times” determined by its own clock. It is not assumed that the agents’ clocks are synchronized or that the event times are evenly spaced. It is shown that the algorithm can solve the problem for any strongly connected graph in the presence of communication and computation delays. 

   more » « less
4. Distributed Q-Learning with State Tracking for Multi-agent Networked Control

   Wang, Hang; Lin, Sen; Jafarkhani, Hamid; Zhang, Junshan (May 2021, AAMAS '21: Proceedings of the 20th International Conference on Autonomous Agents and MultiAgent SystemsMay 2021)

   This paper studies distributed Q-learning for Linear Quadratic Regulator (LQR) in a multi-agent network. The existing results often assume that agents can observe the global system state, which may be infeasible in large-scale systems due to privacy concerns or communication constraints. In this work, we consider a setting with unknown system models and no centralized coordinator. We devise a state tracking (ST) based Q-learning algorithm to design optimal controllers for agents. Specifically, we assume that agents maintain local estimates of the global state based on their local information and communications with neighbors. At each step, every agent updates its local global state estimation, based on which it solves an approximate Q-factor locally through policy iteration. Assuming a decaying injected excitation noise during the policy evaluation, we prove that the local estimation converges to the true global state, and establish the convergence of the proposed distributed ST-based Q-learning algorithm. The experimental studies corroborate our theoretical results by showing that our proposed method achieves comparable performance with the centralized case. 

   more » « less
5. Privacy preservation in a continuous-time static average consensus algorithm over directed graphs

   Rezazadeh, Navid; Kia, Solmaz S. (June 2018, Proceedings of the American Control Conference)

   In this paper, we study the problem of privacy preservation of the continuous-time Laplacian static average consensus algorithm using additive perturbation signals. We consider this problem over a strongly connected and weight-balanced digraph. Starting from a local reference value, in static average consensus algorithm each agent constantly communicates with its neighboring agents to update its local state to compute the average of the reference values across the network. Since every agent transmits its local reference value to its in-neighbors, the reference value of the agents are trivially disclosed. In this paper, we investigate the possibility of preserving the privacy of the reference value of the agents by adding admissible perturbation signals to the local dynamics and the transmitted out signals of the agents. Admissible additive perturbation signals are those signals that do not perturb the final convergence point of the algorithm from the average of the reference values of the agents. Our results show that if an adversarial agent has access to the output of another agent and all the input signals transmitted to that agent, the adversary can discover the private reference value of that agent, regardless of the perturbation signals. Otherwise, the privacy of the agent can be preserved. We demonstrate our results through a numerical example. 

   more » « less