Author name cluster

Rafael Pinot

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

12 papers

2 author rows

ICML Conference 2024 Conference Paper

Byzantine-Robust Federated Learning: Impact of Client Subsampling and Local Updates

Youssef Allouah
Sadegh Farhadkhani
Rachid Guerraoui
Nirupam Gupta
Rafael Pinot
Geovani Rizk
Sasha Voitovych

The possibility of adversarial (a. k. a. , Byzantine) clients makes federated learning (FL) prone to arbitrary manipulation. The natural approach to robustify FL against adversarial clients is to replace the simple averaging operation at the server in the standard $\mathsf{FedAvg}$ algorithm by a robust averaging rule. While a significant amount of work has been devoted to studying the convergence of federated robust averaging (which we denote by $\mathsf{FedRo}$), prior work has largely ignored the impact of client subsampling and local steps, two fundamental FL characteristics. While client subsampling increases the effective fraction of Byzantine clients, local steps increase the drift between the local updates computed by honest (i. e. , non-Byzantine) clients. Consequently, a careless deployment of $\mathsf{FedRo}$ could yield poor performance. We validate this observation by presenting an in-depth analysis of $\mathsf{FedRo}$ tightly analyzing the impact of client subsampling and local steps. Specifically, we present a sufficient condition on client subsampling for nearly-optimal convergence of $\mathsf{FedRo}$ (for smooth non-convex loss). Also, we show that the rate of improvement in learning accuracy diminishes with respect to the number of clients subsampled, as soon as the sample size exceeds a threshold value. Interestingly, we also observe that under a careful choice of step-sizes, the learning error due to Byzantine clients decreases with the number of local steps. We validate our theory by experiments on the FEMNIST and CIFAR-$10$ image classification tasks.

Details

NeurIPS Conference 2024 Conference Paper

Fine-Tuning Personalization in Federated Learning to Mitigate Adversarial Clients

Youssef Allouah
Abdellah El Mrini
Rachid Guerraoui
Nirupam Gupta
Rafael Pinot

Federated learning (FL) is an appealing paradigm that allows a group of machines(a. k. a. clients) to learn collectively while keeping their data local. However, dueto the heterogeneity between the clients’ data distributions, the model obtainedthrough the use of FL algorithms may perform poorly on some client’s data. Personalization addresses this issue by enabling each client to have a differentmodel tailored to their own data while simultaneously benefiting from the otherclients’ data. We consider an FL setting where some clients can be adversarial, andwe derive conditions under which full collaboration fails. Specifically, we analyzethe generalization performance of an interpolated personalized FL framework in thepresence of adversarial clients, and we precisely characterize situations when fullcollaboration performs strictly worse than fine-tuned personalization. Our analysisdetermines how much we should scale down the level of collaboration, accordingto data heterogeneity and the tolerable fraction of adversarial clients. We supportour findings with empirical results on mean estimation and binary classificationproblems, considering synthetic and benchmark image classification datasets

PDF Details DOI

NeurIPS Conference 2024 Conference Paper

Revisiting Ensembling in One-Shot Federated Learning

Youssef Allouah
Akash Dhasade
Rachid Guerraoui
Nirupam Gupta
Anne-Marie Kermarrec
Rafael Pinot
Rafael Pires
Rishi Sharma

Federated Learning (FL) is an appealing approach to training machine learning models without sharing raw data. However, standard FL algorithms are iterative and thus induce a significant communication cost. One-Shot FL (OFL) trades the iterative exchange of models between clients and the server with a single round of communication, thereby saving substantially on communication costs. Not surprisingly, OFL exhibits a performance gap in terms of accuracy with respect to FL, especially under high data heterogeneity. We introduce Fens, a novel federated ensembling scheme that approaches the accuracy of FL with the communication efficiency of OFL. Learning in Fens proceeds in two phases: first, clients train models locally and send them to the server, similar to OFL; second, clients collaboratively train a lightweight prediction aggregator model using FL. We showcase the effectiveness of Fens through exhaustive experiments spanning several datasets and heterogeneity levels. In the particular case of heterogeneously distributed CIFAR-10 dataset, Fens achieves up to a $26. 9$% higher accuracy over SOTA OFL, being only $3. 1$% lower than FL. At the same time, Fens incurs at most $4. 3\times$ more communication than OFL, whereas FL is at least $10. 9\times$ more communication-intensive than Fens.

PDF Details DOI

ICML Conference 2023 Conference Paper

On the Privacy-Robustness-Utility Trilemma in Distributed Learning

Youssef Allouah
Rachid Guerraoui
Nirupam Gupta
Rafael Pinot
John Stephan

The ubiquity of distributed machine learning (ML) in sensitive public domain applications calls for algorithms that protect data privacy, while being robust to faults and adversarial behaviors. Although privacy and robustness have been extensively studied independently in distributed ML, their synthesis remains poorly understood. We present the first tight analysis of the error incurred by any algorithm ensuring robustness against a fraction of adversarial machines, as well as differential privacy (DP) for honest machines’ data against any other curious entity. Our analysis exhibits a fundamental trade-off between privacy, robustness, and utility. To prove our lower bound, we consider the case of mean estimation, subject to distributed DP and robustness constraints, and devise reductions to centralized estimation of one-way marginals. We prove our matching upper bound by presenting a new distributed ML algorithm using a high-dimensional robust aggregation rule. The latter amortizes the dependence on the dimension in the error (caused by adversarial workers and DP), while being agnostic to the statistical properties of the data.

Details

ICML Conference 2023 Conference Paper

Robust Collaborative Learning with Linear Gradient Overhead

Sadegh Farhadkhani
Rachid Guerraoui
Nirupam Gupta
Lê-Nguyên Hoang
Rafael Pinot
John Stephan

Collaborative learning algorithms, such as distributed SGD (or D-SGD), are prone to faulty machines that may deviate from their prescribed algorithm because of software or hardware bugs, poisoned data or malicious behaviors. While many solutions have been proposed to enhance the robustness of D-SGD to such machines, previous works either resort to strong assumptions (trusted server, homogeneous data, specific noise model) or impose a gradient computational cost that is several orders of magnitude higher than that of D-SGD. We present MoNNA, a new algorithm that (a) is provably robust under standard assumptions and (b) has a gradient computation overhead that is linear in the fraction of faulty machines, which is conjectured to be tight. Essentially, MoNNA uses Polyak’s momentum of local gradients for local updates and nearest-neighbor averaging (NNA) for global mixing, respectively. While MoNNA is rather simple to implement, its analysis has been more challenging and relies on two key elements that may be of independent interest. Specifically, we introduce the mixing criterion of $(\alpha, \lambda)$-reduction to analyze the non-linear mixing of non-faulty machines, and present a way to control the tension between the momentum and the model drifts. We validate our theory by experiments on image classification and make our code available at https: //github. com/LPD-EPFL/robust-collaborative-learning.

Details

NeurIPS Conference 2023 Conference Paper

Robust Distributed Learning: Tight Error Bounds and Breakdown Point under Data Heterogeneity

Youssef Allouah
Rachid Guerraoui
Nirupam Gupta
Rafael Pinot
Geovani Rizk

The theory underlying robust distributed learning algorithms, designed to resist adversarial machines, matches empirical observations when data is homogeneous. Under data heterogeneity however, which is the norm in practical scenarios, established lower bounds on the learning error are essentially vacuous and greatly mismatch empirical observations. This is because the heterogeneity model considered is too restrictive and does not cover basic learning tasks such as least-squares regression. We consider in this paper a more realistic heterogeneity model, namely $(G, B)$-gradient dissimilarity, and show that it covers a larger class of learning problems than existing theory. Notably, we show that the breakdown point under heterogeneity is lower than the classical fraction $\frac{1}{2}$. We also prove a new lower bound on the learning error of any distributed learning algorithm. We derive a matching upper bound for a robust variant of distributed gradient descent, and empirically show that our analysis reduces the gap between theory and practice.

PDF Details

ICML Conference 2022 Conference Paper

Byzantine Machine Learning Made Easy By Resilient Averaging of Momentums

Sadegh Farhadkhani
Rachid Guerraoui
Nirupam Gupta
Rafael Pinot
John Stephan

Byzantine resilience emerged as a prominent topic within the distributed machine learning community. Essentially, the goal is to enhance distributed optimization algorithms, such as distributed SGD, in a way that guarantees convergence despite the presence of some misbehaving (a. k. a. , Byzantine ) workers. Although a myriad of techniques addressing the problem have been proposed, the field arguably rests on fragile foundations. These techniques are hard to prove correct and rely on assumptions that are (a) quite unrealistic, i. e. , often violated in practice, and (b) heterogeneous, i. e. , making it difficult to compare approaches. We present RESAM (RESilient Averaging of Momentums), a unified framework that makes it simple to establish optimal Byzantine resilience, relying only on standard machine learning assumptions. Our framework is mainly composed of two operators: resilient averaging at the server and distributed momentum at the workers. We prove a general theorem stating the convergence of distributed SGD under RESAM. Interestingly, demonstrating and comparing the convergence of many existing techniques become direct corollaries of our theorem, without resorting to stringent assumptions. We also present an empirical evaluation of the practical relevance of RESAM.

Details

NeurIPS Conference 2022 Conference Paper

Towards Consistency in Adversarial Classification

Laurent Meunier
Raphael Ettedgui
Rafael Pinot
Yann Chevaleyre
Jamal Atif

In this paper, we study the problem of consistency in the context of adversarial examples. Specifically, we tackle the following question: can surrogate losses still be used as a proxy for minimizing the $0/1$ loss in the presence of an adversary that alters the inputs at test-time? Different from the standard classification task, this question cannot be reduced to a point-wise minimization problem, and calibration needs not to be sufficient to ensure consistency. In this paper, we expose some pathological behaviors specific to the adversarial problem, and show that no convex surrogate loss can be consistent or calibrated in this context. It is therefore necessary to design another class of surrogate functions that can be used to solve the adversarial consistency issue. As a first step towards designing such a class, we identify sufficient and necessary conditions for a surrogate loss to be calibrated in both the adversarial and standard settings. Finally, we give some directions for building a class of losses that could be consistent in the adversarial framework.

PDF Details

ICML Conference 2021 Conference Paper

Mixed Nash Equilibria in the Adversarial Examples Game

Laurent Meunier
Meyer Scetbon
Rafael Pinot
Jamal Atif
Yann Chevaleyre

This paper tackles the problem of adversarial examples from a game theoretic point of view. We study the open question of the existence of mixed Nash equilibria in the zero-sum game formed by the attacker and the classifier. While previous works usually allow only one player to use randomized strategies, we show the necessity of considering randomization for both the classifier and the attacker. We demonstrate that this game has no duality gap, meaning that it always admits approximate Nash equilibria. We also provide the first optimization algorithms to learn a mixture of classifiers that approximately realizes the value of this game, \emph{i. e. } procedures to build an optimally robust randomized classifier.

Details

ICML Conference 2020 Conference Paper

Randomization matters How to defend against strong adversarial attacks

Rafael Pinot
Raphael Ettedgui
Geovani Rizk
Yann Chevaleyre
Jamal Atif

\emph{Is there a classifier that ensures optimal robustness against all adversarial attacks? } This paper tackles this question by adopting a game-theoretic point of view. We present the adversarial attacks and defenses problem as an \emph{infinite} zero-sum game where classical results (\emph{e. g. } Nash or Sion theorems) do not apply. We demonstrate the non-existence of a Nash equilibrium in our game when the classifier and the Adversary are both deterministic, hence giving a negative answer to the above question in the deterministic regime. Nonetheless, the question remains open in the randomized regime. We tackle this problem by showing that any deterministic classifier can be outperformed by a randomized one. This gives arguments for using randomization, and leads us to a simple method for building randomized classifiers that are robust to state-or-the-art adversarial attacks. Empirical results validate our theoretical analysis, and show that our defense method considerably outperforms Adversarial Training against strong adaptive attacks, by achieving 0. 55 accuracy under adaptive PGD-attack on CIFAR10, compared to 0. 42 for Adversarial training.

Details

NeurIPS Conference 2019 Conference Paper

Theoretical evidence for adversarial robustness through randomization

Rafael Pinot
Laurent Meunier
Alexandre Araujo
Hisashi Kashima
Florian Yger
Cedric Gouy-Pailler
Jamal Atif

This paper investigates the theory of robustness against adversarial attacks. It focuses on the family of randomization techniques that consist in injecting noise in the network at inference time. These techniques have proven effective in many contexts, but lack theoretical arguments. We close this gap by presenting a theo- retical analysis of these approaches, hence explaining why they perform well in practice. More precisely, we make two new contributions. The first one relates the randomization rate to robustness to adversarial attacks. This result applies for the general family of exponential distributions, and thus extends and unifies the previous approaches. The second contribution consists in devising a new upper bound on the adversarial risk gap of randomized neural networks. We support our theoretical claims with a set of experiments.

PDF Details

UAI Conference 2018 Conference Paper

Graph-based Clustering under Differential Privacy

Rafael Pinot
Anne Morvan
Florian Yger
Cédric Gouy-Pailler
Jamal Atif

In this paper, we present the first differentially private clustering method for arbitraryshaped node clusters in a graph. This algorithm takes as input only an approximate Minimum Spanning Tree (MST) T released under weight differential privacy constraints from the graph. Then, the underlying nonconvex clustering partition is successfully recovered from cutting optimal cuts on T. As opposed to existing methods, our algorithm is theoretically well-motivated. Experiments support our theoretical findings.

Details