source_extract/sections/section-III-stability-analysis.tex

\section{(In)stability of Robust Distributed Learning}\label{III-main}

In this section, we first derive upper bounds on the stability of robust distributed $(\mathrm{S})\mathrm{GD}$ under general $(f, \kappa)$-robust aggregation rules. 
We next analyze $\mathrm{SMEA}$ to derive lower bounds under Byzantine failures, as well as tight upper and lower bounds for the special case of data poisoning.
Our results show a fundamental gap in stability between the two threat models. 
Definitions of function regularity are given in~\Cref{loss-regularities}.

\subsection{The Case of Byzantine Failures}\label{main-byzantine}

\textbf{Upper bounds.} We start by deriving uniform stability upper bounds for convex optimization. Proofs are deferred to~\Cref{stability-analysis-classic-byzantine}.
\begin{theorem}\label{byz-sgd-ub-convex}
    Consider the setting described in~\Cref{II-problem-formulation} under Byzantine failures.
    Let $\mc{A} \in \{\mathrm{GD}, \mathrm{SGD}\}$ with a $(f, \kappa)$-robust aggregation rule $F$.
    Suppose $\forall z \in \mc{Z}$, $\ell(\cdot;z)$ $C$-Lipschitz and $L$-smooth, and $\mc{A}$ is run for $T\in\mb{N}^*$ iterations with $\gamma \leq \frac{1}{L}$.
    \begin{enumerate}[label=\roman*, topsep=-3pt, itemsep=2pt, parsep=0pt, leftmargin = 23pt]
        \item[\textit{(i)}] If $\ell(\cdot;z)$ is convex $\forall z \in \mc{Z}$, then the uniform stability of $\mc{A}$ is upper bounded by
        \begin{equation}\label{smea-byz-cvx-eq}  
            \textstyle 2 \gamma C^2 T \left( \sqrt{\kappa} + \frac{1}{(n-f)m} \right).
        \end{equation}
        \item[\textit{(ii)}] If $\ell(\cdot;z)$ is $\mu$-strongly convex $\forall z \in \mc{Z}$, then the uniform stability of $\mc{A}$ is upper bounded by
        \begin{equation}\label{smea-byz-stgcvx-eq}  
            \textstyle \frac{2 C^2}{\mu} \left( \sqrt{\kappa} + \frac{1}{(n-f)m} \right).
        \end{equation}
    \end{enumerate}
\end{theorem}
\begin{proof}[Proof sketch.]\label{proof-sketch-byzantine}
Denote $\{{\theta_t\}}_{t \in [T]}$ and ${\{\theta'_t\}}_{t \in [T]}$ the coupled optimization trajectories resulting from two neighboring datasets $\mc{S}, \mc{S}'$.
%, for $T$ iterations of $\mc{A} \in \{ \mathrm{GD}, \mathrm{SGD} \}$ with $F$ a $(f, \kappa)$-robust aggregation rule, and learning rate $\gamma$.
In the context of stability analysis via parameter sensitivity, we track how the parameters diverge along these optimization trajectories. 
To do so, we decompose the analysis by introducing an intermediate comparison between the robust update $G^F_{\gamma}$ and the averaging over honest workers update $G^\mc{A}_{\gamma}$.
This enables us to leverage either the regularity of the loss function or the robustness property of the aggregation rule. 
This approach is motivated by the fact that Byzantine vectors cannot be assumed to exhibit regularities when comparing them.
%Hence, using $G^F_{\gamma} (\theta_t) - G^{F\prime}_{\gamma} (\theta'_t) = G^F_{\gamma} (\theta_t) - G^\mc{A}_{\gamma} (\theta_t) + G^\mc{A}_{\gamma} (\theta_t) - G^{\mc{A}\prime}_{\gamma} (\theta'_t) + G^{\mc{A}\prime}_{\gamma} (\theta'_t) - G^{F\prime}_{\gamma} (\theta'_t)$, and the triangular inequality yields
By adding and subtracting $G^\mc{A}_{\gamma}(\theta_t)$ and $G^{\mc{A}\prime}_{\gamma}(\theta'_t)$, the triangle inequality yields
%\looseness=-1
%_{\mc{A}}
% \begin{multline*}
%     \textstyle 
%     \mb{E} \| G^F_{\gamma} (\theta_t) - G^{F\prime}_{\gamma} (\theta'_t) \|_2
%     \leq 
%     \underbrace{\mb{E} \| G^{\mc{A}}_{\gamma} (\theta_t) - G^{\mc{A}\prime}_{\gamma} (\theta'_t) \|_2}_{\vcentcolon= A} \\
%     + 
%     \underbrace{\mb{E} \left[ \| G^F_{\gamma} (\theta_t) - G^{\mc{A}}_{\gamma} (\theta_t) \|_2 + \| G^{F\prime}_{\gamma} (\theta'_t) - G^{\mc{A}\prime}_{\gamma} (\theta'_t) \|_2 \right]}_{\vcentcolon= B}.
% \end{multline*}
\begin{equation*}
    \textstyle 
    \mb{E}_{\mc{A}} \| G^F_{\gamma} (\theta_t) - G^{F\prime}_{\gamma} (\theta'_t) \|_2
    \leq A + B + B',
\end{equation*}
where $A = \mb{E}_{\mc{A}} \| G^{\mc{A}}_{\gamma} (\theta_t) - G^{\mc{A}\prime}_{\gamma} (\theta'_t) \|_2$,
$B = \mb{E} \| G^F_{\gamma} (\theta_t) - G^{\mc{A}}_{\gamma} (\theta_t) \|_2$,
and $B' = \mb{E} \| G^{F\prime}_{\gamma} (\theta'_t) - G^{\mc{A}\prime}_{\gamma} (\theta'_t) \|_2$.
We then bound $A$ using standard stability arguments~\citep{hardt2016train},
and $B, B'$ with the $(f, \kappa)$-robust property, the Jensen's inequality and boundedness of honest gradients,
\begin{multline*}
    B + B'
    \leq 2 \gamma \mb{E}_{\mc{A}} \sqrt{\kappa \| \Sigma_{\mc{H}, t} \|_{\operatorname{sp}}} 
    \leq 2 \gamma \sqrt{\kappa \mb{E}_{\mc{A}}\| \Sigma_{\mc{H}, t} \|_{\operatorname{sp}}} \\
    \leq 2 \gamma \sqrt{\kappa} C. \qedhere
\end{multline*}
\end{proof}


When there are no Byzantine workers ($f = 0$, hence $\kappa = 0$), both~\eqref{smea-byz-cvx-eq} and~\eqref{smea-byz-stgcvx-eq} reduce to the classical stability bounds established in~\citet{hardt2016train}, known to be tight~\citep{pmlr-v180-zhang22b}.
However, when $f > 0$, the analysis reveals a degradation by an additive term of order $\mathcal{O}\left(\sqrt{\kappa}\right)$.
In the convex setting, this degradation accumulates over the $T$ iterations, whereas in the strongly convex case, it appears as a one-time term independent of $T$.%\looseness=-1

\textbf{Lower bounds.} Since $\kappa \geq \frac{f}{n-2f}$~\citep[Proposition 6]{pmlr-v206-allouah23a}, the additive term in~\Cref{byz-sgd-ub-convex} is lower bounded by $\sqrt{\frac{f}{n-2f}}$. 
We show that this bound is tight by deriving the following lower bound, proved in~\Cref{lowerbound-byzantine}.%\looseness=-1
\begin{theorem}\label{lb-smea-gd-linear-byzantine}
    Consider the setting in~\Cref{II-problem-formulation} under Byzantine failures and assume $\frac{n}{3} \leq f < \frac{n}{2}$.
    Let $\mc{A} \in \{ \mathrm{GD}, \mathrm{SGD} \}$, with $\mathrm{SMEA}$. 
    Suppose $\mc{A}$ is run for $T \in \mb{N}^*$ iterations ($T \in \Omega(m)$ for $\mathrm{SGD}$) with learning rate $\gamma$.
    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,
    and neighboring datasets such that the uniform stability of $\mc{A}$ is lower bounded by\looseness=-1
    \begin{equation}\label{smea-byz-lb-eq}
        \textstyle \Omega \left( \gamma C^2 T \left( \sqrt{\frac{f}{n-2f}} + 1 + \frac{1}{(n-f)m} \right) \right).
    \end{equation}
\end{theorem}
\begin{proof}[Proof sketch.]
Let $C, L \in \mb{R}_+^*$ and let $\ell(\theta;z)=z\theta$, $\theta\in\mathbb{R}$, $z\in[-C,C]$, which is $C$-Lipschitz, $L$-smooth and convex. 
In this particular case, the $\mathrm{SMEA}$ rule amounts to picking the subset of size $n-f$ with smallest variance. 
Our proof relies on three key elements.

\textit{(i)} We maximize the variance among honest gradients by dividing them into two equal-sized subgroups positioned at the boundary of the Lipschitz constraint.
More precisely, $\frac{n-f}{2}$ honest workers have datasets with $m$ identical samples equal to $C$, the remaining $\frac{n-f}{2}$ have samples equal to $-C$.
Hence, this set of $n-f$ values has, at each iteration, a variance equal to $C^2$. 

\textit{(ii)} When $f \ge \frac{n}{3}$, Byzantine workers can craft updates that cause $\mathrm{SMEA}$ to entirely discard one honest subgroup while outweighing the influence of the other. 
Specifically, if Byzantine workers send $\beta = C\left( 1 + \frac{1}{2}\frac{n-f}{\sqrt{f(n-2f)}} \right)$ at each iteration, then the subgroup consisting of $f \geq \frac{n-f}{2}$ Byzantine workers together with $n-2f \leq \frac{n-f}{2}$ honest workers sending $C$ forms the subset with the lowest variance, equal to $C^2/4 < C^2$.
Consequently, under this configuration, the parameter at step $T$ becomes $\theta_T = - \gamma C T \left(1 + \frac{1}{2} \sqrt{\frac{f}{n-2f}}\right)$.

\textit{(iii)} Finally, we exploit the fact that Byzantine workers can observe all communications and adapt their behavior accordingly.
Specifically, we can define an event that triggers them to switch their communicated value $\beta$ to an arbitrarily large number.
For instance, if a single sample from a honest worker is changed from $C$ to $0$—defining a neighboring dataset—the server receives a different average $\frac{m-1}{m} C < C$ that triggers the Byzantine workers.
The choice of an arbitrary large value is a matter of convenience, ensuring that the perturbed run diverges in the positive direction at a rate of $\theta_T^\prime = \frac{\gamma C T}{(n-f)m}$. 
As, in this setting, stability is proportional to $\left|\theta_T - \theta_T^\prime \right|$, this concludes the proof sketch.%\looseness=-1
\end{proof}

Note that, for $\mathrm{SMEA}$, $\sqrt{\kappa} \in \mathcal{O}\Big(\sqrt{\frac{f}{n-f}}\big(1 + \frac{f}{n-2f}\big)\Big)$~\citep[Proposition 5.1]{pmlr-v202-allouah23a}.
Plugging this in our upper-bound and considering the regime $n/3 \leq f \leq n/(2+\nu)$ for some constant $\nu>0$, our upper and lower bounds become tight at a rate of $\varTheta\Big(\sqrt{\frac{f}{n-f}}\Big)$, providing a precise characterization of stability under Byzantine failures.
For $f < n/3$, we lack a strong lower bound; nonetheless, we investigate this regime numerically in~\Cref{V-experimental} (and discuss it in~\Cref{additional-discussions}), yielding valuable insights into the transition from few to many misbehaving workers.

Crucially, the lower bound above cannot be replicated under data poisoning, due to points \textit{(ii)} and \textit{(iii)} in the proof sketch.
Unlike Byzantine workers, who can send arbitrary and adaptive updates, poisoned workers are constrained by the loss function's regularity and by being committed to a fixed dataset before the algorithm begins. 
The next section formally proves a stability gap between the two threat models.
\looseness=-1

\subsection{The Case of Data Poisoning}\label{main-poisonous}

Unlike our previous bounds, which account for the arbitrariness of Byzantine vectors, we now leverage the regularity of poisoned gradients in data poisoning to derive tighter stability bounds for robust distributed learning with $\mathrm{SMEA}$.
The proof sketches below  further elucidate the key distinctions between the threat models.
%Extensions to a wider class of aggregation rules are discussed throughout.
Formal proofs are in~\Cref{stability-poisonous,lb-smea-gd,lb-smea-sgd}.

\textbf{Upper bounds.} We start by proving a tighter upper bound under data poisoning.

\begin{theorem}\label{th-poisoning-convex-smea-main-text}
    Consider the setting described in~\Cref{II-problem-formulation} under data poisoning.
    Let $\mc{A} \in \{\mathrm{GD}, \mathrm{SGD}\}$, with $\mathrm{SMEA}$. 
    Suppose $\ell(\cdot;z)$ $C$-Lipschitz and $L$-smooth $\forall z \in \mc{Z}$, and $\mc{A}$ is run for $T\in\mb{N}^*$ iterations with $\gamma \leq \frac{1}{L}$.
    \begin{enumerate}[label=\roman*, topsep=-3pt, itemsep=2pt, parsep=0pt, leftmargin = 23pt]
        \item[\textit{(i)}] If $\ell(\cdot;z)$ is convex $\forall z \in \mc{Z}$, then the uniform stability of $\mc{A}$ is upper bounded by
        \begin{equation}\label{smea-poisoning-cvx-eq}
            2 \gamma C^2 T \left( \frac{f}{n-f} + \frac{1}{(n-f)m} \right).
        \end{equation}
        \item[\textit{(ii)}] If $\ell(\cdot;z)$ is $\mu$-strongly convex $\forall z \in \mc{Z}$, then the uniform stability of $\mc{A}$ is upper bounded by
        \begin{equation}\label{smea-poisoning-strgcvx-eq}
            \frac{2 C^2}{\mu} \left( \frac{f}{n-2f} + \frac{1}{(n-2f)m} \right).
        \end{equation}
    \end{enumerate}
\end{theorem}
\begin{proof}[Proof sketch.]
    We consider two runs of~\eqref{eq:update}, with $\mathrm{SMEA}$ and $\mathrm{GD}$, on neighboring datasets, initialized with $\theta_0 = \theta_0'$. 
    Denote $\delta_t = \|\theta_t-\theta_t'\|_2$.
    At each step $t$, $\mathrm{SMEA}$ selects subsets of workers $S^*_t$ and $S'^*_t$ of size $n-f$. 
    The key insight is to decompose the update rule based on the intersection $I_t = S^*_t \cap S'^*_t$, where $n-2f \leq |I_t| \leq n-f$,
    and to compare the updates as a gradient step on the intersection $I_t$, $G_{I_t}(\theta_t) = \theta_t - \frac{\gamma}{n-f} \sum_{i \in I_t} \nabla \widehat{R}_i (\theta_t)$, plus a perturbation term from the symmetric difference $\Delta_t = (S^*_t \setminus S'^*_t) \cup (S'^*_t \setminus S^*_t)$, $|\Delta_t| \leq 2f$.
    The proof then relies on two key elements, where we bound the update~\eqref{eq:update} difference by
    \begin{multline}\label{eq:ub-sketch-inter}
        \textstyle \delta_{t+1} \leq \| G_{I_t}(\theta_t) - G_{I_t}(\theta'_t) \|_2 \\
        + \frac{\gamma}{n-f} \| \sum_{i \in S^*_t \setminus S'^*_t} \nabla \widehat{R}_i (\theta_t) - \sum_{i \in S'^*_t \setminus S^*_t} \nabla \widehat{R}'_i (\theta_t) \|_2 \\
        + \frac{\gamma}{(n-f)m} \| \nabla \ell (\theta_t, z^{(a,b)}) - \nabla \ell (\theta_t', z_t^{\prime (a, b)}) \|_2,
    \end{multline}
    where $a, b \in \mc{H} \times \{1, \ldots, m\}$ index the differing samples.

    \textit{(i)} 
    Since $I_t$ represents a fraction $\frac{n-2f}{n-f} \leq \rho_t \vcentcolon= \frac{|I_t|}{n-f} \leq 1$ of the gradient update, its expansivity (cf.~\Cref{lemmaexpansivity}) $\eta_{I_t}$ relates to the full update expansivity $\eta$ via
    \[
        \eta_{I_t} \leq 1 + \rho_t (\eta - 1).
    \]
    If $\ell$ is convex ($\eta=1$), then $\eta_{I_t} \leq 1$.
    If $\ell$ is $\mu$-strongly convex ($\eta = 1 - \gamma\mu$), then $\eta_{I_t} \leq 1 - \gamma\mu \frac{n-2f}{n-f}$.

    \textit{(ii)} We bound the divergence terms in~\eqref{eq:ub-sketch-inter}---arising from the non-shared indices $\Delta_t$ and the differing samples---using the Lipschitz continuity of $\ell$,
    $\| \sum_{i \in S^*_t \setminus S'^*_t} \nabla \widehat{R}_i (\theta_t) - \sum_{i \in S'^*_t \setminus S^*_t} \nabla \widehat{R}'_i (\theta_t) \|_2 \leq 2fC$,
    and $\| \nabla \ell (\theta_t, z^{(a,b)}) - \nabla \ell (\theta_t', z_t^{\prime (a, b)}) \|_2 \leq 2C$.
    Combining~\eqref{eq:ub-sketch-inter}, \textit{(i)} and \textit{(ii)} yields the following recursion
    \begin{equation}\label{eq:sketch-recursion}
        \textstyle \delta_{t+1} \leq \eta_{I_t} \delta_t + 2\gamma C \left( \frac{f}{n-f} + \frac{1}{m(n-f)} \right).
    \end{equation}
    We conclude the proof by solving the recursion and invoking the Lipschitz continuity of $\ell$.
\end{proof}
Crucially, the upper bounds derived above cannot be replicated for Byzantine failures, due to points \textit{(i)} and \textit{(ii)} in the proof sketch.
The fundamental distinction is that poisoned workers---unlike Byzantine workers---remain constrained by the loss function's regularity. 
Furthermore, notice that the proof technique generalizes beyond $\mathrm{SMEA}$, yielding the same upper bounds for any rule that averages $n-f$ gradients, independent of the selection mechanism. 




\textbf{Lower bounds.} Before comparing the above bounds to the Byzantine case, we establish their tightness by deriving matching lower bounds. 
These lower bounds are established for $\projSGD$, which applies a Euclidean projection onto the positive half parameter space after each iteration. 
While this simplifies the lower bounds proofs (see \Cref{lb-smea-sgd}), it does not affect the tightness of our result since the upper bounds on uniform stability remain valid for $\projSGD$ as the projection does not increase the distance between projected points.
\begin{theorem}\label{lower-bound-gd-poisonous-merged}
    Consider the setting of~\Cref{II-problem-formulation} under data poisoning.
    Let $\mc{A} \in \{ \mathrm{GD}, \projSGD \}$, with $\mathrm{SMEA}$, run for $T\in\mb{N}^*$ iterations with $\gamma \leq \frac{1}{L}$.
    \begin{enumerate}[label=\roman*, topsep=-3pt, itemsep=2pt, parsep=0pt, leftmargin = 20pt]
        \item[\textit{(i)}] 
        There exists $\ell$ such that $\forall z \in \mc{Z}, \ell(\cdot; z)$ is $C$-Lipschitz, $L$-smooth and convex,
        and neighboring datasets such that the uniform stability of $\mc{A}$ is lower bounded by\looseness=-1
        \begin{equation}\label{smea-poisoning-cvx-lb-eq}
            \Omega \left( \gamma C^2 T \left(\frac{f}{n-f} + \frac{1}{(n-f)m} \right) \right).
        \end{equation}
        For $\projSGD$, the above result assumes the existence of a constant $\tau \geq c > 0$ (for an arbitrary constant $c$) such that $T \geq \tau m$.
        
        \item[\textit{(ii)}] For $\mc{A} = \mathrm{GD}$, if $T \geq \frac{\ln(1-c)}{\ln(1-\gamma\mu)}$ with $0 < c < 1$, 
        there exist $\ell$ such that $\forall z \in \mc{Z}, \ell(\cdot; z)$ is additionally $\mu$-strongly convex,
        and neighboring datasets such that the uniform stability of $\mc{A}$ is lower bounded by
        \begin{equation}\label{smea-poisoning-strgcvx-lb-eq}
            \Omega \left( \frac{C^2}{\mu} \left( \frac{f}{n-f} + \frac{1}{(n-f)m} \right) \right).
        \end{equation}
    \end{enumerate}
\end{theorem}
\begin{proof}[Proof sketch.]\label{poisonous-proof-sketch} 
For formal proofs, see~\Cref{lb-smea-gd,lb-smea-sgd}.
\begin{comment}
We provide a general rationale for aggregation rules that fail to preserve the  co-coercive inequality of the underlying loss. 
In particular, as detailed below, an additive term necessarily arises in worst-case updates, and this behavior is expected to extend to iterative algorithms.
Let $F$ be a robust aggregation rule and $\ell$ a smooth and convex loss function. 
Suppose there exist $\theta, \omega \!\in\! \Theta$, $\theta \neq \omega$ such that $F$ breaks the co-coercive inequality~\eqref{co-coercivity}, 
that is, denoting $F_\theta=F(\nabla \widehat{R}_1(\theta), \ldots, \nabla \widehat{R}_n(\theta))$ and $F_\omega=F(\nabla \widehat{R}_1(\omega), \ldots, \nabla \widehat{R}_n(\omega))$ such that
\begin{equation}\label{breaking-cocoercivity}
    \textstyle \langle \theta - \omega, F_\theta - F_\omega \rangle \leq 0.
\end{equation}
Then, \eqref{breaking-cocoercivity} implies
\begin{multline*}
    \textstyle \| G^F_\gamma(\theta) - G^F_\gamma(\omega) \|_2^2
    = \| \theta - \omega \|_2^2
        + \gamma^2 \| F_\theta - F_\omega \|_2^2 \\
        - 2 \gamma \langle \theta - \omega, F_\theta - F_\omega \rangle
    > \| \theta - \omega \|_2^2.
\end{multline*}
Specifically, the quantity ${\sigma^F_{\theta, \omega}} = \| G^F_\gamma(\theta) - G^F_\gamma(\omega) \|_2 - \| \theta - \omega \|_2 > 0$ captures the additive growth in distance between parameters due to the update.
To illustrate the behavior of $\sigma^F_{\theta, \omega}$, we examine representative cases under aggregation rules such as $\mathrm{SMEA}$, which average gradients over an adaptively selected subset.
This selection of workers can violate the loss function's co-coercivity inequality: let $S_\theta$ and $S_\omega$ denote the subsets selected for parameters $\theta$ and $\omega$ respectively; violation occurs when $S_\theta \neq S_\omega$. 
The intersection and difference of the two subsets satisfy: 
$
    n-2f \leq | S_\theta \cap S_\omega | \leq n-f \quad\text{and}\quad | S_\theta \setminus S_\omega \cup S_\omega \setminus S_\theta | \leq 2f.
$
Hence, through straightforward algebraic manipulation and leveraging gradient boundedness, we obtain in the worst case scenario ${\sigma^F_{\theta, \omega}} \propto \frac{f}{n-f}$.
\end{comment}
\begin{comment}
We now implement the above observation in a sketched lower bound proof. 
We track how the norm of the parameter difference diverges along the optimization trajectories resulting from two neighboring datasets $\mc{S}, \mc{S}'$, 
for $T$ iterations of $\mc{A} \in \{ \mathrm{GD}, \mathrm{SGD} \}$ with aggregation rule $F$ and learning rate $\gamma$. 
Denote the parameter trajectories by $\{{\theta_t\}}_{t \in \{0, \ldots, T-1\}}$ and ${\{\theta'_t\}}_{t \in \{0, \ldots, T-1\}}$.
We assume the datasets are such that the robust aggregation $F$ does not preserve the co-coercive inequality of the loss function throughout iterations. 
For $t \in \{0, \ldots, T-1\}$, define the additive terms $\sigma^F_t = \| G^F_\gamma(\theta_t) - G^F_\gamma(\theta'_t) \|_2 - \| \theta_t - \theta'_t \|_2$ 
and $\sigma^{\mathrm{\mc{A}}}_t = \frac{\gamma}{(n-f)m} \| \nabla \ell (\theta_t'; z') - \nabla \ell (\theta_t'; z)  \|_2$, where $z'$ and $z$ are the differing samples in $\mc{S}', \mc{S}$, respectively.
Then (either deterministically for $\mathrm{GD}$ or in expectation for $\mathrm{SGD}$):\looseness=-1 
\[
    \textstyle \| \theta_{t+1} - \theta'_{t+1} \|_2
    = \| \theta_{t} - \theta'_{t} \|_2
    + \sigma^F_t
    + \sigma^{\mathrm{\mc{A}}}_t.
\]
We precisely exploit this construction when $F=\mathrm{SMEA}$, designing a loss function and neighboring datasets that enable us to lower bound the additive terms as $\sigma^F_t \geq \gamma C \frac{f}{n-f}$ and $\sigma^{\mathrm{\mc{A}}}_t \geq \frac{\gamma C}{(n-f)m}$.
This recovers the lower bound stated in the theorem, matching the convex upper bound of Theorem~\ref{th-poisoning-convex-smea-main-text}. The main challenge lies in designing such a scenario, which we detail in \Cref{lb-smea-gd,lb-smea-sgd}.
\end{comment}
We specifically sketch below our construction for $\mathcal{A}=\mathrm{GD}$, which will be used extensively in \Cref{V-experimental}. 
In dimension one, the $\mathrm{SMEA}$ rule amounts to picking the subset with the smallest gradient variance. 
For $n=3$ and $f=1$, this reduces to minimizing in $i,j$, $\|g_i - g_j\|_2^2/4$, so $\mathrm{SMEA}$ averages the closest pair of worker gradients.
Let $\ell(\theta;z)=z\theta$, $\theta\in\mathbb{R}$, $z\in[-C,C]$, and set local datasets to be homogeneous, equal to $0$ (worker 1), $-C$ (worker 2), and $C-\delta$ (worker 3, $\delta>0$). Then $\nabla \widehat{R}_1(\theta)=0$, $\nabla \widehat{R}_2(\theta)=-C$, $\nabla \widehat{R}_3(\theta)=C-\delta$, so $\mathrm{SMEA}$ favors $\{1,3\}$, updating the parameter in the negative direction.
Since $C-\delta$ can be made arbitrarily close to $C$, a perturbation of worker 1’s dataset (e.g., changing a sample from $0$ to $-C$, giving $\nabla \widehat{R}'_1(\theta)=-\frac{C}{m}$) makes $\mathrm{SMEA}$ favor $\{1,2\}$, updating the parameter in the positive direction. Hence, parameter divergence is proportional to $\gamma C T$.
This reasoning generalizes to any $f$ and $n$ (see \Cref{lb-smea-gd-convex}), replacing a single sample can cause $\mathrm{SMEA}$ to swap $f$ workers among the $n-f$ originally subsampled, yielding stability
proportional to $\gamma C^2 T \Big( \frac{f}{n-f} + \frac{1}{(n-f)m} \Big)$, where the first term reflects worker swapping and the second the perturbed sample.
\qedhere
\end{proof}

This result establishes an unavoidable additional instability relative to the simple averaging rule.
Interestingly, if $\mathrm{SMEA}$ were co-coercive (cf.\ Equation~\ref{co-coercivity} in~\Cref{loss-regularities}), these lower bounds would not hold: one could then directly apply the techniques of~\citet{hardt2016train} to obtain a tighter upper bound, effectively removing the second term in~\eqref{eq:ub-sketch-inter}.
This suggests that the loss of co-coercivity is the primary driver of the instability observed in~\eqref{smea-poisoning-cvx-lb-eq}-\eqref{smea-poisoning-strgcvx-lb-eq}.
To our knowledge, no robust aggregation rule preserves this inequality. 
Identifying such a rule---or proving that none exists---remains an important open question for future work to further improve stability guarantees under data poisoning.

\paragraph{Fundamental gap with Byzantine bounds.} 
We now compare the bounds obtained for the two threat models.
Crucially, the additional instability term in the Byzantine upper bounds~\eqref{smea-byz-cvx-eq} and~\eqref{smea-byz-stgcvx-eq} decreases from $\mathcal{O}(\sqrt{\kappa})$---which for $\mathrm{SMEA}$ evaluates to $\mathcal{O}\big(\sqrt{\frac{f}{n-f}}(1 + \frac{f}{n-2f})\big)$~\citep[Proposition 5.1]{pmlr-v202-allouah23a}---down to $\mathcal{O}(\frac{f}{n-f})$ in the data poisoning case~\eqref{smea-poisoning-cvx-eq} and~\eqref{smea-poisoning-strgcvx-eq}. 
The upper bound~\eqref{smea-poisoning-cvx-eq} is thus an order of magnitude smaller than the lower bound $\Omega(\sqrt{\frac{f}{n-2f}})$~\eqref{smea-byz-lb-eq} obtained for $f \geq \frac{n}{3}$, establishing a fundamental stability gap.
As $f$ approaches its maximal value $\tfrac{n}{2}$, the gap widens significantly, highlighting the stability contrast between the two threat models. 
\Cref{table-comparaison} summarizes our results.

We present further results for smooth \emph{nonconvex} learning in \Cref{app:nonconvex}, along with a discussion on relaxing other regularity assumptions in \Cref{additional-discussions}.
Taken together, these findings support the view that the stability gap between Byzantine failures and data poisoning is not limited to our baseline assumptions.

In the next section, we show that this stability gap drives a corresponding gap in generalization error, revealing a fundamental difference in the ability of the two threat models to degrade performance on unseen data.%\looseness=-1