Achieving Dimension-Free Communication in Federated Learning via Zeroth-Order Optimization
Authors: Zhe Li
Bicheng Ying
Zidong Liu
Chaosheng Dong
Haibo Yang
Venue: ICLR 2025 Poster (2025)
Keywords: Federated Learning
Zeroth-Order Optimization
Communication Efficiency
Low Rank
Large Language Models
Fine-Tuning
Primary area: optimization

Abstract: Federated Learning (FL) offers a promising framework for collaborative and privacy-preserving machine learning across distributed data sources. 
However, the substantial communication costs associated with FL significantly challenge its efficiency. 
Specifically, in each communication round, the communication costs scale linearly with the model's dimension, which presents a formidable obstacle, especially in large model scenarios. 
Despite various communication-efficient strategies, the intrinsic dimension-dependent communication cost remains a major bottleneck for current FL implementations.
This paper proposes a novel dimension-free communication algorithm - DeComFL, which leverages the zeroth-order optimization techniques and reduces the communication cost from $\mathcal{O}(d)$ to $\mathcal{O}(1)$ by transmitting only a constant number of scalar values between clients and the server in each round, regardless of the dimension $d$ of the model parameters.
Theoretically, in non-convex functions, we prove that our algorithm achieves state-of-the-art rates, which show a linear speedup of the number of clients and local steps under standard assumptions. With additional low effective rank assumption, we can further show that the convergence rate is independent of the model dimension $d$ as well.
Empirical evaluations, encompassing both classic deep learning training and large language model fine-tuning, demonstrate significant reductions in communication overhead. 
Notably, DeComFL achieves this by transmitting only around 1MB of data in total between the server and a client to fine-tune a model with billions of parameters. 
The code is available at https://github.com/ZidongLiu/DeComFL.

Published as a conference paper at ICLR 2025
ACHIEVING DIMENSION-FREE COMMUNICATION IN FEDERATED LEARNING VIA GEROTH-ORDER OPTI- MIZATION
Zhe Li Bicheng Ying"*, Zidong Liu", Chaosheng Dong', Haibo Yang!
1 Rochester Institute of Technology, Rochester, NY 14623, USA
2 Google Inc., Los Angeles, CA 90034, USA
"ComboCurve Inc., Houston, TX 77005, USA 'Amazon.com com Inc., Seattle, WA 98109, USA z1 4
ybc&google com, z. z.1Lu@combocurve.cm chaos sde amazon. com, hbycis@rit.edu
ABSTRACT
Federated Learning (FL) offers a promising framework for collaborative and privacy-preserving machine learning across distributed data sources. However, the substantial communication costs associated with FL significantly challenge its effi- ciency. Specifically, in each communication round, the communication costs scale linearly with the model's dimension, which presents formidable obstacle, espe- cially in large model scenarios. Despite various communication-effiiii the intrinsic dimension-deepnndnt communication cost remains a major bottleneck for current FL implementations. This paper proposes novel dimension- free com- munication algorithm - DeComFL, which leverages the zeroth-order optimization techniques and reduces the communication cost from (d) to O(1) by transmitting only constant number of scalar values between clients and the server in each round, regardless of the dimension d of the model parameters. Theoretically, non- convex functions, we prove that our algorithm achieves state-of-the-an art rates, which show a linear speedup of the number of clients and local steps under standard as- sumptions. With additional low effective rank assumption, we further show that the convergence rate independent the model dimension as well. Empirical evaluations, encompassing both classic deep learning training and large language model fine-tuning, demonstrate significant reductions in communication overhead. Notably, DeComFL achieves this by transmitting only around MMB of data in total between the server and a client to fine-tune a model with billions of parameters. The code is available at hhttps::///e wiggthubb... com/ 2idonggii//Deooo..
strategies,
INTRODUCTION
Federated Learning (FL) is promising distributed machine learning framework that enables large number of clients collaboratively train model under the orchestration of a central server (Kairouz et al., 2021 McMahan et al. 2017). By allowing clients to train models locally without sharing their raw data, FL offers privacy-preservinne preserving distributed learning paradigm. Thanks to these advantages. FL has become popular learning paradigm used in many applications, such as healthcare (Xu et al.) 202 and edge devices (Nguyen et al. 2021 Wang et al. 2021), among others.
Despite its benefits, FL often encounters challenges to its efficiency due to expensive communication costs. Specifically, in one communication round, the server needs to broadeast the global model to all participating clients, and each of these clients is expected to transmit the newest local model to the server for global aggregation (McMahan et al.] (2017). other words, the communication costs for one participating client scale linearly with the model dimension, presenting prohibitively expensive communication overhead for FL systems, especially in large model and/or low communication speed scenarios. More specifically, on the one hand, foundation models in language and vision, such as GPT-
"Equal Contribution; Corresponding Author: Haiho Yang

---

Published as a conference paper at ICLR 2025
3 (Brown al. 2020). and other models (Bommasani et al. 2021 scale with billions of parameters, leading to a tremendous total communication burden. For example, aieettnnng GPT-J-6B on 10 billion tokens with batch size of 262K tokens across four machines would involve transferring 915.5 TB of data throughout the entire training process (Wang et al., 2023b). On the other hand, the typical communication speed for FL. is several Mbps in wireless environments and up several hundred Mbps in wired connections. Given that communication costs increase linearly with model size, this presents a significant challenge in model training and fine-tuning in the FL scenario. To achieve communication-effen
FL., several techniques have been developed, including lazy aggregation or multiple local update steps (McMahan et al.] (017). various compression techniques (Bernstein et al. 2018; Vogels et al. [019:] Yang et al. [02 Waag et al., 2022] Hönig et al. 2022] Yi et al.
2024. Reisizadeh et al. 2020; Huang et al. 2023] Li Lij 2023 Haddadpour et al. 2021), and client sampling strategies (Ribero & Vikalo, 2020). While these methods can reduce certain communication costs, their communication costs still scale linearly with the model dimension for each participating client in one communication round. This intrinsic dinension- dependent communication cost remains a major challenge for current FL. systems, particularly in the era of large deep learning models.
In this paper, we propose novel FL. approach to achieve dimension-free communication per round, leveraging zeroth-order optimization techniques (Nesterov & Spokoiny] 2017 Ghadimi Gha7Gim & Lan] [0033] Liu et al. 2020). We exploit a unique property of zeroth-order gradients: they can be decomposed into a gradient scalar (magnitude) and a perturbation vector (direction). The gradient scalar is computed by using the finite difference of function values, while the perturbation vector can be generated identically across clients from a shared random seed. Therefore, instead of transmitting entire model parameters, we can communicate gradient scalars and random seeds to reconstruct full gradients, resulting in constant communication costs per round. A closely related idea is proposed in (Yue et al. 2023) that projects the first-order gradient into a random direction to get a scalar, which can be viewed as linear approximation of the ZO method. They only considered distributed shared model case. However, in the FL setting, where clients collaborate to learn a global model, simply transmitting seeds and gradient scalars reconstruct gradients is insufficient to guarantee convergence the desired global model, as detailed in a later section. Hence, we propose a novel algorithm DeComFL, deviating from traditional FL appearance while achieving the same objective.
Although the dimension-dependee nication cost, which the product of the number of rounds and the communication cost per round, might still be proportional to the model size. This is because the worst-case convergence rate of ZO methods known to depend on the model dimension (Nesterov & Spokoiny 2017: Duchi et al., 2015). Fortunately, existing works have shown that the loss landscape of deep learning lies in very low-dimensional subspace, where the Hessian of the loss has a remarkably low effective rank (Papyan) Malladi et al.) 2023). By leveraging the low effective rank assumption, we rigorously show that DeComFL achieves a convergence rate independent of the model dimension. To the best of our knowledge, this is the first systematic attempt to achieve dimension-free free communication per client in FL within each communication round and total communication cost.
communication cost per round being addressed, the total commu-
Our main results and contributions are summarized follows:
We propose DeComFL, a novel dimension communication in federated learning framework via zeroth-order optimization. In each round, both the downlink (model pulling) and uplink (model uploading) communications involve transmitting only constant number of scalar values between the participating clients and the server. This dramatically reduces the communication cost from (d) ((1) in both uplink and downlink, where d is the dimension of the model parameters.
Theoretically, in non-convex functions, we prove that DeComFL achieves O /d mPKR) R) under the standard conditions, where is the number of participating clients in one communication round, P is the number of simultaneous perturbations, K is the number of local update steps, and R is the number of communication rounds. This rate highlights the linear speedup in terms of the local update step, the number of perturbations and the clients.
Under the xeeffective rank assumption, we further prove that DeComFL achieves a dimension-free convergence rate of O / / PR). Combined with an (11) communication cost per round, the total communication cost can be established as dimension-free. To the best of our knowledge, this is the first work to achieve this rate in the distributed FL setting.
Comprehensive experiments both training and fine-tuning tasks demonstrate that DeComFL achieves comparable performance to existing algorithms while significantly reducing communi- cation costs by several orders of magnitude. For instance, by traditional methods, fine-tuning an
2

---

Published as a conference paper at ICLR 2025
OPT-1.3B Zhang al. 2022 model in an FL setting requires transmitting approximately 10 GB per round between each client and the server. In contrast, DeComFL requires only 1MB of total communication throughout the entire fine-tuning process.
RELATED WORK
Communication-Eltiieee Federated Learning: Initially, (McMahan et al. 2017) proposed the
FedAvg algorithm, which uses multiple local update steps to reduce the frequency of model transfers between the server and the client, thereby lowering the total communication cost. Since then, various techniques have been developed to further optimize communication efficiency, with most approaches
involving compression methods. For instance, sparsification (Han al. 2020; Li et al. 2020 Ozfatura
et al. 2021; Wang et al. 2023a Tang et al., 2022). quantization (Hönig et al. 2022] Huang et al.
2023
Haddadpour et al. 2021] Shlezinger et al. 2020) Jhunjhunwala et al. |021 Bouzinis et al.
2023
Liu et al. 2023 Zakerinia et al., 2024). and low-rank approximations (Vogels et al. [2019]
Martin & Mahoney (021). However, the communication cost per round between a client and the the model dimension. Taking Top-k an example (Stich et al. 2018 only the top Ik largest coordinates in the gradient vector are selected for communication. Theoretically, the convergence rate of Top-k depends on both the model dimension d and the hyper-parameter Ik. In practice, the choice of k is linearly scaled with the model dimension d, i.e., lk = с x d, where e is constant such 0.001 (Shi et al. 2019). Despite the success of these methods, the intrinsic dimension dimension-dependen communication cost remains major bottleneck for current FL systems, especially in the era of large deep learning models. In this work, our DeComFL achieves a constant (1) communication cost for uplink and downlink transmissions by zeroth-order optimization.
server remains dependent
Zeroth-Order Optimization (Z00): ZOO relies solely on function evaluations, making it ideal for scenarios where explicit gradient computation is impractical, expensive, or unreliable, such as in black-box optimization (Liu et al. 2020 Cai et al., 202T Nikolakakis et al. 2022) and reinforcement learning (Liu et al. 2020: et al. 2024] Li et al. (021). Recently, 700 has shown significant memory advantages in deep learning due to requiring only forward propagation (Malladi et al. 2023 Zhang et al. 2024). However, existing work has not fully exploited ZOO's potential to reduce communication costs in FL, as we propose in this work. For example, FedZO (Fang et al. 2022) applies zeroth-order (ZO) stochastic gradient estimation in FedAvg, achieving a convergence rate of O (V/d/mm m/dK/KBB R) in non-convex cases, but its communication complexity remains (dd) per round, the same as FedAvg. Similarly, BAFFLE (Feng et al. 2023) employs 70O to achieve ((P) communication complexity in the uplink, but the downlink communication complexity remains O(d).
3 DIMENSION-FREE COMMUNICATION IN FEDERATED LEARNING
3.1 PRELIMINARY OF THE ZEROTII-ORDER OPTIMIZATION AND FEDERATED LEARNING
As with most standard FL. settings, we assume that there exist M clients in total in our FL system. Our goal is to minimize the global loss function ff which can be formulated as,
M
min f(x) = min RERd
Σ f((z) where f((x) = E (1) mERd
M
where x is d-dimensional model parameter and f. represents the loss function on client i. The loss function is the expectation of stochastic loss function fa {t), where & is sampled from different local data distributions known as data heterogeneity in FL. The typical FL algorithm comprises three steps in each round: 1) The server initially samples a set of clients and sends the current global model to them. 2) Upon receiving the global model, each client performs multiple local updates based on this model and then transmits the updated local model back to the server. 3) The server aggregates all the returned local models from the clients and updates the global model accordingly.
More specifically, when applying the (stochastic) ZO method for the local update in the classical FedAvg (McMahan et al. 2017). it becomes FedZO (Fang et al.) (002)). The main recursion of server model x, and client models { ( can be summarized into the following forms:
w Er,, Vi C,
(Pull Model)
(2a)
k+1 =att notr 2 k 1= K
(Local Update)
(2b)
3

---

Published as a conference paper at ICLR 2025
Σ iEC.
K+1
(Aggregate Model)
(2c)
Crl
where we use the superscript & for the local update step. r for the communication round, for the client index, and C, for set of sampled client indices, 2,,, typically for random direction vector drawing either from either Gaussian or uniform ball distribution. gh, is gradient scalar calculated as
Ae (Ji(at + pat,ri - (a
(3)
where > O is the smooth parameter. Intuitively, when is sufficiently small, the scalar sf. approximates the gradient ff <x,,) inner product with the random direction = There are other types of ZO gradient estimators. However, in this paper, we only focus on this (3) form called Simultaneous Perturbation Stochastic Approximation (SPSA) (Spall 1992) with the forward style. See (Nesterov & Spokoiny 2017 Liu et al. 2020) for other forms and convergence properties.
When we examine the communication costs incurred between the client and the server within the framework outlined in equations (2a) to (2c). it becomes apparent that vector of length 2d is transmitted during each round. Specifically, the first d-length vector transmitted during the pull model step via the downlink, while the second d-length vector is sent after finishing all local update steps and before aggregating at the server via the uplink. In the era LLMs, this 2d communication cost be huge burden or This observation motivates us to design a novel FL framework wherein the lengths of the vectors communicated via both the uplink and downlink independent of the model dimension d.
prohibitively expensive for scenarios requiring low latency.
3.2 ELIMINATING
DEEENNSIN-DEEENENTT COMMUNICATION IN THE UPLINK
The equations 2a 2c are merely a straightforward substitution of the first-order method with
its zeroth-order counterpart. We can further exploit the zeroth-order property to lower the uplink communication cost. worth noting that the random vector zł,- is generated using a pseudo- random number generator. Consequently, given specific seed, zk can be reproduced for a vector of any length. To exploit this property, we can reformulate 2b as
k+1 x irr
= -ngirr Zyp
k = 1,2, ... K,
(Local Update)
(4a)
Fr+1 Cr 71
Rir
(Aggregate Model Update)
(4b)
Cr
iEC,
Two key modifications are introduced here: 1) = becomes z1: 2) Model aggregation is now computed using the model update (i.e., the difference observed during the local update step). The first modification is feasible if all clients agree on one common seed, and this modification paves the way for grouping the g in the second modification. The second modification is crucial to communication because only |C,| Eiec. oirr is unknown the server, which requires the transmission, but this quantity is merely scalar!
With this seemingly minor adjustment, we significantly reduce the second d-length vector within the uplink, transforming it into small constant quantity. However, this improvement insufficient to achieve dimension- free communication due to the inherent requirements of the pull-model step.
3.3
ELIMINATING DIMENSION- DEEENONE COMMUNICATION IN THE DOWNLINK
The challenge remains to eliminate the full model transfer that occurs during the pull-model step in The solution is similar to the modification model update in (4b), albeit with greater subtlety. Presuming that the client model æK is the same as the server model æ,,, where r' is the last participated round, then the process of pulling the model from the server at the r-th round can be expressed as
(2a.
K
x j.r = c E.r'
(Reconstruct Model)
(5)
j=r 1=1
4

---

Published as a conference paper at ICLR 2025
where 04 16.1 Diec, 9h, is the average gradient scalar. A crucial observation is that, at the end of the local update, the client model "; deviates from the server model in equation (4b). This discrepancy poses problem because our approach relies on communicating the gradient via scalar values instead of directly transmitting the updated model. One straightforward solution is to take snapshot of the client model at the beginning of the local update and revert it after the local update is completed. This ensures consistency because, as implied by equation (5). the client model air at the beginning of the local update identical to the server model E,,-
The data communicated between the server and clients in (5) is reduced to just few gradient scalars and random seeds, achieving dimension-free again! We refer to this step as "Reconstruct Model" rather than "Pull Model" because it builds the model based on the local model instead of the server model. In fact, due to this, we do not even need the server model Z, to be stored on the server.
3.4 DECOMFL ALGORITHM
Algorithm Dimension Communication in Federated Learning (DeComFL) [Server-side]
I: Initialize: (90 K=1. learning rate y, local update steps K, communication rounds R.
2: Allocate: memory for recording three states: 1) state set {4.] storing the last round that client i participated in, seed set {{s 1k=1 1
) 3) gradient set (g 1 R-1
4: for r- 0, 1,.... R 1 do
5: Uniformly sample client set C, with cardinality m and sample K seeds {st] for each client i E C, in parallel do ClientRebuiddMode(( ((g)) & ) ( 1/ 1 LocalUpt [km1,,)))
6:
Send and to client
8:
b Send to client and receive
9:
end for
10: Compute the global gradient scalars {o |
{
Fir
IEC,
km1
11: Store { /k=1 and 1 K and update the client's last update record f, =r
12:
Ex= 1 k= 3
D This step is optional.
13:
end for
Algorithm 2 Dimension-Frie Free Communication Federated Learning (DeComFL.) [Client-side]
1: Initialize: maintain local model æt,o and standby until the following procedures triggered by server. Wi )
2: procedure 1. ClientRebuildMMdelll 3: for = ......, 1 do
Equivalent to Pull-model step.
4: for k= 11=1,-. 1...., K do
Generate x NO0, La) by random seed s,..
6:
k+1 xi n1 2 ",,r"
vf,,, is the local model.
7: end for
8: end for
9:
end procedure
10:
procedure 2. CliemtZOO..caUUudaa(((++)
r)
Can be replaced by other ZO methods.
12: for k 11....... K do
13:
Generate 2 N(00, Ia) by random seed s/
14:
oir- = [f ( + uzt Ehr,) f((xfir:
Forward difference style > Standard ZO-SGD
15:
w.th at, ngt..
16:
end for
17:
revert the local model back to z!,- K )K
This step is crucial.
18: Return
19:
end procedure
With the mathematical groundwork established, algorithm. A comprehensive deseription is provided in Algorithm (from the server's 's perspective) and Algorithm 2 (from the client's perspective), with high-level illustration depicted in Fig. [
prepared to present the DeComFL
As shown in the Algorithm tables, DeComFL deviates significantly from the traditional FL framework. We transform the standard three-step process (pulling, local update, and aggregation) new three-
5

---

Published as a conference paper at ICLR 2025
Server
Secds
[Optional)
Never share server model clients
Opt
[S]
Avg Grae
Lest updares clients
[s]
t:
Client Sampling
CientfcbuildWWddellsss
Client
Client (idle)
Client (idle)
Client
20 Opt.
model
oyc
model
Zo
model
20
Opt
model
Data
Data
Data
Data
reseet
Figure I: Illustration of DeComFL. and Components Used in the Server and Clients.
reconstructing, local update with revert, and global aggregate of gradient scalars. This revised framework necessitates several additional details to ensure the implementation of the algorithm in practice. To highlight few:
step approach:
a) Allocation (Line 2 in Alg. TD: The server is required to maintain some states keep track of the client's s last participation round, gradient scalar history and random seeds.
b) Seed Generation: Server samples K integers from uniform distribution and then sends them to the clients for the base seeds to generate random vectors.
c) ClientRehuildModel (Lines 2-9 in Alg. 2 Assume that the current round is r-th round. Before executing the local update procedure, sampled clients need to reconstruct their own model because they may not participate in training in the (r 1)-th round. Hence, the clients need to fill the gap in the model update between the current round and the last round where they participate the training. is corresponding equation (5)
d) ClientZOLocalUpddee
(Lines 11-19 in Alg. 2 After each sampled client finishes rebuilding its model, local updates begin. Specifically, the client uses shared random seeds sent by the server to generate perturbations for each local update. Each perturbation is used for one corresponding local update. Then, they execute local update steps for K times train their own local models by ZOO algorithms (e.g.. ZO-SGD). Finally, they revert the model as discussed in Sec. 3.3 and send scalars (of, KK k=
back to the server. It is corresponding to equation (4a).
We emphasize that all information transmitted between the client and server consists of a few scalars and random seeds, representing "Dimension-Fie Free" for DeComFI.. For clarity, we only present the simplest case of DeComFL. the main paper. For instance, the presented algorithm uses a single perturbation vector. Extending to incorporate multiple perturbation vectors is straightforward, which is listed in Appendix [.44 All subsequent theorems and experiments are based on this multi- perturbation version. Moreover, and extended into several variants. We defer this to Appendix
algorithmic framework, DeComFL can be readily improved
CONVERGENCE AND COMMUNICATION COST ANALYSIS
4.1 CONVERGENCE ANALYSIS
This section presents the convergence rate of DeComFL under standard assumptions and the additional low effective rank assumption. Due to limited space, all proofs are deferred to Appendix D First, we which are commonly used in the existing literature.
list the following standard assumptions 2
Assumption (Unbiased Stochastic Gradient with Bounded Variance) For any 2 1, we have
V ft( = fx(,), and E [|V (f.(2))) of, Vi.
Assumption (Bounded Gradient Dissimilarity) For any E [M], [[) - S 066-

---

Published as a conference paper at ICLR 2025
Assumption (L-Lipschitz Continuous Gradient) f C (R"), i.e. is continuous and differ- entiable in first order and satisfies L-mootth condition:
[V)()) V - -| x vll Vx, E R
The convergence bound of DeComFI. under the above standard assumptions is as follows:
Theorem (Standard Convergence Bound of DeComFL) Under Assumptions and 3 us-
ing Gaussian perturbations z, N(0, Ia), and if 1 S min 24l(d+4)) mKL(d+P+4) m
mP
m. P(
the sequence of iterates generated by DeComFL satssfesstissiess:
3m (d+3)) ((43)))
R-1 M
4D KRn +
24(d+4)Lm (T2KLL
(22KL
(6L(d+4)m 0² (d mP
OG
m
mP
where = [(x)) [(x=), Dr is the model parameter in the r-th round, P is the number of perturbations, I [(x²) the optimal loss value, K is the number of local update steps, R is the number of communication rounds, d is the dimension of model parameters, and m is the number of sampled clients in each round.
Remark The right side of the bound in Theorem I comprises terms with distinct interpretations.
The first term represents the decrease in the loss value the initial point, the second term quantifies the impact of data heterogeneity, the third term arises from the stochastic gradient estimate, and the finite difference approximation introduces the fourth that is often negligible since μ is typically very small. The crucial terms are the middle two, depending on the dimension of the model parameters.
Corollary (Standard Convergence Rate of DeComFL) Further, based on Theorem that μ < (d43)/PKR and f = when the algorithm runs with sufficient large communication round R.
! supposing da the convergence rate of DeComFL is VmPKR
VmPP
VaRK
Remark 2 Both the number of local updates, K, and the number of perturbations, P, appear in the denominator the final convergence rate, indicating a linear speedup with increasing client numbers and local steps. However, these parameters have opposing effects the learning rate. A larger number of perturbations allows for a larger learning rate, while a larger number of local updates necessitates a smaller learning rate. This is intuitive, more perturbations reduce variance between clients, while more local updates increase the dissimilarity between client models.
The above corollary shows that the convergence rate of the ZO method, unfortunately. depends on the model dimension. However, recent research has shown that many deep learning models with ZO optimizers exhibit faster trainingffine-tningg process than the pessimistic cimension-dependee as we established in the previous theorem. One convincing reason is that several prior studies have demonstrated that the Hessian of the loss function for deep neural networks trained using stochastic gradient descent cxhibits a remarkably low effective rank (Papyan 2020; Yao et al. 2020; Wu et al.) 2020). Inspired by this observation, tighter convergence bound related to the low effective rank can be established rather than one based on the model dimension. To achieve this, we adapt Assumption 1 regarding low effective rank from (Malladi et al. 2023) for the FL setting.
rate,
Assumption 4 (Low x-Effective Rank) Let G(x,) max; max (x,, There ists a Hessian matrix Hxx,) < L La such that:
For all a such that ||ær æx S 2ndGG(xr), we have V25(x) - H(x,).
The effective rank of H(x,), i.e., [[(
(r(H(x,)) is at most k.
Based on this low effective rank assumption, we obtain the convergence bound that relies on the effective rank x only, that is, independent of the dimension the model parameter d. We restrict the theoretical analysis regarding the low effective rank assumption to the case where K = 1 only. This does not significantly limit the applicability our findings, as the communication cost per round in algorithm scales linearly with K, whereas in typical FL. algorithms, this cost is independent of K.
7

---

Published as a conference paper at ICLR 2025
Thus, the communication savings achieved by local update techniques are less pronounced in our context. Further, we assume that 2i, is sampled from sphere with radius vd and the Gaussian case listed the Appendix D.5
Theorem (Convergence of DeComFL with x-Effective Rank) Under assumptions 7 and supposing y S II (1
ad+d-2 Pla+2]
and drawing z from unit ball with radius vd, holds
4D
2 (1
kd d -2 P(d + 2) (o) +²0
1 L aodd+33- 3)s 4
E [
Rn +
2
m
where = fxx0) - f(x*). Selecting 17 =
ymmP) ( and μ Vxll
we can obtain
MRRP V Ad4-333'
R-1 [[
VI (VMRP)
+0
(
(
VmRp)
VE
)
(o + +
(6)
R
Further supposing R > P. the convergence rate is O
Vi
when round R. is sufficient large.
/mitf
To the best of our knowledge, we are the first to quantify the impact of the smoothness parameter y the context low-effective rank analysis. Previous proofs, such as the proof in (Malladi et al.) 2023), adopt the unrealistic condition that μ O, resulting in convergence rate devoid of any terms related to μ.. With our correction, the convergence rate established above is quite similar compared with Corollary with the key difference being the replacement of the dimension d with the effective rank k. This distinction is crucial because x is typically far smaller than the model dimension d, particularly in LLMs where d can be several orders of magnitude larger than Unfortunately, like the Lipschitz constant, determining the exact value of x is challenging and computationally prohibitive. However, as we will demonstrate in the following experiment section, only few thousand rounds are sufficient to train or fine-tune models with millions or even billions of parameters.
Remark 3 Furthermore, we note that FedMeZO (Ling et al., 2024) claims to demonstrate the applicability of the low effective rank assumption federated learning with multiple local updates. However, their proof contains critical error: the sign of Ti in equation (16) is incorrectly handled, leading to a reversal of the inequality's direction.
4.2 COMMUNICATION COST ANALYSIS
We compare the communication cost of DeComFL with three representative FL algorithms: FedAvg, FedZO and FedCom. Each baseline highlights a different aspect of DeComFL. FedAvg. the most classic FL. algorithm, operates in the same multi-agent setup. Fed7O, employing 70-SGD as its optimizer, matches our Z00 techniques. FedCom, focusing on compression techniques, offers comparison point for DeComFL's 's seed and gradient scalar compression strategy.
Table 1: Comparison of Total Communication Complexity of Typical Algorithms
Uplink Comm. Downlink Comm. Per Round
Round Complexity
Uplink Comm. Complexity
Downlink Comm. Complexity
Algorithm
Per Round
FedAvg
md
md. md md
<mka> mPK
O Kez
Ke da P Bd Kez
FedZO
md
O
PK
FedCom
3md
O Ke
mkee
Ours (Standard)
mKP P
2MM K P
0 (
Md
mPKe
Ours (Low rank)
mP
2M
mPP
my
Having established the round complexity in the preceding theorems, can determine the total communication cost to reach an e-approximate solution by calculating the per-round communication cost. Unlike typical FI. algorithms, the number of scalars communicated per round in DeComFL. is
8

---

Published as a conference paper at ICLR 2025
non-deterministic, depending on the lagged history of each client. Specifically, for the "reconstruct model" step (downlink communication), the transmitted vector has a length of 2m P x h, where the factor of 2 accounts for both the seeds and gradient scalars, and h denotes the (potentially random) length of lagged rounds. However, we know that by the Rh-th round, sampled client must have communicated 2RK P scalars with the server reconstruct its model since the beginning. Therefore, on average, 2.M K P scalars per round are communicated between the server and all M clients. For the "local update" step (uplink communication), the returned vector length is always fixed mKP., corresponding to K local updates with P gradient scalars per update for each of the m clients.
We summarize the communication complexity in Table Besides FedAvg, we compare against FedCom (Haddadpour et al., (02T). which can be understood as FedAvg with generic compression operation in the communication. In the table, we use 3 E (0, 1] to represent the compression ratio, and we further assume the order of the round complexity is not impacted. As we can clearly see in the table, the communication cost of all other algorithms has linear, even quadratic, dependency on the mnd model dimension d. Under the low effective-rank scenario, if < MK the theorem indicates that DeComFL can converge much faster than the first-order FL counterparts regarding the communication cost. Estimating the effective low rank Æ. in the pure theoretical domain is hard, similar to the Lipschitz constant L. Based on the results of the numerical experiment shown in the next section, should be safe say that the effective low rank should be much smaller than the total dimensions of the model.
5 EXPERIMENTS
Our experiment results firstly echo our theoretical conclusion that using larger perturbation amount P and local update steps K can make DeComFL converge faster (refer to Table T.. More importantly, experiment results clearly highlight that DeComFL achieves enormous savings in communication overhead in training and especially fine-tuning tasks in LLMs, compared to other basclines.
We begin by training simple Convolutional Neural Network model from scratch the MNIST image classification task (LeCun et al.] 1998). In the training tasks, our FL system comprises 100 clients, and partition the dataset into 100 subsets by Dirichlet distribution (i.e., 1). Each subset is assigned to one sampled client. In each communication round, 10% clients are randomly selected to participate in the training process.
0.35
0.54
0.92
0.30
Defutbatione (Peffomarce Curve)
local updioce11 DuCanFFust!!
Perturatioon10 (Pec) Accurces)
[scall upidere DeComd Limeent
0.88
Reluabbdion-10 (NN fammaam Carve)
loca Lip0000-d DcConFLisdt
Perturbation20 (Rhcl Accurors)
0.66
local 10 (mclmmll/mman))
0.8-
Pertrratton--u (Nutoomance Curve)
local 1p DeComFlisist)
Perturbationedo 40 (Piul Accurats)
local upcasc- Fookeg
0.4
local upcatt-4 loski3
10 restive
tedhug
0.82
100000
20000C
50300
10000C
31000n
200000
Communicatio
Longth
Length
Figure 2: Ablation study of the influence of the number of local updates and perturbations on DeComFL. The communication vector length is the count of accumulated scalars transmitted between the server and a client.
DeComFLL largely reduces communication costs in training tasks. Figure 2 is plotted based on the average communication vector length that transferred between a client and the server. In the figure, we just compared DeComFL with the classical FedAvg as the corresponding first-order algorithm. All algorithms use SGD optimizer with momentum 0.5. For DeComFL, we set the base learning rate as 0.001. The figure clearly shows DeComFL'ss 's substantial communication cost savings, even for the small CNN model containing only 28,938 parameters. (Note: FedAvg has not converged yet).
Increasing P can enhance FL's performance. Moreover, we can observe in Figure 2 that the larger number of perturbations eventually leads to higher test accuracy, which is more influential than local update, while slightly slowing down the algorithm at the beginning. Hence, we further evaluate this perturbation trick on Fashion (Xiao et al. 2017) with a larger CNN model (1,206,590 parameters). Like the learning rate scheduler, 500, 1000, and 2000. Other settings are the same as MNIST. Besides FedAvg. we compare it against FedCom (Haddadpour et al. 2021) (using quantization) and FedAvg+Top Ik (uploading the largest k
use 25 perturbations at the beginning and double it rounds

---

Published as a conference paper at ICLR 2025
3.00
1.75
3.0
Tost Accurary
2.95
1.00
50
200
0.50
2.05
DeComfL
Tedlrg Took Pedffom
Feakig topk
3.60
Redtom
0.00
1200
1400
Rounds
Communcation Vecter
106
Figure 3: Comparison of Multiple FL Algorithms on the Fashion Dataset.
elements of the local update difference). We set k=10% parameters, and the quantization used in FedCom is compressing each element in the parameters to 8 bits. The left plot in Figure 3 shows loss against communication rounds. DeComFL converges slower than the first-order methods, except for Top k, which is expected due to the inherent slower convergence of ZO methods. However, the slowness not by the factor as the standard theorem established and supports the low effective-rank assumption. The right plot, illustrating test accuracy against effective communication vector length, reveals a different trend. DoComFL achieves higher performance with larger perturbations, while the communicated vector lengths are still significantly smaller than other algorithmss
DeComFL can achieve tremendous communication savings LLM fine-tuning tasks. To further verify the DeComFL's effectiveness LLMs, we execute fine-ture tuning tasks series of NLP The models we used are OPT- 125M and OPT-1.3B (Zhang et al. 2022). Due to the size of the model, we sample 2 clients from 8 clients participate each round illustrate the concept. In Table 2 we compare DeComFL. with P 10 against MeZO (single agent setting) and FedZO (multi-agent setting, P 10) fine-tuning baselines. All parameter settings and the definition of tasks are described in Sec. C.I the appendix. Although the number of rounds required for DeComFL convergence varies across different tasks (sce appendix for details), the convergence consistently occurs within thousands of rounds, significantly fewer than the model's billions of dimensions and only slightly greater than that of first-order counterparts. This observation supports our low effective-rank assumption. The tables clearly demonstrate that DeComFL can match even excel MeZO's performance. When using the same P. the performances DeComFL and FedZO almost the same, but the communication cost of DeComFL is dramatically lower than the of FedZO. Lastly, the most important observation is that the communication costs for both model sizes nearly identical, highlighting the dimension free communication achieved by DeComFL.
datasets" [1
Table 2: Test Accuracy and Communication Cost on Fine-Tuning Tasks
Model
Dataset \ Task
FedAvg
MeZO
FedZO with P 10
DeComFL with P 10
SST-2
87.32% (0.24 TB
83,99%
84.11% (0.75 TB)
85.08% (0.36 MB)
CB
82.14% (0.12 TB)
72.49%
74.41%
(0.38 TB)
75.00% (0.12 MB)
WSC
63.25% (0.12 TB)
55.18%
59.47%
(0.75 TB)
59.59% (0.36 MB)
125-
WIC
60.83% (0.12 TB)
53.25%
53.37%
(0.75 TB)
53.38% (0.36 MB)
RTE
63.96% (0.48 TB)
52.91%
54.16%
(0,50 TB)
57.05% (0.24 MB)
BoolQ
62.34% (0.24 TB)
61.46%
61.25% (0.50 TB)
61.60% (0.24 MB)
SST-2
90.3% (1.27 TB)
90.23%
90.33% (5.20 TB)
90.78% (0.24 MB)
CB
83.93% (1.27 TB)
74.01%
74.49%
(7.80 TB)
75.71% (0.36 MB)
WSC
65.65% (1.27 TB)
58.21%
61.11% (7.80 TB)
64.16% (0.36 MB)
OPT-1.3B
WIC
65.82% (1.27 TB)
55.95%
56.08% (5.20 TB)
56.14% (0.24 MB)
RTE
66.13% (2.54 TB)
57.57%
59.21% (3,90 TB)
60.89% (1.80 MB)
BoolQ
63.83% (5.08 TB)
61.98%
62.14% (3.90 TB)
62.50% (1.80 MB)
1I "oadding and splitting datasets are based on htt.htppee//gggggiiaaaa...e/ee/e wttaaaeee..etttteee//aaaaaa / "The value enclosed in parentheses represents the total bytes of the vector transferred hetween the server and
ve
single client throughout the entire fine-tuning phase. TB 1,000,000 MB
10

---

Published as a conference paper at ICLR 2025
ACKNOWLEDGMENTS
We sincerely thank Ms. Yidan(Julie) Huang from Google and Mr. Ziqi Zhou from RIT for their help and support in this work. This work has been partially supported by Al Seed Funding and the GWBC Award RIT.
REFERENCES
Jeremy Bernstein, Yu-Xiang Wang. Kamyar Azizzadenesheli, and Animashree Anandkumar. signsgd: Com- pressed optimisation for non-convex problems. In International Conference on Machine Learning, pp- 560-569. PMIR, 2018.
Rishi Bommasani, Drew A Hudson, Ehsan Adeli, Russ Altman, Simran Arora, Sydney von Arx, Michael S Bernstein, Jeannette Bohg, Antoine Bosselut, Emma Brunskill, et al. On the opportunities and risks of foundation models. arXiv preprint arXiv:2108.07255: 2021.
Pavios S Bouzinis, Panagiotis D Diamantoulakis, and George K. Karagiannidis. Wireless quantized federated learning: a joint computation and communication design. IEEE Transactions on Communications, 2023.
Samuel R Bowman, Gabor Angeli, Christopher Potts, and Christopher D Manning. A large annotated corpus for learning natural language inference. arXiv preprint 1oXiv:1508.05326. 2015.
Tom Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared D Kaplan, Prafulla Dhariwal, Arvind Neclakantan, Pranav Shyam, Girish Sastry, Amanda Askell, et al. Language models are few-shot learners. Advances neural information processing systems, 33:1877-1901, 2020.
HanQin Cai, Yuchen Lou, Daniel McKenzie, and Wotao Yin. A zeroth-order block coordinate descent algorithm for huge-scale black-box optimization. In International Conference on Machine Learning, pp. 1193-1203. PMLR, 2021.
Aochuan Chen, Yimeng Zhang. Jinghan Jia, James Diffenderfer, Jiancheng Liu, Konstantinos Parasyris, Yihua Zhang, Zheng Zhang, Bhavya Kailkhura, and Sijia Liu. Deepzero: Scaling up zeroth-order optimization for deep model training, arXiv preprint arXiv:2310.02035 2023.
Xiangyi Chen. Sijia Liu, Kaidi Xu, Xingguo Li. Xue Lin. Mingyi Hong. and David Cox. Zo- Zo-adamm: Zeroth- order adaptive momentum method for black-box box optimization. Advances in neural information processing systems, 32, 2019.
Christopher Clark, Kenton Lee, Ming-Wos Wei Chang, Tom Kwiatkowski, Michael Collins, and Kristina Toutanova. Boolq: Exploring the surprising difficulty of natural yes/no questions. In NAACL, 2019.
Maric- Carii-Catherine Marneffe, Mandy Simons, and Judith Tonhauser. The CommitmentBank: Investigating projection in naturally occurring discourse. 2019. To appear in proceedings of Sinn und Bedeutung 23. Data can be found at https://gihuu..omm// www.///nwn/oomminennnaaa.ae
John Duchi, Michael Jordan, Martin J Wainwright, and Andre Wibisono. Optimal rates for zero-order convex optimization: The power of two function evaluations. IEEE Transactions on Information Theory, 61(5): 2788-2806, 2015.
Wenzhi Fang, Ziyi Yu, Yuning Jiang, Yuanming Shi, Colin N Jones, and Yong Zhou. Communication efficieen stochastic zeroth-order optimization for federated learning. IEEE Transactions Signal Processing, 70: 5058-5573, 2022.
Haozhe Feng, Tianyu Pang, Chao Du, Wei Chen, Shuicheng Yan, and Min Lin. Does federated learning really need backpropagation? arXiv preprint arX1v:2301.12195. 2023.
Saeed Ghadimi and Guanghui Lan. Stochastic first-and zeroth-order methods for nonconvex stochastic program- ming. SIAM Journal on Optimization, (3(4))2341-2366 2013.
Behrooz Ghorbani, Shankar Krishnan, and Ying Xiao. An investigation into neural net optimization via hessian eigenvalue density. In International Conference Machine Learning, pp.
PMLR, 2019.
Gene H Golub and John H Welsch. Calculation of gauss quadrature rules. Mathematics of computation, 23(106): 221-230. 1969.
Farzin Haddadpour, Mohammad Mahdi Kamani, Aryan Mokhtari, and Mehrdad Mahdavi. Federated learning with compression: Unified analysis and sharp guarantees. In International Conference on Artificial Intelligence and Statistics, pp. 2350-2358. PMLR, 2021.
11

---

Published as a conference paper at ICLR 2025
Pengchao Han, Shiqiang Wang, and Kin K Leung. Adaptive gradient sparsification for efficient federated leamiigg online learning approach. In 2020 IEEE 40th international conference on distributed compuring systems (ICDCS), pp. 300-310, IEEE, 2020.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 770-778, 2016.
Robert Hönig, Yiren Zhao, and Robert Mullins, Dadaquant: Doubly-adaptive quantization for communication- efficient federated learning. In International Conference on Machine Learning, pp. 8852 8866. PMLR, 2022.
Edward J Hu, Yelong Shen, Phillip Wallis, Zeyuan Allen-Zhu, Yuanzhi Li. Shean Wang. Lu Wang. and Weizhu Chen. Lora: Low-rank adaptation of large language models, arXiv preprini arXiv:2106.0966 2021.
Xinmeng Huang, Ping Li, and Xiaoyun Li. Stochastic controlled averaging for federated learning with commu- nication compression. arXiv preprint vrXiv:238.00106 2023.
Divyansh Jhunjhunwala, Advait Gadhikar, Gauri Joshi, and Yonina Eldar. Adaptive quantization of model updates communication-effiicee federated learning. ICASSP 2021-2021 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP). pp. 3110-3114. IEEE, 2021.
Gangshan Jing. He Bai, Jemin George, Aranya Chakrabortty, and Piyush Sharma. Asynchronous distributed reinforcement learning for lqr control via zeroth-order block coordinate descent. IEFF Transactions on Automatic Control, 2024.
Peter Kairouz, Н Brendan McMahan, Brendan Avent, Aurélien Bellet, Mehdi Bennis, Arjun Nitin Bhagoji, Kallista Bonawitz, Zachary Charles, Graham Cormode, Rachel Cummings, ct al. Advances and open problems federated learning. Foundations and Trends@ Machine Learning, 14(1-2):1
2021.
Sai Praneeth Karimireddy, Satyen Kalc, Mehryar Mohri, Sashank Reddi, Schastian Stich, and Ananda Theertha Suresh. Scaffold: Stochastic controlled averaging for federated learning. In International conference on machine learming. pp. 5132-5143. PMLR, 2020.
Vid Kocijan, Thomas Lukasiewicz, Ernest Davis, Gary Marcus, and Leora Morgenstem. A review of winograd schema challenge datasets and approaches. arXiv preprint 2KKV::2004.38331 2020.
Yann LeCun, Léon Bottou, Yoshua Bengio, and Patrick Haffner. Gradient-based learning applied to document recognition. Proceedings of the IEEE, 86(1 1):2278 2324, 1998.
Shiqi Li, Qi Qi. Jingyu Wang, Haifeng Sun, Yujian Li, and F Richard Yu. Ggs: General gradient sparsification for federated learning in edge computing. In ICC 2020-2020 IEEE International Conference on Communications (ICC). pp. 1-7. IEEE, 2020.
Xiang Lisa Li and Perey Liang. Prefix-tuning: Optimizing continuous prompts for generation. arXiv preprint arXiv:2101.00190 2021.
Xiaoyun Li and Ping Li. Analysis of error feedback in federated non-convex optimization with biased com- pression: Fast convergence and partial participation. International Conference on Machine Learning, pp- 19638-19688. PMLR, 2023.
Yingying Li, Yujie Tang. Runyu Zhang, and Na Li. Distributed reinforcement learning for decentralized linear quadratic control: A derivative-free policy optimization approach. IEEE Transactions on Automatic Control, 67(12):6429 6444, 2021.
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, pp. 1827-1838. 2024.
Heting Liu, Fang He, and Guohong Cao. Communication-efficn federated learning for heterogeneous edge devices based on adaptive gradient quantization. In IEEE INFOCOM 2023-IEEE Conference on Computer Commanications, pp. 1-10. IEEF, 2023.
Sijia Liu, Pin- Yu Chen, Xiangyi Chen, and Mingyi Hong. signsgd via zeroth-order oracle. In International Conference on Learning Representations, 201 Sa.
Sijia Liu, Bhavya Kailkhura, Pin- Yu Chen, Paishun Ting, Shiyu Chang, and Lisa Amini. Zeroth- stochastic variance reduction for nonconvex optimization. Advances in Neural Information Processing Systems, 31, 2018b.
12

---

Published as a conference paper at ICLR 2025
Sijia Liu,, Pin-Yu Chen, Bhavya Kailkhura, Gaoyuan Zhang, Alfred Hero III. and Pramod K Varshney. primer zeroth-order optimization in signal processing and machine learning: Principals, recent advances, and applications. IEEE Signal Processing Magazine, 37(5):43-55 54, 2020.
Zhuang Liu, Mingjie Sun, Tinghui Zhou, Gao Huang. and Trevor Darrell, Rethinking the value of network pruning. arXiv preprint arXiv: 100.00527, 2018c.
Sadhika Malladi, Tianyu Gao, Eshaan Nichani, Alex Damian, Jason Lec, Danqi Chen, and Sanjeev Arora. Fine-tuning language models with just forward passes. Advances Neural Information Processing Systems, 36:53038-53075, 2023.
Charles H Martin and Michael W Mahoney, Implicit seff-regularization in deep neural networks: Evidence from random matrix theory and implications for learning. Journal of Machine Learning Research, 22(165):1-73, 2021.
Brendan McMahan, Fider Moore, Daniel Ramage, Seth Hampson, and Blaise Aguera y Arcas. Communication- efficient learning of deep networks from decentralized data. In Artificial intelligence and statistics, pp. 1273-1282. PMLR, 2017.
Yurii Nesterov. Introductory lectures convex optimizaaion: A basic course, volume 87. Springer Science & Business Media, 2013.
Yurii Nesterov and Vladimir Spokoiny. Random gradient-free minimization of convex functions. Foundations of Computational Mathematics, 17:527-566, 2017.
Dinh C Nguyen, Ming Ding, Quoc-Vies Viet Pham, Pubudu N Pathirana, Long Bao Le. Aruna Seneviratne, Jun Li, Dusit Niyato, and H Vincent Poor. Federated learning meets blockchain in edge computing: Opportunities and challenges. IEEE Internet of Things Journal, 8(16):12806-1233 2021.
Konstantinos Nikolakakis, Farzin Haddadpour, Dionysis Kalogerias, and Amin Karbasi. Black- box generaliza- tion: Stability of zeroth-order learning. Advances in Neural Information Processing Systems, 35:31525-31 -1541,, 2022.
Emre Ozfatura, Kerem Ozfatura, and Deniz Gündüz. Time-correlated sparsification for communication-ccficienn federated learning. In 2021 IEEE International Symposium on Information Theory (ISIT), pp. 461 1664 IEEE, 2021.
Vardan Papyan. The full spectrum of deepnet hessians at scale: Dynamics with sgd training and sample size. arXiv preprint arXiv: /8/ 1,07022, 2018.
Vardan Papyan. Traces class/cross-class structure pervade deep learning spectra. Journal of Machine Learning Research, 21(252) 2020.
Mohammad Taher Pilehvar and Jose Camacho-Collados. Wie: the word-in-context dataset for evaluating context-sensitive meaning representations. arXiv preprint arXiv:/808.09122 091211 2018. 2018.
Amirhossein Reisizadeh, Aryan Mokhtari, Hamed Hassami, Ali Jadbabaic, and Ramtin Pedarsani. Fedpaq: Communication-efficii federated learning method with periodic averaging and quantization. In International conference artificial intelligence and statistics, pp. 2021-2031. PMLR, 2020.
Monica Ribero and Haris Vikalo. Communication-efliiienn federated learning via optimal client sampling. arXiv preprint wxXiv:2007.15997 2020.
Shaohuai Shi, Xiaowen Chu, Ka Chun Cheung, and Simon See. Understanding top-k sparsification in distributed deep learning. arXiv preprint 191.v: 11.87777 2019.
Nir Shlezinger, Mingzhe Chen, Yonina C Eldar, H Vincent Poor, and Shuguang Cui. Federated learning with quantization constraints. In ICASSP 2020-2020 JEEE International Conference on Acoustics. Speech and Signal Processing (ICASSP), pp. 8851-8855. IEER, 2020.
Richard Socher, Alex Perelygin, Jean Wu, Jason Chuang, Christopher D Manning, Andrew Y Ng. and Christopher sentiment treebank. In Proceedings of the
Potts. Recursive deep models for semantic compositionality 2013 conference on empirical methods natural language processing, pp. 1631-1642, 2013.
James C Spall. Multivariate stochastic approximation using simultancous perturbation gradient approximation.
IEEE transactions on automatic control, 37(3):332-31) 3411, 1992.
Schastian U Stich, Jcan-Baptiste Cordonnier, and Martin Jaggi. Sparsified sgd with memory. Advances in neural information processing systems, 31, 2018.
13

---

Published as a conference paper at ICLR 2025
Zhenheng Tang, Shaohuai Shi, Bo Li, and Xiaowen Chu. Gossipfl: decentralized federated learning framework with sparsified and adaptive communication, IEEE Transactions on Parallel and Distributed Systems, 34(3): 909-922, 2022.
Thijs Vogels, Sai Praneeth Karimireddy, and Martin Jaggi. Powersgd: Practical low-rank gradient compression for distributed optimization. Advances in Neural Information Processing Systems, 32, 2019.
Alex Wang, Amanpreet Singh, Julian Michael, Felix Hill, Omer Levy, Samuel R Bowman. Glue: A multi- task benchmark and analysis platform for natural language understanding. arXiv preprint 2018.
Bin Wang, Jun Fang, Hongbin Li, and Bing Zeng. Communication-cffiisie federated learning: A variance- reduced stochastic approach with adaptive sparsification. IEEE Transactions on Signal Processing, 2023a.
Jianyu Wang, Zachary Charles, Zheng Xu, Gauri Joshi, H Brendan McMahan, Maruan Al-Shedivat, Galen Andrew, Salman Avestimehr, Katharine Daly, Deepesh Data, et al. A field guide to federated optimization. arXiv preprint 20t.::2177.6991 2021.
Jue Wang. Yucheng Lu, Binhang Yuan, Beidi Chen, Percy Liang, Christopher De Sa, Christopher Rc, and Ce Zhang. Cocktailsgd: Fine-tuning foundation models over 500mbps networks. In International Conference on Machine Learning, pp. 36058-36076. PMLR, 2023b.
Yujia Wang, Lu Lin, and Jinghui Chen. Commuuication-cfficcce adaptive federated learning. In International Conference on Machine Learning, pp. 22802-22885 PMLR, 2022.
Yikai Wu, Xingyu Zhu, Chenwei Wu, Annie Wang, and Rong Ge. Dissecting hessian: Understanding common structure of hessian in neural networks. arXiv preprint arX1v:2010.04261, 2020.
Han Xiao, Kashif Rasul, and Roland Vollgraf. fashion-mmist novel image dataset for benchmarking machine learning algorithms. arXiv preprint 170::170,,,7777, 2017.
Jie Xu, Benjamin S Glicksberg. Chang Su, Peter Walker. Jiang Bian, and Fei Wang. Federated learning for hcalthcare informatics. Journal of healthcare informatics research, 5:1-19, 2021.
Haibo Yang. Jia Liu, and Elizabeth S Bentley. Cfodavg:
achieving efficient communication and fast convergence in non iid federated learning. 2021 19th International Symposium on Modeling and Optimization Mobile, Ad hoc, and Wireless Networks (WiOpt). pp- 1-8. IEFF, 2021.
Zhewei Yao, Amir Gholami, Kurt Keutzer, and Michael W Mahoney. Pyhessian: Neural networks through the lens of the hessian. In 2020 IEEE international conference on big data (Big data), pp. 581-590. IEEE, 2020.
Kai Yi. Georg Meinhardt, Laurent Condat, and Peter Richtárik. Fedcomloc: Communication efficient distributed training sparse and quantized models. arXiv preprint arXiv:2403. 09904, 2024.
Pengyun Yue, Hanzhen Zhao, Cong Fang, Di He, Liwei Wang, Zhouchen Lin, and Song- chun Zhu. Core: Common random reconstruction for distributed optimization with provable low communication complexity. arXiv preprint arXiv:2309. 13307, 2023.
Hossein Zakerinia, Shayan Talaci, Giorgi Nadiradze, and Dan Alistarh. caammunication-effiican federated learning with data and client heterogeneity. In International Conference on Artificial Intelligence and Statistics, pp. 3448-3456. PMLR, 2024.
Susan Zhang, Stephen Roller, Naman Goyal, Mikel Artetxe, Moya Chen, Shuohui Chen, Christopher Dewan, Mona Diah, Xian Li, Xi Victoria Lin, et al. Opt: Open pre-trained transformer language models. arXiv preprint arXiv:2205.0 2022.
Yihua Zhang. Pingzhi Li, Junyuan Hong, Jiaxiang Li, Yimeng Zhang, Wenging Zheng, Pin- Yu Chen, Jason D Lee, Wotao Yin, Mingyi Hong, al. Revisiting zeroth-order optimization for memory-efficiet I1m fine-tuning: benchmark. arXiv preprint arXiv:2402.1 1592, 2024.
Bingchen Zhao, Haoqin Tu, Chen Wei, Jieru Mei, and Cihang Xie. Tuning layernorm in attention: Towards efficient multi- modal 1lm finetuning. arviv preprint arXiv:2312.114222 2023.
14

---

Published as a conference paper at ICLR 2025
A CONCLUSION AND FUTURE WORK
We present DeComFL significantly reducing communication costs in FL, opening new direction for combining FL with the zeroth-order optimization method. Our algorithm requires transmitting only few scalar values, independent of model dimension, in both uplink and downlink communication. Moreover, we rigorously prove that under low-rank assumption, DeComFL achieves convergence rates and total communication costs independent of model dimension a first for theoretical results in federated learning. Empirical evaluations further demonstrate the communication efficiency of DeComFL. in both training and fine-tuning tasks.
limitation of DeComFL. lies in computational cost. Although zeroth-order optimization only re- quires forward passes, the overall computation remains high due to slower convergence. Additionally, this work does not address data heterogeneity issues, a challenge tackled by algorithms like Scaffold for future exploration. Similarly, model pruning (Chen et al. 2023) Liu et al. 2018c) and integration with other optimization algorithms (Liu et al. 2020) may further reduce computational costs in training tasks.
(Karimireddy et al. 2020), which remains
Table 3: Notations in This Paper
Notation
Meaning
d
Total model parameter dimension Number of clients participating in each round Index, total number of clients Index, number communication round Index, number of perturbations Index, number of local update iterations Global model parameters in the r-th round Local model parameters in the k-th iteration and 7-th round client
m
i, M
r,
P
k. K
xr.
at
Data sample used in the k-th iteration and r-th round at client Zeroth-orded gradient estimate scalar
Sir
9
2.
Perturbation the k-th iteration and r-round
f
Global loss function
f
Local loss function at client
C,
Set of clients participating r-th round
B IMPROVEMENTS AND VARIATIONS OF ALGORITHM IMPLEMENTATION
DeComFL discussed the main paper a fairly general framework. In practice, several directions exist to extend and improve the Algorithm
B. IMPROVE THE PERFORMANCE
One well-known issue with ZO methods is that the variance of stochastic gradient introduced by the random perturbation is so significant that takes longer converge and requires a much smaller learning rate than the FO counterparts.
Multiple Perturbations. One common variation in zeroth-order optimization is to use multiple perturbations. Suppose = is Gaussian random vector generated for r-th round, k-thh local update step and p-th perturbation (i.i.d. for any r. p). One step of SGD local update becomes:
P
1-1 2
x 1.r
Σ pml
* rgp where strp 1 (fi(2t; + uxl st..) fi(at, (7)
That is we perturb the model times and calculate P gradient scalars (o.t,p The effective update then becomes weighted average of these perturbations. While using multiple perturbations increases the communication cost linearly with P since all gradient scalars must be transmitted to the server for global aggregation, significantly reduce the variance of the stochastic gradient estimate
15

---

Published as a conference paper at ICLR 2025
and then decrease the required rounds. Also, unlike large memory consumption since we calculate the corresponding gradient scalar p sequentially.
size, this does not increase the
Advanced Optimizers. We can more advanced optimizers to improve the performance or accelerate the algorithm''s 's convergence. For clarity, Algorithm| i based on vanilla ZO-SGD, but should be straightforward to extend to other zeroth-order optimization methods, such as 20-SignSGD (Liu et al.) 2018a), ZO-SVRG (Liu et al. 2018b), ZO-Adam (Chen et al.) 2019), etc. A complete discussion and analysis of these optimizers are beyond the scope of this paper. However, to illustrate the necessary modifications, we present momentum SGD as an example:
m k+1 =Bm k+1 + +1- 2.
(8)
k+1 x..r 11 m.r k+1
(9)
where 3 is a momentum factor between 0 and 1. One pitfall is that the optimizer is no longer stateless like ZO-SGD. Hence, after the local update step, we have to revert both the model parameter x and the optimizer state m K In the model reconstruction step, we maintain the optimizer states and model update at the same time as well.
B.2 DECREASE THE MEMORY CONSUMPTION
Reduce the Memory on the Server Side. A straightforward improvement is that the server longer stores the model if there is no such necessity. This allows the server to function as a simple aggregator of scalar values. In cloud service environment, this translates to utilizing less expensive CPU-only instances instead of costly GPU instances, resulting in substantial cost savings.
In our base algorithm (Algorithm I. the server stores the entire history of selected random seeds and computed gradient scalars, potentially leading to significant memory consumption over many rounds. However, we can optimize this by recognizing that only information from the most recent round of each client is necessary. Since the server tracks each client's 's last updated round, a queue can efficiently manage this history. After clients complete their local updates, the server discards outdated information, minimizing memory usage. Further memory optimization can be achieved by having clients track and send their last participation round to the server, eliminating the need for the server store this information.
Reduce the Memory on the Client Side. One significant memory consumption on the client side is that we have to take snapshot before the local update step. There is an alternative, more memory- efficient solution to ensuring the prerequisite for equation (5) is satisfied namely, that the client model ay at the end of the local update is identical to the server model æ,,, Subtracting (4b) from
(4a
then we get
K
Ix,
x
1.r
(g
(10)
Jom
Since = z after the reconstructing step. the quantity ΣK (g. - -g ) 2 represents the divergence between the local client model and the global server model. By compensating for this divergence, we can synchronize the two models. Crucially, this quantity can be generated using only gradient scalars and random seeds, eliminating the need to store snapshot of the entire model. However, this technique is specific to SGD optimization.
Comparison with FedZO. With the above memory reduction technique, our approach offers signifi- cant memory consumption advantages over FedZO, both on the server and client sides.
Server-Side: Our algorithm can achieve near-zero server memory consumption. By discarding the server-side model and only tracking the latest random seeds and computed gradient scalars, minimize memory usage. In contrast, FedZO requires storing at least two copies of the model (the averaged model and the aggregated update), leading memory peak of at least 2d, where d is the model dimensionality.
Client-Side: Our algorithm requires only + á memory per client, where is for the client model and ő is the largest parameter size from the parameter-wise perturbation (Mallddi et al. 2023). Since
4 is K recursions. We expand the equation from K to before the subtraction.
16

---

Published as a conference paper at ICLR 2025
is typically negligible compared to d, the client-side memory is essentially d. Conversely, FedZO with multiple perturbations necessitates storing the model and intermediate gradients, resulting in a peak memory consumption of 3d (as illustrated in equation 7 We summarized the comparison in the following table.
Table 4: Memory Cost Comparison between FedZO and DeComFL.
Memory Cost FedZO DeComFL
Server
Client
2d
3d
Negligible
R
B.3 OTHERS VARIANTS
Model Pulling for Excessive Lagging If Necessary. If client remains unsampled for extended period, the model-pulling step requires retrieving all historical seeds and gradient scalars to update the model. This can be computationally demanding. In contrast, directly pulling the server's model has a fixed cost regardless of the client's lag time. This introduces trade-off: if a client has limited computational resources and can tolerate communicating full model parameters, might be preferable to pull the server's 's model simply.
Enhanced Privacy through Private Seed Shifting, Data privacy is paramount in FL. While our proposed DeComFI., like other FL algorithms, does not share local raw data with the server, we can further enhance privacy protection by ensuring that the server remains unaware of how the model evolves on the client side. Notice that even without direct access local data, the server could potentially infer some information about local data distribution by comparing model updates between rounds. To address this, we introduce a simple and effective improvement: private shift or function known only to the clients applies to the random seeds. Upon receiving a seed to generate perturbation, the client first applies this private shift function alter the seed. Since this shift is deterministic, is easy to see that this modification does not affect the functionality of our algorithm while it prevents the server from reconstructing the model updates (This shift can be established via another server or a consensus protocol among clients). As a result, the random gradient scalars transmitted the server cannot convey any information about the local data distribution, further enhancing privacy protection.
B.4 DECOMFL WITH P
In Algorithm I andd] 2 in the main paper, we demonstrate DeComFL using one perturbation (P To show that our DeComFL supports multiple perturbations (P > 1), we establish Algorithm and The primary difference between the two cases is the way in which the model is updated.
Algorithm 3 DeComFL (P 1) [Server-side]
I: Initialize: {[ p learning rate n). local update steps K, communication rounds R, the number of
Perturbations P.
2: Allocate: memory for recording three states: 1) state set (4)) storing the last round that client i participated in, 2) seed set (( R-1 gradient set (et(((g)) (
3:
4: for L..., R do
5: Uniformly sample client C, with cardinality and sample P. K seeds (1 each client E parallel do ChientRebiiddMMdde(( - H118 1 18 Me
7:
& Send g, to client
8: (o K = ClientZO1LocalUudaate (s 1 1 Send to client and receive
9:
end for
10: Compute the global gradient scalars = 1
{1
Σ IEC, D 1
Store ((o } 1K and 1r
ik and update the client's update record t, = This step is optional.
12:
Er+1 E. 3 ΣK Ep=r D 2t.p
13:
end for
17

---

Published as a conference paper at ICLR 2025
Algorithm 4 DeComFL (P> [Client-side]
1:
Initialize: maintain local model æ1,0 and standby until the following procedures triggered by server. procedure ClientRebuillMMdde( ((( pp (( k= )
for 1,..... ................................ , 4: for = ,..., do
Equivalent to Pull-model step.
5: for = 1,.... P do
6:
Generate 2,', (0, Ia) by random seed s
This can be on-the-fly style
7:
end for k+1 s,r
w/ DP S -.
Wiy the local model.
9: end for
10: end for
11: end procedure
12:
13: procedure 2. ClennZ/0LoclUUpaacc((1.... 1 1
Can be replaced by other ZO methods.
14: for k 1...., K do
15:
16: for = ....., Po
17:
Generate 2 ~N(0,,)) by random seed sh.p
18:
Dh.n.p = " (fi(xtr pin sh.r) ) - i
Forward difference style
19:
A A + gh.r.p zr.
20:
end for
21: T..
2x, #4
22:
end for
23:
revert the local model back to =!...
b. This step is crucial.
24: Return ((gh,r b
25:
end procedure
B.5 EQUIPPING DECOMFL WITH GRADIENT PROJECTION
This subsection examines related approach from Yue et al. 2023) that utilizes the first-order gradient information but is closely related the zeroth-order method. Although their framework is not applicable to federated learning, we can adapt their projection technique within the DeComFL. framework. The main idea is making an inner production of the first-order gradient with random direction vector 2y, sampled from standard Gaussian distribution:
drr (zr, Vi((er))), 2, ~~~~ NO0, Ia)
(11)
This formula can be viewed as projecting the first-order gradient f.(i...))) into the subspace of Span(z,) since
Projz, (Vf(( (Vir (Zr, Zr)
1 z, j( (2n. ()i(
(12)
where the scalar 1/ can be absorbed into the learning rate.
Note that the dimension of 9.,- is just I (i.c., we compress a d-dimensional gradient information into a scalar). Hence, not surprising that we can replace the ZOO gradient scalar computed in (3) by this scalar obtained by random projection and produce another valid algorithm. The server-side
algorithm of gradient projection is exactly the same as Algorithm [ and the client-side algorithm is listed in Algorithm
straightforward to see that this algorithm shares the same communication cost per round as DeComFL with the ZOO approach. However, this approach requires significantly more computation and memory sources than the ZOO approach. Specifically, for each step, the extra computation required for gradient projection is one backward propagation and one projection step. In high-dimension models with billions of parameters, this extra computation cost is substantial and cannot be ignored. Further, this approach requires the extra storage of gradient, which is in the same order as the model size.
We conducted the same experiment as shown in Figure 2 joy the same communication cost mentioned before, but DeComFL. with Z0O consistently
In Figure two algorithms en-
18

---

Published as a conference paper at ICLR 2025
Algorithm 5 DeComFL with Gradient Projection [Client-side]
1: Initialize: maintain local model vi, and standby until the following procedures triggered by server. procedure ClientRebuildMMdell ((g 1= 1 ((s (1)
for l.....,? 7 4: for k= L..... K do
Equivalent to Pull-moded step.
5: Generate 2,,' (0, Ia) by random seed s....
" = ni 7g.
Ritt the local model.
7: end for
end for end procedure
10:
11:
procedure 2. ChienCGradPrnjI.eelllppppeu K
1R=1:
12:
for k = L.....K K do
Generate z, N0, In) by random seed s Taking hackward gradient computation far
14:
15:
ghr ++1 = = ngh..
(V
D Calculate the projection D. Gradient projection approach
16:
17:
end for
18:
revert the local model back to z?.-.
This step is crucial.
19:
Return [
20:
end procedure
performs better than DeComFL with the gradient projection. Furthermore, we observe that DeComFL. with ZOO exhibits insensitivity the papammer learning rate, while DeComFL with gradient projection is unstable for different learning rates.
0.98
0.96
Test Accuracy
0.92
0.90
0.88
Perturbation=100 (DeComFL)
Porturbation-20 (DeComFL)
0.86
Perturbation-40 (DeComFL)
Perturbation=10 (Gaussian Projection)
0.84
Perturbstion-20 (Gaussian Projection)
Perturbation=400 (Gaussian Projection)
0.82
50000
100000
150000
200000
Communication Vector Length
Figure 4: Comparison DeComFL the first-order method projected on random direction. The communica- tion vector length the count of accumulated scalars transmitted between the server and client.
Here we provide two aspects to explain the preceding phenomenon. First, the zeroth-order method should not be simply reviewed as the projection of finite approximations of the true gradient. Instead, as we will state in Lemma in Sec. D.2 the zeroth-order gradient is an unbiased estimate of the gradient of smoothed function f
/ f(x f(x+ uz)e uzze +|l=1
(") (2m)
-illl1 [ dz [f + μæ)],
The smoother function f has a better function property and curvature to optimize, such as better Lipschitz condition number (theorem 3.1 (a) of Ghadimi & Lan (2013)). As result, it leads to improved convergence properties.
19

---

Published as a conference paper at ICLR 2025
Second, (Z.,( gives the directional derivative of f(z) along This is purely first-order approximation how f()) changes along 2. In contrast, 920 uses function values at x and I + μu to estimate the rate of change in f()) along 2, incorporating higher-orde effects. This can be formally shown by Taylor's expansion:
[[xx+ -()) ++
Thus, the 70 gradient captures more information about the function's 's behavior along than the gradient projection.
C ADDITIONAL EXPERIMENT DETAILS
C.1 EXPERIMENT SETTINGS
Datasets for LLM Fine-tuning Tasks. We utilize a series Natural Language Processing(NL.P)
datasets execute fine-tuning tasks on LLMs (e.g., OPT-125M and OPT-1.3B), such as SST-2 (Socher et al. 2013 Wang et al. 2018) for the sentiment classification task, CB (De Marneffè et al. 2019) for hypothesis inference problem, WSC (Kocijan al. 2020) for commonsense reasoning task,
WIC (Pilehvar & Callcoo-Collados 2018) for word sense disambiguation task, RTE (Bowman et al.
2015 for natural language inference task, and BoolQ (Clark et 2019) for question answering.
Settings. In our FL system, for the experiments on LLMs, there are eight clients in total, and in each communication round, only two clients are sampled to participate in the training. In Table 5| we show the specific typer-parameter settings about learning rate and total communication rounds. For other shared parameters, we set smooth parameter μ = - 33, Dirichlet concentration parameter = 1, and local update step K 1. For DeComFL's experiments, we set train batch size 32 and test batch size 64.
Table 5: Experiment Settings of DeComFL
Model+Fine Tuning
Parameter Dataset
SST-2
CB
WSC
WIC
RTE
BoolQ
Learning rate
5e-6
2e-6
5e-6
2e-7
2e-6
2e-6
OPT-125M+FF
Comm. rounds
3k
lk
3k
3k
2k
2k
Learning rate
2e-6
5e-6
5e-6
2e-7
2e-6
2e-6
OPT-1.3B+FP
Comm. rounds
2k
3k
3k
2k
1.5k
1.5k
Learning rate Comm. rounds
le-4
le-4
le-4
le-4
5e-5
le-4
OPT-125M+LORA
3k
lk
lk
2k
0.5k
0.5k
C.2 ADDITIONAL EXPERIMENT RESULTS
Combine DeComFL with other techniques. Parameter-efficient fine-tuning (PEFT) techniques fine-tune just fraction of the network parameters. As already discussed in (Malladi al., 2023). the performance of zeroth-order optimization on LLMs does not improve substantially when tuning much fewer parameters. We confirm this surprising fact by combining LoRA (Hu al. 202I) with DeComFL. In T the test accuracy can still be comparable to full- uull-parmmeter McZO or DeComFL. We set alpha = 8 and rank 8 in LoRA and target Q and V matrices in the attention layer of LLM. In addition to LoRA, DeComFL can be easily combined with other PEFT techniques, such as trefix-tuning (Li Liang 2021) and LayerNorm-tunnin (Zhao et al., 2023). Also, no matter what PEFT techniques we combine, the communication cost will stay the same if training rounds stay the same.
*FP means full- parameter fine-tuning L.MMs.
20

---

Published as a conference paper at ICLR 2025
Table 6: Test Accuracy on Fine-Tuning Tasks (OPT-125M Model, LoRA)
Dataset
Task
McZ0
FedZO with P = 5
DeComFL with P = 5
DeComFL with P == 10
SST-2
85.07%
85,34% (0.66 TB)
85,42% (0.18 MB)
85.44% (0.36 MB)
CB
69.64%
70.55% (0.22 TB)
71.07% (0.06 MB)
71.43% (0.12 MB)
WSC
52.66%
54.61% (0.22 TB)
54.53% (0.06 MB)
57.03% (0.12 MB)
WIC
53.49%
53.12% (0.44 TB)
53.08% (0.12 MB)
53.71% (0.24 MB)
RTE
50.15%
50.92% (0.11 TB)
51.40% (0.03 MB)
51.40% (0.06 MB)
BoolQ
60.68%
60.53% (0.11 TB)
60.12% (0.03 MB)
60.78% (0.06 MB)
C.3 SUPPORTIVE EXPERIMENTS
C.3.1 EVIDENCE FOR LOW-EFFECTIVE RANK ASSUMPTION
We start by validating the low-effective rank assumption on a small model since the memory requirement for low-effective rank validation LLMs is quite expensive. We build small custom ResNet (He et al. 2016) model trained with the CIFAR1O dataset, then plot the eigenvalue distribution of the Hessian after fixed training steps in the left one of Figure 5 The approach we used to estimate eigenvalue density is based on the algorithm in (Ghorbani et al. 2019), which leverages the stochastic Lanezos algorithm (Golub & Welsch 1969). From the figure, we can clearly that the majority of eigenvalues of the Hessian is O, which aligns with the low-effective rank assumption.
Although it is computationally prohibitive to validate the low effective rank assumption on LLMS since requires the computation of huge Hessian matrix, we can still provide indirect evidence as the right one of 5 shown. We utilize the SST-2 dataset to train four L.MSs with different scales, including 125M. OPT-350M, OPT-1.3B, and OPT-2.7B.
Figure 5 we can observe that from the smallest OPT- 125M model to the largest OPT-2. 7B model, they all converge around the 1250-th round. The larger model converges slightly later, probably because it can achieve higher test accuracy. Hence, the d-dimensional dependent rate is quite pessimistic estimation. This a good implication that some low-effective rank holds in the modern large language model.
107
0.00
10"4
0.85
Frobacylty Dersty
10
Accuney
0.80
10
OPT-350M
660
OFT-1.38
2P7/2.88
300
3003
2500
2003
0
2:0
300
75C
1000
.250
3300
1750
2000
Eigenvauee
Lommunnccation Rounos
Figure 5: Hessian eigenvalue distribution with training custom ResNet on CIFARI0 dataset (Left)); Comparison of convergence of DeComFL multiple LLM scales the SST-2 dataset (Right).
C.3.2 COMMUNICATION COMPARISON OF DECOMFL AND FEDERATED LEARNING ALGORITHMS USING COMPRESSION
To show whether DeComFL can still provide substantial communication savings compared to FedAvg+Topk with smaller k, we use MaSHIon-MNIST dataset to test the FedAvg+Toplk's perfor- mance with different k. including 10%, 5% and 1% of the number of model parameters. Based on the experiment results in Figure communication cost of FedAvg+Tople can reduced, but communication overhead is still far higher than DeComFL.. More seriously, this manner triggers severe performance degradation.
observe the following phenomenon: As smaller Ik, the
21

---

Published as a conference paper at ICLR 2025
0.8
perturbee000
perturb
pertupo=1
0.7
0.6
DeComFL
FedAvg
0.5
Fed/vg TopK[10%)
FedAvg TopK(5%)
Test
0.4
FedAvg TopK[1%)
FedCom
0.3
0.1
0.0
0.2
0.4
0.6
0.8
1.0
Communication Vector Length
1e7
Figure 6: Comparison of DeComFL. and related algorithms. The communication vector length is the count of accumulated scalars transmitted between server client.
D THEORETICAL PROOF
D.1 MAIN RECURSION
We can focus on the evolution of the server-side model only because after the revert of the model (or synchronize step), all sampled clients the same as the server-side model. For other clients that are not sampled, they will sync to the server-side model after the reconstruction step, so that we can virtually assume that all clients and servers iterated with the same server-side model.
The recursion of the side model can be written as
Σ M1
Er
Jr Z
Tir
m
k-LiEC
where we just denote Uú = x. for the client's model. is now clear that our algorithm follows the same routine the Federated Average framework in that it combines the models after each client runs K' local-update steps in their local model 1-
D.2 LEMMAS FOR THE ZEROTH-ORDER OPTIMIZATION
Before we present the proof of our main theorems, first list several well-known lemmas about the zeroth-order optimization, which is the foundation for all the following proofs.
Lemma
Nesterov 2013 f E ch ) if is differentiable and satisfies
(s()) f(x) - (v)) - xx) < 2 at|?.
(13)
Lemma (Nsterov Spokoiny 2017 Ghadimi & Lan 2013)
We define a smooth approximation
of objective function fs J (-) that can be formulated as
(x (2m) / f((x uz)e =| dz Eff + 1z)),
(14)
where μ > is the smoothing parameter, and z is one n-dimensional standard Gaussian random vector. Then, for any f. ch.ll the following statements hold.
(a) The gradient of f/(( is L, -Lipschit continuous where L, L. ((((() can be shown
/
felx + uz) fx(x) ze =1 dz.
(x)
(15)
(2T))
11
22

---

Published as a conference paper at ICLR 2025
(b) For any R..
(z) f((x)) 22221 Ld
(16)
[v][ - -V\((e) - sguldd+3)
(17)
(c) For any x E Rd.
1 11/13/ ((())
4² Ld - + + +4] Vi()]|
1 1xxx
(18)
Following form
17 and utilizing Jensen's inequality
|al| v 21 bll2 + +2
b b 12 we have
1
[V 2/\V)(())]|
1.2 + 3)
(19)
2
1
[V < v
22 + 3)
(20)
2
Moreover, we denote f." (x*) == min f (a) and conclude If.' - f((x*)) s Ld
from [6].
=EB"
Then, we further conclude that
-1²² Ia (ax) (x²) [1(xx) fi((x)) S 1T
(21)
D.3 PROOF OF THEOREM 1
Our main theorem is based on multiple perturbations. To light the notation, we first introduce G that stands for the stochastic zeroth-order gradient estimate on a averaging over P-perturbation directions:
P
P
f( + (ettpishh)) falx) st.r)
P
Σ
kpp
P
1
Fipp
r.
P=1
p=1
p=1
(22)
To begin with, we start with a few lemmas about the property of G
Lemma (Bounds on the Stochastic Zeroth-Order Gradient Variance) The variance of the stochastic zeroth-order gradient E E| s,r f (=tt,)) can be bounded by the true gradient
f[v on the starting point of round r. the local update distance || xr and several constants:
6(d+ + 4)
P ( 4) E, ||a 1r + (11
6(d + 4)
E, ||G (a
0g
P
P
2(d
4) P
12
02
(23)
2P
Proof. For any independent and identically distributed random variables Ip with the mean y. we know
E
Up
y
(24)
p2
p=l
pml
Recall that Gh
Ep=l
G Gh,r,p
E
V
f (a. ). and lemma 2 shows that
st. st + 1² L''d 6)3.
E, G VJ 2(d+4) V
2
Substituting Gl,,, and above properties into 24
we establish
2(d + 4)
1 I (d 6)
E, | VJ (x
<
V f.
ck
p
2P
23

---

Published as a conference paper at ICLR 2025
2(d + 4)
2(d 2(d + 4)
0² 1
P E, [
P
2P
Next, we bound the E, (a )| via the Jensen's inequality:
E / || =B, || Vi V[((z.)+ V/(==)+
33E,
S3L?E, || - 2-11 + 300 v3
Lastly, plugging back, we finish the proof of lemma
2(d 4)
E | V.f -
3L'E, | x
30 + 3
P
2(d
+ 4)
(d2 6)3
0² +
P
2P
6(d + 4)
6 + 4)
[+xx))) 21+++
Er || xx11
P
P
6(d + 4) og
2(d 4)
2L2 6)
0²
2P
Similarly, we can also bound the second-order moments of E Br
,,, as follows.
Lemma 4 (Bounds the Stochastic Zeroth-Order Gradient Second-Order Moments)
E ||G 12 can be bounded by the true gradient ||V fxx))l? on the starting point of round the local
update distance | 1r? and several constants:
E, G 1
6(d P + 4)
[11 6T.
+ P + 4)
E,
P
P
6(d
MM+++44
+
P+4)
2(d +
0² 11 6)3
3)s (25)
P
P
2P
2
Proof. Using Jensen's inequality, know
E, ||, E, ||G - (ff )2 +E,, [+
(26)
From Lemma 2 we have
E. V f (=
1 ;11 1.
<2E,
[ )1( +
=2 [[ V)((x,)) Vf((a,)) VS(x.) ((a,))) )|²
1 + (d)+33)
<6L*E, || 2.1 + 6o% + ([ ) 2 / 12 3)3
Combining with the result 23 we conclude the proof of lemma.
M Ek a - xx [1a] for the local update steps, which
Furthermore, we denote Xr = Er
closely related to E, ||, 1| Using the previous lemma, we can easily establish the upper bound
on Xr-
Lemma (Bounds on Local Update Steps) With Assumptions 7 3 and the learning rate satisfying
<
VGLK the local update distance Xx satisfies
2P
KK3 d + P 2)
3K + P 4)m²
2K + 4)n² o
Xr
[V(x,))
06 +
P
2P
P
1 12 (d + 1)
+ z
P
24

---

Published as a conference paper at ICLR 2025
Proof. Utilizing the relationship -i,, 2, 17 Σイ=
Gi
have
r²² M
K
Xr
Er
G
M
i=1 k=
17
Σ
M
K
kE | |
M
1=1 k=1r=l
1² M
|
2M
k=
where the last inequality holds since E E kX, Er=1 E k)X, Substituting 25 we get
K2n2
M
K
6(d+ + P +
4)
|VS(,,)] + 6I2 P+4)
E | - xrrll
Xr S
2M
P
P
1=1 km1
6(d + P 44
2(d+
Id 6)3
P
p
0²
2P
+
2
(d 3)0
(27)
Moving the term E side, we have
| x. 1| which is Xr again after the double summations, the left-hand
6L2 (d + P 4)n²²
3K (d P 4)m²
3d + P 4)n²
Xr S
[Vf(z,)
oG
2P
P
2P
K (d + 4)m² +
7))
0²
P
2P
1 1,2 R3 (d 3)3/
(28)
When 17 S the proof of this lemma.
2P /6LKV8+P44* the coefficient on the lh..s is larger than } Plugging back, complete
Now, we are ready to present the proof of the main theorem with the above lemmas. To ease the reference, we restate the theorem here again:
Theorem (Restated; Standard Convergence Bound of DeComFL) Under the assumptions 2
and 3 supposing that the perturbation z ~ N(0, Ia), i.e., follows the Gaussian distribution, and
the learning rate satisfies 1) S minf (LL
m P(d+33
). then
mk LKL(dPP4)) P44) MKFL 2L K
holds
((((m)) -(xx))
72KTm
24(d + 4)Tm) mP
E. [( <
og
KRn
m
16I(d + 4)m 0² 24 L2
(29)
mP
where I, is the model parameter in the r-th round, P is the number of perturbations, x² is the optimal point, is the number of local update steps, R is the number of communication rounds, d is the dimension of model parameters, and is the number of sampled clients in each round.
Proof. First, applying the L L-Lisschitz smooth property the global loss function f. we have
f(x,+1) {f(x,) + (Vf(x,,) x,,11,,),,,,11111111 - xrr) + || - x,,
(30)
2
K
+ L
1
K
2
=f(x,) - ()((x)) m
ck f.
Gk
(31)
2
m
IEC, k=1
IEC,
k=1
k=1
25

---

Published as a conference paper at ICLR 2025
Taking conditional expectation E, given the filtration अ, and information before round obtain
[,[[(a++1]] (((r)) B, ((((n))
K
L
K
Gh if
E
G or
(32)
2
m
IEC,
k=1
iEC, k=1
41
A2
Observing Br,g E Ex= (ottr v.f(
0, the cross product term Ai satisfies
A = - K (Fr(a))
M
K
S (attir) )
(33)
MK
Utilizing the Parallelogram Identity, we know
K
1
A1
Knl Knll (x,, 1 K
2
MK
k=1
M
KnEr
f((
2
MK
i=1
R=1
1
Kin (xx, |1
K Kr
MK Σ Σ
v (a
2
M K E,
K1
(xx))))
2
MK
M K MK
Knl
Knl
V / (xx,) 11 KTYE,
(x
- 2
1mm
M
K
M K
+
E
Vfil 111
11 E M
V1((
v.((2,)) 1|2
M
k=1
K=
M K
< - Knl Knll V (xx, |1
KnE,
v (a
(d Kd
+
2
MK
1=
k=1
Lan M
M
E
10,1?
where utilize Jensen's Inequality in the first two inequalities and apply L-smoothness and 17 get the last inequality. Next, we focus on the quadratic term A2.
L A2
Er 2
1
Σ
Σ
G
m
igCr
K
K
E
G - (x
+ LE
a k
m
m
IEC, 1=1
iEC, k=1
M K
E, | - (at + L,
ff (atk
mM
1=1 k=1
iEC, k=
6I. 2)
M K Σ
x x.112= + KTaz²
[6(d + 4)
P |ffx,,)11 + 6(d+
E, /h
P dd
mMP
k=1
26

---

Published as a conference paper at ICLR 2025
[ + 4) Knp²
663 +
0²
Er
(34)
m
P
2P
m
As
where we applied Jensen's inequality in the first inequality; the second equality holds since each V [ar is zero mean and independent to each other; the last inequality utilized the For A3, it can be bounded as follows
term G
Lemma
K
A3 E,
(a
iEC, k=1
1
1 M
Σ
S
(
+ Laj
Er
S
(c
E
Σ
(
M
m
iEC,
k=1
(35)
Continuing bounding the A4 term, we have
K
M
K
A1 EE
v (x
(36)
M
iEC km
1=1
kml
(8)
< 3E,
m
IEC, k=1
K [((()t))
M K
+ 3E
MV R=1
(((
m
M
iEC, k=1
M
+ 3E,
[(((at)))) (ar,,)
M
k=1k=
①
K
M K
< 5
K2 (2 3)3 + 3E, K22
(a
Se (
(37)
M
iECr k=
1=1 k=1
Ag
K
M K
where in step (a), plus and minus the 1
Σ
Vi(a and
Σ
Σ
Vf((tt;) then applies
iEC.
1=1 k=
Jensen's inequality; in step (b), we restore the lemma on the first and last terms. Next, use similar trick to bound As:
K
As =3E,
(((x))
Σ
fi(xx))
VEC, k=1
IEC, k=1
SEC, A=
M
K
Vf((z,) M
fa
M
M
k=1
(a)
<. 9E
V [)((a))]
VEC, k=1
+ - r
vf(())) ΣΣ (xx))
m
VEC. k=
M K
+ 9E,
M Σ
Vf((2,) ((((tt))))
27

---

Published as a conference paper at ICLR 2025
(6)
I 18KL.B,
1 M
2 Zr 11
E
1 [f((),) vf(x,))
M
m iEC,
1 M
K
9K
18K L E
/0 xz,1 11
m E,
[V[((z,) [((x,)
M i=1
K=1
IEC,
(d) S 18KL
1
M
K
9K2
2 x.
M
m
where step (a) applies Jensen's 's inequality; step (b) utilizee the L L-piscchite condition; the equality in step (c) holds because each term [V,((,,,) [(((,,;,))) independent and zero-mean; step (d) results from the data heterogeneous assumption.
Plugging A4 and A5 into A3, we establish
M
K
A3 ELI
1
V (
+ 22
(d
M
9K2 Ln?
+ 18KL
- 20l1
0G
(38)
m
i= 1=1
Now, we are ready to put Aa back to A2 and group the terms
6K + 4) Aa
613 + 4)
[=((x,))1
ΣΣ Br 1 xz/l
mP
mMP
=1
6K 6KI(d+ 4)r?
2KI 4)11²
1 K2 6)
d
+
0²
mP
mP
2mP
M
K
3 2 K2 1, (d (d+
9K2LD
+ 1
arrl?
+
16
og
M
m
1=
1=1
M
K
2
+ LnrEE
V f (
(39)
M
M
K
2x,1" 1²
Combining all pieces and denoting X = Er
1
Σ
we have
M
M
K
1 [x[[(1++1]] (T(
1
1
1
Knl Kn]
KyY,
(a
+ 11 (T.,
2
2
MK
4
k=1 6 4)n²
(=1
6(d 2)LK?
+ 1,
[ax,)))) 2(d 2)
X
mP
m.P
+ 6(d + 44LKK2
p² K312
00 +
0² +
mP
mP
2mP
3
+ 18KL Xx
"1 "2²k3 13 (33
L
1 M K
+ m
OG + Ln L,
ΣΣ
Vs (ott.)
(40)
5f(x,)
(2Km
11
6(d + 4)LK?
[V MP2 + 1
(L
mt L'n+ (d 4)m?
X+ 2KL(d+ +4)?
+ 18KL)1
+
mP
mP
9K2 LI?
6(d 6(d+4))Kr)) mP
1L + 6)
(d
3
+
+
+ "
2mP
(41)
28

---

Published as a conference paper at ICLR 2025
Plugging lemma into 41 and following 1j S min { can further simplifid into
mP
2P
mPdd+3)
24I(d+4)
mKL(d+P44) mKLL
L18
6(d 4)LKgp
Br]f(z,+1) sf(x,) - [n]]lV +
+
m
mP
0² 21² (1 + 4KL(d+ + 4)n
(42)
mP
Rearranging the terms, we have
188KLn Ln
6 + 4)LKn²
KnllVf(<>>11 sf(e,) - E, 1f +
+
mP
1 0² + 7 + 4KLid+ 4)m1
KK2 +3)²
(43)
mP
Dividing 1 Kn on both sides, then we get
(f(x,) - Er(((( + 72KLn
24(d + 44)
[f(+))11
og
Kn
m
mP
16 + 4)m 0² (d
(44)
mP
Recursively executing 44 R rounds, obtain
R-1
((s(xo)) f(x)))
72K
24(d + 4)Lm
og
KRn
m
mP
16L(d (d + 4)7 02 + 2p L2 3)3
(45)
mP
D.4 PROOF OF THEOREM 2
In this section, only consider the case that local update step K = 1, so we ignore superscript k in this proof. The following proof inspired by the MeZO work (Malladi et al. (003)) and extends the proof for the multiple-clien case. In (Malladi et al. 2023), it directly utilized the following form of the effective zeroth-order gradient:
P
vf
1 mP
Σ
gr
Zr.p
iEC, pml
P
(fe(e, + uzrpiEsr)) - f((xri:(.)) Zrpp
mP
IEC,
p=1
EE TT (Z((
(46)
p=1
However, the last equality does not hold in general unless /z - 0. Fortunately, leveraging the basic lemma stated in the previous section and using the mean value theorem, we can fix the proof. Using the mean-value theorem, we know
1 (Ji(xr + p.r Exr) - fi = TT, (i Sir))
(47)
where 2/ x, + ,r,z,, for some 0 [0, (we do not need know what value the is), so that the effective zeroth-order gradient we utilized is
f((rri
Σ
Σ
=
fi
(48)
mp iEC. p=1
29

---

Published as a conference paper at ICLR 2025
To light the notation, we introduce
P
Varrii Er)
2r T r. Vie(Erri
(49)
mP
SEC, p=1
C4 mP
p rp
V Ei,r) (arr
(50)
SEC, p=1
so that compactly write (arii = vf(zzii,)) + Gy- The motivation of introducing V fxxr is because is much easier to handle compared with (.rri and it straightforward to bound the difference:
|
Zr, T (V (Vi( Es.r) Esrr)
V (((r
mP
iEC, p=1
L
1 Zr
P| 112111111/11
mP iEC, p=1
L2² L²²1²
|2r
mp
VEC,
= L 2 d
(51)
Another difference from the proof in (Maladi et al. 2023 is noticing the conditional expectation of the stochastic zeroth-order gradient is unbiased to the Gaussian smooth function fr
E, [ B, 1
Σ (.
V (z(x)
(52)
m IEC,
Notice not unbiased to the gradient of the original function, i.e., E, E,IV E.) (z,,), in general. The covariance matrix of v f has the following relationship.
Lemma The covariance matrix of the stochastic zeroth-order gradient V (xrr; Er) is equivalent to
E [V/or
d
(IV
-EE)) + m
1 - ( I
P(d +2)
m
+ 1+ d 2
(Vf(z))V((..)
P(d+2))
E,
+ Ar
m
m
(53)
where the stochastic gradient noise is denoted as 8i, = Viliar;; E,) V((xx). d is the dimension of model parameters, P is the number of perturbations, and the definitions of Exp and A Agy are
Σ,
(54)
M
i=1
M
1
for
Σ
VI(a,)VA((.) Vf(,))V((a.."
(55)
M
E, can be understood as the covariance matrix introduced by the data randomness and A for as the covariance matrix introduced by sampling the client's different local loss functions.
Proof. Substituting the equation (49 of (x Er) into the covariance matrix, we obtain
E (( = E
Σ
2 VV Z.
2 p2
ECC P.p
30

---

Published as a conference paper at ICLR 2025
P
+
m2p2
E P.p'C
Σ
B 2p2p B
8 27
Tp
(56)
:=
where we dropped the cross term due to the zero mean and independent properties of the stochastic gradient noise Si To find the value of T1, note that"
E
E
Vf(lE,)Vf((,,7
E,EC,
M Vf(le))
= =(m² - -
m
V
M
M
=m Vm8 T +
Vf(a))
Vf(x,)Vf(a,)
(57)
M
A
(The real randomness comes from C, instead of i, Here B, is just for simplicity.) We do not know what f is, but it can be bounded that
Tr ).r) M
-
1 M
[V)(x,)
v/((,,))1 5 s (58)
Focusing on the first term Ti, we have
P
T =
E m2p
Eiy
Vf(la,)
i.EEC
P V/,,,, 2
+ m2
Eiyy
Σ Ezp S.E'C,
Σ p=1
P Vf(xx) (xx
P-1
Aprr +
E
zp V [ft, =p2p
P
mP
p2
p=1
P Σ
Zp Zp2
m2
Zp
p==
P V (f(
Arr + P-1
d P(d+22
2d
V
P(d+2) ([(x,)
P
m.P
d
2d
mP(d+2) MI
S.r:
m
where the first equality is split according to p p' and # p', and we plug the established result (57) into the second equality, the third one is because of the properties of uniform distribution
2d
Epp uv z,=,_]
Tr(uv )
d we
(59)
d+2
See the proof of lemma 2 in Maaladi et al. 2023)
Next, the stochastic gradient noise satisfies
M
E Eii
Σ
B
=
m M
S == mE,
where Tr(E,) < 0²
(60)
i.PEC.
1=1
For the proof here, the notation T. means the expectation with respect to instead of the given condition filtration before
31

---

Published as a conference paper at ICLR 2025
The second term T2 is similar but easier:
P
T2
Σ
7h. mp
P-p'=1
P E,
d mP + 2)
(r(E,))+2E,
(61)
mP
Combining the result 7i and 72, we establish
d
+ -Tr(I,)) + 1 T m
E (V((at))
P(d + 2)
m
P
(V
+
Arr + Exp
P
m
2d
(V((,,)Vf(,,) 2)
A + Er
m m
Regrouping the terms and simplifying the coefficients concludes the proof of this lemma. To ease the reference, we restate the Theorem here again.
Theorem (Restated; Convergence of DeComFL with re-Effective Rank) Under the assump- tions
I 2 and 4
supposing v S 3I (1
dx+dd22
and drawing 2 from the unit ball with
P(d+2)
radius v holds
R-1 R
1
4(f(20) - [(xx))
2h 1+
dk + + 222 P(d 2)
(
(og +
Rn
+ 11 1,2 (.2 3)3 + Apu 1.
Selecting = O
YmP Vitx
and 5 RP / (d+3j3'
4/
we can get
Σ
R 1
B(
o ( (VmRP)
VK
)
=
V
(VV
) (06+00?)
Vk
10 100
(62)
R
VmRP
Further suppose >> P. the convergence rate is O large round R.
_VR Va (mRPP)
when the algorithm runs with sufficient
Proof. Taking the conditional expectation over the recursion of the loss function and expanding the function value via Taylor's 's theorem:
E, [.((((++1))
v2 2
=f(x,) ()( E (Z())))))) +
( V (x,)) 2 [f fz)
1 (63)
where the æ². in the first equality is some value lying between H, and Ør++1 and the inequality applied
the Jensen's inequality on the quadratic term. Using the identity (a, b) 1 [I|a||2 2 ||b||2 - ||u b1
we have
E, E. 5f(x,) ! [[V[(>)))*
(xx 2 + Vfxx,, f2,(2)))1
2
1 E [f TV>
V/ + 17 r.
(64)
Discarding || [x,((,,))1 term and applying 17 and 51]
we have
22
E,[f(x,,1) sf(x,) " |V
8 (d+3) 3)3 3)3
32

---

Published as a conference paper at ICLR 2025
+n [f(
L (f
(65)
Based on the assumption 4
we bound the Hessian
(xx,) by H (z,,) and arrive
E, E. sf(x,) 7 - [V
nu L
(d + L²
8
+ n"² (H()), E
(zr (V
(66)
73
Next we focus bounding the term T3. Plugging the conclusion of Lemma 6 we get
[IV[(=,)] 1 TEE) + 1 , Tr (x,)) (1+ d d-2
d
T3 P(d+2) 2)
m
m
)
(f((.)) ((x,) (2ir, H (x,)) - (A,,,. J. H(x)))
P(d+2)
m
By the assumption, the Hessian upper bound H (I,,) satisfies Thus, obtain
[H I L and Tr (xr)) s Lx.
Ldk
[[f(t,)] T=,))) -
T3 S P(d + 2)
m
m
1+ d d-2
(IV TT(EE _ TT(A
L
P(d+2) 2)
(67)
m
m
dk + d 2) )
1 TrE,,, m
=L
P(d +2)
m
S1 1+ dk + d -2) P(d 2)
1 m
[[V]((=))]
(og + oo)
(68)
Substituting back, we obtain
[,[[(ar+1)] <)(x,) - [( 11²12
(d+ p1
+ + [+ du + d 2)
2(d+2) )
[VVf(x))]
1 (06 0
(69)
To establish the convergence rate, we move the [[ to the left-hand side and take the expectation over both sides
" ( -- nI. (1+ dx + d (ot4-22) ))
E [(,,)|
P(d+2 2)
< E(x,) - E f(x,+1)+ + 12 L
du + d -2)
P(d+2) (06 +0++ n1 I (d 3)3 2
1+
Take telescoping sum from 1 to R and require 7) 5 11
1
(1
dx+d-2 P(d+2)
we obtain
Σ E [(
f
4(f(x)) - [(xR))
+ AnL
1+
dx + dl -d-
P(d+2) ) (oā +02)
R
Rn
z"" " I2
4mp LA,3
(70)
This completes the first part of the proof.
Selecting 1 Rx
and μ S VmRP (d-
VF
we can get
R
E
O ( 0
VmRk +
VK
( (oē+0²)
(71)
R
VmRP
Typically x > P so the convergence rate O
VmRP
33

---

Published as a conference paper at ICLR 2025
Remark 4
The result (70) is intuitive. Besides the terms related μs, which come from that use the exact form instead of approximation, it is similar to McZO's result except for one more term L Lr fr())r) which is corresponding the data heterogeneity between the clients. The intuition can mn
be gained from the rule of total variance:
Var (arVVao (z, Ei) = Var(V + E.. (DDI S +o.
(72)
This implies that our algorithm in K case is equivalent to the MeZO algorithm with larger stochastic gradient noise. the FL scenario, the effective gradient noise equivalent to local mini-batch randomness (in-group variance) plus the sampling randomness (between-grew grrepp variance).
D.5 THE PROOF OF CONVERGENCE OF DECOMFL WITH K- EFFECTIVV RANK; GAUSSIAN CASE
Lastly, present the case that the ii is Gaussian. The main proof idea is that ||z, can be unbounded so that Assumption CastoonIcaaan cannot be applied directly. Nevertheless, the probability of large ||
value decreases exponentially fast. Thus, we can establish the following bound based on two probability events.
Theorem (Convergence of DeComFL with x-Effective Rank; Gaussian) Under the assump-
3 and 4 supposing 1 S JI (1+ Gaussian distribution, then it holds
tions
12
/
dettd2) and Zi,r generated from the standard P(d+2)
R
4(f(xo) f(x'))
2nL 11 de + 2 P(d+2) (06 + 0²)
Σ
R
Rn
+ 1 exp(- exp(-S(mdP)) 0(H²),
where G is defined as the largest value among {G( and MmmPP) means some function values that be lower bounded by md..
Proof. Let A be the event that || ærll < 2r,dG(ar)). Similarly, we can compute the bound based on the event A happens and the event A does not happen:
11²
E, E/( )1 ()(x)) - "[v
(Hx)), E (/aar,) I(4)+)
L (5 (.) 1[19)1 + mu² (d (d+3) L
=f(x,) - - || [ ((,))\ )| + r H(x,), (..i [
n2 LI - H
1(49)) + 0(#2), +0
(73)
where the symbol ((A) is the indicating functions that is 0 when event A does not happen and when event A happens, A stands for the complementary of event A.
Note on the event A we have
P Σ pm1
P z G((x))
2nddG(æ,) < ||0,+11 Ør =
zp Vi(ttiiee)
S
mP
mP LEC,
tEC,
pm1
(74)
We conclude that
Pr[A9] < Pr
Σ
12 2d
(75)
mP iEC,
Utilizing the i.i.d. property, the right-hand side can be calculated via the Chi-square distribution
mdP
Pr
Σ
|| < 2d
Pr[Xmap 2mdd] S exp
(76)
mP
16
34

---

Published as a conference paper at ICLR 2025
where XmdP is the Chi-square distribution with the degrees of freedom mdP. Using the same technique used in (Malladi et al. 2023 Lemma 6), we can conclude
q¹ LI - H E 2
((45)) - 3
(77)
where (2(mP)) means some function value that can be lower bounded by mdP. Typically, mdP is very large value, so this term is vanishing very quickly. Lastly, combining with the proof of Theorem 2. we arrive at the claim of this theorem.
35


Reviews:
[{"review_id": "4A7Veg36kP", "reviewer": "Reviewer_GgPr", "summary": "The authors consider the practical problem of communication costs in federated learning with increasingly large models especially in the era of LLMs. The authors propose DeComFL, which decomposes the local gradient updates from the clients into a scalar magnitude and a pseudo-random perturbation vector. Since the pseudo-random perturbation is recoverable with known seeds, only the scalar magnitude and the random seed are required to be transmitted during each round of FL training, reducing the communication cost to $O(1)$. The author further provides convergence analyses of the proposed algorithm with and without a low effective rank assumption. Empirical experiments show competitive test accuracies and significantly reduced communication costs for DeComFL.", "questions": "1. It is unclear to me why zeroth-order gradients are essential in the problem setting: The authors consider the optimization of model parameters which is essentially white-box. The authors are “downgrading” to zeroth-order information for model updates when first-order information is accessible (since the whole model architecture and parameters are known), which may be suboptimal.\n2. Related to the question above, the authors claim in Line 63 that “decomposition into a gradient scalar and a perturbation vector” is a unique property of zeroth-order gradients. Please clarify and justify this. Can I achieve a similar effect (eventual convergence, though might be different rates) by projecting the first-order gradient to a specific direction of a perturbation vector?\n3. In related works, please clarify the similarities and differences between DeComFL and FedZO? Is DeComFL an extension to FedFL by exploiting the $\\kappa$-effective rank assumption?\n4. In Table 2, no doubt that the communication saving is substantial. However, the last column is misleading as it has a larger P than FedZO (4th column). I would prefer it removed to avoid confusion.\n5. There is no validation of the practical assumption for effective rank. I suggest a comparison of the convergence rate of several differently-sized LLMs. If similar practical convergence rates are observed (with respect to communication cost, I understand the communication costs should be the same for differently-sized models), then $d$ is shown to be pessimistic.", "limitations": "", "rating": 5, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "1. The paper is generally well-written and has a good flow.\n2. The convergence analysis is necessary and duly provided. The discussion on the effective rank assumption to improve the pessimistic convergence bound is interesting. I did not check through the details for the correctness of the proof.\n3. The algorithm design is sound.", "weaknesses": "1. I am not convinced about the critical role of zeroth-order optimization in the problem setting to reduce communication costs.\n2. Parts about the related works and the experiments could be improved, as detailed below in the Questions.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "w9fRtOWUqm", "reviewer": "Reviewer_tpD4", "summary": "The paper uses zero-order optimization in federated learning for achieving communication-efficiency. The main idea is that since the update for zero-order optimization consists of (1) random direction sampled from a gaussian distribution and (2) magnitude 1-d value computed on the data, only (2) needs to be transmitted and (1) could be recovered by the server/other clients if they know the random seed, thus significantly reducing communication cost per each round of training.\n\nThe paper provides convergence guarantees of their proposed method, particularly showing that if the loss function has small effective rank, then convergence does not depend on the dimension of the problem d, but rather depends on the rank of the loss function. \n\nThe paper additionally provides experimental verification of the proposed algorithm.", "questions": "1. What is the difference between the result in Theorem 1 and the prior work that analyzed federated learning with zero-order optimization, e.g. (Fang et al., 2022)? As I understood, algorithmically your method is exactly very similar with only a difference of how direction gradients are samplied & how the communication is performed. Does it pose some extra challenges for the analysis? \n\n2. Why do all the $z_r^k$ are equal on different nodes? I think algorithmically nothing prevents $z_r^k$ to be different on different nodes? The server would just need m times more memory to save all of $z_r^k$. Would such a modification provide a faster convergence?\n\n3. On lines 052-053 paper comments that “because the models become large, communication becomes a bottleneck” howether, for modern models the computation cost can scale quadratically with model dimension, while communication cost scales only linearly. See e.g. [1]. While I do believe communication cost is an important issue in federated learning, I would recommend rephrasing this sentence.\n\n    [1] SWARM Parallelism: Training Large Models Can Be Surprisingly Communication-Efficient, Ryabinin et al. \n\n4. communication cost analysis - might not be accurate? \n\n5. I think $m$ was never introduced in the paper. I understood that $m = | C_r |$, but I didn’t find where it was defined. \n\n6. Could you give an intuition how large the server memory is for training some standard benchmarks? Is it bigger/smaller than saving the full model? \n\n7. I think setting $\\mu$ as in Corollary 1 does not give the desired result, as the term $2 \\mu^2 L^2 (d + 3)^3$ would still have d at the nominator instead of $\\sqrt{d}$. \n8. In Assumption 4, which matrix norm do you use? \n\n9. In theorem 2 $d_{\\kappa}$ wasn’t defined before. \n\n10. Could you also analyze local steps in Theorem 2? What is the difficulty? \n\n11. I think that condition $\\kappa >> P$ could be replaced with just $\\kappa > P$. \n\n12. In Theorem 2, why is setting round R sufficiently large allows to remove the $\\sigma_G^2 + \\sigma^2$ term?", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "The problem tackled is interesting and important and the proposed method saves a lot of communication (order of 1000s in experiments). Theoretical analysis allows to reason about potential communication savings during the overall course of training. Experiments are done on large models (up to OPT-1.3 B).", "weaknesses": "1. The paper does not state how exactly the random seeds are chosen, which might affect the distribution of the generated sequence. \nAs far as I know, random generators guarantee the distribution of sampling a sequence of numbers from the same generator initialized once at some random seed, however with each number having its own random generator with its own random seed, I am not sure what guarantees exist and I imagine it depends on the distributions of the random seeds and particular implementation of random number generator, i.e. if random seed are deterministically chosen in the increasing order (i.e. the next random seed is equal to s + 1, where s is the previous random seed), then the generated numbers probably won’t follow the gaussian distribution. Also, if the random seeds are sampled from the uniform distribution, it is unclear to me, which distribution will follow the generated vectors. \nTherefore, the authors should add a formal statement about the generated sequence of vectors and specify how to generate a sequence of random seeds.\n\n2. In experimental comparison on MNIST, the learning rate is set as the same constant across all the algorithms and settings, which might favor some of the algorithms/settings. For fair comparison it would be better to tune the learning rate separately for each experiment. \n\n3. Experiments on OPT do not compare to the fine tuning with federated averaging. I am wondering, how close to the finetuning with fed avg can zeroth order optimization get. \n\n4. On Fig 3. FedAvg + Topk converges much faster than DeComFL in terms of the number of rounds, and it is only slow on the right plot because k is quite large. I am wondering, if you reduce k, so that FedAvg + Topk converge with similar speed as DeComFL, would ZO optimization still provide substantial communication savings compared to FedAvg + Topk for that smaller k?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "StvRWSVbPE", "reviewer": "Reviewer_Ftuh", "summary": "This paper discusses a federated framework using zeroth order (ZO) optimization called DeComFL. It improves the previous ZO method by Fang et al. (2022) because, in each iteration, DeComFL only uses a constant number of bits of communication for each agent.\n\nThe authors prove the standard convergence theorem and provide a corollary under the $\\kappa$-effective rank assumption. Additionally, they present experiments on training DeComFL, comparing it to the traditional first order method and other zeroth order methods.", "questions": "Can you provide any evidence for the low-rank assumption you made?", "limitations": "", "rating": 6, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "It is quite novel to see the use of a zeroth order method for federated learning, and this paper makes a valuable contribution to this area.\n\nWith small and clever modifications to the previous algorithm by Fang et al. (2022), this research effectively reduces the per-iteration communication costs to a constant for each agent. Supported by both theoretical and experimental evidence, this new method significantly outperforms FedAvg in terms of communications costs.", "weaknesses": "The assumption made in Theorem 2 is not very standard. I am not sure if $\\kappa$ can be truly seen as $O(1)$ constant and independent from $d$. What will be the consequence if $\\kappa$ will scale up with $d$, even if it is not $\\Theta(d)$?\n\nMinor: \n1. I think the algorithm was stated for $P=1$. When reading pages 4 and 5, $P$ does not appear to be any part of the algorithm. It was confusing what role the constant $P$ plays in the algorithm. \n2. In assumption 4, the second maximum should be over $\\xi_{i,r}$? Could it be a typo?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "Q0NwC2SvrB", "reviewer": "Reviewer_HVSK", "summary": "The authors propose a new approach to reducing communication overhead between a server and clients. They have developed a new algorithm that reduces the overhead using zero-order optimization techniques. Noting that in zero-order optimization, it is sufficient to send scalars between a server and clients (unlike first-order optimization, which requires sending vectors), they introduce a new method, called DeComFL, that works with function values. This method is validated by theory and experiments.", "questions": "-", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 2, "strengths": "The paper addresses the significant problem of communication overhead in the field of Federated Learning (FL). Unlike many previous approaches, which typically focus on reducing the communication overhead of gradients, this paper proposes leveraging techniques from zero-order (ZO) optimization, where only function values, which are scalars, need to be transmitted. The idea is promising (though not new; see Weaknesses). I haven't checked the proofs in detail, but they, along with the final results, appear reasonable and clean.", "weaknesses": "Let me point to the weaknesses of the paper:\n\n1. Unfortunately, I'm not sure if the authors are aware, but exactly the same idea to utilize Assumption 4 in the FL setting was in [1]. Albeit, [1] consider the gradient estimator \n$$\\langle \\nabla f_i(\\cdot), z\\rangle z$$\ninstead of (3) from this paper (if $\\mu \\to 0,$ they are equivalent); after that, the idea and the proof techniques are almost the same between this paper and [1].\n2. Additionally, the theory from this paper almost replicates the theory [2] adapted to the multi-client setting.\n3. As a base method, the authors take the FedAvg method. While it is the most famous FL method in the literature, there are numerous more modern methods that should be discussed and compared to this approach (e.g. [3]).\n\n[1]: Yue, Pengyun, et al. \"Core: Common random reconstruction for distributed optimization with provable low communication complexity.\" arXiv preprint arXiv:2309.13307 (2023).\n\n[2]: Malladi, Sadhika, et al. \"Fine-tuning language models with just forward passes.\" Advances in Neural Information Processing Systems 36 (2023): 53038-53075.\n\n[3] Mishchenko, Konstantin, et al. \"Proxskip: Yes! local gradient steps provably lead to communication acceleration! finally!.\" International Conference on Machine Learning. PMLR, 2022.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)