OledFL: Unleashing the Potential of Decentralized Federated Learning via Opposite Lookahead Enhancement

Let $m$ be the total number of clients. $T$ represents the number of communication rounds. $(\cdot)_{i,k}^{t}$ indicates variable $(\cdot)$ at the $k$-th iteration of the $t$-th round in the $i$-th client. $\mathbf{x}$ denotes the model parameters. The communication topology between clients can be represented as graph denoted as $\mathcal{G}=(\mathcal{N},\mathcal{E},{\bf W})$, where $\mathcal{N}=\{1,2,\ldots,m\}$ represents the set of clients, $\mathcal{E}\subseteq\mathcal{N}\times\mathcal{N}$ denotes the links between clients, $w_{i,j}$ represents the weight of the link between client $j$ and client $i$ and ${\bf W}=[w_{i,j}]\in[0,1]^{m\times m}$ represents the mixing matrix. The inner product of two vectors is denoted by $\langle\cdot,\cdot\rangle$, and $\|\cdot\|$ represents the Euclidean norm of a vector. Other symbols will be explained in their respective contexts.

In this paper, we consider a network of $m$ clients whose objective is to jointly solve the following distributed population risk $F$ minimization problem:

where $\mathcal{D}_{i}$ represents the data distribution in the $i$-th client, which exhibits heterogeneity across clients. Each client’s local objective function $F_{i}({\bf x};\xi)$ is associated with the training data samples $\xi$. We denote $\mathbf{x}_{\mathcal{D}}^{\star}=\arg\min_{\mathbf{x}}F(\mathbf{x})$ as the optimal value of (1). Unlike CFL, we address (1) by enabling clients to collaborate through a mixing matrix $\mathbf{W}$ in a decentralized manner, leveraging peer-to-peer communication among clients without the need for server coordination.

Practically, we consider the empirical risk minimization of the non-convex finite-sum problem in DFL as:

where each client stores a private dataset $S_{i}=\{z_{j}\}$, with $z_{j}$ drawn from an unknown distribution $\mathcal{D}_{i}$. We denote $\mathbf{x}^{\star}=\arg\min_{\mathbf{x}}f(\mathbf{x})$ as the optimal value of problem (2).

The most popular decentralized FL optimizers for solving the problem (2) are DFedSAM [16] and DFedAvg [15]. However, the decentralized approach, lacking central server coordination, leads to increased client inconsistency. To enhance consistency, we design the opposite lookahead enhanced (Ole) initialization method before performing local optimization at each client:

where $\mathbf{x}_{i}^{t}=\sum_{j}w_{i,j}\mathbf{x}_{j,K}^{t-1}$ is the aggregated model. Intuitively, at each initialization, clients obtain the opposite direction of the most recent iteration through Ole. This ensures that the values obtained in the subsequent optimization, $\mathbf{x}_{i,K}^{t}$, do not deviate too far from the initial value $\mathbf{x}_{i}^{t}$, thereby strengthening the consistency among clients. A more intuitive explanation of the effect of Ole is shown in Figure 1. The complete algorithm is presented in Algorithm 1 ¹¹1Here we provide the default form of OledFL that is composed with SAM. In the experiments, we will instantiate OledFL as OledFL-SGD (by setting $\lambda=0$) and OledFL-SAM if necessary..

Discuss on Lookhead Optimizer. Zhang et al. [36] propose the lookahead optimizer with the initial optimization value denoted as $\mathbf{x}_{0}^{t}$, whose core iterative form is given by:

It optimizes the sequence of “fast weights” $\mathbf{x}$ through an internal loop $K$ times and then utilizes these fast weights to determine the initial search direction of the “slow weights” $\phi$, which reduces variance and facilitates rapid convergence of lookahead in practice. When we omit the subscript $i$ in (3) and set $\phi^{t-1}=\sum_{j}w_{i,j}\mathbf{x}_{j,K}^{t-1}$ in (4), the Ole component in (3) is exactly opposite to the symbol in (4), which is the origin of the name “Opposite lookahead enhancement”.

Discuss on Catalyst. In distributed optimization, lin et al.[30] propose a generic acceleration scheme for a large class of optimization methods with the initial optimization value denoted as $\mathbf{x}_{0}^{t}$, whose core iterative form as follows:

Through (5), significant acceleration in the convergence of algorithms such as SAG [31], SAGA [32], and SVRG [33] can be achieved. By comparing (5) with (3), it is evident that the initialization coefficient $\beta$ in (3) is a simpler fixed value. When considering the subscript $i$ in (5) [34], the subtraction in Ole is performed using the client’s most recently obtained parameter value $\mathbf{x}_{i,K}^{t-1}$ rather than the value after the previous communication $\mathbf{x}_{i}^{t-1}$. This difference leads to a fundamental distinction between catalyst and ole, where ole initializes the point in the opposite direction of the current point and the local optimal value point, as shown in Figure 1 (OledFL), while catalyst, similar to the momentum method, initializes the point in the direction of $\mathbf{x}^{t}-\mathbf{x}^{t-1}$ from the current point.

Discussion of the relation with Chebyshev Acceleration (CA): Chebyshev Acceleration has been widely utilized to expedite the attainment of consensus among networked agents during the distributed optimization process [37]. When CA is integrated with stochastic gradient accumulation employing a large batch size at each iteration, it can ensure optimal convergence [38, 39]. A key idea of CA involves transforming the mixing matrix from $\bf W$ to $\tilde{\bf{W}}$. Here, $\widetilde{\bf W}$ is expressed as:

In simple terms, CA transforms the communication topology $\bf W$ into $(1+\eta)\bf W-\eta\bf I$ in the communication period, where $\eta<1$. It can be proven that $\widetilde{\bf W}$ facilitates faster achievement of consensus among multiple clients compared to $\bf W$ [40, 41]. The update form of Ole is equivalent to aggregation using the communication matrix $(1+\beta)\bf W-\beta\bf I$, demonstrating a connection between Ole and the core idea of CA. With the relationship to CA, we will constrain $\beta<1$ in Algorithm 1. Figure 1 shows that Ole enhances consistency, and the relationship between Ole and CA can explain that the acceleration effect of CA originates from the enhancement of consistency among clients.

In existing literature on DFL, the most of analyses focus on the studies from the onefold perspective of convergence but ignore learning its impact on generality [16, 15, 42]. Additionally, some studies in distributed learning exclusively analyze the algorithm’s generalization while overlooking the effect on convergence [43, 44, 45]. To offer a more comprehensive examination of the joint performance of both optimization and generalization in FL, we introduce the well-known concept of excess risk in our analysis.

Firstly, we define $\bar{\mathbf{x}}^{T}$ as the final model generated by the OledFL method after $T$ communication rounds, where $\bar{\mathbf{x}}^{T}=\frac{1}{m}\sum_{i=1}^{m}\mathbf{x}_{i}^{T}$. In comparison with $f(\bar{\mathbf{x}}^{T})$, our primary focus is on the efficiency of $F(\bar{\mathbf{x}}^{T})$ which corresponds to its generalization performance and test accuracy. Consequently, we analyze $\mathbb{E}[F(\bar{\mathbf{x}}^{T})]$ based on the excess risk $\mathcal{E}_{E}$ as:

Generally, $\mathbb{E}[f(\mathbf{x}^{\star})]$ is expected to be very small and even to zero if the model could fit the dataset. Thus $\mathcal{E}_{E}$ could be considered as the joint efficiency of the generated model $\bar{\mathbf{x}}^{T}$. Thereinto, $\mathcal{E}_{G}$ means the different performance of $\bar{\mathbf{x}}^{T}$ between the training dataset and the test dataset, and $\mathcal{E}_{O}$ means the similarity between $\bar{\mathbf{x}}^{T}$ and optimization optimum $\mathbf{x}^{\star}$. From the perspective of the excess risk, $\mathcal{E}_{E}$ approximates our focus $\mathbb{E}[F(\bar{\mathbf{x}}^{T})]$. It is worth noting that, in non-convex settings, $\mathcal{E}_{E}$ is measured via gradient residual $\mathbb{E}\|\nabla f(\bar{\mathbf{x}}^{T})\|^{2}$ rather than $f(\bar{\mathbf{x}}^{T})-f(\mathbf{x}^{\star})$. We will investigate the optimization and generalization performance respectively in the following subsections.

Below, we introduce the definition of the mixing matrix and several assumptions utilized in our analysis.

Definition 1 is commonly used to describe the communication topology in DFL, where it can also be viewed as a Markov transition matrix. The term $1-\psi$ measures the speed of convergence to the equilibrium state. Assumptions 1-3 are mild and commonly used to analyze the non-convex objective DFL [15, 16]. Assumption 4 is utilized to bound the uniform stability for the non-convex objective [43, 46, 47]. It is important to note that when describing the algorithm’s convergence speed, we only use assumptions 1-3; whereas in describing the algorithm’s generalization bound, we utilize assumptions 1, 2 and 4. This is because assumption 4 implies bounded gradients, i.e., $\|\nabla f_{i}(\mathbf{x})\|\leq L_{G}$, while assumption 3 is more general than the bounded gradient assumption.

In this part, we present the optimization error and convergence rate of OledFL under the assumptions 1-3. All the proofs can be found in the Appendix B-A.

In this section, we primarily present a generalization analysis of our OledFL method under two gradient properties (bounded variance and Lipschitz continuity). We utilize uniform stability analysis, which is widely adopted in previous literature, to analyze the generalization error of OledFL. Next, we introduce the definition of uniform stability and then demonstrate the effectiveness of OledFL. All detailed proofs can be available in the Appendix B-B.

In DFL framework, we suppose there are $m$ clients participating in the training process as a set $\mathcal{C}=\{i\}_{i=1}^{m}$. Each client has a local dataset $\mathcal{S}_{i}=\{z_{j}\}_{j=1}^{S}$ with total $S$ data sampled from a specific unknown distribution $\mathcal{D}_{i}$. Now we define a re-sampled dataset $\widetilde{\mathcal{S}_{i}}$ which only differs from the dataset $\mathcal{S}_{i}$ on the $j^{*}$-th data. We replace the $\mathcal{S}_{i^{*}}$ with $\widetilde{\mathcal{S}}_{i^{*}}$ and keep other $m-1$ local dataset, which composes a new set $\widetilde{\mathcal{C}}$. $\mathcal{C}$ only differs from the $\widetilde{\mathcal{C}}$ at $j^{*}$-th data on the $i^{*}$-th client. Then, based on these two sets, OledFL could generate two solutions, $\bar{\mathbf{x}}^{t}$ and $\widetilde{\bar{\mathbf{x}}}^{t}$ respectively, after $t$ rounds. By bounding the difference according to these two models, we can obtain stability and generalization efficiency.

Dataset. We evaluate the proposed OledFL on CIFAR-10&100 datasets [49] in both IID and non-IID settings. To simulate non-IID data distribution among federated clients, we utilize the Dirichlet [50] and Pathological distribution [51]. Specifically, in the Dirichlet distribution, the local data of each client is partitioned by sampling label ratios from the Dirichlet distribution Dir($\alpha$). A smaller value of $\alpha$ indicates a higher degree of non-IID. In our experiments, we set $\alpha=0.3$ and $\alpha=0.6$ to represent different levels of non-IID. In the Pathological distribution, the local data of each client is partitioned by sampling label ratios from the Pathological distribution Path($\alpha$), where the value of $\alpha$ represents the number of classes owned by each client. For example, in the CIFAR-10 dataset, we set $\alpha=2$ to indicate that each client possesses only 2 randomly selected classes out of the 10 available. In our experimental setup, we respectively set $\alpha=2$, $\alpha=4$, and $\alpha=6$ for the CIFAR-10 dataset, and $\alpha=10$, $\alpha=20$, and $\alpha=30$ for the CIFAR-100 dataset.

Baselines. The baselines used for comparison include several state-of-the-art (SOTA) methods in both the CFL and DFL settings. Specifically, the centralized baselines include FedAvg [1], FedSAM [52, 17], and SCAFFOLD [18] . In the decentralized setting, D-PSGD [13], DFedAvg, and DFedAvgM [15], along with DFedSAM [16], are used for comparison. Note that both our baseline and proposed algorithms are designed to operate synchronously.

Implementation Details. The total number of clients is set to 100, with 10% of the clients participating in the communication, creating a random bidirectional topology. For decentralized methods, all clients perform the local iteration step, while for centralized methods, only the participating clients perform the local update [16]. The local learning rate is initialized to 0.1 with a decay rate of 0.998 per communication round for all experiments. For SAM-based algorithms, such as DFedSAM and OledFL-SAM, we set the perturbation weight as $\lambda=0.1$. As for $\beta$, we set $\beta=0.99$ for CIFAR-10 and $\beta=0.8$ for CIFAR-100 in the random topology. The maximum number of communication rounds is set to 500 for all experiments on CIFAR-10&100. Additionally, all ablation studies are conducted on the CIFAR-10 dataset with a data partition method of Dir 0.3 and 500 communication rounds.

Communication Configurations. To ensure a fair comparison between decentralized and centralized approaches, we have implemented a dynamic and time-varying connection topology for DFL methods. This approach ensures that the number of connections in each round does not exceed the number of connections in the centralized server, thus enabling the matching of communication volume between the decentralized and centralized methods as [25]. To ensure a fair comparison, we regulate the number of neighbors for each client in DFL using the client participation rate. Here, we set each client to randomly select 10 neighbors during each communication round. Other communication topologies, such as Grid, are generated according to corresponding rules.

Figures 2 and 3 display the comparison between the baseline method and OledFL on the CIFAR10&100 datasets under Dirichlet and Pathological distributions. From the figures, it is evident that OledFL can converge rapidly with fewer communication rounds, and OledFL-SAM also surpasses SCAFFOLD in terms of generalization performance. It is worth noting that, under the Pathological data distribution, CFL methods exhibit instability during training, whereas DFL methods provide a more stable training process.

Performance Analysis. In Table II, we conduct a series of experiments to compare the performance of our method with baseline methods. The results show that under various non-IID settings, our method consistently outperforms other methods, for example, on the CIFAR-10 dataset, our method outperforms the previous SOTA method DFedSAM by at least 4.5% in both Dirichlet and Pathological distributions. Even in the IID case, our method also outperforms DFedSAM by at least 3.5%. Similarly, these results are also observed on the more complex CIFAR-100 dataset, where compared to DFedSAM, our method provides at least a 3% improvement under Dirichlet distribution and at least a 2.6% improvement under Pathological distribution.

Impact of non-IID levels ($\alpha$). The robustness of OledFL in various non-IID settings is evident from Figure 2& 3 and Table II. A smaller value of alpha ($\alpha$) indicates a higher level of non-IID, which makes the task of optimizing a consensus problem more challenging. However, our algorithm consistently outperforms all baselines across different levels of non-IID. Furthermore, methods based on the SAM optimizer consistently achieve higher accuracy across different levels of non-IID. For instance, on the CIFAR-10 dataset, under the Dirichlet distribution, the performance of our algorithm OledFL-SAM only decreases by 1.3% from the IID to Dir 0.3, which significantly outperforms DFedSAM (2.76%), DFedAvgM (3.42%), DFedAvg (2.72%), D-PSGD (3.17%), and FedAvg (3.06%), respectively. This demonstrates the robustness of our method to heterogeneous data.

Impact of Ole Parameter $\beta$. In Table II and Figure 2&3, we observe a significant improvement in generalization and convergence speed due to Ole initialization. Taking the example of CIFAR-10 under Dirichlet 0.3, parameter initialization helps the DFedAvg algorithm achieve an improvement of around 4% in accuracy, and the DFedSAM algorithm achieves an improvement of around 5% in accuracy. In terms of convergence speed, parameter initialization helps both the DFedAvg and DFedSAM algorithms achieve at least 3$\times$ speedup, and in some cases, even up to 8$\times$ speedup, which coincides with our theoretical analysis and demonstrates the efficacy of our proposed OledFL (see Remark 3).

Explanation of the Effectiveness of Ole. To explore the effectiveness of Ole, we plot the loss landscapes and corresponding contour maps of OledFL-SAM and DFedSAM on the CIFAR10 dataset under Dirichlet 0.3, as shown in Figure 5. It is evident that OledFL-SAM can find parameters with lower loss values. Furthermore, from Figure 4, it can be observed that the loss landscape of OledFL-SAM is flatter. According to the research findings of Keskar et al. [53] and Dziugaite et al. [54], flatter loss surfaces lead to better generalization performance. This observation can explain why OledFL-SAM may exhibit superior generalization performance. This is also consistent with the theoretical analysis results in Remark 3.

Below, we explore the effects of topologies on different DFL methods on CIFAR-10 dataset with Dirichlet $\alpha=0.3$.

Impact of Sparse Connectivity $\psi$. Each client in the network only communicates with its predetermined neighbors, and the specific communication pattern is determined by the corresponding topology. In Table V, the degree of sparse connectivity $\psi$ follows the order: Ring $>$ Grid $>$ Exponential $>$ Full-connected [16, 45, 55]. From Figure 6 and Table IV, It can be observed that there is a general trend: as the sparse connectivity $\psi$ decreases, the accuracy of our proposed algorithm on the test set increases. This can be attributed to the fact that a well-designed communication topology enables clients to obtain better initial optimization points through communication, leading to improved results. Furthermore, OledFL consistently achieves higher test set accuracy compared to other DFL baselines across various topologies. For example, Ole can enhance DFedSAM’s performance by over 9% on a Ring topology. Additionally, from Figure 6, it can be observed that the convergence rate and generalization performance of OledFL generally increases with better topological connectivity, confirming the conclusion of Remarks 1&3.

Relationship between $\beta$ and $\psi$. From Section IV, we have concluded that tighter topological connectivity (indicating smaller $\psi$) corresponds to smaller initial parameter values $\beta$. To validate this theoretical result, we conduct experiments on the OledFL algorithm using the parameter set $\beta=\{0.1,0.2,\ldots,0.9\}$ in each of the four topologies presented in Table V to select the optimal $\beta$ corresponding to the algorithm’s performance. The results of the optimal $\beta$ values under different topologies are presented in Figure 7. By comparing the $\psi$-$\beta$ relationships in Figure 7 with the corresponding values in Table V, the experimental results validate our conclusion in Remark 2 of Theorem 1.

We verify the influence of each component and hyperparameter in OledFL. All the ablation studies are conducted with the “Random” topology, which is consistent with the communication configuration used in Section V-B.

Impact of Ole Parameter $\beta$. The convergence curves under different Ole coefficients after 500 communication rounds are displayed in Figure 8 (a) on the CIFAR-10 dataset under the Dirichlet 0.3 distribution. A larger $\beta$ value implies a greater deviation of each client’s initialization point from the corresponding optimal point. We verify the performance curves of OledFL-SAM under the $\beta$ parameter set $\{0.1,0.5,0.7,0.95,0.99\}$. It can be seen that under the random bidirectional topology, the optimal $\beta$ is 0.99. Furthermore, it is clear that as $\beta$ increases, the algorithm’s convergence speed and generalization performance both improve. When $\beta>1$, the algorithm diverges, which is consistent with the upper bound of $\beta$ obtained in the discussion of its relationship with CA in Section III-C.

Impact of Client Number $m$. In Figure 8 (c), we present the performance with different numbers of participants, $m=\{50,100,200\}$. We observe that, with an increase in the number of local data, OledFL achieves the best performance when $m=50$ or 100, while a decrease in performance is observed when $m$ is relatively large. This can be attributed to the fact that a smaller number of clients has a larger number of local training samples, leading to improved training performance.

Impact of Perturbation Radius $\lambda$. The perturbation radius $\lambda$ is an additional factor influencing the convergence of OledFL. It controls the size of the perturbation radius, where a larger perturbation radius implies a more ambiguous direction of parameter descent, thereby affecting the convergence speed. We evaluate OledFL’s generalization performance using different values of $\lambda$ from the set $\{0,0.01,0.05,0.1,0.2,0.3\}$. Figure 8 (d) illustrates the highest accuracy achieved when $\lambda=0.1$. Additionally, we observe that a larger $\lambda$ leads to a slower convergence speed, which is consistent with our previous analysis.

Impact of local epochs $K$. $K$ represents the number of optimization rounds performed by each client. A larger value of $K$ is more likely to lead to the ”client drift” phenomenon, resulting in increased inconsistency between clients and thereby affecting the algorithm’s performance. We assess the generalization performance of OledFL using different values of $K$ from the set $\{1,2,5,10\}$. Figure 8 (b) demonstrates the highest accuracy achieved when $K=5$. Additionally, we observe that a larger $K$ leads to faster convergence in Figure 8 (b), consistent with our theoretically proven $\mathcal{O}(\frac{1}{\sqrt{KT}})$.