Mitigating Non-IID Drift in Zeroth-Order Federated LLM Fine-Tuning with Transferable Sparsity

## Abstract

Abstract Federated Learning enables collaborative fine-tuning of Large Language Models (LLMs) across decentralized Non-Independent and Identically Distributed (Non-IID) clients, but such models’ massive parameter sizes lead to significant memory and communication challenges. This work introduces Meerkat , a sparse zeroth-order optimization (ZO) method designed for federated LLM fine-tuning. By limiting fine-tuning to a transferable, static, extremely sparse subset of parameters, Meerkat achieves remarkable communication efficiency, enabling cost-effective high-frequency synchronization. With theoretical analysis and experiments, we show that this high-frequency communication effectively mitigates Non-IID data challenges and leads to superior performance compared to full-parameter ZO. Furthermore, experiment results show that Meerkat outperforms existing sparsity baselines with better performance at the same communication frequency. To further handle Non-IID drift, Meerkat leverages traceable local updates and forms a virtual path for each client. This virtual path mechanism reveals the GradIP phenomenon: the inner products between LLM pre-training gradients maintained by server and client gradients estimated via ZO converges for extreme Non-IID clients but oscillates for IID ones. This distinct behavior provides a signal for identifying clients with extreme data heterogeneity.
Using this signal, Meerkat-vp is proposed to analyze GradIP trajectories to identify extreme Non-IID clients and applies early stopping to enhance aggregated model quality. Experiments confirm that Meerkat and Meerkat-vp significantly improve the efficiency and effectiveness of ZO federated LLM fine-tuning.

## 1 Introduction

Federated Learning (FL) [23] has emerged as a powerful paradigm for enabling decentralized collaboration, particularly relevant for fine-tuning Large Language Models (LLMs) across numerous client devices [7, 4]. Unlike centralized training, FL allows clients to train models locally and share only model updates with a central server. However, fine-tuning LLMs in a FL setting faces two major challenges: the massive model parameter size and the Non-Independent and Identically Distributed (Non-IID) data distribution across clients. The former leads to high computation demands on clients and significant communication overhead, while the latter causes client drift and hinder global convergence.
These challenges make LLM fine-tuning impractical on resource-constrained clients and hinder the effective use of decentralized data.

Zeroth-order Optimization (ZO) provides a promising avenue for addressing some of these challenges in federated LLM fine-tuning. By estimating gradients through model perturbations and forward passes, ZO bypasses the need for backpropagation and the storage of intermediate activations, leading to more memory-efficient learning on client devices [37, 8, 17, 18, 22]. However, applying standard ZO directly to the massive parameter space of LLMs can still be computationally inefficient and the optimization process unstable [22].
Moreover, adapting ZO for federated LLM fine-tuning remains challenging, particularly in balancing computational efficiency, communication overhead, and model performance under Non-IID data heterogeneity.

In order to address the above challenges, we propose Meerkat, a sparse ZO method designed for efficient federated LLM fine-tuning. Meerkat addresses the computational and communication burdens by focusing ZO updates on a static, extremely sparse (less than $0.1\%$), and transferable subset of LLM parameters. This subset is strategically identified using gradients derived from pre-training data, ensuring that updates target parameters most sensitive to the loss function. This selective approach dramatically reduces communication overhead and supports cost-effective high-frequency synchronization. As we will demonstrate through theoretical analysis and extensive experiments, the combination of high communication frequency and sparsity in Meerkat enables frequent yet lightweight synchronization. This effectively reduces the convergence error floor in theory and practice, leading to consistently superior performance compared to full-parameter ZO fine-tuning and other sparsity methods under the same communication frequency.

Leveraging Meerkat’s efficient high-frequency synchronization to effectively mitigate Non-IID data challenges, we further enhance its adaptability to weak network conditions. By employing a virtual path mechanism to track client updates, we enable the server to analyze client training dynamics without accessing raw data, thus facilitating robust operation even when frequent direct communication is constrained. Within this virtual path, we observe the GradIP phenomenon, a pattern revealed by the GradIP score, which computes the inner product between local client gradients estimated via ZO and server pre-training gradients. GradIP scores converge for Non-IID clients while oscillating for IID clients, serving as a clear indicator of data heterogeneity. Leveraging this insight, we propose Meerkat-vp that introduces a virtual path client selection method to identify clients with significant Non-IID characteristics and apply early stopping, thereby reducing their adverse impact on the aggregated model and enhancing its quality.

In summary, this paper makes the following contributions:

- •
Performance Improvement with Sparsity. Meerkat consistently outperforms full-parameter ZO optimization in both IID and Non-IID settings, demonstrating the effectiveness of our sparse update strategy. Extensive experiments show that Meerkat surpasses not only full-parameter ZO but also other sparse methods, such as LoRA and weight-magnitude, achieving superior performance.
- •
High Frequency Communication with Sparsity Can Lower the Error Floor. Meerkat leverages extreme model sparsity to reduce local computational memory. Exchanging scalar gradients drastically decreases communication costs, enabling high-frequency communication.
- •
Traceable Local Updates and GradIP Phenomenon: Meerkat leverages traceable sparse local updates and forms a virtual path. The virtual paths reveals the GradIP phenomenon: the inner product between LLM pre-training gradients maintained by server and client gradients estimated via ZO converges for extreme Non-IID clients but oscillates for IID ones. This distinct behavior serves as a signal for detecting clients with extreme data heterogeneity.
- •
Meerkat-vp: Early Stopping for Extreme Non-IID Clients. Leveraging the GradIP phenomenon via virtual path client selection, Meerkat-vp effectively manages extreme Non-IID clients, by early stopping these clients to improve global model quality.
- •
Theoretical and Experimental Validation. We present theoretical analysis and extensive experiments across diverse FL settings, validating the scalability and performance benefits of both Meerkat and Meerkat-vp.

Figure: Figure 1: Meerkat: Sparse zeroth-order optimization for federated LLM fine-tuning workflow.
Refer to caption: x1.png

## 2 Sparse Zeroth-Order Optimization for Federated LLM Fine-tuning

This section introduces Meerkat, a sparse ZO method for federated LLM fine-tuning, and its upgraded version, Meerkat-vp, which incorporates Virtual Path Client Selection(VPCS) strategy. This strategy leverages the traceable virtual path of client local updates to identify clients with extremely Non-IID data and applies early stopping to mitigate their adverse impact on global model convergence. We first introduce the technical details of Meerkat, as illustrated in Figure [1](https://arxiv.org/html/2506.03337v1#S1.F1), and subsequently describe Meerkat-vp, shown in Figure [5](https://arxiv.org/html/2506.03337v1#A2.F5). We then present theoretical convergence analysis for both methods and discuss their strengths in terms of cost-effectiveness, traceability, and the use of early stopping to mitigate client drift caused by Non-IID data.

### 2.1 Meerkat : Extreme Sparse Zeroth-Order Federated LLM Fine-Tuning

Sparse ZO On-Device LLM Fine-Tuning.
meerkat performs sparse ZO for LLM fine-tuning on the client device. Let $\mathcal{D}$ denote the client dataset we would like an LLM to fine-tune with loss function $f$. Given the LLM weight $\mathbf{w}\in\mathbb{R}^{d}$, we perform an iterative optimization by randomly sampling a batch $\mathcal{B}\subset\mathcal{D}$ for each step and performing the local update step as

$$ $g=\frac{f(\mathbf{w}+\varepsilon(\mathbf{z}\odot\mathbf{m});\mathcal{B})-f( \mathbf{w}-\varepsilon(\mathbf{z}\odot\mathbf{m});\mathcal{B})}{2\varepsilon} \,,\quad\widehat{\nabla}f=g\,(\mathbf{z}\odot\mathbf{m})\,.$ (1) $$

where $\mathbf{z}\in\mathbb{R}^{d}$ is a random vector sampled from a Gaussian distribution $\mathcal{N}(0,I_{d})$,
$\varepsilon\in\mathbb{R}$ is the perturbation magnitude, and $\mathbf{m}\in\{0,1\}^{d}$ is a binary sparse mask with density ratio $u$ that selects a subset of parameters for updates.

Extremely Sparse Parameters Obtained from Pre-Training.
According to the formulation in Eq ([1](https://arxiv.org/html/2506.03337v1#S2.E1)), we focus the perturbation of the LLM on a subset of parameters determined by a binary mask $\mathbf{m}$.
The mask $\mathbf{m}$ is derived from the pre-training process of the LLM.
We compute the average squared gradients of each parameter over a subset of the C4 dataset [26].
Then, we select the top $u$ parameters with the highest average squared gradient values and mark them as $1$ in $\mathbf{m}$.
In practice, we set $u$ to $0.1\%$, resulting in extremely sparse updates.

FL with Meerkat. The workflow of Meerkat is illustrated in Figure [1](https://arxiv.org/html/2506.03337v1#S1.F1) and Algorithm [2](https://arxiv.org/html/2506.03337v1#alg2). Meerkat first loads each client with the pre-trained weight $\mathbf{w}_{0}$ and the sparse mask $\mathbf{m}$. Next, Meerkat initializes a random seed list $\{s_{1}^{1},\dots,s_{1}^{T}\}$ at the server to generate the random Gaussian vector $\mathbf{z}$ for each local step in the first round.
Next, Meerkat performs an iterative federated optimization with $R$ rounds of client-server synchronization with each round as follows.

(1) Local ZO update at each client.
Upon receiving global model weights $\mathbf{w}_{r-1}$ and seed list $\{s_{r}^{1},\dots,s_{r}^{T}\}$ from the server, each client performs $T$ local iteration steps.
In each local step $t$, the client perturbs the model parameters selected by $\mathbf{m}$ with the random vector $\mathbf{z}_{k}^{t}$ generated by the random seed $s_{r}^{t}$. Each client then computes projected gradient $g_{k}^{t}$ (a scalar) according to Eq. ([1](https://arxiv.org/html/2506.03337v1#S2.E1)). Using $g_{k}^{t}$, each client calculates the local gradient $\widehat{\nabla}f_{k}^{t}$ and updates the local model $w_{k}$ with learning rate $\eta$. After $T$ local steps, each client uploads a list of projected gradients $\{g_{k}^{1},g_{k}^{2},\dots,g_{k}^{T}\}$ to the server.
(2) Server reconstructs client update with virtual path.
Since the server shares the same random seed list with clients for the round, it can reconstruct each client’s local model update path upon receiving their projected gradients. We term this server-side reconstruction process the virtual path, as it allows the server to follow the client’s local steps without accessing raw data. As shown in Step 2 of Algorithm [2](https://arxiv.org/html/2506.03337v1#alg2), the server uses the preserved random seed and receives project gradients of each local step from each client to recover the local model update path for each client.
(3) Sever aggregates and initiate the next round: After virtual path reconstruction, the server aggregates the reconstructed client model weights $\mathbf{w}_{k}^{T}$ to sparsely update the global model to $\mathbf{w}_{r}$. Subsequently, the server sends $\mathbf{w}_{r}$ and a a new seed list $\{s_{r+1}^{1},\dots,s_{r+1}^{T}\}$ to clients and initializes next round.

Meerkat-vp: Virtual Path Client Selection and Early Stopping. Meerkat-vp extends Meerkat by incorporating a VPCS strategy designed for heterogeneous environments. Leveraging the virtual path reconstruction capability, the server analyzes client update trajectories to identify those with extremely Non-IID data distributions. Meerkat-vp then applies an early stopping mechanism to these identified clients, restricting them to a single local step to mitigate the negative impact of their skewed updates on global model convergence and performance.

### 2.2 Theoretical Convergence Analysis

We theoretically analyze the convergence of Meerkat and Meerkat-vp under the Polyak–Łojasiewicz (PL)-type non-convex condition. All technical assumptions and the corresponding proof are presented in Appendix [B](https://arxiv.org/html/2506.03337v1#A2).

###### Theorem 2.1 (Convergence rate of Meerkat ) .

Under Assumptions [B.1](https://arxiv.org/html/2506.03337v1#A2.Thmtheorem1)–[B.6](https://arxiv.org/html/2506.03337v1#A2.Thmtheorem6), if the learning rate satisfy $\eta=\min\left\{\frac{1}{L(u+2)},\frac{\mu\,\sqrt{c}\bigl{(}1+\sqrt{c_{h}}
\bigr{)}}{2\,L^{2}(2+u)^{2}}\right\}$, then the global model $\{\mathbf{w}^{r}\}$ generated by the Meerkat algorithm satisfies the following convergence bound:

$$ $\displaystyle\frac{1}{R}\sum_{r=0}^{R-1}\left(f(w^{r})-f^{*}\right)$ $\displaystyle\leq\mathcal{O}\!\left(\frac{(2+u)^{2}}{TR}\cdot\mathbb{E}[f(w^{0 })-f(w^{R})]\right)+\mathcal{O}\!\left(\frac{T}{2+u}\right)+O\!\bigl{(}1\bigr{)}$ (2) $$

###### Theorem 2.2 (Convergence rate of Meerkat-vp ) .

Under Assumptions [B.1](https://arxiv.org/html/2506.03337v1#A2.Thmtheorem1)–[B.6](https://arxiv.org/html/2506.03337v1#A2.Thmtheorem6), if the learning rate satisfies $\eta=\min\left\{\frac{1}{L(u+2)},\frac{\mu\,\sqrt{c}\,\bigl{(}K_{g}\,T+K_{b}
\bigr{)}}{2\,K\,(2+u)^{2}\,L^{2}\,T\,\gamma}\right\}$ and each client $k\in K_{b}$ performs $T=1$ local step while the remaining $K_{g}$ clients perform $T$ local steps, then the global model $\{\mathbf{w}^{r}\}$ generated by the Meerkat-vp algorithm satisfies the following convergence bound:

$$ $\displaystyle\frac{1}{R}\sum_{r=0}^{R-1}\mathbb{E}_{\overline{z}}\bigl{[}f(w^{ r})-f^{*}\bigr{]}$ $\displaystyle\leq O\!\biggl{(}\frac{(K_{g}+K_{b})^{2}\,(2+u)^{2}\,\gamma\,T}{c \,(K_{g}T+K_{b})^{2}\,R}\biggr{)}+\,O\!\biggl{(}\frac{1+u}{K_{g}+K_{b}}\sum_{k =1}^{K_{g}+K_{b}}\Delta_{k}\biggr{)}$ (3) $\displaystyle\quad+\,O\!\biggl{(}\frac{c\,T\,K_{g}}{(K_{g}+K_{b})(1+u)\,\gamma }\biggr{)}+\,O\!\biggl{(}\frac{c\,K_{b}\,\sigma_{h}^{2}}{(K_{g}+K_{b})(1+u)\,T \,\gamma}\biggr{)}+O\!\bigl{(}1\bigr{)}.$ $$

The detailed theoretical analysis and proofs for Theorem [2.1](https://arxiv.org/html/2506.03337v1#S2.Thmtheorem1) (Meerkat) can be found in Appendix [B.4](https://arxiv.org/html/2506.03337v1#A2.SS4), and for Theorem [2.2](https://arxiv.org/html/2506.03337v1#S2.Thmtheorem2) (Meerkat-vp) in Appendix [B.5](https://arxiv.org/html/2506.03337v1#A2.SS5).

Insights of Meerkat.
Meerkat’s convergence reveals the intricate interplay of local steps $T$ and density $u$ on performance. (1) Meerkat’s sparsity can theoretically improve performance. Lower $u$ (higher sparsity) quadratically benefits the rate-dependent term $(\propto(2+u)^{2})$, favoring faster initial convergence. However, it inflates the steady-state error $\bigl{(}\propto\tfrac{1}{2+u}\bigr{)}$. Comparing to the full-parameter case $(u=1)$, sparsity $(u<1)$ can reduce the overall bound by decreasing the rate-dependent term, offering communication and computational benefits. Yet, excessive sparsity can increase the steady-state error, suggesting an optimal density level $u\in(0,\,1]$. (2) High frequency communication with sparsity can lower the error floor. Increasing $T$ improves the transient term scaling with $\mathcal{O}\!\bigl{(}\frac{(2+u)^{2}}{T\,R}\bigr{)}$, potentially accelerating convergence towards the steady state; however, it expands the steady-state term $\mathcal{O}\!\bigl{(}\tfrac{T}{2+u}\bigr{)}$, thereby increasing the error floor. Conversely, decreasing $T$ reduces the steady-state term, leading to a tighter final accuracy. Although smaller $T$ can lead to larger rate-dependent term. It’s impact diminishes as the number of rounds $R$ increases. This analysis suggests that operating with frequent communication can theoretically reduce the steady-state error.

Advantages of Meerkat-vp.
We compare each component of the error bound under the same $T$ and $R$. First, the *transient term ratio* between Meerkat-vp and Meerkat is approximately $\gamma(1+\sqrt{c_{h}})^{2}<1$, and as $c_{h}\to 1$ so $\gamma\to 0$, the product $\gamma(1+\sqrt{c_{h}})^{2}\to 0$, causing the transient error to vanish. Second, the *noise term ratio* is given by $\frac{\sigma_{h}^{2}/2}{\sigma_{h}^{2}/(\mu(1+\sqrt{c_{h}})^{2})}=\frac{\mu(1+
\sqrt{c_{h}})^{2}}{2}$, which remains below 1 whenever $\mu(1+\sqrt{c_{h}})^{2}<2$. Since $\mu<1$ empirically, this condition typically holds. Moreover, Meerkat-vp introduces an additional variance term $\frac{cK_{b}\sigma_{h}^{2}}{2K(2+u)LT\gamma}$ that decays as $\mathcal{O}(1/T)$, making it negligible for large local steps. Lastly, in terms of heterogeneity, the coefficient of the heterogeneity term $\sum_{k}\Delta_{k}$ in Meerkat-vp is smaller: $\frac{(2+u)L}{4K}<\frac{L}{K}$, and the extra variance term scales inversely with $K$, thus diminishing in larger systems. Therefore, $E_{\mathrm{\textsc{Meerkat-vp}}}\;<\;E_{\mathrm{\textsc{Meerkat}}}$ and this gap widens as data heterogeneity $c_{h}$ increases. The detailed mathematical derivations and analysis, please refer to the Appendix [B.5](https://arxiv.org/html/2506.03337v1#A2.SS5).

###### Theorem 2.1 (Convergence rate of Meerkat ) .

###### Theorem 2.2 (Convergence rate of Meerkat-vp ) .

### 2.3 Claim 1: Meerkat Can Outperforms Full-Parameter Federated ZO Under Same Synchronization Frequency

We claim that with fixed and extreme sparsity, Meerkat outperforms full-parameter ZO in federated LLM fine-tuning under the same synchronization frequency and effectively mitigates the Non-IID client data problem through frequent synchronization and sparsity.

Advantages of Sparsity in Federated ZO. ZO has an intrinsic need for sparsity due to its reliance on nearly uniform perturbations across dimensions. Research on ZO shows that selecting sensitive parameters using gradient-based methods consistently outperforms alternative strategies such as weight magnitude or random parameter selection [9].
Following this idea, Meerkat produces LLM-sensitive parameters with gradient-based sparsification on pre-training data such as C4 [26]. Moreover,
Meerkat fine-tunes LLMs by estimating gradients through forward passes, completely bypassing backpropagation. This approach minimizes the need to cache gradients and activations, leading to significant memory savings. Focusing on sensitive parameters — those with the greatest influence on loss value changes upon random perturbation — Meerkat ensures efficient and effective fine-tuning even under extreme sparsity levels (e.g., updating only $0.1\%$ of the parameters). Furthermore, these sensitive parameters, derived from pre-training datasets like C4, exhibit transferability across downstream tasks, allowing for parameter-efficient ZO. Theoretical analysis (Appendix [B.4](https://arxiv.org/html/2506.03337v1#A2.SS4)) also confirms that lower density $u$ leads to faster convergence via improved rate-dependent terms $\mathcal{O}((2+u)^{2}/(TR))$, while excessive sparsity increases the steady-state error $\mathcal{O}(T/(2+u))$, suggesting an optimal sparsity trade-off.

Performance Under High Synchronization Frequency. The lightweight communication of Meerkat enables frequent client-server synchronization at a low cost, which is crucial for addressing data heterogeneity [36, 24] in FL. In high-frequency communication scenarios, both the clients and the server only exchange a list of scalars (projected gradients) whereas in lower-frequency synchronization, clients have to upload projected gradients but still download sparse model parameters. By eliminating the need to download sparse model parameters in high-frequency synchronization, this approach is significantly more bandwidth-efficient, further minimizing communication overhead. We present the high-frequency synchronization algorithm of Meerkat in Appendix [B](https://arxiv.org/html/2506.03337v1#A2) Algorithm [3](https://arxiv.org/html/2506.03337v1#alg3). By facilitating frequent synchronization, training can better prevent clients from drifting. Our previous theoretical analysis also demonstrates that a smaller $T$ might influence the rate-dependent term, its beneficial impact on reducing the steady-state error is significant for achieving a tighter final accuracy over many rounds $R$.

### 2.4 Claim 2: Empirical GradIP Phenomenon Reveals Data Heterogeneity

Meerkat’s traceable virtual path allows us to analyze client local training dynamics, revealing an empirical phenomenon related to data heterogeneity via a metric we call GradIP.

###### Definition 2.3 .

Gradient Inner Product (GradIP) score:
let $\widehat{\nabla}f_{k}^{t}$ (see Algorithm [2](https://arxiv.org/html/2506.03337v1#alg2)) denote the gradient of LLM computed by ZO with Eq ([1](https://arxiv.org/html/2506.03337v1#S2.E1)) on client $k$ at local step $t$. Let $\nabla f_{p}$ denote the gradient of LLM computed by backpropagation on pre-training data. We define the GradIP score as $\langle\nabla f_{p},\widehat{\nabla}f_{k}^{t}\rangle$.

GradIP As Indicator for Data Heterogeneity.
Leveraging the virtual path reconstruction capability of Meerkat, the server can trace each client’s local training trajectory. This process uses the uploaded projected gradients $g_{k}^{t}$ along with the shared random seeds (which regenerate $\mathbf{z}_{k}^{t}$) and the sparse mask $\mathbf{m}$ to reconstruct the local gradient $\widehat{\nabla}f_{k}^{t}$. To understand the impact of a client’s local data distribution on its training process, we introduce the GradIP metric. Inspired by the use of pre-training data gradients to identify sensitive parameters, GradIP quantifies the cosine similarity between the local gradient computed during client training and the LLM pre-training gradient.

Empirical GradIP Phenomenon.
Through the traceable virtual path provided by Meerkat, we empirically investigated the behavior of the GradIP score among clients with different data distributions (IID and Non-IID) over their local training steps. Our analysis, presented in Appendix [B.6](https://arxiv.org/html/2506.03337v1#A2.SS6), demonstrates distinct patterns in the dynamics of gradient norms based on data heterogeneity. While IID client gradient norms exhibit fluctuations, those of extremely Non-IID clients decay and converge towards zero. The GradIP definition depends on the fixed pre-training gradient norm, local client gradient norm, and the angle $\theta$ between them. Given the data dissimilarity, we hypothesize that $\theta$ between these two gradient vectors is nearly orthogonal. This leads us to expect a different manifestation of the GradIP Phenomenon when comparing IID and extremely Non-IID clients, primarily influenced by their differing local gradient norm trajectories.

Figure: Algorithm 1 Meerkat-vp

###### Definition 2.3 .

### 2.5 Claim 3: Virtual Path Client Selection via GradIP Analysis

Building upon the traceable virtual path capability introduced in Meerkat, we claim that VPCS, by leveraging GradIP analysis, effectively identifies and manages clients with extremely Non-IID data distribution, thereby improving global model performance and convergence.
As established in Section [2.4](https://arxiv.org/html/2506.03337v1#S2.SS4), the GradIP score, computable by the server through virtual path reconstruction, provides a effective signal to identify such clients. VPCS utilizes this GradIP signal to detect extremely Non-IID clients. By analyzing the GradIP score trajectory and its behavior over local steps during a calibration phase, using metrics defined in Appendix table [3](https://arxiv.org/html/2506.03337v1#A3.T3), the server empirically identifies clients exhibiting the characteristic diminishing GradIP behavior associated with extremely Non-IID data distribution. Upon identification via GradIP analysis, VPCS applies early stopping: these clients perform only one local training step per communication round. To ensure full data utilization over training, a data pointer tracks the batch processed, allowing clients to resume from that point in subsequent rounds. This strategy mitigates client drift from skewed data while ensuring their entire dataset is eventually processed. Algorithm [1](https://arxiv.org/html/2506.03337v1#alg1) outlines the detailed procedure, and Figure [5](https://arxiv.org/html/2506.03337v1#A2.F5) illustrates the workflow. Our previous theoretical analysis of Meerkat-vp suggests that early stopping on extremely Non-IID clients can lead to improved global model performance.

## 3 Experiment

In this section, we aim to validate the effectiveness of Meerkat and Meerkat-vp. We aim to address the following research questions in response to claims in Section [2](https://arxiv.org/html/2506.03337v1#S2).

- •
RQ 1 for Claim 1 ([2.3](https://arxiv.org/html/2506.03337v1#S2.SS3)): Is Meerkat more effective than full parameter federated ZO under the same synchronization frequency, especially in heterogeneous environments?
- •
RQ 2 for Claim 2 ([2.4](https://arxiv.org/html/2506.03337v1#S2.SS4)): Can the empirical GradIP phenomenon, observed via the virtual path, effectively reveal data heterogeneity by showing distinct behaviors for IID and Non-IID clients?
- •
RQ 3 for Claim 3 ([2.5](https://arxiv.org/html/2506.03337v1#S2.SS5)): Can Meerkat-vp, leveraging GradIP analysis, mitigate the impact of extreme Non-IID data compared to Meerkat?

We focus on models Gemma-2-2b [31], Qwen2-1.5B [1], Llama-3.2-1B [7]. We conduct experiments on SST2 [28], AG’s News [38], Yelp polarity (yelp) [38], RTE [32], BoolQ [6], WSC [12], WiC [25] datasets. The datasets are partitioned across clients following a Dirichlet distribution to simulate clients with Non-IID data. For more experimental settings, we refer the readers to Appendix [C.1](https://arxiv.org/html/2506.03337v1#A3.SS1).

**Table 1: Performance comparison of Meerkat and Full-FedZO on tasks SST-2, AgNews, Yelp, BoolQ, RTE, WSC, WIC under an Non-IID setting. “Acc” is the average test accuracy across tasks. Bold numbers indicate the highest value in each row.**
|  | Methods | Local Step | SST-2 | AgNews | Yelp | BoolQ | RTE | WSC | WIC | Acc |
| --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- |
| LLaMA-3.2-1B | Full-FedZO | 10 | 0.909 | 0.705 | 0.940 | 0.641 | 0.542 | 0.634 | 0.523 | 0.699 |
| Weight Magnitude | 10 | 0.902 | 0.857 | 0.951 | 0.696 | 0.551 | 0.519 | 0.546 | 0.717 |  |
| Lora-FedZO | 10 | 0.901 | 0.749 | 0.96 | 0.649 | 0.524 | 0.634 | 0.59 | 0.715 |  |
| Meerkat | 10 | 0.916 | 0.872 | 0.964 | 0.695 | 0.600 | 0.653 | 0.614 | 0.759 |  |
| Full-FedZO | 30 | 0.904 | 0.706 | 0.935 | 0.636 | 0.533 | 0.634 | 0.539 | 0.698 |  |
| Weight Magnitude | 30 | 0.902 | 0.84 | 0.946 | 0.674 | 0.542 | 0.556 | 0.550 | 0.716 |  |
| Lora-FedZO | 30 | 0.904 | 0.556 | 0.964 | 0.652 | 0.533 | 0.634 | 0.545 | 0.684 |  |
| Meerkat | 30 | 0.897 | 0.862 | 0.965 | 0.646 | 0.577 | 0.644 | 0.583 | 0.739 |  |
|  | Full-FedZO | 50 | 0.889 | 0.696 | 0.935 | 0.633 | 0.542 | 0.634 | 0.529 | 0.694 |
|  | Weight Magnitude | 50 | 0.897 | 0.838 | 0.948 | 0.662 | 0.551 | 0.562 | 0.554 | 0.716 |
|  | Lora-FedZO | 50 | 0.876 | 0.447 | 0.967 | 0.639 | 0.541 | 0.634 | 0.562 | 0.667 |
|  | Meerkat | 50 | 0.909 | 0.827 | 0.965 | 0.647 | 0.595 | 0.634 | 0.567 | 0.734 |
|  | Full-FedZO | 100 | 0.901 | 0.705 | 0.939 | 0.632 | 0.533 | 0.634 | 0.525 | 0.695 |
|  | Weight Magnitude | 100 | 0.885 | 0.83 | 0.946 | 0.66 | 0.56 | 0.534 | 0.548 | 0.709 |
|  | Lora-FedZO | 100 | 0.868 | 0.247 | 0.953 | 0.642 | 0.521 | 0.634 | 0.529 | 0.628 |
|  | Meerkat | 100 | 0.896 | 0.777 | 0.961 | 0.658 | 0.577 | 0.644 | 0.573 | 0.726 |
| Qwen2-1.5b | Full-FedZO | 10 | 0.888 | 0.700 | 0.928 | 0.694 | 0.808 | 0.673 | 0.639 | 0.761 |
| Weight Magnitude | 10 | 0.881 | 0.84 | 0.939 | 0.681 | 0.795 | 0.672 | 0.623 | 0.776 |  |
| Lora-FedZO | 10 | 0.939 | 0.847 | 0.944 | 0.667 | 0.795 | 0.663 | 0.521 | 0.768 |  |
| Meerkat | 10 | 0.949 | 0.881 | 0.934 | 0.752 | 0.813 | 0.682 | 0.628 | 0.805 |  |
| Full-FedZO | 30 | 0.892 | 0.699 | 0.926 | 0.708 | 0.791 | 0.663 | 0.594 | 0.753 |  |
| Weight Magnitude | 30 | 0.88 | 0.843 | 0.939 | 0.681 | 0.786 | 0.673 | 0.594 | 0.771 |  |
| Lora-FedZO | 30 | 0.923 | 0.843 | 0.948 | 0.666 | 0.777 | 0.673 | 0.519 | 0.764 |  |
| Meerkat | 30 | 0.944 | 0.878 | 0.928 | 0.734 | 0.800 | 0.663 | 0.624 | 0.795 |  |
|  | Full-FedZO | 50 | 0.868 | 0.696 | 0.922 | 0.707 | 0.773 | 0.663 | 0.594 | 0.746 |
|  | Weight Magnitude | 50 | 0.883 | 0.855 | 0.938 | 0.703 | 0.768 | 0.673 | 0.595 | 0.774 |
|  | Lora-FedZO | 50 | 0.934 | 0.834 | 0.941 | 0.679 | 0.76 | 0.653 | 0.510 | 0.759 |
|  | Meerkat | 50 | 0.948 | 0.872 | 0.926 | 0.746 | 0.795 | 0.663 | 0.594 | 0.792 |
|  | Full-FedZO | 100 | 0.864 | 0.691 | 0.917 | 0.675 | 0.777 | 0.653 | 0.620 | 0.742 |
|  | Weight Magnitude | 100 | 0.888 | 0.842 | 0.934 | 0.695 | 0.768 | 0.656 | 0.579 | 0.766 |
|  | Lora-FedZO | 100 | 0.934 | 0.785 | 0.937 | 0.664 | 0.786 | 0.653 | 0.512 | 0.753 |
|  | Meerkat | 100 | 0.936 | 0.878 | 0.925 | 0.741 | 0.795 | 0.663 | 0.610 | 0.792 |
| Gemma2-2b | Full-FedZO | 10 | 0.928 | 0.721 | 0.943 | 0.731 | 0.564 | 0.644 | 0.595 | 0.732 |
| Weight Magnitude | 10 | 0.931 | 0.849 | 0.955 | 0.778 | 0.711 | 0.634 | 0.595 | 0.779 |  |
| Lora-FedZO | 10 | 0.936 | 0.853 | 0.966 | 0.763 | 0.568 | 0.663 | 0.605 | 0.765 |  |
| Meerkat | 10 | 0.939 | 0.869 | 0.96 | 0.804 | 0.591 | 0.634 | 0.609 | 0.772 |  |
| Full-FedZO | 30 | 0.927 | 0.802 | 0.932 | 0.725 | 0.568 | 0.634 | 0.581 | 0.738 |  |
| Weight Magnitude | 30 | 0.935 | 0.851 | 0.951 | 0.771 | 0.653 | 0.634 | 0.598 | 0.770 |  |
| Lora-FedZO | 30 | 0.932 | 0.804 | 0.966 | 0.671 | 0.551 | 0.634 | 0.589 | 0.735 |  |
| Meerkat | 30 | 0.94 | 0.855 | 0.947 | 0.734 | 0.568 | 0.644 | 0.601 | 0.756 |  |
|  | Full-FedZO | 50 | 0.932 | 0.791 | 0.943 | 0.712 | 0.582 | 0.634 | 0.567 | 0.737 |
|  | Weight Magnitude | 50 | 0.936 | 0.851 | 0.941 | 0.745 | 0.591 | 0.628 | 0.597 | 0.756 |
|  | Lora-FedZO | 50 | 0.91 | 0.779 | 0.942 | 0.664 | 0.557 | 0.634 | 0.597 | 0.726 |
|  | Meerkat | 50 | 0.945 | 0.857 | 0.966 | 0.767 | 0.613 | 0.634 | 0.623 | 0.772 |
|  | Full-FedZO | 100 | 0.925 | 0.818 | 0.933 | 0.672 | 0.533 | 0.615 | 0.567 | 0.723 |
|  | Weight Magnitude | 100 | 0.922 | 0.839 | 0.942 | 0.723 | 0.568 | 0.644 | 0.592 | 0.747 |
|  | Lora-FedZO | 100 | 0.922 | 0.247 | 0.942 | 0.62 | 0.541 | 0.634 | 0.573 | 0.640 |
|  | Meerkat | 100 | 0.94 | 0.851 | 0.951 | 0.745 | 0.551 | 0.634 | 0.574 | 0.749 |

### 3.1 Answer to RQ1: Superiority of Meerkat Compared to Full-FedZO in FL

This section experimentally validates Claim 1 (Section [2.3](https://arxiv.org/html/2506.03337v1#S2.SS3)), demonstrating Meerkat’s superiority over full-parameter Federated ZO under the same synchronization frequency and its effectiveness in mitigating Non-IID challenges via high-frequency synchronization.

First, to support the argument for the Advantages of Sparsity, we compared Meerkat against full-parameter Full-FedZO and other sparsity methods (Weight Magnitude, LoRA-FedZO) under equivalent synchronization frequencies (fixed local steps $T=10,30,50,100$). Meerkat’s inherent $0.1\%$ sparsity provides over 1000x communication savings compared to Full-FedZO. Results (Tables [1](https://arxiv.org/html/2506.03337v1#S3.T1), [5](https://arxiv.org/html/2506.03337v1#A3.T5)) consistently show Meerkat outperforming Full-FedZO on most tasks. Meerkat also outperforms other sparsity methods on many tasks. These findings validate its superiority at the same communication frequency. Notably, under the same setting, Meerkat demonstrated better performance compared to DeComFL [16]. The detailed result in Table [11](https://arxiv.org/html/2506.03337v1#A3.T11)

Next, we validate our claims by evaluating performance under an extreme communication regime, specifically by setting the local step $T$ to 1. In this high-frequency setup, we compared Meerkat against baselines (Full-FedZO and LoRA-FedZO) under both IID and Non-IID data distributions. For the Non-IID case, we used Dirichlet distributions with $\alpha=0.5,0.3,$ and $0.1$. Figure [2](https://arxiv.org/html/2506.03337v1#S3.F2) presents results for $\alpha=0.5$, while results for $\alpha=0.3$ and $0.1$ are available in Appendix [C.2](https://arxiv.org/html/2506.03337v1#A3.SS2) figure [6](https://arxiv.org/html/2506.03337v1#A3.F6). Specifically, Figure [2](https://arxiv.org/html/2506.03337v1#S3.F2) reveals a remarkable finding: on the Qwen2-1.5b model, Meerkat’s average test accuracy over seven tasks under Non-IID data matches that under IID. Beyond this exact match, results show that at a local step of $T=1$, Meerkat effectively bridges the performance gap between IID and Non-IID settings, achieving nearly comparable test accuracy across both data distributions, and consistently outperforms baselines. We further investigate the performance of Meerkat under high-frequency communication with varying sparsity ratios, as shown in Table [7](https://arxiv.org/html/2506.03337v1#A3.T7) in Appendix [C.2](https://arxiv.org/html/2506.03337v1#A3.SS2). Notably, even at extreme sparsity levels such as $10^{-3}$ and $10^{-4}$, Meerkat maintains strong performance. This significantly reduces the memory demand of local computation resources, making it highly suitable for resource-constrained federated settings. Our experimental findings collectively validate Claim 1, demonstrating Meerkat’s superiority over baselines under equivalent communication budgets. The combined use of high-frequency communication and sparsity mechanisms proves effective in mitigating challenges posed by Non-IID data distributions. We also explored sensitive parameter selection using downstream task data. Since performance remained comparable under identical communication frequencies and sparsity levels, we prioritized pre-training data to better preserve client privacy. See Appendix [C.2](https://arxiv.org/html/2506.03337v1#A3.SS2), Tables [13](https://arxiv.org/html/2506.03337v1#A3.T13), [12](https://arxiv.org/html/2506.03337v1#A3.T12), and [14](https://arxiv.org/html/2506.03337v1#A3.T14) for details.

Figure: Figure 2: This figure compares three methods—Full-FedZO, LoRA-FedZO, and Meerkat—on three LLMs: LLaMA-3.2-1B, Qwen2-1.5b, and Gemma2-2b. The x-axis shows the different methods, and each method has two bars indicating performance under IID and Non-IID settings. The Non-IID results are obtained under a Dirichlet distribution with $\alpha=0.5$ .The y-axis represents the average test accuracy across multiple downstream tasks—SST2, AgNews, Yelp, BoolQ, RTE, WSC, and WiC. All detailed results for these tasks are provided in Appendix [C.2](https://arxiv.org/html/2506.03337v1#A3.SS2), Table [7](https://arxiv.org/html/2506.03337v1#A3.T7).
Refer to caption: x2.png

### 3.2 Answer to RQ2: GradIP Trajectories as Effective Indicators of Data Heterogeneity

Figure: Figure 3: Under a density ratio of $5\times 10^{-3}$, we track the GradIP (see Definition [2.3](https://arxiv.org/html/2506.03337v1#S2.Thmtheorem3)) over 100 local training steps on the SST-2 dataset using LLaMA-3.2-1B model, comparing a client with IID data to a client with Non-IID data.
Refer to caption: x3.png

This section experimentally validates Claim 2 (Section [2.4](https://arxiv.org/html/2506.03337v1#S2.SS4)), investigating GradIP trajectories as indicators of data heterogeneity. Based on our theoretical analysis assuming single-label Non-IID data (Section [B.6](https://arxiv.org/html/2506.03337v1#A2.SS6)), we study the dynamics of gradient-related metrics during local training.
We first compare two extremes: IID clients vs. clients with single-label (extreme Non-IID) data. We track three metrics: GradIP score, local gradient norm, and cosine value between the local and pre-training gradients. As shown in Figures [3](https://arxiv.org/html/2506.03337v1#S3.F3) and [7](https://arxiv.org/html/2506.03337v1#A3.F7), GradIP for extreme Non-IID clients steadily decays to zero over 100 steps, while for IID clients it fluctuates persistently. To understand this, we analyze its components: Figure [8](https://arxiv.org/html/2506.03337v1#A3.F8)(a) shows cosine value stays near zero (i.e., gradients are nearly orthogonal) for both settings, suggesting the gradient norm is the key factor. Indeed, Figure [8](https://arxiv.org/html/2506.03337v1#A3.F8)(b) shows that the gradient norm mirrors GradIP’s behavior across the two settings. Moreover, in later stages, GradIP declines more sharply for Non-IID clients than for IID ones, making this stage-wise mean difference an additional criterion for identifying Non-IID clients. We further extend our analysis to more general Non-IID scenarios (Figure [9](https://arxiv.org/html/2506.03337v1#A3.F9), Figure [10](https://arxiv.org/html/2506.03337v1#A3.F10), Figure [11](https://arxiv.org/html/2506.03337v1#A3.F11)), where GradIP exhibits similar dynamics that correlate with the degree of heterogeneity.

### 3.3 Answer to RQ3: VPCS Early Stopping Clients with Extremely Non-IID Data

This section experimentally validates Claim 3 (Section [2.5](https://arxiv.org/html/2506.03337v1#S2.SS5)). As established in Section [3.2](https://arxiv.org/html/2506.03337v1#S3.SS2), GradIP trajectories provide an effective signal for identifying clients with extremely Non-IID data, exhibiting distinct behaviors. Leveraging this signal, VPCS detects extremely Non-IID clients during a calibration phase and applies early stopping, limiting them to one local training step per communication round (Algorithm [1](https://arxiv.org/html/2506.03337v1#alg1)). To validate the effectiveness of this VPCS strategy in improving performance, we compared Meerkat-vp with Meerkat and Random Client Selection, which randomly selects the same number of clients for early stopping as VPCS, under Non-IID data distributions dirichlet $\alpha=0.5$ and the same communication frequencies. Crucially, for the same model, dataset, and communication frequency, the three methods employed the same sparsity level. Figure [4](https://arxiv.org/html/2506.03337v1#S3.F4) illustrates the average test accuracy across multiple downstream tasks for Meerkat-vp compared to Meerkat and Random Client Selection. Detailed results for individual tasks are presented in Appendix [C.2](https://arxiv.org/html/2506.03337v1#A3.SS2) Table [6](https://arxiv.org/html/2506.03337v1#A3.T6). As shown in Figure [4](https://arxiv.org/html/2506.03337v1#S3.F4), Meerkat-vp consistently outperforms both Meerkat and Random Client Selection in different communication frequencies. These experimental results strongly validate Claim 3, confirming that VPCS effectively leverages GradIP analysis to manage extremely Non-IID clients, leading to improved performance for ZO federated LLM fine-tuning.

Figure: Figure 4: This figure compares two methods—Meerkat-vp, Meerkat and Random Client Selection—across three LLMs: LLaMA-3.2-1B, Qwen2-1.5b, and Gemma2-2b. The x-axis shows the local step values ($10$, $30$, $50$, $100$), while the y-axis indicates the average test accuracy over multiple downstream tasks—SST-2, AgNews, Yelp, BoolQ, RTE, WSC, and WiC—in a Non-IID setting. All detailed results for these tasks are presented in Appendix [C.2](https://arxiv.org/html/2506.03337v1#A3.SS2) Table [6](https://arxiv.org/html/2506.03337v1#A3.T6).
Refer to caption: x4.png

## 4 Related Work

Our research leverages advances in ZO federated optimization, sparsity techniques for LLMs, and communication frequency adjustments strategies for addressing data heterogeneity. ZO methods significantly reduce computational and communication overhead. Integrating sparsity into LLM fine-tuning amplifies these benefits, substantially decreasing resource demands during training and inference. Concurrently, communication frequency adjustments mitigate performance degradation induced by Non-IID data, emphasizing a crucial trade-off between communication budget and global model performance. A detailed discussion is provided in Appendix [A](https://arxiv.org/html/2506.03337v1#A1).

## 5 Conclusion

In this paper, we introduce Meerkat, a sparse zeroth-order federated fine-tuning methodology. Experiments show Meerkat outperforms Full-FedZO and other sparsity methods on most tasks at equivalent communication frequencies. Meerkat’s efficiency enables high-frequency communication, effectively mitigating Non-IID drift. Moreover, we propose Meerkat-vp. This methodology utilizes VPCS, which analyzes GradIP via virtual paths to enable the selective early stopping of extreme Non-IID clients. This approach is shown to improve model performance. Our work thus offers effective methods for efficient ZO federated LLM fine-tuning under varying network conditions and data heterogeneity. Given the technical focus of this work on algorithm, there are no direct negative societal consequences inherent to it that need to be emphasized; potential negative impacts would arise from the specific applications where these methods are deployed.

## References

- qwe [2024]
Qwen2 technical report.
2024.
- Acar et al. [2021]
Durmus Alp Emre Acar, Yue Zhao, Ramon Matas Navarro, Matthew Mattina, Paul N. Whatmough, and Venkatesh Saligrama.
Federated learning based on dynamic regularization, 2021.
URL [https://arxiv.org/abs/2111.04263](https://arxiv.org/abs/2111.04263).
- Bottou et al. [2018]
Léon Bottou, Frank E. Curtis, and Jorge Nocedal.
Optimization methods for large-scale machine learning, 2018.
URL [https://arxiv.org/abs/1606.04838](https://arxiv.org/abs/1606.04838).
- Brown et al. [2020]
Tom Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared D Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, et al.
Language models are few-shot learners.
*Advances in neural information processing systems*, 33:1877–1901, 2020.
- Chen et al. [2024]
Jun Chen, Hong Chen, Bin Gu, and Hao Deng.
Fine-grained theoretical analysis of federated zeroth-order optimization.
*Advances in Neural Information Processing Systems*, 36, 2024.
- Clark et al. [2019]
Christopher Clark, Kenton Lee, Ming-Wei Chang, Tom Kwiatkowski, Michael Collins, and Kristina Toutanova.
Boolq: Exploring the surprising difficulty of natural yes/no questions.
*arXiv preprint arXiv:1905.10044*, 2019.
- Dubey et al. [2024]
Abhimanyu Dubey, Abhinav Jauhri, Abhinav Pandey, Abhishek Kadian, Ahmad Al-Dahle, Aiesha Letman, Akhil Mathur, Alan Schelten, Amy Yang, Angela Fan, et al.
The llama 3 herd of models.
*arXiv preprint arXiv:2407.21783*, 2024.
- Fang et al. [2022]
Wenzhi Fang, Ziyi Yu, Yuning Jiang, Yuanming Shi, Colin N Jones, and Yong Zhou.
Communication-efficient stochastic zeroth-order optimization for federated learning.
*IEEE Transactions on Signal Processing*, 70:5058–5073, 2022.
- Guo et al. [2024]
Wentao Guo, Jikai Long, Yimeng Zeng, Zirui Liu, Xinyu Yang, Yide Ran, Jacob R. Gardner, Osbert Bastani, Christopher De Sa, Xiaodong Yu, Beidi Chen, and Zhaozhuo Xu.
Zeroth-order fine-tuning of llms with extreme sparsity, 2024.
URL [https://arxiv.org/abs/2406.02913](https://arxiv.org/abs/2406.02913).
- Huang et al. [2024]
Weiyu Huang, Yuezhou Hu, Guohao Jian, Jun Zhu, and Jianfei Chen.
Pruning large language models with semi-structural adaptive sparse training, 2024.
URL [https://arxiv.org/abs/2407.20584](https://arxiv.org/abs/2407.20584).
- Karimireddy et al. [2021]
Sai Praneeth Karimireddy, Satyen Kale, Mehryar Mohri, Sashank J. Reddi, Sebastian U. Stich, and Ananda Theertha Suresh.
Scaffold: Stochastic controlled averaging for federated learning, 2021.
URL [https://arxiv.org/abs/1910.06378](https://arxiv.org/abs/1910.06378).
- Levesque et al. [2012]
Hector Levesque, Ernest Davis, and Leora Morgenstern.
The winograd schema challenge.
In *Thirteenth international conference on the principles of knowledge representation and reasoning*, 2012.
- Li et al. [2021]
Qinbin Li, Yiqun Diao, Quan Chen, and Bingsheng He.
Federated learning on non-iid data silos: An experimental study, 2021.
URL [https://arxiv.org/abs/2102.02079](https://arxiv.org/abs/2102.02079).
- Li et al. [2020a]
Tian Li, Anit Kumar Sahu, Manzil Zaheer, Maziar Sanjabi, Ameet Talwalkar, and Virginia Smith.
Federated optimization in heterogeneous networks, 2020a.
URL [https://arxiv.org/abs/1812.06127](https://arxiv.org/abs/1812.06127).
- Li et al. [2020b]
Xiang Li, Kaixuan Huang, Wenhao Yang, Shusen Wang, and Zhihua Zhang.
On the convergence of fedavg on non-iid data, 2020b.
URL [https://arxiv.org/abs/1907.02189](https://arxiv.org/abs/1907.02189).
- Li et al. [2024]
Zhe Li, Bicheng Ying, Zidong Liu, Chaosheng Dong, and Haibo Yang.
Achieving dimension-free communication in federated learning via zeroth-order optimization, 2024.
URL [https://arxiv.org/abs/2405.15861](https://arxiv.org/abs/2405.15861).
- Ling et al. [2024]
Zhenqing Ling, Daoyuan Chen, Liuyi Yao, Yaliang Li, and Ying Shen.
On the convergence of zeroth-order federated tuning for large language models.
In *Proceedings of the 30th ACM SIGKDD Conference on Knowledge Discovery and Data Mining*, pages 1827–1838, 2024.
- Liu et al. [2024]
Yong Liu, Zirui Zhu, Chaoyu Gong, Minhao Cheng, Cho-Jui Hsieh, and Yang You.
Sparse mezo: Less parameters for better performance in zeroth-order llm fine-tuning, 2024.
URL [https://arxiv.org/abs/2402.15751](https://arxiv.org/abs/2402.15751).
- Liu et al. [2023a]
Zichang Liu, Aditya Desai, Fangshuo Liao, Weitao Wang, Victor Xie, Zhaozhuo Xu, Anastasios Kyrillidis, and Anshumali Shrivastava.
Scissorhands: Exploiting the persistence of importance hypothesis for LLM KV cache compression at test time.
In Alice Oh, Tristan Naumann, Amir Globerson, Kate Saenko, Moritz Hardt, and Sergey Levine, editors, *Advances in Neural Information Processing Systems 36: Annual Conference on Neural Information Processing Systems 2023, NeurIPS 2023, New Orleans, LA, USA, December 10 - 16, 2023*, 2023a.
- Liu et al. [2023b]
Zichang Liu, Jue Wang, Tri Dao, Tianyi Zhou, Binhang Yuan, Zhao Song, Anshumali Shrivastava, Ce Zhang, Yuandong Tian, Christopher Re, et al.
Deja vu: Contextual sparsity for efficient llms at inference time.
In *International Conference on Machine Learning*, pages 22137–22176. PMLR, 2023b.
- Lu et al. [2024]
Xudong Lu, Aojun Zhou, Yuhui Xu, Renrui Zhang, Peng Gao, and Hongsheng Li.
SPP: Sparsity-preserved parameter-efficient fine-tuning for large language models.
In *Forty-first International Conference on Machine Learning*, 2024.
URL [https://openreview.net/forum?id=9Rroj9GIOQ](https://openreview.net/forum?id=9Rroj9GIOQ).
- Malladi et al. [2023]
Sadhika Malladi, Tianyu Gao, Eshaan Nichani, Alex Damian, Jason D Lee, Danqi Chen, and Sanjeev Arora.
Fine-tuning language models with just forward passes.
*Advances in Neural Information Processing Systems*, 36:53038–53075, 2023.
- McMahan et al. [2017]
Brendan McMahan, Eider Moore, Daniel Ramage, Seth Hampson, and Blaise Aguera y Arcas.
Communication-efficient learning of deep networks from decentralized data.
In *Artificial intelligence and statistics*, pages 1273–1282. PMLR, 2017.
- Mendieta et al. [2022]
Matias Mendieta, Taojiannan Yang, Pu Wang, Minwoo Lee, Zhengming Ding, and Chen Chen.
Local learning matters: Rethinking data heterogeneity in federated learning.
In *Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition*, pages 8397–8406, 2022.
- Pilehvar and Camacho-Collados [2018]
Mohammad Taher Pilehvar and Jose Camacho-Collados.
Wic: the word-in-context dataset for evaluating context-sensitive meaning representations.
*arXiv preprint arXiv:1808.09121*, 2018.
- Raffel et al. [2020]
Colin Raffel, Noam Shazeer, Adam Roberts, Katherine Lee, Sharan Narang, Michael Matena, Yanqi Zhou, Wei Li, and Peter J Liu.
Exploring the limits of transfer learning with a unified text-to-text transformer.
*Journal of machine learning research*, 21(140):1–67, 2020.
- Shao et al. [2024]
Hang Shao, Bei Liu, and Yanmin Qian.
One-shot sensitivity-aware mixed sparsity pruning for large language models.
In *ICASSP 2024-2024 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP)*, pages 11296–11300. IEEE, 2024.
- Socher et al. [2013]
Richard Socher, Alex Perelygin, Jean Wu, Jason Chuang, Christopher D Manning, Andrew Y Ng, and Christopher Potts.
Recursive deep models for semantic compositionality over a sentiment treebank.
In *Proceedings of the 2013 conference on empirical methods in natural language processing*, pages 1631–1642, 2013.
- Su et al. [2024]
Junda Su, Zirui Liu, Zeju Qiu, Weiyang Liu, and Zhaozhuo Xu.
In defense of structural sparse adapters for concurrent llm serving.
In *Findings of the Association for Computational Linguistics: EMNLP 2024*, pages 4948–4953, 2024.
- Sun et al. [2023]
Jingwei Sun, Ziyue Xu, Hongxu Yin, Dong Yang, Daguang Xu, Yiran Chen, and Holger R. Roth.
Fedbpt: Efficient federated black-box prompt tuning for large language models, 2023.
URL [https://arxiv.org/abs/2310.01467](https://arxiv.org/abs/2310.01467).
- Team [2024]
Gemma Team.
Gemma.
2024.
doi: 10.34740/KAGGLE/M/3301.
URL [https://www.kaggle.com/m/3301](https://www.kaggle.com/m/3301).
- Wang [2018]
Alex Wang.
Glue: A multi-task benchmark and analysis platform for natural language understanding.
*arXiv preprint arXiv:1804.07461*, 2018.
- Wang et al. [2021]
Jianyu Wang, Qinghua Liu, Hao Liang, Gauri Joshi, and H. Vincent Poor.
A novel framework for the analysis and design of heterogeneous federated learning.
*IEEE Transactions on Signal Processing*, 69:5234–5249, 2021.
doi: 10.1109/TSP.2021.3106104.
- Wang et al. [2019]
Ziheng Wang, Jeremy Wohlwend, and Tao Lei.
Structured pruning of large language models.
*arXiv preprint arXiv:1910.04732*, 2019.
- Xu et al. [2024]
Zhaozhuo Xu, Zirui Liu, Beidi Chen, Shaochen Zhong, Yuxin Tang, Jue Wang, Kaixiong Zhou, Xia Hu, and Anshumali Shrivastava.
Soft prompt recovers compressed llms, transferably.
In *Forty-first International Conference on Machine Learning, ICML 2024, Vienna, Austria, July 21-27, 2024*. OpenReview.net, 2024.
URL [https://openreview.net/forum?id=muBJPCIqZT](https://openreview.net/forum?id=muBJPCIqZT).
- Yang et al. [2024]
Zhiqin Yang, Yonggang Zhang, Yu Zheng, Xinmei Tian, Hao Peng, Tongliang Liu, and Bo Han.
Fedfed: Feature distillation against data heterogeneity in federated learning.
*Advances in Neural Information Processing Systems*, 36, 2024.
- Zhang et al. [2021]
Qingsong Zhang, Bin Gu, Zhiyuan Dang, Cheng Deng, and Heng Huang.
Desirable companion for vertical federated learning: New zeroth-order gradient based algorithm.
In *Proceedings of the 30th ACM International Conference on Information & Knowledge Management*, pages 2598–2607, 2021.
- Zhang et al. [2015]
Xiang Zhang, Junbo Zhao, and Yann LeCun.
Character-level convolutional networks for text classification.
*Advances in neural information processing systems*, 28, 2015.
- Zhang et al. [2024a]
Yihua Zhang, Pingzhi Li, Junyuan Hong, Jiaxiang Li, Yimeng Zhang, Wenqing Zheng, Pin-Yu Chen, Jason D. Lee, Wotao Yin, Mingyi Hong, Zhangyang Wang, Sijia Liu, and Tianlong Chen.
Revisiting zeroth-order optimization for memory-efficient LLM fine-tuning: A benchmark.
In *Forty-first International Conference on Machine Learning, ICML 2024, Vienna, Austria, July 21-27, 2024*. OpenReview.net, 2024a.
URL [https://openreview.net/forum?id=THPjMr2r0S](https://openreview.net/forum?id=THPjMr2r0S).
- Zhang et al. [2024b]
Yuxin Zhang, Lirui Zhao, Mingbao Lin, Yunyun Sun, Yiwu Yao, Xingjia Han, Jared Tanner, Shiwei Liu, and Rongrong Ji.
Dynamic sparse no training: Training-free fine-tuning for sparse llms, 2024b.
URL [https://arxiv.org/abs/2310.08915](https://arxiv.org/abs/2310.08915).
- Zhao et al. [2018]
Yue Zhao, Meng Li, Liangzhen Lai, Naveen Suda, Damon Civin, and Vikas Chandra.
Federated learning with non-iid data.
2018.
doi: 10.48550/ARXIV.1806.00582.
URL [https://arxiv.org/abs/1806.00582](https://arxiv.org/abs/1806.00582).
- Zheng et al. [2024]
Haizhong Zheng, Xiaoyan Bai, Xueshen Liu, Z Morley Mao, Beidi Chen, Fan Lai, and Atul Prakash.
Learn to be efficient: Build structured sparsity in large language models.
*arXiv preprint arXiv:2402.06126*, 2024.
- Zhou et al. [2024]
Yang Zhou, Zhuoming Chen, Zhaozhuo Xu, Victoria Lin, and Beidi Chen.
Sirius: Contextual sparsity with correction for efficient llms.
*arXiv preprint arXiv:2409.03856*, 2024.

## Appendix

In Section [A](https://arxiv.org/html/2506.03337v1#A1), we present the related work relevant to this study. In Section [B](https://arxiv.org/html/2506.03337v1#A2), we present the theoretical convergence analysis of Meerkat, including its high-frequency communication method. Additionally, we analyze the convergence of Meerkat-VP and demonstrate its superior performance compared to Meerkat. We further prove that under extreme Non-IID settings, the gradient norm gradually vanishes during convergence, whereas in IID settings, it tends to oscillate. In Section [C](https://arxiv.org/html/2506.03337v1#A3), we provide details on experimental hyperparameters and report supplementary results.

## Appendix A Review of Related Works

Federated Zeroth-Order Optimization.
Zeroth-order optimization [22, 39] has gained increasing attention in federated learning [8, 37], particularly for addressing challenges in training costs, privacy, and communication overhead. Fine-Grained  [5] demonstrates how clients can reduce upload overhead by sending estimated gradients rather than full model parameters to the server, though download costs remain significant due to complete model weight transfers. DeComFL [16] further advances this approach by using gradient scalars for both uploads and downloads, substantially reducing bidirectional communication costs. However, it does not address the challenges posed by data heterogeneity (Non-IID) in federated learning. The integration of AirComp wireless technology enables direct over-the-air aggregation of model updates [8]. In black-box settings where pre-trained language model parameters are inaccessible, FedBPT [30] employs ZO to optimize prompt vectors, achieving efficient distributed optimization with reduced computational and communication overhead. FedMeZO [15] analyzes the convergence properties of ZO for federated LLM fine-tuning.

Sparsity in LLM.
Current research on sparsity in LLMs explores techniques such as pruning, contextual sparsity prediction, and structured sparsity [40, 20, 19, 21, 42, 27, 34, 10, 43, 29, 35]. These methods enhance both training and inference by improving computational efficiency, reducing memory usage, and enabling deployment in resource-constrained environments.
Sparsity has also proven particularly effective in zeroth-order (ZO) optimization [9, 18], especially when combined with weight quantization for fine-tuning LLMs.
Building on this, our work investigates the role of sparsity in resource-frugal federated fine-tuning of LLMs.

High-Frequency Communication for Non-IID Federated Learning. Data heterogeneity across clients is a major challenge in Federated Learning, significantly degrading performance compared to IID settings. Increasing communication frequency, by reducing local training steps per round, is explored as a strategy to mitigate this issue. Early work showed that merely reducing local steps had limited improvements in extreme non-IID scenarios [41]. Theoretical analysis later confirmed that smaller local training steps can improve convergence speed under Non-IID conditions, but at the cost of increased communication budget, highlighting a critical trade-off [15]. To effectively handle challenges arising from non-IID data that often necessitate higher communication, various algorithms have been proposed: SCAFFOLD [11] highlights the ’client-drift’ problem in FedAvg, noting it’s exacerbated by increased local training steps (reduced communication frequency), and proposes using control variates to mitigate this drift, enabling improved convergence; FedDyn [2] guarantees consistent convergence to the global optimum even with a larger number of local training steps (lower communication frequency). This overcomes the limitation of traditional methods where high communication frequency is needed to compensate for local-global optimum inconsistency. Empirical studies further demonstrate that performance is highly sensitive to the number of local training steps under different non-IID distributions, and the optimal communication frequency depends on the specific data heterogeneity [13]. These works underscore the complex interplay between data heterogeneity, local computation, and communication frequency. This complexity motivates the development of algorithmic solutions to improve efficiency and robustness in FL under Non-IID settings.

## Appendix B Theoretical and Algorithm Analysis

### B.1 Notations and Definitions

In this subsection, we formally define the assumptions, notations and concepts used in the convergence analysis of Meerkat and Meerkat-vp. Table [2](https://arxiv.org/html/2506.03337v1#A2.T2) summarizes the key symbols.

**Table 2: Notations used in our theoretical analysis.**
| Notation | Meaning |
| --- | --- |
| $\mathbf{w}$ | global model parameter |
| $K$ | total number of clients in the federated system |
| $p_{k}$ | probability or weight assigned to client $k$ |
| $f_{k}(\mathbf{w})$ | total loss computed over all data samples of the client k. |
| $f(\mathbf{w})$ | global loss function evaluated by the global model over all data |
| $T$ | number of local update steps per communication round |
| $r$ | communication round |
| $t$ | local update time step |
| $\eta$ | local learning rate |
| $\varepsilon$ | perturbation magnitude in ZO estimation |
| $\mathbf{z}_{k}^{t}$ | standard Gaussian vector for client $k$ at local step $t$ from $\mathcal{N}(0,I_{d})$ |
| $\mathbf{m}$ | binary sparse mask vector ($\mathbf{m}\in\{0,1\}^{d}$) |
| $d$ | model dimension |
| $R$ | federated learning training round |
| $u$ | sparsity ratio |
| $c$ | gradient coverage |
| $g_{k}^{t}$ | projected gradient estimate for client $k$ at local step $t$ |
| $\widehat{\nabla}f_{k}^{t}$ | zeroth-order gradient of client $k$ at local step $t$ |
| $L$ | Lipschitz smoothness (Assumption 1) |
| $\mu$ | PL inequality (Assumption 2) |
| $f^{*}$ | minimal global loss achieved by optimizing the global model |
| $f_{k}^{*}$ | minimal client loss achieved by optimizing the local model on client $k$ |
| $c_{h}$ and $\sigma_{h}^{2}$ | heterogeneity-induced variance (Assumption 4) |
| $\|\cdot\|_{\text{op}}$ | operator norm of a matrix |
| $\sigma^{2}$ | variance of the sparse ZO gradient estimator(Assumption 6) |
| $\gamma$ | The clients with balanced data distributions contribute to the global model during training. |

### B.2 Assumptions

We introduce the assumptions used in the convergence analysis of Meerkat and Meerkat-vp.

###### Assumption B.1 ( Lipschitz smoothness) .

We assume that each client $k$’s local objective function $f_{k}(\mathbf{w})$ is differentiable and has $L$-Lipschitz continuous gradients:

$$ $\|\nabla f_{k}(\mathbf{w}_{1})-\nabla f_{k}(\mathbf{w}_{2})\|\leq L\|\mathbf{w }_{1}-\mathbf{w}_{2}\|,\quad\forall\mathbf{w}_{1},\mathbf{w}_{2}\in\mathbb{R}^ {d}.$ $$

Consequently, the global loss $f(\mathbf{w})=\sum_{k=1}^{K}p_{k}f_{k}(\mathbf{w})$ is also $L$-smooth.

###### Assumption B.2 (PL inequality) .

We assume that $f(\mathbf{w})$ satisfies the Polyak-Łojasiewicz (PL) condition:

$$ $f(\mathbf{w})-f^{*}\leq\frac{1}{2\mu}\|\nabla f(\mathbf{w})\|^{2},\quad\forall \mathbf{w}\in\mathbb{R}^{d},$ $$

$\mu>0$ is the PL constant. This condition holds for a broad class of non-convex objectives and is commonly used in analyzing convergence of gradient-based and zeroth-order methods.

###### Assumption B.3 (Global–Local Disparities in Non-i.i.d. Setting) .

For any $\theta\in\mathbb{R}^{d}$, the discrepancy between the local and global gradient is bounded by

$$ $\bigl{\|}\nabla f(\theta)-\nabla f_{i}(\theta)\bigr{\|}^{2}\;\leq\;c_{h}\, \bigl{\|}\nabla f(\theta)\bigr{\|}^{2}\;+\;\sigma_{h}^{2},$ $$

where $c_{h}>0$ and $\sigma_{h}^{2}\geq 0$ are constants, and $\theta$ is the global model parameter broadcast to all clients at the start of each round. We further assume $c_{h}\in(0,1)$. In particular,

- •
A smaller $c_{h}$ corresponds to lower *data heterogeneity*: local gradient deviations from the global gradient are small, indicating that client data distributions are nearly i.i.d.
- •
A larger $c_{h}$ signals stronger non-i.i.d data distribution effects, with greater variation between each client’s gradient and the global gradient.

###### Assumption B.4 (Bounded stochastic gradient variance) .

For any sample $(x,y)\sim\mathcal{D}$ and any $\mathbf{w}\in\mathbb{R}^{d}$, denote $f(\mathbf{w};(x,y))$ as the loss on that single data point, and let
$\overline{f}(\mathbf{w}):=\mathbb{E}_{(x,y)\sim\mathcal{D}}\bigl{[}f(\mathbf{w
};(x,y))\bigr{]}$
be the average full-batch loss. We assume

$$ $\bigl{\|}\nabla f(\mathbf{w};(\mathbf{x},y))-\nabla\overline{f}(\mathbf{w}) \bigr{\|}_{2}^{2}\;\leq\;\sigma^{2}.$ $$

###### Assumption B.5 (Local–Global Optimality Gap) .

For each client $k$, define the local–global optimality gap as

$$ $\Delta_{k}\;=\;\bigl{\lVert}\mathbf{w}_{k}^{*}-\mathbf{w}^{*}\bigr{\rVert}_{2} ^{2},$ $$

where $\mathbf{w}_{k}^{*}$ is the local optimal model on client $k$ and $\mathbf{w}^{*}$ is the global optimal model.

###### Assumption B.6 (Sensitive parameters are sparse) .

At each local step $t$ (and for every client $k$), there exists a binary mask $\mathbf{m}\in\{0,1\}^{d}$ with exactly $u$ non-zero entries and a constant $c\in[0,1]$ such that

$$ $\left\|\mathbf{m}\odot\nabla f_{k}\!\left(\mathbf{w}_{k}^{t};(\mathbf{x}_{t}, \mathbf{y}_{t})\right)\right\|^{2}=c\,\left\|\nabla f_{k}\!\left(\mathbf{w}_{k }^{t};(\mathbf{x}_{t},\mathbf{y}_{t})\right)\right\|^{2}.$ $$

We further assume $c\gg\frac{u}{d}$, meaning this small subset of “sensitive” parameters captures a disproportionately large fraction of the gradient norm.

These assumptions are standard and foundational in optimization and FL literature[3, 14, 15, 33, 9]

We start by formulating the expectation of the sensitive sparse ZO surrogate gradient norm square in terms of its corresponding stochastic gradient norm square.

###### Lemma B.7 (Sensitive sparse ZO surrogate gradient norm square) .

$$ $\mathbb{E}_{\overline{z}}\Bigl{\|}\widehat{\nabla}f\bigl{(}w_{t},(x_{t},y_{t}) ,\overline{z}_{t}\bigr{)}\Bigr{\|}^{2}\;=\;(2+u)c\,\Bigl{\|}\nabla f\bigl{(}w_ {t};(x_{t},y_{t})\bigr{)}\Bigr{\|}^{2}.$ $$

###### Proof.

Our masked perturbation $\overline{\mathbf{z}}$ is sampled as
$\overline{\mathbf{z}}\sim\mathcal{N}\!\bigl{(}0,\,\widetilde{I}_{d,\mathbf{m}}
\bigr{)},$
where
$\widetilde{I}_{d,\mathbf{m}}$ equals the identity matrix $I_{d}$ with its
main diagonal masked by $\mathbf{m}$.

We expand the sensitive sparse ZO surrogate–gradient covariance matrix:

$$ $\begin{array}[]{l@{}}\mathbb{E}_{\overline{z}}\widehat{\nabla}f(w,(x,y), \overline{z})\widehat{\nabla}f(w,(x,y),\overline{z})^{\top}\\ =\mathbb{E}_{\overline{z}}[\overline{z}\overline{z}^{\top}((\mathbf{m}\odot \nabla f(w;(x,y)))(\mathbf{m}\odot\nabla f(w;(x,y)))^{\top})\overline{z} \overline{z}^{\top}]\\ =2((\mathbf{m}\odot\nabla f(w;(x,y)))(\mathbf{m}\odot\nabla f(w;(x,y)))^{\top} )+\|\mathbf{m}\odot\nabla f(w;(x,y))\|^{2}\widetilde{I}_{d,\mathbf{m}}\end{array}$ $$

The above expected squared norm is obtained by summing the diagonal elements of this covariance matrix:

$$ $\displaystyle\mathbb{E}_{\overline{z}}\!\Bigl{\|}\widehat{\nabla}f\bigl{(}w_{t },x_{t},\overline{z}_{t}\bigr{)}\Bigr{\|}^{2}$ $\displaystyle=\,\bigl{(}\operatorname{diag}\!\bigl{[}\mathbb{E}_{\overline{z}} \widehat{\nabla}f\!\bigl{(}w,(x,y),\overline{z}\bigr{)}\widehat{\nabla}f\! \bigl{(}w,(x,y),\overline{z}\bigr{)}^{\!\top}\bigr{]}\bigr{)}^{\!2}$ $\displaystyle=\,2c\,\bigl{\|}\nabla f\bigl{(}w_{t};(x_{t},y_{t})\bigr{)}\bigr{ \|}^{2}+uc\,\bigl{\|}\nabla f\bigl{(}w_{t};(x_{t},y_{t})\bigr{)}\bigr{\|}^{2}$ $\displaystyle=\,(2+u)c\,\bigl{\|}\nabla f\bigl{(}w_{t};(x_{t},y_{t})\bigr{)} \bigr{\|}^{2}.$ $$

∎

###### Lemma B.8 (Unbiasedness of Masked Sparse ZO Surrogate Gradient) .

$$ $\mathbb{E}_{\overline{z}}\!\bigl{[}\widehat{\nabla}f_{k}(\mathbf{w}_{k}^{t}, \overline{z})\bigr{]}=\mathbf{m}\!\odot\!\nabla f_{k}(\mathbf{w}_{k}^{t}), \quad\text{where }\overline{z}=z\!\odot\!\mathbf{m}.$ (4) $$

###### Proof.

First, consider the estimator defined as:

$$ $\widehat{\nabla}f_{k}(\mathbf{w}_{k}^{t},z)=\frac{f_{k}(\mathbf{w}_{k}^{t}+ \varepsilon(z\odot\mathbf{m}))-f_{k}(\mathbf{w}_{k}^{t}-\varepsilon(z\odot \mathbf{m}))}{2\varepsilon}\cdot(z\odot\mathbf{m}).$ $$

To proceed, we apply a first-order Taylor expansion of $f_{k}$ around $\mathbf{w}_{k}^{t}$ for small $\varepsilon$:

$$ $f_{k}(\mathbf{w}_{k}^{t}\pm\varepsilon(z\odot\mathbf{m}))=f_{k}(\mathbf{w}_{k} ^{t})\pm\varepsilon\langle\nabla f_{k}(\mathbf{w}_{k}^{t}),z\odot\mathbf{m} \rangle+\mathcal{O}(\varepsilon^{2}).$ $$

Substitute these expansions into the numerator of the estimator:

$$ $\displaystyle f_{k}\bigl{(}\mathbf{w}_{k}^{t}+\varepsilon\,(z\odot\mathbf{m}) \bigr{)}-f_{k}\bigl{(}\mathbf{w}_{k}^{t}-\varepsilon\,(z\odot\mathbf{m})\bigr{)}$ $\displaystyle\quad=\bigl{[}f_{k}(\mathbf{w}_{k}^{t})+\varepsilon\,\langle \nabla f_{k}(\mathbf{w}_{k}^{t}),\,z\odot\mathbf{m}\rangle\bigr{]}$ $\displaystyle\qquad-\bigl{[}f_{k}(\mathbf{w}_{k}^{t})-\varepsilon\,\langle \nabla f_{k}(\mathbf{w}_{k}^{t}),\,z\odot\mathbf{m}\rangle\bigr{]}+\mathcal{O} (\varepsilon^{2}).$ $$

Simplify the expression:

$$ $f_{k}(\mathbf{w}_{k}^{t}+\varepsilon(z\odot\mathbf{m}))-f_{k}(\mathbf{w}_{k}^{ t}-\varepsilon(z\odot\mathbf{m}))=2\varepsilon\langle\nabla f_{k}(\mathbf{w}_{ k}^{t}),z\odot\mathbf{m}\rangle+\mathcal{O}(\varepsilon^{2}).$ $$

Thus, the estimator becomes:

$$ $\widehat{\nabla}f_{k}(\mathbf{w}_{k}^{t},z)=\frac{2\varepsilon\langle\nabla f_ {k}(\mathbf{w}_{k}^{t}),z\odot\mathbf{m}\rangle+\mathcal{O}(\varepsilon^{2})}{ 2\varepsilon}\cdot(z\odot\mathbf{m})=\left[\langle\nabla f_{k}(\mathbf{w}_{k}^ {t}),z\odot\mathbf{m}\rangle+\mathcal{O}(\varepsilon)\right](z\odot\mathbf{m}).$ $$

As $\varepsilon\to 0$, the $\mathcal{O}(\varepsilon)$ term disappears, yielding the approximation:

$$ $\widehat{\nabla}f_{k}(\mathbf{w}_{k}^{t},z)\approx\langle\nabla f_{k}(\mathbf{ w}_{k}^{t}),z\odot\mathbf{m}\rangle\cdot(z\odot\mathbf{m}).$ $$

Next, compute the expectation $\mathbb{E}_{z}\left[\widehat{\nabla}f_{k}(\mathbf{w}_{k}^{t},z)\right]$. Since the estimator is a vector, consider its $j$-th component:

$$ $\left[\widehat{\nabla}f_{k}(\mathbf{w}_{k}^{t},z)\right]_{j}\approx\langle \nabla f_{k}(\mathbf{w}_{k}^{t}),z\odot\mathbf{m}\rangle\cdot(z_{j}m_{j}).$ $$

Express the inner product explicitly:

$$ $\langle\nabla f_{k}(\mathbf{w}_{k}^{t}),z\odot\mathbf{m}\rangle=\sum_{i=1}^{d} (\nabla f_{k}(\mathbf{w}_{k}^{t}))_{i}z_{i}m_{i}.$ $$

Thus, the $j$-th component is:

$$ $\left[\widehat{\nabla}f_{k}(\mathbf{w}_{k}^{t},z)\right]_{j}\approx\left(\sum_ {i=1}^{d}(\nabla f_{k}(\mathbf{w}_{k}^{t}))_{i}z_{i}m_{i}\right)z_{j}m_{j}.$ $$

Now, take the expectation over $z\sim\mathcal{N}(0,\mathbf{I}_{d})$, where $z_{i}$ are independent standard normal variables:

$$ $\mathbb{E}_{z}\left[\left(\sum_{i=1}^{d}(\nabla f_{k}(\mathbf{w}_{k}^{t}))_{i} z_{i}m_{i}\right)z_{j}m_{j}\right]=\sum_{i=1}^{d}(\nabla f_{k}(\mathbf{w}_{k}^ {t}))_{i}m_{i}m_{j}\mathbb{E}[z_{i}z_{j}].$ $$

Since $\mathbb{E}[z_{i}z_{j}]=\delta_{ij}$ (1 if $i=j$, 0 otherwise), the sum reduces to:

$$ $(\nabla f_{k}(\mathbf{w}_{k}^{t}))_{j}m_{j}^{2}\mathbb{E}[z_{j}^{2}].$ $$

Given $m_{j}^{2}=m_{j}$ (as $m_{j}=0$ or $1$) and $\mathbb{E}[z_{j}^{2}]=1$, this becomes:

$$ $(\nabla f_{k}(\mathbf{w}_{k}^{t}))_{j}m_{j}.$ $$

Thus, for each component $j$:

$$ $\mathbb{E}_{z}\left[\left[\widehat{\nabla}f_{k}(\mathbf{w}_{k}^{t},z)\right]_{ j}\right]\approx m_{j}(\nabla f_{k}(\mathbf{w}_{k}^{t}))_{j}.$ $$

This implies:

$$ $\mathbb{E}_{z}\left[\widehat{\nabla}f_{k}(\mathbf{w}_{k}^{t},z)\right]\approx \mathbf{m}\odot\nabla f_{k}(\mathbf{w}_{k}^{t}).$ $$

Finally, as $\varepsilon\to 0$, the higher-order terms in the Taylor expansion vanish, making the approximation exact:

$$ $\mathbb{E}_{\overline{z}}\left[\widehat{\nabla}f_{k}(\mathbf{w}_{k}^{t}, \overline{z})\right]=\mathbf{m}\odot\nabla f_{k}(\mathbf{w}_{k}^{t}).$ $$

∎

###### Assumption B.1 (
Lipschitz smoothness) .

###### Assumption B.2 (PL inequality) .

###### Assumption B.3 (Global–Local Disparities in Non-i.i.d. Setting) .

###### Assumption B.4 (Bounded stochastic gradient variance) .

###### Assumption B.5 (Local–Global Optimality Gap) .

###### Assumption B.6 (Sensitive parameters are sparse) .

###### Lemma B.7 (Sensitive sparse ZO surrogate gradient norm square) .

###### Proof.

###### Lemma B.8 (Unbiasedness of Masked Sparse ZO Surrogate Gradient) .

###### Proof.

### B.3 Meerkat convergence analysis

We consider the federated zeroth-order optimization problem, where the objective is to minimize the global loss function[17]:

$$ $\displaystyle\min_{\mathbf{w}}f(\mathbf{w})$ $\displaystyle=\sum_{k=1}^{K}p_{k}f_{k}(\mathbf{w})$ $$

Each client performs $T$ local steps:

$$ $\displaystyle\mathbf{w}^{t+1}_{k}=\mathbf{w}^{t}_{k}-\eta\nabla f_{k}^{t}( \mathbf{w}),\quad t=0,1,\dots,T-1$ $$

starting from the global model $\mathbf{w}^{0}_{k}=\mathbf{w}^{r}$. After clients finish local updates, the server performs weighted aggregation of their model updates.

$$ $\displaystyle\mathbf{w}^{r+1}=\sum_{k=1}^{K}p_{k}\mathbf{w}_{k}^{r}.$ $$

###### Theorem B.9 .

[Client Local ZO Update Convergence]
Let $f_{k}$ be $L$-smooth and $\widehat{\nabla}f_{k}^{t}$ be an unbiased sparse zeroth-order gradient estimator with variance bounded by $\sigma^{2}$. Then we have

If we set constant learning rate $\eta=\frac{1}{L(u+2)}$ and $T$ local steps, the output of client $k$ satisfies:

$$ $\frac{1}{T}\sum_{t=0}^{T-1}\mathbb{E}\|\nabla f_{k}(\mathbf{w}_{k}^{t})\|^{2} \leq\mathcal{O}\left(\frac{1}{T}\right)+\mathcal{O}(\sigma^{2}).$ (5) $$

###### Proof.

We start by proving Theorem [B.9](https://arxiv.org/html/2506.03337v1#A2.Thmtheorem9) euqation [5](https://arxiv.org/html/2506.03337v1#A2.E5) that each client achieves local convergence during training with sparse zeroth-order finetuning. Next, we demonstrate that server-side aggregation also converge. Finally, by leveraging the PL inequality, we prove that Meerkat exhibits linear convergence to global minimum.

Part 1: Client Local ZO Update Convergence

We analyze the effect of one local step of Meerkat under sparse zeroth-order updates. Let client $k$ perform the local update:

$$ $\mathbf{w}_{k}^{t+1}=\mathbf{w}_{k}^{t}-\eta\widehat{\nabla}f_{k}^{t},$ $$

where the stochastic sparse zeroth-order gradient estimator is defined as:

$$ $g_{k}^{t}=\frac{f_{k}(\mathbf{w}_{k}^{t}+\varepsilon(\mathbf{z}_{k}^{t}\odot \mathbf{m}))-f_{k}(\mathbf{w}_{k}^{t}-\varepsilon(\mathbf{z}_{k}^{t}\odot \mathbf{m}))}{2\varepsilon}.$ $$

$$ $\widehat{\nabla}f_{k}^{t}=g_{k}^{t}\cdot(\mathbf{z}_{k}^{t}\odot\mathbf{m})$ $$

###### Theorem B.9 .

###### Proof.

#### Descent via Lipschitz smoothness.

Since $f_{k}(\mathbf{w})$ is Lipschitz smoothness:

$$ $f_{k}(\mathbf{w}_{k}^{t+1})\leq f_{k}(\mathbf{w}_{k}^{t})+\langle\nabla f_{k}( \mathbf{w}_{k}^{t}),\mathbf{w}_{k}^{t+1}-\mathbf{w}_{k}^{t}\rangle+\frac{L}{2} \|\mathbf{w}_{k}^{t+1}-\mathbf{w}_{k}^{t}\|^{2}.$ $$

Substituting the update $\mathbf{w}_{k}^{t+1}-\mathbf{w}_{k}^{t}=-\eta\widehat{\nabla}f_{k}^{t}$, we obtain:

$$ $f_{k}(\mathbf{w}_{k}^{t+1})\leq f_{k}(\mathbf{w}_{k}^{t})-\eta\langle\nabla f_ {k}(\mathbf{w}_{k}^{t}),\widehat{\nabla}f_{k}^{t}(\mathbf{w},\overline{\mathbf {z}}_{t})\ \rangle+\frac{L\eta^{2}}{2}\|\widehat{\nabla}f_{k}^{t}(\mathbf{w}, \overline{\mathbf{z}}_{t})\|^{2}.$ $$

Taking expectation, we have:

$$ $\mathbb{E}_{\overline{\mathbf{z}}}[f_{k}(\mathbf{w}_{k}^{t+1})]\leq\mathbb{E}_ {\overline{\mathbf{z}}}[f_{k}(\mathbf{w}_{k}^{t})]-\eta\mathbb{E}_{\overline{ \mathbf{z}}}\|\mathbf{m}\odot\nabla f_{k}(\mathbf{w}_{k}^{t})\|^{2}+\frac{L \eta^{2}}{2}\mathbb{E}_{\overline{\mathbf{z}}}\|\widehat{\nabla}f_{k}(\mathbf{ w}_{k}^{t},\overline{\mathbf{z}}_{t})\|^{2}.$ $$

$$ $\mathbb{E}_{\overline{\mathbf{z}}}[f_{k}(\mathbf{w}_{k}^{t+1})]\leq\mathbb{E}_ {\overline{\mathbf{z}}}[f_{k}(\mathbf{w}_{k}^{t})]-c\eta\mathbb{E}_{\overline{ \mathbf{z}}}\|\nabla f_{k}(\mathbf{w}_{k}^{t})\|^{2}+\frac{L\eta^{2}}{2}(2+u)c \mathbb{E}_{\overline{\mathbf{z}}}\bigl{\|}\nabla f_{k}\bigl{(}\mathbf{w}_{k}^ {t}\bigr{)}\bigr{\|}^{2}.$ $$

$$ $\mathbb{E}_{\overline{\mathbf{z}}}f_{k}(\mathbf{w}_{k}^{t+1})\leq\mathbb{E}_{ \overline{\mathbf{z}}}f_{k}(\mathbf{w}_{k}^{t})-\left(c\eta_{t}-\frac{L\eta_{t }^{2}}{2}c(u+2)\right)\|\nabla_{\mathbf{w}}f_{k}(\mathbf{w}_{k}^{t})\|^{2}+ \frac{L\eta_{t}^{2}}{2}c(u+2)\sigma^{2}.$ $$

Denote $\alpha=Lc(u+2)$, we can rewrite as:

$$ $\mathbb{E}_{\overline{\mathbf{z}}}f_{k}(\mathbf{w}_{k}^{t+1})\leq\mathbb{E}_{ \overline{\mathbf{z}}}\left\{f_{k}(\mathbf{w}_{k}^{t})-\eta_{t}\left(c-\frac{ \alpha}{2}\eta_{t}\right)\|\nabla_{\mathbf{w}}f_{k}(\mathbf{w}_{k}^{t})\|^{2} \right\}+\frac{\alpha}{2}\sigma^{2}\eta_{t}^{2}.$ $$

From the above inequality, we get $\eta<\frac{2c}{\alpha}$. Suppose we use a constant learning rate $\eta_{t}=\eta=\frac{c}{\alpha}=\frac{1}{L(u+2)}$, we get:

$$ $\mathbb{E}_{\overline{\mathbf{z}}}f_{k}(\mathbf{w}_{k}^{t+1})\leq\mathbb{E}_{ \overline{\mathbf{z}}}\left\{f_{k}(\mathbf{w}_{k}^{t})-\frac{c\eta}{2}\|\nabla _{\mathbf{w}}f_{k}(\mathbf{w}_{k}^{t})\|^{2}\right\}+\frac{\alpha}{2}\sigma^{2 }\eta^{2}.$ (6) $$

#### Accumulating over T 𝑇 T italic_T steps.

Summing equation [6](https://arxiv.org/html/2506.03337v1#A2.E6) over $t=0$ to $T-1$, we get:

$$ $\displaystyle\frac{1}{T}\sum_{t=0}^{T-1}\mathbb{E}_{\overline{\mathbf{z}}}\| \nabla f_{k}(\mathbf{w}_{k}^{t})\|^{2}$ $\displaystyle\leq\frac{2}{c\eta T}(f_{k}(\mathbf{w}_{k}^{0})-f_{k}^{*})+\frac{ 1}{T}\sum_{t=0}^{T-1}\frac{\alpha}{2c\eta}\sigma^{2}\eta^{2}$ (7) $\displaystyle=\frac{2L(u+2)}{cT}(f_{k}(\mathbf{w}_{k}^{0})-f_{k}^{*})+\sigma^{2}$ $\displaystyle=\mathcal{O}\left(\frac{u}{T}(f_{k}(\mathbf{w}_{k}^{0})-f_{k}^{*} )\right)+\mathcal{O}(1).$ $$

∎

### B.4 Meerkat Convergence Analysis

We now proceed to analyze the convergence of the global model in our federated learning framework. Having established the convergence properties of local client updates, we demonstrate how these results extend to guarantee the convergence of the server-aggregated global model.

###### Proof.

We approach this proof systematically by analyzing how the local convergence properties of clients extend to the global model through the aggregation process.

Global Model Update Representation.
First, the global model update can be represented as:

$$ $\displaystyle\mathbf{w}^{r+1}-\mathbf{w}^{r}=\sum_{k=1}^{K}p_{k}(\mathbf{w}_{k }^{T}-\mathbf{w}^{r})$ $$

where each client $k$ starts from the global model $\mathbf{w}^{r}$ and performs $T$ local updates to reach $\mathbf{w}_{k}^{T}$.

Client Local Update Accumulation
For any client $k$, the accumulated local updates can be expressed as:

$$ $\displaystyle\mathbf{w}_{k}^{r,T}-\mathbf{w}^{r}=-\eta\sum_{t=0}^{T-1}\widehat {\nabla}f_{k}^{t}$ $$

Global Loss Descent Analysis
By the $L$-smoothness property (Assumption [B.1](https://arxiv.org/html/2506.03337v1#A2.Thmtheorem1)), we have:

$$ $f(\mathbf{w}^{r+1})\leq f(\mathbf{w}^{r})+\langle\nabla f(\mathbf{w}^{r}), \mathbf{w}^{r+1}-\mathbf{w}^{r}\rangle+\frac{L}{2}\|\mathbf{w}^{r+1}-\mathbf{w }^{r}\|^{2}$ (8) $$

For the inner product we can get:

$$ $\displaystyle\langle\nabla f(\mathbf{w}^{r}),\mathbf{w}^{r+1}-\mathbf{w}^{r}\rangle$ $\displaystyle=\sum_{k=1}^{K}p_{k}\langle\nabla f(\mathbf{w}^{r}),\mathbf{w}_{k }^{r,T}-\mathbf{w}^{r}\rangle$ $$

Accoding to the client local update process, we have:

$$ $\displaystyle\sum_{k=1}^{K}p_{k}\langle\nabla f_{k}(\mathbf{w}^{r}),\mathbf{w} _{k}^{r,T}-\mathbf{w}^{r}\rangle$ $\displaystyle=-\eta\sum_{k=1}^{K}p_{k}\langle\nabla f(\mathbf{w}^{r}),\sum_{t= 0}^{T-1}\widehat{\nabla}f_{k}(\mathbf{w}^{r,t},\overline{\mathbf{z}}_{t})\rangle$ $\displaystyle=-\eta\sum_{k=1}^{K}p_{k}\sum_{t=0}^{T-1}\langle\nabla f(\mathbf{ w}^{r}),\widehat{\nabla}f_{k}(\mathbf{w}^{r,t},\overline{\mathbf{z}}_{t})\rangle$ $$

We assume that each client’s weight is equal $p_{k}=1/K$, by substituting it into the above inequality, we have:

$$ $\sum_{k=1}^{K}p_{k}\bigl{\langle}\nabla f_{k}(\mathbf{w}^{r}),\,\mathbf{w}_{k} ^{r,T}-\mathbf{w}^{r}\bigr{\rangle}=-\frac{\eta}{K}\sum_{k=1}^{K}\sum_{t=0}^{T -1}\bigl{\langle}\nabla f(\mathbf{w}^{r}),\,\widehat{\nabla}f_{k}(\mathbf{w}^{ r,t},\overline{\mathbf{z}}_{t})\bigr{\rangle}.$ (9) $$

Based on the equation [9](https://arxiv.org/html/2506.03337v1#A2.E9) and $\widehat{\nabla}f_{k}^{t}$ is unbiased, we have:

$$ $\sum_{k=1}^{K}\sum_{t=0}^{T-1}\bigl{\langle}\nabla f(w^{r}),\,\widehat{\nabla} f_{k}(\mathbf{w}^{r,t},\overline{\mathbf{z}}_{t})\bigr{\rangle}\;=\;\sum_{k=1} ^{K}\sum_{t=0}^{T-1}\bigl{\langle}\nabla f(w^{r}),\,\mathbb{E}_{\overline{z}} \!\bigl{[}\widehat{\nabla}f_{k}(\mathbf{w}^{r,t},\overline{\mathbf{z}}_{t}) \bigr{]}\bigr{\rangle}$ $$

We substitute the equation [4](https://arxiv.org/html/2506.03337v1#A2.E4) and get:

$$ $\sum_{k=1}^{K}\sum_{t=0}^{T-1}\bigl{\langle}\nabla f(w^{r}),\,\mathbb{E}_{ \overline{z}}\!\bigl{[}\widehat{\nabla}f_{k}(\mathbf{w}^{r,t},\overline{ \mathbf{z}}_{t})\bigr{]}\bigr{\rangle}\;=\;\sum_{k=1}^{K}\sum_{t=0}^{T-1}\bigl {\langle}\nabla f(w^{r}),\,\mathbf{m}\odot\nabla f_{k}(w^{r,t})\bigr{\rangle}.$ $$

Under the Cauchy–Schwarz inequality, we have:

$$ $\bigl{\langle}\nabla f(\mathbf{w}^{r}),\;\mathbf{m}\odot\nabla f_{k}(\mathbf{w }^{r,t})\bigr{\rangle}\;\leq\;\|\nabla f(\mathbf{w}^{r})\|\;\|\mathbf{m}\odot \nabla f_{k}(\mathbf{w}^{r,t})\|$ $$

We substitute Assumption [B.6](https://arxiv.org/html/2506.03337v1#A2.Thmtheorem6) get:

$$ $\|\nabla f(\mathbf{w}^{r})\|\;\|\mathbf{m}\odot\nabla f_{k}(\mathbf{w}^{r,t}) \|\;=\;\sqrt{c}\,\|\nabla f(\mathbf{w}^{r})\|\;\|\nabla f_{k}(\mathbf{w}^{r,t} )\|.$ $$

Thus we get:

$$ $\bigl{\langle}\nabla f(\mathbf{w}^{r}),\;\mathbf{m}\odot\nabla f_{k}(\mathbf{w }^{r,t})\bigr{\rangle}\;\leq\;\sqrt{c}\,\|\nabla f(\mathbf{w}^{r})\|\;\|\nabla f _{k}(\mathbf{w}^{r,t})\|.$ $$

By the triangle inequality, we have

$$ $\|\nabla f_{k}(\mathbf{w}^{r,t})\|\;\leq\;\|\nabla f(\mathbf{w}^{r})\|+\| \nabla f_{k}(\mathbf{w}^{r,t})-\nabla f(\mathbf{w}^{r})\|$ $$

We substitute Assumption [B.3](https://arxiv.org/html/2506.03337v1#A2.Thmtheorem3) and use the properties of square roots we get:

$$ $\displaystyle\|\nabla f(\mathbf{w}^{r})\|$ $\displaystyle+\|\nabla f_{k}(\mathbf{w}^{r,t})-\nabla f(\mathbf{w}^{r})\|$ $\displaystyle\leq\|\nabla f(\mathbf{w}^{r})\|+\sqrt{\,c_{h}\,\|\nabla f( \mathbf{w}^{r})\|^{2}+\sigma_{h}^{2}\,}$ $\displaystyle\leq(1+\sqrt{c_{h}})\,\|\nabla f(\mathbf{w}^{r})\|+\sigma_{h}.$ $$

Using the bound
$\langle\nabla f(\mathbf{w}^{r}),\;m\odot\nabla f_{k}(\mathbf{w}^{r,t})\rangle
\leq\sqrt{c}\,\|\nabla f(\mathbf{w}^{r})\|\;\|\nabla f_{k}\|$
from Cauchy–Schwarz and Assumption [B.6](https://arxiv.org/html/2506.03337v1#A2.Thmtheorem6), and then plugging in the above,
we obtain

$$ $\displaystyle\langle\nabla f(\mathbf{w}^{r}),\,m\odot\nabla f_{k}(\mathbf{w}^{ r,t})\rangle$ $\displaystyle\leq\sqrt{c}\,\|\nabla f(\mathbf{w}^{r})\|\bigl{[}(1+\sqrt{c_{h}} )\,\|\nabla f(\mathbf{w}^{r})\|+\sigma_{h}\bigr{]}$ $\displaystyle\leq\sqrt{c}\,(1+\sqrt{c_{h}})\,\|\nabla f(\mathbf{w}^{r})\|^{2} \;+\;\sqrt{c}\,\sigma_{h}\,\|\nabla f(\mathbf{w}^{r})\|.$ $$

Recall that the server update inner product is

$$ $\bigl{\langle}\nabla f(w^{r}),\,w^{r+1}-w^{r}\bigr{\rangle}\;=\;-\,\frac{\eta} {K}\sum_{k=1}^{K}\sum_{t=0}^{T-1}\bigl{\langle}\nabla f,\;m\odot\nabla f_{k} \bigr{\rangle}.$ $$

Substituting the bound to equation [9](https://arxiv.org/html/2506.03337v1#A2.E9). We have:

$$ $\displaystyle\bigl{\langle}\nabla f(w^{r}),\,w^{r+1}-w^{r}\bigr{\rangle}\;\geq \;-\,\eta\,T\,\sqrt{c}\,(1+\sqrt{c_{h}})\,\|\nabla f(w^{r})\|^{2}\;-\;\eta\,T \,\sqrt{c}\,\sigma_{h}\,\|\nabla f(w^{r})\|.$ (10) $$

Substituting this inequality to equation [8](https://arxiv.org/html/2506.03337v1#A2.E8), we have:

$$ $\displaystyle f\bigl{(}w^{r+1}\bigr{)}$ $\displaystyle\leq f\bigl{(}w^{r}\bigr{)}\;-\;\eta\,T\,\sqrt{c}\,\bigl{(}1+ \sqrt{c_{h}}\bigr{)}\,\bigl{\|}\nabla f(w^{r})\bigr{\|}^{2}$ $\displaystyle\quad-\,\eta\,T\,\sqrt{c}\,\sigma_{h}\,\bigl{\|}\nabla f(w^{r}) \bigr{\|}+\,\frac{L}{2}\,\bigl{\|}w^{r+1}-w^{r}\bigr{\|}^{2}$ (11) $$

Applying Jensen’s inequality, the last term of the equation [11](https://arxiv.org/html/2506.03337v1#A2.E11) will be:

$$ $\|\mathbf{w}^{r+1}-\mathbf{w}^{r}\|^{2}\leq\eta^{2}\sum_{k=1}^{K}p_{k}\|\sum_{ t=0}^{T-1}\widehat{\nabla}f_{k}^{r,t}\|^{2}$ $$

And then we apply Cauchy-Schwarz inequality, the last term of the equation [11](https://arxiv.org/html/2506.03337v1#A2.E11) will be:

$$ $\|\mathbf{w}^{r+1}-\mathbf{w}^{r}\|^{2}\leq\eta^{2}T\sum_{k=1}^{K}p_{k}\sum_{t =0}^{T-1}\|\widehat{\nabla}f_{k}^{r,t}\|^{2}$ $$

Substitute this inequaltiy to equation [11](https://arxiv.org/html/2506.03337v1#A2.E11) We get:

$$ $\displaystyle f\bigl{(}w^{r+1}\bigr{)}$ $\displaystyle\leq f\bigl{(}w^{r}\bigr{)}-\,\eta\,T\,\sqrt{c}\,(1+\sqrt{c_{h}}) \,\bigl{\|}\nabla f(w^{r})\bigr{\|}^{2}-\,\eta\,T\,\sqrt{c}\,\sigma_{h}\,\bigl {\|}\nabla f(w^{r})\bigr{\|}$ $\displaystyle\quad+\,\frac{L}{2}\,\eta^{2}\,T\,\sum_{k=1}^{K}p_{k}\sum_{t=0}^{ T-1}\bigl{\|}\widehat{\nabla}f_{k}^{r,t}\bigr{\|}^{2}.$ $$

Taking Expectation and lemma [B.7](https://arxiv.org/html/2506.03337v1#A2.Thmtheorem7):

$$ $\displaystyle\mathbb{E}_{\overline{z}}\,f(\mathbf{w}^{r+1})$ $\displaystyle\leq\mathbb{E}_{\overline{z}}\,f(\mathbf{w}^{r})-\;\eta\,T\,\sqrt {c}\,(1+\sqrt{c_{h}})\,\|\nabla f(\mathbf{w}^{r})\|^{2}$ $\displaystyle\quad-\;\eta\,T\,\sqrt{c}\,\sigma_{h}\,\|\nabla f(\mathbf{w}^{r}) \|+\;\frac{L\,\eta^{2}\,T\,(2+u)\,c}{2K}\sum_{k=1}^{K}\sum_{t=0}^{T-1}\|\nabla f _{k}(\mathbf{w}^{r,t})\|^{2}\,.$ $$

According to the equation [7](https://arxiv.org/html/2506.03337v1#A2.E7), we know that the client-average squared gradient has upper bound. We substitute the equation [7](https://arxiv.org/html/2506.03337v1#A2.E7) to the above inequality last term we get:

$$ $\displaystyle\mathbb{E}_{\overline{z}}\,f(w^{r+1})$ $\displaystyle\leq\mathbb{E}_{\overline{z}}\,f(w^{r})-\,\eta\,T\,\sqrt{c}\,(1+ \sqrt{c_{h}})\,\|\nabla f(w^{r})\|^{2}-\,\eta\,T\,\sqrt{c}\,\sigma_{h}\,\| \nabla f(w^{r})\|$ $\displaystyle\quad+\,\frac{L\,\eta^{2}\,T\,(2+u)\,c}{2K}\sum_{k=1}^{K}\Bigl{[} \frac{2\,L\,(u+2)}{c}\bigl{(}f_{k}(w^{r})-f_{k}^{*}\bigr{)}+T\,\sigma^{2}\Bigr {]}$ $\displaystyle\leq\mathbb{E}_{\overline{z}}\,f(w^{r})-\,\eta\,T\,\sqrt{c}\,(1+ \sqrt{c_{h}})\,\|\nabla f(w^{r})\|^{2}-\,\eta\,T\,\sqrt{c}\,\sigma_{h}\,\| \nabla f(w^{r})\|$ $\displaystyle\quad+\,\frac{L^{2}\,\eta^{2}\,T\,(2+u)\,(u+2)}{K}\sum_{k=1}^{K} \bigl{(}f_{k}(w^{r})-f_{k}^{*}\bigr{)}+\,\frac{L\,\eta^{2}\,T^{2}\,(2+u)\,c}{2 }\,\sigma^{2}$ (12) $$

Accumulating Over $R$ Rounds.
Summing equation [B.4](https://arxiv.org/html/2506.03337v1#A2.Ex68) over $r=0$ to $R-1$, we get:

$$ $\displaystyle\mathbb{E}_{\overline{z}}\bigl{[}f(w^{R})\bigr{]}-\mathbb{E}_{ \overline{z}}\bigl{[}f(w^{0})\bigr{]}$ $\displaystyle\leq-\,\eta\,T\,\sqrt{c}\,(1+\sqrt{c_{h}})\sum_{r=0}^{R-1}\bigl{ \|}\nabla f(w^{r})\bigr{\|}^{2}$ (13) $\displaystyle\quad-\,\eta\,T\,\sqrt{c}\,\sigma_{h}\sum_{r=0}^{R-1}\bigl{\|} \nabla f(w^{r})\bigr{\|}$ $\displaystyle\quad+\,\frac{L^{2}\,\eta^{2}\,T\,(2+u)\,(u+2)}{K}\sum_{r=0}^{R-1 }\sum_{k=1}^{K}\bigl{(}f_{k}(w^{r})-f_{k}^{*}\bigr{)}$ $\displaystyle\quad+\,\frac{L\,\eta^{2}\,T^{2}\,(2+u)\,c}{2}\,\sigma^{2}\,R\,.$ $$

From the accumulated global descent inequality over $R$ rounds:

First we set

$$ $S\;=\;\sum_{r=0}^{R-1}\|\nabla f(w^{r})\|^{2}.$ $$

This represents the sum of squared gradient norms over $R$ rounds. The second term in the inequality involves $\sum_{r=0}^{R-1}\|\nabla f(w^{r})\|$, and we apply the Cauchy-Schwarz inequality to it. For the sequence $a_{r}=\|\nabla f(w^{r})\|$ (with $r=0,1,\ldots,R-1$), we consider it as a vector in $\mathbb{R}^{R}$ along with a vector of ones:

$$ $\sum_{r=0}^{R-1}\|\nabla f(w^{r})\|=\sum_{r=0}^{R-1}\|\nabla f(w^{r})\|\cdot 1 \leq\sqrt{\sum_{r=0}^{R-1}\|\nabla f(w^{r})\|^{2}}\cdot\sqrt{\sum_{r=0}^{R-1}1 ^{2}}.$ $$

Since $\sum_{r=0}^{R-1}1^{2}=R$, we obtain:

$$ $\sum_{r=0}^{R-1}\|\nabla f(w^{r})\|\leq\sqrt{\sum_{r=0}^{R-1}\|\nabla f(w^{r}) \|^{2}}\cdot\sqrt{R}=\sqrt{R}\sqrt{S}=\sqrt{RS}.$ $$

Substituting this into the second term, we have:

$$ $\eta T\sqrt{c}\sigma_{h}\sum_{r=0}^{R-1}\|\nabla f(w^{r})\|\leq\eta T\sqrt{c} \sigma_{h}\sqrt{RS}.$ $$

Thus, the inequality becomes:

$$ $\displaystyle\mathbb{E}_{\overline{z}}[f(w^{R})]-\mathbb{E}_{\overline{z}}[f(w ^{0})]$ $\displaystyle\leq-\eta T\sqrt{c}(1+\sqrt{c_{h}})S+\eta T\sqrt{c}\sigma_{h} \sqrt{RS}$ $\displaystyle\quad+\frac{L^{2}\eta^{2}T(2+u)(u+2)}{K}\sum_{r=0}^{R-1}\sum_{k=1 }^{K}(f_{k}(w^{r})-f_{k}^{*})$ $\displaystyle\quad+\frac{L\eta^{2}T^{2}(2+u)c}{2}\sigma^{2}R.$ $$

Second, we focus on the term $\eta T\sqrt{c}\sigma_{h}\sqrt{RS}$ and apply Young’s Inequality with $\delta>0$ and non-negative real numbers $x$ and $y$,

$$ $xy\leq\frac{x^{2}}{2\delta}+\frac{y^{2}\delta}{2}.$ $$

We identify $x=\sqrt{S}$ and $y=\eta T\sqrt{c}\sigma_{h}\sqrt{R}$, since:

$$ $\eta T\sqrt{c}\sigma_{h}\sqrt{RS}=(\eta T\sqrt{c}\sigma_{h}\sqrt{R})\cdot\sqrt {S}.$ $$

Applying Young’s Inequality:

$$ $\sqrt{S}\cdot(\eta T\sqrt{c}\sigma_{h}\sqrt{R})\leq\frac{(\sqrt{S})^{2}}{2 \delta}+\frac{(\eta T\sqrt{c}\sigma_{h}\sqrt{R})^{2}\delta}{2}.$ $$

Therefore:

$$ $\eta T\sqrt{c}\sigma_{h}\sqrt{RS}\leq\frac{S}{2\delta}+\frac{\eta^{2}T^{2}c \sigma_{h}^{2}R\delta}{2}.$ $$

$$ $-\eta T\sqrt{c}\sigma_{h}\sqrt{RS}\leq\frac{S}{2\delta}+\frac{\eta^{2}T^{2}c \sigma_{h}^{2}R\delta}{2}.$ $$

Finally we replace the second term in the inequality with the above result:

$$ $\displaystyle\mathbb{E}_{\overline{z}}[f(w^{R})]-\mathbb{E}_{\overline{z}}[f(w ^{0})]$ $\displaystyle\leq-\eta T\sqrt{c}(1+\sqrt{c_{h}})S+\left(\frac{S}{2\delta}+ \frac{\eta^{2}T^{2}c\sigma_{h}^{2}R\delta}{2}\right)$ $\displaystyle\quad+\frac{L^{2}\eta^{2}T(2+u)^{2}}{K}\sum_{r=0}^{R-1}\sum_{k=1} ^{K}(f_{k}(w^{r})-f_{k}^{*})$ $\displaystyle\quad+\frac{L\eta^{2}T^{2}(2+u)c}{2}\sigma^{2}R.$ $$

This inequality now depends on $\delta$.

$$ $\displaystyle\Bigl{(}\eta T\sqrt{c}\,\bigl{(}1+\sqrt{c_{h}}\bigr{)}-\frac{1}{2 \delta}\Bigr{)}\sum_{r=0}^{R-1}\|\nabla f(w^{r})\|^{2}\;\leq$ $\displaystyle\;\mathbb{E}_{\overline{z}}\!\bigl{[}f(w^{0})-f(w^{R})\bigr{]}+{ \eta^{2}T^{2}c\sigma_{h}^{2}R\delta}{2}$ (14) $\displaystyle+\frac{L^{2}\eta^{2}T\,(2+u)^{2}}{K}\sum_{r=0}^{R-1}\sum_{k=1}^{K }\!\bigl{(}f_{k}(w^{r})-f_{k}^{*}\bigr{)}$ $\displaystyle+\frac{L\,\eta^{2}T^{2}(2+u)c\,\sigma^{2}R}{2}\;.$ $$

According to Assumption [B.1](https://arxiv.org/html/2506.03337v1#A2.Thmtheorem1), we have:

$$ $f_{k}(\mathbf{w}^{*})\leq f_{k}(\mathbf{w}_{k}^{*})+\langle\nabla f_{k}( \mathbf{w}_{k}^{*}),\mathbf{w}^{*}-\mathbf{w}_{k}^{*}\rangle+\frac{L}{2}\| \mathbf{w}^{*}-\mathbf{w}_{k}^{*}\|_{2}^{2}.$ $$

Since $\mathbf{w}_{k}^{*}$ is the minimizer of $f_{k}(\mathbf{w})$, the gradient at the local optimum must be zero:

$$ $\nabla f_{k}(\mathbf{w}_{k}^{*})=0.$ $$

Substituting this into the inner product term:

$$ $\langle\nabla f_{k}(\mathbf{w}_{k}^{*}),\mathbf{w}^{*}-\mathbf{w}_{k}^{*} \rangle=\langle 0,\mathbf{w}^{*}-\mathbf{w}_{k}^{*}\rangle=0.$ $$

Thus, the inner product term disappears because the gradient at $\mathbf{w}_{k}^{*}$ is zero, making the inner product with any vector (including $\mathbf{w}^{*}-\mathbf{w}_{k}^{*}$) equal to zero.

With the inner product term vanishing, the inequality simplifies to:

$$ $f_{k}(\mathbf{w}^{*})\leq f_{k}(\mathbf{w}_{k}^{*})+\frac{L}{2}\Delta_{k}.$ $$

This provides an upper bound on $f_{k}(\mathbf{w}^{*})$ in terms of the local optimal loss $f_{k}^{*}$ and the optimality gap $\Delta_{k}$.

The global optimal loss is defined as:

$$ $f^{*}=f(\mathbf{w}^{*})=\sum_{k=1}^{K}p_{k}f_{k}(\mathbf{w}^{*}).$ $$

Using the bound derived for each local loss:

$$ $f_{k}(\mathbf{w}^{*})\leq f_{k}^{*}+\frac{L}{2}\Delta_{k},$ $$

we substitute this into the expression for $f^{*}$:

$$ $f^{*}=\sum_{k=1}^{K}p_{k}f_{k}(\mathbf{w}^{*})\leq\sum_{k=1}^{K}p_{k}\left(f_{ k}^{*}+\frac{L}{2}\Delta_{k}\right).$ $$

Expanding the right-hand side:

$$ $f^{*}\leq\sum_{k=1}^{K}p_{k}f_{k}^{*}+\frac{L}{2}\sum_{k=1}^{K}p_{k}\Delta_{k}.$ $$

From the above equation, we have:

$$ $f^{*}-\frac{L}{2}\sum_{k=1}^{K}p_{k}\Delta_{k}\leq\sum_{k=1}^{K}p_{k}f_{k}^{*}.$ $$

$$ $-\frac{1}{K}\sum_{k=1}^{K}f_{k}^{*}\leq-f^{*}+\frac{L}{2K}\sum_{k=1}^{K}\Delta _{k}.$ $$

From the equation [14](https://arxiv.org/html/2506.03337v1#A2.E14), we have the term:

$$ $\frac{L^{2}\eta^{2}T(2+u)^{2}}{K}\sum_{r=0}^{R-1}\sum_{k=1}^{K}\left(f_{k}(w^{ r})-f_{k}^{*}\right).$ $$

First, we express the double sum as:

$$ $\sum_{r=0}^{R-1}\sum_{k=1}^{K}\left(f_{k}(w^{r})-f_{k}^{*}\right)=\sum_{r=0}^{ R-1}\left(\sum_{k=1}^{K}f_{k}(w^{r})-\sum_{k=1}^{K}f_{k}^{*}\right).$ $$

Since $p_{k}=\frac{1}{K}$, we have:

$$ $\sum_{k=1}^{K}f_{k}(w^{r})=Kf(w^{r}),$ $$

where $f(w^{r})=\sum_{k=1}^{K}p_{k}f_{k}(w^{r})=\frac{1}{K}\sum_{k=1}^{K}f_{k}(w^{r})$. Therefore:

$$ $\sum_{r=0}^{R-1}\sum_{k=1}^{K}\left(f_{k}(w^{r})-f_{k}^{*}\right)=\sum_{r=0}^{ R-1}\left(Kf(w^{r})-\sum_{k=1}^{K}f_{k}^{*}\right).$ $$

From the earlier derivation, we have the inequality:

$$ $-\frac{1}{K}\sum_{k=1}^{K}f_{k}^{*}\leq-f^{*}+\frac{L}{2K}\sum_{k=1}^{K}\Delta _{k}.$ $$

Substituting this into the expression above:

$$ $\sum_{r=0}^{R-1}\sum_{k=1}^{K}\left(f_{k}(w^{r})-f_{k}^{*}\right)\leq\sum_{r=0 }^{R-1}\left(Kf(w^{r})-\left(Kf^{*}-\frac{L}{2}\sum_{k=1}^{K}\Delta_{k}\right) \right).$ $$

Thus:

$$ $\sum_{r=0}^{R-1}\sum_{k=1}^{K}\left(f_{k}(w^{r})-f_{k}^{*}\right)\leq\sum_{r=0 }^{R-1}\left(Kf(w^{r})-Kf^{*}+\frac{L}{2}\sum_{k=1}^{K}\Delta_{k}\right).$ $$

Since $\Delta_{k}$ is constant across iterations, we can factor it out:

$$ $K\sum_{r=0}^{R-1}(f(w^{r})-f^{*})+\frac{L}{2}\sum_{r=0}^{R-1}\sum_{k=1}^{K} \Delta_{k}=K\sum_{r=0}^{R-1}(f(w^{r})-f^{*})+\frac{LR}{2}\sum_{k=1}^{K}\Delta_ {k}.$ $$

Now, multiply by the coefficient:

$$ $\frac{L^{2}\eta^{2}T(2+u)^{2}}{K}\sum_{r=0}^{R-1}\sum_{k=1}^{K}\left(f_{k}(w^{ r})-f_{k}^{*}\right)\leq\frac{L^{2}\eta^{2}T(2+u)^{2}}{K}\left[K\sum_{r=0}^{R- 1}(f(w^{r})-f^{*})+\frac{LR}{2}\sum_{k=1}^{K}\Delta_{k}\right].$ $$

Simplifying:

$$ $L^{2}\eta^{2}T(2+u)^{2}\sum_{r=0}^{R-1}(f(w^{r})-f^{*})+\frac{L^{3}\eta^{2}T(2 +u)^{2}R}{2K}\sum_{k=1}^{K}\Delta_{k}.$ $$

Substituting this result into the original target inequality, we get:

$$ $\displaystyle\left(\eta T\sqrt{c}\left(1+\sqrt{c_{h}}\right)-\frac{1}{2\delta} \right)\sum_{r=0}^{R-1}\|\nabla f(w^{r})\|^{2}$ $\displaystyle\leq\mathbb{E}_{\overline{z}}\left[f(w^{0})-f(w^{R})\right]+\frac {\eta^{2}T^{2}c\sigma_{h}^{2}R\delta}{2}$ $\displaystyle\quad+L^{2}\eta^{2}T(2+u)^{2}\sum_{r=0}^{R-1}(f(w^{r})-f^{*})$ $\displaystyle\quad+\frac{L^{3}\eta^{2}T(2+u)^{2}R}{2K}\sum_{k=1}^{K}\Delta_{k}$ $\displaystyle\quad+\frac{L\eta^{2}T^{2}(2+u)c\sigma^{2}R}{2}.$ $$

According to the Assumption [B.2](https://arxiv.org/html/2506.03337v1#A2.Thmtheorem2) we have:

$$ $2\mu(f(\mathbf{w}^{r})-f^{*})\leq\|\nabla f(\mathbf{w}^{r})\|^{2},\quad\forall \mathbf{w}^{r}\in\mathbb{R}^{d},$ $$

$$ $2\mu\sum_{r=0}^{R-1}(f(\mathbf{w}^{r})-f^{*})\leq\sum_{r=0}^{R-1}\|\nabla f( \mathbf{w}^{r})\|^{2},\quad\forall\mathbf{w}^{r}\in\mathbb{R}^{d},$ $$

We let $\eta T\sqrt{c}\left(1+\sqrt{c_{h}}\right)-\frac{1}{2\delta}>0$ and substitute the above inequality, we have:

$$ $\displaystyle 2\mu(\eta T\sqrt{c}\left(1+\sqrt{c_{h}}\right)-\frac{1}{2\delta} )\sum_{r=0}^{R-1}(f(\mathbf{w}^{r})-f^{*})$ $\displaystyle\leq\mathbb{E}_{\overline{z}}\left[f(w^{0})-f(w^{R})\right]+\frac {\eta^{2}T^{2}c\sigma_{h}^{2}R\delta}{2}$ $\displaystyle\quad+L^{2}\eta^{2}T(2+u)^{2}\sum_{r=0}^{R-1}(f(w^{r})-f^{*})$ $\displaystyle\quad+\frac{L^{3}\eta^{2}T(2+u)^{2}R}{2K}\sum_{k=1}^{K}\Delta_{k}$ $\displaystyle\quad+\frac{L\eta^{2}T^{2}(2+u)c\sigma^{2}R}{2}.$ $$

$$ $\displaystyle\sum_{r=0}^{R-1}\bigl{(}f(w^{r})-f^{*}\bigr{)}\;\leq$ $\displaystyle\;\frac{\displaystyle\mathbb{E}_{\overline{z}}\bigl{[}f(w^{0})-f( w^{R})\bigr{]}}{\displaystyle 2\mu\bigl{(}\eta T\sqrt{c}(1+\sqrt{c_{h}})-\frac {1}{2\delta}\bigr{)}\;-\;L^{2}\eta^{2}T(2+u)^{2}}$ (15) $\displaystyle+\;\frac{\displaystyle\eta^{2}T^{2}\,c\,\sigma_{h}^{2}\,R\delta}{ \displaystyle 2\Bigl{[}\,2\mu\bigl{(}\eta T\sqrt{c}(1+\sqrt{c_{h}})-\frac{1}{2 \delta}\bigr{)}\;-\;L^{2}\eta^{2}T(2+u)^{2}\Bigr{]}}$ $\displaystyle+\;\frac{\displaystyle L^{3}\,\eta^{2}T\,(2+u)^{2}\,R\;\sum_{k=1} ^{K}\Delta_{k}}{\displaystyle 2K\,\Bigl{[}\,2\mu\bigl{(}\eta T\sqrt{c}(1+\sqrt {c_{h}})-\frac{1}{2\delta}\bigr{)}\;-\;L^{2}\eta^{2}T(2+u)^{2}\Bigr{]}}$ $\displaystyle+\;\frac{\displaystyle L\,\eta^{2}T^{2}\,(2+u)\,c\,\sigma^{2}\,R} {\displaystyle 2\Bigl{[}\,2\mu\bigl{(}\eta T\sqrt{c}(1+\sqrt{c_{h}})-\frac{1}{ 2\delta}\bigr{)}\;-\;L^{2}\eta^{2}T(2+u)^{2}\Bigr{]}}\,.$ $$

$$ $\displaystyle\frac{1}{R}\sum_{r=0}^{R-1}\bigl{(}f(w^{r})-f^{*}\bigr{)}\;\leq$ $\displaystyle\;\frac{1}{R}\frac{\displaystyle\mathbb{E}_{\overline{z}}\bigl{[} f(w^{0})-f(w^{R})\bigr{]}}{\displaystyle 2\mu\bigl{(}\eta T\sqrt{c}(1+\sqrt{c_ {h}})-\frac{1}{2\delta}\bigr{)}\;-\;L^{2}\eta^{2}T(2+u)^{2}}$ (16) $\displaystyle+\;\frac{\displaystyle\eta^{2}T^{2}\,c\,\sigma_{h}^{2}\ \delta}{ \displaystyle 2\Bigl{[}\,2\mu\bigl{(}\eta T\sqrt{c}(1+\sqrt{c_{h}})-\frac{1}{2 \delta}\bigr{)}\;-\;L^{2}\eta^{2}T(2+u)^{2}\Bigr{]}}$ $\displaystyle+\;\frac{\displaystyle L^{3}\,\eta^{2}T\,(2+u)^{2}\;\sum_{k=1}^{K }\Delta_{k}}{\displaystyle 2K\,\Bigl{[}\,2\mu\bigl{(}\eta T\sqrt{c}(1+\sqrt{c_ {h}})-\frac{1}{2\delta}\bigr{)}\;-\;L^{2}\eta^{2}T(2+u)^{2}\Bigr{]}}$ $\displaystyle+\;\frac{\displaystyle L\,\eta^{2}T^{2}\,(2+u)\,c\,\sigma^{2}\ }{ \displaystyle 2\Bigl{[}\,2\mu\bigl{(}\eta T\sqrt{c}(1+\sqrt{c_{h}})-\frac{1}{2 \delta}\bigr{)}\;-\;L^{2}\eta^{2}T(2+u)^{2}\Bigr{]}}\,.$ $$

We select $\delta=\frac{1}{\eta T\sqrt{c}(1+\sqrt{c_{h}})}$, which leads to:

$$ $\frac{1}{2\delta}=\frac{\eta T\sqrt{c}(1+\sqrt{c_{h}})}{2}$ $$

Substituting into the denominator:

$$ $2\mu\left(\eta T\sqrt{c}(1+\sqrt{c_{h}})-\frac{\eta T\sqrt{c}(1+\sqrt{c_{h}})} {2}\right)=\mu\eta T\sqrt{c}(1+\sqrt{c_{h}})$ $$

With the chosen $\delta$, we have:

$$ $\displaystyle\frac{1}{R}\sum_{r=0}^{R-1}\left(f(w^{r})-f^{*}\right)$ $\displaystyle\leq\frac{1}{R}\cdot\frac{\mathbb{E}_{\overline{z}}\left[f(w^{0}) -f(w^{R})\right]}{\mu\eta T\sqrt{c}(1+\sqrt{c_{h}})-L^{2}\eta^{2}T(2+u)^{2}}$ (17) $\displaystyle\quad+\frac{\sqrt{c}\sigma_{h}^{2}}{2(1+\sqrt{c_{h}})\left[\mu \sqrt{c}(1+\sqrt{c_{h}})-L^{2}\eta(2+u)^{2}\right]}$ $\displaystyle\quad+\frac{L^{3}\eta(2+u)^{2}\sum_{k=1}^{K}\Delta_{k}}{2K\left[ \mu\sqrt{c}(1+\sqrt{c_{h}})-L^{2}\eta(2+u)^{2}\right]}$ $\displaystyle\quad+\frac{L\eta T(2+u)c\sigma^{2}}{2\left[\mu\sqrt{c}(1+\sqrt{c _{h}})-L^{2}\eta(2+u)^{2}\right]},$ $$

where the step-size $\eta$ must satisfy:
$\eta<\frac{\mu\sqrt{c}(1+\sqrt{c_{h}})}{L^{2}(2+u)^{2}}\quad$ to ensure denominator positivity.

Plugging in a constant learning rate $\eta=\min\left\{\frac{1}{L(u+2)},\frac{\mu\,\sqrt{c}\bigl{(}1+\sqrt{c_{h}}
\bigr{)}}{2\,L^{2}(2+u)^{2}}\right\}$. We substitute this $\eta$ to equation [17](https://arxiv.org/html/2506.03337v1#A2.E17) and get:

$$ $\displaystyle\frac{1}{R}\sum_{r=0}^{R-1}\!\bigl{(}f(w^{r})-f^{*}\bigr{)}\;\leq$ $\displaystyle\frac{4L^{2}(2+u)^{2}}{\mu^{2}c\bigl{(}1+\sqrt{c_{h}}\bigr{)}^{2} TR}\;\mathbb{E}_{\overline{z}}\!\bigl{[}f(w^{0})-f^{*}\bigr{]}$ $\displaystyle+\frac{\sigma_{h}^{2}}{\mu\bigl{(}1+\sqrt{c_{h}}\bigr{)}^{2}}+ \frac{L}{K}\,\sum_{k=1}^{K}\Delta_{k}+\frac{T\,c\,\sigma^{2}}{2L\,(2+u)}\;.$ $$

$$ $\displaystyle\frac{1}{R}\sum_{r=0}^{R-1}\bigl{(}f(w^{r})-f^{*}\bigr{)}\leq \mathcal{O}\!\left(\frac{(2+u)^{2}}{TR}\cdot\mathbb{E}[f(w^{0})-f(w^{R})] \right)+\mathcal{O}\!\left(\frac{T}{2+u}\right)+\mathcal{O}(1).$ (18) $$

∎

###### Proof.

### B.5 Meerkat-vp Convergence Analysis

We propose a Virtual Path Client Selection (Meerkat-vp) mechanism that identifies clients with highly heterogeneous data distributions based on their optimization trajectories. Instead of excluding them, Meerkat-vp applies early stopping to these clients to limit their adverse influence on global model updates while still preserving their participation.

###### Proof.

Motivation for Early Stopping: In federated learning, clients perform local updates starting from the global model $w^{r}$. For $T>1$, clients may drift towards their local optima, introducing bias into the global update due to data heterogeneity. By identifying "bad" clients and limiting them to one update step, we reduce their drift and align their contributions more closely with the global gradient.

We divide the $K$ clients into two groups:

- •
Balanced-distribution clients ($K_{g}$): Perform $T$ local step updates.
- •
Skewed-distribution clients ($K_{b}$): Perform only 1 local step update.

The global model update becomes:

$$ $w^{r+1}=w^{r}+\frac{1}{K}\sum_{k\in K_{g}}(w_{k}^{r,T}-w^{r})+\frac{1}{K}\sum_ {k\in K_{b}}(w_{k}^{r,1}-w^{r})$ $$

where:

$$ $w_{k}^{r,T}-w^{r}=-\eta\sum_{t=0}^{T-1}\widehat{\nabla}f_{k}(w^{r,t}),\quad w_ {k}^{r,1}-w^{r}=-\eta\widehat{\nabla}f_{k}(w^{r})$ $$

###### Proof.

#### Loss Descent Analysis

Using the $L$-smoothness property:

$$ $f(w^{r+1})\leq f(w^{r})+\langle\nabla f(w^{r}),w^{r+1}-w^{r}\rangle+\frac{L}{2 }\|w^{r+1}-w^{r}\|^{2}$ $$

We analyze the inner product term:

$$ $\displaystyle\langle\nabla f(w^{r}),w^{r+1}-w^{r}\rangle$ $\displaystyle=\sum_{k=1}^{K}p_{k}\langle\nabla f(\mathbf{w}^{r}),\mathbf{w}_{k }^{r,T}-\mathbf{w}^{r}\rangle$ $$

$$ $\displaystyle\sum_{k=1}^{K}p_{k}\langle\nabla f(\mathbf{w}^{r}),\mathbf{w}_{k} ^{r,T}-\mathbf{w}^{r}\rangle$ $\displaystyle=-\eta\sum_{k=1}^{K}p_{k}\langle\nabla f(\mathbf{w}^{r}),\sum_{t= 0}^{T-1}\widehat{\nabla}f_{k}(\mathbf{w}^{r,t},\overline{\mathbf{z}}_{t})\rangle$ $\displaystyle=-\eta\sum_{k=1}^{K}p_{k}\sum_{t=0}^{T-1}\langle\nabla f(\mathbf{ w}^{r}),\widehat{\nabla}f_{k}(\mathbf{w}^{r,t},\overline{\mathbf{z}}_{t})\rangle$ $$

Since we have balanced-distribution clients and skewed-distribution clients:

$$ $\langle\nabla f(w^{r}),w^{r+1}-w^{r}\rangle=\frac{1}{K}\sum_{k\in K_{g}} \langle\nabla f(w^{r}),w_{k}^{r,T}-w^{r}\rangle+\frac{1}{K}\sum_{k\in K_{b}} \langle\nabla f(w^{r}),w_{k}^{r,1}-w^{r}\rangle$ $$

$$ $\displaystyle\langle\nabla f(w^{r}),w^{r+1}-w^{r}\rangle$ $\displaystyle=-\frac{\eta}{K}\sum_{k\in K_{g}}\sum_{t=0}^{T-1}\langle\nabla f( w^{r}),\widehat{\nabla}f_{k}(w^{r,t})\rangle$ (19) $\displaystyle\quad-\frac{\eta}{K}\sum_{k\in K_{b}}\langle\nabla f(w^{r}), \widehat{\nabla}f_{k}(w^{r})\rangle$ $$

Since $\widehat{\nabla}f_{k}^{t}$ is unbiased, we have:

$$ $\sum_{k=1}^{K}\sum_{t=0}^{T-1}\bigl{\langle}\nabla f(w^{r}),\,\widehat{\nabla} f_{k}(\mathbf{w}^{r,t},\overline{\mathbf{z}}_{t})\bigr{\rangle}\;=\;\sum_{k=1} ^{K}\sum_{t=0}^{T-1}\bigl{\langle}\nabla f(w^{r}),\,\mathbb{E}_{\overline{z}} \!\bigl{[}\widehat{\nabla}f_{k}(\mathbf{w}^{r,t},\overline{\mathbf{z}}_{t}) \bigr{]}\bigr{\rangle}$ $$

We substitute the equation [4](https://arxiv.org/html/2506.03337v1#A2.E4) and get:

$$ $\sum_{k=1}^{K}\sum_{t=0}^{T-1}\bigl{\langle}\nabla f(w^{r}),\,\mathbb{E}_{ \overline{z}}\!\bigl{[}\widehat{\nabla}f_{k}(\mathbf{w}^{r,t},\overline{ \mathbf{z}}_{t})\bigr{]}\bigr{\rangle}\;=\;\sum_{k=1}^{K}\sum_{t=0}^{T-1}\bigl {\langle}\nabla f(w^{r}),\,\mathbf{m}\odot\nabla f_{k}(w^{r,t})\bigr{\rangle}.$ $$

Thus taking expectation of equation [19](https://arxiv.org/html/2506.03337v1#A2.E19), we can get:

$$ $\displaystyle\mathbb{E}_{\overline{z}}\langle\nabla f(\mathbf{w}^{r}),\mathbf{ w}^{r+1}-\mathbf{w}^{r}\rangle=-\frac{\eta}{K}\Bigg{(}$ $\displaystyle\sum_{k\in K_{g}}\sum_{t=0}^{T-1}\langle\nabla f(\mathbf{w}^{r}), \,\mathbf{m}\odot\nabla f_{k}(\mathbf{w}^{r,t})\rangle$ (20) $\displaystyle+\sum_{k\in K_{b}}\langle\nabla f(\mathbf{w}^{r}),\,\mathbf{m} \odot\nabla f_{k}(\mathbf{w}^{r})\rangle\Bigg{)}$ $$

Under the Cauchy–Schwarz inequality, we have:

$$ $\bigl{\langle}\nabla f(\mathbf{w}^{r}),\;\mathbf{m}\odot\nabla f_{k}(\mathbf{w }^{r,t})\bigr{\rangle}\;\leq\;\|\nabla f(\mathbf{w}^{r})\|\;\|\mathbf{m}\odot \nabla f_{k}(\mathbf{w}^{r,t})\|$ $$

We substitute Assumption [B.6](https://arxiv.org/html/2506.03337v1#A2.Thmtheorem6) get:

$$ $\|\nabla f(\mathbf{w}^{r})\|\;\|\mathbf{m}\odot\nabla f_{k}(\mathbf{w}^{r,t}) \|\;=\;\sqrt{c}\,\|\nabla f(\mathbf{w}^{r})\|\;\|\nabla f_{k}(\mathbf{w}^{r,t} )\|.$ $$

Thus we get:

$$ $\bigl{\langle}\nabla f(\mathbf{w}^{r}),\;\mathbf{m}\odot\nabla f_{k}(\mathbf{w }^{r,t})\bigr{\rangle}\;\leq\;\sqrt{c}\,\|\nabla f(\mathbf{w}^{r})\|\;\|\nabla f _{k}(\mathbf{w}^{r,t})\|.$ $$

By the triangle inequality, we have

$$ $\|\nabla f_{k}(\mathbf{w}^{r,t})\|\;\leq\;\|\nabla f(\mathbf{w}^{r})\|+\| \nabla f_{k}(\mathbf{w}^{r,t})-\nabla f(\mathbf{w}^{r})\|$ $$

We substitute Assumption [B.3](https://arxiv.org/html/2506.03337v1#A2.Thmtheorem3) and use the properties of square roots we get:

$$ $\displaystyle\|\nabla f(\mathbf{w}^{r})\|+\|\nabla f_{k}(\mathbf{w}^{r,t})- \nabla f(\mathbf{w}^{r})\|$ $\displaystyle\leq\|\nabla f(\mathbf{w}^{r})\|+\sqrt{\,c_{h}\,\|\nabla f( \mathbf{w}^{r})\|^{2}+\sigma_{h}^{2}\,}$ $\displaystyle\leq(1+\sqrt{c_{h}})\,\|\nabla f(\mathbf{w}^{r})\|+\sigma_{h}.$ $$

Using the bound
$\langle\nabla f(\mathbf{w}^{r}),\;m\odot\nabla f_{k}(\mathbf{w}^{r,t})\rangle
\leq\sqrt{c}\,\|\nabla f(\mathbf{w}^{r})\|\;\|\nabla f_{k}\|$
from Cauchy–Schwarz and Assumption [B.6](https://arxiv.org/html/2506.03337v1#A2.Thmtheorem6), and then plugging in the above,
we obtain

$$ $\displaystyle\langle\nabla f(\mathbf{w}^{r}),\,m\odot\nabla f_{k}(\mathbf{w}^{ r,t})\rangle$ $\displaystyle\leq\sqrt{c}\,\|\nabla f(\mathbf{w}^{r})\|\bigl{[}(1+\sqrt{c_{h}} )\,\|\nabla f(\mathbf{w}^{r})\|+\sigma_{h}\bigr{]}$ $\displaystyle\leq\sqrt{c}\,(1+\sqrt{c_{h}})\,\|\nabla f(\mathbf{w}^{r})\|^{2} \;+\;\sqrt{c}\,\sigma_{h}\,\|\nabla f(\mathbf{w}^{r})\|.$ $$

Since this bound holds uniformly for all $k$ and $t$, and based on the equation [20](https://arxiv.org/html/2506.03337v1#A2.E20) we get:

$$ $\displaystyle\sum_{k\in K_{g}}\sum_{t=0}^{T-1}\langle\nabla f(\mathbf{w}^{r}), \mathbf{m}\odot\nabla f_{k}(\mathbf{w}^{r,t})\rangle+\sum_{k\in K_{b}}\langle \nabla f(\mathbf{w}^{r}),\mathbf{m}\odot\nabla f_{k}(\mathbf{w}^{r})\rangle$ $\displaystyle\leq\left(|K_{g}|T+|K_{b}|\right)\left[\sqrt{c}(1+\sqrt{c_{h}})\| \nabla f(\mathbf{w}^{r})\|^{2}+\sqrt{c}\sigma_{h}\|\nabla f(\mathbf{w}^{r})\| \right].$ $$

We get:

$$ $\displaystyle\mathbb{E}_{\overline{z}}[f(w^{r+1})]$ $\displaystyle\leq\mathbb{E}_{\overline{z}}[f(w^{r})]-\frac{\eta\sqrt{c}\alpha} {K}(1+\sqrt{c_{h}})\|\nabla f(w^{r})\|^{2}$ (21) $\displaystyle\quad-\frac{\eta\sqrt{c}\alpha}{K}\sigma_{h}\|\nabla f(w^{r})\|+ \frac{L}{2}\mathbb{E}_{\overline{z}}\|w^{r+1}-w^{r}\|^{2}$ $$

where $\alpha=|K_{g}|T+|K_{b}|$.

Since the global model update is given by:

$$ $w^{r+1}=w^{r}+\frac{1}{K}\sum_{k\in K_{g}}(w_{k}^{r,T}-w^{r})+\frac{1}{K}\sum_ {k\in K_{b}}(w_{k}^{r,1}-w^{r})$ $$

We substitute the local updates and the squared norm is:

$$ $\|w^{r+1}-w^{r}\|^{2}=\frac{\eta^{2}}{K^{2}}\left\|\sum_{k\in K_{g}}\sum_{t=0} ^{T-1}\widehat{\nabla}f_{k}(w^{r,t})+\sum_{k\in K_{b}}\widehat{\nabla}f_{k}(w^ {r})\right\|^{2}$ $$

Define the update contribution per client:

$$ $\widehat{\Delta}_{k}=\begin{cases}-\eta\sum_{t=0}^{T-1}\widehat{\nabla}f_{k}(w ^{r,t})&\text{if }k\in K_{g},\\ -\eta\widehat{\nabla}f_{k}(w^{r})&\text{if }k\in K_{b}.\end{cases}$ $$

Then:

$$ $w^{r+1}-w^{r}=\frac{1}{K}\sum_{k=1}^{K}\widehat{\Delta}_{k}$ $$

$$ $\|w^{r+1}-w^{r}\|^{2}=\frac{1}{K^{2}}\left\|\sum_{k=1}^{K}\widehat{\Delta}_{k} \right\|^{2}$ $$

Using the Cauchy-Schwarz inequality:

$$ $\left\|\sum_{k=1}^{K}\widehat{\Delta}_{k}\right\|^{2}\leq K\sum_{k=1}^{K}\| \widehat{\Delta}_{k}\|^{2},\quad\text{where }\widehat{\Delta}_{k}\text{ denotes the actual model update on client }k.$ $$

So:

$$ $\|w^{r+1}-w^{r}\|^{2}\leq\frac{1}{K}\sum_{k=1}^{K}\|\widehat{\Delta}_{k}\|^{2}$ $$

Now compute $\|\widehat{\Delta}_{k}\|^{2}$:

$$ $\|\widehat{\Delta}_{k}\|^{2}=\eta^{2}\left\|\sum_{t=0}^{T-1}\widehat{\nabla}f_ {k}(w^{r,t})\right\|^{2}\quad\text{for }k\in K_{g},$ $$

$$ $\|\widehat{\Delta}_{k}\|^{2}=\eta^{2}\left\|\widehat{\nabla}f_{k}(w^{r})\right \|^{2}\quad\text{for }k\in K_{b}.$ $$

Thus:

$$ $\|w^{r+1}-w^{r}\|^{2}\leq\frac{\eta^{2}}{K}\left(\sum_{k\in K_{g}}\left\|\sum_ {t=0}^{T-1}\widehat{\nabla}f_{k}(w^{r,t})\right\|^{2}+\sum_{k\in K_{b}}\left\| \widehat{\nabla}f_{k}(w^{r})\right\|^{2}\right)$ $$

We take the expectation:

$$ $\mathbb{E}_{\overline{z}}\|w^{r+1}-w^{r}\|^{2}\leq\frac{\eta^{2}}{K}\left(\sum _{k\in K_{g}}\mathbb{E}_{\overline{z}}\left\|\sum_{t=0}^{T-1}\widehat{\nabla}f _{k}(w^{r,t})\right\|^{2}+\sum_{k\in K_{b}}\mathbb{E}_{\overline{z}}\left\| \widehat{\nabla}f_{k}(w^{r})\right\|^{2}\right)$ $$

For $k\in K_{b}$:

$$ $\mathbb{E}_{\overline{z}}\left\|\widehat{\nabla}f_{k}(w^{r})\right\|^{2}=(2+u) c\left\|\nabla f_{k}(w^{r})\right\|^{2}$ $$

For $k\in K_{g}$:

$$ $\mathbb{E}_{\overline{z}}\left\|\sum_{t=0}^{T-1}\widehat{\nabla}f_{k}(w^{r,t}) \right\|^{2}$ $$

Using the Cauchy-Schwarz inequality:

$$ $\mathbb{E}_{\overline{z}}\left\|\sum_{t=0}^{T-1}\widehat{\nabla}f_{k}(w^{r,t}) \right\|^{2}\leq T\sum_{t=0}^{T-1}\mathbb{E}_{\overline{z}}\left\|\widehat{ \nabla}f_{k}(w^{r,t})\right\|^{2}$ $$

According to the lemma [B.7](https://arxiv.org/html/2506.03337v1#A2.Thmtheorem7):

$$ $\mathbb{E}_{\overline{z}}\left\|\widehat{\nabla}f_{k}(w^{r,t})\right\|^{2}=(2+ u)c\left\|\nabla f_{k}(w^{r,t})\right\|^{2}$ $$

So:

$$ $\mathbb{E}_{\overline{z}}\left\|\sum_{t=0}^{T-1}\widehat{\nabla}f_{k}(w^{r,t}) \right\|^{2}\leq T(2+u)c\sum_{t=0}^{T-1}\left\|\nabla f_{k}(w^{r,t})\right\|^{2}$ $$

Combine the terms we get:

$$ $\mathbb{E}_{\overline{z}}\|w^{r+1}-w^{r}\|^{2}\leq\frac{\eta^{2}(2+u)c}{K} \left(T\sum_{k\in K_{g}}\sum_{t=0}^{T-1}\left\|\nabla f_{k}(w^{r,t})\right\|^{ 2}+\sum_{k\in K_{b}}\left\|\nabla f_{k}(w^{r})\right\|^{2}\right)$ $$

We substitute this inequality to the equation [21](https://arxiv.org/html/2506.03337v1#A2.E21).

$$ $\displaystyle\mathbb{E}_{\overline{z}}[f(w^{r+1})]$ $\displaystyle\leq\mathbb{E}_{\overline{z}}[f(w^{r})]-\frac{\eta\sqrt{c}\alpha} {K}(1+\sqrt{c_{h}})\left\|\nabla f(w^{r})\right\|^{2}$ (22) $\displaystyle\quad-\frac{\eta\sqrt{c}\alpha}{K}\sigma_{h}\left\|\nabla f(w^{r} )\right\|$ $\displaystyle\quad+\frac{\eta^{2}(2+u)cL}{2K}\left(T\sum_{k\in K_{g}}\sum_{t=0 }^{T-1}\left\|\nabla f_{k}(w^{r,t})\right\|^{2}+\sum_{k\in K_{b}}\left\|\nabla f _{k}(w^{r})\right\|^{2}\right)$ $$

$$ $\displaystyle\mathbb{E}_{\overline{z}}\bigl{[}f(w^{r+1})\bigr{]}$ $\displaystyle\leq\mathbb{E}_{\overline{z}}\bigl{[}f(w^{r})\bigr{]}-\frac{\eta \sqrt{c}\,\alpha}{K}\,(1+\sqrt{c_{h}})\,\bigl{\|}\nabla f(w^{r})\bigr{\|}^{2}- \frac{\eta\sqrt{c}\,\alpha}{K}\,\sigma_{h}\bigl{\|}\nabla f(w^{r})\bigr{\|}$ $\displaystyle\quad+\frac{\eta^{2}(2+u)\,c\,L\,T}{2K}\sum_{k\in K_{g}}\sum_{t=0 }^{T-1}\bigl{\|}\nabla f_{k}(w^{r,t})\bigr{\|}^{2}+\frac{\eta^{2}(2+u)\,c\,L}{ 2K}\sum_{k\in K_{b}}\bigl{\|}\nabla f_{k}(w^{r})\bigr{\|}^{2}$ $$

According to the equation [7](https://arxiv.org/html/2506.03337v1#A2.E7), we know that the client-average squared gradient has upper bound.

$$ $\displaystyle\mathbb{E}_{\overline{z}}\bigl{[}f(w^{r+1})\bigr{]}$ $\displaystyle\leq\mathbb{E}_{\overline{z}}\bigl{[}f(w^{r})\bigr{]}-\frac{\eta \sqrt{c}\,\alpha}{K}\,(1+\sqrt{c_{h}})\,\bigl{\|}\nabla f(w^{r})\bigr{\|}^{2}- \frac{\eta\sqrt{c}\,\alpha}{K}\,\sigma_{h}\,\bigl{\|}\nabla f(w^{r})\bigr{\|}$ (23) $\displaystyle\quad+\frac{\eta^{2}(2+u)\,c\,L\,T}{2K}\sum_{k\in K_{g}}\Bigl{[} \frac{2L(2+u)}{c}\bigl{(}f_{k}(w_{k}^{0,r})-f_{k}^{*}\bigr{)}+T\,\sigma^{2} \Bigr{]}$ $\displaystyle\quad+\frac{\eta^{2}(2+u)\,c\,L}{2K}\sum_{k\in K_{b}}\bigl{\|} \nabla f_{k}(w^{r})\bigr{\|}^{2}.$ $$

Using Assumption [B.3](https://arxiv.org/html/2506.03337v1#A2.Thmtheorem3), which states that for any $\theta\in\mathbb{R}^{d}$,

$$ $\left\|\nabla f(\theta)-\nabla f_{i}(\theta)\right\|^{2}\leq c_{h}\left\| \nabla f(\theta)\right\|^{2}+\sigma_{h}^{2},$ $$

we can bound the squared norm of the local gradient $\left\|\nabla f_{k}(w^{r})\right\|^{2}$. Specifically, by the inequality $(x+y)^{2}\leq 2x^{2}+2y^{2}$, we have:

$$ $\left\|\nabla f_{k}(w^{r})\right\|^{2}=\left\|\nabla f(w^{r})+(\nabla f_{k}(w^ {r})-\nabla f(w^{r}))\right\|^{2}\leq 2\left\|\nabla f(w^{r})\right\|^{2}+2 \left\|\nabla f_{k}(w^{r})-\nabla f(w^{r})\right\|^{2}.$ $$

Then, applying Assumption [B.3](https://arxiv.org/html/2506.03337v1#A2.Thmtheorem3) with $\theta=w^{r}$ and $i=k$:

$$ $\left\|\nabla f_{k}(w^{r})-\nabla f(w^{r})\right\|^{2}\leq c_{h}\left\|\nabla f (w^{r})\right\|^{2}+\sigma_{h}^{2}.$ $$

Therefore,

$$ $\left\|\nabla f_{k}(w^{r})\right\|^{2}\leq 2\left\|\nabla f(w^{r})\right\|^{2} +2\left(c_{h}\left\|\nabla f(w^{r})\right\|^{2}+\sigma_{h}^{2}\right)=(2+2c_{h })\left\|\nabla f(w^{r})\right\|^{2}+2\sigma_{h}^{2}.$ $$

Thus, we obtain the bound:

$$ $\left\|\nabla f_{k}(w^{r})\right\|^{2}\leq(2+2c_{h})\left\|\nabla f(w^{r}) \right\|^{2}+2\sigma_{h}^{2}.$ $$

We substitute the bound to the inequality [23](https://arxiv.org/html/2506.03337v1#A2.E23), according to the Assumption [B.3](https://arxiv.org/html/2506.03337v1#A2.Thmtheorem3), we substitute the last term:

$$ $\displaystyle\mathbb{E}_{\overline{z}}\bigl{[}f(w^{r+1})\bigr{]}$ $\displaystyle\leq\mathbb{E}_{\overline{z}}\bigl{[}f(w^{r})\bigr{]}-\frac{\eta \sqrt{c}\,\alpha}{K}\,(1+\sqrt{c_{h}})\,\|\nabla f(w^{r})\|^{2}-\frac{\eta \sqrt{c}\,\alpha}{K}\,\sigma_{h}\,\|\nabla f(w^{r})\|$ $\displaystyle\quad+\frac{\eta^{2}(2+u)\,c\,L\,T}{2K}\sum_{k\in K_{g}}\Bigl{[} \frac{2L(2+u)}{c}\bigl{(}f_{k}(w_{k}^{0,r})-f_{k}^{*}\bigr{)}+T\,\sigma^{2} \Bigr{]}$ $\displaystyle\quad+\frac{\eta^{2}(2+u)\,c\,L}{2K}\sum_{k\in K_{b}}\Bigl{[}(2+2 c_{h})\,\|\nabla f(w^{r})\|^{2}+\sigma_{h}^{2}\Bigr{]}.$ $$

$$ $\displaystyle\mathbb{E}_{\overline{z}}\bigl{[}f(w^{r+1})\bigr{]}$ $\displaystyle\leq\mathbb{E}_{\overline{z}}\bigl{[}f(w^{r})\bigr{]}-\frac{\eta \sqrt{c}\,\alpha}{K}\,(1+\sqrt{c_{h}})\,\|\nabla f(w^{r})\|^{2}-\frac{\eta \sqrt{c}\,\alpha}{K}\,\sigma_{h}\,\|\nabla f(w^{r})\|$ $\displaystyle\quad+\frac{\eta^{2}(2+u)\,c\,L\,T}{2K}\sum_{k\in K_{g}}\Bigl{[} \frac{2L(2+u)}{c}\bigl{(}f_{k}(w_{k}^{0,r})-f_{k}^{*}\bigr{)}+T\,\sigma^{2} \Bigr{]}$ $\displaystyle\quad+\frac{\eta^{2}(2+u)\,c\,L\,|K_{b}|\,(1+c_{h})}{K}\,\|\nabla f (w^{r})\|^{2}+\frac{\eta^{2}(2+u)\,c\,L\,|K_{b}|\,\sigma_{h}^{2}}{K}.$ $$

$$ $\displaystyle\mathbb{E}_{\overline{z}}\bigl{[}f(w^{r+1})\bigr{]}$ $\displaystyle\leq\mathbb{E}_{\overline{z}}\bigl{[}f(w^{r})\bigr{]}$ (24) $\displaystyle\quad+\frac{\eta^{2}(2+u)\,c\,L\,K_{b}\,(1+c_{h})-\;\eta\sqrt{c} \,\alpha}{K}\,\bigl{\|}\nabla f(w^{r})\bigr{\|}^{2}$ $\displaystyle\quad-\frac{\eta\sqrt{c}\,\alpha\,\sigma_{h}}{K}\,\bigl{\|}\nabla f (w^{r})\bigr{\|}$ $\displaystyle\quad+\frac{\eta^{2}(2+u)^{2}\,L^{2}T}{K}\sum_{k\in K_{g}}\!\bigl {(}f_{k}(w_{k}^{0,r})-f_{k}^{*}\bigr{)}$ $\displaystyle\quad+\frac{\eta^{2}(2+u)\,c\,L}{2K}\Bigl{(}T^{2}\,\sigma^{2}\,K_ {g}+2\,K_{b}\sigma_{h}^{2}\Bigr{)}.$ $$

Accumulating Over $R$ Rounds.
Summing equation [24](https://arxiv.org/html/2506.03337v1#A2.E24) over $r=0$ to $R-1$,

$$ $\displaystyle\mathbb{E}_{\overline{z}}\bigl{[}f(w^{R})\bigr{]}-\mathbb{E}_{ \overline{z}}\bigl{[}f(w^{0})\bigr{]}$ $\displaystyle\leq\frac{\eta^{2}(2+u)\,c\,L\,K_{b}\,(1+c_{h})-\eta\sqrt{c}\, \alpha}{K}\sum_{r=0}^{R-1}\bigl{\|}\nabla f(w^{r})\bigr{\|}^{2}$ (25) $\displaystyle\quad-\frac{\eta\sqrt{c}\,\alpha\,\sigma_{h}}{K}\sum_{r=0}^{R-1} \bigl{\|}\nabla f(w^{r})\bigr{\|}$ $\displaystyle\quad+\frac{\eta^{2}(2+u)^{2}\,L^{2}\,T}{K}\sum_{r=0}^{R-1}\sum_{ k\in K_{g}}\bigl{(}f_{k}(w_{k}^{0,r})-f_{k}^{*}\bigr{)}$ $\displaystyle\quad+\frac{\eta^{2}(2+u)\,c\,L\,R}{2K}\Bigl{(}T^{2}\,\sigma^{2} \,K_{g}+2\,K_{b}\,\sigma^{2}\Bigr{)}.$ $$

According to our previous derivation, we know that:

$$ $\sum_{r=0}^{R-1}\bigl{\|}\nabla f(w^{r})\bigr{\|}\;\leq\;\sqrt{R}\,\sqrt{\sum_ {r=0}^{R-1}\bigl{\|}\nabla f(w^{r})\bigr{\|}^{2}}\,.$ (26) $$

Apply Young’s inequality with $\delta>0$ and nonnegative real numbers $x$ and $y$,

$$ $xy\leq\frac{x^{2}}{2\delta}+\frac{y^{2}\delta}{2}.$ $$

$$ $\displaystyle\frac{\eta\sqrt{c}\,\sigma_{h}\alpha}{K}\sum_{r=0}^{R}\|\nabla f( w^{r})\|$ $\displaystyle\leq\frac{\eta\sqrt{c}\,\alpha\sigma_{h}\sqrt{R}}{K}\sqrt{\sum_{r =0}^{R}\|\nabla f(w^{r})\|^{2}}$ $\displaystyle\leq\frac{1}{2\delta}\sum_{r=0}^{R}\|\nabla f(w^{r})\|^{2}\;+\; \frac{\eta^{2}\,c\,\alpha^{2}\sigma_{h}^{2}\,R\,\delta}{2\,K^{2}}$ $\displaystyle-\frac{\eta\sqrt{c}\,\sigma_{h}\alpha}{K}\sum_{r=0}^{R}\|\nabla f (w^{r})\|$ $\displaystyle\leq\frac{1}{2\delta}\sum_{r=0}^{R}\|\nabla f(w^{r})\|^{2}\;+\; \frac{\eta^{2}\,c\,\alpha^{2}\sigma_{h}^{2}\,R\,\delta}{2\,K^{2}}.$ $$

We substitute this to the equation [25](https://arxiv.org/html/2506.03337v1#A2.E25).

$$ $\displaystyle\mathbb{E}_{\overline{z}}\bigl{[}f(w^{R})\bigr{]}\;-\;\mathbb{E}_ {\overline{z}}\bigl{[}f(w^{0})\bigr{]}$ $\displaystyle\leq\Biggl{(}\frac{\eta^{2}(2+u)\,c\,L\,K_{b}\,(1+c_{h})\;-\;\eta \sqrt{c}\,\alpha}{K}\;+\;\frac{1}{2\delta}\Biggr{)}\sum_{r=0}^{R-1}\|\nabla f( w^{r})\|^{2}$ (27) $\displaystyle\quad+\frac{\eta^{2}\,c\,\alpha^{2}\sigma_{h}^{2}\,R\,\delta}{2\, K^{2}}+\frac{\eta^{2}(2+u)^{2}\,L^{2}\,T}{K}\sum_{r=0}^{R}\sum_{k\in K_{g}} \bigl{(}f_{k}(w_{k}^{0,r})-f_{k}^{*}\bigr{)}$ $\displaystyle\quad+\frac{\eta^{2}(2+u)\,c\,L\,R}{2\,K}\Bigl{(}T^{2}\,\sigma^{2 }\,K_{g}+2\,K_{b}\,\sigma_{h}^{2}\Bigr{)}.$ $$

Given that $w_{k}^{0,r}=w^{r}$, this term is equivalent to $\sum_{r=0}^{R}\sum_{k\in K_{g}}\bigl{(}f_{k}(w^{r})-f_{k}^{*}\bigr{)}$.

From our previous discussion, we have the inequality for a single round $r$:

$$ $\sum_{k\in K_{g}}\bigl{(}f_{k}(w^{r})-f_{k}^{*}\bigr{)}\leq\sum_{k=1}^{K}\bigl {(}f_{k}(w^{r})-f_{k}^{*}\bigr{)}$ $$

and the inequality used in Part 2 of the proof:

$$ $\sum_{r=0}^{R-1}\sum_{k=1}^{K}\left(f_{k}(w^{r})-f_{k}^{*}\right)\leq\sum_{r=0 }^{R-1}\left(Kf(w^{r})-Kf^{*}+\frac{L}{2}\sum_{k=1}^{K}\Delta_{k}\right).$ $$

Combining these two inequalities, we obtain a bound for the sum over the set $K_{g}$:

We set $\gamma\leq 1$ which means that the subset clients the effect to the global:

$$ $\sum_{r=0}^{R-1}\sum_{k\in K_{g}}\bigl{(}f_{k}(w^{r})-f_{k}^{*}\bigr{)}\;\leq \;\gamma\,\sum_{r=0}^{R-1}\!\Bigl{(}K\,\bigl{(}f(w^{r})-f^{*}\bigr{)}+\frac{L} {2}\sum_{k=1}^{K}\!\Delta_{k}\Bigr{)}$ $$

We substitute this to the above inequality get:

$$ $\displaystyle\mathbb{E}_{\overline{z}}\bigl{[}f(w^{R})\bigr{]}-\mathbb{E}_{ \overline{z}}\bigl{[}f(w^{0})\bigr{]}$ $\displaystyle\leq\left(\frac{\eta^{2}(2+u)\,c\,L\,K_{b}\,(1+c_{h})}{K}-\frac{ \eta\sqrt{c}\,\alpha}{K}+\frac{1}{2\delta}\right)\sum_{r=0}^{R-1}\|\nabla f(w^ {r})\|^{2}$ $\displaystyle\quad+\frac{\eta^{2}\,c\,\alpha^{2}\,\sigma_{h}^{2}\,R\,\delta}{2 \,K^{2}}+\eta^{2}(2+u)^{2}\,L^{2}\,T\,\gamma\sum_{r=0}^{R-1}\bigl{(}f(w^{r})-f ^{*}\bigr{)}$ $\displaystyle\quad+\frac{\eta^{2}(2+u)^{2}\,L^{3}\,T\,R\,\gamma}{2\,K}\sum_{k= 1}^{K}\Delta_{k}$ $\displaystyle\quad+\frac{\eta^{2}(2+u)\,c\,L\,R}{2\,K}\Bigl{(}T^{2}\,\sigma^{2 }\,K_{g}+2\,K_{b}\,\sigma_{h}^{2}\Bigr{)}.$ $$

We substitute $\alpha$:

$$ $\displaystyle\mathbb{E}_{\overline{z}}\bigl{[}f(w^{R})\bigr{]}-\mathbb{E}_{ \overline{z}}\bigl{[}f(w^{0})\bigr{]}$ $\displaystyle\leq\left(\frac{\eta^{2}(2+u)cLK_{b}(1+c_{h})}{K}-\frac{\eta\sqrt {c}(K_{g}T+K_{b})}{K}+\frac{1}{2\delta}\right)\sum_{r=0}^{R-1}\|\nabla f(w^{r} )\|^{2}$ $\displaystyle\quad+\frac{\eta^{2}c(K_{g}^{2}T^{2}+2K_{g}TK_{b}+K_{b}^{2}) \sigma_{h}^{2}R\delta}{2K^{2}}+\eta^{2}(2+u)^{2}L^{2}T\gamma\sum_{r=0}^{R-1}(f (w^{r})-f^{*})$ $\displaystyle\quad+\frac{\eta^{2}(2+u)^{2}L^{3}TR\gamma}{2K}\sum_{k=1}^{K} \Delta_{k}+\frac{\eta^{2}(2+u)cLR}{2K}\left(T^{2}\sigma^{2}K_{g}+2K_{b}\sigma_ {h}^{2}\right).$ $$

To simplify the inequality, we solve for $\delta$:

$$ $\frac{1}{2\delta}=-\frac{\eta\sqrt{c}(K_{g}T+K_{b})}{2K}-\frac{\eta^{2}(2+u) cLK_{b}(1+c_{h})}{K}+\frac{\eta\sqrt{c}(K_{g}T+K_{b})}{K},$ $$

$$ $\frac{1}{2\delta}=\frac{\eta\sqrt{c}(K_{g}T+K_{b})}{2K}-\frac{\eta^{2}(2+u)cLK _{b}(1+c_{h})}{K},$ $$

$$ $\delta=\frac{K}{\eta\sqrt{c}(K_{g}T+K_{b})-2\eta^{2}(2+u)cLK_{b}(1+c_{h})}.$ $$

For $\delta>0$, the denominator must be positive:

$$ $\eta\sqrt{c}(K_{g}T+K_{b})-2\eta^{2}(2+u)cLK_{b}(1+c_{h})>0,$ $$

yielding the condition:

$$ $\eta<\frac{\sqrt{c}(K_{g}T+K_{b})}{2(2+u)cLK_{b}(1+c_{h})}.$ $$

Substitute $\delta$:

$$ $\displaystyle\mathbb{E}_{\overline{z}}\bigl{[}f(w^{R})\bigr{]}-\mathbb{E}_{ \overline{z}}\bigl{[}f(w^{0})\bigr{]}$ $\displaystyle\leq-\frac{\eta\sqrt{c}(K_{g}T+K_{b})}{2K}\sum_{r=0}^{R-1}\| \nabla f(w^{r})\|^{2}$ $\displaystyle\quad+\frac{\eta^{2}c(K_{g}T+K_{b})^{2}\sigma_{h}^{2}R}{2K\left( \eta\sqrt{c}(K_{g}T+K_{b})-2\eta^{2}(2+u)cLK_{b}(1+c_{h})\right)}$ $\displaystyle\quad+\eta^{2}(2+u)^{2}L^{2}T\gamma\sum_{r=0}^{R-1}(f(w^{r})-f^{*})$ $\displaystyle\quad+\frac{\eta^{2}(2+u)^{2}L^{3}TR\gamma}{2K}\sum_{k=1}^{K} \Delta_{k}$ $\displaystyle\quad+\frac{\eta^{2}(2+u)cLR}{2K}\left(T^{2}\sigma^{2}K_{g}+2K_{b }\sigma_{h}^{2}\right).$ $$

According to the Assumption [B.2](https://arxiv.org/html/2506.03337v1#A2.Thmtheorem2) we have:

$$ $2\mu(f(\mathbf{w}^{r})-f^{*})\leq\|\nabla f(\mathbf{w}^{r})\|^{2},\quad\forall \mathbf{w}^{r}\in\mathbb{R}^{d},$ $$

$$ $2\mu\sum_{r=0}^{R-1}(f(\mathbf{w}^{r})-f^{*})\leq\sum_{r=0}^{R-1}\|\nabla f( \mathbf{w}^{r})\|^{2},\quad\forall\mathbf{w}^{r}\in\mathbb{R}^{d},$ $$

Combine the PL inequality to the above function we get:

$$ $\displaystyle\frac{\eta\sqrt{c}(K_{g}T+K_{b})}{2K}\sum_{r=0}^{R-1}\|\nabla f(w ^{r})\|^{2}$ $\displaystyle\leq\mathbb{E}_{\overline{z}}\bigl{[}f(w^{0})\bigr{]}-\mathbb{E}_ {\overline{z}}\bigl{[}f(w^{R})\bigr{]}$ $\displaystyle\quad+\frac{\eta^{2}c(K_{g}T+K_{b})^{2}\sigma_{h}^{2}R}{2K\left( \eta\sqrt{c}(K_{g}T+K_{b})-2\eta^{2}(2+u)cLK_{b}(1+c_{h})\right)}$ $\displaystyle\quad+\eta^{2}(2+u)^{2}L^{2}T\gamma\sum_{r=0}^{R-1}(f(w^{r})-f^{*})$ $\displaystyle\quad+\frac{\eta^{2}(2+u)^{2}L^{3}TR\gamma}{2K}\sum_{k=1}^{K} \Delta_{k}$ $\displaystyle\quad+\frac{\eta^{2}(2+u)cLR}{2K}\left(T^{2}\sigma^{2}K_{g}+2K_{b }\sigma_{h}^{2}\right).$ $$

Let $S_{E}=\sum_{r=0}^{R-1}\mathbb{E}[f(w^{r})-f^{*}]$, $D_{\delta}=\eta\sqrt{c}(K_{g}T+K_{b})-2\eta^{2}(2+u)cLK_{b}(1+c_{h})$. We require $D_{\delta}>0$.

Substituting this back into the original inequality:

$$ $\displaystyle\mathbb{E}[f(w^{R})]-\mathbb{E}[f(w^{0})]$ $\displaystyle\leq-\frac{\eta\mu\sqrt{c}(K_{g}T+K_{b})}{K}S_{E}+\eta^{2}(2+u)^{ 2}L^{2}T\gamma S_{E}$ $\displaystyle\quad+\frac{\eta^{2}c(K_{g}T+K_{b})^{2}\sigma_{h}^{2}R}{2KD_{ \delta}}$ $\displaystyle\quad+\frac{\eta^{2}(2+u)^{2}L^{3}TR\gamma}{2K}\sum_{k=1}^{K} \Delta_{k}$ $\displaystyle\quad+\frac{\eta^{2}(2+u)cLR}{2K}\left(T^{2}\sigma^{2}K_{g}+2K_{b }\sigma_{h}^{2}\right).$ $$

Collecting terms involving $S_{E}$:

$$ $\mathbb{E}[f(w^{R})]-\mathbb{E}[f(w^{0})]\leq\left(\eta^{2}(2+u)^{2}L^{2}T \gamma-\frac{\eta\mu\sqrt{c}(K_{g}T+K_{b})}{K}\right)S_{E}+\text{other terms}.$ $$

Moving $S_{E}$ to the left side:

$$ $\displaystyle\Bigl{(}\frac{\eta\mu\sqrt{c}\,(K_{g}T+K_{b})}{K}-\;\eta^{2}(2+u) ^{2}L^{2}T\gamma\Bigr{)}\,S_{E}$ $\displaystyle\leq\mathbb{E}[f(w^{0})]-\mathbb{E}[f(w^{R})]$ $\displaystyle\quad+\,\frac{\eta^{2}c\,(K_{g}T+K_{b})^{2}\sigma_{h}^{2}\,R}{2K \,D_{\delta}}+\frac{\eta^{2}(2+u)^{2}L^{3}T\,R\gamma}{2K}\sum_{k=1}^{K}\Delta_ {k}$ $\displaystyle\quad+\,\frac{\eta^{2}(2+u)cL\,R}{2K}\bigl{(}T^{2}\sigma^{2}K_{g} +2K_{b}\sigma_{h}^{2}\bigr{)}.$ (28) $$

Since $\mathbb{E}[f(w^{R})]\geq f^{*}$ (typically $f^{*}$ is the minimum), we have $\mathbb{E}[f(w^{0})]-\mathbb{E}[f(w^{R})]\leq\mathbb{E}[f(w^{0})-f^{*}]$. Let $f_{0}^{*}=\mathbb{E}[f(w^{0})-f^{*}]$ (the initial expected suboptimality). Let the coefficient of $S_{E}$ be $C^{\prime}_{S}=\frac{\eta\mu\sqrt{c}(K_{g}T+K_{b})}{K}-\eta^{2}(2+u)^{2}L^{2}T\gamma$. To ensure $C^{\prime}_{S}>0$, we need $\eta$ sufficiently small such that $\eta<\frac{\mu\sqrt{c}(K_{g}T+K_{b})}{K(2+u)^{2}L^{2}T\gamma}$. Then:

$$ $\displaystyle C^{\prime}_{S}S_{E}$ $\displaystyle\leq f_{0}^{*}+\frac{\eta^{2}c(K_{g}T+K_{b})^{2}\,\sigma_{h}^{2} \,R}{2\,K\,D_{\delta}}+\frac{\eta^{2}(2+u)^{2}\,L^{3}\,T\,R\,\gamma}{2\,K}\sum _{k=1}^{K}\Delta_{k}$ $\displaystyle\quad+\frac{\eta^{2}(2+u)\,c\,L\,R}{2\,K}\Bigl{(}T^{2}\,\sigma^{2 }\,K_{g}+2\,K_{b}\,\sigma_{h}^{2}\Bigr{)}.$ $$

Our goal is $\frac{1}{R}S_{E}=\frac{1}{R}\sum_{r=0}^{R-1}\mathbb{E}[f(w^{r})-f^{*}]$. Dividing both sides by $R$:

$$ $\displaystyle C^{\prime}_{S}\,\frac{1}{R}\sum_{r=0}^{R-1}\mathbb{E}[f(w^{r})-f ^{*}]$ $\displaystyle\leq\frac{f_{0}^{*}}{R}+\frac{\eta^{2}\,c\,(K_{g}T+K_{b})^{2}\, \sigma_{h}^{2}}{2K\,D_{\delta}}$ $\displaystyle\quad+\frac{\eta^{2}\,(2+u)^{2}\,L^{3}\,T\,\gamma}{2K}\sum_{k=1}^ {K}\Delta_{k}$ $\displaystyle\quad+\frac{\eta^{2}\,(2+u)\,c\,L}{2K}\bigl{(}T^{2}\sigma^{2}K_{g }+2K_{b}\sigma_{h}^{2}\bigr{)}.$ $$

Finally, dividing both sides by $C^{\prime}_{S}$ (assuming $C^{\prime}_{S}>0$):

$$ $\displaystyle\frac{1}{R}\sum_{r=0}^{R-1}\mathbb{E}_{\overline{z}}[f(w^{r})-f^{ *}]$ $\displaystyle\leq\frac{1}{C^{\prime}_{S}}\left[\frac{f_{0}^{*}}{R}+\frac{\eta^ {2}c(K_{g}T+K_{b})^{2}\sigma_{h}^{2}}{2K\left(\eta\sqrt{c}(K_{g}T+K_{b})-2\eta ^{2}(2+u)cLK_{b}(1+c_{h})\right)}\right.$ $\displaystyle\quad\left.+\frac{\eta^{2}(2+u)^{2}L^{3}T\gamma}{2K}\sum_{k=1}^{K }\Delta_{k}+\frac{\eta^{2}(2+u)cL}{2K}\left(T^{2}\sigma^{2}K_{g}+2K_{b}\sigma_ {h}^{2}\right)\right],$ $$

where

$$ $C^{\prime}_{S}\;=\;\frac{\eta\,\mu\sqrt{c}\,(K_{g}T+K_{b})}{K}\;-\;\eta^{2}(2+ u)^{2}L^{2}T\,\gamma,\qquad D_{\delta}\;=\;\eta\sqrt{c}\,(K_{g}T+K_{b})-2\eta^ {2}(2+u)cL\,K_{b}(1+c_{h}).$ $$

To ensure both $C^{\prime}_{S}>0$ and $D_{\delta}>0$, we require

$$ $\eta<\underbrace{\frac{\sqrt{c}(K_{g}T+K_{b})}{2(2+u)cL\,K_{b}(1+c_{h})}}_{= \overline{\eta}_{\delta}},\qquad\eta<\underbrace{\frac{\mu\sqrt{c}(K_{g}T+K_{b })}{K(2+u)^{2}L^{2}T\,\gamma}}_{=\overline{\eta}_{S}}.$ $$

Let

$$ $\eta_{\max}=\min\{\overline{\eta}_{\delta},\;\overline{\eta}_{S}\},\qquad \theta\in\bigl{(}0,\tfrac{1}{2}\bigr{]}.$ $$

Choosing $\theta=\tfrac{1}{2}$ gives

$$ $\eta=\tfrac{1}{2}\,\eta_{\max}=\frac{\mu\sqrt{c}\,(K_{g}T+K_{b})}{2\,K\,(2+u)^ {2}L^{2}T\,\gamma}.$ $$

We select

$$ $\eta=\frac{\mu\sqrt{c}(K_{g}T+K_{b})}{2K(2+u)^{2}L^{2}T\gamma}$ $$

And from previous client convergence conclusion, we pick a constant local learning rate

$$ $\eta_{\rm client}=\frac{c}{\alpha}=\frac{1}{L\,(u+2)}<\frac{2c}{\alpha}$ $$

Substituting the learning rate $\eta=\min\!\Biggl{\{}\frac{1}{L\,(u+2)},\;\frac{\mu\,\sqrt{c}\,\bigl{(}K_{g}\,
T+K_{b}\bigr{)}}{2\,K\,(2+u)^{2}\,L^{2}\,T\,\gamma}\Biggr{\}}$, since $\eta$ is a small value, we neglect $\eta^{2}$.

$$ $\displaystyle\frac{1}{R}\sum_{r=0}^{R-1}\mathbb{E}_{\overline{z}}\bigl{[}f(w^{ r})-f^{*}\bigr{]}$ $\displaystyle\leq\frac{4K^{2}(2+u)^{2}L^{2}T\gamma\,\mathbb{E}[f(w^{0})-f^{*}] }{\mu^{2}\,c\,(K_{g}T+K_{b})^{2}\,R}\;+\;\frac{\sigma_{h}^{2}}{2}\;+\;\frac{(2 +u)\,L}{4K}\sum_{k=1}^{K}\Delta_{k}$ $\displaystyle\quad+\;\frac{c}{4K(2+u)L\,T\,\gamma}\Bigl{(}T^{2}\sigma^{2}K_{g} +2K_{b}\sigma_{h}^{2}\Bigr{)}.$ $$

$$ $\displaystyle\frac{1}{R}\sum_{r=0}^{R-1}\mathbb{E}_{\overline{z}}\bigl{[}f(w^{ r})-f^{*}\bigr{]}$ $\displaystyle\leq O\!\biggl{(}\frac{K^{2}\,(2+u)^{2}\,\gamma\,T}{c\,(K_{g}T+K_ {b})^{2}\,R}\biggr{)}$ (29) $\displaystyle\quad+\,O\!\biggl{(}\frac{1+u}{K}(\sum_{k=1}^{K_{g}}\Delta_{kg}+ \sum_{k=1}^{K_{b}}\Delta_{kb})\biggr{)}$ $\displaystyle\quad+\,O\!\biggl{(}\frac{c\,T\,K_{g}}{K(1+u)\,\gamma}\biggr{)}$ $\displaystyle\quad+\,O\!\biggl{(}\frac{c\,K_{b}\,\sigma_{h}^{2}}{K(1+u)\,T\, \gamma}\biggr{)}+O\!\bigl{(}1\bigr{)}.$ $$

∎

Define the error upper-bounds for Meerkat-vp and the baseline Meerkat as follows:

$$ $\displaystyle E_{\mathrm{\textsc{Meerkat-vp}}}$ $\displaystyle=\underbrace{\frac{4K^{2}(2+u)^{2}L^{2}T\,\gamma}{\mu^{2}\,c\,(K_ {g}T+K_{b})^{2}}\,\frac{\mathbb{E}[f(w^{0})-f^{*}]}{R}}_{\text{(I) Transient term}}+\underbrace{\biggl{[}\frac{\sigma_{h}^{2}}{2}+\frac{(2+u)L}{4K}\sum_{k= 1}^{K}\Delta_{k}+\frac{c\bigl{(}T^{2}\sigma^{2}K_{g}+2K_{b}\sigma_{h}^{2}\bigr {)}}{4K(2+u)L\,T\,\gamma}\biggr{]}}_{\text{(II) Steady-state term}},$ $\displaystyle E_{\mathrm{\textsc{Meerkat}}}$ $\displaystyle=\underbrace{\frac{4L^{2}(2+u)^{2}}{\mu^{2}\,c\,(1+\sqrt{c_{h}})^ {2}\,T}\,\frac{\mathbb{E}[f(w^{0})-f^{*}]}{R}}_{\text{(I') Transient term}}+ \underbrace{\biggl{[}\frac{\sigma_{h}^{2}}{\mu\,(1+\sqrt{c_{h}})^{2}}+\frac{L} {K}\sum_{k=1}^{K}\Delta_{k}+\frac{T\,c\,\sigma^{2}}{2L\,(2+u)}\biggr{]}}_{ \text{(II') Steady-state term}}.$ $$

- •
Transient term ratio:
$\frac{(I)}{(I^{\prime})}\;\approx\;\gamma\,(1+\sqrt{c_{h}})^{2}\;<\;1,\quad
\text{and as }c_{h}\to 1,\;\gamma(1+\sqrt{c_{h}})^{2}\to 0.$
- •
Noise term ratio:
$\frac{\sigma_{h}^{2}/2}{\sigma_{h}^{2}/(\mu\,(1+\sqrt{c_{h}})^{2})}=\frac{\mu
\,(1+\sqrt{c_{h}})^{2}}{2},\quad\text{which is }<1\text{ when }\mu\,(1+\sqrt{c
_{h}})^{2}<2.$
Empirically $\mu<1$, thus $\mu\,(1+\sqrt{c_{h}})^{2}<2$ is True. Additionally, VPCS includes an extra term $\frac{cK_{b}\sigma_{h}^{2}}{2K(2+u)LT\gamma}$, which decays as $\frac{1}{T}$ and becomes negligible for large $T$.
- •
Heterogeneity and variance terms:
$\frac{(2+u)L}{4K}\sum_{k=1}^{K}\Delta_{k}\;<\;\frac{L}{K}\sum_{k=1}^{K}\Delta_
{k},\quad\text{and the extra variance term decays as }1/K.$

Therefore, under the same $T$ and $R$, $E_{\mathrm{\textsc{Meerkat-vp}}}<E_{\mathrm{\textsc{Meerkat}}}$ and this gap widens as data heterogeneity $c_{h}$ increases.

### Remarks

The analysis of the upper bound in Equation [17](https://arxiv.org/html/2506.03337v1#A2.E17) reveals how the local training step $T$, density level $u$, and communication rounds $R$ collectively influence the optimization dynamics through a balance of convergence rate, bias–variance trade-offs, and steady-state error control:

- •
Impact of Local Update Steps $T$:
A smaller $T$ amplifies the term $\mathcal{O}\left(\frac{(2+u)^{2}}{TR}\cdot\mathbb{E}[f(w^{0})-f(w^{R})]\right)$, increasing the average optimality gap after $R$ communication rounds when $R$ is fixed. However, this effect can be mitigated by increasing $R$, as the scaling factor $\frac{1}{R}$ reduces the term’s impact. Conversely, reducing $T$ diminishes the variance term $\mathcal{O}\left(\frac{T}{2+u}\right)$, leading to a smaller steady-state error. Thus, a smaller $T$ may prolong the transient phase but ultimately achieves a tighter optimality gap relative to $f^{*}$ after sufficient rounds.
- •
Density Level $u$.
Reducing $u$ (i.e., increasing sparsity) quadratically benefits the transient term, yet it also inflates the steady-state term through the denominator $2+u$. Choosing $u$ therefore amounts to balancing communication savings against the plateau error; aggressive sparsification should be coupled with smaller $T$ to avoid performance degradation.
- •
Meerkat-vp Client Selection Strategy:
By early-stopping extreme data-imbalance clients with a single local training step, Meerkat-vp effectively reduces Non-IID drift in zeroth-order federated llm fine-tuning. This strategy
lowers the coefficient of the transient term and further reduces heterogeneity- and
variance-induced steady-state error. Under fixed $T$ and $R$, these effects yield
strictly faster convergence and a tighter optimality gap in Non-IID settings.

These conclusions illustrate how tuning $T$, $R$, $u$, and the Meerkat-vp client selection
strategy can optimize performance in federated, sparse, and Non-IID learning scenarios.

### B.6 Empirical analysis of the GradIP Phenomenon

By Lemma [B.8](https://arxiv.org/html/2506.03337v1#A2.Thmtheorem8), the masked sparse zeroth-order (ZO) surrogate gradient is an *unbiased* estimator of the masked first-order gradient.
Building on this fact, we define the vector $g_{c}(w;x,y)$ is obtained by computing the gradient of the cross-entropy loss for a single sample with respect to a small subset of parameters selected by a mask.

From logits to Softmax Probabilities we have:

- •
The model’s final layer outputs a logit for each class:
$h(x;w)=\bigl{(}h_{1},\dots,h_{C}\bigr{)}\in\mathbb{R}^{C}.$
- •
The softmax probabilities are given by:
$p_{j}(x;w)=\frac{e^{h_{j}}}{\sum_{r=1}^{C}e^{h_{r}}}.$

The cross-entropy loss for a single sample is:

$$ $\ell(w;x,y)=-\log p_{y}(x;w),\quad\text{where }y\in\{1,\dots,C\}.$ $$

For each logit $h_{j}$, the partial derivative is:

$$ $\frac{\partial\ell}{\partial h_{j}}=p_{j}-\mathbf{1}_{\{y=j\}}=p_{j}-(e_{y})_{ j},$ $$

where $e_{y}$ is the one-hot vector with 1 in the $y$-th component.

Since we are only interested in the sensitive parameters selected by the mask $m$, the gradient with respect to the parameters can be written as:

$$ $\displaystyle g_{c}(w;x,y)$ $\displaystyle=\nabla_{w_{m}}\ell(w;x,y)$ $\displaystyle=\sum_{j=1}^{C}\frac{\partial\ell}{\partial h_{j}}\;\nabla_{w_{m} }h_{j}(x;w)$ $\displaystyle=\Bigl{(}p(x;w)-e_{y}\Bigr{)}^{\!\top}\nabla_{w_{m}}h(x;w).$ $$

Here:

- •
$\nabla_{w_{m}}h_{j}(x;w)$ is the gradient/Jacobian of the logit $h_{j}$ with respect to the masked parameter $w_{m}$.
- •
By collecting the coefficients $p_{j}-\mathbf{1}_{y=j}$ into a vector, we obtain the compact form:
$g_{c}(w;x,y)=(p-e_{y})^{\!\top}\nabla_{w_{m}}h(x;w).$

In our existing local client convergence inequality and from the assumption [B.4](https://arxiv.org/html/2506.03337v1#A2.Thmtheorem4), we can empirically write the key constant estimator variance:

$$ $\sigma_{k}^{2}=\frac{1}{d}\operatorname{Var}_{(x,y)\sim D_{k}}[g_{c}(w;x,y)].$ $$

We write $g_{c}$ in matrix form:
Define:

$$ $\mathbf{J}(x;w)=\nabla_{w_{m}}h(x;w)\in\mathbb{R}^{d_{m}\times C},\quad\mathbf {a}(x,y;w)=p(x;w)-\mathbf{e}_{y}\in\mathbb{R}^{C}.$ $$

Thus:

$$ $g_{c}(w;x,y)=\mathbf{J}^{\!\top}(x;w)\,\mathbf{a}(x,y;w)\in\mathbb{R}^{d_{m}}.$ $$

We substitute this equation to the above estimator variance:

$$ $\sigma_{k}^{2}=\frac{1}{d_{m}}\underbrace{\mathbb{E}_{(x,y)}\bigl{\|}g(w;x,y)- \nabla f_{k}(w)\bigr{\|}^{2}}_{\text{total variance}}=\frac{1}{d_{m}} \operatorname{tr}\left(\mathbf{J}^{\!\top}\,\underbrace{\operatorname{Cov}_{(x ,y)}\bigl{[}\mathbf{a}(x,y;w)\bigr{]}}_{\Sigma_{a}}\,\mathbf{J}\right).$ $$

Note:

- •
$\Sigma_{a}\in\mathbb{R}^{C\times C}$ is determined solely by the label distribution and prediction probabilities.
- •
$\mathbf{J}$ reflects the network structure and influences only a similarity coefficient.

Analysis of Extreme Non-IID (Single Label $y^{\dagger}$):

- •
The label is fixed, so $\mathbf{1}_{y=j}$ is constant.
- •
If the model is mostly correct: $p\approx\mathbf{e}_{y^{\dagger}}$, then $\mathbf{a}(x,y;w)\approx\mathbf{0}$, yielding:
$\Sigma_{a}\approx\mathbf{0}\quad\Longrightarrow\quad\sigma_{\text{non}}^{2}
\approx\frac{1}{d_{m}}\operatorname{tr}(\mathbf{0})=0.$

Analysis of Approximate IID (Balanced Multi-Label)

- •
The label $y$ varies across $\{1,\dots,C\}$.
- •
Even as the loss decreases, $p_{j}$ differs across classes. The covariance is:
$(\Sigma_{a})_{rs}=\mathbb{E}\left[(p_{r}-\mathbf{1}_{y=r})(p_{s}-\mathbf{1}_{y
=s})\right]-\underbrace{\left(\mathbb{E}[p_{r}-\mathbf{1}_{y=r}]\right)}_{=0}
\underbrace{\left(\mathbb{E}[p_{s}-\mathbf{1}_{y=s}]\right)}_{=0}.$
This matrix has diagonal elements $\mathbb{E}\left[(p_{r}-\mathbf{1}_{y=r})^{2}\right]>0$, making $\Sigma_{a}$ positive definite or semi-definite but non-zero. Thus:
$\sigma_{\text{iid}}^{2}=\frac{1}{d_{m}}\operatorname{tr}\left(\mathbf{J}^{\!
\top}\Sigma_{a}\mathbf{J}\right)>0.$

Our local convergence bound is:

$$ $\frac{1}{T}\sum_{t=0}^{T-1}\mathbb{E}\|\nabla f_{k}(w_{k}^{t})\|^{2}\leq O \left(\frac{1}{T}\right)+\sigma_{k}^{2},$ $$

which indicates that in the steady state, the upper bound of the gradient norm is determined by $\sigma_{k}^{2}$. Therefore,

$$ $\sigma_{\text{iid}}^{2}\gg\sigma_{\text{non-iid}}^{2}\approx 0\quad \Longrightarrow\quad\begin{cases}\text{IID clients: Gradient Norm oscillates significantly;}\\ \text{Non-IID clients: Gradient Norm decreases monotonically and approaches 0. }\end{cases}$ $$

### Remarks

In summary, by substituting the explicit form of the cross-entropy gradient into our sparse ZO convergence formula, we can empirically explain that due to the variance differences caused by label distributions, the Gradient Norms of IID clients maintains significant fluctuations, while that of extremely Non-IID clients rapidly decays and converges to zero.

Figure: Algorithm 2 Meerkat: Sparse Zeroth-Order Optimization for Federated LLM Fine-Tuning

Figure: Figure 5: Meerkat-vp: Each client locally trains with a prescribed statistic step, yielding a sequence of projected gradients. The server leverages a randomly sampled vector $z_{k}^{t}$ from the Gaussian distribution $\mathcal{N}(\mathbf{0},\mathbf{I}_{d})$ to reconstruct $\nabla f_{k}^{t}$, and then computes GradIP (see Definition [2.3](https://arxiv.org/html/2506.03337v1#S2.Thmtheorem3)) at every local training step. By analyzing the resulting GradIP values across all clients, the system distinguishes those clients with extremely Non-IID data from those that are relatively balanced. For the parameters later phase steps , initial phase steps, quiescent step ratio, and initial to later ratio, please refer to Table [3](https://arxiv.org/html/2506.03337v1#A3.T3) in Appendix [C.1](https://arxiv.org/html/2506.03337v1#A3.SS1)
Refer to caption: x5.png

Figure: Algorithm 3 Meerkat with high frequency server-client synchronization

## Appendix C More Experimental Details

### C.1 Additional Experimental Settings

Testbed. All experiments are run on servers with the following configurations:
RTX A6000 Setup: Ubuntu 18.04.6 LTS with 2 NVIDIA RTX A6000 GPUs (each with 48GB GPU memory).
GH200 Setup: Ubuntu 20.04 with 1 NVIDIA GH200 GPU (97GB GPU memory).
A100 Setup: Ubuntu 22.04 with 1 NVIDIA A100 GPU (40GB GPU memory).

Dataset.
We conducted experiments using datasets from the GLUE and SuperGLUE benchmarks, including SST2, AgNews, Yelp, BoolQ, RTE, WSC, and WiC. To create IID clients data, we shuffle the entire dataset and evenly divide it among the clients. To create Non-IID clients data, we split the data using a Dirichlet distribution. For all tasks, the Dirichlet $\alpha$ parameter is set to $0.5$ to control the degree of data heterogeneity.

Evaluation metric.
In our experiments, test accuracy is used as the primary evaluation metric. Accuracy is computed as the proportion of correctly predicted labels across all evaluation samples., Additionally, we incorporate the GradIP score (see Definition [2.3](https://arxiv.org/html/2506.03337v1#S2.Thmtheorem3)) to analyze further the dynamics of local model training under IID and Non-IID client data settings. GradIP provides a metric to measure the quality of client training trajectories, particularly in heterogeneous data distributions.

Notations. We present the parameters definition used in Meerkat-vp in Table [3](https://arxiv.org/html/2506.03337v1#A3.T3).

**Table 3: Meerkat-vp Parameters Notation**
| Term | Explanation |
| --- | --- |
| calibration steps $T_{\textsf{cali}}$ | Number of steps each client performs to measure GradIP. |
| initial phase steps $T_{\textsf{init}}$ | Number of earliest local steps used to measure the early-phase GradIP. |
| later phase steps $T_{\textsf{later}}$ | Number of latest local steps used to observe the late-phase GradIP. |
| convergence threshold $\sigma$ | Threshold indicating when GradIP is effectively zero. |
| quiescent step ratio $\rho_{\textsf{quie}}$ | Fraction of later phase where GradIP stays below threshold |
| Initial to later ratio $\rho_{\textsf{later}}$ | Ratio of average GradIP in the initial phase to that in the later phase. |

Hyper-parameters. We use the following hyper-parameters in our experiments; see Table [4](https://arxiv.org/html/2506.03337v1#A3.T4)

**Table 4: Hyper-parameters used in our experiments.**
| Parameter | Value |
| --- | --- |
| Meerkat learning rate | [2e-4, 2e-8] |
| Meerkat-vp learning rate | [2e-4, 2e-8] |
| LoRA-FedZO learning rate | [2e-4, 2e-8] |
| Full-FedZO learning rate | [2e-4, 2e-8] |
| Batch size | 16 |
| Dirichlet alpha | 0.5, 0.3, 0.1 |
| LoRA rank | 16 |
| LoRA alpha | 16 |
| initial phase steps | 20 |
| later phase steps | 20 |
| convergence threshold | 1 |
| quiescent step ratio | [0.4, 0.5, 0.7] |
| Initial to later ratio | [1.5, 2, 5, 10, 15] |
| calibration steps | 100 |
| Total clients | 10 |

### C.2 Additional Experiment Results

In this section, we present additional experimental results to compare Meerkat, Meerkat-vp, Full-FedZO, and LoRA-FedZO under various settings. The results include five tables and three figures, providing a detailed evaluation of performance across different models, datasets and experiment settings. Table [3](https://arxiv.org/html/2506.03337v1#A3.T3) provides a description of the parameters used in Meerkat-vp, and Table [4](https://arxiv.org/html/2506.03337v1#A3.T4) lists the experiment parameters used in this experiment.Table [5](https://arxiv.org/html/2506.03337v1#A3.T5) compares Meerkat and Full-FedZO on multiple tasks at the same communication frequency for Llama-3.2-1B, Qwen2-1.5B, and Gemma-2-2b models. Table [6](https://arxiv.org/html/2506.03337v1#A3.T6) presents results in a Non-IID client data scenario, comparing Meerkat-vp and Meerkat under the same communication frequency and sparsity density, and demonstrating Meerkat-vp improved performance.
Table [7](https://arxiv.org/html/2506.03337v1#A3.T7) investigates the robustness of Meerkat by evaluating test accuracy with local step 1 across different sparsity densities. Table [8](https://arxiv.org/html/2506.03337v1#A3.T8) compares Meerkat, Full-FedZO and LoRA-FedZO under high communication frequency across IID and Non-IID client data settings. Figure [7](https://arxiv.org/html/2506.03337v1#A3.F7) and Figure [9](https://arxiv.org/html/2506.03337v1#A3.F9) further illustrate the phenomenon of GradIP under IID and Non-IID client data settings.

**Table 5: Performance comparison of Meerkat and Full-FedZO on tasks SST-2, AgNews, Yelp, BoolQ, RTE, WSC, WIC under an IID client data setting. “Acc” is the average test accuracy across tasks. Bold numbers indicate the highest value in each row.**
|  | Methods | Local Step | SST-2 | AgNews | Yelp | BoolQ | RTE | WSC | WIC | Acc |
| --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- |
| LLaMA-3.2-1B | Full-FedZO | 10 | 0.913 | 0.700 | 0.938 | 0.646 | 0.537 | 0.634 | 0.540 | 0.701 |
| Meerkat | 10 | 0.925 | 0.881 | 0.964 | 0.751 | 0.684 | 0.634 | 0.648 | 0.784 |  |
| Full-FedZO | 30 | 0.913 | 0.700 | 0.935 | 0.643 | 0.542 | 0.634 | 0.528 | 0.699 |  |
| Meerkat | 30 | 0.919 | 0.865 | 0.967 | 0.729 | 0.644 | 0.663 | 0.617 | 0.772 |  |
| Full-FedZO | 50 | 0.913 | 0.698 | 0.939 | 0.641 | 0.520 | 0.634 | 0.539 | 0.698 |  |
| Meerkat | 50 | 0.920 | 0.871 | 0.966 | 0.734 | 0.648 | 0.653 | 0.614 | 0.772 |  |
| Full-FedZO | 100 | 0.903 | 0.705 | 0.934 | 0.656 | 0.537 | 0.634 | 0.537 | 0.701 |  |
| Meerkat | 100 | 0.913 | 0.842 | 0.945 | 0.722 | 0.573 | 0.634 | 0.595 | 0.746 |  |
| Qwen2-1.5b | Full-FedZO | 10 | 0.891 | 0.701 | 0.931 | 0.696 | 0.800 | 0.682 | 0.579 | 0.754 |
| Meerkat | 10 | 0.944 | 0.889 | 0.942 | 0.788 | 0.817 | 0.700 | 0.656 | 0.819 |  |
| Full-FedZO | 30 | 0.902 | 0.702 | 0.930 | 0.709 | 0.817 | 0.663 | 0.583 | 0.758 |  |
| Meerkat | 30 | 0.942 | 0.895 | 0.940 | 0.786 | 0.840 | 0.710 | 0.659 | 0.825 |  |
| Full-FedZO | 50 | 0.902 | 0.705 | 0.929 | 0.701 | 0.808 | 0.663 | 0.590 | 0.757 |  |
| Meerkat | 50 | 0.942 | 0.885 | 0.934 | 0.784 | 0.840 | 0.634 | 0.637 | 0.808 |  |
| Full-FedZO | 100 | 0.899 | 0.714 | 0.928 | 0.705 | 0.831 | 0.682 | 0.594 | 0.765 |  |
| Meerkat | 100 | 0.946 | 0.886 | 0.930 | 0.776 | 0.804 | 0.653 | 0.653 | 0.807 |  |
| Gemma2-2b | Full-FedZO | 10 | 0.87 | 0.732 | 0.944 | 0.717 | 0.564 | 0.634 | 0.592 | 0.723 |
| Meerkat | 10 | 0.943 | 0.892 | 0.97 | 0.817 | 0.724 | 0.653 | 0.636 | 0.805 |  |
| Full-FedZO | 30 | 0.91 | 0.81 | 0.942 | 0.73 | 0.56 | 0.644 | 0.578 | 0.739 |  |
| Meerkat | 30 | 0.943 | 0.887 | 0.973 | 0.812 | 0.617 | 0.663 | 0.608 | 0.786 |  |
| Full-FedZO | 50 | 0.911 | 0.812 | 0.942 | 0.735 | 0.551 | 0.634 | 0.572 | 0.737 |  |
| Meerkat | 50 | 0.94 | 0.873 | 0.964 | 0.812 | 0.604 | 0.634 | 0.617 | 0.778 |  |
| Full-FedZO | 100 | 0.917 | 0.83 | 0.936 | 0.728 | 0.56 | 0.644 | 0.59 | 0.744 |  |
| Meerkat | 100 | 0.949 | 0.87 | 0.954 | 0.815 | 0.568 | 0.634 | 0.592 | 0.769 |  |

**Table 6: Comparison of Meerkat-vp and Meerkat under Non-IID client data setting, with the same local step and sparsity. Tasks include SST-2, AgNews, Yelp, BoolQ, RTE, WSC, and WIC. “Acc” indicates the average test accuracy across all tasks. Bold numbers highlight the best result in each row.**
|  | Methods | Local Step | SST-2 | AgNews | Yelp | BoolQ | RTE | WSC | WIC | Acc |
| --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- |
| LLaMA-3.2-1B | Meerkat-vp | 10 | 0.922 | 0.864 | 0.962 | 0.713 | 0.617 | 0.644 | 0.625 | 0.764 |
| Meerkat | 10 | 0.916 | 0.872 | 0.964 | 0.695 | 0.600 | 0.653 | 0.614 | 0.759 |  |
| Meerkat-vp | 30 | 0.919 | 0.825 | 0.963 | 0.685 | 0.595 | 0.634 | 0.631 | 0.750 |  |
| Meerkat | 30 | 0.897 | 0.862 | 0.965 | 0.646 | 0.577 | 0.644 | 0.583 | 0.739 |  |
| Meerkat-vp | 50 | 0.909 | 0.836 | 0.959 | 0.691 | 0.577 | 0.615 | 0.615 | 0.743 |  |
| Meerkat | 50 | 0.909 | 0.827 | 0.965 | 0.647 | 0.595 | 0.634 | 0.567 | 0.734 |  |
| Meerkat-vp | 100 | 0.904 | 0.824 | 0.962 | 0.684 | 0.577 | 0.653 | 0.630 | 0.747 |  |
| Meerkat | 100 | 0.896 | 0.777 | 0.961 | 0.658 | 0.577 | 0.644 | 0.573 | 0.726 |  |
| Qwen2-1.5b | Meerkat-vp | 10 | 0.941 | 0.886 | 0.947 | 0.76 | 0.822 | 0.653 | 0.636 | 0.806 |
| Meerkat | 10 | 0.949 | 0.881 | 0.934 | 0.752 | 0.813 | 0.682 | 0.628 | 0.805 |  |
| Meerkat-vp | 30 | 0.935 | 0.876 | 0.953 | 0.759 | 0.822 | 0.653 | 0.626 | 0.803 |  |
| Meerkat | 30 | 0.944 | 0.878 | 0.928 | 0.734 | 0.800 | 0.663 | 0.624 | 0.795 |  |
| Meerkat-vp | 50 | 0.931 | 0.882 | 0.946 | 0.754 | 0.804 | 0.644 | 0.63 | 0.798 |  |
| Meerkat | 50 | 0.948 | 0.872 | 0.926 | 0.746 | 0.795 | 0.663 | 0.594 | 0.792 |  |
| Meerkat-vp | 100 | 0.935 | 0.874 | 0.947 | 0.751 | 0.817 | 0.653 | 0.644 | 0.803 |  |
| Meerkat | 100 | 0.936 | 0.878 | 0.925 | 0.741 | 0.795 | 0.663 | 0.61 | 0.792 |  |
| Gemma2-2b | Meerkat-vp | 10 | 0.948 | 0.873 | 0.971 | 0.802 | 0.657 | 0.663 | 0.609 | 0.789 |
| Meerkat | 10 | 0.939 | 0.869 | 0.96 | 0.804 | 0.591 | 0.634 | 0.609 | 0.772 |  |
| Meerkat-vp | 30 | 0.948 | 0.86 | 0.974 | 0.799 | 0.6 | 0.634 | 0.619 | 0.776 |  |
| Meerkat | 30 | 0.94 | 0.855 | 0.947 | 0.734 | 0.568 | 0.644 | 0.601 | 0.755 |  |
| Meerkat-vp | 50 | 0.949 | 0.853 | 0.969 | 0.782 | 0.551 | 0.615 | 0.620 | 0.762 |  |
| Meerkat | 50 | 0.945 | 0.857 | 0.966 | 0.767 | 0.613 | 0.634 | 0.623 | 0.772 |  |
| Meerkat-vp | 100 | 0.944 | 0.812 | 0.97 | 0.733 | 0.551 | 0.634 | 0.634 | 0.754 |  |
| Meerkat | 100 | 0.94 | 0.851 | 0.951 | 0.745 | 0.551 | 0.634 | 0.574 | 0.749 |  |

**Table 7: Meerkat performance at local step $=1$ with varying outlier percentages across the LLaMA-3.2-1B, Qwen2-1.5b, and Gemma2-2b models. We report test accuracy on SST-2, AgNews, Yelp, BoolQ, RTE, WSC, and WIC under both IID and Non-IID client data settings. Bold numbers indicate the highest value in each row.**
|  |  | IID | Non-IID |  |  |  |  |  |  |  |  |  |  |  |  |
| --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- |
| Model | Outlier Percentage | SST-2 | AgNews | Yelp | BoolQ | RTE | WSC | WIC | SST-2 | AgNews | Yelp | BoolQ | RTE | WSC | WIC |
| LLaMA-3.2-1B | 5e-1 | 0.917 | 0.72 | 0.965 | 0.725 | 0.653 | 0.644 | 0.634 | 0.895 | 0.669 | 0.964 | 0.684 | 0.644 | 0.653 | 0.594 |
| 5e-2 | 0.913 | 0.861 | 0.966 | 0.749 | 0.653 | 0.644 | 0.633 | 0.915 | 0.87 | 0.97 | 0.722 | 0.653 | 0.644 | 0.619 |  |
| 5e-3 | 0.900 | 0.885 | 0.971 | 0.769 | 0.702 | 0.653 | 0.614 | 0.930 | 0.874 | 0.963 | 0.753 | 0.620 | 0.66 | 0.62 |  |
| 5e-4 | 0.910 | 0.877 | 0.954 | 0.773 | 0.720 | 0.663 | 0.641 | 0.911 | 0.888 | 0.956 | 0.700 | 0.693 | 0.663 | 0.628 |  |
|  | 5e-5 | 0.922 | 0.879 | 0.964 | 0.724 | 0.631 | 0.625 | 0.648 | 0.92 | 0.876 | 0.940 | 0.725 | 0.613 | 0.663 | 0.626 |
| Qwen2-1.5b | 5e-1 | 0.854 | 0.856 | 0.947 | 0.766 | 0.82 | 0.663 | 0.644 | 0.845 | 0.854 | 0.946 | 0.753 | 0.826 | 0.682 | 0.631 |
| 5e-2 | 0.925 | 0.868 | 0.949 | 0.778 | 0.826 | 0.692 | 0.647 | 0.93 | 0.853 | 0.943 | 0.759 | 0.822 | 0.663 | 0.663 |  |
| 5e-3 | 0.926 | 0.851 | 0.945 | 0.765 | 0.813 | 0.692 | 0.658 | 0.924 | 0.866 | 0.94 | 0.759 | 0.822 | 0.692 | 0.661 |  |
| 5e-4 | 0.92 | 0.764 | 0.943 | 0.774 | 0.813 | 0.682 | 0.645 | 0.918 | 0.848 | 0.943 | 0.762 | 0.813 | 0.682 | 0.647 |  |
|  | 5e-5 | 0.903 | 0.78 | 0.941 | 0.748 | 0.80 | 0.673 | 0.625 | 0.896 | 0.799 | 0.937 | 0.739 | 0.80 | 0.673 | 0.633 |
| Gemma2-2b | 5e-1 | 0.842 | 0.867 | 0.963 | 0.751 | 0.657 | 0.673 | 0.626 | 0.871 | 0.855 | 0.952 | 0.695 | 0.653 | 0.663 | 0.619 |
| 5e-2 | 0.932 | 0.878 | 0.977 | 0.809 | 0.791 | 0.663 | 0.623 | 0.92 | 0.863 | 0.968 | 0.786 | 0.706 | 0.653 | 0.634 |  |
| 5e-3 | 0.952 | 0.871 | 0.971 | 0.837 | 0.800 | 0.663 | 0.639 | 0.942 | 0.853 | 0.97 | 0.807 | 0.751 | 0.653 | 0.645 |  |
| 5e-4 | 0.941 | 0.824 | 0.967 | 0.83 | 0.764 | 0.663 | 0.612 | 0.941 | 0.83 | 0.962 | 0.831 | 0.746 | 0.634 | 0.63 |  |
|  | 5e-5 | 0.92 | 0.828 | 0.952 | 0.797 | 0.6 | 0.634 | 0.606 | 0.922 | 0.764 | 0.949 | 0.774 | 0.56 | 0.634 | 0.601 |

**Table 8: Performance comparison of Full-FedZO, LoRA-FedZO, and Meerkat under synchronous updates with $localstep=1$, evaluated on both IID and Non-IID client data settings(Dirichlet $\alpha=0.5$) across LLaMA-3.2-1B, Qwen2-1.5b, and Gemma2-2b. We report test accuracy on SST-2, AgNews, Yelp, BoolQ, RTE, WSC, and WIC. Bold numbers indicate the highest value in each row.**
| Model | Method | SST-2 | AgNews | Yelp | BoolQ | RTE | WSC | WIC | Acc |
| --- | --- | --- | --- | --- | --- | --- | --- | --- | --- |
| LLaMA-3.2-1B (IID) | Full-FedZO | 0.918 | 0.801 | 0.937 | 0.686 | 0.54 | 0.625 | 0.58 | 0.726 |
| LoRA-FedZO | 0.915 | 0.855 | 0.944 | 0.672 | 0.599 | 0.663 | 0.599 | 0.749 |  |
| Meerkat | 0.900 | 0.885 | 0.971 | 0.773 | 0.702 | 0.653 | 0.614 | 0.785 |  |
| LLaMA-3.2-1B (Non-IID) | Full-FedZO | 0.911 | 0.831 | 0.937 | 0.672 | 0.528 | 0.587 | 0.567 | 0.719 |
| LoRA-FedZO | 0.8669 | 0.842 | 0.944 | 0.659 | 0.53 | 0.567 | 0.578 | 0.712 |  |
| Meerkat | 0.93 | 0.888 | 0.963 | 0.753 | 0.67 | 0.66 | 0.62 | 0.783 |  |
| Qwen2-1.5b (IID) | Full-FedZO | 0.9013 | 0.726 | 0.918 | 0.700 | 0.797 | 0.710 | 0.579 | 0.761 |
| LoRA-FedZO | 0.935 | 0.752 | 0.925 | 0.686 | 0.794 | 0.673 | 0.606 | 0.767 |  |
| Meerkat | 0.926 | 0.851 | 0.945 | 0.778 | 0.813 | 0.692 | 0.658 | 0.809 |  |
| Qwen2-1.5b (Non-IID) | Full-FedZO | 0.844 | 0.725 | 0.937 | 0.688 | 0.769 | 0.663 | 0.565 | 0.741 |
| LoRA-FedZO | 0.932 | 0.76 | 0.944 | 0.682 | 0.773 | 0.682 | 0.565 | 0.763 |  |
| Meerkat | 0.924 | 0.866 | 0.94 | 0.762 | 0.822 | 0.692 | 0.661 | 0.809 |  |
| Gemma2-2b (IID) | Full-FedZO | 0.934 | 0.84 | 0.953 | 0.774 | 0.542 | 0.644 | 0.606 | 0.756 |
| LoRA-FedZO | 0.942 | 0.856 | 0.94 | 0.735 | 0.52 | 0.644 | 0.606 | 0.749 |  |
| Meerkat | 0.952 | 0.871 | 0.971 | 0.837 | 0.8 | 0.663 | 0.639 | 0.819 |  |
| Gemma2-2b (Non-IID) | Full-FedZO | 0.93 | 0.824 | 0.95 | 0.744 | 0.56 | 0.625 | 0.575 | 0.744 |
| LoRA-FedZO | 0.9415 | 0.825 | 0.954 | 0.711 | 0.528 | 0.625 | 0.578 | 0.737 |  |
| Meerkat | 0.942 | 0.853 | 0.97 | 0.807 | 0.751 | 0.653 | 0.645 | 0.803 |  |

**Table 9: Performance comparison of LoRA-FedZO, and Meerkat under synchronous updates with $localstep=1$, evaluated on Non-IID client data settings (Dirichlet $\alpha=0.3$) across LLaMA-3.2-1B, Qwen2-1.5b, and Gemma2-2b. We report test accuracy on SST-2, AgNews, Yelp, BoolQ, RTE, WSC, and WIC. Bold numbers indicate the highest value in each row.**
| Model | Method | SST-2 | AgNews | Yelp | BoolQ | RTE | WSC | WIC | Acc |
| --- | --- | --- | --- | --- | --- | --- | --- | --- | --- |
| LLaMA-3.2-1B (Non-IID) | Full-FedZO | 0.891 | 0.759 | 0.94 | 0.623 | 0.528 | 0.644 | 0.551 | 0.705 |
| LoRA-FedZO | 0.915 | 0.866 | 0.952 | 0.646 | 0.586 | 0.653 | 0.554 | 0.739 |  |
| Meerkat | 0.918 | 0.843 | 0.97 | 0.761 | 0.626 | 0.653 | 0.609 | 0.769 |  |
| Qwen2-1.5b (Non-IID) | Full-FedZO | 0.52 | 0.347 | 0.45 | 0.62 | 0.532 | 0.632 | 0.51 | 0.516 |
| LoRA-FedZO | 0.855 | 0.732 | 0.907 | 0.674 | 0.72 | 0.634 | 0.603 | 0.732 |  |
| Meerkat | 0.91 | 0.809 | 0.954 | 0.772 | 0.822 | 0.682 | 0.661 | 0.801 |  |
| Gemma2-2b (Non-IID) | Full-FedZO | 0.881 | 0.761 | 0.94 | 0.688 | 0.552 | 0.613 | 0.603 | 0.720 |
| LoRA-FedZO | 0.922 | 0.826 | 0.921 | 0.681 | 0.52 | 0.625 | 0.606 | 0.729 |  |
| Meerkat | 0.942 | 0.873 | 0.97 | 0.806 | 0.688 | 0.634 | 0.615 | 0.79 |  |

**Table 10: Performance comparison of LoRA-FedZO, and Meerkat under synchronous updates with $localstep=1$, evaluated on Non-IID client data settings (Dirichlet $\alpha=0.1$) across LLaMA-3.2-1B, Qwen2-1.5b, and Gemma2-2b. We report test accuracy on SST-2, AgNews, Yelp, BoolQ, RTE, WSC, and WIC. Bold numbers indicate the highest value in each row.**
| Model | Method | SST-2 | AgNews | Yelp | BoolQ | RTE | WSC | WIC | Acc |
| --- | --- | --- | --- | --- | --- | --- | --- | --- | --- |
| LLaMA-3.2-1B (Non-IID) | Full-FedZO | 0.891 | 0.754 | 0.933 | 0.626 | 0.522 | 0.365 | 0.512 | 0.658 |
| LoRA-FedZO | 0.902 | 0.845 | 0.942 | 0.643 | 0.533 | 0.365 | 0.559 | 0.684 |  |
| Meerkat | 0.92 | 0.794 | 0.965 | 0.745 | 0.582 | 0.644 | 0.603 | 0.750 |  |
| Qwen2-1.5b (Non-IID) | Full-FedZO | 0.49 | 0.247 | 0.44 | 0.62 | 0.528 | 0.634 | 0.5 | 0.494 |
| LoRA-FedZO | 0.848 | 0.735 | 0.92 | 0.67 | 0.746 | 0.548 | 0.601 | 0.724 |  |
| Meerkat | 0.889 | 0.78 | 0.944 | 0.732 | 0.822 | 0.634 | 0.637 | 0.777 |  |
| Gemma2-2b (Non-IID) | Full-FedZO | 0.879 | 0.741 | 0.937 | 0.681 | 0.48 | 0.634 | 0.601 | 0.708 |
| LoRA-FedZO | 0.91 | 0.78 | 0.914 | 0.682 | 0.551 | 0.567 | 0.608 | 0.716 |  |
| Meerkat | 0.944 | 0.866 | 0.971 | 0.805 | 0.728 | 0.605 | 0.628 | 0.792 |  |

Figure: (a) This figure compares three methods—Full-FedZO, LoRA-FedZO, and Meerkat—on three LLMs: LLaMA-3.2-1B, Qwen2-1.5b, and Gemma2-2b. The x-axis shows the different methods, and each method has two bars indicating performance under IID and Non-IID settings. The Non-IID results are obtained under a Dirichlet $\alpha=0.3$ .The y-axis represents the average test accuracy across multiple downstream tasks—SST2, AgNews, Yelp, BoolQ, RTE, WSC, and WiC.
Refer to caption: x6.png

**Table 11: Test accuracy of Meerkat versus DecomFL on Qwen2-1.5b with a single local step under Non-IID data settings (Dirichlet $\alpha=1$). Results are shown for SST-2, BoolQ, RTE, and WSC; bold indicates the best score in each row. Experiments use 8 clients in total, with 2 clients participating in each round, following the DecomFL configuration.**
| Model | Method | SST-2 | BoolQ | RTE | WSC |
| --- | --- | --- | --- | --- | --- |
| Qwen2-1.5b | DecomFL | 0.868 | 0.674 | 0.773 | 0.653 |
| Meerkat | 0.918 | 0.734 | 0.817 | 0.682 |  |

**Table 12: Performance comparison of Task-Mask, and Meerkat under synchronous updates with $localstep=1$, evaluated on IID client data settings across LLaMA-3.2-1B, Qwen2-1.5b, and Gemma2-2b. We report test accuracy on SST-2, AgNews, Yelp, BoolQ, RTE, WSC, and WIC. Bold numbers indicate the highest value in each row.**
| Model | Method | SST-2 | AgNews | Yelp | BoolQ | RTE | WSC | WIC |
| --- | --- | --- | --- | --- | --- | --- | --- | --- |
| LLaMA-3.2-1B (IID) | Task | 0.910 | 0.847 | 0.957 | 0.718 | 0.661 | 0.644 | 0.661 |
| Meerkat | 0.90 | 0.885 | 0.971 | 0.773 | 0.702 | 0.653 | 0.614 |  |
| Qwen2-1.5b (IID) | Task | 0.936 | 0.827 | 0.954 | 0.765 | 0.83 | 0.711 | 0.664 |
| Meerkat | 0.926 | 0.851 | 0.945 | 0.778 | 0.813 | 0.692 | 0.658 |  |
| Gemma2-2b (IID) | Task | 0.942 | 0.868 | 0.972 | 0.78 | 0.728 | 0.644 | 0.6 |
| Meerkat | 0.952 | 0.871 | 0.971 | 0.837 | 0.8 | 0.663 | 0.639 |  |

**Table 13: Performance comparison of Task-Mask, and Meerkat under synchronous updates with $localstep=1$, evaluated on Non-IID client data settings (Dirichlet $\alpha=0.5$) across LLaMA-3.2-1B, Qwen2-1.5b, and Gemma2-2b. We report test accuracy on SST-2, AgNews, Yelp, BoolQ, RTE, WSC, and WIC. Bold numbers indicate the highest value in each row.**
| Model | Method | SST-2 | AgNews | Yelp | BoolQ | RTE | WSC | WIC |
| --- | --- | --- | --- | --- | --- | --- | --- | --- |
| LLaMA-3.2-1B (Non-IID) | Task | 0.904 | 0.874 | 0.956 | 0.744 | 0.591 | 0.615 | 0.622 |
| Meerkat | 0.93 | 0.888 | 0.963 | 0.753 | 0.62 | 0.66 | 0.62 |  |
| Qwen2-1.5b (Non-IID) | Task | 0.938 | 0.863 | 0.956 | 0.779 | 0.817 | 0.692 | 0.65 |
| Meerkat | 0.924 | 0.866 | 0.94 | 0.762 | 0.822 | 0.692 | 0.661 |  |
| Gemma2-2b (Non-IID) | Task | 0.91 | 0.834 | 0.966 | 0.822 | 0.72 | 0.644 | 0.578 |
| Meerkat | 0.942 | 0.853 | 0.97 | 0.807 | 0.751 | 0.653 | 0.645 |  |

**Table 14: Test accuracy of Meerkat versus Task-Mask on Qwen2-1.5b with a 10 local step under Non-IID data settings (Dirichlet $\alpha=0.5$). Results are shown for SST-2, BoolQ, RTE, and WSC; bold indicates the best score in each row. Experiments use 8 clients in total, with 2 clients participating in each round, following the DecomFL configuration.**
| Model | Method | SST-2 | BoolQ | RTE | WSC |
| --- | --- | --- | --- | --- | --- |
| Qwen2-1.5b | Task | 0.932 | 0.784 | 0.823 | 0.681 |
| Meerkat | 0.944 | 0.752 | 0.813 | 0.682 |  |

Figure: (a) The GradIP measured for IID and Non-IID clients data under the WIC task using the Llama-3.2-1B model.
Refer to caption: x8.png

Figure: (a) Cosine similarity between local ZO gradients and C4 pre-trained gradients.
Refer to caption: x15.png

Figure: (a) GradIP for Non-IID clients on the AgNews task, where the two classes have a highly imbalanced ratio (5 vs. 89 samples).
Refer to caption: x17.png

Figure: (a) The experiments, conducted using the Qwen2-1.5B model on the BoolQ dataset, reveal that under Non-IID settings—especially with a 1:20 class imbalance—there is a pronounced decline in GradIP between the early and later stages of training. In the extreme Non-IID case, the GradIP values in the later stages tend to approach zero.
Refer to caption: x19.png

Figure: (a) The experiments, conducted using the Qwen2-1.5B model on the AGNews dataset, reveal that under Non-IID settings—especially with a 1:15:1:1 class imbalance—there is a pronounced decline in GradIP between the early and later stages of training. In the extreme Non-IID case, the GradIP values in the later stages tend to approach zero.
Refer to caption: x22.png

## Peer Reviews

confidence: 3
contribution: 4
initial_rating: 6
presentation: 4
questions: see weakness 1, 2, 3
soundness: 4
strengths: 1. Virtual path and GradIP are novel ideas. By reconstructing each client’s local update trajectory, the server gains visibility into how that client is moving in parameter space without seeing private data. GradIP then becomes a quantitative signal that reveals which clients are extreme Non IID.

2. The paper provides convergence analyses for both MEERKAT and MEERKAT VP.

2. Strong empirical validation. The experiments cover multiple open LLMs (Llama 3.2 1B, Qwen2 1.5B, Gemma2 2B), multiple tasks (SST2, AgNews, Yelp polarity, BoolQ, RTE, WSC, WiC), both IID and strongly Non IID Dirichlet splits, and multiple baselines
summary: This paper proposes a sparse zeroth order federated fine tuning framework for LLMs that is both theoretically grounded and highly practical. MEERKAT uses a transferable 0.1 percent sensitivity mask and frequent synchronization to tame memory and bandwidth while reducing Non IID drift. Virtual path reconstruction and the GradIP score then allow the server to detect extreme Non IID clients and actively limit their damage through MEERKAT VP. Experiments across multiple open LLMs and multiple classification and reasoning benchmarks show consistent gains over strong baselines like Full FedZO and LoRA FedZO at matched communication frequency, along with dramatic savings in memory and bandwidth.
weaknesses: 1. hyperparameters in MEERKAT VP : The early stopping rule uses thresholds on GradIP phase ratios and quiescent duration. Although a small sensitivity study is reported, it is still unclear how practitioners should pick these thresholds for new tasks with no oracle labels. 


2. Baselines in experiments:  There is active work on federated LoRA under heterogeneous clients, which explicitly tackles aggregation noise, knowledge contamination, and aggregation distortion by separating global and client specific structure or by using rank adaptive aggregation. The paper mentions LoRA FedZO but does not deeply compare against these newer structured aggregation approaches, so it is hard to see whether MEERKAT VP replaces them, complements them, or could be combined with them. Existing works are listed below: 

[1] Zhe Li, Bicheng Ying, Zidong Liu, Chaosheng Dong, and Haibo Yang. Achieving dimension-free
communication in federated learning via zeroth-order optimization. In The Thirteenth International
Conference on Learning Representations, 2025.

[2] Youbang Sun, Zitao Li, Yaliang Li, and Bolin Ding. Improving loRA in privacy-preserving federated
learning. In The Twelfth International Conference on Learning Representations, 2024.

[3] Pengxin Guo, Shuang Zeng, Yanran Wang, Huijie Fan, Feifei Wang, and Liangqiong Qu. Selective
aggregation for low-rank adaptation in federated learning. In The Thirteenth International
Conference on Learning Representations, 2025.

3. Lack of explicit adversarial evaluation: MEERKAT VP is essentially throttling clients whose updates are harmful. This is similar to defending against malicious or poisoned clients. However, the experiments do not include adversarial threat models like label flipping or Byzantine behavior. Showing that GradIP based early stopping also mitigates such attacks would significantly strengthen the robustness story.

---

confidence: 4
contribution: 3
initial_rating: 6
presentation: 2
questions: i.Would the performance of MEERKAT/MEERKAT-VP significantly decline as the number of clients increases to a larger magnitude? For example, would the server-side virtual path reconstruction incur a higher computational overhead with an increased number of clients, and has the potential reduction in the efficiency of MEERKAT-VP's early stopping strategy been considered if a large number of clients are categorized as "extreme Non-IID"?

ii.The early stopping strategy of  MEERKAT-VP relies on a threshold for identifying the GradIP phenomenon. How is this threshold determined? Should the paper analyze the model performance's sensitivity to this threshold choice, and potentially propose an automatic or adaptive mechanism for threshold selection?
soundness: 3
strengths: i.MEERKAT employs an extremely sparse and static subset of parameters for fine-tuning. This drastically reduces the communication load and memory consumption on client devices, addressing the primary scalability bottleneck of LLMs in FL.

ii.The extreme sparsity enables cost-effective high-frequency client-server synchronization. This high synchronization rate is key to effectively suppressing the client drift caused by Non-IID data distributions across decentralized clients.

iii.The paper proposes using a static sparsity mask identified through gradients from pre-training data. This transferable sparsity ensures that the chosen small subset of parameters is highly effective for downstream tasks, allowing for consistent performance throughout the FL process.

iv.MEERKAT-VP introduces the Virtual Path mechanism, which allows the server to diagnose the severity of Non-IID data without accessing the raw client data.It utilizes the discovered GradIP phenomenon to strategically identify and apply early stopping to severely Non-IID clients. This ensures robustness and convergence quality while maintaining data privacy.

v.The work provides strong experimental evidence demonstrating that MEERKAT consistently outperforms full-parameter Zeroth-Order Optimization and other SOTA sparse fine-tuning methods under various Non-IID settings.

vi.The use of Zeroth-Order Optimization , combined with extreme sparsity, makes the approach highly suitable for clients with limited computational resources, as it avoids the need to calculate full, complex second-order gradient information.
summary: This paper introduces MEERKAT and its extension MEERKAT-VP, a novel methodology to tackle the twin challenges of high communication overhead and Non-IID data drift when fine-tuning LLMs in a Federated Learning setting. MEERKAT addresses efficiency by using a sparse Zeroth-Order Optimization method that limits fine-tuning to an extremely sparse (e.g., <0.1%), static subset of parameters, drastically reducing communication costs and enabling high-frequency server synchronization to mitigate drift. Building on this, MEERKAT-VP uses the concept of a virtual path based on local updates to detect the GradIP phenomenon in extreme Non-IID clients, subsequently applying early stopping to restrict these clients' local steps, thereby improving global model quality. The experiments confirm that MEERKAT, through its combined approach of extreme sparsity and strategic client management, effectively mitigates Non-IID data challenges and achieves superior performance and efficiency compared to existing baselines.
weaknesses: i.In the description of the steps in Figure 1 of the paper, the word "Aggregrate" appears, and the correct spelling should be "Aggregate".In the phrase on lines 153–154, "(3) Sever aggregates and initiate the next round...", shouldn't the word "Sever" actually be spelled "Server"?Line 165 contains a redundant repetition of the article "a" in the phrase "and a a new seed list."

ii.Although the paper validates the effectiveness of the extreme sparsity level of 0.1%, it fails to deeply analyze the performance impact of varying sparsity levels (such as 0.01%, 0.5%, 1%) across different scales of LLMs (e.g., larger models like 7B/13B) and different task types (e.g., complex reasoning tasks versus simple classification tasks). Furthermore, the transferability of the sparsity mask was only tested on a few domain shift datasets (C4, Wiki, Code datasets) and was not verified for its adaptability in highly specialized domains (such as legal), thus making it difficult to support a conclusion of broader applicability.

iii.The paper compares MEERKAT/MEERKAT-VP against Full-FedZO, LoRA-FedZO, and the baseline FedDYN improvement method. However, it fails to include state-of-the-art Federated LLM fine-tuning methods specifically designed for Non-IID scenarios. These missing baselines include established methods adaptable for LLMs, such as FedAvgM and SCAFFOLD, or FedSparse. This omission makes it difficult to ascertain whether the performance advantages of the proposed method truly surpass the latest research achievements.

---

confidence: 3
contribution: 2
initial_rating: 2
presentation: 3
questions: * The client identification mechanism in MEERKAT-VP uses an "initial phase" and a "later phase" of local training to analyze GradIP scores. What is the motivation for this two-phase design?
* Figure 3 shows the GradIP trajectories. To make the effect of the proposed solution more intuitive, could the authors add a plot showing the trajectory for a client being managed by MEERKAT-VP (i.e., after mitigating the global weight changes after the design)?
soundness: 2
strengths: * The paper is clearly presented, systematically proposing three distinct claims and validating them one by one.
* It includes a detailed convergence analysis for the proposed methods.
* The experimental evaluation is comprehensive, covering various benchmarks and recent LLMs.
summary: This paper proposes MEERKAT, a sparse zeroth-order optimization method for federated LLM fine-tuning. By updating a static, highly sparse subset of parameters, MEERKAT reduces communication costs and enables frequent synchronization to alleviate Non-IID drift. It also introduces a “virtual path” mechanism that uncovers the GradIP phenomenon—the inner product between server and client gradients varies across data heterogeneity. Building on this, MEERKAT-VP detects extreme Non-IID clients and mitigates their impact through early stopping. The paper provides theoretical convergence results and validates the method with extensive experiments.
weaknesses: * The use of sparse updates for communication efficiency in FL is a well-explored area, often framed as model compression. The paper should provide a more thorough comparison with this body of work to clarify the unique contributions of applying sparsity specifically to ZO-based FL fine-tuning. Applying sparsity to new FL models (here is federated fine-tuning) seems not a strong contribution.
* Methods for tackling the Non-IID issue in compressed FL have also been developed, such as the one in [a]. The paper would be stronger if it compared its GradIP-aware solution not just with other non-sparse fine-tuning methods, but also with compression-aware FL baselines that explicitly address Non-IID data, even if they are not designed for LLMs.
* The rationale for setting the number of local training steps to one for identified Non-IID clients is not fully convincing. These clients may hold important minority data that is crucial for preventing the global model from becoming biased. You should not move it only because it is minority and hard to converge into the global model. The paper should better justify why this aggressive early stopping is preferable to other strategies that might still leverage the clients' unique data more fully. 

[a] Huang, Xinmeng, Ping Li, and Xiaoyun Li. "Stochastic Controlled Averaging for Federated Learning with Communication Compression." The Twelfth International Conference on Learning Representations.

---

confidence: 4
contribution: 3
initial_rating: 6
presentation: 3
questions: The core optimization (sparse ZO on a static mask) seems to be a general technique, not specialized for FL. Are there any other properties of this sparse ZO method that make it uniquely suited for the federated setting, beyond the communication efficiency gains and the virtual path mechanisms they enable?
soundness: 4
strengths: 1. **Strong Empirical Performance:** The method is well-validated empirically. Empirical results clearly show that MEERKAT consistently and significantly outperforms full-parameter ZO and LoRA-based ZO baselines, especially in Non-IID settings. 
2. **Comprehensive Analysis:** The paper provides strong support for its claims through both theoretical convergence analysis and extensive empirical ablations. The validation is structured clearly around three main claims, and each is convincingly argued with evidence.
3. **Novel Mechanism for Heterogeneity:** The discovery of the "GradIP" phenomenon is a novel contribution. Using this signal, which is enabled by the virtual path, to identify and manage extreme Non-IID clients (MEERKAT-VP) is a clever and effective FL-native strategy for handling heterogeneity.
summary: This paper proposes MEERKAT, a novel framework for federated fine-tuning of LLMs that combines Zeroth-Order optimization with extreme sparsity. The core idea is that this combination is extremely memory-efficient and communication-efficient. The authors claim this efficiency enables high-frequency client-server synchronization, which in turn is the key to mitigating Non-IID client drift. Furthermore, the paper introduces a "virtual path" mechanism, where the server can reconstruct client update trajectories, and use"GradIP", a metric based on the inner product of client and pre-training gradients, that can identify clients with extreme Non-IID data. The authors then propose MEERKAT-VP, an extension that uses this signal to apply early stopping to these problematic clients, further improving global model performance.
weaknesses: The paper's primary strategy for handling extreme Non-IID clients (MEERKAT-VP) is purely defensive. It aims to "mitigate their adverse impact" by identifying them via GradIP and applying early stopping. This implies that the base MEERKAT method is still vulnerable to significant client drift from these clients. This strategy is inherently limited: it focuses on reducing the participation of "bad" clients rather than developing a mechanism to effectively learn from their (potentially valuable) information.


Decision: Accept (Poster)