EvoFed: Leveraging Evolutionary Strategies for Communication-Efficient Federated Learning
Authors: Mohammad Mahdi Rahimi
Hasnain Irshad Bhatti
Younghyun Park
Humaira Kousar
Do-Yeon Kim
Jaekyun Moon
Venue: NeurIPS 2023 poster (2023)
Keywords: evolutionary strategies
federated learning
gradient compression
distributed learning

Abstract: Federated Learning (FL) is a decentralized machine learning paradigm that enables collaborative model training across dispersed nodes without having to force individual nodes to share data.
However, its broad adoption is hindered by the high communication costs of transmitting a large number of model parameters. 
This paper presents EvoFed, a novel approach that integrates Evolutionary Strategies (ES) with FL to address these challenges.
EvoFed employs a concept of `fitness-based information sharing’, deviating significantly from the conventional model-based FL. 
Rather than exchanging the actual updated model parameters, each node transmits a distance-based similarity measure between the locally updated model and each member of the noise-perturbed model population. Each node, as well as the server, generates an identical population set of perturbed models in a completely synchronized fashion using the same random seeds. 
With properly chosen noise variance and population size, perturbed models can be combined to closely reflect the actual model updated using the local dataset, allowing the transmitted similarity measures (or fitness values) to carry nearly the complete information about the model parameters.
As the population size is typically much smaller than the number of model parameters, the savings in communication load is large. The server aggregates these fitness values and is able to update the global model. This global fitness vector is then disseminated back to the nodes, each of which applies the same update to be synchronized to the global model. Our analysis shows that EvoFed converges, and our experimental results validate that at the cost of increased local processing loads, EvoFed achieves performance comparable to FedAvg while reducing overall communication requirements drastically in various practical settings.

EvoFed: Leveraging Evolutionary Strategies for Communication-Fffiiee Federated Learning
Mohammad Mahdi Rahimi Humaira Kousar Jaekyun Moon
Hasnain Irshad Bhatti Younghyun Park
KAIST humairrakousar:22/aaaitt
{mahi, hwshainn dnffkf369 jmoonkkaist.. edu
Abstract
Federated Learning (FL) is a decentralized machine learning paradigm that en- ables collaborative model training across dispersed nodes without having to force individual nodes to share data. However, its broad adoption is hindered by the high communication costs of transmitting a large number of model parameters. This paper presents EvoFed, a novel approach that integrates Evolutionary Strate- gies (ES) with FI. to address these challenges. EvoFed employs concept of fitness-based information sharing', deviating significantly from the conventional model-based FL. Rather than exchanging the actual updated model parameters, each node transmits a distance-based similarity measure between the locally up- dated model and each member of the noise-perturbed model population. Each node, as well as the server, generates an identical population set of perturbed models in completely synchronized fashion using the same random seeds. With properly chosen noise variance and population size, perturbed models can be combined closely reflect the actual model updated using the local dataset, allowing the transmitted similarity measures (or fitness values) to carry nearly the complete information about the model parameters. As the population size is typically much smaller than the number of model parameters, the savings in communication load is large. The server aggregates these fitness values and able to update the global model. This global fitness vector is then disseminated back to the nodes, each of which applies the same update to synchronized to the global model. Our analysis shows that EvoFed converges, and experimental results validate that at the cost increased local processing loads, EvoFed achieves performance comparable to FedAvg while reducing overall communication requirements drastically in various practical settings.
Introduction
Federated Learning (FL) provides a decentralized machine learning framework that enables model training across many devices, known clients, without needing collect and process sensitive client data on the centralized server [1] The typical FL process begins with each client downloading an identical initialized model from central server, performing model updates with local data, and then uploading the updated local model for the next communication round. Subsequently, the server combines the uploaded models refine the global model, typically using technique like FedAvg (2)
This iterative cycle repeats for fixed number of rounds, ensuring collaborative model improvement across clients.
Although FL provides notable benefits, such as a certain level of privacy preservation and the utilization of diverse data sources, one of the major challenges associated with FL is the significant
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

communication overhead involved in transmitting model updates between clients and the server, especially when dealing with models that have a large number of parameters.
Various strategies have been developed to mitigate the communication burden in FI.. These techniques can be broadly classified into three categories: Compressing updates: sparsification [1, structured updates [3], and quantization [ reduce the size of transmitted model updates, ii) Local computa- tion: performing multiple local epochs at the clients [6] lessens the frequency of communication with the server, and iii) Advanced aggregation methods and client selection: MOCHA [ enhances the
efficacy of update aggregation and g reduce communication by only selecting subset of clients
to participate in each training round.
Existing FL techniques primarily rely on trans- mitting gradient signals or model updates, which
Ask Generate generation
Evaluate Call fitness
computed through backpropagation (BP). On
Update generation
the other hand, Evolutionary Strategies (ES) [TO]-
12 update model parameters by utilizing fitness values obtained from evaluating a population of models. This approach eliminates the need for a gradient signal, as depicted in Fig. T Recent ad- vances in neuroevolution have shown promise in supervised settings and competitive performance with reinforcement learning in control tasks [[3]- 15 11, In this context, ES offers a distinct advantage compared to traditional BP methods. This paradigm shift opens up the possibility of searching for novel solutions beyond the gradient- based methods. However, it is critical to note that ES, despite its potential, still lags behind gradient- based methods in certain problems like supervised learning. Fig. 2[a reveals the performance gap between ES and BP. This emphasizes the need for balanced approach that would leverage the strengths of both ES and gradient- gradient-based methods to achieve optimal results.
of -m(0
0, 6,st
Figure 1: ES follows an iterative ask, evaluate, and tell approach for optimization. The stralegy starts by generating candidate solutions of base model(ask), which are then assessed using fitness measure (eval- uate). The basc model is updated towards a better solution using the evaluation results (tell).
Our proposed method operates on the premise of incorporating high-quality gradient signals into the evaluation process of ES. The process can be formalized as follows:
FMNIT
30
Test 3cunayy))))
Given a base model, denoted by 0, we instantiate population P comprised of N model samples, Each individual sample, 0', is de- rived by adding random perturbations 0. Unlike traditional ES, where the fitness of O' corresponds to its performance on the task, we instead assess the fitness of each sample 8 by measuring its sim- ilarity to 8", the model parameters updated through gradient descent steps. This operation effectively exploits the gradient signal con- struct a fitness vector, process we term Population- Based Gradient Encoding (PBGE). Fig. 2 shows the results of a representative experimental setting where PBGE is able to follow BP closely on the
10
233
-00
600
1000
Epocts
(a) Estimation with ES
FHNIS
300
FMNIST dataset while maintaining an effective compression rate of over 98.99888.9 8%. In particular, this method significantly outperforms sparsification strategies at equivalent compression rates.
30
76CE13309
222
-00
500
500
1000
In the context of FL, the gradient signal can be encoded into fitness vector for the population of models and communicated to the server. For global synchronization, well-established approach like FedAvg would involve reconstruction and aggregation of the clients' models and sharing of the aggregated model with the clients. However, by utilizing shared random seeds, we can ensure uniformity in the generated populations between clients and the server. This allows us to transmit and aggregate only the small fitness vectors without reconstructing the models, reinforcing communication efficiency. In addition, there is an advantage in implementing extra privacy measures. When encryption is desired, the required overhead would much smaller with the fitness vectors than with the model parameter vectors because of the size difference. A brief overview of EvoFed is shown in Fig. (th detailed methodology is provided in Section 4).
Espacts
(b) The proposed method
Figure 2: Test accuracy on FM- NIST dataset comparing (a) ES against BP, and (b) PBGE with BP and Sparse with 98.8% com- pression.
2

---

Generate perturbations Update
Get fitness scores Upload
Broedcast aggregated
fitness Update model
000 1
Aggregated
Seed
Fitness
Initial model
Perturbed madel
Locally updated model (by backprapagation)
* Globally updated model (by fitness)
Figure 3: Overview of the proposed EvoFed: (I) Using the shared random seed, each client generates population of perturbations around the local model. Each client also performs gradient update of the local model using the local data as in conventional FL. (2) Each client evaluates the fitness of each perturbed model with respect to the updated model. The fitness values are communicated to the server. (3) The server aggregates the fitness values. Clients update their local models using broadcast aggregated fitness.
introduce a novel concept of Population- Based Gradient Encoding (PBGE), which allows an accurate representation of the large local gradient vector using relatively small fitness vector, significantly reducing the communication burden as well as the encryption overhead in FL environments. We also propose and verify the EvoFed framework that integrates PBGE into federated learning based on the exchange and aggregation of the fitness vectors between clients and the server.
Contributions. To summarize, our main contribution
Our approach achieves similar performance FedAvg on both FMNIST and CIFAR-10 datasets. The advantage is that our scheme achieves very high compression, exceeding 98.8% on FMNIST and 79 CIFAR-10 10 in key practical settings. Significantly, our EvoFed model also outperforms traditional compression methods, offering superior results at similar compression rates. The price we pay is the overhead of generating a population of perturbed models and computing similarity measures. This overhead could be substantial in the form of increased local processing time depending on the size of the population, but the client computational load can be traded with local memory space by employing parallel processing. In addition, as discussed later, reduce population size without affecting performance.
2 Related Work
Federated Learning. Several techniques have been proposed to alleviate the communication over-
head in FL, such as model compression [ 19 20), distillation techniques [2T 25), and client update subsampling [26] (7]. However, these approaches often come with trade-offs, including increased convergence time, lower accuracy, or additional computational requirements. More importantly, they still require the exchange of model parameters, which requires substantial communication bandwidth. Furthermore, (8 shows that the gradient sparsity of all participants has a negative impact on global convergence and communication complexity in FI..
Evolutionary Strategies. ES are black-box optimization algorithms inspired by biological evolu- tion 129 ES algorithms iteratively refine a population of solutions based on fitness evaluations. Within the NES
Natural Evolution Strategies (NES) is specific variant of ES 30 framework, the distribution Py: (0), parameterized by v. is adopted to represent the population and maximize the average objective value Eg-pe [+t] via stochastic gradient ascent, where (0) is the fitness function. NES algorithms leverage a score function estimator as in [1O]. Our method follows the guidelines provided by (66, where the parameter distribution pv: is a factored Gaus- sian. Accordingly, we can represent [o
12 335
using the mean parameter vector 0, such that Ea-pe [f(0)] = Le + σe)]. Given a differentiable function estimator, the well-known conversion procedure allows optimization over to be rewritten as (see, for example, 37
V Ve + ac)] 1 (100
The strategy of sharing seeds for random number generators to synchronize parallel processes and maintain consistency is well-established practice in areas ranging from parallel simulations to cryptographic protocols (39]. The appeal of shared random seeds stems from their ability to offer deterministic randomness, ensuring that multiple entities, operating independently, can produce synchronized and identical random outputs. Within the realm of ES, this concept was effectively harnessed by [36] to address the challenge of scalability. We also utilize the shared random seeds to
3

---

((0) L(0f)
((0)) = -- 1|0; m11
62
(0)(
60
[( 0
0 8: - -0))1(())
8
8
Contour of fitness/ (0)) L(O))
Contour of finness (0)) -110 -116
Figure 4: Illustration of one update step of typical ES and the proposed Population Bascd Gradient Encoding (PBGE) strategy. Left: using loss value L(f) directly for the fitmess f0), existing ES, lcads to an inherently noisy estimate of the gradient signal VeB. fitness as the distance to the updated model 0' obtained through BP (i.e.. f(0) = -110 0' 13).. This enables the reliable estimate of (' on the convex surface. By sampling sufficient number of perturbations
oe)] due to the noisy loss surface. Right: PBGE defines
decent gradient signal be obtained, which aligns the true gradient signal (() computed from the BP.
scale down the communication load in distributed setting, However, the key difference is that the work of [36] distributes the perturbations into multiple workers dealing with a single global objective, whereas our method generates identical perturbations across all clients, with each having distinet objective. An important consequence is that with our method, each client only needs to communicate N fitness values update the model, instead of MN N values in (36) with M denoting the number of nodes, enabling scalability regardless of the number of clients.
Federated Learning and Evolutionary Strategies. Several studies have explored the optimization of FL using ES. For instance, [40] introduced an evolutionary approach for network architecture search (NAS) in real-time FL, which minimizes local payload while optimizing model performance. Sparse evolutionary training (SET) 41 substitutes fully connected layers neural networks with sparse layers to decrease the number of model parameters. Furthermore, 42 presented the SET algorithm that optimizes neural networks in FL via a bi-objective method to maximize accuracy performance while minimizing communication overhead. Additionally, 43] introduces the MOEA/D framework 44 to the environment of FL and FLEA [5 utilized Evolutionary Algorithms FL setup at the client-level evolve models.
While these studies have made significant contributions, the present work establishes a unique way of using ES as method to reduce communication overhead in FL by transmitting fitness values instead of model parameters. In particular, the new gradient-driven fitness function essentially separates our work from the traditional utilization of ES for compression.
3 -aaed Gradient Encoding
This work focuses on the process of encoding gradient information through an identical population of models generated at both ends of some network link. Population distribution is a zero mean isotropic multivariate Gaussian with fixed covariance 2 We also adopt 'mirrored sampling' [6 47 for variance reduction where the Gaussian noise vector is instantiated with pairs of perturbations -e.
Given the reference point 0' update and V ((0) represents the gradient derived from the data, we define the fitness function (0) measure the similarity between the model parameters 0 and 0': f(0) = -Ile 0'113. This choice ensures that the gradient of the expectation, VoB,~ (f + aε)]. aligns with the actual gradient (())), effectively encoding the gradient information in the fitness values:
L(O) where r) is the learning rate in the BP-based gradient
V Vg + σe) 1 V 10 0/1 2((0- 0')
where the first equality simply follows from the assumption that is zero-mean. The visual represen- tation of this process is illustrated in Fig. 4
Eq.
2 gives 0' = 0 VoE,[-11(0 + σe) 0'| and
comparing with the BP operation 8'
have
1 v Vo + σe) - 0111).
v))) =
2
Now also utilizing Eq. I we write
1
7))
EE..ioo. oc)e)
(3)
20

---

Client
Server
[(0))n))
(()))==1
Upload ay
(0,)1==2
Fvaluate
((A)))--
C Download Ft
@
Appregate
(f(Og) Jilly = 1.2.., M)-MRRI
Reconstruct
Update
of
62 model parameter of aith partition
((,))=) fitness of a/te partition
Figure 5: Partition- based Model Parameter Compression. Illustration of dividing model parameters into K partitions and compressing them individually using PBGE.
where f is the specific distance- based fitness function defined above. Approximating the expectation by sampling, we further write
N Σ f(0 00)6
VoL(0) 2No
(4)
which shows how the gradient update information can be encoded using the fitness values f(O σ&e) corresponding to the perturbations 6, Consequently, this removes the need to evaluate each perturbation with the dataset, is done in existing ES, and the entire update process is encoded with low-cost distance measurement.
Finally, the update on / itself based on the fitness values is naturally given by
0' 2 0
Σ /(0 aa)6
2No
allowing a remote model update based on the transmitted f(0+0Ee; values with the shared knowledge of the 6 values.
The implemented algorithm consistently executes three steps: (i) Compute the target 6' through gradient descent, (ii) Implement perturbations to the model parameters and assess the perturbed parameters by computing their Euclidean distance 0', and (iii) Utilize the assessment results and encode the gradient with the fitness measures.
Partitioning, In the context of PBGE, the fitness function indicates the model distance, not the model performance on client data. This feature enables a unique partition-baat bbated approach for handling a large number of model parameters. Here, the parameters, flattened into vector 0, are split into K partitions: 8[1], 0[2],.... K]. Each partition is then effectively encoded individually using PBGE, which is advantageous when working with large models, storing large population of those may be burdensome for clients with limited memory. Partitioning allows us to compute K fitness values per each perturbation, providing K times more reference points to encode the gradient information given a population size. Hence, even with a small population size (requiring less memory), we achieve robust performance as validated by the empirical results provided in Supplementary Materials. Essentially, partitioning provides a tradeoff of memory with communication as more fitness values now need be communicated per each perturbation. This partitioning process is visualized in Fig. Notably, this partitioning technique can be used with any model architecture, regardless of its specific design, providing practical and efficient means of compressing large models.
EvoFed
EvoFed operates on the principle that the evolutionary update step depends only the fitness values given the perturbation samples. In the FL context, we can leverage this characteristic to devise an accurate yet communication-effin -ffficient strategy for model updates. This section provides detailed exposition our methodology, breaking it down into stages for clarity. This iterative process, as outlined in Algorithm [] aims gradually converge the model parameters at all nodes to an optimal solution while minimizing data transmission during each update. An overall view of our proposed methodology is depicted in Fig. g
5

---

1h -d(.. 61,)
Update
0--
Upload ftj
Server
Grudions Segnal
660
Aggregate
27
Download F.
9ce
Contour of eggregated fitness Figure 6: Local Updates and Fitness Evaluation (left) and Server/Client-side Update (right). Left: Client performs BP on local data obtain 0'.j. evaluates fitness fi., by distance measure (e.g. L2) with 0f, and uploads fu to server. Right: After obtaining the aggregated fitness Fr, all nodes update baseline model 9e according to Eq. 9
Contour of losa 4,(6)
4.1 Initial Setup
The initialization of the server and clients in EvoFed begins with the same baseline model, denoted by 8. A key assumption is that the server and all clients share the same seed (c.g., via broadcasting) for identical random population generation. This approach ensures consistent baseline models and populations across all nodes.
In this step, population of candidate solutions (in this case, models) is generated by adding random perturbations the current best solution (the baseline model). The generation of i-th member of the model population can be formulated as follows:
0 0, + +(0,
(6)
Here, (0, of) represents the perturbations sampled from multivariate normal distribution with zero mean and a shared covariance matrix oI. We also denote the population at each node at any given time t as P, 10 62 .... 0N J. where 02 represents the i-th model in the population generated by adding the i-th perturbation to the baseline model parameters, and N is the size of the population.
4.2 Local Updates and Fitness Evaluation
Each client node begins by executing BP on its local dataset, using the baseline model, O,, resulting in an updated model, 6'. Following this, the fitness of each member 0f in the local population, Pt, is evaluated. This evaluation done by measuring the similarity between 0 and 0;. The L2 norm or Euclidean distance serves the measure of this similarity. The fitness of 0f is represented f(0)):
f(0) -100 11:13
(7)
The process of local update and fitness evaluation is illustrated in Fig. 6 The fitness values are the only information that needs to be communicated among nodes. The fitness vectors significantly smaller in size compared to the model parameter vectors, which helps reduce the communication overhead. Hence, each client sends fitness vector, f, (f(O)), f())) f(0 }} corresponding all population members, to the server.
4.3 Server-side Aggregation and Update
The server's responsibility to aggregate the fitness values reported by all client nodes, forming global fitness vector F, comprising N elements, with F; representing the fitness value of the 2th member of the population. Each client's contribution to F, is weighted by their respective batch size by. giving larger influence to clients with potentially more accurate local updates.
The global fitness vector F, is computed as follows:
M
1
F.
bffe.f
(8)
where M is the total number of clients and fr.j is the fitness value vector from client j at time After the aggregation, the server broadcasts F; that each client updates the baseline model 0,.

---

Algorithm EvoFed: Federated Learning with Evolutionary Strategies
1: Input: Learning rates 7), population size N, noise std seed 8
2: Initialize: server and M clients with seed and identical parameters Op and Bo., respectively
for each communication round 0, ...,
parallel
4: for each client j in parallel do
5: 8',, Pt. (VV,)
/BBakprroaggation Update
6: Sample 4 ~ (0 of)
//ample perturbations //Intiiaiize population
7:
0i, 0
for 1, N
8:
f. = - 110 - B lli for i = N, N
// Compute fitness vector using Lu calculation
9:
end for
E, 2, byfin for I,,., N
Server averages fitness vectors I/ Server updates model using the aggregated fitness
11:
Oc+1 0c + No
a E -= F c
12: Broadcast {F), Fi,...... )
13:
for each client j in parallel do
0y-1, Oeg + No ΣN F
Client updates model using the aggregated fitness
15: end for
16:
end for
4.4 Broadcasting Fitness
Once the aggregation is complete, the server broadcasts F, to all client nodes, maintaining synchronic- ity across the network. This only involves the transmission of the fitness vector, again reducing communication overhead. The aggregated fitness vector can used by the local clients (as well as by the server, if needed) update the local models.
4.5 Client-side Update
When the global fitness vector F; is received from the server, the clients can update their local model following Eq. [5] This strategy involves the addition of weighted sum of noise vectors to the current model parameters, where the weights are aggregated fitness values:
0.+1 Bs
F
F
No
where e/ is the i-th noise vector from the population at time t.
Notably, the right side of Eq. 9 can be shown equivalent to the average of all locally updated models akin to FedAvg, i.e., is straightforward to show that
M
01-1
Σ b,0
(10)
Σ bj y=1
where Btti, is the updated model of client j at time + defined
0411 = 00
a
s 6
(11)
No 1
4.6 Convergence Analysis
Theorem 1. Suppose that [f) is the 3-smooth function, i.e., (VL VLg(v)]l S Bl - ell for any u. v, and also suppose that the variance of the stochastic gradient of D, is bounded, i.e. V (0) < B² for all j. When perturbation él sampled, a conditioned mirrored sampling applied such that 1 IN
E (e)2 < G² N EN (et)² O. Given
decreasing learning rate T) A0,3 EvoFed converges in the sense of
T-1
E [[(0))
T-1 HT
Σ TE [VL(0.)) t=0
<
oG2 + 4a
m
HT
7

---

Client
Upload E(G,)
Server
Upload E(F)
TEEs
Encryption B(G)
Aggregation
Decryption E(F)
6B8
(E(E))) E(F)
Download F
Download F
Figure 7: Privacy enhancement through Fully Homomorphic Eneryption and Trusted Execution Environments.
where Hr = Et= ttt and I," represents the minimum value of l(0)-
Given a decreasing learning rate (e.g., 7) 1+t ) it can be seen that H Ei Tte
T
increases, while 2 "i co. Consequently, the upper bound stated in Theorem approaches 0 as T grows, ensuring convergence towards a stationary point. The detailed discussions and the proof can be found in Supplementary Materials.
4.7 EvoFed and Privacy Enhancements
Unlike other FL methods, EvoFed operates on fitness measures. Encryption on smaller fitness vectors requires lower overhead compared to encryption on large model parameter vectors. Fig. 7 shows Fully Homomorphic Encryption (FHE) server while keeping individual client data confidential. For the decryption of the aggregated fitness vector, EvoFed can leverage third-party Trusted Execution Environments (TEEs), such as Intel SGX [SI], providing secure space for sensitive computations.
[4850) 50 that allows aggregation of encrypted data on the
4.8 Partial Client Participation
When FL. has to operate with a large client pool, a typical practice is to select only subset of clients in each global round. In EvoFed, this means that the newly joined clients in given round can either download the latest model or else the last & fitness vectors from the server, where the time gap from the last participation. In the latter case, the model updates from Eq. (9) can be modified to accommodate k-step updates:
N
0. = 0
a
F
t-1
(12)
No
:=
Note that even in the former case where the latest model is downloaded by the newly joined clients, the level security not compromised as far as the client-to-server messages are concerned.
Experiments
Our algorithm's effectiveness is assessed three image classification datasets: FMNIST (52) MNIST [53), and CIFAR-10 (54). Both MNIST and FMNIST contain 60,000 training samples and 10.000 samples, whereas CIFAR-I0 composed of 50,000 training samples and 10,000 test samples. We employ CNN model having 1 1k parameters for the MNIST and FMNIST datasets and a more substantial model with 2.3M parameters for CIFAR-10. A grid search has been conducted to identify the optimal performance hyperparameters for each baseline, as outlined in the results section. We take into account both global accuracy and communication costs to ascertain hyperparameters that maximize accuracy while minimizing communication overhead.
Data Distribution. We distribute the training of each dataset among clients for model training, and the performance of the final global model is evaluated using the original test set. Our experimental setup contains M 5 clients with non-IID data distribution (assigning two classes to each client).
Implementation Details. Our EvoFed framework is built using JAX [55], which facilitates extensive parallelization and, in particular, consistent random number generation across large number of nodes. We have implemented our framework on the Evosax [56] library, a convenient tool for the ES algorithm. EvoFed is configured with population size of 128 and a mini-batch size of 256 for MNIST / FMNIST and 64 for CIFAR-10. We perform ten local epochs (performing ten BP steps before fitness calculation) and train over 1, 1,000 global rounds.
Baselines. We compare the performance of the proposed EvoFed with BP, FedAvg, ES,, FedAvg with quantization (Fed-quant), and FedAvg with Sparsification (Fed-sparse). In each scenario, push

---

PHNIST
CIFAR-10
100
100
70
Clatal Arsuneyth)
20
8
20
Cu Fwc.Fadi..... 672
Dysl M4190.000
200
1930
200
402
800
1990
230
400
600
600
1300
Epocts
(a) MNIST Accuracy
(h) FMNIST Accuracy
(c) CIFAR-10 Accuracy
MNIST
FMINST
CEARR100
200
Communtaiia comm:ntatteee--g-. Sooke)
Failing
Conmin www.terr--ggggg Scokk)
que aetting
Fac-ge RETONT
105
Euffesh P%1
137
20
40
100
60
10
20
40
52
Global Accuracy:5
Global AccuracySii
Global Accuracy)))
(d) MNIST Comm. cost
(e) FMNIST Comm, cost
(1) CIFAR-10 Comm. cost
Figure 8: Performance comparison of EvoFed and baseline methods MNIST, FMNIST, and CIFAR-10 datasets. The top row displays the accuracy achieved by each method on the respective datasets, while the bottom row illustrates the communication cost associated with each method.
for maximum compression, stopping right before the model starts to show performance degradation relative to FedAvg with no compression. BP provides the upper-performance baseline, while ES serves reference emphasizing the significance of PBGE.
6 Results and Discussions
In this section, we discuss the experimental results in detail and provide further insights into the performance of EvoFed. The accuracy of EvoFed, compared with multiple baseline methods and different datasets, is shown in Fig. 8 (a). (b), and (c). Efficiently encoding and exchanging gradient information, EvoFed enhances the effectiveness of the ES algorithm across all tasks, delivering results comparable to FedAvg. Also, EvoFed achieves superior accuracy at an equivalent compression rate compared to sparsification. This suggests that utilizing a shared population of samples can reduce the information necessary for gradient compression, thereby enhancing the efficiency of the process. Fig. [ (d), (e), and (f) shows the performance of each method as function of communication load for all three datasets. It can be seen that EvoFed tends to utilize significantly less communication resources as compared to other high-aceuracy techniques.
Table summarizes the performance of different schemes on MNIST, FMNIST, and CIFAR-10 datasets, focusing on communication cost and accuracy. EvoFed achieves significantly lower commu- nication costs compared to FedAvg while maintaining competitive accuracy levels. In the MNIST dataset, EvoFed achieves an accuracy of 97.62% with mere 9.2 MB of communication load, while FedAvg achieves 98.09% accuracy at a considerably high communication cost of 73.7 MB. The effective compression achieved an impressive 98.8% which indicates that the gradient vector is condensed into just 1.2% of the fitness vector that is communicated between clients and the server. Similarly, for the FMNIST dataset, EvoFed achieves an accuracy of 84.72% with only 7.78 MB of communication, whereas FedAvg's ' accuracy is 85.53% with a communication cost of 40.99 MB. The efficiency of EvoFed becomes even more apparent in the CIFAR-I0 dataset where the model compression is over 99.7%. EvoFed achieves an accuracy of 54. 12% with a low communication cost of only 0.023 GB, surpassing FedAvg, which performs 50.22% at a communication cost of 2.134 GB. The simpler ES method actually gives better performance as well as higher communication efficiency than EvoFed for MNIST but its accuracy for other data sets is highly limited.
Additional Experiments. Fig. 9 illustrates the performance of EvoFed with varying numbers of samples N within the population and varying number of clients M. The model's I's performance is

---

MINSTT Commn Cost (MB)
FMINST Comun Cost (MIB)
CIAAR-10
Max
Max
Comm.
Cost (GB)
Max
Methods
90% Acc.
Max Ace.
Acc.
70% Acc.
Max Acc.
Acc.
45% Acc.
Max Acc.
Acc.
ES
0.1
4.6
98.30%
0.48
4.85
76.86%
0.021
37.47%
FedAvg
4.2
73.7
98.09%
0.87
40.99
85.53%
0.266
2.134
50.22%
Fed-quant
1.7
41.8
98. 15%
0.94
37.98
83.23%
0.086
0.800
49.78%
Fod-sparse
67.85%
2.78
17.13
73.17%
0.129
0.671
47.36%
EvoFed (our)
0.8
9.2
97.625
0.75
7.78
84.72%
0.004
0.023
54.1
Table 1: Performance of different schemes presented in tabular form, corresponding to Fig.
8
significantly influenced by the population size, which directly affects the algorithm's ss exploration capability and compression rate. We observe a performance improvement we increase the pop- ulation size, although at the cost of increased computation and memory usage. Nonetheless, this improvement is not linear and plateaus once sufficient samples are generated to explore the parameter space. For instance, in the case of the FMNIST dataset and a model with 11K parameters, any performance enhancement beyond generated sample size of 128 is marginal.
Fig. (b)) showcases EvoFed's performance trend as the number of clients increases. A minor performance decline is observable for some larger values of M relative to M=5. This decline could potentially be attributed to the limited data available per client and the increased variance associated with local training. Nonetheless, we believe that carefully tuning the hyperparameters based on data distribution could assist in achieving more robust performance.
Effect Population
Changing
100
100
80
2010
80
Accuscor
60
355
Accurtoy
60
122
20
11-2
(a) Varying number of population from 8 to 4096
(b) Varying number of clients from 5 to 100
Figure 9: Effect of population size (left) and number of clients (right) on EvoFed
Supplementary Materials provide further details regarding hyperparameters, model architectures, and experiments. We also include detailed ablation study with different evolutionary strategies, the population size, and the number of partitions, as well as detailed communication and computational complexity analyses.
7
Conclusion
EvoFed, the novel paradigm presented herein, unites FL and ES to offer an efficient decentralized machine learning strategy. By exchanging compact fitness values instead of extensive model param- eters, EvoFed significantly curtails communication costs. Its performance parallels FedAvg while demonstrating impressive equivalent model compression of over 98.8% FMNIST and 99. on CIFAR-10 in representative experimental settings. Consequently, EvoFed represents a substantial stride forward in FL, successfully tackling the critical issue of high communication overhead.
Acknowledgments
special acknowledgment goes to Do-yeon Kim for the valuable discussions on the convergence analysis presented in Section 4. This work supported by the National Research Foundation of Korea (NRF) grant funded by the Korean government (MSIT) (No. NRF-2019R 11--001901112202066 135), and by HITP funds from MSIT of Korea (No. 2020-0-00626).
References
[1] Jakub Konečný, H Brendan McMahan, Felix X Yu, Peter Richtárik, Ananda Theertha Suresh, and Dave Bacon. Federated learning: Strategies for improving communication efficiency. arXiv preprint arXiv:1610.05400 2016.
10

---

[2] H Brendan McMahan, Eider Moore. Daniel Ramage, Seth Hampson, and Blaise Agüera Arcas. Communication efficient urXiv:1602.05629, 2016.
tenffiicccttnnefeciintettt learning deep networks from decentralized data. arXiv preprint
[3] Jianyu Wang, Ananda Theertha Yu, and Gregory Wornell, Federated learning with matched averaging. arXiv preprint arXiv:2002.064400 2020.
[4] Dan Alistarh, Demjan Grubic, Jenry Li, Ryota Tomioka, and Milan Vojnovic. Qsgd: Communication-effiiieenn sgd via gradient quantization and encoding. In Advances Neural Information Processing Systems, pages 1709-1720, 2017.
[5] Yuzhu Mao, Zihao Zhao, Guangfeng Yan, Yang Liu, Tian Lan, Linqi Song, and Wenbo Ding. Communication-effiiiee federated learning with adaptive quantization. ACM Transactions Intelligent Systems and Technology (TIST), 13(4):1-26, 2022.
[6] Sebastian U Stich. Local sgd converges fast and communicates little. arXiv preprint 1xXiv:1805009761 2018.
[7] Virginia Smith, Chao-Kat Kai Chiang, Maziar Sanjabi, and Ameet S Talwalkar, Federated multi-task learning. In Advances in Neural Information Processing Systems, pages 4424 4434, 2017.
[8] Felix Sattler, Simon Wiedemann, Klaus-Robert Müller, and Wojciech Samek. Robust and communication-eeficceen federated learning from non-iid data. In IEEE transactions on neural networks and learning systems. 2019.
[9] Tian Li, Anit Kumar Sahu, Manzil Zaheer, Maziar Sanjabi, Ameet Talwalkar, and Virginia Smith. Fair resource allocation in federated learning. arXiv preprint 1eXXx:1905.11997 2020.
[10] Ronald J Williams. Simple statistical gradient-foloowing algorithms for connectionist reinforce- ment learning. Reinforcement learning, pages 5-32, 1992.
[11] Frank Sehnke, Christian Osendorfer, Thomas Rückstieß, Alex Graves, Jan Peters, and Jürgen Schmidhuber. Parameter-exploring policy gradients. Neural Networks, 23(4):551-559, 2010.
[12] Daan Wierstra, Tom Schaul, Tobias Glasmachers, Yi Sun, Jan Peters, and Jürgen Schmidhuber. Natural evolution strategies. The Journal of Machine Learning Research, 15(1):949 9800999999..... 2014.
[13] Xin Yao. Evolving artificial neural networks. Proceedings of the IEEE, 87(9):1233-1447, 1999.
[14] Joel Lehman and Risto Mikkkulainen. Neurocvolution. Scholarpedia, 86)::30977,2011
[15] Sebastian Risi and Julian Togelius. Neuroevolution games: State of the art and open challenges. CoRR, abs/1410.7326, 2014.
[16] Sebastian Risi and Julian Togelius. Neuroevolution in games: State of the art and open challenges. IEEE Transactions on Computational Intelligence and Al in Games, 9(1:225 41, 2015.
[17] Daniel Golovin, John Karro, Greg Kochanski, Chansoo Lee, Xingyou Song, and Qiuyi Zhang. Gradientless descent: High-dimensional zeroth-order optimization. arXiv preprint arXiv:1911.06311 2019.
[18] Robert Tjarko Lange, Tom Schaul, Yutian Chen, Chris Lu, Tom Zahavy, Valentin Dalibard, and Sebastian Flennerhag. Discovering attention-base based genetic algorithms via meta-black-box optimization. arXiv preprint arXiv:2304.03995, 2023.
[19] Felix Sattler, Simon Wiedemann, Robert Müller, and Wojciech Samek. Sparse bi- nary compression: Towards distributed deep learning with minimal communication. In 2019 International Joint Conference on Neural Networks (JJCNN), pages 1-8. IEEE, 2019.
[20] Jinjin Xu, Wenli Du, Yaochu Jin, Wangli He, and Ran Cheng. Ternary compression for communication-efice federated learning. IEEE Transactions on Neural Networks and Learning Systems, 2020.

---

[21] Eunjeong Jeong. Seungeun Oh, Hyesung Kim, Jihong Park, Mehdi Bennis, and Seong Leong-Lyun Kim. Communication-effce efficieent on-device machine learning: Federated distillation and augmen- tation under non-iid private data. arXiv preprint arXiv: 1811.1111111 1.19, 2018.
[22] Sohei Itahara, Takayuki Nishio, Yusuke Koda, Masahiro Morikura, and Koji Yamamoto. Distillation-base semi-supervised federated learning for communication-effcceeet collaborative training with non-iid private data. arXiv preprint arXiv:2008.06188 06188, 2020.
[23] Felix Sattler, Arturo Marban, Roman Rischke, and Wojciech Samek. Conmunication-efficcoe federated distillation. arXiv preprint 20I.:Xi::1120006600 2020.
[24] Tao Lin, Lingjing Kong, Sebastian U Stich, and Martin Jaggi. Ensemble distillation for robust model fusion in federated learning. Advances Neural Information Processing Systems, 33: 2351-2363, 2020.
[25] Chuhan Wu, Fangzhao Wu, Lingjuan Lyu, Yongfeng Huang, and Xing Xie. Communication- efficient federated learning via knowledge distillation. Nature communications, 13(1):1-8, 2022.
[26] Mingzhe Chen, Nir Shlezinger, H Vincent Poor, Yonina C Eldar, and Shuguang Cui. Communication--ffiioie federated learning. Proceedings of the National Academy of Sciences, 1 118(17)x20247881188 2021.
[27] Takayuki Nishio and Ryo Yonetani. Client selection for federated learning with heterogeneous resources in mobile edge. In ICC 2019-2019 IEEE international conference on communications (ICC), pages 1-7. IEEE, 2019.
[28] Canh T Dinh, Nguyen H Tran, Minh NH Nguyen, Choong Seon Hong, Wei Bao, Albert Y Zomaya, and Vincent Gramoli. Federated learning over wireless networks: Convergence analysis and resource allocation. IEEE/ACM Transactions on Networking, 29(1):398 2020.
[29] Ingo Rechenberg. Evolutionsstrategie Optimierung technischer systeme nach prinzipien der biologischen evolution. 1973.
[30] Daan Wierstra, Tom Schaul, Jan Peters, and Jürgen Schmidhuber. Fitness expectation max- imization. In Parallel Problem Solving from Nature- X: 10th International Conference, Dortmund, Germany, September 13-17, 2008. Proceedings 10, pages 337-346. Springer, 2008.
[31] Sun Yi, Daan Wierstra, Tom Schaul, and Jürgen Schmidhuber. Stochastic search using the natural gradient. In Proceedings of the 26th Annual International Conference on Machine Learning, pages 1161-168, 2009.
[32] Yi Sun, Daan Wierstra, Tom Schaul, and Jürgen Schmidhuber. Efficient natural evolution strate- gies. In Proceedings of the 11th Annual conference on Genetic and evolutionary computation, pages 539-546, 2009.
[33] Tobias Glasmachers, Tom Schaul, and Jürgen Schmidhuber. A natural evolution strategy for multi-objective optimization. In Parallel Problem Solving from Nature, PPSN XI: 11th International Conference, Kraków, Poland, September 11-15, 2010, Proceedings. Part I 11, pages 627-636 Springer, 2010.
[34] Tobias Glasmachers, Tom Schaul, Sun Yi, Daan Wierstra, and Jürgen Schmidhuber. Exponential natural evolution strategies. In Proceedings of the 12th annual conference on Genetic and evolutionary computation, pages 393-3333-00 993-400,40 2010.
[35] Tom Schaul, Tobias Glasmachers, and Jürgen Schmidhuber. High dimensions and heavy tails for natural evolution strategies. In Proceedings of the 13th annual conference on Genetic and evolutionary computation, pages 845-852, 2011.
[36] Tim Salimans, Jonathan Ho, Xi Chen, Szymon Sidor, and llya Sutskever. Evolution strategies scalable alternative to reinforcement learning. arXiv preprint arXiv: 1703 17011173344.44 2017.
12

---

[37] James C Spall. Multivariate stochastic approximation using simultaneous perturbation gradient approximation. IEEE transactions on automatic control, 37(3):332-341 1992.
[38] Yurii Nesterov and Vladimir Spokoiny, Random gradient-free minimization of convex functions. Foundations Computational Mathematics, 17:527-566, 2017.
[39] W. Diffie and M. Hellman. New directions cryptography. IEEE Transactions on Information Theory, 22(6))644-653 654, 1976. doi: 10.1 10.1109/TT.1199611556666
[40] Hangyu Zhu and Yaochu Jin. Real-time federated evolutionary neural architecture search. IEEE Transactions on Evolutionary Computation, 26(2):364-377 -78, 2021.
[41] Decebal Constantin Mocanu, Elena Mocanu, Peter Stone, Phuong H Nguyen, Madeleine Gibescu, and Antonio Liotta. Scalable training of artificial neural networks with adaptive sparse connectivity inspired by network science. Nature communications, 91): 2018.
[42] Hangyu Zhu and Yaochu Jin. Multi-objective evolutionary federated learning. IEEE transactions on neural networks and learning systems, 3104:1310 2019.
[43] Zheng-yi Chai, Chuan-dong Yang, and Ya-lun Li. Communication efficiency optimization in federated learning based on multi-objective evolutionary algorithm. Evolutionary Intelligence, pages 1-12, 2022.
[44] Qingfu Zhang and Hui Li. Moea/d: A multiobjective evolutionary algorithm based on decom- position. IEEE Transactions on evolutionary computation, 11(6):712-711 2007.
[45] Ivanoe De Falco, Antonio Della Cioppa, Tomas Koutny, Martin Ubl, Michal Krema, Um- berto Scafuri, and Ernesto Tarantino. A federated learning-inspired evolutionary algorithm: Application glucose prediction. Sensors, 23(6):2957, 2023.
[46] John Geweke. Antithetic acceleration of monte carlo integration in bayesian inference. Journal of Econometrics, 38(1-2):73-89 1988.
[47] Dimo Brockhoff, Anne Auger, Nikolaus Hansen, Dirk V Arnold, and Tim Hohm. Mirrored sampling and sequential selection for evolution strategies. In Parallel Problem Solving from Nature, PPSN XI: 11th International Conference, Kraków, Poland, September 11-15, 2010, Proceedings, Part 11, pages 11-21. Springer, 2010.
[48] Masahiro Yagisawa. Fully homomorphic encryption without bootstrapping. Cryptology ePrint Archive, 2015.
[49] Hao Chen, Kim Laine, and Rachel Player. Simple encrypted arithmetic library-seal v2. 1. In Financial Cryptography and Data Security: FC 2017 International Workshops, WAHC, BITCOIN, VOTING, WTSC, and TA, Sliema, Malta, April 7, 2017, Revised Selected Papers 21, pages 3-18. Springer, 2017.
[50] Junfeng Fan and Frederik Vercauteren. Somewhat practical fully homomorphic encryption. Cryptology ePrint Archive, 2012.
[51] Ittai Anati, Shay Gueron, Simon Johnson, and Vincent Scarlata. Innovative technology for cpu based attestation and sealing. In Proceedings of the 2nd international workshop on hardware and architectural support for security and privacy, volume 13. ACM New York, NY, USA, 2013.
[52] Han Xiao, Kashif Rasul, and Roland Vollgraf. Fashion-mnist: a novel image dataset for benchmarking machine learning algorithms. arXiv preprint arXiv: 17Xiv:170..07747, 2017.
[53] Yann LeCun, Léon Bottou, Yoshua Bengio, and Patrick Haffner. Gradient-based learning applied to document recognition. Proceedings of the IEEE, 86(1 86(11):22785 (((11)2278-2324 1998.
[54] Alex Krizhevsky, Geoffrey Hinton, et al. Learning multiple layers of features from tiny images. 2009.
13

---

[55] James Bradbury, Roy Frostig, Peter Hawkins, Matthew James Johnson, Chris Leary, Dougal Maclaurin, George Necula, Adam Paszke, Jake VanderPlas, Skye Lunderman-Milnes and Qiao Zhang. JAX: composable transformations of Python+NumPy programs, 2018. URL
http: //tgt//ggttttbbtt cwwm jax
[56] Robert Tjarko Lange. evosax: Jax- Jax-based evolution strategies. arXiv preprint arXiv:2212.04180,
2022.
14


Reviews:
[{"review_id": "hMut6LgTwK", "reviewer": "Reviewer_3tMK", "summary": "This paper introduces a new method called EvoFed, which combines Evolutionary Strategies (ES) with Federated Learning to address the challenge of high communication costs in the traditional FL setting. Instead of sending the actual model parameters, each device sends a measure of how similar its updated model is to a set of perturbed models. These perturbed models are generated in the same way on every device and server. By carefully choosing the variance and size of the perturbed models, the similarity measures can carry almost all the information about the model parameters. Since the perturbed models are smaller in size, the communication load is reduced. The authors show results in a deep CNN network trained on MNIST, FMNIST and CIFAR-10, demonstrating that EvoFed performs as well as FedAvg and compresses the model by at least 98%. ", "questions": "Please see comments above in weakness.", "limitations": "The paper could benefit from more discussion on the limitations of the proposed method. There is no obvious negative societal impact.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "1. The idea of using evolutionary schemes for model-sharing in FL is compelling and seems original.\n2. The work could have high impact (if evaluated thoroughly) and pave way for large-scale adoption of FL on edge applications.\n", "weaknesses": "1. The paper is difficult to follow at places. For instance, authors need to clarify their intuition for model partitioning in Section 3. How are the number of partitions chosen? Is this model-agnostic? If not, some empirical results or insights can help the reader reproduce the findings in their works.\n2. The paper has some hard to follow sentences and uses abbreviations that are not expanded prior (e.g., BP). A thorough proof-reading of the manuscript would be helpful.\n3. The evaluations are limited. The paper introduces a new paradigm for federated learning using evolutionary schemes which reduces communication costs significantly. In order to understand the true impact of this idea, it needs to be juxtaposed against some state-of-the-art pruning techniques for FL (e.g., Lin, Rongmei, Yonghui Xiao, Tien-Ju Yang, Ding Zhao, Li Xiong, Giovanni Motta, and Françoise Beaufays. \"Federated pruning: improving neural network efficiency with federated learning.\" arXiv preprint arXiv:2209.06359 (2022)). \n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "> The authors need to clarify their intuition for model partitioning in Section 3.\n \nEvolutionary Strategies exhibit sensitivity to the ratio of the population to parameter size. As detailed in Appendix C.1, a population size that is not adequate can hinder convergence. To assist clients with resource constraints, we introduced model partitioning. By computing fitness over multiple partitions, gradient estimation accuracy (as presented in Eq. 2) can be improved even with a small population size. Therefore, by compressing manageable portions of the model with a small population, we can enhance convergence, as elaborated in Appendix C.4.\n \n>How is the number of partitions chosen?\n \nThe number of partitions is tailored according to the available resources for clients. As delineated in Tables 1 and 2 of Appendix A.4, there's a linear correlation between increasing population and client resource usage. For resource-limited clients, elevating the number of partitions offers a viable strategy to uphold performance without overburdening resources. A detailed exploration of the effects of partitioning granularity at different population sizes can be found in Appendix C.4.\n \n> Is it model-agnostic? If not, empirical results or insights would help in reproducing the findings.\" \n \nIndeed, our partitioning approach is model-agnostic. We treat all models as data vectors, regardless of their built-in structure. This allows for versatile application across various model architectures.\n \n> The paper has unclear sentences and unexplained abbreviations (e.g., BP).\n \nWe will take a thorough review to fix any ambiguities and make sure we're clear in our writing.\n \n \n> The paper should be compared with state-of-the-art pruning techniques for FL.\n\n\nWe maintain that EvoFed is designed to integrate with other techniques, such as quantization or pruning, seamlessly. This implies that even state-of-the-art pruning methods can leverage the compression efficiency of EvoFed, further optimizing their performance. Having said that, we also provide a comparison with a SOTA technique. Unfortunately though, the paper that the reviewer suggested does not provide source codes, and the reported results there do not allow apple-apple comparison with ours either. Thus, we chose PruneFL [1], a similar paper, as our benchmark. We've detailed a comparison between PruneFL and EvoFed in Fig. 4 from the attached PDF. The results clearly show EvoFed’s reduction in communication needs compared to both PruneFL and FedAvg.\n \n[1] Jiang, Yuang, et al. \"Model pruning enables efficient federated learning on edge devices.\" IEEE Transactions on Neural Networks and Learning Systems (2022).\n \n> There should be more discussion on the limitations of the proposed method.\n \n \nOne constraint of our method pertains to the resource demands accompanying an enlarged population size. While we provide some practical ways to get around this issue (refer to Appendix A, where we analyze resource utilization in detail), the complexity of our method depends strongly on population size, and thus one has to be very cautious in designing the overall system. We will mention this in our revision."}, {"review_id": "0oz92ZbJSy", "reviewer": "Reviewer_cJ4W", "summary": "This paper offers a solution to a problem in federated learning: it's expensive to pass large model parameters back and forth from the server to the local/client nodes who train with their own data. The solution depends on the same random number generator and seed in every local node plus complete synchronization of model parameter updates. Rather than pass the model parms, distance measures (aka fitness scores) between  a population of perturbed models and a locally trained model are transmitted to the server, then aggregated and passed back to the clients who update the model parms locally.  This local (or server) model parameter update is the crux of the algorithm. The sum of all clients' distances for one perturbation model is tweaked according to an ES covariance matrix of perturbations  and added to the existing parameter with normalization and two  factors which are the learning rate parameter and inverse of the noise vector. This is repeated for every perturbation model in the local population.  This is called fitness-based information sharing and the method is called \"Population-Based Gradient Estimation'.  The population of perturbations within an Evolutionary Strategy must be carefully chosen in terms of variance (sigma) and size (M).  Because every local node references the same perturbed models and  the distances reflect the local data at each node, there is a claim of nearly full information encoding while the transmission cost of the distances is much smaller that then number of model parms.  The depth of the model update claim comes from showing that the summed differences of each client perturbation model  *and*, summed over M perturbation models,  approximates a gradient parallel to the gradient trained by back propagation.  The ES handles the accurate addition of noise relative to the perturbations and their variance. A privacy enhancement through Fully Homomorphic Encryption and the clients being TEEs/Trusted Execution Environments is also provided.\n\n", "questions": "Is mirrored sampling important?\nWhat defines convergence?\nWhat role does batch size play in the algorithm's efficiency? Are clients expected to draw different batches after each update from the server?  \nHow are parameters chosen?", "limitations": "no limitation in this scope", "rating": 6, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "This is a form of adaptive compression which is a great way to solve a communications overload problem. Most approaches transmit the updates to the model or gradient signals.  EvoFEd outperforms traditional compression methods. The L2 norm distance calculation is simple and so is the server-side batchsize-weighted aggregation and update. The client-side update of the model references noise vectors from the populations.  The integration with fully homomorphic encryption is good.", "weaknesses": "It's not entirely clear from the paper in what types of fitness landscape this will work. And, it's not clear why a parallel gradient which is then perturbed is going to lead to *optimal* convergence. \n A Natural Evolutionary Strategy is used to generate perturbations of the model's parms and the newly perturbed models are then used as benchmarks to measure a distance that reveals the gradient of one model that is trained with back propagation. The stochastic gradient ascent of NES is discarded. More information on the factored Gaussian parameter distribution that motivates its selection would be helpful.  An explanation of why the NES was chosen over other ES would improve clarity.  \nIt's also not clear how to set any of the parameters in the NES, ie population (M) and variance.\n\nThis method requires more synchronization than a federated learning model in general. ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "> It's not entirely clear from the paper in what types of fitness landscape this will work. Why would a parallel gradient, when perturbed, lead to optimal convergence?\n\nWe appreciate the reviewer raising an important question. In a nutshell, as long as the score function estimator of Eq.2 is correct (which would be the case with a sufficiently large population; see Appendix C.1), the estimated gradient $\\frac{1}{\\sigma} \\nabla_{\\theta} \\mathbb{E}_{\\epsilon \\sim \\mathcal{N}(0,1)} { f(\\theta + \\sigma \\epsilon) \\epsilon }$ is parallel to the true gradient of the loss function $\\nabla\\_\\theta L(\\theta_t)$.\nMore specifically, if we choose L2 distance as the fitness function as done in the paper, the evolution-strategy-based model update becomes identical (assuming a learning rate of 0.5) to the backpropagation-based model update (as for the proof, please refer to B.1 in Appendix).\n \n> The stochastic gradient ascent of NES is discarded.\n \nActually, the update step that happens on the aggregation of fitness vectors is the gradient ascent of NES. We tuned a separate optimizer for this and provided the hyperparameters in Appendix D.\n \n>More information on the factored Gaussian parameter distribution that motivates its selection would be helpful.\n \nFactored Gaussian has a diagonal covariance matrix, leading to reduced memory usage. This benefit is especially important in our FL application, where memory resources are critical to all individual clients.\n\n\n> An explanation of why the NES was chosen over other ES would improve clarity.\n \nNatural Evolution Strategies (NES) are typically chosen when there's a large difference between the number of parameters and the population size, especially when our objective isn't to obtain a wide range of solutions. NES is effective at estimating a single gradient because it uses uniform perturbations. The straightforward nature of OpenAI-ES not only makes it efficient (in terms of memory and CPU demands) and simplifies our convergence analysis. Plus, there's no need to manage extra covariance matrices. When comparing OpenAI-ES with other methods like CMA, PGPE, and PSO, we found that OpenAI-ES had the upper hand, as illustrated in Fig.3 of the attached PDF.\n \n> It's also not clear how to set any of the parameters in the NES, ie population (M) and variance.\n \nWe suggest adjusting parameters by gradually increasing the population size until reaching an optimal point, as described in Appendix C.1. Further parameter adjustments can be achieved through Bayesian search.\n \n \n> This method requires more synchronization than a federated learning model in general.\n\nWhen we described our algorithm in the main manuscript, we simply spoke of one local iteration per global round, but in actual experiments, multiple local updates are made for each global exchange (this will be clarified in the revision). In this sense, the synchronization requirement is no different from other FL schemes. Now, even if the reviewer means seed synchronization, the seeds can be predetermined, and again the requirement is the same as in conventional FL, where the initial models must be shared among all participants.\n \n> Is mirrored sampling important?\n \nMirror sampling is indeed very important. Mirrored sampling ensures an unbiased population. As demonstrated in [2], mirrored sampling eliminates the impact of outlier individuals and prevents ES from falling into local optima during the initial stages of training. It plays a pivotal role in theoretical analyses, especially concerning sigma, and sigma^3 sums up to zero.\n \n[2] Salimans, Tim, et al. \"Evolution strategies as a scalable alternative to reinforcement learning.\" arXiv preprint arXiv:1703.03864 (2017).\n \n \n> What defines convergence?\n \nConvergence in the context of neural networks is achieved when the training process stabilizes and the network's parameters no longer significantly improve the model's performance. In the case of our theorem, we proved that the gradient of the loss function with respect to the parameters $(\\nabla L(\\theta))$ converges to $0$ as the communication round $t$ increases. Please see section B.3 of the Supplementary Material for more detail.\n \n \n> What role does batch size play in the algorithm's efficiency?\n \nFirst, it's important to note that gradient estimation using ES remains consistent regardless of the batch size used to obtain the target gradient. The roles of batch sizes mirror traditional learning but do not influence compression rates in our setting because compression is done after getting the target update.\n \n> Are clients expected to draw different batches after each update from the server?\n \nIn our experiments, we select different batches after each update aligned with standard training practices.\n \n> How are parameters chosen?\n \nOptimal parameters are determined through a Bayesian search by running more than 200 experiments for the initial 500 rounds.\n \n "}, {"review_id": "3Uj497UL1L", "reviewer": "Reviewer_rYCA", "summary": "This paper proposes to utilize a variant of evolution strategy in federated learning framework in order to reduce its communication cost while maintaining the accuracy. The proposed approach, EvoFed, is mainly based on so called OpenAI-ES, a variant of evolution strategy intended to be used for policy optimization on decentralized environment. Differently from OpenAI-ES, which communicates the fitness of each candidate solution (cumulative reward in RL setting), EvoFed lets clients perform stochastic gradient descent locally with their local dataset and the fitness of candidate solutions are assigned based on the distance to the locally-updated parameter value. In this way, the gradient information is utilized and it is expected to improve the efficiency of the training, which is one of the most important disadvantages of evolution strategies. The authors performed a theoretical analysis of the proposed algorithm as well as empirical comparison with some baseline approaches on MNIST, FMNIST, and CIFAR10. \n", "questions": "1. (related to the 1st weakness pointed out above) the experiments are done on small image classification tasks. Because it was not clearly stated in the introduction what kind of tasks are considered as target tasks of this work, I couldn’t confirm whether these experiments reflects the target of FL. Moreover, the network size is relatively small. For MNIST and FMNIST, the number of parameters of a used CNN is only 11k. For CIFAR-10, it is increased to 2.3M, but the accuracy of the model trained by the standard back propagation was only about 70 %. It is interesting to see whether the proposed approach is still effective for greater models, where the communication cost is more important.\n\n2. (related to the 2nd and 3rd weaknesses pointed out above) Related to Theorem 1, there are several questions. \n2.1. It seems the statement in Theorem 1 contains some mistakes. In delta_M, i appears but delta_M is used as if it is independent of i. Is the summation or something is missing? Moreover, theta in delta_M is not defined. Is it theta_t? If so, is the summation or something is missing? Because of these points, it was not clear what is the point of the theorem.\n2.2. Because of the above point, I am not sure if I understand it correctly. But it looks like that it doesn’t really implies the convergence as delta_M is irrelevant to T. Having a large M implies more communication cost. The intension of this Theorem should be more clearly explained in the main text.\n2.3. The standard deviation is supposed to be proportional to the square root of T to derive the bound. If T is large, it means that the candidate solutions are far from the current center of distribution. In this situation, I coudn’t understand why it makes sense to define the fitness of the candidate solutions by the distance from the updated solution. This point should also be explained.\n2.4. What is eta? The learning rate for SGD to get theta’? Please explain it.\n2.5. Immediately after Theorem 1, the authors say “the appropriate value of alpha is 0.5 by the aforementioned reasoning.” However, I couldn’t get which part is refereed to.\n\n3. The fitness is sometimes defined by the Euclidean norm, and sometimes its square. From the derivation I think it should be squared. I found this inconsistency in Eq (3) and Eq (6) and Algorithm 1. Please check this point carefully.\n\n4. In Eq (7) b_j is introduced, but it is not used later in the paper. It seems that they are implicitly assumed to be equal. Please state it.\n\n5. Figure 8.d, e, f are visible only for high accuracy part. I suggest to show these graph in log-scale so that the differences are visible also for the low accuracy part.\n", "limitations": "No limitation is explained in the paper.", "rating": 6, "confidence": 4, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "* a novel and promising application of evolution strategies to federated learning framework to reduce the communication cost.\n* a novel fitness evaluation scheme for evolution strategies so that they can utilize stochastic gradient\n* empirical results showing performance comparative to FedAvg, a standard federated learning approach, with reduced communication cost.\n", "weaknesses": "* limited empirical evaluation: both the image size and the network size are relatively small. \n* theoretical bounds provided in the paper doesn’t probably reflect the reality.\n* limited technical novelty\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "> limited empirical evaluation: both the image and network sizes are relatively small.\n\nThanks for the comments; we have augmented our experiments to encompass larger datasets and networks. To disentangle the influences of task/dataset complexity from model architecture complexity, we undertook two specific experiments: We employed the same model used to run CIFAR10 on CIFAR100 and also fortified the model with two additional CNN layers. The comparative results of these investigations are depicted in Fig. 1 and 2 against backpropagation (BP, a centralized setup) and FedAvg.\n \nFig. 1 reveals a generally subdued performance for both BP and FedAvg on the larger CIFAR100 dataset, yet EvoFed manages to align its performance closely with that of FedAvg and even exceeds eventually. In Fig. 2, the performance gap (with many rounds) between the 2 layers and 4 layers is the same between EvoFed and BP, confirming that EvoFed accuracy improves with the network size. What we want to stress here also is that we maintained the same population size as we went from 2 layers to 4 layers with EvoFed, meaning that the compression ratio actually improved with the 4-layer EvoFed.\n \n \n> Related to Theorem 1, there are several questions\n \n> 2.1. In delta_M, i appears but delta_M is used as if it is independent of i. Is the summation or something is missing? Moreover, theta in delta_M is not defined. Is it theta_t? If so, is the summation or something is missing? Because of these points, it was not clear what is the point of the theorem.\n\n> 2.2. Because of the above point, I am not sure if I understand it correctly. But it looks like that it doesn’t really implies the convergence as delta_M is irrelevant to T. Having a large M implies more communication cost.\n \n$\\delta_M$ depends on $i$, yes. But $\\delta_M$ can be suppressed to a small value with sufficiently large $M$, regardless of $i$. And yes, $\\theta$ depends on $t$ as well, but again the sample mean estimator is close enough to the expectation across $t$ given large $M$, so that $\\delta_M$ stays marginal regardless of $i$ or $t$. On the communication cost issue, we agree with the reviewer in principle, but empirically we find that EvoFed converges with fairly reasonable values of $M$ (e.g., $M=128$ ).\n \n> 2.3. The standard deviation is supposed to be proportional to the square root of T to derive the bound. If T is large, it means that the candidate solutions are far from the current center of distribution. In this situation, I coudn’t understand why it makes sense to define the fitness of the candidate solutions by the distance from the updated solution. This point should also be explained.\n \nWe appreciate the comment. We first give a short answer: This condition on sigma was also unsettling to us, but we were able to empirically find practical $T$ values that were large enough to make the bound small while we could still find reasonable perturbation samples using the resulting sigma, albeit large. Another answer we would like to give is that we have managed to obtain an alternative bound that does not rely on the growing sigma condition. We were able to include this alternative bound in Appendix (see B.3 of Appendix, page 5). Given a chance, we hope to replace the main manuscript’s bound with this one. \n\n> 2.4. What is eta? The learning rate for SGD to get theta’?\n \nIt is indeed the learning rate for SGD to obtain theta.\n \n \n> 2.5. Immediately after Theorem 1, the authors say “the appropriate value of alpha is 0.5 by the aforementioned reasoning.” However, I couldn’t get which part is refereed to.\n \nEq.4 discusses how the gradient on the loss surface translates to the gradient on the convex fitness surface, utilizing $0.5$ as the learning rate. First, we refer to Eq.4. It is to emphasize that if we use a learning rate of $0.5$, the result of updating the model using the evolutionary strategy can be the same as the result of updating the model using backpropagation (i.e., $\\theta - 0.5 \\times \\nabla_{\\theta} |\\theta - \\theta'|^2 = \\theta - 0.5 \\times (2\\theta - 2\\theta') = \\theta'\n$). We will make this clear in our revision.\n \n \n> The fitness is sometimes defined by the Euclidean norm, and sometimes its square. From the derivation I think it should be squared. I found this inconsistency in Eq (3) and Eq (6), and Algorithm 1. Please check this point carefully.\n \nThank you; the correct fitness is the l2-square. We will ensure consistency throughout the document.\n \n \n> In Eq (7), b_j is introduced, but it is not used later in the paper. It seems that they are implicitly assumed to be equal. Please state it.\n \nYes, the batch size is assumed to remain the same across clients. We will make this clear.\n \n \n> Figure 8.d, e, f are visible only for high accuracy part. I suggest to show these graph in log-scale so that the differences are visible also for the low accuracy part.\n \nThank you for the suggestion; we will revise it accordingly. Our additional experimental results are shown in the log scale in the attached pdf.\n "}, {"review_id": "oqRxcJsgEJ", "reviewer": "Reviewer_91Ta", "summary": "This paper solves the huge communication burden problem in federated learning (FL). This paper proposes an evolutionary strategy (ES) based way to address the communication burden. Specifically, the ES only needs to transmit the fitness values among clients and server, and the fitness values could reflect the model update direction. The proposed EvoFed could compress the model more than 98.8% on FMNIST and 99.7% on CIFAR-10, nearly reducing all communication.", "questions": "1. Some important experimental studies should be moved to the main body, e.g., the ablation study of population size, which is a significant factor in EvoFed.", "limitations": "The authors provide limitations and social impacts.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The proposed EvoFed is novel and interesting. Instead of transmitting models or model updates, the authors sample several model points with noise perturbation and then calculate fitness values which could reflect the gradient directions. Transmitting fitness values could save lots of communication cost.\n2. The paper is sounded and theoretically supported. EvoFed is motivated by the population-based gradient estimation, and Equation 4 could derive the plausibility of utilizing the distance function as the fitness value function. Additionally, this paper also provide the convergence analysis to show the learning speed of population-based ES. According to Theorem 1, if the population size M is large enough, the second term of RHS could be sufficiently small.\n3. Privacy enhancement via TEEs are considered.\n4. The supp. provides abundant experimental studies including the population sizes and the partition ways.", "weaknesses": "1. The paper only studies small datasets such as FMNIST and CIFAR-10. These two benchmarks are easy to obtain good performances. More complex datasets such as CIFAR-100 or benchmarks in FedML should be investigated. On complex datasets, the reviewer thinks that a population size of 32 or 128 could not lead to qualified accuracy compared with FedAvg.\n2. The reviewer sees that the local update epoch is one in section 4.2. However, updating local models up to more epochs should be studied and reported. If the local epoch becomes larger, the reviewer thinks that the population size should be larger.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "> The paper only studies small datasets such as FMNIST and CIFAR-10. These two benchmarks are easy to obtain good performances. More complex datasets, such as CIFAR-100 or benchmarks in FedML, should be investigated.\n \nAs other reviewers have also suggested, we have extended our experiments to include larger datasets. Specifically, we've evaluated our method on CIFAR100 using the same model we employed for CIFAR10. Our scheme exceeds FedAvg with sufficient rounds, as seen in Fig. 1 of the attached PDF.  \n \n \n> On complex datasets, the reviewer thinks that a population size of 32 or 128 could not lead to qualified accuracy compared with FedAvg.\n \nYes and no. Please again see Fig. 1 of the attached PDF, where we used the same population size of 32, the same as we used for CIFAR-10. For early rounds, EvoFed falls below FedAvg. But as the rounds progress, EvoFed eventually performs better. \n \n \n> The reviewer sees that the local update epoch is one in section 4.2. However, updating local models up to more epochs should be studied and reported. If the local epoch grows, the reviewer thinks the population size should be larger.\n \nWe appreciate your attention to detail. When we described our algorithm, we simply talked about 1 local update for each global round, but we actually ran experiments with multiple local updates. For example, in Fig. 8 of the main paper. We will clarify the specification in the revision. We find that the population size does not have to grow as the local epoch increases, as the gradient estimation depends on the distance between the perturbation samples and the last updated model, no matter how many local updates are done.\n \n \n> Some important experimental studies should be moved to the main body, e.g., the ablation study of population size, which is a significant factor in EvoFed.\n \nWe agree. We will move the key results mentioned to the main body during revision."}]

Author rebuttal:
We are deeply grateful to all the reviewers for their detailed analysis and insightful comments on our work. We appreciate the recognition of the novelty and potential impact of our approach, its promising application in reducing communication costs, the successful integration with encryption methods, and our substantial experimental studies.
We have carefully considered all the concerns raised by the reviewers and conducted additional experiments to address them. We provide answers to each reviewer below.

Meta-review: This proposes EvoFed, a method that combines Evolutionary Strategies (ES) with Federated Learning to address the challenge of high communication costs in the traditional FL setting. Instead of sending the actual model parameters, each device sends a measure of how similar its updated model is to a set of perturbed models. These perturbed models are generated in the same way on every device and server. Also, EvoFed significantly reduces communication overhead and enhances privacy by providing protection against eavesdroppers who do not participate in collaborative learning. 

All the reviewers (also myself) are in favor of accepting the paper. All the major concerns have been resolved after the rebuttal/discussion period.
Decision: Accept (poster)