EvoFed: Leveraging Evolutionary Strategies for Communication-Efficient Federated Learning

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.

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. 2. 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. 3. Privacy enhancement via TEEs are considered. 4. 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. 2. 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.

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.

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

3 good

Presentation

3 good

Contribution

3 good

Limitations

The authors provide limitations and social impacts.

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.

Strengths

* a novel and promising application of evolution strategies to federated learning framework to reduce the communication cost. * a novel fitness evaluation scheme for evolution strategies so that they can utilize stochastic gradient * empirical results showing performance comparative to FedAvg, a standard federated learning approach, with reduced communication cost.

Weaknesses

* limited empirical evaluation: both the image size and the network size are relatively small. * theoretical bounds provided in the paper doesn’t probably reflect the reality. * limited technical novelty

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. 2. (related to the 2nd and 3rd weaknesses pointed out above) Related to Theorem 1, there are several questions. 2.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. 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. The intension of this Theorem should be more clearly explained in the main text. 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. 2.4. What is eta? The learning rate for SGD to get theta’? Please explain it. 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. 3. 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. 4. 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. 5. 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.

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

2 fair

Presentation

2 fair

Contribution

2 fair

Limitations

No limitation is explained in the paper.

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.

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. 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. It's also not clear how to set any of the parameters in the NES, ie population (M) and variance. This method requires more synchronization than a federated learning model in general.

Questions

Is mirrored sampling important? What defines convergence? What role does batch size play in the algorithm's efficiency? Are clients expected to draw different batches after each update from the server? How are parameters chosen?

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

2 fair

Presentation

2 fair

Contribution

2 fair

Limitations

no limitation in this scope

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%.

Strengths

1. The idea of using evolutionary schemes for model-sharing in FL is compelling and seems original. 2. The work could have high impact (if evaluated thoroughly) and pave way for large-scale adoption of FL on edge applications.

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. 2. 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. 3. 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)).

Questions

Please see comments above in weakness.

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

2 fair

Contribution

3 good

Limitations

The paper could benefit from more discussion on the limitations of the proposed method. There is no obvious negative societal impact.

Thank you for your response

I am satisfied with the authors response. The bound derived in the appendix makes more sense to me, and I agree that replacing the current theorem with the one in the appendix is beneficial.