source_extract/sections/section-II-problem-formulation.tex

\section{Preliminaries}\label{II-Background-motivation}\label{II-problem-formulation}

\paragraph{Problem setting.} 
We consider a distributed setup with a central server and $n$ workers, where up to $f$ (with $f < \frac{n}{2}$) may be subject to either \textit{Byzantine failures} or \textit{data poisoning}, as defined below. 
We refer to such workers as \emph{misbehaving}, unless we need to distinguish between the two attack types.
Their identities are unknown to the server.
While the actual number of misbehaving workers may be less than $f$, we assume the worst-case scenario where exactly $f$ workers are misbehaving. The remaining \emph{honest} workers form the set $\mc{H} \subseteq [n] \vcentcolon= \{1, \ldots, n\}$, with $|\mc{H}| = n-f$.
Each honest worker $i \in \mc{H}$ holds a local dataset $\mc{D}_i = \{z^{(i,1)}, \ldots, z^{(i,m)} \}$ composed of $m$ i.i.d.\ data points (or samples) from an input space $\mathcal{Z}$ drawn from a distribution $p_i$. We denote $\mc{S} = \cup_{i\in\mc{H}}\mc{D}_i$. 
Given a parameter vector $\theta \in \Theta \subset \mb{R}^d$ representing the model, a data point $z \in \mc{Z}$ incurs a differentiable loss defined by a real-valued function $\ell(\theta; z)$. The goal is to minimize the \emph{population} risk over the honest workers, %\looseness=-1
\[
    R_{\mc{H}}(\theta) = \frac{1}{|\mc{H}|} \sum\limits_{i\in\mc{H}} \mb{E}_{z \sim p_i}[ \ell(\theta, z) ].
\]
As we only have access to a finite number of samples from each distribution, the above objective can only be solved approximately by minimizing the \emph{empirical} risk over the honest workers, with the added challenge that the honest subgroup is unknown,
\[
    \widehat{R}_{\mc{H}}(\theta) = \frac{1}{|\mc{H}|} \sum\limits_{i\in\mc{H}}\widehat{R}_{i}(\theta) = \frac{1}{|\mc{H}|} \sum\limits_{i\in\mc{H}} \frac{1}{m} \sum\limits_{z \in \mc{D}_i} \ell(\theta, z).
\]
The expected excess population risk of a distributed learning algorithm's output $\mc{A(\mc{S})}$ can be decomposed into the generalization and optimization errors~\citep[e.g.,][Section 5]{hardt2016train} as follows
\begin{multline}\label{gen-error-ineq}
    \textstyle \mb{E} \big[ R_{\mc{H}}(\mc{A(\mc{S})}) - \inf\limits_{\theta \in \Theta} R_{\mc{H}}(\theta) \big]
    \leq \mb{E} \big[ R_{\mc{H}}(\mc{A(\mc{S})}) \\ - \widehat{R}_{\mc{H}}(\mc{A(\mc{S})}) \big]
    + \mb{E} \big[ \widehat{R}_{\mc{H}}(\mc{A(\mc{S})}) - \inf\limits_{\theta \in \Theta} \widehat{R}_{\mc{H}}(\theta) \big]
\end{multline}
Prior work on robust distributed learning has focused primarily on the optimization error, i.e., the second term on the right-hand side. In contrast, our goal is to study the generalization error, corresponding to the first term.
Formally, we define the notion of \textit{robustness} as follows.
\begin{definition}
    An algorithm is said to be $(f, \rho,$ \text{statistical})-resilient if it outputs a parameter $\hat{\theta}$ such that 
    \[
        \mb{E}_{\mc{A}} \big[ R_{\mc{H}}(\hat{\theta}) - \inf_{\theta\in\Theta} R_{\mc{H}}(\theta) \big] \leq \rho.
    \] 
    We say $(f, \rho, \text{empirical})$-resilient when we only consider empirical risk.
\end{definition}
Note that the (standard) notion of $(f, \rho, \text{empirical})$-resilience is impossible in general for any $\rho$ when $f \geq n/2$~\citep{liu2021approximate}, justifying our assumption $f < n/2$.



\textbf{Threat models.} We analyze this resilience property under two standard threat models widely studied in the literature~\citep{farhadkhani2024brief,blanchard-ml-with-adversaries}.%\looseness=-1

\textit{Byzantine failures.} In this threat model, misbehaving workers can act arbitrarily: they may deviate from the prescribed algorithm, collude, and send adversarial updates to the server while having access to all information exchanged between honest workers and the server. This model follows the classical notion of Byzantine failures in distributed systems introduced in the seminal work of~\citet{lamport1982byzantine}.\looseness=-1
 
\textit{Data poisoning.} In this restricted threat model, misbehaving workers follow the prescribed algorithm but may corrupt their local training data \emph{before} execution.
Specifically, for each misbehaving worker $i \notin \mc{H}$, a local dataset $\mc{D}_i \in \mc{Z}^m$ is adversarially constructed with full knowledge of the honest workers' data distributions $\{ p_i, ~ i \in \mc{H} \}$.



\paragraph{Background on robust distributed optimization.} 
Robust distributed optimization algorithms aim to achieve $(f,\rho,\text{empirical})$-resilience. They are typically adaptations of standard first-order iterative optimization algorithms like gradient descent ($\mathrm{GD}$) or stochastic gradient descent ($\mathrm{SGD}$). 
These algorithms are made resilient by replacing the server-side averaging operator by a robust aggregation rule $F: (\mb{R}^d)^{n} \to \mb{R}^d$~\citep{gerraoui-byzantine-primer}.
Formally, given a learning rate $\gamma$, the parameter $\theta_t$ at iteration $t \in \{0, \ldots, T-1\}$ is updated as follows
\begin{equation}\label{eq:update}
    \theta_{t+1} = G^F_{\gamma}(\theta_t) := \theta_t - \gamma F(g^{(1)}_t, \ldots, g^{(n)}_t),
\end{equation}
where $g^{(i)}_t$ denotes the update sent by worker $i$ at iteration $t$. For an honest worker $i \in \mc{H}$, we have $g^{(i)}_t = \nabla \widehat{R}_i (\theta_t)$ under $\mathrm{GD}$, or $g^{(i)}_t = \nabla \ell (\theta_t; z^{(i)}_t)$ under $\mathrm{SGD}$, with $z^{(i)}_t$ uniformly sampled from the local dataset $\mc{D}_i$. 
For a misbehaving worker $i \notin \mc{H}$, $g^{(i)}_t$ is either an arbitrary vector in $\mathbb{R}^d$ (Byzantine failures) or a gradient computed on corrupted data (data poisoning).\looseness=-1

Recent advances in robust distributed optimization have identified key properties sufficient for a robust aggregation rule to ensure $(f,\rho, \text{empirical})$-resilience~\citep{pmlr-v206-allouah23a,pmlr-v202-allouah23a}. 
The following definition encompasses a wide range of aggregation rules and has been shown to yield tight resilience guarantees across a variety of practical distributed learning settings.
We denote by $\| \cdot \|_2$ the Euclidean norm.
\begin{definition}\label{robustness-definition}
    Let $n \geq 1$, $0 \leq f < n/2$ and $\kappa \geq 0$. An aggregation rule $F$ is said $(f, \kappa)$-robust if for any $g_1, \ldots, g_n \in \mb{R}^d$, 
    any set $S \subset [n]$ of size $n-f$, with $\overline{g}_S = \frac{1}{|S|} \sum_{i \in S} g_i$ and $\Sigma_{S} = \frac{1}{|S|} \sum_{i \in S} (g_i-\overline{g}_S) {(g_i-\overline{g}_S)}^{\intercal}$, we have
    \[
        \| F(g_1, \ldots, g_n) - \overline{g}_S \|_2^2 \leq \kappa \|\Sigma_S\|_{\text{sp}}.
    \]
    Here, $\|\cdot\|_{\text{sp}}$ denotes the spectral norm (i.e., the largest eigenvalue), $f$ and $\kappa$ are referred to as the \textit{robustness parameter} and \textit{robustness coefficient} of $F$, respectively.
\end{definition}
Any aggregation rule $F$ that is $(f,\mathcal{O}(f/n))$-robust achieves optimal $(f,\rho,\text{empirical})$-resilience.
Specifically, iterative methods employing such a rule attain an optimization error that matches the information-theoretic lower bound for first-order optimization in the presence of $f$ misbehaving workers~\citep{farhadkhani2024relevance}.
One such optimal rule is SMEA, introduced by \citet{pmlr-v202-allouah23a}.
\begin{definition}\label{smea-definition}
    Given $f, n \in \mb{N}$, $f < n/2$ and vectors $g_1, \ldots, g_n \in \mb{R}^d$,
    the smallest maximum eigenvalue averaging aggregation rule (SMEA) outputs the average of the $n-f$ gradients that are most directionally consistent, discarding outliers based on covariance,
    \[
        \overline{g}_{S^*} = \frac{1}{|S^*|} \sum_{i\in S^*} g_{i},
        \quad\text{with}\quad S^* \in \underset{\substack{{S \subseteq \{1, \ldots, n\},}\\{|S|=n-f}}}{\arg\!\min} \|\Sigma_S\|_{\text{sp}}.
    \]
\end{definition}
However, the above results focus on the optimization error, overlooking the impact of robust aggregation rules on the generalization error---the first term in the right-hand side of~\eqref{gen-error-ineq}.
To address this gap, we provide a rigorous analysis of the generalization guarantees of robust distributed learning, focusing on the $\mathrm{SMEA}$ aggregation rule as it yields optimal optimization guarantees.



\paragraph{Stability under misbehaving workers.} 
We leverage the algorithmic stability framework  to bound the generalization error of robust distributed learning algorithms. 
We do so via uniform stability, which measures how sensitive a learning algorithm is to changes in its training data. 
This approach was introduced by~\citet{vapnik74theory,RogersWagner78,DevroyeWagner79} and later popularized by~\citet{Bousquet2002StabilityAG, JMLR:v11:shalev-shwartz10a, hardt2016train}.
We revisit this framework to study generalization in robust distributed learning, where the change is only in the honest workers' data.%\looseness=-1

\begin{definition}\label{uniform-stability-def}
    Consider $n$ workers, with $f$ misbehaving and $n-f$ honest, each holding $m$ local samples. 
    A distributed algorithm $\mc{A}$ is said $\varepsilon$-uniformly stable if, for all honest datasets $\mc{S}, \mc{S}' \in \mc{Z}^{(n-f)m}$ that are \textit{neighboring}—i.e., differing in at most one sample—we have
    \[
        \sup_{z \in \mc{Z}} \mb{E}[\ell(\mc{A}(\mc{S}); z) - \ell(\mc{A}(\mc{S}'); z)] \leq \varepsilon,
    \]
    where the expectation is over the randomness of $\mc{A}$.
\end{definition}
This property leads to the following bound on the generalization error, proved in~\Cref{gen-and-Byzantine}.
\begin{proposition}\label{lemmagen1}
    If $\mc{A}$ is $\varepsilon$-\textit{uniformly stable}, then 
    \[
        | \mb{E}_{\mc{S}, \mc{A}}[ R_{\mc{H}}(\mc{A}(\mc{S})) - \widehat{R}_{\mc{H}}(\mc{A}(\mc{S})) ] | \leq \varepsilon.
    \]
\end{proposition}
The link between uniform stability and generalization can be further strengthened to yield high-probability generalization bounds, as discussed in \Cref{IV-excessrisk}.
We can now formalize a relationship between empirical resilience and statistical resilience through stability: any algorithm that is $(f, \rho, \text{empirical})$-resilient and $\varepsilon$-uniformly stable is $(f, \rho + \varepsilon, \text{statistical})$-resilient. 
Here, $\varepsilon$ quantifies the effect of misbehaving workers on generalization, and is the central focus of this paper.