From Local SGD to Local Fixed-Point Methods for Federated Learning

Introduction

In the ‘big data’ era, the explosion in size and complexity of the data arises in parallel to a shift towards distributed computations, as modern hardware increasingly relies on the power of uniting many parallel units into one system. For distributed optimization tasks, specific issues arise, such as decentralized data storage. For instance, the huge amount of mobile phones or smart home devices in the world contain an important volume of data captured and stored on each of them. This data contains a wealth of potentially useful information to their owners, and more so if appropriate machine learning models could be trained on the heterogeneous data stored across the network of such devices. Yet, many users are increasingly sensitive to privacy concerns and prefer their data to never leave their devices. But the only way to share knowledge while not having all data in one place is to communicate, to keep moving towards the solution of the overall problem. Typically, mobile phones communicate back and forth with a distant server, so that a global model is progressively improved and converges to a steady state, which is globally optimal for all users. This is precisely the purpose of the recent and rising paradigm of federated learning (Konečný et al., 2016; McMahan et al., 2017) where typically a global supervised model is trained in a massively distributed manner over a network of heterogeneous devices. Communication, which can be costly and slow, is the main bottleneck in this framework. So, it is of primary importance to devise novel algorithmic strategies, where the computation and communication loads are balanced.

A strategy increasingly used by practitioners is to make use of local computations; that is, more local computations are performed on each device before communication and subsequent model averaging, with the hope that this will reduce the total number of communications needed to obtain a globally meaningful solution. Thus, local gradient descent methods have been investigated (Stich, 2019; Khaled et al., 2019, 2020; Ma et al., 2017; Haddadpour & Mahdavi, 2019). Despite their practical success, local methods are little understood and there is much to be discovered. In this paper, we don’t restrict ourselves to gradient descent to minimize an average of smooth functions; we consider the much broader setting of finding a fixed point of an average of a large number $M$ of operators. Indeed, most, if not all, iterative methods are fixed-point methods, which aim at finding a fixed point of some operator (Bauschke et al., 2011). Fixed-point methods are typically made from compositions and averages of gradient or proximity operators of functions (Combettes & Yamada, 2015; Bauschke & Combettes, 2017); for instance, a sum of proximity operators corresponds to the ‘proximal average’ of functions (Yu, 2013). Using more involved Lyapunov functions than the distance to the solution or the objective value, convergence of methods with inertia, e.g. Nesterov’s acceleration techniques, to a fixed point, can be established (Lessard et al., 2016). (Block-)coordinate or alternating minimization methods are fixed-point methods as well (Richtárik & Takáč, 2014; Pesquet & Repetti, 2015). Let us also mention that by the design of nontrivial fixed-point operators, nonlinear inverse problems can be solved (Combettes & Woodstock, 2020). Beyond optimization, fixed-point methods are used to solve monotone inclusions or variational inequalities, with applications in mechanics or stochastic control. They are also used to find saddle points of convex–concave functions, e.g. Nash equilibria in game theory. Yet another example is attaining the steady-state of a control system or a dynamic phenomenon modeled by a PDE.

We investigate two strategies. The first one consists, for each computing node, in iterating several times some sequence of operations; we call this local steps. The second strategy consists in reducing the number of communication steps by sharing information only with some low probability, and doing only local computations inbetween. We analyze two algorithms, which instantiate these two ideas, and we prove their convergence. Their good performances are illustrated by experiments.

2 Mathematical Background

A Generic Distributed Fixed-Point Method with Local Steps

We call an epoch a sequence of local iterations, followed by averaging; that is, the $n$-th epoch, for $n\geq 1$, is the sequence of iterations of indices $k+1=t_{n-1}+1,\ldots,t_{n}$ (the 0-th epoch is the initialization step $x_{i}^{0}\coloneqq\hat{x}^{0}$, for $i=1,\ldots,M$). We assume that the number of iterations in each epoch, between two aggregation steps, is bounded by some integer $H\geq 1$; that is,

$1\leq t_{n}-t_{n-1}\leq H$, for every $n\geq 1$.

To analyze Algorithm 1, we introduce the following averaged vector:

(i) $\widetilde{\mathcal{T}}_{\lambda}$ is $\zeta$-averaged, with $\zeta=\frac{H\alpha\lambda}{1+(H-1)\alpha\lambda}.$

(iii) The squared differences between two successive updates are summable:

Proof. The convergence property and the property $(iii)$ come from the application of the Krasnosel’skii–Mann theorem, see Theorem 5.15 in (Bauschke & Combettes, 2017). The properties (i) and (ii) are applications of Proposition 4.46, Proposition 4.42, and Proposition 4.35 in (Bauschke & Combettes, 2017). (iv) and (v) come from Theorem 1 in (Davis & Yin, 2016). $\square$

For the baseline algorithm (Algorithm 1 with $H=1$), where averaging occurs after every iteration, we have after $H$ iterations:

We can compare this ‘progress’, made in decreasing the squared distance to the solution, with the one in Theorem 2.3-(ii), where $\frac{1-\zeta}{\zeta}=\frac{1-\alpha\lambda}{H\alpha\lambda}$. This latter value multiplies $\|\hat{x}^{(n+1)H}-\hat{x}^{nH}\|^{2}$, which can be up to $H^{2}$ larger than $\|\hat{x}^{k+1}-\hat{x}^{k}\|^{2}$, for $k$ in $nH,\ldots,(n+1)H-1$. So, in favorable cases, Algorithm 1 progresses as fast as the baseline algorithm. In less favorable cases, the progress in one epoch is $H$ times smaller, corresponding to the progress in 1 iteration. Given that communication occurs only once per epoch, the ratio of convergence speed to communication burden is, roughly speaking, between 1 and $H$ times better than the one of the baseline algorithm. They don’t converge to the same elements, however.

A complementary result on the convergence speed is the following. In the rest of the section, the $t_{n}$ are not restricted to be uniform; we assume that Assumption (2.1) holds, as well as:

Each operator $\mathcal{T}_{i}$ is firmly nonexpansive.

Then we have the following results on the iterates of Algorithm 1:

The next result gives us an explicit complexity, in terms of number of iterations sufficient to achieve $\varepsilon$-accuracy:

Suppose that $H\geq 2$ and that $\lambda\leq\frac{1}{8}$. Then a sufficient condition on the number $T$ of iterations to reach $\varepsilon$-accuracy, for any $\varepsilon>0$, is

Note that as long as the target accuracy is not too high, in particular if $\varepsilon\geq\frac{9\sigma^{2}}{8}$, then $\frac{T}{H}=\mathcal{O}\left(\frac{\|\hat{x}^{0}-x^{\star}\|^{2}}{\varepsilon}\right)$. If $\varepsilon<\frac{9}{8}\sigma^{2}$, the communication complexity is equal to $\frac{T}{H}=\mathcal{O}\left(\frac{\|\hat{x}^{0}-x^{\star}\|^{2}\sigma}{\epsilon^{3/2}}\right)$.

Hence, to get a convergence rate of $\frac{1}{\sqrt{MT}}$ we can choose the parameter $H$ as $\mathcal{O}\left(T^{1/4}M^{-3/4}\right)$, which implies a total number of $\Omega\left(T^{3/4}M^{3/4}\right)$ synchronization steps. If we need a rate of $1/\sqrt{T}$, we can set a larger value $H=\mathcal{O}\left(T^{1/4}\right)$.

We remark that if $H=1$, i.e. communication occurs after every iteration, the last term in Theorem 2.6, which depends on $H-1$, is zero. This is coherent with the fact that $x^{\dagger}=x^{\star}$ in that case, so that the algorithm converges to an exact fixed point of $\mathcal{T}$. In that sense, Theorem 2.6 is tight.

Consider that $\mathcal{T}_{i}(x_{i}^{k})=x_{i}^{k}-\frac{1}{L}\nabla f_{i}(x_{i}^{k})$, where each convex function $f_{i}$ is $L$-smooth; that is, $f_{i}$ is differentiable with $L$-Lipschitz continuous gradient. Then the assumptions in Theorem 2.6 are satisfied and our results recover known results about Local GD for heterogeneous data as particular cases (Khaled et al., 2019).

2 Linear convergence with contractive operators

(i) $\widetilde{\mathcal{T}}_{\lambda}$ is $\xi^{H}$-contractive, with \xi=\max\big{(}\lambda\chi+(1-\lambda),\lambda(1+\chi)-1\big{)}.

In the conditions of Theorem 2.11, the convergence rate $\xi$ with respect to the number of iterations is the same, whatever $H$: the distance to a fixed point is contracted by a factor of $\xi$ after every iteration, in average. The fixed point depends on $H$, however.

In the conditions of Theorem 2.11, without further knowledge on the operators $\mathcal{T}_{i}$, we should set $\lambda=1$, so that $\xi=\chi$, since every other choice may slow down the convergence.

Since Algorithm 1 converges linearly to $x^{\dagger}$, it remains to characterize the distance between $x^{\dagger}$ and $x^{\star}$.

In the conditions of Theorem 2.11, suppose that $\lambda=1$. So, $\xi=\chi$. Then

(1) If $M=1$, $\mathcal{T}_{1}=\mathcal{T}$, so that $\|\mathcal{T}_{1}(x^{\star})-x^{\star}\|=0$ and $S=0$, so that we recover that $x^{\dagger}=x^{\star}$, whatever $H$. In that case, the unique node and the master do not need to communicate, and the variable at the node will converge to $x^{\star}$. In other words, communication is irrelevant in that case.

(2) If $H=1$, $1-\xi^{H-1}=0$ and $S=0$, so that we recover that $x^{\dagger}=x^{\star}$.

(3) If $H\rightarrow+\infty$, $S$ is finite and we have

This corresponds to $x^{\dagger}=\frac{1}{M}\sum_{i=1}^{M}x^{\star}_{i}$, where $x^{\star}_{i}$ is the fixed point of $T_{i}$.

(4) If we let $H$ vary from $1$ to $+\infty$, $S$ increases monotonically from to the value in (14).

(5) In ‘one-shot minimization’, applying $\mathcal{T}_{i}$ consists in going to its fixed point: $\mathcal{T}_{i}(x)=x_{i}^{\star}$, for every $x$. Then $\xi=0$. Hence, $S=0$, because $x^{\dagger}=\frac{1}{M}\sum_{i=1}^{M}x^{\star}_{i}=x^{\star}$.

(6) In the homogeneous case $\mathcal{T}_{i}=\mathcal{T}$ for every $i$,

since $\mathcal{T}(x^{\star})=x^{\star}$. In this case, the $M$ nodes do the same computations, so this is the same as having only one node, like in (1).

Let us consider that each $\mathcal{T}_{i}:x\mapsto x-\gamma\nabla F_{i}(x)$, for some $L$-smooth and $\mu$-strongly convex function $F_{i}$, with $L\geq\mu>0$ and $0<\gamma\leq 2/(L+\mu)$. Set $\lambda=1$. Then $\xi=\chi=1-\gamma\mu$ and $\|\mathcal{T}_{i}(x^{\star})-x^{\star}\|=\gamma\|\nabla F_{i}(x^{\star})\|$. To our knowledge, our characterization of the convergence behavior is new and improves upon state-of-the-art results (Khaled et al., 2019), even in this case.

To summarize, in presence of contractive operators, Algorithm 1 converges at the same rate as the baseline algorithm ($H=1$), up to a neighborhood of size $S$, for which we give a tight bound. So, if the desired accuracy $\epsilon=\|\hat{x}^{k}-x^{\star}\|$ is not lower than $S$, using local steps is the way to go, since the communication load is divided by $H$, chosen as the largest value such that $S\leq\epsilon$ in (13).

A Randomized Communication-Efficient Distributed Fixed-Point Method

Now, we propose a second loopless algorithm, where the local steps in Algorithm 1, which can be viewed as an inner loop between two communication steps, is replaced by a probabilistic aggregation. This yields Algorithm 2, shown above. It is communication-efficient in the following sense: while in Algorithm 1 the number of communication rounds is divided by $H$ (or by the average of $t_{n}-t_{n-1}$ in the nonuniform case), in Algorithm 2 it is multiplied by the probability $p\leq 1$. Thus, $p$ plays the same role as $1/H$.

To analyze Algorithm 2, we suppose that the operators are contractive:

In the particular case of gradient descent (GD) as the operator, this assumption is satisfied with $\rho>0$ for strongly convex smooth functions, see Theorem 2.1.11 in (Nesterov, 2004).

Almost sure linear convergence of Algorithm 2 up to a neighborhood is established in the next theorem:

Since the previous theorem may be difficult to analyze, the next results gives a bound to reach $\varepsilon$-accuracy in in Algorithm 2:

Under Assumption 3.1 and if $\lambda<\frac{p}{15}$, for any $\varepsilon>0$, $\varepsilon$-accuracy is reached after $T$ iterations, with

Experiments

Model Although our approach can be applied more broadly, we focus on logistic regression, since this is one of the most important models for classification. The corresponding objective function takes the following form:

Datasets We use the ’a9a’ and ’a4a’ datasets from the LIBSVM library and we set $\kappa$ to be $\frac{L}{n}$, where $n$ is the size of the dataset and $L$ is a Lipschitz constant of the first part of $\nabla f$, without regularization.

Hardware and software We implemented all algorithms in Python using the package MPI4PY, in order to run the code on a truly parallel architecture. All methods were evaluated on a computer with an Intel(R) Xeon(R) Gold 6146 CPU at 3.20GHz, having 24 cores. The cores are connected to 2 sockets, with 12 cores for each of them.

We consider gradient descent (GD) steps as the operators. That is, we consider the problem of minimizing the finite sum:

where each function $f_{i}$ is convex and $L$-smooth. We set $\mathcal{T}_{i}(x_{i}^{k})\coloneqq x^{k}_{i}-\frac{1}{L}\nabla f_{i}(x_{i}^{k})$. We use $\frac{1}{L}$ as the stepsize, so that each $\mathcal{T}_{i}$ is firmly nonexpansive. The results of Algorithms 1 and 2 are illustrated in Figures 1 and 3, respectively.

2 Local cycling GD

In this section, we consider another operator, which is cycling GD. So, we consider minimizing the same function as in (20), but this time each function $f_{i}$ is also a finite sum: $f_{i}=\frac{1}{N}\sum_{j=1}^{N}f_{ij}$. Instead of applying full gradient steps, we apply $N$ element-wise gradient steps, in the sequential order of the data points. Thus,

where $S_{ij}:y\mapsto y-\frac{1}{NL}\nabla f_{ij}$. If, for each $i$, all functions $f_{ij}$ have the same minimizer $x^{\star}_{i}$, then this joint minimizer is a fixed point of $\mathcal{T}_{i}$. Also, these operators can be shown to be firmly nonexpansive. The results of Algorithms 1 and 2 are illustrated in Figures 2 and 4, respectively.

3 Results

We observe a very tight match between our theory and the numerical results. As can be seen, the larger the value of the parameters $H$ and $\lambda$, the faster the convergence at the beginning, but the larger the radius of the neighborhood. In terms of computational time, there is no big advantage, since the experiments were run on a single machine and the communication time was negligible. But in a distributed setting where communication is slow, our approach has a clear advantage. We can also observe the absence of oscillations. Hence, there is a clear advantage of local methods when only limited accuracy is required.

In the experiment with cyclic GD, the algorithm converges only to a neighbourhood of the ideal solution, even when 1 local step is used. This happens because the assumption of a joint minimizer for all $i$ is not satisfied here. However, since the operators are firmly nonexpansive, we have convergence to a fixed point. The convergence of Algorithm 1 is illustrated with respect to the relaxation parameter $\lambda$. If $\lambda$ is small, convergence is slower, but the algorithm converges to a point closer to the true solution $x^{\star}$. In Figure 4, we further illustrate the behavior of Algorithm 2 with respect to the probability $p$, for cyclic gradient descent. We can see that the fastest and most accurate convergence is obtained for an intermediate value of $p$, here $p=0.2$.

The experiments with Algorithm 2 show that, with a low probability $p$ of update, the neighborhood is substantially larger; however, with $p$ increasing, the convergence in terms of communication rounds becomes worse. Therefore, with careful selection of the probability parameter, a significant advantage can be obtained.

Conclusion

We have proposed two strategies to reduce the communication burden in a generic distributed setting, where a fixed point of an average of operators is sought. We have shown that they improve the convergence speed, while achieving the goal of reducing the communication load. At convergence, only an approximation of the ideal fixed point is attained, but if medium accuracy is sufficient, the proposed algorithms are particularly adequate.

In future work, we will generalize the setting to randomized fixed-point operators, to generalize stochastic gradient descent approaches. We will also investigate compression (Khaled & Richtárik, 2019; Chraibi et al., 2019) of the communicated variables, with or without variance reduction, in combination with locality.

Acknowledgements

Part of this work was done while the first author was an intern at KAUST.

References

Supplementary material

Let us list here the notations used in the paper and the Appendix:

The value $V_{k}$ measures the deviation of the iterates from their average. This value is crucial for the convergence analysis. The values $g_{i}(x^{k})$ and $\hat{g}^{k}$ can be viewed as analogues of the gradient and the average gradient in our more general setting. The value $\sigma^{2}$ serves as a measure of variance adapted to methods with local steps.

A.2 Basic Facts

Jensen’s inequality. For any convex function $f$ and any vectors $x^{1},\ldots x^{M}$ we have

In particular, with $f(x)=\|x\|^{2}$, we obtain

Facts from linear algebra. We will use the following important properties:

A.3 Technical lemmas

Technical Lemma 1. If $\mathcal{T}$ is firmly nonexpansive, then

Appendix B Analysis of Algorithm 1 in Theorem 2.6

The first lemma allows us to find a recursion on the optimality gap for a single step of local method:

Under Assumption 2.5 and under the condition $0\leq\lambda\leq 1$, we have

B.2 Proof of Lemma B.2

In this section, we prove the following extended version of Lemma B.2: Under Assumption 2.5 and under the condition $0\leq\lambda\leq 1$, we have

Moreover, for $\lambda\leq\frac{1}{8\max(1,H-1)}$, we have

Setting $\lambda=2$ and $\beta=\frac{1}{3}$, we get

Using $\lambda\leq\frac{1}{8\max(1,H-1)}$, we get

B.3 Proof of Theorem 2.6

B.4 Proof of Corollary 2.7

Suppose that $\lambda\leq\frac{1}{8\max(1,H-1)}$ and that Assumption 2.5 holds. Then a sufficient condition on the number $T$ of iterations to reach $\varepsilon$-accuracy, for any $\varepsilon>0$, is

Appendix C Analysis of Algorithm 1: Proof of Theorem 2.14

We set $\widetilde{\mathcal{T}}=\frac{1}{M}\sum_{i=1}^{M}\mathcal{T}_{i}^{H}$.

Thus, we just have to bound $\|\widetilde{\mathcal{T}}(x^{\star})-x^{\star}\|$:

Appendix D Analysis of Algorithm 2

We first derive two lemmas, which will be combined to prove Theorem 3.2.

The first lemma provides a recurrence property, for one iteration of Algorithm 2:

We now bound the variance $V_{k}$ for one iteration, using the contraction property:

D.2 Proof of Lemma D.2

If communication happens, $V_{k}=0$. Therefore,

Setting $c_{1}=2$, $c_{2}=\frac{1}{3}$, we get

D.3 Proof of Theorem 3.2

Using the law of total expectation, we get

D.4 Proof of Corollary 3.3

Under Assumption 3.1 and if $\lambda<\frac{p}{15}$, for any $\varepsilon>0$, $\varepsilon$-accuracy is reached after $T$ iterations, with

Regarding the second term, if $\displaystyle 150\lambda^{3}\sigma^{2}\leq\frac{1}{2}p^{2}\varepsilon\min\left\{\frac{\lambda\rho}{\rho+1},\frac{p}{5}\right\}$, then $\displaystyle\begin{cases}150\lambda^{3}\sigma^{2}\leq\frac{1}{2}p^{2}\varepsilon\frac{\lambda\rho}{\rho+1},\\ 150\lambda^{3}\sigma^{2}\leq\frac{p^{3}\varepsilon}{10}\end{cases}$,

so that $\lambda\leq\min\left\{\frac{p}{18\sigma}\sqrt{\frac{\varepsilon\rho}{\rho+1}},\frac{p\varepsilon^{\frac{1}{3}}}{40\sigma^{\frac{2}{3}}}\right\}.$

Regarding the first term, and using the fact that $\lambda<\frac{p}{15}$, if $\displaystyle\left[1-\min\left\{\frac{\lambda\rho}{\rho+1},\frac{p}{5}\right\}\right]^{T}\Psi_{0}\leq\frac{\varepsilon}{2}$,

then $T\geq\max\left\{\frac{1+\rho}{\lambda\rho},\frac{5}{p}\right\}\log\frac{2\Psi_{0}}{\varepsilon}$, so that $\lambda=\min\left\{\frac{p}{15},\frac{p}{18\sigma}\sqrt{\frac{\varepsilon\rho}{\rho+1}},\frac{p\varepsilon^{\frac{1}{3}}}{40\sigma^{\frac{2}{3}}}\right\}.$