Achieving Dimension-Free Communication in Federated Learning via Zeroth-Order Optimization

## Abstract

Abstract Federated Learning (FL) offers a promising framework for collaborative and privacy-preserving machine learning across distributed data sources.
However, the substantial communication costs associated with FL pose a significant challenge to its efficiency.
Specifically, in each communication round, the communication costs scale linearly with the model’s dimension, which presents a formidable obstacle, especially in large model scenarios.
Despite various communication efficient strategies, the intrinsic dimension-dependent communication cost remains a major bottleneck for current FL implementations.
In this paper, we introduce a novel dimension-free communication strategy for FL, leveraging zero-order optimization techniques.
We propose a new algorithm, FedDisco, which facilitates the transmission of only a constant number of scalar values between clients and the server in each communication round, thereby reducing the communication cost from 𝒪 ​ ( d ) 𝒪 𝑑 \mathcal{O}(d) to 𝒪 ​ ( 1 ) 𝒪 1 \mathcal{O}(1) , where d 𝑑 d is the dimension of the model parameters.
Theoretically, in non-convex functions, we prove that our algorithm achieves state-of-the-art rates, which show a linear speedup of the number of clients and local steps under standard assumptions and dimension-free rate for low effective rank scenarios.
Empirical evaluations through classic deep learning training and large language model fine-tuning substantiate significant reductions in communication overhead compared to traditional FL approaches.

## 1 Introduction

Federated Learning (FL) is a promising distributed machine learning framework that enables a large number of clients to collaboratively train a model under the orchestration of a central server [, ].
By allowing clients to train models locally without sharing their raw data, FL offers a privacy-preserving distributed learning paradigm.
Thanks to these advantages, FL has become a popular learning paradigm used in many applications, such as healthcare[] and edge devices[, ], among others.

Despite its benefits, FL often encounters challenges to its efficiency due to expensive communication costs. Specifically, in one communication round, the server needs to broadcast the global model to all participating clients, and each of these clients is expected to transmit a new local model to the server for global aggregation []. In other words, the communication costs for one participating client scale linearly with the model’s dimension, presenting a prohibitively expensive communication overhead for the FL system, especially in large model and/or low communication speed scenarios.
For example, foundation models in language and vision, such as GPT-3 [], and many other models [], scale with billions of parameters.
On the other hand, the typical communication speed for FL is several Mbps in wireless environments and up to several hundred Mbps in wired connections.
As a result, when training these models in a distributed/federated approach, communication becomes the key bottleneck in scaling. To achieve communication-efficient FL, several techniques have been developed, including lazy aggregation or local update steps [], various compression techniques [, , , , , , , , , ], and client sampling strategies [].
While these methods can reduce certain communication costs, their communication costs still scale linearly with the model’s dimension for each participating client in one communication round. This intrinsic dimension-dependent communication cost remains a major bottleneck for current FL systems, particularly in the era of large deep learning models.

In this paper, we propose a novel approach to FL that achieves dimension-free communication per round, leveraging zeroth-order optimization techniques [, , ].
Our core idea is to decompose each update in a zeroth-order optimization algorithm into a gradient scalar and a perturbation vector.
The gradient scalar is computed using the finite difference of function values, while the perturbation vector can be generated identically across clients from a shared random seed.
This decomposition is not possible in first-order methods.
Instead of transmitting the entire model parameters, our approach only communicates gradient scalars and random seeds, resulting in constant communication costs per round.
However, the total communication cost, which is the product of the number of rounds and the communication cost per round, might still be proportional to the model size. This is because the convergence rate of zeroth-order methods is known to depend on the model dimension
[, ].

Recent work [] has shown that the Hessian matrix of the loss function often exhibits low effective rank. By leveraging a low effective rank assumption, we rigorously show that our proposed algorithm achieves a convergence rate independent of the model dimension. Furthermore, extensive experiments validate the effectiveness of our approach, demonstrating significant communication cost savings in both training[, ] and fine-tuning tasks[, , ] compared to existing FL methods. To the best of our knowledge, this is the first systematic attempt to achieve dimension-free communication per client in FL within each communication round.

Our main results and contributions are summarized as follows:

- •
We propose FedDisco, a novel zeroth-order federated learning framework with dimension-free communication.
In each round, both the downlink (model pulling) and uplink (model uploading) communications involve transmitting only a constant number of scalar values between the participating clients and the server. This dramatically reduces the communication cost from $\mathcal{O}(d)$ to $\mathcal{O}(1)$, where $d$ is the dimension of the model parameters.
- •
Theoretically, in non-convex functions, we prove that FedDisco achieves ${\mathcal{O}}\big{(}\frac{\sqrt{d}}{\sqrt{mPKR}}\big{)}$ under the standard conditions, where $P$ is number of simultaneous perturbations, $K$ is the number of local update step and $R$ is number of communication rounds. This rate highlights the linear speedup in terms of the local update step, the number of perturbation and clients.
Under the $\kappa$-effective rank setting, we prove a dimension-free rate of ${\mathcal{O}}\big{(}\frac{\sqrt{\kappa}}{\sqrt{mPR}}\big{)}$.
One of our key technical contributions is proving the dimension-free rate without the strong and unrealistic assumption in [] that requires the finite difference step-size parameter $\mu\to 0$.
- •
We conduct comprehensive experiments on both training and the fine-tuning tasks for our FedDisco.
Our results decisively demonstrate that FedDisco achieves nearly the same performance as other algorithms while significantly reducing communication costs by several orders of magnitude. Additionally, our experiments reveal that using a large number of perturbations (large $P$) improves performance without incurring additional memory overhead.

### 1.1 Related Work

Communication-Efficient Federated Learning:
Initially, [] proposed the FedAvg algorithm, which uses multiple local update steps to reduce the frequency of model transfers, thereby lowering the total communication cost. Since then, various techniques have been developed to further optimize communication efficiency, with most approaches involving compression methods.
For instance, sparsification [, , , , ], quantization [, , , , , , ], and low-rank approximations [, ].
However, the communication cost per round between a client and the server remains dependent on the model dimension. Taking Top-K as an example [], only the top $K$ largest coordinates in the gradient vector are selected for communication.

In theory, the convergence rate of Top-K depends on both the model dimension $d$ and the hyper-parameter $K$. In practice, the choice of $K$ is linearly scaled with the model dimension $d$, i.e., $K=c\times d$, where $c$ is a constant such as 0.001 [].
Despite the success of these methods, the intrinsic dimension-dependent communication cost remains a major bottleneck for current FL systems, especially in the era of large deep learning models.
In this work, our proposed FedDisco achieves a constant ${\mathcal{O}}(1)$ communication cost for both uplink and downlink transmissions by utilizing zero-order optimization.

Zeroth-Order Optimization (ZOO):
Zeroth-Order Optimization (ZOO) relies solely on function evaluations, making it ideal for scenarios where explicit gradient computation is impractical, expensive, or unreliable, such as in black-box optimization [, , ] and reinforcement learning [, , ].
Recently, ZOO has shown significant memory advantages in deep learning since it requires only forward propagation [, ].
However, existing work has not fully exploited ZOO’s potential to reduce communication costs in federated learning, as we propose in this work. For example, FedZO [] applies zeroth-order stochastic gradient estimation in the classic FedAvg algorithm, achieving a convergence rate of ${\mathcal{O}}(\frac{\sqrt{d}}{\sqrt{mKR}})$ in non-convex cases, but its communication complexity remains ${\mathcal{O}}(d)$ per round, the same as FedAvg.
Similarly, BAFFLE [] employs ZOO to achieve ${\mathcal{O}}(P)$ communication complexity in the uplink, but the downlink communication complexity remains ${\mathcal{O}}(d)$.

Our work is inspired by MeZO [], which introduced the low effective rank assumption and demonstrated dimension-free convergence.
However, MeZO focuses primarily on memory efficiency with ideal assumptions and is limited to centralized learning scenarios.
Our approach builds upon this foundation to achieve dimension-free communication in federated learning.

## 2 Fed erated Learning with Di men s ion-Free Co mmunication (FedDisco)

### 2.1 Problem Formulation and Vanilla Algorithm Description

As most standard FL settings, we assume that there exist $M$ clients in total in our FL system.
Our goal is to minimize the global loss function $f$ formulated as,

$$ $\displaystyle\min_{{\boldsymbol{x}}\in\mathbb{R}^{d}}f({\boldsymbol{x}})=\min_{{\boldsymbol{x}}\in\mathbb{R}^{d}}\frac{1}{M}\sum_{i=1}^{M}f_{i}({\boldsymbol{x}})\;\;\;{\rm where\;}f_{i}({\boldsymbol{x}}):=\mathbb{E}\hskip 1.42271pt[f({\boldsymbol{x}};\xi_{i})],$ (1) $$

where ${\boldsymbol{x}}$ is a $d$-dimensional model parameter and $f_{i}$ represents the loss function on client $i$. The loss function is the expectation of a stochastic loss function $f_{i}({\boldsymbol{x}};\xi_{i})$, where $\xi_{i}$ is sampled from different local data distributions, which is known as data heterogeneity in FL.
The typical FL algorithm comprises three steps in each round:
1) The server initially samples a set of clients and sends the current global model to them.
2) Upon receiving the global model, each client performs local computations based on this model and then transmits the updated local model back to the server.
3) The server aggregates all the returned local models from the clients and updates the global model accordingly.
During each round of this process, the communication costs between a client and the server are $2d$ per round, as the model is transmitted via the uplink and downlink channels, respectively.

To achieve a constant communication cost per round, we proposed FedDisco algorithm by utilizing zeroth-order optimization. The central concept is to avoid transferring model parameters between clients and the server, which becomes prohibitively expensive for large models.
Instead, communication in FedDisco is limited by random seeds and gradient scalars used in zeroth-order optimization.
As shown in Algorithm [1](#alg1) and Figure [1](#S2.F1), FedDisco contains five key stages in each round:

- 1.
Sampling clients. The server first samples a set of clients to participate, denoted by $C_{r}$. The server only needs to send $K$ random seeds $\{s^{k}_{r}\}_{k=1}^{K}$.
- 2.
Local Model Rebuild. Rather than directly synchronizing the global model, each client rebuilds its local model by using only random seeds and gradient scalars (Line 20-26). These scalars are stored in the server and transmitted from the server to client.
- 3.
Local Computation. After having a local model, each client runs $K$ local update steps via zeroth-order optimization using the random seeds $\{s^{k}_{r}\}_{k=1}^{K}$: ${\boldsymbol{x}}_{i,r}^{k+1}={\boldsymbol{x}}_{i,r}^{k}-\eta\cdot g_{i,r}^{k}\cdot{\boldsymbol{z}}_{r}^{k},$ where ${\boldsymbol{x}}^{k}_{i,r}$ is the model parameter at the client $i$ in the $r$-th round and $k$-th local update and ${\boldsymbol{z}}_{r}^{k}\sim{\mathcal{N}}(\textbf{0},\textbf{I}_{d})$ by random seed and gradient scalar is $g_{i,r}^{k}=\frac{1}{\mu}\big{(}f_{i}({\boldsymbol{x}}_{i,r}^{k}+\mu{\boldsymbol{z}}_{r}^{k};\xi_{i,r}^{k})-f_{i}({\boldsymbol{x}}_{i,r}^{k};\xi_{i,r}^{k})\big{)}$ (Line 28-34).
Then the client sends the gradient scalars $\{g_{i,r}^{k}\}_{k=1}^{K}$ to the server.
- 4.
Global Aggregation.
The server received gradient scalars from each participating client and then aggregate them by averaging: $\{g_{r}^{k}\}_{k=1}^{K}=\big{\{}\sum_{i\in C_{r}}g_{i,r}^{k}/|C_{r}|\big{\}}_{k=1}^{K}$. The server needs to store the gradient scalar $\{g_{r}^{k}\}_{k=1}^{K}$ and random seeds $\{s^{k}_{r}\}_{k=1}^{K}$ for future use.
- 5.
Local Model Sync. The client model after the local update is not the same as the global aggregation ones. So there is another synchronization step that the clients update the model with the difference of global gradient scalars and the local scalars.

In simple words, FedDisco takes advantage of the zeroth-order optimization to only communicating the random seeds and gradient scalars between clients and the server, thus reducing the communication costs from $\mathcal{O}(d)$ in existing FL methods to $\mathcal{O}(K)$. The update can be summarized as

$$ $\displaystyle{\boldsymbol{x}}_{r+1}=$ $\displaystyle\frac{1}{m}\sum_{i\in C_{r}}{\boldsymbol{x}}_{i,r}^{K},\;\;{\boldsymbol{x}}_{i,r}^{0}={\boldsymbol{x}}_{r},\;\;{\boldsymbol{x}}_{i,r}^{k+1}={\boldsymbol{x}}_{i,r}^{k}-\eta g_{i,r}^{k}{\boldsymbol{z}}_{i,r}^{k},\;\;k=0,\cdots K-1.$ (2) $$

Figure: Algorithm 1 Federated Learning with Dimension-Free Communication (FedDisco)

Figure: Figure 1: Illustration of the FedDisco algorithm and the components used in server and clients.
Refer to caption: /html/2405.15861/assets/Disco_FL2.png

### 2.2 Improvements and Variations of Algorithm Implementation

In Algorithm [1](#alg1), we present the algorithm in a simplified format for clarity.
In practice, there are several potential improvements.
I. Only one random seed.
Instead of assigning a unique set of seeds $\{s_{r}^{k}\}_{k=1}^{K}$ for each local update step, a single random seed suffices because sequential random vectors generated from the same seed are deterministic. This approach further reduces the downlink communication costs per round to $\mathcal{O}(1)$ without altering the algorithm.
II. Multiple perturbations. One common variation in zeroth-order optimization is to use multiple perturbations $\{z_{r,p}\}_{p=1}^{P}$ per step, with the effective update being a weighted average of these perturbations.
Unlike large mini-batch size, this does not increase the memory consumption since we calculate the corresponding gradient scalar $\{g_{i,r,p}^{k}\}_{p=1}^{P}$ sequentially. This approach can significantly reduce the variance of the stochastic gradient estimate but also proportionally increases the communication overhead per round since we need to transfer multiple gradient scalars.

Memory consumption can also be optimized. Note that in our base algorithm (Table [1](#alg1)), the server stores the entire history of selected random seeds and computed gradient scalars.
This can lead to significant memory usage over many rounds.
However, we observe that gradient and seed information older than the most lagged client’s last update is no longer needed.
Since the server already tracks the last updated round for each client, we can efficiently manage the history using a queue.
After clients complete their local updates, the server can discard outdated information from the queue, thus minimizing memory usage.

The base ZOO methods can be replaced as well. For clarity, the algorithm in Table [1](#alg1) is based on vanilla ZO-SGD, but it can be readily extended to other zeroth-order optimization methods like ZO-SignSGD [], ZO-SVRG [], ZO-Adam[] etc. One pitfall is unlike ZO-SGD, the optimizer is no longer stateless. To ensure synchronization between client and server, this state in the optimizer must also be synchronized, which can be achieved via a reset procedure, as discussed below.

Reset the Local Information Instead of Synchronization.
The purpose of "ClientSyncModel" is to ensure that at the end of each round, the models stored on the clients match the server’s model.
This leads to a consistent starting point for the subsequent "ClientRebuildModel" step.
Notice the model before the local update is also a valid starting point since it represents the server’s model from the $r-$th round.
Hence, a simple alternative approach is modifying the "ClientZOLocalUpdate" function into
1) Snapshot the current model and optimizer state.
2) Execute the local update and return the gradient scalars.;
3) Reset the model and optimizer back to previous snapshot value.
This reset approach differs subtly from synchronization in terms of which version of the server’s model the client aligns with: resetting aligns with the $r-$th round’s version, while synchronization aligns with the latest $(r+1)-$th round. To accommodate this, the server must update the client’s last update record variable $t_{i}$ to $r-1$ instead of $r$ at the end of each round.

The reset approach offers an additional advantage: it can reset both model parameters and optimizer states without extra communication costs. This is particularly beneficial for stateful optimizers like momentum or Adam. For instance, the momentum values on each client diverge after local updates due to varying gradients. Resetting the optimizer state and consistently using the server’s averaged gradient scalars ensures consistency between clients and the server. The main drawback of using reset instead of synchronization is that there is an extra memory consumption due to snapshot.

Model Pulling for Excessive Lagging If Necessary.
If a client remains unsampled for an extended period, the model pulling step requires retrieving all historical seeds and gradient scalars to update the model.
This can be computationally demanding.
In contrast, directly pulling the server’s model has a fixed cost regardless of the client’s lag time.
This introduces a trade-off: if a client has limited computational resources and can tolerate communicating full model parameters, it might be preferable to simply pull the server’s model.

Enhanced Privacy through Private Seed Shifting.
Data privacy is paramount in FL.
While our proposed algorithm, like other FL methods, does not share local data with the server, we can further enhance privacy by ensuring the server remains unaware of how the model evolves on the client side.
Notice that even without direct access to local data, the server could potentially infer some information about the local distribution by comparing model updates between rounds.
To address this, we introduce a simple yet effective improvement: a private shift or function, known only to the clients, applies to the random seeds.
Upon receiving a seed to generate a perturbation, the client first applies this private shift function to alter the seed.
Since this shift is deterministic, it is easy to see that this modification does not affect the functionality of our algorithm while it prevents the server from reconstructing the model updates (
This shift can be established via another server or a consensus protocol among clients).
As a result, the random gradient scalars transmitted to the server cannot convey any information about the local data distribution, further enhancing privacy protection.

## 3 Convergence and Communication Cost Analysis

This section presents the convergence rate of FedDisco under both standard assumptions and the additional low effective rank assumption.
Due to space constraints, all proofs are deferred to Appendix [A](#A1).
First, we list the following standard assumptions [1](#Thmassumption1), [2](#Thmassumption2), [3](#Thmassumption3), which are commonly used in the existing literature.

###### Assumption 1 (Unbiased Stochastic Gradient with Bounded Variance)

For any $r\geq 1$, we have

$$ $\mathbb{E}\hskip 1.42271pt[\nabla f_{i}({\boldsymbol{x}}_{r};\xi_{r})]=\nabla f_{i}({\boldsymbol{x}}_{r})\;{\rm and}\;\mathbb{E}\hskip 1.42271pt\left[\|\nabla f_{i}({\boldsymbol{x}}_{r};\xi_{r})-\nabla f_{i}({\boldsymbol{x}}_{r})\|^{2}\right]\leq\sigma^{2},\;\;\forall i.$ $$

###### Assumption 2 (Bounded Gradient Dissimilarity)

For any $i\in[M]$, $\|\nabla f({\boldsymbol{x}})-\nabla f_{i}({\boldsymbol{x}})\|^{2}\leq\sigma_{G}^{2}$.

###### Assumption 3 ( $L$ -Lipschitz Continuous Gradient)

$f\in{\mathcal{C}}_{L}^{1,1}(\mathbb{R}^{d})$, i.e., $f$ is continuous and differentiable in first order and satisfies $L$-smooth condition:

$$ $\displaystyle\|\nabla f({\boldsymbol{x}})-\nabla f({\boldsymbol{y}})\|\leq L\|{\boldsymbol{x}}-{\boldsymbol{y}}\|,\;\forall{\boldsymbol{x}},{\boldsymbol{y}}\in\mathbb{R}^{d}$ $$

The convergence bound of FedDisco under the above standard assumptions is as follows:

###### Theorem 1 (Standard Convergence Bound of FedDisco)

Under the assumptions [1](#Thmassumption1), [2](#Thmassumption2) and [3](#Thmassumption3), using Gaussian perturbations ${\boldsymbol{z}}_{r}^{k}\sim{\mathcal{N}}(\textbf{0},{\boldsymbol{I}}_{d})$,
and if $\eta\leq\min\{\frac{mP}{24L(d+4)},\frac{2P}{mKL(d+P+4)},\frac{1}{mK^{2}L},\frac{mP(d+3)^{3}}{2L[3mPK(d+3)^{3}+(d+6)^{3}]}\}$, then the sequence of iterates generated by the FedDisco Algorithm satisfies:

$$ $\displaystyle\frac{1}{R}\sum_{r=0}^{R-1}\mathbb{E}\hskip 1.42271pt_{r}\|\nabla f({\boldsymbol{x}}_{r})\|^{2}\leq$ $\displaystyle\frac{4\big{(}f({\boldsymbol{x}}_{0})-f({\boldsymbol{x}}^{\star})\big{)}}{KR\eta}+\left(\frac{72KL\eta}{m}+\frac{24(d+4)L\eta}{mP}\right)\sigma_{G}^{2}$ $\displaystyle\;\;\;+\frac{16L(d+4)\eta}{mP}\sigma^{2}+2\mu^{2}L^{2}(d+3)^{3},$ (3) $$

where ${\boldsymbol{x}}_{r}$ is the model parameter in the $r$-th round, $P$ is the number of perturbations, ${\boldsymbol{x}}^{*}$ is the optimal point, $K$ is the number of local update steps, $R$ is the number of communication rounds, $d$ is the dimension of model parameters, and $m$ is the number of sampled clients in each round. $\hfill\blacksquare$

###### Remark 1

The right-hand side of equation ([3](#A1.Ex29)) comprises terms with distinct interpretations. The first term represents the decrease in the loss value at the initial point, the second term quantifies the impact of data heterogeneity, the third term arises from the stochastic gradient estimate, and the fourth is introduced by the finite difference approximation. The last term is often negligible since $\mu$ is typically very small.
The crucial terms are the middle two, which, unfortunately, both depend on the dimension of the model parameters.

###### Corollary 1 (Standard Convergence Rate of FedDisco)

Further, based on theorem [1](#Thmtheorem1), supposing that $\mu\leq\frac{1}{(d+3)\sqrt{PKR}}$ and $\eta={\mathcal{O}}\left(\frac{\sqrt{mP}}{\sqrt{dRK}}\right)$,
the convergence rate of FedDisco is ${\mathcal{O}}\left(\frac{\sqrt{d}}{\sqrt{mPKR}}\right)$ when the algorithm runs with sufficient large communication round $R$. $\hfill\blacksquare$

###### Remark 2

Both the number of local updates, $K$, and the number of perturbations, $P$, appear in the denominator of the final convergence rate, indicating a linear speedup with increasing client numbers and local steps. However, these parameters have opposing effects on the learning rate. A larger number of perturbations allows for a larger learning rate, while a larger number of local updates necessitates a smaller learning rate. This is intuitive, as more perturbations reduce variance between clients, while more local updates increase the dissimilarity between client models.

Recently, research has shown that many deep learning models exhibit a faster training process than the pessimistic dimension-dependent rate.
This is because the Hessian matrix of the loss function often tends to have a low effective rank [].
Inspired by this observation, a tighter convergence bound related to the low effective rank can be established, rather than one based on the model dimension. To achieve this, we adapt Assumption 1 regarding low effective rank from [] for the FL setting.

###### Assumption 4 (Local $\kappa$ -Effective rank)

Let $G({\boldsymbol{x}}_{r})=\max_{i}\max_{\xi_{r}\in\mathcal{D}}\|\nabla f_{i}({\boldsymbol{x}}_{r};\xi_{i,r})\|$. There exists a Hessian matrix $\mathbf{H}({\boldsymbol{x}}_{r})\preceq L\cdot\mathbf{I}_{d}$ such that:

- •
For all ${\boldsymbol{x}}$ such that $\|{\boldsymbol{x}}-{\boldsymbol{x}}_{r}\|\leq 2\eta dG({\boldsymbol{x}}_{r})$, we have $\nabla^{2}f({\boldsymbol{x}})\preceq\mathbf{H}({\boldsymbol{x}}_{r})$.
- •
The effective rank of $\mathbf{H}({\boldsymbol{x}}_{r})$, i.e., $\frac{tr(\mathbf{H}({\boldsymbol{x}}_{r}))}{\|\mathbf{H}({\boldsymbol{x}}_{r})\|}$, is at most $\kappa$.

Based on this local effective rank assumption, we obtain the convergence bound that relies on the effective rank $\kappa$ only, that is, independent of the dimension of the model parameter $d$.
For ease of illustration, we restrict the theoretical analysis regarding the low effective rank assumption to the case where $K=1$ only. This does not significantly limit the applicability of our findings, as the communication cost per round in our algorithm scales linearly with $K$, whereas in typical federated learning algorithms, this cost is independent of $K$. Thus, the communication savings achieved by local update techniques are less pronounced in our context.
Further, we assume that $z_{i,r}$ is sampled from a sphere with radius $\sqrt{d}$ and the Gaussian case is listed in the Appendix.

###### Theorem 2 (Convergence of FedDisco with $\kappa$ -Effective Rank)

Under the assumptions [1](#Thmassumption1), [2](#Thmassumption2), [3](#Thmassumption3) and [4](#Thmassumption4), supposing $\eta\leq\frac{1}{L}\left(1+\frac{d\kappa+d-2}{P(d+2)}\right)^{-1}$ and drawing ${\boldsymbol{z}}_{i}^{r}$ from the unit ball with radius $\sqrt{d}$, the sequence of iterates generated by the FedDisco Algorithm satisfies:

$$ $\displaystyle\frac{1}{R}\sum_{r=0}^{R-1}\mathbb{E}\hskip 1.42271pt\|\nabla f({\boldsymbol{x}}_{r})\|^{2}\leq$ $\displaystyle\;\frac{4(f({\boldsymbol{x}}_{0})-f({\boldsymbol{x}}^{\star}))}{R\eta}+\frac{2L\eta}{m}\left(1+\frac{d\kappa+d-2}{P(d+2)}\right)(\sigma_{G}^{2}+\sigma^{2})$ $\displaystyle\;\;{}+\frac{1}{4}\mu^{2}L^{2}(d+3)^{3}\eta+\mu^{2}L^{3}d\eta^{2}+\frac{4\mu^{2}Ld}{R\eta}.\hfill$ (4) $$

Selecting $\eta={\mathcal{O}}\left(\frac{\sqrt{mP}}{\sqrt{R\kappa}}\right)$ and $\mu\leq\frac{\sqrt{\kappa}}{\sqrt{mP(d+3)^{3}}}$, we can get

$$ $\displaystyle\frac{1}{R}\sum_{r=0}^{R-1}\mathbb{E}\hskip 1.42271pt\|\nabla f({\boldsymbol{x}}_{r})\|^{2}={\mathcal{O}}\left(\frac{\sqrt{\kappa}}{\sqrt{mRP}}\right)+{\mathcal{O}}\left(\Big{(}\frac{\sqrt{P}}{\sqrt{mR\kappa}}+\frac{\sqrt{\kappa}}{\sqrt{mRP}}\Big{)}(\sigma_{G}^{2}+\sigma^{2})\right).$ (5) $$

Typically, $\kappa\gg P$ holds, so the convergence rate of FedDisco is ${\mathcal{O}}\left(\frac{\sqrt{\kappa}}{\sqrt{mRP}}\right)$. $\hfill\blacksquare$

###### Remark 3

Our proof is inspired by MeZO [], but we relax the strong assumption used in MeZO, which constitutes a significant technical contribution. The proof in [] relies on an approximation that holds only when the finite difference step size $\mu$ approaches zero (see the first equation in the proof of Lemma 2 in []). This is impractical, as $\mu$ cannot be zero in real-world applications. We extend the proof to the multi-agent setting, rectify the approximation issue, and quantify the impact of a non-zero $\mu$. When $\mu\to 0$ and we consider the centralized setting, i.e., $M=m=1$ and $\sigma_{G}^{2}=0$, our theorem reduces to the MeZO case.

Compared with Corollary [1](#Thmcorollary1), the convergence rate is quite similar, with the key difference being the replacement of the dimension $d$ with the effective rank $\kappa$. This difference is crucial because $\kappa$ is typically much smaller than $d$, especially in large language models where $d$ can be orders of magnitude larger than $\kappa$. See [] for more evidences and discussions.

###### Assumption 1 (Unbiased Stochastic Gradient with Bounded Variance)

###### Assumption 2 (Bounded Gradient Dissimilarity)

###### Assumption 3 ( L 𝐿 L -Lipschitz Continuous Gradient)

###### Theorem 1 (Standard Convergence Bound of FedDisco)

###### Remark 1

###### Corollary 1 (Standard Convergence Rate of FedDisco)

###### Remark 2

###### Assumption 4 (Local κ 𝜅 \kappa -Effective rank)

###### Theorem 2 (Convergence of FedDisco with κ 𝜅 \kappa -Effective Rank)

###### Remark 3

### 3.1 Communication Cost Analysis

Unlike typical FL algorithms, the communication vector length per round in our proposed algorithm is non-deterministic, depending on the lagged history of each client.
However, we can still compute the amortized communication length per round.
For the pull model step (downlink communication), the vector length is $2mKP\times{\boldsymbol{h}}$, where the factor $2$ comes from the seeds and the gradient scalars, and ${\boldsymbol{h}}$ denotes the length of lagged rounds.
It can be shown that $\mathbb{E}\hskip 1.42271pt{\boldsymbol{h}}=\frac{M}{m}$ as when the total number of rounds R is sufficiently large, all $M$ clients will need to pull $RKP$ information to rebuild their models.
For the local update step (uplink communication), the returned vector length is always fixed at $mKP$ corresponding to $K$ local updates with $P$ gradient scalars per update for each of the $m$ clients.
We summarize the communication complexity in the following table [1](#S3.T1).

**Table 1: Comparison of communication complexity of typical algorithms**
| Algorithm | Uplink Comm.<br>Per Round | Downlink Comm.<br>Per Round | Round<br>Complexity | Uplink Comm.<br>Complexity | Downlink Comm.<br>Complexity |
| --- | --- | --- | --- | --- | --- |
| FO-FedAvg | $md$ | $md$ | ${\mathcal{O}}(\frac{1}{mK\epsilon^{2}})$ | ${\mathcal{O}}(\frac{d}{K\epsilon^{2}})$ | ${\mathcal{O}}(\frac{d}{K\epsilon^{2}})$ |
| FedZO | $md$ | $md$ | ${\mathcal{O}}(\frac{d}{mPK\epsilon^{2}})$ | ${\mathcal{O}}(\frac{d^{2}}{PK\epsilon^{2}})$ | ${\mathcal{O}}(\frac{d^{2}}{PK\epsilon^{2}})$ |
| Ours (Standard) | $mKP$ | $2MKP$ | ${\mathcal{O}}(\frac{d}{mPK\epsilon^{2}})$ | ${\mathcal{O}}(\frac{d}{\epsilon^{2}})$ | ${\mathcal{O}}(\frac{Md}{m\epsilon^{2}})$ |
| Ours (Low rank) | $mP$ | $2MP$ | ${\mathcal{O}}(\frac{\kappa}{mP\epsilon^{2}})$ | ${\mathcal{O}}(\frac{\kappa}{\epsilon^{2}})$ | ${\mathcal{O}}(\frac{M\kappa}{m\epsilon^{2}})$ |

If we compare our algorithm with other naive combinations of the zeroth-order algorithm and FL framework, the communication of our algorithm can reach several magnitudes lower than them.
Hence, if $\kappa\ll\frac{md}{MK}$, the theorem indicates that our proposed algorithm can converge much faster than the first-order FL counter-parts regarding the communication cost.
It is hard to estimate the effective low rank $\kappa$ in pure theoretically domain.
Based on the results in numerical experiment shown in the next section, it should be safe to say that the effective low rank should be much smaller than the total dimensions of the model.

## 4 Experiments

In this section, we evaluate the performance of the FedDisco and compare it with several other algorithms through numerical experiments. We begin by training a simple Convolutional Neural Network model from scratch on the MNIST image classification task [].
The FL system comprises 100 clients, with the dataset evenly partitioned into 100 subsets, each assigned to one client. In each communication round, 10% of the clients are randomly selected to participate in the training process.

Figure: Figure 2: Ablation study of the influence of the number of local updates and perturbations on FedDisco.
Refer to caption: /html/2405.15861/assets/mnist_local_update_acc.png

Figure [2](#S4.F2) is plotted based on the average communication vector length that is transferred between one client and server.
In the figure, we just compared FedDisco with the classical FedAvg algorithm since it is the corresponding first-order algorithm. All algorithms uses SGD optimizer with momentum $0.5$ and set the base learning rate as $0.001$.
The figure clearly demonstrates the substantial communication cost savings achieved by our algorithm, even for the small CNN model containing only 28938 parameters. (Note: FedAvg has not converged yet).
We can also clearly observe in Figure [2](#S4.F2) that both local update $K$ and perturbations $P$ can strongly influence the algorithm’s performance.
As discussed in the previous section, the communication cost per round is doubled if the local updates and perturbations are doubled.
However, the algorithm will converge faster with larger $K$ and $P$.
It is clear that the larger number of perturbations eventually leads to higher test accuracy (more influential than local update) while it slightly slows down the algorithm at the beginning.

Figure: Figure 3: Comparison between multiple federated learning algorithms on the Fashion Dataset.
Refer to caption: /html/2405.15861/assets/Fashion_loss.png

Next, based on above ablation study, we evaluate a perturbation trick on the Fashion dataset[] with a larger CNN model (1,206,590 parameters).
Like the learning rate scheduler, we use a small base number of perturbations of 25 then double it at rounds 500, 1000, and 2000. Other settings are same as MNIST ones.
Besides FedAvg, we compare it against FedCom [] (using the quantization technique) and FedAvg + Top K (uploading the largest K elements of the local update difference). We select $K$ equals to the 10% number of the parameters and quantization technique used in FedCom is compressing the each elements in the parameters to use 8 bits only.
The left plot in Figure [3](#S4.F3) shows loss against communication rounds. FedDisco converges slower than the first-order methods, except for Top K, which is expected due to the inherent slower convergence of zeroth-order methods. The right plot, illustrating test accuracy against effective communication vector length, reveals a different trend. FedDisco achieves reasonably high test accuracy with significantly less communication.

To further verify the effectiveness of FedDisco on LLMs, we execute fine-tuning tasks on the SST-2 dataset [, ], which is for the sentiment classification task, and CB dataset [], which is for hypothesis inference problem (^1^11The loading and splitting dataset are based on [https://huggingface.co/datasets/super_glue](https://huggingface.co/datasets/super_glue).). The model we used is OPT-125M[]. Due to the model’s size, we set 3 clients with 2 participating in each round to illustrate the core concept. Table [2](#S4.T2) compares FedDisco with varying numbers of perturbations against MeZO and standard SGD fine-tuning as baselines. The learning rate is set to 1e-6 for SST-2 (running 10,000 rounds) and 1e-7 for CB (running 4,000 rounds). The table clearly demonstrates that FedDisco matches MeZO’s performance and can even outperform the first-order approach. Notably, the last column listed the total communication cost of FedDisco with 10 perturbations, which is even less than the size of a single model.

**Table 2: Comparison of FedDisco (last 4 columns) and MeZO and SGD on fine tuning tasks**
| Task | SGD | MeZO | # Perturb = 1 | # Perturb = 5 | # Perturb = 10 | Comm. Cost |
| --- | --- | --- | --- | --- | --- | --- |
| SST-2 | 86.40% | 84.90% | 84.69% | 85.16% | 86.73% | 3e5 |
| CB | 77.22% | 74.80% | 73.85% | 74.65% | 74.90% | 1.2e5 |

## 5 Conclusion and Future Works

We presents a novel algorithm FedDisco that significantly reduces communication costs in FL, opening a new direction for combining FL with zeroth-order optimization. We rigorously prove that under a low-rank assumption, FedDisco’s convergence rate and total communication cost are independent of the model dimension, marking the first theoretical result to achieve this. Our empirical evaluations further demonstrate the communication efficiency of FedDisco in both training and fine-tuning tasks.
One limitation of FedDisco is its computational cost. Although ZOO requires forward passes only, the overall computation remains high due to the slow convergence rate. Due to the scope of this paper, we have not explored several potential computational improvements. For example, in LLM fine-tuning, techniques like LoRA [] and prefix tuning [] could reduce computation and the search space, potentially accelerating ZOO convergence.
Similarly, model pruning [, ] and integration with other optimization algorithms[] could reduce computational costs in training tasks.

## Appendix A Appendix

**Table 3: Notations in this paper**
| Notation | Meaning |
| --- | --- |
| $d$ | Model parameter dimension |
| $m$ | Number of clients participating in each round |
| $i,M$ | Index, number of clients |
| $r,R$ | Index, number of communication round |
| $p,P$ | Index, number of perturbations |
| $k,K$ | Index, number of local update iterations |
| ${\boldsymbol{x}}_{r}$ | Global model parameters in the $r$-th round |
| ${\boldsymbol{x}}_{i,r}^{k}$ | Local model parameters in the $k$-th iteration and $r$-th round at client $i$ |
| $\xi_{i,r}^{k}$ | Data sample used in the $k$-th iteration and $r$-th round at client $i$ |
| $g_{i,r}^{k}$ | Zeroth-order gradient estimate scalar |
| ${\boldsymbol{z}}_{r}^{k}$ | Perturbation in the $k$-th iteration and $r$-round |
| $f$ | Global loss function |
| $f_{i}$ | Local loss function at client $i$ |
| $C_{r}$ | Set of clients participating in $r$-th round |

### A.1 Main Recursion

We can focus on the server-side model’s evolution only because after the execution of "ClientSyncModel" functions or reset the model, all sampled clients are the same as server-side model. For other clients that are not sampled, they will sync to the server-side model after the execution of "ClientSyncModel" so that we can virtually assume all clients and servers are iterated with the same server-side model.

The recursion of the server-side model can be written as

$$ $\displaystyle{\boldsymbol{x}}_{r+1}=$ $\displaystyle{\boldsymbol{x}}_{r}-\eta\sum_{k=1}^{K}g_{r}^{k}{\boldsymbol{z}}_{r}^{k}={\boldsymbol{x}}_{r}-\frac{\eta}{m}\sum_{k=1}^{K}\sum_{i\in C_{r}}g_{i,r}^{k}{\boldsymbol{z}}_{r}^{k}=\frac{1}{m}\sum_{i\in C_{r}}\Big{(}\underbrace{{\boldsymbol{x}}_{i,r}-\eta\sum_{k=1}^{K}g_{i,r}^{k}{\boldsymbol{z}}_{r}^{k}}_{:={\boldsymbol{x}}_{i,r+1}}\Big{)}.$ $$

where we just denote ${\boldsymbol{x}}_{i,r}={\boldsymbol{x}}_{r}$ for the client’s model.
It is now clear that our algorithm follows the same routine as the Federated Average framework that it combines the models after each client runs $K$ local-update steps in their local model ${\boldsymbol{x}}_{i,r+1}$.

### A.2 Lemmas for the Zeroth-order Optimization

Before we present the proof of our main theorem, we first list several well-known lemmas about the zeroth-order optimization, which is the foundation for all following proofs.

###### Lemma 1

[] $f\in{\mathcal{C}}_{L}^{1,1}(\mathbb{R}^{n})$ if it is differentiable and satisfies

$$ $\displaystyle|f({\boldsymbol{y}})-f({\boldsymbol{x}})-\langle\nabla f({\boldsymbol{x}}),{\boldsymbol{y}}-{\boldsymbol{x}}\rangle|\leq\frac{L}{2}\|{\boldsymbol{y}}-{\boldsymbol{x}}\|^{2}.$ (6) $$

###### Lemma 2

[, ]
We define a smooth approximation of objective function $f_{i}$ as $f_{i}^{\mu}(\cdot)$ that can be formulated as

$$ $\displaystyle f_{i}^{\mu}({\boldsymbol{x}}):=\frac{1}{(2\pi)^{\frac{P}{2}}}\int f_{i}({\boldsymbol{x}}+\mu{\boldsymbol{z}})e^{-\frac{1}{2}\|{\boldsymbol{z}}\|^{2}}d{\boldsymbol{z}}=\mathbb{E}\hskip 1.42271pt[f_{i}({\boldsymbol{x}}+\mu{\boldsymbol{z}})],$ (7) $$

where $\mu>0$ is the smoothing parameter, and ${\boldsymbol{z}}$ is one n-dimensional standard Gaussian random vector.
Then, for any $f_{i}\in{\mathcal{C}}_{L}^{1,1}$, the following statements hold.

- (a)
The gradient of $f_{i}^{\mu}(\cdot)$ is $L_{\mu}$-Lipschitz continuous where $L_{\mu}\leq L$. $\nabla f_{i}^{\mu}({\boldsymbol{x}})$ can be shown as
$\displaystyle\nabla f_{i}^{\mu}({\boldsymbol{x}})=\frac{1}{(2\pi)^{\frac{P}{2}}}\int\frac{f_{i}({\boldsymbol{x}}+\mu{\boldsymbol{z}})-f_{i}({\boldsymbol{x}})}{\mu}{\boldsymbol{z}}e^{-\frac{1}{2}\|{\boldsymbol{z}}\|^{2}}d{\boldsymbol{z}}.$
(8)
- (b)
For any ${\boldsymbol{x}}\in\mathbb{R}^{d}$,
$\displaystyle|f_{i}^{\mu}({\boldsymbol{x}})-f_{i}({\boldsymbol{x}})|\leq$
$\displaystyle\frac{1}{2}\mu^{2}Ld$
(9)
$\displaystyle\|\nabla f_{i}^{\mu}({\boldsymbol{x}})-\nabla f_{i}({\boldsymbol{x}})\|\leq$
$\displaystyle\frac{1}{2}\mu L(d+3)^{\frac{3}{2}}$
(10)
- (c)
For any ${\boldsymbol{x}}\in\mathbb{R}^{d}$,
$\displaystyle\frac{1}{\mu^{2}}\mathbb{E}\hskip 1.42271pt_{\boldsymbol{z}}\left[\Big{(}f_{i}({\boldsymbol{x}}+\mu{\boldsymbol{z}})-f_{i}({\boldsymbol{x}})\Big{)}^{2}\|{\boldsymbol{z}}\|^{2}\right]\leq\frac{\mu^{2}}{2}L^{2}(d+6)^{3}+2(d+4)\|\nabla f_{i}({\boldsymbol{x}})\|^{2}$
(11)

Following form ([10](#A1.E10)) and utilizing Jensen’s inequality $\|a\|^{2}\leq 2\|a-b\|^{2}+2\|b\|^{2}$, we have

$$ $\displaystyle\|\nabla f_{i}^{\mu}({\boldsymbol{x}})\|^{2}\leq 2\|\nabla f_{i}({\boldsymbol{x}})\|^{2}+\frac{1}{2}\mu^{2}L^{2}(d+3)^{3},$ (12) $\displaystyle\|\nabla f_{i}({\boldsymbol{x}})\|^{2}\leq 2\|\nabla f_{i}^{\mu}({\boldsymbol{x}})\|^{2}+\frac{1}{2}\mu^{2}L^{2}(d+3)^{3}.$ (13) $$

Moreover, we denote $f_{i}^{\mu}({\boldsymbol{x}}^{*}):=\min\limits_{{\boldsymbol{x}}\in\mathbb{R}^{d}}f_{i}^{\mu}({\boldsymbol{x}})$ and conclude $|f_{i}^{\mu}({\boldsymbol{x}}^{*})-f_{i}({\boldsymbol{x}}^{*})|\leq\frac{\mu^{2}Ld}{2}$ from $\eqref{eq.oo}$. Then, we further conclude that

$$ $\displaystyle-\mu^{2}Ld\leq\left[f_{i}^{\mu}({\boldsymbol{x}})-f_{i}^{\mu}({\boldsymbol{x}}^{*})\right]-\left[f_{i}({\boldsymbol{x}})-f_{i}({\boldsymbol{x}}^{*})\right]\leq\mu^{2}Ld.$ (14) $$

###### Lemma 1

###### Lemma 2

### A.3 Proof of theorem 1

Our main theorem is based on multiple perturbations. To light the notation, we first introduce $G_{i,r}^{k}$ that stands for the stochastic zeroth-order gradient estimate on ${\boldsymbol{x}}_{i,r}^{k}$ averaging over $P$-perturbation directions:

$$ $\displaystyle G_{i,r}^{k}:=$ $\displaystyle\frac{1}{P}\sum_{p=1}^{P}G_{i,r,p}^{k}=\frac{1}{P}\sum\limits_{p=1}^{P}\frac{f_{i}({\boldsymbol{x}}_{i,r}^{k}+\mu{\boldsymbol{z}}_{r,p}^{k};\xi_{i,r}^{k})-f_{i}({\boldsymbol{x}}_{i,r}^{k};\xi_{i,r}^{k})}{\mu}{\boldsymbol{z}}_{r,p}^{k}=\frac{1}{P}\sum\limits_{p=1}^{P}g_{i,r,p}^{k}\cdot{\boldsymbol{z}}_{r,p}^{k}$ (15) $$

To begin with, we start with a few lemma about the property about $G_{i,r}^{k}$.

###### Lemma 3 (Bounds on the stochastic zeroth-order gradient variance)

The variance of stochastic zeroth-order gradient $\mathbb{E}\hskip 1.42271pt\|G_{i,r}^{k}-\nabla f_{i}^{\mu}({\boldsymbol{x}}_{i,r}^{k})\|^{2}$ can be bounded by the true gradient $\|\nabla f({\boldsymbol{x}}_{r})\|^{2}$ on the starting point of round $r$, the local update distance $\|{\boldsymbol{x}}_{i,r}^{k}-{\boldsymbol{x}}_{r}\|^{2}$ and several constants:

$$ $\displaystyle\mathbb{E}\hskip 1.42271pt_{r}\left\|G_{i,r}^{k}-\nabla f_{i}^{\mu}({\boldsymbol{x}}_{i,r}^{k})\right\|^{2}\leq$ $\displaystyle\frac{6(d+4)}{P}\|\nabla f({\boldsymbol{x}}_{r})\|^{2}+\frac{6L^{2}(d+4)}{P}\mathbb{E}\hskip 1.42271pt_{r}\left\|{\boldsymbol{x}}_{i,r}^{k}-{\boldsymbol{x}}_{r}\right\|^{2}+\frac{6(d+4)}{P}\sigma_{G}^{2}$ $\displaystyle+\frac{2(d+4)}{P}\sigma^{2}+\frac{\mu^{2}L^{2}(d+6)^{3}}{2P}.$ (16) $$

Proof. For any independent and identically distributed random variables $\{{\boldsymbol{y}}_{p}\}_{p=1}^{P}$ with the mean $\bar{y}$, we know

$$ $\displaystyle\mathbb{E}\hskip 1.42271pt\left\|\frac{1}{P}\sum_{p=1}^{P}{\boldsymbol{y}}_{p}-\bar{y}\right\|^{2}=\frac{1}{P^{2}}\sum_{p=1}^{P}\mathbb{E}\hskip 1.42271pt\|{\boldsymbol{y}}_{p}-\bar{y}\|^{2}$ (17) $$

Recall that $G_{i,r}^{k}=\frac{1}{P}\sum_{p=1}^{P}G_{i,r,p}^{k}$, $\mathbb{E}\hskip 1.42271pt[G_{i,r,p}^{k}|{\boldsymbol{x}}_{i,r}^{k}]=\nabla f_{i}^{\mu}({\boldsymbol{x}}_{i,r}^{k})$, and lemma [2](#Thmlemma2) shows that

$$ $\displaystyle\mathbb{E}\hskip 1.42271pt_{r}\|G_{i,r,p}^{k}-\nabla f_{i}^{\mu}({\boldsymbol{x}}_{i,r}^{k})\|^{2}\leq 2(d+4)\|\nabla f_{i}({\boldsymbol{x}}_{i,r}^{k};\xi_{i,r}^{k})\|^{2}+\frac{\mu^{2}}{2}L^{2}(d+6)^{3}.$ $$

Substituting $G_{i,r}^{k}$ and above properties into ([17](#A1.E17)), we establish

$$ $\displaystyle\mathbb{E}\hskip 1.42271pt_{r}\left\|G_{i,r}^{k}-\nabla f_{i}^{\mu}({\boldsymbol{x}}_{i,r}^{k})\right\|^{2}\leq$ $\displaystyle\frac{2(d+4)}{P}\mathbb{E}\hskip 1.42271pt_{r}\left\|\nabla f_{i}({\boldsymbol{x}}_{i,r}^{k};\xi_{i,r}^{k})\right\|^{2}+\frac{\mu^{2}L^{2}(d+6)^{3}}{2P}$ $\displaystyle\leq$ $\displaystyle\frac{2(d+4)}{P}\mathbb{E}\hskip 1.42271pt_{r}\left\|\nabla f_{i}({\boldsymbol{x}}_{i,r}^{k})\right\|^{2}+\frac{2(d+4)}{P}\sigma^{2}+\frac{\mu^{2}L^{2}(d+6)^{3}}{2P}$ $$

Next, we bound the $\mathbb{E}\hskip 1.42271pt_{r}\left\|\nabla f_{i}({\boldsymbol{x}}_{i,r}^{k})\right\|^{2}$ via the Jensen’s inequality:

$$ $\displaystyle\mathbb{E}\hskip 1.42271pt_{r}\left\|\nabla f_{i}({\boldsymbol{x}}_{i,r}^{k})\right\|^{2}=$ $\displaystyle\mathbb{E}\hskip 1.42271pt_{r}\left\|\nabla f_{i}({\boldsymbol{x}}_{i,r}^{k})-\nabla f_{i}({\boldsymbol{x}}_{r})+\nabla f_{i}({\boldsymbol{x}}_{r})-\nabla f({\boldsymbol{x}}_{r})+\nabla f({\boldsymbol{x}}_{r})\right\|^{2}$ $\displaystyle\leq$ $\displaystyle 3\mathbb{E}\hskip 1.42271pt_{r}\left\|\nabla f_{i}({\boldsymbol{x}}_{i,r}^{k})-\nabla f_{i}({\boldsymbol{x}}_{r})\right\|^{2}+3\mathbb{E}\hskip 1.42271pt_{r}\|\nabla f_{i}({\boldsymbol{x}}_{r})-\nabla f({\boldsymbol{x}}_{r})\|^{2}+3\|\nabla f({\boldsymbol{x}}_{r})\|^{2}$ $\displaystyle\leq$ $\displaystyle 3L^{2}\mathbb{E}\hskip 1.42271pt_{r}\left\|{\boldsymbol{x}}_{i,r}^{k}-{\boldsymbol{x}}_{r}\right\|^{2}+3\sigma_{G}^{2}+3\|\nabla f({\boldsymbol{x}}_{r})\|^{2}$ $$

Lastly, plugging back, we finish the proof of lemma

$$ $\displaystyle\mathbb{E}\hskip 1.42271pt_{r}\left\|G_{i,r}^{k}-\nabla f_{i}^{\mu}({\boldsymbol{x}}_{i,r}^{k})\right\|^{2}\leq$ $\displaystyle\frac{2(d+4)}{P}\Big{(}3L^{2}\mathbb{E}\hskip 1.42271pt_{r}\left\|{\boldsymbol{x}}_{i,r}^{k}-{\boldsymbol{x}}_{r}\right\|^{2}+3\sigma_{G}^{2}+3\|\nabla f({\boldsymbol{x}}_{r})\|^{2}\Big{)}$ $\displaystyle\;\;{}+\frac{2(d+4)}{P}\sigma^{2}+\frac{\mu^{2}L^{2}(d+6)^{3}}{2P}$ $\displaystyle=$ $\displaystyle\frac{6(d+4)}{P}\|\nabla f({\boldsymbol{x}}_{r})\|^{2}+\frac{6L^{2}(d+4)}{P}\mathbb{E}\hskip 1.42271pt_{r}\left\|{\boldsymbol{x}}_{i,r}^{k}-{\boldsymbol{x}}_{r}\right\|^{2}$ $\displaystyle\;\;{}+\frac{6(d+4)}{P}\sigma_{G}^{2}+\frac{2(d+4)}{P}\sigma^{2}+\frac{\mu^{2}L^{2}(d+6)^{3}}{2P}$ $$

$\hfill\blacksquare$

Similarly, we can also bound the second-order moments of $\mathbb{E}\hskip 1.42271pt_{r}\|G_{i,r}^{k}\|^{2}$ as follows.

###### Lemma 4 (Bounds on the stochastic zeroth-order gradient second-order moments)

$\mathbb{E}\hskip 1.42271pt\|G_{i,r}^{k}\|^{2}$ can be bounded by the true gradient $\|\nabla f({\boldsymbol{x}}_{r})\|^{2}$ on the starting point of round $r$, the local update distance $\|{\boldsymbol{x}}_{i,r}^{k}-{\boldsymbol{x}}_{r}\|^{2}$ and several constants:

$$ $\displaystyle\mathbb{E}\hskip 1.42271pt_{r}\|G_{i,r}^{k}\|^{2}\leq$ $\displaystyle\frac{6(d+P+4)}{P}\|\nabla f({\boldsymbol{x}}_{r})\|^{2}+\frac{6L^{2}(d+P+4)}{P}\mathbb{E}\hskip 1.42271pt_{r}\left\|{\boldsymbol{x}}_{i,r}^{k}-{\boldsymbol{x}}_{r}\right\|^{2}$ $\displaystyle\;\;{}+\frac{6(d+P+4)}{P}\sigma_{G}^{2}+\frac{2(d+4)}{P}\sigma^{2}+\frac{\mu^{2}L^{2}(d+6)^{3}}{2P}+\frac{1}{2}\mu^{2}L^{2}(d+3)^{3}$ (18) $$

Proof. Using Jensen’s inequality, we know

$$ $\displaystyle\mathbb{E}\hskip 1.42271pt_{r}\|G_{i,r}^{k}\|^{2}=\mathbb{E}\hskip 1.42271pt_{r}\|G_{i,r}^{k}-\nabla f_{i}^{\mu}({\boldsymbol{x}}_{i,r}^{k})\|^{2}+\mathbb{E}\hskip 1.42271pt_{r}\|\nabla f_{i}^{\mu}({\boldsymbol{x}}_{i,r}^{k})\|^{2}$ (19) $$

From Lemma [2](#Thmlemma2), we have

$$ $\displaystyle\mathbb{E}\hskip 1.42271pt_{r}\|\nabla f_{i}^{\mu}({\boldsymbol{x}}_{i,r}^{k})\|^{2}\leq$ $\displaystyle 2\mathbb{E}\hskip 1.42271pt_{r}\|\nabla f_{i}({\boldsymbol{x}}_{i,r}^{k})\|^{2}+\frac{1}{2}\mu^{2}L^{2}(d+3)^{3}$ $\displaystyle=$ $\displaystyle 2\mathbb{E}\hskip 1.42271pt_{r}\|\nabla f_{i}({\boldsymbol{x}}_{i,r}^{k})-\nabla f_{i}({\boldsymbol{x}}_{r})+\nabla f_{i}({\boldsymbol{x}}_{r})-\nabla f({\boldsymbol{x}}_{r})+\nabla f({\boldsymbol{x}}_{r})\|^{2}+\frac{1}{2}\mu^{2}L^{2}(d+3)^{3}$ $\displaystyle\leq$ $\displaystyle 6L^{2}\mathbb{E}\hskip 1.42271pt_{r}\|{\boldsymbol{x}}_{i,r}^{k}-{\boldsymbol{x}}_{r}\|^{2}+6\sigma_{G}^{2}+6\|\nabla f({\boldsymbol{x}}_{r})\|^{2}+\frac{1}{2}\mu^{2}L^{2}(d+3)^{3}$ $$

Combining with the result ([3](#A1.Ex7)), we conclude the proof of lemma.
$\hfill\blacksquare$

Furthermore, we denote $\chi_{r}=\mathbb{E}\hskip 1.42271pt_{r}\left[\frac{1}{M}\sum_{i=1}^{M}\sum_{k=1}^{K}\left\|{\boldsymbol{x}}_{i,r}^{k}-{\boldsymbol{x}}_{r}\right\|^{2}\right]$ for the local update steps, which is closely related to $\mathbb{E}\hskip 1.42271pt_{r}\|G_{i,r}^{k}\|^{2}$. Using the previous lemma, we can easily establish the upper-bound on $\chi_{r}$.

###### Lemma 5 (Bounds on local update steps)

With Assumptions [1](#Thmassumption1)-[3](#Thmassumption3) and the learning rate satisfying $\eta\leq\frac{2P}{\sqrt{6}LK\sqrt{d+P+4}}$, the local update distance $\chi_{r}$ satisfies

$$ $\displaystyle\chi_{r}\leq$ $\displaystyle\frac{6K^{3}(d+P+4)\eta^{2}}{P}\|\nabla f({\boldsymbol{x}}_{r})\|^{2}+\frac{6K^{3}(d+P+4)\eta^{2}}{2P}\sigma_{G}^{2}+\frac{2K^{3}(d+4)\eta^{2}}{P}\sigma^{2}$ $\displaystyle\;\;\;{}+\frac{\mu^{2}L^{2}K^{3}(d+6)^{3}\eta^{2}}{P}+\frac{1}{2}\mu^{2}L^{2}K^{3}(d+3)^{3}\eta^{2}$ $$

Proof. Utilizing the relationship ${\boldsymbol{x}}_{i,r}^{k}-{\boldsymbol{x}}_{r}=\eta\sum_{\tau=1}^{k}G_{i,r}^{\tau}$, we have

$$ $\displaystyle\chi_{r}=$ $\displaystyle\mathbb{E}\hskip 1.42271pt_{r}\left[\frac{\eta^{2}}{M}\sum_{i=1}^{M}\sum_{k=1}^{K}\left\|\sum_{\tau=1}^{k}G_{i,r}^{\tau}\right\|^{2}\right]$ $\displaystyle\leq$ $\displaystyle\frac{\eta^{2}}{M}\sum_{i=1}^{M}\sum_{k=1}^{K}\sum_{\tau=1}^{k}k\mathbb{E}\hskip 1.42271pt_{r}\left\|G_{i,r}^{\tau}\right\|^{2}$ $\displaystyle\leq$ $\displaystyle\frac{K^{2}\eta^{2}}{2M}\sum_{i=1}^{M}\sum_{k=1}^{K}\left\|G_{i,r}^{k}\right\|^{2},$ $$

where the last inequality holds since $\sum_{k=1}^{K}\sum_{\tau=1}^{k}kX_{\tau}=\sum_{\tau=1}^{K}(\sum_{k=\tau}^{K}k)X_{\tau}$. Substituting ([18](#A1.E18)), we get

$$ $\displaystyle\chi_{r}\leq$ $\displaystyle\frac{K^{2}\eta^{2}}{2M}\sum_{i=1}^{M}\sum_{k=1}^{K}\left(\frac{6(d+P+4)}{P}\|\nabla f({\boldsymbol{x}}_{r})\|^{2}+\frac{6L^{2}(d+P+4)}{P}\mathbb{E}\hskip 1.42271pt\left\|{\boldsymbol{x}}_{i,r}^{k}-{\boldsymbol{x}}_{r}\right\|^{2}\right.$ $\displaystyle\;\;\;\left.+\frac{6(d+P+4)}{P}\sigma_{G}^{2}+\frac{2(d+4)}{P}\sigma^{2}+\frac{\mu^{2}L^{2}(d+6)^{3}}{2P}+\frac{1}{2}\mu^{2}L^{2}(d+3)^{3}\right)$ (20) $$

Moving the term $\mathbb{E}\hskip 1.42271pt\left\|{\boldsymbol{x}}_{i,r}^{k}-{\boldsymbol{x}}_{r}\right\|^{2}$, which is $\chi_{r}$ again after the double summations, to the left hand side, we have

$$ $\displaystyle\left(1-\frac{6L^{2}K^{2}(d+P+4)\eta^{2}}{2P}\right)\chi_{r}\leq$ $\displaystyle\frac{3K^{3}(d+P+4)\eta^{2}}{P}\|\nabla f({\boldsymbol{x}}_{r})\|^{2}+\frac{3K^{3}(d+P+4)\eta^{2}}{2P}\sigma_{G}^{2}$ $\displaystyle+\frac{K^{3}(d+4)\eta^{2}}{P}\sigma^{2}+\frac{\mu^{2}L^{2}K^{3}(d+6)^{3}\eta^{2}}{2P}+\frac{1}{4}\mu^{2}L^{2}K^{3}(d+3)^{3}\eta^{2}$ (21) $$

When $\eta\leq\frac{2P}{\sqrt{6}LK\sqrt{d+P+4}}$, the coefficient on the l.h.s. is larger than $\frac{1}{2}$. Plugging back, we complete the proof of this lemma.
$\hfill\blacksquare$

Now we are ready to present the proof of main theorem with above lemmas. To ease the reference, we restate the theorem here again:

###### Theorem 3 (Restated; Standard Convergence Bound of FedDisco)

Under the assumptions [1](#Thmassumption1), [2](#Thmassumption2) and [3](#Thmassumption3), supposing that the perturbation ${\boldsymbol{z}}_{r}^{k}\sim{\mathcal{N}}(\textbf{0},{\boldsymbol{I}}_{d})$, i.e., follows the Gaussian distribution, and the learning rate satisfies $\eta\leq\min\{\frac{mP}{24L(d+4)},\frac{2P}{mKL(d+P+4)},\frac{1}{mK^{2}L},\frac{mP(d+3)^{3}}{2L[3mPK(d+3)^{3}+(d+6)^{3}]}\}$, then it holds

$$ $\displaystyle\frac{1}{R}\sum_{r=0}^{R-1}\mathbb{E}\hskip 1.42271pt_{r}\|\nabla f({\boldsymbol{x}}_{r})\|^{2}\leq$ $\displaystyle\frac{4\big{(}f({\boldsymbol{x}}_{0})-f({\boldsymbol{x}}^{\star})\big{)}}{KR\eta}+\left(\frac{72KL\eta}{m}+\frac{24(d+4)L\eta}{mP}\right)\sigma_{G}^{2}$ $\displaystyle\;\;\;+\frac{16L(d+4)\eta}{mP}\sigma^{2}+2\mu^{2}L^{2}(d+3)^{3},$ (22) $$

where ${\boldsymbol{x}}_{r}$ is the model parameter in the $r$-th round, $P$ is the number of perturbations, ${\boldsymbol{x}}^{*}$ is the optimal point, $K$ is the number of local update steps, $R$ is the number of communication rounds, $d$ is the dimension of model parameters, and $m$ is the number of sampled clients in each round.

Proof.
First, applying the $L-$Lipschitz smooth property on the global loss function $f$, we have

$$ $\displaystyle f({\boldsymbol{x}}_{r+1})\leq$ $\displaystyle f({\boldsymbol{x}}_{r})+\langle\nabla f({\boldsymbol{x}}_{r}),{\boldsymbol{x}}_{r+1}-{\boldsymbol{x}}_{r}\rangle+\frac{L}{2}\|{\boldsymbol{x}}_{r+1}-{\boldsymbol{x}}_{r}\|^{2}$ (23) $\displaystyle=$ $\displaystyle f({\boldsymbol{x}}_{r})-\eta\left\langle\nabla f({\boldsymbol{x}}_{r}),\frac{1}{m}\sum\limits_{i\in C_{r}}\sum\limits_{k=1}^{K}G_{i,r}^{k}\right\rangle+\eta^{2}\frac{L}{2}\left\|\frac{1}{m}\sum\limits_{i\in C_{r}}\sum\limits_{k=1}^{K}G_{i,r}^{k}\right\|^{2},$ (24) $$

Taking conditional expectation $\mathbb{E}\hskip 1.42271pt_{r}$ given the filtration ${\boldsymbol{x}}_{r}$ and information before round $r$, we obtain

$$ $\displaystyle\mathbb{E}\hskip 1.42271pt_{r}[f({\boldsymbol{x}}_{r+1})]\leq$ $\displaystyle f({\boldsymbol{x}}_{r})\underbrace{-\eta\mathbb{E}\hskip 1.42271pt_{r}\left\langle\nabla f({\boldsymbol{x}}_{r}),\frac{1}{m}\sum\limits_{i\in C_{r}}\sum\limits_{k=1}^{K}G_{i,r}^{k}\right\rangle}_{A_{1}}+\underbrace{\frac{L}{2}\eta^{2}\mathbb{E}\hskip 1.42271pt_{r}\left\|\frac{1}{m}\sum\limits_{i\in C_{r}}\sum\limits_{k=1}^{K}G_{i,r}^{k}\right\|^{2}}_{A_{2}}$ (25) $$

Observing $\mathbb{E}\hskip 1.42271pt_{r,\xi}\left[\frac{1}{M}\sum_{i=1}^{M}\sum_{k=1}^{K}\big{(}G_{i,r}^{k}-\nabla f_{i}^{\mu}({\boldsymbol{x}}_{i,r}^{k})\big{)}\right]=0$, the cross product term $A_{1}$ satisfies

$$ $\displaystyle A_{1}=$ $\displaystyle-K\eta\mathbb{E}\hskip 1.42271pt_{r}\left[\left\langle\nabla f({\boldsymbol{x}}_{r}),\frac{1}{MK}\sum\limits_{i=1}^{M}\sum\limits_{k=1}^{K}\nabla f_{i}^{\mu}({\boldsymbol{x}}_{i,r}^{k})\right\rangle\right]$ (26) $$

Utilizing the Parallelogram Identity, we know

$$ $\displaystyle A_{1}=$ $\displaystyle-\frac{1}{2}K\eta\|\nabla f({\boldsymbol{x}}_{r})\|^{2}-\frac{1}{2}K\eta\mathbb{E}\hskip 1.42271pt_{r}\left\|\frac{1}{MK}\sum\limits_{i=1}^{M}\sum\limits_{k=1}^{K}\nabla f_{i}^{\mu}({\boldsymbol{x}}_{i,r}^{k})\right\|^{2}$ $\displaystyle\;\;\;+\frac{1}{2}K\eta\mathbb{E}\hskip 1.42271pt_{r}\left\|\frac{1}{MK}\sum\limits_{i=1}^{M}\sum\limits_{k=1}^{K}\big{[}\nabla f_{i}^{\mu}({\boldsymbol{x}}_{i,r}^{k})-\nabla f_{i}({\boldsymbol{x}}_{r})\big{]}\right\|^{2}$ $\displaystyle\leq$ $\displaystyle-\frac{1}{2}K\eta\|\nabla f({\boldsymbol{x}}_{r})\|^{2}-\frac{1}{2}K\eta\mathbb{E}\hskip 1.42271pt_{r}\left\|\frac{1}{MK}\sum\limits_{i=1}^{M}\sum\limits_{k=1}^{K}\nabla f_{i}^{\mu}({\boldsymbol{x}}_{i,r}^{k})\right\|^{2}$ $\displaystyle\;\;\;+\frac{1}{2}K\eta\frac{1}{MK}\mathbb{E}\hskip 1.42271pt_{r}\sum\limits_{i=1}^{M}\sum\limits_{k=1}^{K}\left\|\nabla f_{i}^{\mu}({\boldsymbol{x}}_{i,r}^{k})-\nabla f_{i}({\boldsymbol{x}}_{r})\right\|^{2}$ $\displaystyle\leq$ $\displaystyle-\frac{1}{2}K\eta\|\nabla f({\boldsymbol{x}}_{r})\|^{2}-\frac{1}{2}K\eta\mathbb{E}\hskip 1.42271pt_{r}\left\|\frac{1}{MK}\sum\limits_{i=1}^{M}\sum\limits_{k=1}^{K}\nabla f_{i}^{\mu}({\boldsymbol{x}}_{i,r}^{k})\right\|^{2}$ $\displaystyle\;\;\;+\frac{\eta}{M}\mathbb{E}\hskip 1.42271pt_{r}\sum\limits_{i=1}^{M}\sum\limits_{k=1}^{K}\left\|\nabla f_{i}^{\mu}({\boldsymbol{x}}_{i,r}^{k})-\nabla f_{i}({\boldsymbol{x}}_{i,r}^{k})\right\|^{2}+\frac{\eta}{M}\mathbb{E}\hskip 1.42271pt_{r}\sum\limits_{i=1}^{M}\sum\limits_{k=1}^{K}\|\nabla f_{i}({\boldsymbol{x}}_{i,r}^{k})-\nabla f_{i}({\boldsymbol{x}}_{r})\|^{2}$ $\displaystyle\leq$ $\displaystyle-\frac{1}{2}K\eta\|\nabla f({\boldsymbol{x}}_{r})\|^{2}-\frac{1}{2}K\eta\mathbb{E}\hskip 1.42271pt_{r}\left\|\frac{1}{MK}\sum\limits_{i=1}^{M}\sum\limits_{k=1}^{K}\nabla f_{i}^{\mu}({\boldsymbol{x}}_{i,r}^{k})\right\|^{2}+\frac{1}{4}\mu^{2}KL^{2}(d+3)^{3}\eta$ $\displaystyle\;\;\;+\frac{L^{2}\eta}{M}\sum\limits_{k=1}^{K}\sum\limits_{i=1}^{M}\mathbb{E}\hskip 1.42271pt_{r}\left\|{\boldsymbol{x}}_{i,r}^{k}-{\boldsymbol{x}}_{r}\right\|^{2},$ $$

where we utilize Jensen’s Inequality in the first two inequalities and apply $L$-smoothness and [10](#A1.E10) to get the last inequality.
Next, we focus on the quadratic term $A_{2}$.

$$ $\displaystyle A_{2}=$ $\displaystyle\frac{L}{2}\eta^{2}\mathbb{E}\hskip 1.42271pt_{r}\left\|\frac{1}{m}\sum\limits_{i\in C_{r}}\sum\limits_{k=1}^{K}G_{i,r}^{k}\right\|^{2}$ $\displaystyle\leq$ $\displaystyle L\eta^{2}\mathbb{E}\hskip 1.42271pt_{r}\left\|\frac{1}{m}\sum\limits_{i\in C_{r}}\sum\limits_{k=1}^{K}[G_{i,r}^{k}-\nabla f_{i}^{\mu}({\boldsymbol{x}}_{i,r}^{k})]\right\|^{2}+L\eta^{2}\mathbb{E}\hskip 1.42271pt_{r}\left\|\frac{1}{m}\sum\limits_{i\in C_{r}}\sum\limits_{k=1}^{K}\nabla f_{i}^{\mu}({\boldsymbol{x}}_{i,r}^{k})\right\|^{2}$ $\displaystyle=$ $\displaystyle\frac{L\eta^{2}}{mM}\sum_{i=1}^{M}\sum\limits_{k=1}^{K}\mathbb{E}\hskip 1.42271pt_{r}\left\|G_{i,r}^{k}-\nabla f_{i}^{\mu}({\boldsymbol{x}}_{i,r}^{k})\right\|^{2}+L\eta^{2}\mathbb{E}\hskip 1.42271pt_{r}\left\|\frac{1}{m}\sum\limits_{i\in C_{r}}\sum\limits_{k=1}^{K}\nabla f_{i}^{\mu}({\boldsymbol{x}}_{i,r}^{k})\right\|^{2}$ $\displaystyle\leq$ $\displaystyle\frac{6L^{3}(d+4)\eta^{2}}{mMP}\sum_{i=1}^{M}\sum_{k=1}^{K}\mathbb{E}\hskip 1.42271pt_{r}\left\|{\boldsymbol{x}}_{i,r}^{k}-{\boldsymbol{x}}_{r}\right\|^{2}+\frac{KL\eta^{2}}{m}\left[\frac{6(d+4)}{P}\|\nabla f({\boldsymbol{x}}_{r})\|^{2}+\frac{6(d+4)}{P}\sigma_{G}^{2}\right]$ $\displaystyle{}+\frac{KL\eta^{2}}{m}\left[\frac{2(d+4)}{P}\sigma^{2}+\frac{\mu^{2}L^{2}(d+6)^{3}}{2P}\right]+\underbrace{L\eta^{2}\mathbb{E}\hskip 1.42271pt_{r}\left\|\frac{1}{m}\sum\limits_{i\in C_{r}}\sum\limits_{k=1}^{K}\nabla f_{i}^{\mu}({\boldsymbol{x}}_{i,r}^{k})\right\|^{2}}_{A_{3}},$ (27) $$

where we applied Jensen’s inequality in the first inequality; the second equality holds since each term $\left[G_{i,r}^{k}-\nabla f_{i}^{\mu}({\boldsymbol{x}}_{i,r}^{k})\right]$ is zero mean and independent to each other; the last inequality utilized the Lemma [3](#Thmlemma3). For $A_{3}$, it can be bounded as follows

$$ $\displaystyle A_{3}=$ $\displaystyle L\eta^{2}\mathbb{E}\hskip 1.42271pt_{r}\left\|\frac{1}{m}\sum\limits_{i\in C_{r}}\sum\limits_{k=1}^{K}\nabla f_{i}^{\mu}({\boldsymbol{x}}_{i,r}^{k})\right\|^{2}$ $\displaystyle=$ $\displaystyle L\eta^{2}\mathbb{E}\hskip 1.42271pt_{r}\left\|\frac{1}{M}\sum\limits_{i=1}^{M}\sum\limits_{k=1}^{K}\nabla f_{i}^{\mu}({\boldsymbol{x}}_{i,r}^{k})\right\|^{2}+L\eta^{2}\underbrace{\mathbb{E}\hskip 1.42271pt_{r}\left\|\frac{1}{m}\sum\limits_{i\in C_{r}}\sum\limits_{k=1}^{K}\nabla f_{i}^{\mu}({\boldsymbol{x}}_{i,r}^{k})-\frac{1}{M}\sum\limits_{i=1}^{M}\sum\limits_{k=1}^{K}\nabla f_{i}^{\mu}({\boldsymbol{x}}_{i,r}^{k})\right\|^{2}}_{A_{4}}$ (28) $$

Continuing bounding the $A_{4}$ term, we have

$$ $\displaystyle A_{4}=$ $\displaystyle\mathbb{E}\hskip 1.42271pt_{r}\left\|\frac{1}{m}\sum\limits_{i\in C_{r}}\sum\limits_{k=1}^{K}\nabla f_{i}^{\mu}({\boldsymbol{x}}_{i,r}^{k})-\frac{1}{M}\sum\limits_{i=1}^{M}\sum\limits_{k=1}^{K}\nabla f_{i}^{\mu}({\boldsymbol{x}}_{i,r}^{k})\right\|^{2}$ (29) $\displaystyle\stackrel{{\scriptstyle(a)}}{{\leq}}\;$ $\displaystyle 3\mathbb{E}\hskip 1.42271pt_{r}\left\|\frac{1}{m}\sum\limits_{i\in C_{r}}\sum\limits_{k=1}^{K}\left[\nabla f_{i}^{\mu}({\boldsymbol{x}}_{i,r}^{k})-\nabla f_{i}({\boldsymbol{x}}_{i,r}^{k})\right]\right\|^{2}$ $\displaystyle\;\;\;+3\mathbb{E}\hskip 1.42271pt_{r}\left\|\frac{1}{m}\sum\limits_{i\in C_{r}}\sum\limits_{k=1}^{K}\nabla f_{i}({\boldsymbol{x}}_{i,r}^{k})-\frac{1}{M}\sum\limits_{i=1}^{M}\sum\limits_{k=1}^{K}\nabla f_{i}({\boldsymbol{x}}_{i,r}^{k})\right\|^{2}$ $\displaystyle\;\;\;+3\mathbb{E}\hskip 1.42271pt_{r}\left\|\frac{1}{M}\sum\limits_{i=1}^{M}\sum\limits_{k=1}^{K}\left[\nabla f_{i}({\boldsymbol{x}}_{i,r}^{k})-\nabla f_{i}^{\mu}({\boldsymbol{x}}_{i,r}^{k})\right]\right\|^{2}$ $\displaystyle\stackrel{{\scriptstyle(b)}}{{\leq}}\;$ $\displaystyle\frac{3}{2}\mu^{2}K^{2}L^{2}(d+3)^{3}+\underbrace{3\mathbb{E}\hskip 1.42271pt_{r}\left\|\frac{1}{m}\sum\limits_{i\in C_{r}}\sum\limits_{k=1}^{K}\nabla f_{i}({\boldsymbol{x}}_{i,r}^{k})-\frac{1}{M}\sum\limits_{i=1}^{M}\sum\limits_{k=1}^{K}\nabla f_{i}({\boldsymbol{x}}_{i,r}^{k})\right\|^{2}}_{A_{5}},$ (30) $$

where in the step (a), we plus and minus the $\frac{1}{m}\sum\limits_{i\in C_{r}}\sum\limits_{k=1}^{K}\nabla f_{i}({\boldsymbol{x}}_{i,r}^{k})$ and $\frac{1}{M}\sum\limits_{i=1}^{M}\sum\limits_{k=1}^{K}\nabla f_{i}({\boldsymbol{x}}_{i,r}^{k})$ then applies Jensen’s inequality; in the step (b), we restore to the lemma [2](#Thmlemma2) on the first and last terms. Next, we use the similar trick to bound $A_{5}$:

$$ $\displaystyle A_{5}=$ $\displaystyle 3\mathbb{E}\hskip 1.42271pt_{r}\Bigg{\|}\frac{1}{m}\sum\limits_{i\in C_{r}}\sum\limits_{k=1}^{K}\nabla f_{i}({\boldsymbol{x}}_{i,r}^{k})-\frac{1}{m}\sum\limits_{i\in C_{r}}\sum\limits_{k=1}^{K}\nabla f_{i}({\boldsymbol{x}}_{r})+\frac{1}{m}\sum\limits_{i\in C_{r}}\sum\limits_{k=1}^{K}\nabla f_{i}({\boldsymbol{x}}_{r})$ $\displaystyle\;\;\;-\frac{1}{M}\sum\limits_{i=1}^{M}\sum\limits_{k=1}^{K}\nabla f_{i}({\boldsymbol{x}}_{r})+\frac{1}{M}\sum\limits_{i=1}^{M}\sum\limits_{k=1}^{K}\nabla f_{i}({\boldsymbol{x}}_{r})-\frac{1}{M}\sum\limits_{i=1}^{M}\sum\limits_{k=1}^{K}\nabla f_{i}({\boldsymbol{x}}_{i,r}^{k})\Bigg{\|}^{2}$ $\displaystyle\stackrel{{\scriptstyle(a)}}{{\leq}}$ $\displaystyle 9\mathbb{E}\hskip 1.42271pt_{r}\left\|\frac{1}{m}\sum\limits_{i\in C_{r}}\sum\limits_{k=1}^{K}\left[\nabla f_{i}({\boldsymbol{x}}_{i,r}^{k})-\nabla f_{i}({\boldsymbol{x}}_{r})\right]\right\|^{2}+9\mathbb{E}\hskip 1.42271pt_{r}\left\|\frac{1}{m}\sum\limits_{i\in C_{r}}\sum\limits_{k=1}^{K}\nabla f_{i}({\boldsymbol{x}}_{r})-\frac{1}{M}\sum\limits_{i=1}^{M}\sum\limits_{k=1}^{K}\nabla f_{i}({\boldsymbol{x}}_{r})\right\|^{2}$ $\displaystyle\;\;+9\mathbb{E}\hskip 1.42271pt_{r}\left\|\frac{1}{M}\sum\limits_{i=1}^{M}\sum\limits_{k=1}^{K}\left[\nabla f_{i}({\boldsymbol{x}}_{r})-\nabla f_{i}({\boldsymbol{x}}_{i,r}^{k})\right]\right\|^{2}$ $\displaystyle\stackrel{{\scriptstyle(b)}}{{\leq}}$ $\displaystyle 18KL^{2}\mathbb{E}\hskip 1.42271pt_{r}\left[\frac{1}{M}\sum_{i=1}^{M}\sum_{k=1}^{K}\left\|{\boldsymbol{x}}_{i,r}^{k}-{\boldsymbol{x}}_{r}\right\|^{2}\right]+9K^{2}\mathbb{E}\hskip 1.42271pt_{r}\left\|\frac{1}{m}\sum_{i\in C_{r}}\left[\nabla f_{i}({\boldsymbol{x}}_{r})-\nabla f({\boldsymbol{x}}_{r})\right]\right\|^{2}$ $\displaystyle\stackrel{{\scriptstyle(c)}}{{=}}$ $\displaystyle 18KL^{2}\mathbb{E}\hskip 1.42271pt_{r}\left[\frac{1}{M}\sum_{i=1}^{M}\sum_{k=1}^{K}\left\|{\boldsymbol{x}}_{i,r}^{k}-{\boldsymbol{x}}_{r}\right\|^{2}\right]+\frac{9K^{2}}{m^{2}}\mathbb{E}\hskip 1.42271pt_{r}\sum_{i\in C_{r}}\left\|\nabla f_{i}({\boldsymbol{x}}_{r})-\nabla f({\boldsymbol{x}}_{r})\right\|^{2}$ $\displaystyle\stackrel{{\scriptstyle(d)}}{{\leq}}$ $\displaystyle 18KL^{2}\mathbb{E}\hskip 1.42271pt_{r}\left[\frac{1}{M}\sum_{i=1}^{M}\sum_{k=1}^{K}\left\|{\boldsymbol{x}}_{i,r}^{k}-{\boldsymbol{x}}_{r}\right\|^{2}\right]+\frac{9K^{2}}{m}\sigma_{G}^{2},$ $$

where step (a) applies Jensen’s inequality; step (b) utilizes the $L-$Lipschitze condition; the equality in step (c) holds because each term $\left[\nabla f_{i}({\boldsymbol{x}}_{r})-\nabla f_{i}({\boldsymbol{x}}_{i,r}^{k})\right]$ is independent and zero-mean; step (d) results from the data heterogeneous assumption.

Plugging $A_{4}$ and $A_{5}$ into $A_{3}$, we establish

$$ $\displaystyle A_{3}\leq$ $\displaystyle L\eta^{2}\mathbb{E}\hskip 1.42271pt_{r}\left\|\frac{1}{M}\sum\limits_{i=1}^{M}\sum\limits_{k=1}^{K}\nabla f_{i}^{\mu}({\boldsymbol{x}}_{i,r}^{k})\right\|^{2}+\frac{3}{2}\mu^{2}K^{2}L^{3}(d+3)^{3}\eta^{2}$ $\displaystyle{}+18KL^{3}\eta^{2}\mathbb{E}\hskip 1.42271pt_{r}\left[\frac{1}{M}\sum_{i=1}^{M}\sum_{k=1}^{K}\left\|{\boldsymbol{x}}_{i,r}^{k}-{\boldsymbol{x}}_{r}\right\|^{2}\right]+\frac{9K^{2}L\eta^{2}}{m}\sigma_{G}^{2}$ (31) $$

Now, we are ready to put $A_{3}$ back to $A_{2}$ and group the terms

$$ $\displaystyle A_{2}\leq$ $\displaystyle\frac{6KL(d+4)\eta^{2}}{mP}\|\nabla f({\boldsymbol{x}}_{r})\|^{2}+\frac{6L^{3}(d+4)\eta^{2}}{mMP}\sum_{i=1}^{M}\sum_{k=1}^{K}\mathbb{E}\hskip 1.42271pt_{r}\left\|{\boldsymbol{x}}_{i,r}^{k}-{\boldsymbol{x}}_{r}\right\|^{2}$ $\displaystyle{}+\frac{6KL(d+4)\eta^{2}}{mP}\sigma_{G}^{2}+\frac{2KL(d+4)\eta^{2}}{mP}\sigma^{2}+\frac{\mu^{2}KL^{3}(d+6)^{3}\eta^{2}}{2mP}$ $\displaystyle{}+18KL^{3}\eta^{2}\mathbb{E}\hskip 1.42271pt_{r}\left[\frac{1}{M}\sum_{i=1}^{M}\sum_{k=1}^{K}\left\|{\boldsymbol{x}}_{i,r}^{k}-{\boldsymbol{x}}_{r}\right\|^{2}\right]+\frac{3}{2}\mu^{2}K^{2}L^{3}(d+3)^{3}\eta^{2}+\frac{9K^{2}L\eta^{2}}{m}\sigma_{G}^{2}$ $\displaystyle{}+L\eta^{2}\mathbb{E}\hskip 1.42271pt_{r}\left\|\frac{1}{M}\sum\limits_{i=1}^{M}\sum\limits_{k=1}^{K}\nabla f_{i}^{\mu}({\boldsymbol{x}}_{i,r}^{k})\right\|^{2}$ (32) $$

Combining all pieces and denoting $\chi_{r}=\mathbb{E}\hskip 1.42271pt_{r}\left[\frac{1}{M}\sum\limits_{i=1}^{M}\sum\limits_{k=1}^{K}\left\|{\boldsymbol{x}}_{i,r}^{k}-{\boldsymbol{x}}_{r}\right\|^{2}\right]$, we have

$$ $\displaystyle\mathbb{E}\hskip 1.42271pt_{r}[f({\boldsymbol{x}}_{r+1})]\leq$ $\displaystyle f({\boldsymbol{x}}_{r})-\frac{1}{2}K\eta\|\nabla f({\boldsymbol{x}}_{r})\|^{2}-\frac{1}{2}K\eta\mathbb{E}\hskip 1.42271pt_{r}\left\|\frac{1}{MK}\sum\limits_{i=1}^{M}\sum\limits_{k=1}^{K}\nabla f_{i}^{\mu}({\boldsymbol{x}}_{i,r}^{k})\right\|^{2}+\frac{1}{4}\mu^{2}KL^{2}(d+3)^{3}\eta$ $\displaystyle{}+L^{2}\eta\chi_{r}+\frac{6(d+4)LK\eta^{2}}{mP}\|\nabla f({\boldsymbol{x}}_{r})\|^{2}+\frac{6L^{3}(d+4)\eta^{2}}{mP}\chi_{r}$ $\displaystyle{}+\frac{6(d+4)LK\eta^{2}}{mP}\sigma_{G}^{2}+\frac{2(d+4)LK\eta^{2}}{mP}\sigma^{2}+\frac{\mu^{2}(d+6)^{3}L^{3}K\eta^{2}}{2mP}$ $\displaystyle{}+18KL^{3}\eta^{2}\chi_{r}+\frac{3}{2}\mu^{2}K^{2}L^{3}\eta^{2}(d+3)^{3}$ $\displaystyle{}+\frac{9K^{2}L\eta^{2}}{m}\sigma_{G}^{2}+L\eta^{2}\mathbb{E}\hskip 1.42271pt_{r}\left\|\frac{1}{M}\sum\limits_{i=1}^{M}\sum\limits_{k=1}^{K}\nabla f_{i}^{\mu}({\boldsymbol{x}}_{i,r}^{k})\right\|^{2}$ (33) $\displaystyle\leq$ $\displaystyle f({\boldsymbol{x}}_{r})-\left(\frac{1}{2}K\eta-\frac{6(d+4)LK\eta^{2}}{mP}\right)\|\nabla f({\boldsymbol{x}}_{r})\|^{2}+\frac{1}{4}\mu^{2}KL^{2}(d+3)^{3}\eta$ $\displaystyle{}+\left(L^{2}\eta+\frac{6L^{3}(d+4)\eta^{2}}{mP}+18KL^{3}\eta^{2}\right)\chi_{r}+\frac{2KL(d+4)\eta^{2}}{mP}\sigma^{2}$ $\displaystyle{}+\left(\frac{9K^{2}L\eta^{2}}{m}+\frac{6(d+4)LK\eta^{2}}{mP}\right)\sigma_{G}^{2}+\frac{\mu^{2}KL^{3}(d+6)^{3}\eta^{2}}{2mP}+\frac{3}{2}\mu^{2}K^{2}L^{3}(d+3)^{3}\eta^{2}$ (34) $$

Plugging lemma [5](#Thmlemma5) into [34](#A1.E34) and following $\eta\leq\min\{\frac{mP}{24L(d+4)},\frac{2P}{mKL(d+P+4)},\frac{1}{mK^{2}L},\frac{mP(d+3)^{3}}{2L[3mPK(d+3)^{3}+(d+6)^{3}]}\}$, we can further simplified it into

$$ $\displaystyle\mathbb{E}\hskip 1.42271pt_{r}[f({\boldsymbol{x}}_{r+1})]\leq$ $\displaystyle f({\boldsymbol{x}}_{r})-\frac{1}{4}K\eta\|\nabla f({\boldsymbol{x}}_{r})\|^{2}+\left(\frac{18K^{2}L\eta^{2}}{m}+\frac{6(d+4)LK\eta^{2}}{mP}\right)\sigma_{G}^{2}$ $\displaystyle+\frac{4KL(d+4)\eta^{2}}{mP}\sigma^{2}+\frac{1}{2}\mu^{2}KL^{2}(d+3)^{3}\eta$ (35) $$

Rearranging the terms, we have

$$ $\displaystyle\frac{1}{4}K\eta\|\nabla f({\boldsymbol{x}}_{r})\|^{2}\leq$ $\displaystyle f({\boldsymbol{x}}_{r})-\mathbb{E}\hskip 1.42271pt_{r}[f({\boldsymbol{x}}_{r+1})]+\left(\frac{18K^{2}L\eta^{2}}{m}+\frac{6(d+4)LK\eta^{2}}{mP}\right)\sigma_{G}^{2}$ $\displaystyle+\frac{4KL(d+4)\eta^{2}}{mP}\sigma^{2}+\frac{1}{2}\mu^{2}KL^{2}(d+3)^{3}\eta$ (36) $$

Dividing $\frac{1}{4}K\eta$ on both sides, then we get

$$ $\displaystyle\|\nabla f({\boldsymbol{x}}_{r})\|^{2}\leq$ $\displaystyle\frac{4}{K\eta}\Big{(}f({\boldsymbol{x}}_{r})-\mathbb{E}\hskip 1.42271pt_{r}[f({\boldsymbol{x}}_{r+1})]\Big{)}+\left(\frac{72KL\eta}{m}+\frac{24(d+4)L\eta}{mP}\right)\sigma_{G}^{2}$ $\displaystyle+\frac{16L(d+4)\eta}{mP}\sigma^{2}+2\mu^{2}L^{2}(d+3)^{3}$ (37) $$

Recursively executing ([37](#A1.E37)) $R$ rounds, we can obtain

$$ $\displaystyle\frac{1}{R}\sum_{r=0}^{R-1}\mathbb{E}\hskip 1.42271pt_{r}\|\nabla f({\boldsymbol{x}}_{r})\|^{2}\leq$ $\displaystyle\frac{4\big{(}f({\boldsymbol{x}}_{0})-f({\boldsymbol{x}}^{*})\big{)}}{KR\eta}+\left(\frac{72KL\eta}{m}+\frac{24(d+4)L\eta}{mP}\right)\sigma_{G}^{2}$ $\displaystyle+\frac{16L(d+4)\eta}{mP}\sigma^{2}+2\mu^{2}L^{2}(d+3)^{3}$ (38) $$

$\hfill\blacksquare$

###### Lemma 3 (Bounds on the stochastic zeroth-order gradient variance)

###### Lemma 4 (Bounds on the stochastic zeroth-order gradient second-order moments)

###### Lemma 5 (Bounds on local update steps)

###### Theorem 3 (Restated; Standard Convergence Bound of FedDisco)

### A.4 Proof of theorem 2

In this section, we only consider the case that local update step $K=1$, so we ignore superscript $k$ in this proof. The following proof is inspired by the MeZO work [] and extends the proof for the multiple-client case. In [], they directly utilized the following form of the effective zeroth-order gradient:

$$ $\displaystyle\hat{\nabla}f({\boldsymbol{x}}_{r};\xi_{r})=$ $\displaystyle\frac{1}{mP}\sum_{i\in C_{r}}\sum_{p=1}^{P}{\boldsymbol{z}}_{r,p}{\boldsymbol{z}}_{r,p}^{\top}\nabla f_{i}({\boldsymbol{x}}_{r};\xi_{i,r})$ (39) $$

However, this form is just a approximation and only holds when $\mu\to 0$, which makes the claim in [] is not strictly correct. Fortunately, leveraging the basic lemma stated in the previous section and using the mean value theorem, we can fix the proof. Using the mean-value theorem, we know

$$ $\displaystyle\frac{1}{\mu}\left(f_{i}({\boldsymbol{x}}_{r}+\mu{\boldsymbol{z}}_{r,p};\xi_{i,r})-f_{i}({\boldsymbol{x}}_{r};\xi_{i,r})\right)={\boldsymbol{z}}_{r,p}^{\top}\nabla f_{i}({\boldsymbol{x}}_{r}^{\prime};\xi_{i,r})$ (40) $$

where ${\boldsymbol{x}}_{r}^{\prime}={\boldsymbol{x}}_{r}+\mu\theta{\boldsymbol{z}}_{r,p}$ for some $\theta\in[0,1]$ (we do not need to what value the $\theta$ is). So that the effective zeroth-order gradient we utilized is

$$ $\displaystyle\hat{\nabla}f({\boldsymbol{x}}_{r};\xi_{r})=$ $\displaystyle\frac{1}{mP}\sum_{i\in C_{r}}\sum_{p=1}^{P}{\boldsymbol{z}}_{r,p}{\boldsymbol{z}}_{r,p}^{\top}\nabla f_{i}({\boldsymbol{x}}_{r}^{\prime};\xi_{i,r})$ (41) $$

Another fix for the proof in [] is noticing the conditional expectation of the stochastic zeroth-order gradient is unbiased to the smooth function

$$ $\displaystyle\mathbb{E}\hskip 1.42271pt_{r}\hat{\nabla}f({\boldsymbol{x}}_{r};\xi_{r})=\mathbb{E}\hskip 1.42271pt_{r}\frac{1}{m}\sum_{i\in C_{r}}\nabla f^{\mu}_{i}({\boldsymbol{x}}_{r})=\nabla f^{\mu}({\boldsymbol{x}}_{r})$ (42) $$

Notice it is not unbiased to the gradient of original function, i.e., $\mathbb{E}\hskip 1.42271pt_{r}\hat{\nabla}f({\boldsymbol{x}}_{r};\xi_{r})\neq\nabla f({\boldsymbol{x}}_{r})$, in general.
The covariance matrix of $\hat{\nabla}f({\boldsymbol{x}}_{r};\xi_{r})$ has the following relationship.

###### Lemma 6

The covariance matrix of the stochastic zeroth-order gradient is equivalent to

$$ $\displaystyle\mathbb{E}\hskip 1.42271pt\left[\hat{\nabla}f({\boldsymbol{x}}_{r};\xi_{r})\hat{\nabla}f({\boldsymbol{x}}_{r};\xi_{r})^{\top}\right]=$ $\displaystyle\frac{d}{P(d+2)}\left(\|\nabla f({\boldsymbol{x}}_{r}^{\prime})\|^{2}+\frac{1}{m}\mbox{\rm{\small Tr}}(\Sigma_{r})+\frac{1}{m}\mbox{\rm{\small Tr}}(\Delta_{f,r})\right)\cdot{\boldsymbol{I}}$ $\displaystyle\;\;\;{}+\left(1+\frac{d-2}{P(d+2)}\right)\left(\nabla f({\boldsymbol{x}}_{r}^{\prime})\nabla f({\boldsymbol{x}}_{r}^{\prime})^{\top}+\frac{1}{m}\Sigma_{r}+\frac{1}{m}\Delta_{f,r}\right)$ (43) $$

where the stochastic gradient noise denoted as ${\boldsymbol{s}}_{i,r}=\nabla f_{i}({\boldsymbol{x}}_{r}^{\prime})-\nabla f^{\mu}_{i}({\boldsymbol{x}}_{r})$, $d$ is the dimension of model parameters and $P$ is the number of perturbations and the definition of $\Sigma_{r}$ and $\Delta_{f,r}$ is

$$ $\displaystyle\Sigma_{r}=$ $\displaystyle\frac{1}{M}\sum_{i=1}^{M}{\boldsymbol{s}}_{i,r}{\boldsymbol{s}}_{i,r}^{\top}$ (44) $\displaystyle\Delta_{f,r}=$ $\displaystyle\nabla f({\boldsymbol{x}}_{r}^{\prime})\nabla f({\boldsymbol{x}}_{r}^{\prime})^{\top}-\frac{1}{M}\sum_{i=1}^{M}\nabla f_{i}({\boldsymbol{x}}_{r}^{\prime})\nabla f_{i}({\boldsymbol{x}}_{r}^{\prime})^{\top}$ (45) $$

Proof. Substituting the definition of $\hat{\nabla}f({\boldsymbol{x}}_{r};\xi_{r})$ into the covariance matrix, we obtain

$$ $\displaystyle\mathbb{E}\hskip 1.42271pt\left[\hat{\nabla}f({\boldsymbol{x}}_{r};\xi_{r})\hat{\nabla}f({\boldsymbol{x}}_{r};\xi_{r})^{\top}\right]=$ $\displaystyle\underbrace{\mathbb{E}\hskip 1.42271pt\left[\frac{1}{m^{2}P^{2}}\sum_{i,i^{\prime}\in C_{r}}\sum_{p,p^{\prime}=1}^{P}{\boldsymbol{z}}_{p}{\boldsymbol{z}}_{p}^{\top}\nabla f_{i}({\boldsymbol{x}}_{r}^{\prime})\nabla f_{i^{\prime}}({\boldsymbol{x}}_{r}^{\prime})^{\top}{\boldsymbol{z}}_{p^{\prime}}{\boldsymbol{z}}_{p^{\prime}}^{\top}\right]}_{:=T_{1}}$ $\displaystyle\;\;\;{}+\underbrace{\mathbb{E}\hskip 1.42271pt\left[\frac{1}{m^{2}P^{2}}\sum_{i,i^{\prime}\in C_{r}}\sum_{p,p^{\prime}=1}^{P}{\boldsymbol{z}}_{p}{\boldsymbol{z}}_{p}^{\top}{\boldsymbol{s}}_{i,r}{\boldsymbol{s}}_{i,r}^{\top}{\boldsymbol{z}}_{p^{\prime}}{\boldsymbol{z}}_{p^{\prime}}^{\top}\right]}_{:=T_{2}}$ (46) $$

where we dropped the cross term due to the zero mean and independent properties. For the proof here only, unlike $\mathbb{E}\hskip 1.42271pt_{r}$, the notation $\mathbb{E}\hskip 1.42271pt_{x}$ means the expectation with respect to $x$ instead of the given condition on $x$ or filtration before $x$. Note that

$$ $\displaystyle\mathbb{E}\hskip 1.42271pt_{i,i^{\prime}}\sum_{i,i^{\prime}\in C_{r}}\nabla f_{i}({\boldsymbol{x}}_{r}^{\prime})\nabla f_{i^{\prime}}({\boldsymbol{x}}_{r}^{\prime})^{\top}$ $\displaystyle=$ $\displaystyle(m^{2}-m)\nabla f({\boldsymbol{x}}_{r}^{\prime})\nabla f({\boldsymbol{x}}_{r}^{\prime})^{\top}+\frac{m}{M}\sum_{i=1}^{M}\nabla f_{i}({\boldsymbol{x}}_{r}^{\prime})\nabla f_{i}({\boldsymbol{x}}_{r}^{\prime})^{\top}$ $\displaystyle=$ $\displaystyle m^{2}\nabla f({\boldsymbol{x}}_{r}^{\prime})\nabla f({\boldsymbol{x}}_{r}^{\prime})^{\top}+m\underbrace{\left(\nabla f({\boldsymbol{x}}_{r}^{\prime})\nabla f({\boldsymbol{x}}_{r}^{\prime})^{\top}-\frac{1}{M}\sum_{i=1}^{M}\nabla f_{i}({\boldsymbol{x}}_{r}^{\prime})\nabla f_{i}({\boldsymbol{x}}_{r}^{\prime})^{\top}\right)}_{:=\Delta_{f,r}}$ (47) $$

(The real randomness comes from $C_{r}$ instead of $i,i^{\prime}$. Here $\mathbb{E}\hskip 1.42271pt_{i,i^{\prime}}$ is just for simplicity.) We don’t know what $\Delta_{f,r}$ is, but it can be bounded that

$$ $\displaystyle\mbox{\rm{\small Tr}}(\Delta_{f,r})=\|\nabla f({\boldsymbol{x}}_{r}^{\prime})\|^{2}-\frac{1}{M}\sum_{i=1}^{M}\left\|\nabla f_{i}({\boldsymbol{x}}_{r}^{\prime})\right\|^{2}=\frac{1}{M}\sum_{i=1}^{M}\left\|\nabla f({\boldsymbol{x}}_{r}^{\prime})-\nabla f_{i}({\boldsymbol{x}}_{r}^{\prime})\right\|^{2}\leq\sigma_{G}^{2}$ (48) $$

Focusing on the first term $T_{1}$, we have

$$ $\displaystyle T_{1}=$ $\displaystyle\frac{P-1}{m^{2}P}\mathbb{E}\hskip 1.42271pt_{i,i^{\prime}}\sum_{i,i^{\prime}\in C_{r}}\nabla f_{i}({\boldsymbol{x}}_{r}^{\prime})\nabla f_{i^{\prime}}({\boldsymbol{x}}_{r}^{\prime})^{\top}$ $\displaystyle\;\;\;{}+\frac{1}{m^{2}P^{2}}\mathbb{E}\hskip 1.42271pt_{i,i^{\prime}}\sum_{i,i^{\prime}\in C_{r}}\mathbb{E}\hskip 1.42271pt_{{\boldsymbol{z}}_{p}}\sum_{p=1}^{P}{\boldsymbol{z}}_{p}{\boldsymbol{z}}_{p}^{\top}\nabla f_{i}({\boldsymbol{x}}_{r}^{\prime})\nabla f_{i^{\prime}}({\boldsymbol{x}}_{r}^{\prime})^{\top}{\boldsymbol{z}}_{p}{\boldsymbol{z}}_{p}^{\top}$ $\displaystyle=$ $\displaystyle\frac{P-1}{P}\nabla f({\boldsymbol{x}}_{r}^{\prime})\nabla f({\boldsymbol{x}}_{r}^{\prime})^{\top}+\frac{P-1}{mP}\Delta_{f,r}+\frac{1}{P^{2}}\mathbb{E}\hskip 1.42271pt_{{\boldsymbol{z}}_{p}}\sum_{p=1}^{P}{\boldsymbol{z}}_{p}{\boldsymbol{z}}_{p}^{\top}\nabla f({\boldsymbol{x}}_{r}^{\prime})\nabla f({\boldsymbol{x}}_{r}^{\prime})^{\top}{\boldsymbol{z}}_{p}{\boldsymbol{z}}_{p}^{\top}$ $\displaystyle\;\;\;{}+\frac{1}{mP^{2}}\mathbb{E}\hskip 1.42271pt_{{\boldsymbol{z}}_{p}}\sum_{p=1}^{P}{\boldsymbol{z}}_{p}{\boldsymbol{z}}_{p}^{\top}\Delta_{f,r}{\boldsymbol{z}}_{p}{\boldsymbol{z}}_{p}^{\top}$ $\displaystyle=$ $\displaystyle\frac{P-1}{P}\nabla f({\boldsymbol{x}}_{r}^{\prime})\nabla f({\boldsymbol{x}}_{r}^{\prime})^{\top}+\frac{P-1}{mP}\Delta_{f,r}+\frac{d}{P(d+2)}\|\nabla f({\boldsymbol{x}}_{r}^{\prime})\|^{2}{\boldsymbol{I}}+\frac{2d}{P(d+2)}\nabla f({\boldsymbol{x}}_{r}^{\prime})\nabla f({\boldsymbol{x}}_{r}^{\prime})^{\top}$ $\displaystyle\;\;\;{}+\frac{d}{mP(d+2)}\mbox{\rm{\small Tr}}(\Delta_{f,r}){\boldsymbol{I}}+\frac{2d}{mP(d+2)}\Delta_{f,r}$ $$

where the first equality is split according to $p=p^{\prime}$ and $p\neq p^{\prime}$, and we plug in the established result ([47](#A1.E47)) into the second equality, the third one is because of the properties of uniform distribution or see the proof of lemma 2 in [].
Next the stochastic gradient noise satisfies

$$ $\displaystyle\mathbb{E}\hskip 1.42271pt_{i,i^{\prime}}\sum_{i,i^{\prime}\in C_{r}}{\boldsymbol{s}}_{i,r}{\boldsymbol{s}}_{i,r}^{\top}=\frac{m}{M}\sum_{i=1}^{M}{\boldsymbol{s}}_{i,r}{\boldsymbol{s}}_{i,r}^{\top}:=m{\Sigma}_{r},\;\;\;\;\;\;{\rm where}\;\;\mbox{\rm{\small Tr}}({\Sigma}_{r})\leq\sigma^{2}.$ (49) $$

The second term $T_{2}$ is similar but easier:

$$ $\displaystyle T_{2}=$ $\displaystyle\frac{1}{mP^{2}}\mathbb{E}\hskip 1.42271pt_{{\boldsymbol{z}}_{p},{\boldsymbol{z}}_{p}^{\prime}}\sum_{p,p^{\prime}=1}^{P}{\boldsymbol{z}}_{p}{\boldsymbol{z}}_{p}^{\top}\Sigma_{r}{\boldsymbol{z}}_{p^{\prime}}{\boldsymbol{z}}_{p^{\prime}}^{\top}$ $\displaystyle=$ $\displaystyle\frac{P-1}{mP}\Sigma_{r}+\frac{d}{mP(d+2)}\Big{(}\mbox{\rm{\small Tr}}(\Sigma_{r}){\boldsymbol{I}}+2\Sigma_{r}\Big{)}$ (50) $$

Combining the result $T_{1}$ and $T_{2}$, we establish

$$ $\displaystyle\mathbb{E}\hskip 1.42271pt\left[\hat{\nabla}f({\boldsymbol{x}}_{r};\xi_{r})\hat{\nabla}f({\boldsymbol{x}}_{r}^{\prime};\xi_{r})^{\top}\right]=$ $\displaystyle\frac{d}{P(d+2)}\left(\|\nabla f({\boldsymbol{x}}_{r}^{\prime})\|^{2}+\frac{1}{m}\mbox{\rm{\small Tr}}(\Sigma_{r})+\frac{1}{m}\mbox{\rm{\small Tr}}(\Delta_{f,r})\right)\cdot{\boldsymbol{I}}$ $\displaystyle\;\;\;{}+\frac{P-1}{P}\left(\nabla f({\boldsymbol{x}}_{r}^{\prime})\nabla f({\boldsymbol{x}}_{r}^{\prime})^{\top}+\frac{1}{m}\Delta_{f,r}+\frac{1}{m}\Sigma_{r}\right)$ $\displaystyle\;\;\;{}+\frac{2d}{P(d+2)}\left(\nabla f({\boldsymbol{x}}_{r}^{\prime})\nabla f({\boldsymbol{x}}_{r}^{\prime})^{\top}+\frac{1}{m}\Delta_{f,r}+\frac{1}{m}\Sigma_{r}\right)$ $$

Regrouping the terms and simplified the coefficients concludes the proof of this lemma. $\hfill\blacksquare$

To ease the reference, we restate the Theorem here again.

###### Theorem 4 (Restated; Convergence of FedDisco with $\kappa$ -Effective Rank)

Under the assumptions [1](#Thmassumption1), [2](#Thmassumption2), [3](#Thmassumption3) and [4](#Thmassumption4), supposing $\eta\leq\frac{1}{L}\left(1+\frac{d\kappa+d-2}{P(d+2)}\right)^{-1}$ and drawing ${\boldsymbol{z}}_{i}^{r}$ from the unit ball with radius $\sqrt{d}$, it holds

$$ $\displaystyle\frac{1}{R}\sum_{r=0}^{R-1}\mathbb{E}\hskip 1.42271pt\|\nabla f({\boldsymbol{x}}_{r})\|^{2}\leq$ $\displaystyle\;\frac{4(f({\boldsymbol{x}}_{0})-f({\boldsymbol{x}}^{\star}))}{R\eta}+\frac{2L\eta}{m}\left(1+\frac{d\kappa+d-2}{P(d+2)}\right)(\sigma_{G}^{2}+\sigma^{2})$ $\displaystyle\;\;{}+\frac{1}{4}\mu^{2}L^{2}(d+3)^{3}\eta+\mu^{2}L^{3}d\eta^{2}+\frac{4\mu^{2}Ld}{R\eta}.\hfill$ $$

Proof. Taking the conditional expectation over the recursion of the smooth function $f^{\mu}$ (we should not use $f$ since the unbiased property):

$$ $\displaystyle\mathbb{E}\hskip 1.42271pt_{r}[f^{\mu}({\boldsymbol{x}}_{r+1})]$ $\displaystyle\leq$ $\displaystyle f^{\mu}({\boldsymbol{x}}_{r})-\eta\|\nabla f^{\mu}({\boldsymbol{x}}_{r})\|^{2}+\frac{\eta^{2}}{2}\left\langle\boldsymbol{H}(x_{r}),\mathbb{E}\hskip 1.42271pt\left[\hat{\nabla}f({\boldsymbol{x}}_{r};\xi_{r})\hat{\nabla}f({\boldsymbol{x}}_{r};\xi_{r})^{\top}\right]\right\rangle$ $\displaystyle=$ $\displaystyle f^{\mu}({\boldsymbol{x}}_{r})-\eta\|\nabla f^{\mu}({\boldsymbol{x}}_{r})\|^{2}+\frac{\eta^{2}}{2}\cdot\frac{d}{P(d+2)}\left(\|\nabla f({\boldsymbol{x}}_{r}^{\prime})\|^{2}+\frac{1}{m}\mbox{\rm{\small Tr}}(\Sigma_{r})+\mbox{\rm{\small Tr}}(\Delta_{f,r})\right)\mbox{\rm{\small Tr}}(\boldsymbol{H}(x_{r}))$ $\displaystyle\;\;\;{}+\frac{\eta^{2}}{2}\cdot\left(1+\frac{d-2}{P(d+2)}\right)\left(\nabla f({\boldsymbol{x}}_{r}^{\prime})^{\top}\boldsymbol{H}(x_{r})\nabla f({\boldsymbol{x}}_{r}^{\prime})+\frac{1}{m}\langle\Sigma_{r},\boldsymbol{H}(x_{r})\rangle+\frac{1}{m}\langle\Delta_{f,r},\boldsymbol{H}(x_{r})\rangle\right)$ (51) $$

By the assumption, the Hessian upper bound $\boldsymbol{H}(x_{r})$ satisfies $\|\boldsymbol{H}(x_{r})\|\leq L$ and $\mbox{\rm{\small Tr}}(\boldsymbol{H}(x_{r}))\leq L\kappa$. Thus

$$ $\displaystyle\mathbb{E}\hskip 1.42271pt_{r}[f^{\mu}({\boldsymbol{x}}_{r+1})]$ $\displaystyle\leq$ $\displaystyle f^{\mu}({\boldsymbol{x}}_{r})-\eta\|\nabla f^{\mu}({\boldsymbol{x}}_{r})\|^{2}+\frac{\eta^{2}L}{2}\cdot\frac{d\kappa}{P(d+2)}\left(\|\nabla f({\boldsymbol{x}}_{r}^{\prime})\|^{2}+\frac{1}{m}\mbox{\rm{\small Tr}}(\Sigma_{r})+\frac{1}{m}\mbox{\rm{\small Tr}}(\Delta_{f,r})\right)$ $\displaystyle\;\;\;{}+\frac{\eta^{2}L}{2}\cdot\left(1+\frac{d-2}{P(d+2)}\right)\left(\|\nabla f({\boldsymbol{x}}_{r}^{\prime})\|^{2}+\frac{1}{m}\mbox{\rm{\small Tr}}(\Sigma_{r})+\frac{1}{m}\mbox{\rm{\small Tr}}(\Delta_{f,r})\right)$ $\displaystyle=$ $\displaystyle f^{\mu}({\boldsymbol{x}}_{r})-\eta\|\nabla f^{\mu}({\boldsymbol{x}}_{r})\|^{2}+\frac{\eta^{2}L}{2}\cdot\left(1+\frac{d\kappa+d-2}{P(d+2)}\right)\left(\|\nabla f({\boldsymbol{x}}_{r}^{\prime})\|^{2}+\frac{1}{m}\mbox{\rm{\small Tr}}(\Sigma_{r})+\frac{1}{m}\mbox{\rm{\small Tr}}(\Delta_{f,r})\right)$ $\displaystyle\leq$ $\displaystyle f^{\mu}({\boldsymbol{x}}_{r})-\eta\|\nabla f^{\mu}({\boldsymbol{x}}_{r})\|^{2}+\frac{\eta^{2}L}{2}\cdot\left(1+\frac{d\kappa+d-2}{P(d+2)}\right)\left(\|\nabla f({\boldsymbol{x}}_{r}^{\prime})\|^{2}+\frac{1}{m}(\sigma_{G}^{2}+\sigma^{2})\right)$ (52) $$

Next notice that

$$ $\displaystyle\|\nabla f({\boldsymbol{x}}_{r}^{\prime})\|^{2}\leq$ $\displaystyle 2\|\nabla f({\boldsymbol{x}}_{r})\|^{2}+2\|\nabla f({\boldsymbol{x}}_{r})-\nabla f({\boldsymbol{x}}_{r}^{\prime})\|^{2}$ $\displaystyle\leq$ $\displaystyle 2\|\nabla f({\boldsymbol{x}}_{r})\|^{2}+2L^{2}\mu^{2}\theta^{2}\|{\boldsymbol{z}}_{r,p}\|^{2}$ $\displaystyle\leq$ $\displaystyle 2\|\nabla f({\boldsymbol{x}}_{r})\|^{2}+2L^{2}\mu^{2}d$ (53) $$

and

$$ $\displaystyle\|\nabla f^{\mu}({\boldsymbol{x}}_{r})\|^{2}\geq\;$ $\displaystyle\frac{1}{2}\|\nabla f({\boldsymbol{x}}_{r})\|^{2}-\|\nabla f^{\mu}({\boldsymbol{x}}_{r})-\nabla f({\boldsymbol{x}}_{r})\|^{2}$ $\displaystyle\geq\;$ $\displaystyle\frac{1}{2}\|\nabla f({\boldsymbol{x}}_{r})\|^{2}-\frac{1}{4}\mu^{2}L^{2}(d+3)^{3}$ (54) $$

Substituting back, we obtain

$$ $\displaystyle\mathbb{E}\hskip 1.42271pt_{r}[f^{\mu}({\boldsymbol{x}}_{r+1})]\leq$ $\displaystyle f^{\mu}({\boldsymbol{x}}_{r})-\frac{\eta}{2}\|\nabla f({\boldsymbol{x}}_{r})\|^{2}+\frac{1}{4}\eta\mu^{2}L^{2}(d+3)^{3}$ $\displaystyle\;\;+\frac{\eta^{2}L}{2}\cdot\left(1+\frac{d\kappa+d-2}{P(d+2)}\right)\left(2\|\nabla f({\boldsymbol{x}}_{r})\|^{2}+2\mu^{2}L^{2}d+\frac{1}{m}(\sigma_{G}^{2}+\sigma^{2})\right)$ (55) $$

To establish the convergence rate, we move the $\|\nabla f({\boldsymbol{x}}_{r})\|^{2}$ to the left-hand side and take the expectation over the both sides

$$ $\displaystyle\eta\left(\frac{1}{2}-\eta L\cdot\left(1+\frac{d\kappa+d-2}{P(d+2)}\right)\right)\mathbb{E}\hskip 1.42271pt\|\nabla f({\boldsymbol{x}}_{r})\|^{2}$ $\displaystyle\;\;\;\leq\mathbb{E}\hskip 1.42271pt[f^{\mu}({\boldsymbol{x}}_{r})]-\mathbb{E}\hskip 1.42271pt[f^{\mu}({\boldsymbol{x}}_{r+1})]{}+\frac{\eta^{2}L}{2m}\cdot\left(1+\frac{d\kappa+d-2}{P(d+2)}\right)(\sigma_{G}^{2}+\sigma^{2})+\frac{1}{4}\eta\mu^{2}L^{2}(d+3)^{3}+\eta^{2}\mu^{2}L^{3}d$ (56) $$

Take telescoping sum from $r=1$ to $R$ and require $\eta\leq\frac{1}{4L}\left(1+\frac{d\kappa+d-2}{P(d+2)}\right)^{-1}$, we obtain

$$ $\displaystyle\frac{1}{R}\sum_{r=1}^{R}\mathbb{E}\hskip 1.42271pt\|\nabla f^{(}{\boldsymbol{x}}_{r})\|^{2}\leq$ $\displaystyle\,\frac{4(f^{\mu}({\boldsymbol{x}}_{0})-f^{\mu}({\boldsymbol{x}}_{R}))}{R\eta}+\frac{2\eta L}{m}\left(1+\frac{d\kappa+d-2}{P(d+2)}\right)(\sigma_{G}^{2}+\sigma^{2})$ $\displaystyle{}\;\;+\frac{1}{4}\eta\mu^{2}L^{2}(d+3)^{3}+\eta^{2}\mu^{2}L^{3}d$ (57) $$

Last we can bound $f^{\mu}({\boldsymbol{x}}_{0})-f^{\mu}({\boldsymbol{x}}_{R})\leq f({\boldsymbol{x}}_{0})-f({\boldsymbol{x}}^{\star})+\mu^{2}Ld$ to complete the proof.

Selecting $\eta={\mathcal{O}}\left(\frac{\sqrt{mP}}{\sqrt{R\kappa}}\right)$ and $\mu\leq\frac{\sqrt{\kappa}}{\sqrt{mP(d+3)^{3}}}$, we can get

$$ $\displaystyle\frac{1}{R}\sum_{r=1}^{R}\mathbb{E}\hskip 1.42271pt\|\nabla f({\boldsymbol{x}}_{r})\|^{2}={\mathcal{O}}\left(\frac{\sqrt{\kappa}}{\sqrt{mRP}}\right)+{\mathcal{O}}\left(\left(\frac{\sqrt{P}}{\sqrt{mR\kappa}}+\frac{\sqrt{\kappa}}{\sqrt{mRP}}\right)(\sigma_{G}^{2}+\sigma^{2})\right)$ (58) $$

Typically $\kappa>P$ so the convergence rate is ${\mathcal{O}}\left(\frac{\sqrt{\kappa}}{\sqrt{mRP}}\right)$.
$\hfill\blacksquare$

###### Remark 4

The result ([57](#A1.E57)) is intuitive. Besides the terms related to $\mu$, which is coming from that we use the exact form instead of approximation, it is similar to MeZO’s result except one more term $\frac{1}{m}\mbox{\rm{\small Tr}}(\Delta_{f,r})$, which corresponding to the data heterogeneity between the clients. The intuition can gain from the rule of total variance:

$$ $\displaystyle{\rm Var}(\nabla f_{i}(x,\xi_{i}))={\rm Var}(\nabla f_{i}(x))+\mathbb{E}\hskip 1.42271pt_{i}[{\rm Var}(\nabla f_{i}(x,\xi_{i})|i))]\leq\sigma_{G}^{2}+\sigma^{2}$ (59) $$

This implies that is our algorithm in $K=1$ case is equivalent to the MeZO algorithm with larger stochastic gradient noise. In FL scenario, the effective gradient noise is equivalent to local mini-batch randomness (in-group variance) plus the sampling randomness (between-group variance).

Lastly, we present the case the ${\boldsymbol{z}}_{i,p}$ is Gaussian case. The main proof idea is noting $\|{\boldsymbol{z}}_{i,p}\|$ can be unbounded so that Assumption [4](#Thmassumption4) cannot be applied directly. But the probability of large $\|{\boldsymbol{z}}_{i,p}\|$ value decrease exponentially fast. So we can establish the following bound based on two probability events.

###### Theorem 5 (Convergence of FedDisco with $\kappa$ -Effective Rank; Gaussian)

Under the assumptions [1](#Thmassumption1), [2](#Thmassumption2), [3](#Thmassumption3) and [4](#Thmassumption4), supposing $\eta\leq\frac{1}{L}\left(1+\frac{d\kappa+d-2}{P(d+2)}\right)^{-1}$ and ${\boldsymbol{z}}_{i,r}$ generated from the standard Gaussian distribution, then it holds

$$ $\displaystyle\frac{1}{R}\sum_{r=1}^{R}\mathbb{E}\hskip 1.42271pt\|\nabla f({\boldsymbol{x}}_{r})\|^{2}\leq$ $\displaystyle\;\frac{4(f({\boldsymbol{x}}_{0})-f({\boldsymbol{x}}^{\star}))}{R\eta}+\frac{2\eta L}{m}\left(1+\frac{d\kappa+d-2}{P(d+2)}\right)(\sigma_{G}^{2}+\sigma^{2})$ $\displaystyle\;\;{}+\eta^{2}LG^{2}\exp(-\Omega(mdP))+{\mathcal{O}}(\mu^{2})$ $$

where $G$ is defined as the largest value among $\{G({\boldsymbol{x}}_{r})\}_{r=1}^{R}$ and $\Omega(mdP)$ means some function value that can be lower bounded by $mdP$.

Proof. Let ${\mathcal{A}}$ be the event that $\|{\boldsymbol{x}}_{r+1}-{\boldsymbol{x}}_{r}\|\leq 2\eta dG({\boldsymbol{x}}_{r})$. Similarly, we can compute the bound based on the event ${\mathcal{A}}$ happened and the event ${\mathcal{A}}$ did not:

$$ $\displaystyle\mathbb{E}\hskip 1.42271pt_{r}[f^{\mu}({\boldsymbol{x}}_{r+1})]\leq$ $\displaystyle f^{\mu}({\boldsymbol{x}}_{r})-\eta\|\nabla f^{\mu}({\boldsymbol{x}}_{r})\|^{2}+\frac{\eta^{2}}{2}\left\langle\boldsymbol{H}({\boldsymbol{x}}_{r}),\mathbb{E}\hskip 1.42271pt\left[\hat{\nabla}f({\boldsymbol{x}}_{r};\xi_{r})\hat{\nabla}f({\boldsymbol{x}}_{r};\xi_{r})^{\top}\right]\cdot\mathds{1}({\mathcal{A}})\right\rangle$ $\displaystyle\;\;\;{}+\frac{\eta^{2}}{2}\|\hat{\nabla}f({\boldsymbol{x}}_{r};\xi_{r})\cdot\mathds{1}({\mathcal{A}}^{c})\|^{2}$ $\displaystyle=$ $\displaystyle f^{\mu}({\boldsymbol{x}}_{r})-\eta\|\nabla f^{\mu}({\boldsymbol{x}}_{r})\|^{2}+\frac{\eta^{2}}{2}\left\langle\boldsymbol{H}({\boldsymbol{x}}_{r}),\mathbb{E}\hskip 1.42271pt\left[\hat{\nabla}f({\boldsymbol{x}}_{r};\xi_{r})\hat{\nabla}f({\boldsymbol{x}}_{r};\xi_{r})^{\top}\right]\right\rangle$ $\displaystyle\;\;\;{}+\frac{\eta^{2}}{2}\left\langle L{\boldsymbol{I}}-\boldsymbol{H}({\boldsymbol{x}}_{r}),\mathbb{E}\hskip 1.42271pt\left[\hat{\nabla}f({\boldsymbol{x}}_{r};\xi_{r})\hat{\nabla}f({\boldsymbol{x}}_{r};\xi_{r})^{\top}\cdot\mathds{1}({\mathcal{A}}^{c})\right]\right\rangle$ (60) $$

where the symbol $\mathds{1}({\mathcal{A}})$ is the indicating functions that is 0 when event ${\mathcal{A}}$ didn’t happen and 1 when event ${\mathcal{A}}$ happened, ${\mathcal{A}}^{c}$ stands for the complementary of event ${\mathcal{A}}$.

Note on the event ${\mathcal{A}}^{c}$, we have

$$ $\displaystyle 2\eta dG({\boldsymbol{x}}_{r})\leq\|{\boldsymbol{x}}_{r+1}-{\boldsymbol{x}}_{r}\|=\eta\left\|\frac{1}{mP}\sum_{i\in C_{r}}\sum_{p=1}^{P}{\boldsymbol{z}}_{p}{\boldsymbol{z}}_{p}^{\top}\nabla f_{i}({\boldsymbol{x}}_{r}^{\prime};\xi_{i,r})\right\|\leq\frac{\eta}{mP}\sum_{i\in C_{r}}\sum_{p=1}^{P}\|z_{i,p}\|^{2}G({\boldsymbol{x}}_{r})$ (61) $$

We conclude that

$$ $\displaystyle{\mathbb{P}}[{\mathcal{A}}^{c}]\leq{\mathbb{P}}\left[\frac{1}{mP}\sum_{i\in C_{r}}\sum_{p=1}^{P}\|z_{i,p}\|^{2}\leq 2d\right]$ (62) $$

Utilizing the i.i.d. property, the right hand side can be calculated via the Chi-square distribution

$$ $\displaystyle{\mathbb{P}}\left[\frac{1}{mP}\sum_{i\in C_{r}}\sum_{p=1}^{P}\|z_{i,p}\|^{2}\leq 2d\right]={\mathbb{P}}[\chi_{mdP}>2mdP]\leq\exp\left(-\frac{mdP}{16}\right)$ (63) $$

where $\chi_{mdP}$ is the Chi-square distribution with the degrees of freedom $mdP$. Using the same technique used in [, Lemma 6], we can conclude

$$ $\displaystyle\frac{\eta^{2}}{2}\left\langle L{\boldsymbol{I}}-\boldsymbol{H}({\boldsymbol{x}}_{r}),\mathbb{E}\hskip 1.42271pt\left[\hat{\nabla}f({\boldsymbol{x}}_{r};\xi_{r})\hat{\nabla}f({\boldsymbol{x}}_{r};\xi_{r})^{\top}\cdot\mathds{1}({\mathcal{A}}^{c})\right]\right\rangle\leq\eta^{2}LG({\boldsymbol{x}}_{r})^{2}\exp(-\Omega(mdP))$ (64) $$

where $\Omega(mdP)$ means some function value that can be lower bounded by $mdP$. Typically, $mdP$ is a very large value so that this term is vanishing very quickly. Lastly, combining with the proof of Theorem [2](#Thmtheorem2), we arrive the claim of this theorem. $\hfill\blacksquare$

###### Lemma 6

###### Theorem 4 (Restated; Convergence of FedDisco with κ 𝜅 \kappa -Effective Rank)

###### Remark 4

###### Theorem 5 (Convergence of FedDisco with κ 𝜅 \kappa -Effective Rank; Gaussian)

## Peer Reviews

confidence: 4
contribution: 2
initial_rating: 5
presentation: 3
questions: 1. It is unclear to me why zeroth-order gradients are essential in the problem setting: The authors consider the optimization of model parameters which is essentially white-box. The authors are “downgrading” to zeroth-order information for model updates when first-order information is accessible (since the whole model architecture and parameters are known), which may be suboptimal.
2. Related to the question above, the authors claim in Line 63 that “decomposition into a gradient scalar and a perturbation vector” is a unique property of zeroth-order gradients. Please clarify and justify this. Can I achieve a similar effect (eventual convergence, though might be different rates) by projecting the first-order gradient to a specific direction of a perturbation vector?
3. In related works, please clarify the similarities and differences between DeComFL and FedZO? Is DeComFL an extension to FedFL by exploiting the $\kappa$-effective rank assumption?
4. In Table 2, no doubt that the communication saving is substantial. However, the last column is misleading as it has a larger P than FedZO (4th column). I would prefer it removed to avoid confusion.
5. There is no validation of the practical assumption for effective rank. I suggest a comparison of the convergence rate of several differently-sized LLMs. If similar practical convergence rates are observed (with respect to communication cost, I understand the communication costs should be the same for differently-sized models), then $d$ is shown to be pessimistic.
soundness: 2
strengths: 1. The paper is generally well-written and has a good flow.
2. The convergence analysis is necessary and duly provided. The discussion on the effective rank assumption to improve the pessimistic convergence bound is interesting. I did not check through the details for the correctness of the proof.
3. The algorithm design is sound.
summary: The authors consider the practical problem of communication costs in federated learning with increasingly large models especially in the era of LLMs. The authors propose DeComFL, which decomposes the local gradient updates from the clients into a scalar magnitude and a pseudo-random perturbation vector. Since the pseudo-random perturbation is recoverable with known seeds, only the scalar magnitude and the random seed are required to be transmitted during each round of FL training, reducing the communication cost to $O(1)$. The author further provides convergence analyses of the proposed algorithm with and without a low effective rank assumption. Empirical experiments show competitive test accuracies and significantly reduced communication costs for DeComFL.
weaknesses: 1. I am not convinced about the critical role of zeroth-order optimization in the problem setting to reduce communication costs.
2. Parts about the related works and the experiments could be improved, as detailed below in the Questions.

---

confidence: 4
contribution: 2
initial_rating: 5
presentation: 2
questions: 1. What is the difference between the result in Theorem 1 and the prior work that analyzed federated learning with zero-order optimization, e.g. (Fang et al., 2022)? As I understood, algorithmically your method is exactly very similar with only a difference of how direction gradients are samplied & how the communication is performed. Does it pose some extra challenges for the analysis? 

2. Why do all the $z_r^k$ are equal on different nodes? I think algorithmically nothing prevents $z_r^k$ to be different on different nodes? The server would just need m times more memory to save all of $z_r^k$. Would such a modification provide a faster convergence?

3. On lines 052-053 paper comments that “because the models become large, communication becomes a bottleneck” howether, for modern models the computation cost can scale quadratically with model dimension, while communication cost scales only linearly. See e.g. [1]. While I do believe communication cost is an important issue in federated learning, I would recommend rephrasing this sentence.

    [1] SWARM Parallelism: Training Large Models Can Be Surprisingly Communication-Efficient, Ryabinin et al. 

4. communication cost analysis - might not be accurate? 

5. I think $m$ was never introduced in the paper. I understood that $m = | C_r |$, but I didn’t find where it was defined. 

6. Could you give an intuition how large the server memory is for training some standard benchmarks? Is it bigger/smaller than saving the full model? 

7. I think setting $\mu$ as in Corollary 1 does not give the desired result, as the term $2 \mu^2 L^2 (d + 3)^3$ would still have d at the nominator instead of $\sqrt{d}$. 
8. In Assumption 4, which matrix norm do you use? 

9. In theorem 2 $d_{\kappa}$ wasn’t defined before. 

10. Could you also analyze local steps in Theorem 2? What is the difficulty? 

11. I think that condition $\kappa >> P$ could be replaced with just $\kappa > P$. 

12. In Theorem 2, why is setting round R sufficiently large allows to remove the $\sigma_G^2 + \sigma^2$ term?
soundness: 3
strengths: The problem tackled is interesting and important and the proposed method saves a lot of communication (order of 1000s in experiments). Theoretical analysis allows to reason about potential communication savings during the overall course of training. Experiments are done on large models (up to OPT-1.3 B).
summary: The paper uses zero-order optimization in federated learning for achieving communication-efficiency. The main idea is that since the update for zero-order optimization consists of (1) random direction sampled from a gaussian distribution and (2) magnitude 1-d value computed on the data, only (2) needs to be transmitted and (1) could be recovered by the server/other clients if they know the random seed, thus significantly reducing communication cost per each round of training.

The paper provides convergence guarantees of their proposed method, particularly showing that if the loss function has small effective rank, then convergence does not depend on the dimension of the problem d, but rather depends on the rank of the loss function. 

The paper additionally provides experimental verification of the proposed algorithm.
weaknesses: 1. The paper does not state how exactly the random seeds are chosen, which might affect the distribution of the generated sequence. 
As far as I know, random generators guarantee the distribution of sampling a sequence of numbers from the same generator initialized once at some random seed, however with each number having its own random generator with its own random seed, I am not sure what guarantees exist and I imagine it depends on the distributions of the random seeds and particular implementation of random number generator, i.e. if random seed are deterministically chosen in the increasing order (i.e. the next random seed is equal to s + 1, where s is the previous random seed), then the generated numbers probably won’t follow the gaussian distribution. Also, if the random seeds are sampled from the uniform distribution, it is unclear to me, which distribution will follow the generated vectors. 
Therefore, the authors should add a formal statement about the generated sequence of vectors and specify how to generate a sequence of random seeds.

2. In experimental comparison on MNIST, the learning rate is set as the same constant across all the algorithms and settings, which might favor some of the algorithms/settings. For fair comparison it would be better to tune the learning rate separately for each experiment. 

3. Experiments on OPT do not compare to the fine tuning with federated averaging. I am wondering, how close to the finetuning with fed avg can zeroth order optimization get. 

4. On Fig 3. FedAvg + Topk converges much faster than DeComFL in terms of the number of rounds, and it is only slow on the right plot because k is quite large. I am wondering, if you reduce k, so that FedAvg + Topk converge with similar speed as DeComFL, would ZO optimization still provide substantial communication savings compared to FedAvg + Topk for that smaller k?

---

confidence: 4
contribution: 3
initial_rating: 6
presentation: 3
questions: Can you provide any evidence for the low-rank assumption you made?
soundness: 4
strengths: It is quite novel to see the use of a zeroth order method for federated learning, and this paper makes a valuable contribution to this area.

With small and clever modifications to the previous algorithm by Fang et al. (2022), this research effectively reduces the per-iteration communication costs to a constant for each agent. Supported by both theoretical and experimental evidence, this new method significantly outperforms FedAvg in terms of communications costs.
summary: This paper discusses a federated framework using zeroth order (ZO) optimization called DeComFL. It improves the previous ZO method by Fang et al. (2022) because, in each iteration, DeComFL only uses a constant number of bits of communication for each agent.

The authors prove the standard convergence theorem and provide a corollary under the $\kappa$-effective rank assumption. Additionally, they present experiments on training DeComFL, comparing it to the traditional first order method and other zeroth order methods.
weaknesses: The assumption made in Theorem 2 is not very standard. I am not sure if $\kappa$ can be truly seen as $O(1)$ constant and independent from $d$. What will be the consequence if $\kappa$ will scale up with $d$, even if it is not $\Theta(d)$?

Minor: 
1. I think the algorithm was stated for $P=1$. When reading pages 4 and 5, $P$ does not appear to be any part of the algorithm. It was confusing what role the constant $P$ plays in the algorithm. 
2. In assumption 4, the second maximum should be over $\xi_{i,r}$? Could it be a typo?

---

confidence: 3
contribution: 2
initial_rating: 6
presentation: 4
questions: -
soundness: 3
strengths: The paper addresses the significant problem of communication overhead in the field of Federated Learning (FL). Unlike many previous approaches, which typically focus on reducing the communication overhead of gradients, this paper proposes leveraging techniques from zero-order (ZO) optimization, where only function values, which are scalars, need to be transmitted. The idea is promising (though not new; see Weaknesses). I haven't checked the proofs in detail, but they, along with the final results, appear reasonable and clean.
summary: The authors propose a new approach to reducing communication overhead between a server and clients. They have developed a new algorithm that reduces the overhead using zero-order optimization techniques. Noting that in zero-order optimization, it is sufficient to send scalars between a server and clients (unlike first-order optimization, which requires sending vectors), they introduce a new method, called DeComFL, that works with function values. This method is validated by theory and experiments.
weaknesses: Let me point to the weaknesses of the paper:

1. Unfortunately, I'm not sure if the authors are aware, but exactly the same idea to utilize Assumption 4 in the FL setting was in [1]. Albeit, [1] consider the gradient estimator 
$$\langle \nabla f_i(\cdot), z\rangle z$$
instead of (3) from this paper (if $\mu \to 0,$ they are equivalent); after that, the idea and the proof techniques are almost the same between this paper and [1].
2. Additionally, the theory from this paper almost replicates the theory [2] adapted to the multi-client setting.
3. As a base method, the authors take the FedAvg method. While it is the most famous FL method in the literature, there are numerous more modern methods that should be discussed and compared to this approach (e.g. [3]).

[1]: Yue, Pengyun, et al. "Core: Common random reconstruction for distributed optimization with provable low communication complexity." arXiv preprint arXiv:2309.13307 (2023).

[2]: Malladi, Sadhika, et al. "Fine-tuning language models with just forward passes." Advances in Neural Information Processing Systems 36 (2023): 53038-53075.

[3] Mishchenko, Konstantin, et al. "Proxskip: Yes! local gradient steps provably lead to communication acceleration! finally!." International Conference on Machine Learning. PMLR, 2022.

Meta-review: The reviews on this paper were a bit mixed, with some concerns about various aspects including zero-order vs projected first-order approaches, experimental aspects, assumptions, and prior work.  For the most part, these concerns were resolved following the discussion.  One reviewer still wanted to see more motivation on whether there are settings of interest where clients have no gradient access and/or projected gradients are too costly.  Another reviewer noted that the connections/comparisons of ZOO vs projection can be improved.

Since the authors did incorporate a fairly significant discussion on this in the revised paper, the decision leans slightly towards acceptance.  Further editing to address these points should also be considered; for that, the following excerpt from the discussion may be useful: *"...authors didn't correctly state a connection between gradient projected to some direction, and zero order gradients over the same direction. I also agree that a better comparison of ZOO in the projection of the true gradient to that direction would be nice to have in the paper that is currently lacking it."*

Decision: Accept (Poster)