source_extract/sections/opening.tex

\section{Introduction}\label{I-intro}
With the proliferation of large-scale data and pervasive connectivity, distributed learning has evolved into a fundamental paradigm in modern AI~\citep{MAL-083}.
From federated smartphones to geo-distributed datacenters, algorithms now orchestrate millions of workers toward shared objectives. 
Yet, unlike the idealized setting of perfectly cooperative workers, real-world systems face a range of adversarial misbehaviors, broadly categorized under the umbrella of Byzantine failures~\citep{gerraoui-byzantine-primer}.
Encompassing everything from intermittent data corruption and hardware failure to sophisticated attacks, these failures threaten the reliability of distributed learning algorithms.

Robust distributed learning aims to maintain strong learning guarantees despite the presence of such misbehaviors. %\looseness=-1
The prevailing approach is to model a fraction of workers as corrupted, either Byzantine---able to send arbitrarily corrupted updates---or poisoned, where corruption is limited to local training data. 
While~\citet{farhadkhani2024relevance} surprisingly showed that both threat models yield similar empirical risk guarantees, experiments consistently observe significantly worse generalization---i.e., higher risk on unseen data---under Byzantine failures~\citep[cf.][and additional discussion in~\Cref{additional-discussions}]{pmlr-v206-allouah23a, karimireddy2022byzantinerobust}.
Whether this gap reflects an inherent difference in adversarial power or only the suboptimality of practical attacks remains unknown.
We address this open problem with the first theoretical analysis of the generalization gap between Byzantine failures and data poisoning.

To this end, we use algorithmic stability~\citep{Bousquet2002StabilityAG} to quantify generalization resilience against both forms of attacks. 
In particular, uniform stability---which measures an algorithm's sensitivity to the replacement of a single training example---offers a worst-case, distribution-free, and algorithm-centric perspective on generalization. This stands in contrast to approaches based on uniform convergence~\citep{vapnik1998statistical}, PAC-Bayes~\citep{mcallester1999pac}, or mutual information~\citep{russo2019much}, which provide less direct insight into algorithm-specific behavior.
This makes stability well-suited for addressing the open question under consideration, as it enables a focused analysis of the potential harm posed by different threat models on the generalization performance of robust learning algorithms. 

\paragraph{Summary of our contributions.} 
We formalize a unified framework to analyze generalization error of robust distributed learning under different threat models (\Cref{II-Background-motivation}).
Our results rigorously expose a significant gap in the generalization guarantees between Byzantine failures and data poisoning. 
Specifically, for convex objective we prove the following:
(1) When $f$ workers among $n$ are Byzantine, the uniform algorithmic stability of robust distributed ($\mathrm{S}$)$\mathrm{GD}$ with $\mathrm{SMEA}$---an optimal high-dimensional robust aggregation rule---degrades with an additive factor $\Omega \big( \sqrt{ \frac{f}{n-2f} } \big)$ for $f\geq\frac{n}{3}$ (\Cref{main-poisonous}).
(2) This factor improves to $\varTheta \big( \frac{f}{n-f} \big)$ when we restrict the misbehavior to poisoned data (\Cref{main-byzantine}). 
\Cref{table-comparaison} summarizes our results.
Lastly, we show that the above difference yields a fundamental generalization gap between the two threat models (\Cref{V-experimental}) by establishing a proportional relationship between stability and generalization (\Cref{th:stability-to-gen}).
This latter result may also be of independent interest, as it identifies a setting in which stability exactly characterizes generalization, enabling lower bounds on generalization via stability arguments.

\begin{table}[t]
\centering
\begin{tabular}{l|c|c}
    Regime & Byzantine failures & Data poisoning \\ \hline
    $f < \frac{n}{3}$ & $\mc{O}(\sqrt{\frac{f}{n-f}})$ & $\varTheta(\frac{f}{n-f})$ \\
    $\frac{n}{3} \leq f < \frac{n}{2+\nu}$ & $\varTheta(\sqrt{\frac{f}{n-f}})$ &  $\varTheta(\frac{f}{n-f})$ \\
    $f \sim \frac{n}{2}$ & $\Omega(\sqrt{\frac{f}{n-2f}})$ & $\varTheta(\frac{f}{n-f})$  \\
\end{tabular}
\caption{
    Uniform stability overhead in different threat models for convex loss functions.
    Here, $\mathcal{O}(\cdot)$ and $\Omega(\cdot)$ denote upper and lower bounds up to absolute constant factors.
}\label{table-comparaison}
\end{table}

% \textbf{Conflict of interest disclosure.} The authors report no conflicts of interest.