source_extract/sections/section-IV-numerical-experiments.tex

\section{Generalization Gap}\label{V-experimental}

While we proved tight stability bounds for robust distributed learning in~\Cref{III-main}, it remains unclear how the uncovered stability gap translates into generalization error under the two threat models.
To address this, we focus on the smooth convex setting with $\mathrm{SMEA}$ and construct a data distribution where the generalization error is not merely upper bounded by uniform stability but is in fact \emph{proportional} to it, independently of the threat model.

\begin{lemma}\label{th:stability-to-gen}
    Consider the setting described in~\Cref{II-problem-formulation}, with $m=1$, regardless of the assumed threat model.
    There exist $\ell \in {\mb{R}}^{\Theta \times \mc{Z}}$ such that $\forall z \in \mc{Z}, \ell(\cdot; z)$ is $C$-Lipschitz, $L$-smooth and convex,
    data distributions ${\{p_i\}}_{i\in\mc{H}}$ over $\mc{Z}$, 
    such that for any distributed algorithm $\mc{A}$, we have
    \begin{multline}\label{stability-to-gen-bis}
        \left| \mb{E}_{\mc{A}, \mc{S} \sim \otimes_{i\in\mc{H}} \left(p_i^{\otimes m}\right) } \big[ R_{\mc{H}}(\mc{A(\mc{S})}) - \widehat{R}_{\mc{H}}(\mc{A(\mc{S})}) \big] \right| \\
        = \frac{1}{4(n-f)}\sup_{z \in \mc{Z}} \mb{E}_{\mc{A}} \left[ \ell(\mc{A}(S); z) - \ell(\mc{A}(S'); z) \right],
    \end{multline}
    where the dependence on the threat model arises solely through the stability term.
\end{lemma}
Lemma~\labelcref{th:stability-to-gen} establishes a direct equality between the generalization gap and algorithmic stability, confirming that the threat model's impact is captured by the latter---a result that may be of independent interest for deriving lower bounds on generalization using stability tools.
Notably, This construction unifies the lower-bound settings (i.e., honest datasets and loss function) shared by both worst-case data poisoning and Byzantine attack scenarios.
Therefore, our findings reveal a fundamental separation: there exist data distributions and Byzantine attacks whose generalization error is strictly larger (in terms of convergence rate) than that of the worst-case data poisoning attack, as demonstrated by the following theorem, proved in~\Cref{gen-error-linear}. %\looseness=-1

\begin{theorem}\label{th:generalization-gap}
    Consider the setting of~\Cref{th:stability-to-gen}, where $\frac{n}{3} \leq f < \frac{n}{2}$, $\mc{A} \in \{ \mathrm{GD}, \mathrm{SGD} \}$ with $\mathrm{SMEA}$. 
    Then, there exist $\ell \in {\mb{R}}^{\Theta \times \mc{Z}}$ such that $\forall z \in \mc{Z}, \ell(\cdot; z)$ is $C$-Lipschitz, $L$-smooth and convex,
    data distributions ${\{p_i\}}_{i\in\mc{H}}$ over $\mc{Z}$, and a Byzantine attack such that, for any data poisoning attack, we have
    \begin{equation}\label{quotient-gap}
        \frac{\mathcal{E}^{\mathrm{byz}}_{gen}}{\mathcal{E}^{\mathrm{pois}}_{gen}} \in \Omega\left( \frac{n-f}{\sqrt{f(n-2f)}} \right),
    \end{equation}
    where $\mathcal{E}^{\mathrm{byz}}_{gen}$ and $\mathcal{E}^{\mathrm{pois}}_{gen}$ denote generalization errors under the Byzantine and data poisoning attacks, respectively.
\end{theorem}
Theorem~\labelcref{th:generalization-gap} quantifies the separation between the threat models, proving that the generalization error under Byzantine attacks asymptotically dominates that of data poisoning.
Specifically, the factor $\frac{n-f}{\sqrt{f(n-2f)}}$ grows from a minimum of $2$, when $f=\frac{n}{3}$, to exceed $\frac{\sqrt{n}}{2}$ as $f$ approaches the breakdown point ($f=\frac{n}{2}-1$, or $\frac{n-1}{2}$).
Below, we complement our theoretical results
with numerical experiments that validate the analysis and provide further insights. 
Then, we discuss the broader intuition underlying the emergence of this generalization gap between the two threat models.



\textbf{Numerical validation.}
We numerically instantiate the construction used in proving the stability lower bound under data poisoning, which coincides with the Byzantine case when $f\geq\frac{n}{3}$ (see~\Cref{lb-smea-gd-convex,lowerbound-byzantine} for further details), with $m=1$.
Under this configuration, we can use~\Cref{th:stability-to-gen} as demonstrated in~\Cref{th:generalization-gap}.
For our experiments, we fix the learning rate and the Lipschitz coefficient $\gamma = C = 1$, the number of epochs $T=5$, the number of total workers $n=15$ and vary the number of misbehaving workers $f$ from $1$ to $7$.
As expected, we observe that under data poisoning, our theoretical upper bound (scaled by the factor $\frac{1}{4(n-f)}$ from Equation~\ref{stability-to-gen-bis}) closely matches the empirically measured generalization error (\Cref{fig:numerical}), confirming the practical tightness of our analysis in this setting, including the constant factors.

Next, we evaluate the system's performance under the Byzantine attack described in the proof of the stability lower bound in~\Cref{lb-smea-gd-linear-byzantine}.
In particular, for each $f$, we fix $\mc{H}$ to maximize honest gradients' variance. 
The Byzantine workers then accelerate the divergence of the parameters, either in the positive or negative direction, triggered by a specific event that depends on the observed communication.
Numerically, this is achieved by adaptively crafting updates that remain within the aggregation rule’s selection range (see~\Cref{appD-numerical-experiment} for details). 
We observe that this Byzantine attack results in a significantly higher generalization error that grows with the number of Byzantine workers. 
Importantly, when $f\geq\frac{n}{3}$, the attack produces an error greater than the lower bound reported in~\Cref{lb-smea-gd-linear-byzantine}.%, scaled by $\frac{1}{4(n-f)}$.
This was expected as our data distribution produces datasets matching the worst-case one crafted for the Byzantine lower bound. 
The gap between the two curves illustrates that our attack optimizes the numerical constant in the lower bound.

Interestingly, even when $f<\frac{n}{3}$, Byzantine failures continue to induce substantially greater generalization error than worst-case data poisoning, emphasizing that the gap persists even with a moderate fraction of misbehaving workers.
In fact, as $f<\frac{n}{3}$ decreases, it becomes increasingly challenging (but not impossible) to simultaneously maintain maximal honest gradients' variance and amplify the influence of Byzantine workers.
In the absence of an order-of-magnitude larger lower bound under Byzantine failures in the regime $f < n/3$, it is natural to ask whether the generalization gap also extends to this low-to-moderate fraction of misbehaving workers. 
While our numerical experiments support this intuition, the open question remains whether the gap is merely a constant factor or truly an order of magnitude.
\looseness=-1

In summary, our numerical experiment demonstrates that Byzantine failures can have a significantly greater generalization error than worst-case data poisoning across all regimes, from low to high fractions of misbehaving workers.
Remarkably, this also confirms the fundamental generalization gap between Byzantine and data poisoning threat models, as highlighted above in~\Cref{th:generalization-gap}.

\begin{figure*}[ht!]
    %\vspace{.3in}
    \begin{center}
        \includegraphics[width=0.63\linewidth]{materials/numerical_analysis_aistats_gen.pdf}
        \caption{Generalization Error Under Optimal Poisoning And Tailored Byzantine Attacks.}\label{fig:numerical}
    \end{center}
    %\vspace{.3in}
\end{figure*}



\textbf{Why threat model differences affect generalization, but not optimization?}
In contrast to~\citet{farhadkhani2024relevance}, who show similar optimization error guarantees for both threat models, our work reveals a gap in generalization error.
The key intuition is as follows. 
Optimization analysis focuses on how accurately the descent direction is estimated at each step, whereas generalization analysis examines the algorithm's sensitivity to individual training samples, independent of how informative the estimated direction is for optimization. 
In the worst case, both corruptions similarly impair optimization direction estimation. 
However, as discussed in Section~\ref{III-main}, stability analysis benefits from the additional regularity and non-adaptive nature of data poisoning.
\looseness=-1

Specifically, optimization error analysis relies on the smoothness of the empirical loss over honest workers \citep[e.g., Theorem 1 in][]{pmlr-v206-allouah23a} to control its decrease along the optimization trajectory, typically via terms like $\widehat{R}_{\mathcal{H}}(\theta_{t+1}) - \widehat{R}_{\mathcal{H}}(\theta_t)$ or $\|\nabla \widehat{R}_{\mathcal{H}} (\theta_t)\|^2_2$. 
This smoothness-based control applies equally to both threat models, as the regularity of corrupted gradients is not invoked. 
In contrast, stability analysis aims to bound the difference $\ell(\theta_t, z) - \ell(\theta'_t, z)$ between the losses along two optimization trajectories $\theta_t$ and $\theta'_t$ produced by neighboring datasets. 
Here, regularities can be exploited under data poisoning---where corrupted updates remain gradients of a smooth loss function (cf.\ proof of \Cref{th-poisoning-convex-smea-main-text})---but not under Byzantine failures, which require an intermediate comparison step (cf.\ proof of \Cref{byz-sgd-ub-convex}).


Furthermore, prior work~\citep{pmlr-v206-allouah23a} shows that for the optimization error, $(f,\kappa)$-robustness with $\kappa \in \mathcal{O}(f/n)$ suffices to achieve an upper bound under Byzantine failures that matches the lower bound for poisoned data~\citep[Theorem 1 \& Proposition 1]{pmlr-v206-allouah23a}.
Hence, this bound cannot be improved using the regularity of corrupted gradients.
%\looseness=-1