\documentclass{article}

% Recommended, but optional, packages for figures and better typesetting:
\usepackage{microtype}
\usepackage{graphicx}
\usepackage{subfigure}
\usepackage{booktabs} 

% hyperref makes hyperlinks in the resulting PDF.
% If your build breaks (sometimes temporarily if a hyperlink spans a page)
% please comment out the following usepackage line and replace
% \usepackage{icml2026} with \usepackage[nohyperref]{icml2026} above.
\usepackage{hyperref}
% Attempt to make hyperref and algorithmic work together better:
\newcommand{\theHalgorithm}{\arabic{algorithm}}

\usepackage[accepted]{icml2026}

\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{mathtools}
\usepackage{amsthm}
\usepackage{bm}
\usepackage{mathrsfs}
 
\usepackage[capitalize,noabbrev]{cleveref}

\theoremstyle{plain}
\newtheorem{theorem}{Theorem}[section]
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{corollary}[theorem]{Corollary}
\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{assumption}[theorem]{Assumption}
\theoremstyle{remark}
\newtheorem{remark}[theorem]{Remark}

\usepackage{comment}
\usepackage{mathtools}
\usepackage{amsmath,amsfonts,amssymb,amsthm}
\usepackage{bbm}
\usepackage{enumitem}
\usepackage{cleveref}
\usepackage{tikz}
\usetikzlibrary{calc}
\makeatletter
\newtheorem*{rep@theorem}{\normalfont\bfseries\rep@title}
\newcommand{\newreptheorem}[2]{%
\newenvironment{rep#1}[1]{%
  \par\medskip
 \def\rep@title{#2~\ref{##1}}%
 \begin{rep@theorem}}%
 {\end{rep@theorem}}}
\makeatother
\newreptheorem{theorem}{Theorem}
\newreptheorem{lemma}{Lemma}
\newreptheorem{proposition}{Proposition}

\newcommand\mc{\mathcal}
\newcommand\mb{\mathbb}
\newcommand\indep{\perp\!\!\!\perp}
\DeclarePairedDelimiter\ceil{\lceil}{\rceil}
\DeclarePairedDelimiter\floor{\lfloor}{\rfloor}
\DeclareMathOperator{\Tr}{Tr}
\definecolor{noattack-green}{rgb}{0, 0.5, 0}
\definecolor{poisoning-blue}{rgb}{0, 0, 0.5}
\definecolor{byzantine-red}{rgb}{0.5, 0, 0}
\newcommand{\projSGD}{\mathrm{projected}\text{--}\mathrm{SGD}}

\allowdisplaybreaks%

\usepackage[disable,textsize=tiny]{todonotes}
%\usepackage{todonotes}
\newcommand{\comm}[3][noinline]{\todo[#1, size=\tiny]{#2: #3}}
\newcommand{\tb}[1]{\textcolor{orange}{#1}}
\newcommand{\tbtodo}[2][noinline]{\comm[color=orange,#1]{TB}{#2}}
\newcommand{\bat}[1]{\textcolor{magenta}{#1}}
\newcommand{\batodo}[2][noinline]{\comm[color=magenta,#1]{BL}{#2}}
\newcommand{\au}[1]{\textcolor{green}{#1}}
\newcommand{\autodo}[2][noinline]{\comm[color=green,#1]{AB}{#2}}
\newcommand{\ngp}[1]{\textcolor{red}{#1}}
\newcommand{\ngtodo}[2][noinline]{\comm[color=red,#1]{NG}{#2}}

\icmltitlerunning{Byzantine Failures Hurt Generalization More than Data Poisoning}

\begin{document}

\twocolumn[
\icmltitle{Tight Stability Bounds for Robust Distributed Learning: \\Byzantine Failures Hurt Generalization More than Data Poisoning}

\begin{icmlauthorlist}
\icmlauthor{Thomas Boudou}{yyy}
\icmlauthor{Batiste Le Bars}{comp}
\icmlauthor{Nirupam Gupta}{sch}
\icmlauthor{Aurélien Bellet}{yyy}
\end{icmlauthorlist}

\icmlaffiliation{yyy}{PreMeDICaL team, Inria, Idesp, Inserm, Université de Montpellier, Montpellier, France}
\icmlaffiliation{comp}{Univ. Lille, Inria, CNRS, Centrale Lille, UMR 9189, CRIStAL, F-59000 Lille, France}
\icmlaffiliation{sch}{Department of Computer Science, University of Copenhagen, Copenhagen, Danemark}

\icmlcorrespondingauthor{Thomas Boudou}{thomas.boudou@inria.fr}

% You may provide any keywords that you
% find helpful for describing your paper; these are used to populate
% the "keywords" metadata in the PDF but will not be shown in the document
\icmlkeywords{Machine Learning, ICML}

\vskip 0.3in
]

\printAffiliationsAndNotice{}  

\begin{abstract} 
  Robust distributed learning algorithms aim to maintain reliable performance despite the presence of misbehaving workers. 
  Such misbehaviors are commonly modeled as \textit{Byzantine failures}, allowing arbitrarily corrupted communication, 
  or as \textit{data poisoning}, a weaker form of corruption restricted to local training data.
  While prior work shows similar optimization guarantees for both models, an important question remains: \textit{How do these threat models impact generalization?} 
  %Empirical evidence suggests a gap, yet it remains unclear whether it is unavoidable or merely an artifact of suboptimal attacks. 
  We show, for the first time, a fundamental gap in generalization guarantees between the two threat models: Byzantine failures yield strictly worse rates than those achievable under data poisoning.
  Our findings are based upon a tight algorithmic stability analysis of robust distributed learning. 
  Specifically, with $f$ out of $n$ workers misbehaving, we prove that: 
  \textit{(i)} under data poisoning, the uniform algorithmic stability of a robust distributed learning algorithm 
  % with an optimal optimization guarantee 
  degrades by an additive factor $\varTheta \big( \frac{f}{n-f} \big)$; whereas 
  \textit{(ii)} under Byzantine failures, the degradation factor is $\Omega \big( \sqrt{ \frac{f}{n-2f}}\, \big)$.
\end{abstract}



\input{./sections/opening.tex}

\input{./sections/section-II-problem-formulation.tex}

\input{./sections/section-III-stability-analysis.tex}

\input{./sections/section-IV-numerical-experiments.tex}

\input{./sections/related-work.tex}

\input{./sections/payoff-and-closure.tex}

\section*{Impact Statement}
This paper presents work whose goal is to advance the field of machine learning. There are many potential societal consequences of our work, none of which we feel must be specifically highlighted here.


\section*{Acknowledgements}
The work of Thomas Boudou and Aurélien Bellet is supported by grant ANR 22-PECY-0002 IPOP (Interdisciplinary Project on Privacy) project of the
Cybersecurity PEPR.\

\bibliography{references}
\bibliographystyle{icml2026}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% APPENDIX
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\newpage
\appendix
\onecolumn

\section*{Organization of the appendix}

The supplementary materials are organized as follows.

\begin{itemize}
    \item \Cref{gen-and-Byzantine} contains deferred proofs for~\Cref{II-Background-motivation}, focusing on the link between uniform stability and generalization bounds under Byzantine failures and data poisoning.
    \item \Cref{loss-regularities} summarizes the regularity assumptions and includes key expansivity results.
    \item \Cref{deferred-sec-3-1} provides detailed proofs of~\Cref{byz-sgd-ub-convex,lb-smea-gd-linear-byzantine} presented in~\Cref{main-byzantine}.
    \item \Cref{deferred-sec-3-2} provides detailed proofs of~\Cref{th-poisoning-convex-smea-main-text,lower-bound-gd-poisonous-merged} presented in~\Cref{main-poisonous}.
    \item \Cref{app:nonconvex} provides additional bounds for nonconvex smooth optimization.
    \item \Cref{deferred-section-4} specifies details supporting~\Cref{V-experimental}, including generalization error computations~(\Cref{gen-error-linear}) and numerical experiments~(\Cref{appD-numerical-experiment}).
    \item \Cref{refined-heterogeneity} gives example of results with refined bounded heterogeneity and bounded variance assumptions instead of the more general bounded gradients assumption.
    \item \Cref{IV-excessrisk} states high-probability excess risk bounds for robust distributed learning under smooth and strongly convex loss functions.
    \item \Cref{additional-discussions} discusses additional important points not included in the main text.
\end{itemize}

\input{./appendices/appA-gen-byzantine.tex}

\input{./appendices/appB-regularity.tex}

\input{./appendices/appD1-empirical-cov.tex}

\input{./appendices/appD2-stability-byzantine.tex}

\input{./appendices/appE1-stability-poisonous.tex}

\input{./appendices/appE2-lowerbound-smea-gd.tex}

\input{./appendices/appE3-lowerbound-smea-sgd.tex}

\input{./appendices/appF-stability-nonconvex.tex}

\input{./appendices/appG-numerical-experiments.tex}

\input{./appendices/appH-heterogeneity.tex}

\input{./appendices/appI-excess-risk.tex}

\input{./appendices/appJ-additional-discussion.tex}

\end{document}