An official website of the United States government
We consider the problem of decentralized sequential active hypothesis testing (DSAHT), where two transmitting agents, each possessing a private message, are actively helping a third agent–and each other–to learn the message pair over a discrete memoryless multiple access channel (DM-MAC). The third agent (receiver) observes the noisy channel output, which is also available to the transmitting agents via noiseless feedback. We formulate this problem as a decentralized dynamic team, show that optimal transmission policies have a time-invariant domain, and characterize the solution through a dynamic program. Several alternative formulations are discussed involving time-homogenous cost functions and/or variable-length codes, resulting in solutions described through fixed-point, Bellman-type equations. Subsequently, we make connections with the problem of simplifying the multi-letter capacity expressions for the noiseless feedback capacity of the DM-MAC. We show that restricting attention to distributions induced by optimal transmission schemes for the DSAHT problem, without loss of optimality, transforms the capacity expression, so that it can be thought of as the average reward received by an appropriately defined stochastic dynamical system with time-invariant state space.
more »
« less
Agent-level optimal LQG control of dynamically decoupled systems with processing delays
We consider the problem of controlling a set of dynamically decoupled plants where the plants' subcontrollers communicate with each other according to a fixed and known network topology. We assume the communication to be instantaneous but there is a fixed processing delay associated with incoming transmissions. We provide explicit closed-form expressions for the optimal decentralized controller under these communication constraints and using standard LQG assumptions for the plants and cost function. Although this problem is convex, it is challenging due to the irrationality of continuous-time delays and the decentralized information-sharing pattern. We show that the optimal subcontrollers each have an observer-regulator architecture containing LTI and FIR blocks and we characterize the signals that subcontrollers should transmit to each other across the network.
more »
« less
- Award ID(s):
- 1710892
- PAR ID:
- 10198822
- Date Published:
- Journal Name:
- IEEE Conference on Decision and Control
- Page Range / eLocation ID:
- 5980 to 5985
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
This paper addresses the problem of decentralized learning in the presence of data poisoning attacks. In this problem, we consider a collection of nodes connected through a network, each equipped with a local function. The objective is to compute the global minimizer of the aggregated local functions, in a decentralized manner, i.e., each node can only use its local function and data exchanged with nodes it is connected to. Moreover, each node is to agree on the said minimizer despite an adversary that can arbitrarily change the local functions of a fraction of the nodes. This problem setting has applications in robust learning, where nodes in a network are collectively training a model that minimizes the empirical loss with possibly attacked local data sets. In this paper, we propose a novel decentralized learning algorithm that enables all nodes to reach consensus on the optimal model, in the absence of attacks, and approximate consensus in the presence of data poisoning attacks.more » « less
-
We consider a multi-agent linear quadratic optimal control problem. Due to communication constraints, the agents are required to quantize their local state measurements before communicating them to the rest of the team, thus resulting in a decentralized information structure. The optimal controllers are to be synthesized under this decentralized and quantized information structure. The agents are given a set of quantizers with varying quantization resolutions—higher resolution incurs higher communication cost and vice versa. The team must optimally select the quantizer to prioritize agents with ‘highquality’ information for optimizing the control performance under communication constraints. We show that there exist a sepatation between the optimal solution to the control problem and the choice of the optimal quantizer. We show that the optimal controllers are linear and the optimal selection of the quantizers can be determined by solving a linear program.more » « less
-
null (Ed.)In this paper, we study communication-efficient decentralized training of large-scale machine learning models over a network. We propose and analyze SQuARM-SGD, a decentralized training algorithm, employing momentum and compressed communication between nodes regulated by a locally computable triggering rule. In SQuARM-SGD, each node performs a fixed number of local SGD (stochastic gradient descent) steps using Nesterov's momentum and then sends sparisified and quantized updates to its neighbors only when there is a significant change in its model parameters since the last time communication occurred. We provide convergence guarantees of our algorithm for strongly-convex and non-convex smooth objectives. We believe that ours is the first theoretical analysis for compressed decentralized SGD with momentum updates. We show that SQuARM-SGD converges at rate O(1/nT) for strongly-convex objectives, while for non-convex objectives it converges at rate O(1/√nT), thus matching the convergence rate of \emphvanilla distributed SGD in both these settings. We corroborate our theoretical understanding with experiments and compare the performance of our algorithm with the state-of-the-art, showing that without sacrificing much on the accuracy, SQuARM-SGD converges at a similar rate while saving significantly in total communicated bits.more » « less
-
Abstract In recent years, three-dimensional (3D) construction printing has emerged as a viable alternative to conventional construction methods. Particularly promising for large scale construction are collective printing systems consisting of multiple mobile 3D printers. However, the design of these systems typically relies on the assumption of continuous communication between the printers, which is unrealistic in dynamically changing construction environments. As a first step toward decentralized collective 3D printing, we explore an active sensing framework allowing individual agents to reconstruct the shape of the structure, toward assessing other agents' progress in the absence of direct communication. In this vein, the shape of the structure is discretized as a 2D lattice embodying its topology, such that the problem is equivalent to the inference of a network. We leverage environmental modifications introduced by each agent through the printing of new layers to track the structure evolution. We demonstrate the validity of a sequential approach based on system identification through numerical simulations. Our work paves the way to decentralized collective 3D construction printing, as well as other applications in collective behavior that rely on the physical medium to transfer information among agents.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Conference Paper:
- https://doi.org/10.1109/CDC42340.2020.9303979
