Tuan-Anh NGUYEN

Abstract :

Distributed learning has been studied intensively in recent years due to its practicality for a wide range of applications, where data transfer incurs high costs in terms of privacy and communication bandwidth. In this context, it is crucial to design algorithms that are suitable for edge devices with limited computational and communication capabilities, while still achieving optimal performance in a distributed setting. However, this is a challenging task as the algorithm’s performance depends on multiple factors such as the overlay communication network, computational capabilities, and the nature of the data on each device. The majority of research in distributed learning has focused on the offline setting, where data is stored locally, and the objective function remains static throughout the learning process. However, this offline setting becomes unrealistic for many machine learning applications, as data is generated continuously. In this thesis, we study the problem of distributed online learning, where multiple agents learn from streams of data generated at local devices to reach a consensus on a global objective function. We propose projection-free algorithms that are well-suited for a distributed setting. These algorithms are carefully designed to achieve optimal regret bounds in various scenarios of online and distributed learning, including delayed feedback and zeroth-order feedback for convex and non-convex functions. We conduct an extensive theoretical study and experimentally validate the performance of our algorithms by comparing them with existing ones on real-world problems. Furthermore, we provide an empirical study on the energy consumption of training federated learning (FL) on edge devices, taking into account data heterogeneity and the trade-off between computation and communication when varying the number of devices and data partitioning.