-

-

-

Communication efficiency is a major and well-studied premise in federated learning (FL). Various compression schemes have been proposed to alleviate prohibitively high communication costs. In stochastic formulations of FL, principled approaches to compression can substantially improve existing measures. Minimal random coding (MRC), introduced in [1], leverages side information, common randomness, and tools from importance-sampling. The authors of [2] proposed to use MRC for stochastic FL and show substantial improvements in various domains.

The task of the student is to understand the principles of the proposed compression schemes and their application to stochastic FL for different learning narratives. The student should analyze where the substantial communication improvements originate from, and what open problems remain.

[1] Marton Havasi, Robert Peharz, and Jose Miguel ´ Hernandez-Lobato. Minimal random code learning: ´ Getting bits back from compressed model parameters. In International Conference on Learning Representations, 2019.

[2]  Berivan Isik, Francesco Pase, Deniz Gunduz, Sanmi Koyejo, Tsachy Weissman, and Michele Zorzi. Adaptive compression in federated learning via side information. In International Conference on Artificial Intelligence and Statistics, pp. 487–495, 2024.

Fully decentralized schemes do not require a central entity and have been studied in [1, 2]. These works aim to reach consensus on a desirable machine learning model among all clients. We can mainly distinguish between i) gossip algorithms [3] where clients share their result with all neighbors, naturally leading to high communication complexities, and ii) random walk approaches like [4, 5] where the model is communicated only to a specific neighbor until matching certain convergence criteria. Such random walk approaches are used in federated learning to reduce the communication load in the network and at the clients’ side.

The main task of the student is to study the work in [5], which additionally accounts for the heterogeneity of the clients’ data. Further, drawbacks and limitations of the proposed approach should be determined.

[1] J. B. Predd, S. B. Kulkarni, and H. V. Poor, “Distributed learning in wireless sensor networks,” IEEE Signal Process. Mag., vol. 23, no. 4, pp. 56–69, 2006.

[2] S. Boyd, N. Parikh, E. Chu, B. Peleato, J. Eckstein et al., “Distributed optimization and statistical learning via the alternating direction method of multipliers,” Found. Trends Mach. Learn., vol. 3, no. 1, pp. 1–122, 2011.

[3] S. S. Ram, A. Nedi ?c, and V. V. Veeravalli, “Asynchronous gossip algorithms for stochastic optimization,” in IEEE Conf. Decis. Control. IEEE, 2009, pp. 3581–3586.

[4] D. Needell, R. Ward, and N. Srebro, “Stochastic gradient descent, weighted sampling, and the randomized kaczmarz algorithm,” Adv. Neural Inf. Process. Syst., vol. 27, 2014.

[5] G. Ayache, V. Dassari, and S. E. Rouayheb, “Walk for learning: A random walk approach for federated learning from heterogeneous data,” arXiv preprint arXiv:2206.00737, 2022.

Prerequisites