Decentralized Concurrent Learning with Coordinated Momentum and Restart

One promising direction to alleviate the slow convergence issue in decision-making algorithms is the incorporation of momentum with dynamic damping, see [3, 10, 11]. For single-agent gradient-based dynamics with momentum, the use of decreasing damping has been shown to play a crucial role in inducing favorable acceleration properties [12, 13, 14, 15]. However, it has also been shown that stability bounds in terms of $\mathcal{KL}$ functions may not exist for such systems unless the damping coefficients are persistently exciting [16], a condition that precludes vanishing coefficients. Furthermore, it is well-known that, without proper tuning, the use of momentum can lead to undesirable oscillations [17]. To address potential instability issues and to eliminate oscillatory behaviors, restart mechanisms that reset the momentum have been developed for single-agent systems using adaptive [17, 18] and periodic policies (usually called “scheduled”) with carefully selected frequencies [13, 19, 20, 17]. Recent works have also investigated the development of similar momentum-based algorithms in multi-agent systems, including distributed continuous-time heavy-ball dynamics with constant damping [21], limiting equations of stochastic recursive algorithms as multi-agent flows with momentum [22], and decision-making algorithms with momentum for high-order multi-agent systems [23, 24, 25]. However, existing approaches have primarily focused on undirected network topologies. Additionally, the incorporation of momentum and restarting mechanisms in decentralized concurrent learning algorithms has remained unexplored. Such algorithms are essential when a network of agents seeks to collaboratively and efficiently learn a common model by sharing local estimates with neighboring agents, without revealing their private data. Applications of these algorithms span various domains, including source seeking in autonomous mobile robots [26], adaptive formation control of robotic teams [27], and cooperative adaptive control [28].

Motivated by the previous background, in this paper we study the synthesis and analysis of decentralized concurrent learning dynamics with momentum and restart for general directed graphs. In particular, we consider a model that extends the centralized dynamics studied in [13, 14], and [19] to cases where each agent implements its own restart policy and shares information only with neighbors characterized by the topology of the communication graph. To assess the impact of the topology of graph on the stability properties of the dynamics, we exploit analytical tools from graph theory and hybrid dynamical system’s theory [29]. Using these tools, this paper makes the following primary contributions:

(1) We first introduce a class of multi-agent concurrent learning (CL) algorithms that incorporate momentum and a centralized restarting mechanism. We demonstrate that if: (a) the graph is strongly connected, (b) the overall data collected by the agents satisfies a “cooperative richness condition,” and (c) the restarting frequency exceeds a certain threshold that encodes the “asymmetry” of the communication graph, then the resulting error estimation dynamics are input-to-state stable [30] with respect to measurement noise and model error approximations. Furthermore, the convergence is exponential with rates assignable via the restarting period. These results are presented in Theorem 1.

(2) Next, by leveraging the robustness properties of the dynamics, we interconnect the momentum-based concurrent learning algorithms with a decentralized coordinated restarting mechanism, enabling a fully decentralized implementation. The resulting dynamical systems are also globally stable and exhibit convergence rates consistent with Theorem 1 following an initial synchronization phase of the restarting times. These results are presented in Theorem 2.

(3) Finally, we present three applications of the proposed momentum-based CL algorithms with restart within the context of data-enabled control: (a) cooperative parameter estimation without persistently exciting regressors in networks where nodes have private data with heterogeneous informativity properties; (b) data-enabled cooperative model-reference adaptive control; (c) data-enabled cooperative feedback-optimization. By employing (hybrid) Lyapunov-based techniques, we show that the resulting closed-loop systems exhibit favorable stability and convergence properties, which are also illustrated via numerical examples.

The rest of this paper is organized as follows: Section 2 presents the preliminaries. Section 3 presents the problem formulation. Section 4 presents the main results. Section 5 presents applications, Section 6 includes the proofs, and Section 7 concludes the paper.

To estimate $\theta^{\star}$, we consider a decentralized momentum-based concurrent learning (DMCL) algorithm with the following update rule for the local estimate $\theta_{i}\in\mathbb{R}^{n}$ of each agent:

where $\tau_{i}$ is a dynamic, non-decreasing coefficient, with rate of growth bounded by $\omega>0$, and which satisfies

where $(T,T_{0})$ are tunable parameters. The auxiliary state $p_{i}\in\mathbb{R}^{n}$ captures the incorporation of momentum, and it satisfies

where $k_{c}>0$ is a tunable gain, $\Lambda_{i}$ is a suitable mapping described below, and $a_{ji}$ is the $ji^{th}$ entry of the adjacency matrix of the graph $\mathcal{G}$ modeling the flow of information betwen agent $i$ and its neighbors. The key components of the DMCL dynamics are explained below:

1. (a)

   The function $\Lambda_{i}$ has the general form:

   $$\Lambda_{i}(\theta_{i},\nu_{i},t,\upsilon_{i})=k_{t}\Psi_{i}\left(\theta_{i},t,\upsilon_{i}\right)+k_{r}\Phi_{i}(\theta_{i},\nu_{i}),$$

   (4)

   where $k_{r}>0$ and $k_{t}\geq 0$ are tunable constants.

2. (b)

   The function $\Psi_{i}$ in (4) is given by

   $\displaystyle\Psi_{i}(\theta_{i},t,\upsilon_{i}(t)):=\phi_{i}(t)\left(\hat{\psi}_{i}(\theta_{i},t)-\psi_{i}^{\star}(t,\upsilon_{i}(t))\right),$

   (5)

   and it incorporates the real-time information available to the $i^{\text{th}}$ agent, where $\psi_{i}^{\star}$ is given by (3), $\hat{\psi}_{i}(\theta_{i},t)\coloneqq\phi_{i}(t)^{\top}\theta_{i}$, and $\upsilon_{i}(t):=d_{i}(t)$ is a time-varying disturbance.

3. (c)

   The function $\Phi_{i}$ in (4) is given by

   $\displaystyle\Phi_{i}(\theta_{i},\nu_{i})\!\coloneqq\!\sum_{k=1}^{\bar{k}_{i}}\phi_{i}(t_{i,k})\!\!\left(\hat{\psi}_{i}(\theta_{i},t_{i,k}){-}\psi_{i}^{\star}(t_{i,k},\nu_{i,k})\right),$

   (6)

   and it incorporates past recorded measurements of the signal $\psi_{i}^{\star}$ in (3) and the regressor $\phi_{i}$, obtained at a sequence of times $\{t_{i,k}\}_{k=1}^{\bar{k}_{i}}$, where $\bar{k}_{i}\in\mathbb{Z}_{\geq 0}$, and where $\nu_{i,k}:=d_{i}(t_{i,k})$ and $\nu_{i}\coloneqq(\nu_{i,1},\nu_{i,2},\dots,\nu_{i,\overline{k}_{i}})\in\mathbb{R}^{\overline{k}_{i}}$ models the persistent disturbances occurring during data collection.

4. (d)

   The last term in the dynamics of $p_{i}$ captures the exchange of information between agent $i$ and its neighbors. Note that, in general, we have that $a_{ij}\neq a_{ji}$.

To study the DMCL dynamics, the data matrix associated to the $i^{th}$ agent is defined as:

Rather than assuming that every matrix $\Delta_{i}$ is positive definite, as in standard single-agent concurrent learning (CL) [9], we will assume a weaker “cooperative” richness condition on the overall data of the network [33, Def. 2].

If (8) holds, the data $\{\Delta_{i}\}_{i\in\mathcal{V}}$ is said to be cooperatively sufficiently rich (CSR).

The form of the DMCL dynamics is closely related to the accelerated gradient flows with momentum studied in [13, 35, 14, 24], which have the general form

and where $f$ is a suitable convex cost function and $\tau_{c}:\mathbb{R}_{\geq 0}\to\mathbb{R}_{>0}$ is a time-varying coefficient. Indeed, using the vectors $\theta:=(\theta_{1},\theta_{2},\ldots,\theta_{N})$, $p:=(p_{1},p_{2},\ldots,p_{N})$, the parameter error coordinates $\tilde{\theta}:=\theta-\mathbf{1}_{N}\otimes\theta^{\star}$, $\tilde{p}:=p-\mathbf{1}_{N}\otimes\theta^{\star}$, and the Laplacian matrix of the graph $\mathcal{L}$, the DMCL dynamics with a centralized coefficient $\tau=\tau_{1}=\ldots=\tau_{N}$ can be written as the following dynamical system:

where $\hat{\mathbf{F}}$ is given by

and where $\mathbf{L}\coloneqq\mathcal{L}\otimes I_{n}$, and where $\mathbf{A}$ and $\mathbf{\Delta}$ are block-diagonal matrices given by:

and $\mathbf{U}$ is given by:

However, while similar decentralized algorithms have been studied in [23, 24, 25], the DMCL dynamics do not describe a standard gradient flow with momentum due to the lack of symmetry on $\mathcal{L}$, i.e., the right-hand side of (10) cannot be expressed as the gradient of a potential function, a property that usually plays a crucial role in the stability properties of momentum-based dynamics.

The following example highlights some of the challenges that can arise when momentum is used and the multi-agent system (MAS) has a communication topology characterized by a directed graph.

To address the instability observed in Example 1, while simultaneously inducing suitable convergence rates achieved via momentum, we can incorporate restart mechanisms into the algorithm. Such mechanisms persistently reset the momentum $\dot{\theta}_{i}$ and the dynamic coefficients $\tau_{i}$ whenever $\tau_{i}$ exceeds the upper bound $T$. The resets are performed according to the following discrete-time updates:

where $\eta_{i}\in\{0,1\}$ is a pre-defined parameter indicating the restart policy of agent $i$. It has been shown that this approach can curtail the oscillations of momentum-based algorithms [13, 17] and also “robustify” their stability properties with respect to persistent disturbances [19]. Indeed, note that the policy $\eta_{i}=1$ implies $p_{i}^{+}=\theta_{i}$, which implies $\dot{\theta}_{i}^{+}=0$. For multi-agent systems with undirected graphs, similar restart mechanisms of the form (15) have been studied in [25, 24]. However, the effectiveness of restarting in the context of multi-agent systems with directed graphs has remained largely unexplored, and, as suggested by Example 1 the extension is non-trivial. Indeed, from the behavior observed in Figure 1 it should be clear that a “slow” restart policy (e.g., when $T$ is large) will not be able to stabilize the system. However, a “fast” restart policy (e.g., when $T$ is small) would keep $p_{i}$ approximately constant, thus reducing the effectiveness of using momentum. The right plot of Figure 1 shows the emerging behavior of the DMCL algorithm when restart is implemented by each node of the network with a “suitable” frequency and in a coordinated manner. While similar phenomena has been recently observed in game-theoretic problems [24], the use of momentum and restart in decentralized CL problems, and its dependence on the data of the system, the topology of the graph, and the perturbed models (3) have remained largely unexplored. This observation motivates the main research problem that we study in this paper:

In the next section we provide an answer to Problem 1 using tools from hybrid dynamical systems and graph theory.

When using a common coefficient $\tau_{c}\in\mathbb{R}_{>0}$ to coordinate the restart of the DMCL algorithm, the resulting dynamical system can be modeled by the following differential inclusion, in vectorial form, with state $y_{c}\coloneqq(\theta,p,\tau_{c},s)$:

whenever $y_{c}\in\mathbf{C}_{c}\times\mathbb{R}_{\geq 0}$, and where $u\coloneqq(\upsilon,\nu)$, the function $\mathbf{\Lambda}$ is given by

and the vectors $\upsilon$ and $\nu$ are defined as

where $\bar{k}:=\sum_{i\in\mathcal{V}}\overline{k}_{i}$. The maps $\mathbf{\Psi}$ and $\mathbf{\Phi}$ above are defined as

where the functions $\Phi_{i},\Psi_{i}$ were defined in (5)-(6) for all $i\in\mathcal{V}$. Since $\theta$ and $p$ are allowed to evolve in $\mathbb{R}^{nN}$, while $\tau_{c}\in[T_{0},T]$, in (16), the flow set $\mathbf{C}_{c}$ is defined as:

which guarantees that during flows the state $\tau_{c}$ remains in the interval $[T_{0},T]$. To incorporate restarts into the DMCL algorithm, each time $\tau_{c}$ meets the condition $\tau_{c}=T$, it is reset to $T_{0}$, and, all the states $(\theta_{i},p_{i})$ are updated as in (15). Therefore, using

with $\eta=(\eta_{1},\eta_{2},\ldots,\eta_{N})$, the discrete-time updates of the states $(\theta,p,\tau)$ of the hybrid system can be written in vectorial form as

which are executed whenever $(\theta,p,\tau)$ are in the jump set $\mathbf{D}_{c}$, defined as follows:

Therefore, the overall discrete-time dynamics of the system with state $y_{c}$ can be written as:

By combining (16) and (23), the DMCL algorithm with centralized restart can be viewed as a HDS of the form (1), with data

Note that in this centralized HDS the jump set (22) only imposes conditions on the state $\tau_{c}$. Namely, a restart is triggered whenever $\tau_{c}=T$. If $\dot{\tau}(t)=\text{constant}\in[0,\omega]$ for all time, then the HDS would model a DMCL algorithm with scheduled periodic restart, where the time between two consecutive restarts is $(T-T_{0})\omega^{-1}$. However, the differential inclusion in (16) also allows us to consider scenarios where $\dot{\tau}$ is not constant but rather is any absolutely continuous function (between restarts) satisfying $\dot{\tau}\in[0,\omega]$, which includes functions that remain constant for arbitrarily long periods of time.

Before presenting our first main result, we introduce two technical propositions that play important roles in our results. All the proofs are presented in Section 6.

With Propositions 1-2 at hand, we are now ready to present the first main result of this paper, which provides conditions to stabilize the DMCL algorithm using a centralized restart. In particular, we study the stability properties of $\mathcal{H}_{c}$ with respect to the closed set $\mathcal{A}_{c}\coloneqq\mathcal{A}_{\theta p}\times[T_{0},T]\times\mathbb{R}_{\geq 0}$, where

which precisely describes the situation where all agent’s estimates $\theta_{i}$ are equal to the true parameter $\theta^{*}$.

The main result of Theorem 1 reveals the impact of the asymmetry of $\mathcal{G}$ on the resetting parameter $T$. In particular, the following observations are in order:

Next, the following corollary leverages the expression of $T^{*}$ to obtain convergence bounds that parallel those obtained for centralized single-agent systems [19].

The bound from Corollary 1 implies that, as $T_{0}{\to}0^{+}$, the convergence of $\theta_{i}$ towards $\theta_{i}^{*}$ is of order $\mathcal{O}\left({e^{-\sqrt{\underline{\sigma}_{\mathbf{\Sigma}}/\overline{\sigma}_{\mathbf{Q}}}}}\right)$, for all $i\in\mathcal{V}$. We complete this section with a corollary for the case $\eta=0$, which guarantees the ISS properties of $\mathcal{H}_{c}$, but not convergence bounds of the form (32).

The resetting bounds of Theorem 1 and Corollary 2 only provide sufficient conditions for ISS with exponential convergence rates. It remains an open question how to obtain tight bounds on $(T_{0},T)$ that are also necessary for stability. We do not further pursue these questions in this paper.

Since a central coordinator might not exist in large-scale networks, in this section, we study decentralized restart strategies based on each agent $i\in\mathcal{V}$ implementing an individual dynamic coefficient $\tau_{i}$. To simplify our discussion, in this section we assume that $\eta_{i}=1$ and $\dot{\tau}_{i}=\omega$ for all $i\in\mathcal{V}$, and that $k_{t}=0$, which allows us to remove the state variable $s$ and its associated dynamics. However, all our results can be extended to the case when time-varying regressors are included.

When each agent implements its own coefficient $\tau_{i}$, the continuous-time DMCL dynamics (16) become

where the main state is now $x=(\theta,p,\tau)\in\mathbb{R}^{Nn}\times\mathbb{R}^{Nn}\times\mathbb{R}^{N}$, $\mathcal{T}\coloneqq\text{diag}(\tau\otimes\mathbf{1}_{n})$, $\tau=(\tau_{1},\tau_{2},\dots,\tau_{N})$, $\mathbf{\Phi}$ is given by (18b), and the flow set is given by

In this case, restarts of the form (15) with $\eta_{i}=1$ occur whenever at least one of the agents satisfies the condition $\tau_{i}=T$. This behavior can be modeled by the following jump set:

However, note that this approach would lead to uncoordinated restarts of the individual dynamics of the agents across the system. For example, for any time window $[T_{0},T]$, one can select $N$ equidistant initial conditions $\tau_{i}(0,0)\in[T_{0},T]$, where $i\in\{1,2,\ldots,N\}$, which result in solutions experiencing $N$ restarts during this time window, each restart separated by intervals of flow of length $\frac{T-T_{0}}{N}$. Therefore, as $N\to\infty$, asynchronous restarts would occur more often, hindering the advantages of incorporating momentum into the flows of the algorithm to accelerate the overall system.

To address this issue, and inspired by the synchronization algorithms of [36], we integrate the restart dynamics (15) of each agent with a decentralized coordination mechanism for the states $\tau_{i}$. Specifically, each agent $i\in\mathcal{V}$ performs individual restarts of the form (15) when $\tau_{i}=T$. However, the agents also implement the following additional discrete-time updates whenever their neighbors $j\in\mathcal{N}_{i}$ satisfy the condition $\tau_{j}=T$:

where $r_{i}>0$ is a tunable parameter. To incorporate these additional discrete-time updates into the overall jump map of the system, consider the set-valued map

which is defined to be non-empty if and only if $\tau_{i}=T$ and $\tau_{j}\in[0,T)$. In words, the mapping $G_{d}(x)$ captures the resets of the individual states $(\theta_{i},p_{i},\tau_{i})\in\mathbb{R}^{2n+1}$ of agent $i$ via (15), and also the updates of its neighbors $j\in\mathcal{N}_{i}$ via (36). The overall jump-map of the multi-agent hybrid system can then be defined using the outer-semicontinuous hull of $G_{d}$¹¹1The outer-semicontinuous hull of a set-valued mapping $G:\mathbb{R}^{n}\rightrightarrows\mathbb{R}^{n}$ is the unique set-valued mapping $\bar{G}:\mathbb{R}^{n}\rightrightarrows\mathbb{R}^{n}$ satisfying $\text{graph}(\bar{G})=\text{cl}(\text{graph}(G))$, where $\text{cl}(\cdot)$ stands for the closure., denoted $\overline{G}_{d}$ leading to