We consider the problem of running a distributed machine learning algorithm on the cloud. This imposes several challenges. In particular, cloud instances may have different performances/speeds. To fully leverage the performance of the instances, we want to characterize their speed and potentially use the fastest ones. To explore the speed of the instances while exploiting them (assigning computational tasks), we use the theory of multi-armed bandits (MABs).

The goal of the research intership is to start by implementing existing theoretical algorithms [1] and possibly adapting them based on the experimental observations.

[1] M. Egger, R. Bitar, A. Wachter-Zeh and D. Gündüz, Efficient Distributed Machine Learning via Combinatorial Multi-Armed Bandits, submitted to IEEE Journal on Selected Areas in Communications (JSAC), 2022.

• Information Theory
• Machine Learning Basics
• Python (Intermediate Level)

In federated learning, a machine learning model shall be trained on private user data with the help of a central server, the so-called federator. This setting differs from other machine learning settings in that the user data shall not be shared with the federator for privacy reasons and/or to decrease the communication load of the system.

Even though only intermediate results are shared, extra care is necessary to guarantee data privacy. An additional challenge arises if the system includes malicious users that breach protocol and send corrupt computation results.

The goal of this work is to design, implement and analyze coding- and information-theoretic solutions for privacy and security in federated learning.

• Coding Theory (e.g., Channel Coding)
• Information Theory
• Machine Learning Basics

The rapid growth of data being recorded and processes per day necessitates to outsource large computations to external workers. In neural network training and inference processes, matrix multiplication is a core computation. That is why a large body of research is concerned with designing schemes for distributed matrix multiplication that allows for tolerating straggling workers (i.e., slow or even unresponsive workers). While reconcstructing the exact result can be costly, approximate schemes can improve on the efficiency while only sacrificing little in terms of accuracy. In this project, the student should study existing approximate matrix multiplication schemes and improve on the achievable rate while maintaining low error rates.

- Coding Theory (e.g., Channel Coding)
- Information Theory

Since the introduction of federated learning in [1], we can observe a rapidly growing body of research. In particular, we face challenges with respect to privacy, security and efficiency. The first half of this research internship aims at implementing a generic framework for simulating decentralized optimization procedures in a federated leraning setting. During the second half and with the help of the framework, the student should analyze the performance of selected state-of-the-art schemes.

• Coding Theory (e.g., Channel Coding)
• Information Theory
• Machine Learning Basics
• Python (Intermediate Level)

In the initially proposed federated learning setting [1], the federator observes partial gradient computations of all clients contributing to a decentralized training procedure. However, clients might send malicious (corrupt) computations to harm the training process on purpose. Considering this model, security against malicious clients can be ensured by running statistics on the partial results [2, 3]. For example, clients’ results that differ significantly from the vast majority of responses can be excluded from the training process. In recent works, secure aggregation of partial work was proposed [4]. The goal is to let the master only observe the sum of all local models, and by this to enhance the privacy level of the clients’ data. These works, however, complicate the use of statistics to account for corrupt partial computations as the master only observes the aggregated result. The goal of this research internship is to review related literature on secure federated learning including their limitations, and to explore possible approaches to ensure security against potentially corrupt results while preserving privacy of the clients’ data.

[1] B. McMahan, E. Moore, D. Ramage, S. Hampson, and B. A. y. Arcas, “Communication-Efficient Learning of Deep Networks from Decentralized Data,” vol. 54, pp. 1273–1282, 20--22 Apr 2017.

[2] P. Blanchard, E. M. El Mhamdi, R. Guerraoui, and J. Stainer, “Machine Learning with Adversaries: Byzantine Tolerant Gradient Descent,” in Advances in Neural Information Processing Systems, 2017, vol. 30.

[3] Z. Yang and W. U. Bajwa, “ByRDiE: Byzantine-Resilient Distributed Coordinate Descent for Decentralized Learning,” IEEE Transactions on Signal and Information Processing over Networks, vol. 5, no. 4, pp. 611–627, Dec. 2019.

[4] K. Bonawitz et al., “Practical Secure Aggregation for Privacy-Preserving Machine Learning,” Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security. 2017. doi: 10.1145/3133956.3133982.

• Coding Theory (e.g., Channel Coding)
• Information Theory

In distributed computing, a main node wants to outsource computationally expensive tasks, e.g., large matrix-matrix multiplications, to a set of workers in a parallelized manner. However, some of the workers might be slow or even unresponsive. As waiting for the completion of all workers' tasks diminishes the benefits of distributed computing, the idea to use coding theory to mitigate the effect of stragglers [1] triggered a large body of research. As part of this, one line of work is concerned with hierarchical coded computing. The student should study the schemes introduced in [2, 3], for which the extended version [4] serves as additional input. Optionally, the student can investigate if we can adapt these scheme to keep the data information-theoretically private from a set of z colluding workers.

[1] K. Lee, M. Lam, R. Pedarsani, D. Papailiopoulos and K. Ramchandran, "Speeding up distributed machine learning using codes," 2016 IEEE International Symposium on Information Theory (ISIT), 2016, pp. 1143-1147, doi: 10.1109/ISIT.2016.7541478.

[2] S. Kiani, N. Ferdinand and S. C. Draper, "Hierarchical coded matrix multiplication," 2019 16th Canadian Workshop on Information Theory (CWIT), 2019, pp. 1-6, doi: 10.1109/CWIT.2019.8929896.

[3] N. Ferdinand and S. C. Draper, "Hierarchical Coded Computation," 2018 IEEE International Symposium on Information Theory (ISIT), 2018, pp. 1620-1624, doi: 10.1109/ISIT.2018.8437473.

[4] S. Kianidehkordi, N. Ferdinand and S. C. Draper, "Hierarchical Coded Matrix Multiplication," in IEEE Transactions on Information Theory, vol. 67, no. 2, pp. 726-754, Feb. 2021, doi: 10.1109/TIT.2020.3036763.

• Coding Theory (e.g., Channel Coding)
• Linear Algebra
• Information Theory (optional)