Distributed Networked Real-time Learning

By uniform integrability, $\nabla_{\theta}\mathbb{E}_{\mathcal{P}_{i}}\mathcal{L}(\bm{x}_{i},y_{i};\theta)=\mathbb{E}_{\mathcal{P}_{i}}g_{i}(\theta)$. Assumption 0 thus implies that $\mathbb{E}_{\mathcal{P}_{i}}[g_{i}(\theta)]=\triangledown\ell(\theta)$ for all $i$ and $\theta$.

Let $\varepsilon_{i}(\theta)\triangleq g_{i}(\theta)-\triangledown\ell(\theta)$, then it holds that $\mathbb{E}[\varepsilon_{i}(\theta)]=0$. We further assume:

Assumption 1: For all $\theta_{i}\in\Theta$, the random variables $\{\varepsilon_{i}(\theta_{i}):i\in\{1,\dots,N\}\}$ are independent and

Define $\sigma^{2}=\sum_{i=1}^{N}\sigma_{i}^{2}$. By independence of data streams:

for all $\theta\in\Theta,j\in\left.{\{1,\dots,N\}}\right\backslash{\{i}\}$.

Streams generate data over time according to independent Poisson processes $D_{i}(t)$ with rate $\mu_{i}>0$ and $D_{i}(0)=1$. We assume the time required to compute gradient estimates and/or exchange parameters locally among neighbors or with the central server are negligible compared to the time in between model updates. In what follows we make use of a virtual clock that produces ticks according to an aggregate counting process $D(t)=\sum_{i=1}^{N}D_{i}(t)$ with rate $\mu=\sum_{i=1}^{N}\mu_{i}$. Let $k\in\mathbb{N}^{+}$ denote the index set of ticks associated with the aggregate process. Since we assume the parameter is updated once a data point arrives, the $k$-th iteration is completed at the $k$-th tick. Index $k$ denotes the $k$-th step in the schemes described below.

In FL, gradient estimates are communicated to a central server where a model is updated as follows:

where $\gamma$ is the learning rate, $\mathbf{1}_{i,k}$ is a indicator of whether node $i$ performs the an update: $\bm{1}_{i,k}=1$ if the next gradient estimate comes from the $i$-th stream and $\mathbf{1}_{i,k}=0$ otherwise.

The algorithmic scheme described in (1) was first analyzed in [9] for data in batch form and has been used in the recent literature on asynchronous parallel optimization algorithms (see for example [10], [11] and [12]). As Figure 1 suggests, with heterogeneous data streams, the scheme in (1) trades off speed in producing parameter updates at the expense of heterogeneous noise in gradient estimates. In what follows we introduce a distributed approach that relies on a network regularization penalty to ensure the ensemble average approximates a stationary point (i.e. a choice of parameters with null gradient). We will show that in such a networked approach the trade-off between precision and speed is mitigated.

In the NR scheme, we consider a network of local compute nodes which we model as a graph $\mathcal{G}=(\mathcal{N},\mathcal{E})$, where $\mathcal{N}=\{1,\dots,N\}$ stands for the set of nodes and $\mathcal{E}\subseteq\mathcal{N}\times\mathcal{N}$ is the set of links connecting nodes. Let $A=[\alpha_{ij}]\in\mathbb{R}^{N\times N}$ be the adjacency matrix of $\mathcal{G}$, where $\alpha_{ij}\in\{0,1\}$ indicates whether node $i$ communicates with node $j$: ${\alpha}_{ij}=1$ if two nodes can exchange local information and ${\alpha}_{ij}=0$ otherwise.

In this scheme, each local node $i$ performs model updates according to a linear combination of local gradient estimate and the gradient of a consensus potential:

where $\bm{\theta}_{t}^{\intercal}=(\theta_{1,t}^{\intercal},\dots,\theta_{N,t}^{\intercal})\in\mathbb{R}^{p\times N}$. The consensus potential is a measure of similarity across local models.²²2This consensus potential has been used in the literature of opinion dynamics (see e.g. [13]). The update performed by node $i$ is of the form:

where $a>0$ is a regularization parameter, and

Note that the basic iterate (2) can be interpreted as a stochastic gradient approach to solve the local problem:

in which the objective function is a linear combination of loss and consensus potential.³³3This interpretation is not novel (see e.g. [14], [15] for its use in swarm (flocking) optimization and in multi-task learning [4, 5, 6, 7, 8]). When $a=0$, each local node ignores the neighboring models. For large values of $a>0$, the resulting dynamics reflect the countervailing effects of seeking to minimize consensus potential and improving model fit. With highly dissimilar initial models, each local node largely ignores its own data and opts for updates that lead to a model that is similar to the local average. Once approximate consensus is achieved, local gradient estimates begin to dictate the dynamics of model updates.

In what follows it will be convenient to rewrite (2) as follows:

Given that local nodes independently update and maintain their own parameters, the network regularized scheme is not subject to the possibility of biased gradient estimates stemming from update delays in FL (see [16]).

The scheme proposed in (2) has already been considered in the machine learning literature. In a series of papers (see [4, 5, 6, 7, 8])), the authors consider an approach to multi-task learning based upon a network regularization penalty as in (2). This paper focuses on distributed single-task learning. In contrast to the papers referred above, we consider a non-convex setting with heterogeneous nodes asynchronously updating their respective models at different rates over time.

The scheme proposed in (2) is also related to the literature on consensus optimization (see e.g. [17], [11], [18]). However, the proposed approach can not be interpreted as being based upon averaging over local models as in consensus-based optimization. In that literature, the basic iteration is of the form:

where ${\bf W}_{k}\in\mathbb{R}^{N\times N}$ is doubly stochastic and $g(\theta_{i,k})$ is a noisy gradient estimate. Indeed one can rewrite (2) as:

with $W_{i,i}=1-\gamma a\sum_{j}\alpha_{i,j}$ and $W_{i,j}=\gamma a\sum_{j}\alpha_{i,j}$. However, the resulting matrix ${\bf W}$ is not doubly stochastic in general since we only require $a>0$. Thus, the approach to consensus in (2) can not be interpreted as being based upon averaging over local models as in consensus-optimization.

The algorithms proposed in [11] and [18] are designed for batch data while our approach deals with streaming data. For example, in [11], each node uses the same mini-batch size for estimating gradients while in our approach gradient estimation noise is heterogeneous. In addition, the algorithms proposed in [11] and [18], every node is equally likely to be selected at each iteration to update its local model. In contrast, in our approach data streams are heterogeneous so that certain nodes are more likely to update their models at any given time. Finally, in [11] the objective function (loss) is defined with respect to a distribution that is biased towards the nodes that update more often. This is in contrast to the objective function defined in this paper (i.e. $\ell(\theta)$), where every node contributes to the global distribution with the same weight regardless of their updating frequency.

The ensemble average $\bar{\theta}_{k}\triangleq\frac{1}{N}\sum\nolimits_{i=1}^{N}\theta_{i,k}$ plays an important role in characterizing the performance of the network regularized scheme. To this end, we analyze the process $\{\overline{V}_{k}:k>0\}$ defined as

Let $e_{i,k}\triangleq\theta_{i,k}-\bar{\theta}_{k}$ and $V_{i,k}\triangleq\|e_{i,k}\|^{2}$, then $\overline{V}_{k}=\frac{1}{N}\sum_{i=1}^{N}V_{i,k}$. We now introduce some additional notations. Let $\deg(i)$ denote the degree of vertex $i$ in graph $\mathcal{G}$ and $\overline{d}:=\max_{i}\deg(i)$. Let $\mathbb{E}[\overline{V}_{k+1}|\bm{\theta}_{k}]$ denote the conditional expectation of $\overline{V}_{k+1}$ given $\mathbf{\theta}_{k}$. We define $\mu_{\max}=\max\{\mu_{i}:1\leq i\leq N\}$ and $\mu_{\min}=\min\{\mu_{i}:1\leq i\leq N\}$. We first prove two intermediate results.

Lemma 1 Suppose Assumptions 0, 1 and 2 hold. It holds that

where $\delta_{i,k}=\delta_{i,k}^{f}+\delta_{i,k}^{g}+\delta_{i,k}^{n}$, and

Lemma 2 Suppose Assumptions 0, 1, 2 and 3 hold. Let $\xi={\mu_{\max}}/{\mu_{\min}}$, then:

where $\lambda_{2}$ denotes the second-smallest of the Laplacian associated with graph $\mathcal{G}$ and

We are now ready to state and prove the main theorem.

As in [19], convergence is described in terms of the expected value of the average squared norm of the gradient in the first $K$-updates. The ensuing corollary goes into further detail by describing the same result in terms of real-time elapsed and not just on a total number of iterations.

Theorem 1: Suppose Assumptions 0, 1, 2 and 3 hold. Choose $\gamma<$$\min\{\bar{\gamma}_{1},\bar{\gamma}_{2}\}$, where

are positive by choosing $a>\frac{4\mu_{\min}L+\xi L}{4{\lambda}_{2}\mu_{\max}}$. With scheme (2), it holds that

where $\eta=\frac{\gamma\xi}{N}\Big{(}\frac{1}{2}-2{\gamma}L(2+\frac{1}{N})\Big{)}$.

The regularization penalty parameter $a$ must be high enough to ensure cohesion between local models. This condition is weaker with a higher degree of connectivity (i.e. higher values of $\lambda_{2}$).

Note also that for fixed $N>0$, when $a\to\infty$, then $\gamma\propto 1/a$. So convergence, as characterized by Theorem 1, may be slower. This is not necessarily the case since the conditions in Theorem 1 identify a wide range of choices for $a$ and $\gamma$. For example, simulations indicate that for fixed $\gamma$ higher values of $a$ may speed up convergence (see Figure 3 (c)).

The analysis in Theorem 1 takes place in the time scale indexed by $k>0$ and associated with the clicks associated with a Poisson process with rate $\mu>0$. To embed the result in Theorem 1 in real-time, recall that $\{D(t):t\geq 0\}$ is the counting process governing the aggregation of all data streams. Given our assumption on computation times being negligible, the total number of updates completed in $[0,t)$ is also $D(t)$. Let us define the conditional average squared gradient norm $\|\bar{\triangledown}\ell_{t}\|^{2}$ in the interval $[0,t)$ as follows:

Hence, the result in Theorem 1 can be reinterpreted by taking expectation of (4) over $D(t)$ as:

According to Theorem 1, and using $\gamma\sim\frac{1}{N}$, the coupling of solutions via the network regularization penalty implies the ensemble average approximates a stationary point in the sense that:

The approximation quality is monotonically increasing in the number of nodes. The convergence properties outlined above are related to the ensemble average. It is, therefore, necessary to examine the degree to which individual models differ from the ensemble average. This is the gist of the next result.

Corollary 1: With the same assumptions and definitions in Theorem 1, it holds that

We embed the result in Corollary 1 in real-time. Define the conditional average of $\bar{V}_{k}$ in the interval $[0,t)$ as

The random process $\{\bar{V}_{t}:t>0\}$ tracks the average distance of individual models to the ensemble average. Similar to the discussion of Theorem 1, the real-time result of Corollary 1 is as follows:

This implies the asymptotic difference between individual models and the ensemble average satisfies:

The network regularization parameter $a>0$ plays an important role in controlling the upper bound of in Corollary 1. For fixed $N>0$, when $a\to\infty$, then $\gamma,\eta\propto 1/a$ and $|\kappa|\propto a^{2}$, it follows that $\mathbb{E}\left[\frac{1}{K}\sum_{k=0}^{K-1}\overline{V}_{k}\right]\propto 1/a$. Hence, the upper bound in Corollary 1 can be made arbitrarily small by choosing large enough $a$.

We now present the counterpart convergence result regarding to FL.

Proposition 1: Suppose Assumptions 0, 1, 2 and 3 hold. For scheme 1, with a choice $\gamma\in(0,\frac{2}{L})$, it holds that:

with $\tilde{\eta}=$$\gamma(1-\frac{L\gamma}{2})$.

To embed the process in Proposition 1 in real-time, let us define the average squared gradient norm $\|\triangledown\tilde{\ell}_{t}\|^{2}$ in the interval $[0,t)$ as follows:

Hence, the result in Proposition 1 can be reinterpreted by taking expectation of (5) over $D(t)$ as:

To compare FL with NR, we also make $\gamma\sim\frac{1}{N}$. The asymptotic approximation quality is given by:

which suggests that the approximation quality is determined by the faster data streams. This leads to unsatisfactory performance whenever $\mu_{i}\propto\sigma^{2}_{i}$ (i.e. faster data streams are also less accurate). Evidently, the opposite holds true when faster nodes are also more accurate, i.e. $\mu_{i}\propto 1/\sigma^{2}_{i}$. However, in many real-time machine learning applications, this is not likely to be the case. Obtaining higher precision gradient estimates requires larger batches and/or increased computation. Thus nodes with higher precision are less likely to be the faster ones.

We can observe from Figure (a) that when the learning rate is moderate, both FL and NR can converge, but the empirical standard deviation of FL is much larger than that of NR. With increased $\gamma$, FL fails to converge while NR still performs relatively well, as shown in Figure (b). We can see that NR is more robust with respect to the learning rate.

As we increase $a$ from $1$ to $10$, we can observe from Figure 3 (a) and (b) that the consensus among nodes increases and the empirical mean standard deviation of the “node 0” decreases. As presented in Corollary 1, the regularization parameter $a$ influences the degree of similarity between individual models and the ensemble average. Note that we only identify a range of values for $a$ (lower bound) and $\gamma$ (upper bound) for which convergence is guaranteed so that a higher value of $a$ does not necessarily imply slower convergence, as shown in Figure 3 (c).

In the third experiment, we check the effect of increased connectivity in the homogeneous setting by using a Watts-Strogatz “small world” topology (see [22]), in which each node is connected with 2 (or 8) nearest neighbors.

We can see from Figure 4 that increasing the connectivity of the topology only improves the performance slightly, meaning that only a limited connectivity is needed for the network regularized approach to enjoy a satisfactory rate of convergence.