An official website of the United States government
This papers studies multi-agent (convex and nonconvex) optimization over static digraphs. We propose a general distributed asynchronous algorithmic framework whereby i) agents can update their local variables as well as communicate with their neighbors at any time, without any form of coordination; and ii) they can perform their local computations using (possibly) delayed, out-of-sync information from their neighbors. Delays need not be known to the agents or obey any specific profile, and can also be time-varying (but bounded). The algorithm builds on a tracking mechanism that is robust against asynchrony (in the above sense), whose goal is to estimate locally the sum of agents’ gradients. When applied to strongly convex functions, we prove that it converges at an R-linear (geometric) rate as long as the step-size is sufficiently small. A sublinear convergence rate is proved, when nonconvex problems and/or diminishing, uncoordinated step-sizes are employed. To the best of our knowledge, this is the first distributed algorithm with provable geometric convergence rate in such a general asynchonous setting.
more »
« less
Distributed Optimization Over Time-Varying Graphs With Imperfect Sharing of Information
We study strongly convex distributed optimization problems where a set of agents are interested in solving a separable optimization problem collaboratively. In this article, we propose and study a two-time-scale decentralized gradient descent algorithm for a broad class of lossy sharing of information over time-varying graphs. One time-scale fades out the (lossy) incoming information from neighboring agents, and one time-scale regulates the local loss functions' gradients. We show that assuming a proper choice of step-size sequences, certain connectivity conditions, and bounded gradients along the trajectory of the dynamics, the agents' estimates converge to the optimal solution with the rate of O(T^{−1/2}) . We also provide novel tools to study distributed optimization with diminishing averaging weights over time-varying graphs.
more »
« less
- Award ID(s):
- 1749981
- PAR ID:
- 10427586
- Date Published:
- Journal Name:
- IEEE Transactions on Automatic Control
- Volume:
- 68
- Issue:
- 7
- ISSN:
- 0018-9286
- Page Range / eLocation ID:
- 1 to 8
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
We consider the distributed optimization problem, where a group of agents work together to optimize a common objective by communicating with neighboring agents and performing local computations. For a given algorithm, we use tools from robust control to systematically analyze the performance in the case where the communication network is time-varying. In particular, we assume only that the network is jointly connected over a finite time horizon (commonly referred to as B-connectivity), which does not require connectivity at each time instant. When applied to the distributed algorithm DIGing, our bounds are orders of magnitude tighter than those available in the literature.more » « less
-
Summary This paper introduces a new class of feedback‐based data‐driven extremum seeking algorithms for the solution of model‐free optimization problems in smooth continuous‐time dynamical systems. The novelty of the algorithms lies on the incorporation of memory to store recorded data that enables the use of information‐rich datasets during the optimization process, and allows to dispense with the time‐varying dither excitation signal needed by standard extremum seeking algorithms that rely on a persistence of excitation (PE) condition. The model‐free optimization dynamics are developed for single‐agent systems, as well as for multi‐agent systems with communication graphs that allow agents to share their state information while preserving the privacy of their individual data. In both cases, sufficient richness conditions on the recorded data, as well as suitable optimization dynamics modeled by ordinary differential equations are characterized in order to guarantee convergence to a neighborhood of the solution of the extremum seeking problems. The performance of the algorithms is illustrated via different numerical examples in the context of source‐seeking problems in multivehicle systems.more » « less
-
We study distributed estimation and learning problems in a networked environment where agents exchange information to estimate unknown statistical properties of random variables from their privately observed samples. The agents can collectively estimate the unknown quantities by exchanging information about their private observations, but they also face privacy risks. Our novel algorithms extend the existing distributed estimation literature and enable the participating agents to estimate a complete sufficient statistic from private signals acquired offline or online over time and to preserve the privacy of their signals and network neighborhoods. This is achieved through linear aggregation schemes with adjusted randomization schemes that add noise to the exchanged estimates subject to differential privacy (DP) constraints, both in an offline and online manner. We provide convergence rate analysis and tight finite-time convergence bounds. We show that the noise that minimizes the convergence time to the best estimates is the Laplace noise, with parameters corresponding to each agent’s sensitivity to their signal and network characteristics. Our algorithms are amenable to dynamic topologies and balancing privacy and accuracy trade-offs. Finally, to supplement and validate our theoretical results, we run experiments on real-world data from the US Power Grid Network and electric consumption data from German Households to estimate the average power consumption of power stations and households under all privacy regimes and show that our method outperforms existing first-order privacy-aware distributed optimization methods.more » « less
-
In science and engineering, we often deal with signals that are acquired from time-varying systems represented by dynamic graphs. We observe these signals, and the interest is in finding the time-varying topology of the graphs. We propose two Bayesian methods for estimating these topologies without assuming any specific functional relationships among the signals on the graphs. The two methods exploit Gaussian processes, where the first method uses the length scale of the kernel and relies on variational inference for optimization, and the second method is based on derivatives of the functions and Monte Carlo sampling. Both methods estimate the time-varying topologies of the graphs sequentially. We provide numerical tests that show the performance of the methods in two settings.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Journal Article:
- https://doi.org/10.1109/TAC.2022.3207866
