An official website of the United States government
In distributed machine learning, where agents collaboratively learn from diverse private data sets, there is a fundamental tension between consensus and optimality . In this paper, we build on recent algorithmic progresses in distributed deep learning to explore various consensus-optimality trade-offs over a fixed communication topology. First, we propose the incremental consensus -based distributed stochastic gradient descent (i-CDSGD) algorithm, which involves multiple consensus steps (where each agent communicates information with its neighbors) within each SGD iteration. Second, we propose the generalized consensus -based distributed SGD (g-CDSGD) algorithm that enables us to navigate the full spectrum from complete consensus (all agents agree) to complete disagreement (each agent converges to individual model parameters). We analytically establish convergence of the proposed algorithms for strongly convex and nonconvex objective functions; we also analyze the momentum variants of the algorithms for the strongly convex case. We support our algorithms via numerical experiments, and demonstrate significant improvements over existing methods for collaborative deep learning.
more »
« less
Consensus over evolutionary graphs
We establish average consensus on graphs with dynamic topologies prescribed by evolutionary games among strategic agents. Each agent possesses a private reward function and dynamically decides whether to create new links and/or whether to delete existing ones in a selfish and decentralized fashion, as indicated by a certain randomized mechanism. This model incurs a time-varying and state-dependent graph topology for which traditional consensus analysis is not applicable. We prove asymptotic average consensus almost surely and in mean square for any initial condition and graph topology. In addition, we establish exponential convergence in expectation. Our results are validated via simulation studies on random networks.
more »
« less
- Award ID(s):
- 1717207
- PAR ID:
- 10098522
- Date Published:
- Journal Name:
- Consensus over evolutionary graphs
- Page Range / eLocation ID:
- 2218 to 2223
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
Graphs are the dominant formalism for modeling multi-agent systems. The algebraic connectivity of a graph is particularly important because it provides the convergence rates of consensus algorithms that underlie many multi-agent control and optimization techniques. However, sharing the value of algebraic connectivity can inadvertently reveal sensitive information about the topology of a graph, such as connections in social networks. Therefore, in this work we present a method to release a graph’s algebraic connectivity under a graph-theoretic form of differential privacy, called edge differential privacy. Edge differential privacy obfuscates differences among graphs’ edge sets and thus conceals the absence or presence of sensitive connections therein. We provide privacy with bounded Laplace noise, which improves accuracy relative to conventional unbounded noise. The private algebraic connectivity values are analytically shown to provide accurate estimates of consensus convergence rates, as well as accurate bounds on the diameter of a graph and the mean distance between its nodes. Simulation results confirm the utility of private algebraic connectivity in these contexts.more » « less
-
The growing success of graph signal processing (GSP) approaches relies heavily on prior identification of a graph over which network data admit certain regularity. However, adaptation to increasingly dynamic environments as well as demands for real-time processing of streaming data pose major challenges to this end. In this context, we develop novel algorithms for online network topology inference given streaming observations assumed to be smooth on the sought graph. Unlike existing batch algorithms, our goal is to track the (possibly) time-varying network topology while maintaining the memory and computational costs in check by processing graph signals sequentially-in-time. To recover the graph in an online fashion, we leverage proximal gradient (PG) methods to solve a judicious smoothness-regularized, time-varying optimization problem. Under mild technical conditions, we establish that the online graph learning algorithm converges to within a neighborhood of (i.e., it tracks) the optimal time-varying batch solution. Computer simulations using both synthetic and real financial market data illustrate the effectiveness of the proposed algorithm in adapting to streaming signals to track slowly-varying network connectivity.more » « less
-
Abstract Introduction Digital twins, a form of artificial intelligence, are virtual representations of the physical world. In the past 20 years, digital twins have been utilized to track wind turbines' operations, monitor spacecraft's status, and even create a model of the Earth for climate research. While digital twins hold much promise for the neurocritical care unit, the question remains on how to best establish the rules that govern these models. This model will expand on our group’s existing digital twin model for the treatment of sepsis. Methods The authors of this project collaborated to create a Direct Acyclic Graph (DAG) and an initial series of 20 DELPHI statements, each with six accompanying sub-statements that captured the pathophysiology surrounding the management of acute ischemic strokes in the practice of Neurocritical Care (NCC). Agreement from a panel of 18 experts in the field of NCC was collected through a 7-point Likert scale with consensus defined a-priori by ≥ 80% selection of a 6 (“agree”) or 7 (“strongly agree”). The endpoint of the study was defined as the completion of three separate rounds of DELPHI consensus. DELPHI statements that had met consensus would not be included in subsequent rounds of DELPHI consensus. The authors refined DELPHI statements that did not reach consensus with the guidance of de-identified expert comments for subsequent rounds of DELPHI. All DELPHI statements that reached consensus by the end of three rounds of DELPHI consensus would go on to be used to inform the construction of the digital twin model. Results After the completion of three rounds of DELPHI, 93 (77.5%) statements reached consensus, 11 (9.2%) statements were excluded, and 16 (13.3%) statements did not reach a consensus of the original 120 DELPHI statements. Conclusion This descriptive study demonstrates the use of the DELPHI process to generate consensus among experts and establish a set of rules for the development of a digital twin model for use in the neurologic ICU. Compared to associative models of AI, which develop rules based on finding associations in datasets, digital twin AI created by the DELPHI process are easily interpretable models based on a current understanding of underlying physiology.more » « less
-
The effective resistance between a pair of nodes in a weighted undirected graph is defined as the potential difference induced between them when a unit current is injected at the first node and extracted at the second node, treating edge weights as the conductance values of edges. The effective resistance is a key quantity of interest in many applications and fields including solving linear systems, Markov Chains and continuous-time averaging networks. We develop an efficient linearly convergent distributed algorithm for computing effective resistances and demonstrate its performance through numerical studies. We also apply our algorithm to the consensus problem where the aim is to compute the average of node values in a distributed manner. We show that the distributed algorithm we developed for effective resistances can be used to accelerate the convergence of the classical consensus iterations considerably by a factor depending on the network structure.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Conference Paper:
- https://doi.org/10.23919/ECC.2018.8550392
