Federated Learning One World Seminar

Abstract: Local SGD is a popular optimization method in distributed learning, often outperforming other algorithms like mini-batch SGD in practice. Despite its success, theoretically proving the dominance of local SGD in scenarios with reasonable data heterogeneity has been challenging, creating a gap between theory and practice. In this talk, we will discuss new lower bounds for local SGD under existing first-order data heterogeneity assumptions, demonstrating that most of these assumptions are insufficient to prove the effectiveness of local update steps. Furthermore, under these same assumptions, we demonstrate the min-max optimality of accelerated mini-batch SGD, which resolves our theoretical understanding of distributed optimization for several problem classes. Our results emphasize the need for better models of data heterogeneity to understand the effectiveness of local SGD in practice. To address this, we consider higher-order smoothness and heterogeneity assumptions, providing new upper bounds that imply the dominance of local SGD over mini-batch SGD when data heterogeneity is low. In particular, in the strongly convex setting, we study the fixed-point discrepancy of local SGD and how data heterogeneity assumptions control it. Finally, we present a simple personalized variant of local SGD that rectifies several convergence issues, including the fixed-point discrepancy, and offers a better computation-communication trade-off.  

Abstract: Distributed learning has emerged as a leading paradigm for training large machine learning models. However, in real-world scenarios, participants may be unreliable or malicious, posing a significant challenge to the integrity and accuracy of the trained models. Byzantine fault tolerance mechanisms have been proposed to address these issues, but they often assume full participation from all clients, which is not always practical due to the unavailability of some clients or communication constraints. In our work, we propose the first distributed method with client sampling and provable tolerance to Byzantine workers. The key idea behind the developed method is the use of gradient clipping to control stochastic gradient differences in recursive variance reduction. This allows us to bound the potential harm caused by Byzantine workers, even during iterations when all sampled clients are Byzantine. Furthermore, we incorporate communication compression into the method to enhance communication efficiency. Under quite general assumptions, we prove convergence rates for the proposed method that match the existing state-of-the-art (SOTA) theoretical results.

Abstract: Federated learning is a powerful distributed optimization framework in which multiple clients collaboratively train a global model without sharing their raw data. In this work, we tackle the personalized version of the federated learning problem. In particular, we ask: throughout the training process, can each client in a federated system identify a subset of similar clients and collaboratively train with just those clients? In the affirmative, we formalize this problem as a stochastic optimization problem, achieving optimal convergence rates for a large class of loss functions. We propose simple iterative algorithms which identify clusters of similar clients and train a personalized model-per-cluster, using local client gradients and flexible constraints on the clusters. The convergence rates of our algorithms asymptotically match those obtained if we knew the true underlying clustering of the clients and are provably robust in the Byzantine setting where some fraction of the clients are malicious.

Abstract: Byzantine robustness has been gaining a lot of attention due to the growth of the interest in collaborative and federated learning. To address this issue, different Byzantine-robust mechanisms have been proposed in recent years. In this talk, I will focus on the approaches based on variance reduction and, in particular, present our recent paper where variance reduction allows us to significantly improve prior convergence guarantees.