\section{Introduction}
\label{sec:intro}

Federated Learning (FL) \cite{mcmahan2017fl} is a privacy-aware distributed machine learning paradigm.
It has recently attracted widespread attention as a result of emerging data silos and growing privacy awareness \cite{wu2022communication,lyu2020towards}.
In this paradigm, data owners (clients) repeatedly use their private data to compute local gradients and send them to a central server for aggregation.
In this way, clients can collaborate to train a model without exposing their private data.
However, the distributed property of FL also makes it vulnerable to Byzantine attacks \cite{blanchard2017krum, guerraoui2018bulyan,lyu2022privacy,sun2021data}.
During the training phase, Byzantine clients can send arbitrary messages to the central server to bias the global model.
Moreover, it is challenging for the central server to identify the Byzantine clients, since the server can neither access clients' training data nor monitor local training processes.

In order to defend against Byzantine attacks, the community has proposed a wealth of defenses \cite{blanchard2017krum, guerraoui2018bulyan, yin2018mediantrmean}.
Most defenses abandon the averaging step adopted by conventional FL frameworks, e.g., FedAvg \cite{mcmahan2017fl}.
Instead, they use robust AGgregation Rules (AGRs) to aggregate local gradients in order to defend against Byzantine attacks.
Most existing robust AGRs assume that the data distribution on different clients is identically and independently distributed (IID) \cite{bernstein2018signsgd, ghosh2019robust}.
However, the data is usually non-independent and identically distributed (non-IID) in real-world FL applications \cite{mcmahan2017fl,karimireddy2020scaffold, kairouz2021advances}.
As a result, in more realistic non-IID settings, most robust AGRs fail to defend against Byzantine attacks, and thus suffer from significant performance degradation \cite{karimireddy2022bucketing, acharya2022cgm}.

To investigate the cause of the degradation, we perform a thorough experimental study on various robust AGRs.
Close inspection reveals that the reason behind the degradation is different for different AGRs with different types of aggregation strategies.
For \emph{conservative} AGRs that only aggregate few gradients to get rid of Byzantines, they suffer from \emph{integrity} failure.
The integrity failure describes that an AGR can only identify \emph{few} honest gradients for aggregation.
This failure will lead to an aggregated gradient with limited utility due to the gradient heterogeneity \cite{li2020fedprox,karimireddy2020scaffold} in the non-IID setting.
For \emph{radical} AGRs that aggregate as many gradients as possible to avoid such deviation, they suffer from another \emph{identification} failure.
The identification failure means that an AGR fails to distinguish between honest and Byzantine gradients.
This failure is mainly due to the curse of dimensionality \cite{guerraoui2018bulyan,diakonikolas2017being} aggravated by the non-IIDness.
Both failures deviate the aggregated gradient from the optimal gradient (the average of honest gradients).
As a result, most existing AGRs fail to achieve a satisfactory performance in the non-IID setting.

Motivated by the above observations, we propose a GrAdient decomposItioN method called GAIN\xspace that can handle both failures in various non-IID settings.
In particular, to address the identification failure due to the curse of dimensionality, GAIN\xspace decomposes each high-dimensional gradient into low-dimensional groups for gradient identification.
Then, GAIN\xspace incorporates gradients with low identification scores into final aggregation to tackle the integrity failure.

Our contributions in this work are summarized below.
\begin{itemize}
    \item We reveal the root reasons for the performance degradation of current robust AGRs in the non-IID setting by proposing two new concepts: integrity failure and identification failure.
    Integrity failure origins from the gradient heterogeneity,
    and identification failure is a result of the aggravated curse of dimensionality in the non-IID setting.
    \item We propose a novel and compatible approach called GAIN\xspace, which applies robust AGRs on the decomposed gradients, followed by identification before aggregation,
    rather than directly operating on the original gradients as the existing defenses (Multi-Krum \cite{blanchard2017krum}, Bulyan \cite{guerraoui2018bulyan}, etc) do.
    \item We also provide convergence analysis for integrating existing robust AGRs into GAIN\xspace. In particular, we provide an upper bound for the sum of gradient norms.
    \item We also offer empirical experiments on three real-world datasets across various settings to validate the effectiveness and superiority of our GAIN\xspace.
\end{itemize}

\section{Related Works}
\label{sec:related_works}

Byzantine robust learning is first introduced by \cite{blanchard2017krum}.
Subsequently, a range of works study the robustness against Byzantine attacks by proposing various robust AGgregation Rules (AGRs) under the IID setting.
Generally, we can classify the current robust AGRs into two categories: \textbf{conservative} AGRs and \textbf{radical} AGRs.

Typical conservative AGRs, including Bulyan \cite{guerraoui2018bulyan}, Median \cite{yin2018mediantrmean}, Trimmed Mean \cite{yin2018mediantrmean}, etc., only aggregate few gradients to reduce the risk of the introduced Byzantine gradients.
Bulyan \cite{guerraoui2018bulyan} applies a variant of trimmed mean as a post-processing method to handle the curse of dimensionality.
\cite{yin2018mediantrmean} theoretically analyze the statistical optimality of Median and Trimmed Mean.
The radical AGRs, e.g., Multi-Krum \cite{blanchard2017krum}, DnC \cite{shejwalkar2021dnc}, incorporate as many gradients as possible to avoid such deviation.
Multi-Krum is a distance-based AGR proposed by \cite{blanchard2017krum}.
\cite{pillutla2019geometric} discuss the Byzantine robustness of Geometric Median and propose a computationally efficient approximation.
\cite{shejwalkar2021dnc} propose to perform dimensionality reduction using random sampling, followed by spectral-based outlier removal.
Recently, a quantity of works \cite{allen2020safeguard, karimireddy2021history, farhadkhani2022momentum,chenbyzantine} discuss the effect of distributed momentum to Byzantine robustness from different perspectives.
However, in more realistic FL applications where the data is non-IID, the efficacy of these defenses are quite limited.
They fail to obtain high-quality aggregated gradient in the non-IID setting, thus suffer from significant performance degradation.

Recently works have also explored defenses that can be applicable to the non-IID setting.
\cite{park2021sageflow} can only achieve Byzantine robustness when the server has a validation set, which compromises the privacy principle of the FL \cite{mcmahan2017fl}.
\cite{data2021byzantine} adapt a robust mean estimation algorithm to FL to combat Byzantines in the non-IID setting.
However, it requires $\Omega(d^2)$ time ($d$ is the number of model parameters), which is unacceptable due to the high dimensionality of model parameters.
\cite{el2021collaborative} consider Byzantine robustness in the asynchronous communication and unconstrained topologies settings.
\cite{acharya2022cgm} propose to apply geometric median only to the sparsified gradients to save computation cost.
\cite{karimireddy2022bucketing} perform a bucketing process before aggregation to reduce the gradient heterogeneity.
These methods guarantee convergence of SGD in the existence of Byzantines.
However, convergence is not enough in the context of non-convex, high dimensional case of neural networks \cite{guerraoui2018bulyan}.
These methods lack of the guarantee that the aggregated gradient does not deviate from the optimal gradient (the average of honest gradients).
As a result, they may lead to convergence towards ineffectual models.

\section{Notations and Preliminaries}
\label{sec:setup}

\textbf{Notations.}
For any positive integer $n\in{\mathbb{N}}^+$, we denote the set $\{1,\ldots,n\}$ by $[n]$.
The cardinality of a set $\mathcal{S}$ is denoted by $\text{\#}\mathcal{S}$ or $|\mathcal{S}|$.
For a real number $x\in{\mathbb{R}}$, we use $|x|$ to denote the absolute value of number $x$.
We denote the $\ell_2$ norm of vector ${\bm{x}}$ by $\|{\bm{x}}\|$.
We use $\component{{\bm{x}}}{j}$ to represent the $j$-th component of vector ${\bm{x}}$.
The sub-vector of vector ${\bm{x}}$ indexed by index set $\indexset{}$ is denoted by $\component{{\bm{x}}}{\indexset{}}=(\component{{\bm{x}}}{j_1},\ldots,\component{{\bm{x}}}{j_k})$, where $\indexset{}=\{j_1,\ldots,j_k\}$, and $k=|\mathcal{J}|$ is the number of indices.
For a random variable $X$, we use $\mathbb{E}[X]$ and $\mathrm{Var}[X]$ to denote the expectation and variance of $X$, respectively.

\textbf{Federated learning.}
We consider the federated learning system with a center server and $n$ clients following \cite{blanchard2017krum, yin2018mediantrmean, guerraoui2018bulyan}.
Then the objective is to minimize loss $\loss(\param)$ defined as follows.
\begin{align}
\label{eq:fl_objective}
\loss(\param)=\frac{1}{n}\sum_{i=1}^n\loss[i](\param),
\quad\text{where }\loss[i](\param)=\mathbb{E}_{\samples{i}}[\loss(\param;\samples{i})],
i\in[n],
\end{align}
where $\param$ is the model parameter,
$\loss[i]$ is the loss function on the $i$-th client,
$\samples{i}$ is the data distribution on the $i$-th client,
and $\loss(\param;\vxi)$ is the loss function.

In the $t$-th communication round, the server distributes the parameter $\param[t]$ to the clients.
Each client $i$ conducts several epochs of local training on local data to obtain the updated local parameter $\localparam{i}{t}$.
Then, client $i$ computes the local gradient $\sgrad{i}{t}$ as follows and sends it to the server.

\begin{align}
\sgrad{i}{t}=\param[t]-\localparam{i}{t}.
\end{align}
Finally, the server collects the local gradients and uses the average gradient to update the global model.
\begin{align}
\label{eq:fedavg}
    \param[t+1]=\param[t]-\avgsgrad{t},
    \quad\avgsgrad{t}=\frac{1}{n}\sum_{i=1}^n\sgrad{i}{t}.
\end{align}

This process is repeated until the global model converges or the number of communication rounds reaches the set value $T$.

\textbf{Byzantine threat model.}
In real-world applications, not all clients in FL systems are honest. 
In other words, there may exist Byzantine clients in FL systems \cite{blanchard2017krum}.
Suppose that an adversary controls $f$ Byzantines clients among the total $n$ clients. 
Let $\mathcal{B}\in[n]$ denote set of Byzantine clients and $\mathcal{H}=[n]\setminus\mathcal{B}$ denote the set of honest clients.
In the presence of Byzantine clients, the uploaded message of client $i$ in the $t$-th communication round is
\begin{align}
\label{eq:local_update}
   \sgrad{i}{t}=
   \begin{cases}
      \localparam{i}{t+1}-\param[t], & i\in\mathcal{H}, \\
      *, & i\in\mathcal{B}, 
   \end{cases}
\end{align}
where $*$ represents arbitrary value.

\textbf{Robust AGRs.}
Most solutions replace the averaging step by a robust alternative to defend against Byzantine attacks.
More specifically, the server aggregates the gradients and updates the global model as follows.
\begin{align}
\label{eq:robust_aggregation}
\param[t+1]=\param[t]-\aggsgrad{t},
\quad\aggsgrad{t}=\mathcal{A}(\sgrad{1}{t}, \ldots,\sgrad{n}{t}), 
\end{align}

where $\aggsgrad{t}$ is the aggregated gradient,
and $\mathcal{A}$ is a robust AGR, e.g., Multi-Krum \cite{blanchard2017krum}, Bulyan \cite{guerraoui2018bulyan}.

For notation simplicity, we omit the superscript $t$ of the gradient symbols when there is no ambiguity in the rest of this paper.

\section{Failures of existing Robust AGRs in the Non-IID Setting}
\label{sec:motivation}

Most robust AGRs focus on Byzantine robustness in the IID setting \cite{blanchard2017krum,guerraoui2018bulyan}.
When the data is non-IID, the performance of these robust AGRs drop drastically \cite{shejwalkar2021dnc,karimireddy2022bucketing}.
In order to understand the root cause of this performance drop, we perform an experimental study on various robust AGRs.
Particularly, we examine the behaviors of robust AGRs under the attack of $20\%$ Byzantines in both IID and non-IID settings on CIFAR-10 \cite{krizhevsky2009cifar} in \cref{fig:observation}.
More detailed setups are covered in \cref{appsec:motivation_setup}.
A close inspection reveals that AGRs of different types demonstrate different failures in the non-IID setting.
As mentioned earlier in \cref{sec:related_works}, most robust AGRs fall under the umbrella of either \emph{conservative} AGRs or \emph{radical} AGRs.
Next, we choose two representative AGRs (Bulyan and Multi-Krum) from both types and summarize how they fail in the non-IID setting.

\begin{figure}[h]
\centering
\includegraphics[width=0.6\textwidth]{figures/legend.pdf}
\\
\begin{subfigure}[]{0.23\textwidth}
\centering
\includegraphics[width=\textwidth]{figures/bulyan_selection.pdf}
\caption{Honest ratio of a\\ conservative AGR.}
\label{fig:bulyan_selection}
\end{subfigure}
\begin{subfigure}[]{0.23\textwidth}
\centering
\includegraphics[width=\textwidth]{figures/bulyan_performance.pdf}
\caption{Performance of a\\ conservative AGR.}
\label{fig:bulyan_performance}
\end{subfigure}
\begin{subfigure}[]{0.23\textwidth}
\centering
\includegraphics[width=\textwidth]{figures/mkrum_selection.pdf}
\caption{Honest ratio of a\\ radical AGR.}
\label{fig:krum_selection}
\end{subfigure}
\begin{subfigure}[]{0.23\textwidth}
\centering
\includegraphics[width=\textwidth]{figures/mkrum_performance.pdf}
\caption{Performance of a\\ radical AGR.}
\label{fig:krum_performance}
\end{subfigure}
\caption{The behaviors of a conservative AGR (Bulyan) and a radical AGR (Multi-Krum) under the attack of $20\%$ Byzantines in both IID and non-IID settings on CIFAR-10 dataset. More detailed setups are covered in \cref{appsec:motivation_setup}.
The dotted lines represent the performance without Byzantines.
}
\label{fig:observation}
\end{figure}


\textbf{Integrity failure of a conservative AGR.}
We take a closer look at a representative conservative AGR -- Bulyan \cite{guerraoui2018bulyan}.
Specifically, we consider an indicator called \emph{honest ratio} -- the ratio of selected honest client number to all selected client number
(\# selected honest clients / \# selected clients) of a robust AGR in each communication round.
A higher honest ratio suggests a higher proportion of honest gradients among the gradients aggregated by AGR.
In particular, honest ratio 1 (0) suggests that all gradients that the AGR aggregates are honest (Byzantine).
In \cref{fig:bulyan_selection}, we report the honest ratio of the conservative AGR (Bulyan) in both IID and non-IID settings.
The results show that in both settings, all the gradients aggregated by the conservative AGR are honest,
which demonstrates the strong Byzantine filtering ability of a conservative AGR.
Unfortunately, we find that Byzantine filtering is not enough in the non-IID setting.
The results in \cref{fig:bulyan_performance} illustrate that the accuracy is significantly lower in the non-IID setting.
This performance degradation implies a sharp deviation of the aggregated gradient from the \emph{optimal} gradient (the average of honest gradients) in the non-IID setting.
Honest gradients are heterogeneous when the data is non-IID \cite{li2020fedprox,wang2021fieldguide,karimireddy2020scaffold}.
As a result, aggregating only partial honest gradients will deviate the aggregated gradient from the optimal gradient, and eventually lead to ineffectual models.
Therefore, in addition to Byzantine filtering, \emph{it is also crucial to incorporate sufficient honest gradients into aggregation in the non-IID setting}.

\textbf{Identification failure of a radical AGR.}
We closely examine a typical radical AGR --
Multi-Krum \cite{blanchard2017krum}.

In \cref{fig:krum_selection}, we demonstrate the honest ratio of the radical AGR in both IID and non-IID settings.
As shown in the figure, the radical AGR succeeds in identifying honest gradients for aggregation in the IID setting but fails in the non-IID setting.
The critical reason behind is that while the curse of dimensionality \cite{guerraoui2018bulyan} can be provably addressed in the IID setting, it will be aggravated and intractable in the non-IID setting.
When the data is non-IID, Byzantines can easily exploit the curse of dimensionality to compromise radical AGRs, thus degrade the utility of global model as shown in \cref{fig:krum_performance}.
Therefore, \emph{it is critical to overcome the aggravated curse of dimensionality in the non-IID setting}.

As analyzed above,
most robust AGRs suffer from identification failure and integrity failure due to gradient heterogeneity and the aggravated curse of dimensionality in the non-IID setting.
As a result, they fail to stop the aggregated gradient deviating from the optimal gradient, which leads to unsatisfactory performance in the non-IID setting.


\section{Proposed Method}
\label{sec:proposed}

Our observations in \cref{sec:motivation} clearly motivate the need for a more robust defense to defeat Byzantine attacks in the non-IID setting.
Inspired by these observations, we propose a novel GrAdient decomposItioN method called GAIN\xspace, which consists of three stages as follows.

\textbf{Decomposition.}
First, GAIN\xspace decomposes the gradients for gradient identification.
The decomposition is specified by a partition of set $[d]$, where $d$ is the dimension of gradients.
Let $\{\indexset{1},\ldots\indexset{p}\}$ denote the partition, where $p$ is the number of groups.
Particularly, the partition satisfies:
\begin{gather}
\indexset{q}\ne\emptyset,
\quad\forall q\in[p]
\quad\text{and}\quad
[d]=\bigcup_{q=1}^p\indexset{q},
\quad\text{and}\quad
\indexset{q}\bigcap\indexset{q'}=\emptyset,
\quad\forall q, q'\in[p], q\ne q',
\end{gather}
where $\emptyset$ represents the empty set,
$\bigcup$ represents the union of sets,
and $\bigcap$ represents the intersection of sets.
Each gradient $\sgrad{i}{}$ is correspondingly decomposed into $p$ sub-vectors as follows.
\begin{align}
    \subsgrad{i}{q}=\component{\sgrad{i}{}}{\indexset{q}},
    \quad i\in[n],q\in[p],
\end{align}
where $\subsgrad{i}{q}$ is the $q$-th sub-vector of gradient $\sgrad{i}{}$.

\textbf{Identification.}
Then, GAIN\xspace applies any robust AGR $\mathcal{A}$ to each group of sub-vectors corresponding to $\indexset{q}$:
\begin{align}
\subaggsgrad{q}=\mathcal{A}(\subsgrad{1}{q},\ldots,\subsgrad{n}{q}),
\quad q\in[p],
\end{align}
where $\subaggsgrad{q}$ is the aggregation result of group $q$.
By performing aggregation on groups of low-dimensional sub-vectors, GAIN\xspace can circumvent the curse of dimensionality, thus avoiding the identification failure discussed in \cref{sec:motivation}.
In other words, $\subaggsgrad{q}$ can get rid of Byzantines.

Note that $\subaggsgrad{q}$ may still suffer from deviation due to the integrity failure of the AGR $\mathcal{A}$ as illustrated in \cref{sec:motivation}.
Therefore, it is inappropriate to directly use the aggregation results $\{\subaggsgrad{q},q\in[p]\}$ as the final output.
Instead, we use $\subaggsgrad{q}$ as an honest reference to compute identification scores for each client as follows.
\begin{align}
\label{eq:group_score}
\groupscore{i}{q}=\|\subsgrad{i}{q}-\subaggsgrad{q}\|,
\quad i\in[n], q\in[p].
\end{align}
Since the group-wise aggregation result $\subaggsgrad{q}$ can get rid of Byzantines, the identification score $\groupscore{i}{q}$ can provably characterize the potential for the $\subsgrad{i}{q}$ being a sub-vector of an honest gradient.
Then, GAIN\xspace collects the identification scores from all groups and computes the final aggregation result.
In particular, the final identification score $\clientscore{i}$ of each client is composed of its identification scores received from all groups as follows.
\begin{align}
    \label{eq:client_score}
    \clientscore{i} = \sum_{q=1}^{p}\groupscore{i}{q},
    \quad i\in[n].
\end{align}


\textbf{Aggregation.}
To avoid integrity failure, GAIN\xspace selects total $n-f$ gradients with the lowest identification scores for aggregation.
Let $\mathcal{I}$ denote the index set of selected gradients, then the average of selected gradients is output as the final aggregation result as follows:
\begin{align}
    \aggsgrad{} = \frac{1}{n-f}\sum_{i\in\mathcal{I}}\sgrad{i}{}.
\end{align}

Note that in the first stage (Decomposition) of GAIN\xspace, $\mathcal{A}$ could be any $c$-resilient AGR (\cref{asp:byzantine_resilience}). The key difference lies in that all the existing robust AGRs (Multi-Krum, Bulyan, etc) directly operate on the original gradients before aggregation; instead we propose to apply robust AGRs on the decomposed gradient, followed by identification before aggregation. In this way, we can help enhance the identification ability and integrity of the current robust AGRs that satisfy the $c$-resilient property (\cref{asp:byzantine_resilience}) in the non-IID setting. 
Detailed theoretical analysis and empirical support can be referred to \cref{sec:theoretical} and \cref{sec:experiments} respectively.

\section{Theoretical Analysis}
\label{sec:theoretical}
In this section, we provide a convergence analysis for our GAIN\xspace approach.

We analyze a popular FL model widely considered by
\cite{karimireddy2021history,karimireddy2022bucketing,acharya2022cgm}.
In particular, each local gradient is computed by SGD as follows.
\begin{align}
\label{eq:honest_local_update}
  \sgrad{i}{t}=\nabla\loss(\param[t];\batch{i}{t}),
  \quad i\in[n],
\end{align}
where $\batch{i}{t}$ represents a minibatch uniformly sampled from the local data distribution $\samples{i}$ in the $t$-th communication round,
and $\nabla\loss(\param[t],\batch{i}{t})$ represents the gradient of loss over the minibatch $\batch{i}{t}$.

We make the following assumptions, which are standard in FL \cite{karimireddy2021history,karimireddy2022bucketing,acharya2022cgm}.

\begin{restatable}[Unbiased Estimator]{assumption}{aspunbias}
\label{asp:unbias}
The stochastic gradients sampled from any local data distribution are unbiased estimators of local gradients over ${\mathbb{R}}^{d}$ for all clients, i.e.,
\begin{equation}
\label{eq:unbias}
\begin{gathered}
\mathbb{E}_{\batch{i}{t}}[\nabla\loss[i](\param;\batch{i}{t})]=\nabla\loss[i](\param),\\
\forall\param\in{\mathbb{R}}^{d}, i\in[n], t\in{\mathbb{N}}^+.
\end{gathered}
\end{equation}
\end{restatable}

\begin{restatable}[Bounded Variance]{assumption}{aspvar}
\label{asp:bounded_var}
The variance of stochastic gradients sampled from any local data distribution is uniformly bounded over ${\mathbb{R}}^{d}$ for all clients, i.e., there exists $\sigma\ge0$ such that
\begin{equation}
\label{eq:bounded_var}
\begin{gathered}
\mathbb{E}\|\nabla\loss[i](\param;\batch{i}{t})-\nabla\loss[i](\param)\|^2\le\sigma^2,\\
\forall\param\in{\mathbb{R}}^{d}, i\in[n], t\in{\mathbb{N}}^+.
\end{gathered}
\end{equation}
\end{restatable}

\begin{restatable}[Gradient Dissimilarity]{assumption}{aspdissim}
\label{asp:dissimilarity}
The difference between the local gradients and the global gradient is uniformly bounded over ${\mathbb{R}}^{d}$ for all clients, i.e., there exists $\kappa\ge0$ such that
\begin{align}
\label{eq:dissimilarity}
\|\nabla\loss[i](\param)-\nabla\loss(\param)\|^2 \le\kappa^2,
\quad\forall\param\in{\mathbb{R}}^{d}, i\in[n].
\end{align}
\end{restatable}

We consider arbitrary non-convex loss function $\loss(\cdot)$ that satisfies the following Lipschitz condition. This condition is widely applied in the convergence analysis of Byzantine-robust federated learning \cite{karimireddy2022bucketing,allen2020safeguard,el2021collaborative}.
\begin{restatable}[Lipschitz Smoothness]{assumption}{asplipschitz}
\label{asp:lipschitz}
The loss function is $L$-Lipschitz smooth with respect over ${\mathbb{R}}^d$, i.e., 
\begin{equation}
\begin{gathered}
\|\nabla\loss({\bm{w}})-\nabla\loss({\bm{w}}')\|\le L\|{\bm{w}}-{\bm{w}}'\|,\\
\forall{\bm{w}},{\bm{w}}'\in{\mathbb{R}}^d.
\end{gathered}
\end{equation}
\end{restatable}

\cref{asp:unbias} establishes the unbiased property of stochastic gradient.
\cref{asp:bounded_var} bounds the variance of the stochastic gradients within a client.
And \cref{asp:dissimilarity} is a common measure of the non-IID level in federated learning \cite{data2021byzantine,karimireddy2020scaffold,karimireddy2022bucketing}.

We consider robust AGRs that satisfy the following robustness criterion (\cref{asp:byzantine_resilience}) introduced by \cite{el2021momentum}.
A wide class of state-of-the-art AGRs satisfy this criterion \cite{el2021momentum}.
\begin{restatable}[$(f,\lambda)$-resilient]{definition}{defbyzresil}
\label{asp:byzantine_resilience}
For $f\le n$ and real value $\lambda$, an AGR $\mathcal{A}$ is called $(f,\lambda)$-resilient if for any input $\{{\bm{x}}_1,\ldots,{\bm{x}}_n\}$ and any set ${\mathcal{S}}\subseteq[n]$ of size $n-f$,
the output of $\mathcal{A}$ satisfies:
\begin{equation}
\begin{gathered}
\|\mathcal{A}({\bm{x}}_1, \ldots,{\bm{x}}_n) - \Bar{{\bm{x}}}_{\mathcal{S}}\|\le \lambda\max_{i,i'\in{\mathcal{S}}}\|{\bm{x}}_i-{\bm{x}}_{i'}\|, \\
\end{gathered}
\end{equation}
where $\Bar{{\bm{x}}}_{\mathcal{S}}=\sum_{i\in{\mathcal{S}}}{\bm{x}}_i/|{\mathcal{S}}|$.
\end{restatable}

We show that given any $(f,\lambda)$-resilient base AGR $\mathcal{A}$, our GAIN\xspace can help the global model to reach a better parameter point.

\begin{restatable}[]{proposition}{propconvergence}
\label{prop:convergence}
Suppose \cref{asp:unbias,asp:bounded_var,asp:dissimilarity,asp:lipschitz} hold, and let $\eta=1/2L$.
Given an $(f,\lambda)$-resilient robust AGR $\mathcal{A}$, we start from ${\bm{w}}^0$ and run GAIN\xspace for $T$ communication rounds, it satisfies
\begin{align}
\label{eq:prop_convergence}
\loss({\bm{w}}^0)\ge\frac{3}{16L}\sum_{t=1}^T(\|\nabla\loss({\bm{w}}^t)\|^2-e^2),
\end{align}
where
\begin{align}
e^2
={\mathcal{O}}((\kappa^2+\sigma^2)(1+\frac{n-f+1}{p})(1+c^2+\frac{1}{n-f})\frac{f^2}{(n-f)^2}).
\end{align}
\end{restatable}

Please refer to \cref{appsec:proof} for the proof.
\cref{prop:convergence} provides an upper bound for the sum of gradient norms in presence of Byzantine gradients.
\cref{eq:prop_convergence} indicates that as the number of communication rounds increases, we can find an approximate optimal parameter ${\bm{w}}$ with $\|\nabla\loss({\bm{w}})\|\le e$.
Furthermore, as the number of sub-vectors $p$ increases, the approximation becomes better, i.e., $e^2$ decreases, which validates the efficacy of our approach.
From another aspect, \cref{prop:convergence} also characterizes the fundamental difficulties of Byzantine-robust federated learning in the non-IID setting.
The negative term $-e^2$ on the RHS implies that FL may never converge to an optimal point.
By contrast, the global model may wander among sub-optimal points.
What's more, even after reaching the convergence point, the global model may step into another sub-optimal in the next communication round.
A detailed comparison of the convergence results between our approach and recent works is presented in \cref{appsec:comparaion}.


\section{Experiments}
\label{sec:experiments}

\subsection{Experimental Setups}
\label{subsec:experimental_setups}

\textbf{Datasets.} Our experiments are conducted on three real-world datasets: CIFAR-10 \cite{krizhevsky2009cifar}, CIFAR-100 \cite{krizhevsky2009cifar}, a subset of ImageNet \cite{russakovsky2015imagenet} refered as ImageNet-12 and FEMNIST \cite{caldas2018leaf}.
CIFAR-10 dataset consists of 60,000 32$\times$32 color images in 10 classes, with 6,000 images per class. There are 50,000 training images and 10,000 test images in CIFAR-10 dataset.
CIFAR-100 dataset consists of 60,000 32$\times$32 color images in 100 classes, with 600 images per class. There are 50,000 training images and 10,000 test images in CIFAR-100 dataset.
ImageNet-12 consists of 15,600 color images in 12 classes, with 1,300 images per class. There are 12,480 training images and 3,120 test images in this subset of ImageNet.
FEMNIST consists of 817,851 28$\times$28 gray-scale images in 62 classes.
There are 772,066 training images and 857,85 test images in FEMNIST.

For FEMNIST, the data is naturally partitioned into 3,597 clients based on the writer of the digit/character.
For each client, we randomly sample a 0.9 portion of data as the training data and let the remaining 0.1 portion of data be the test data following \cite{caldas2018leaf}.
Intuitively, the data distribution across different clients is non-IID.

\begin{table}[t]
\caption{Accuracy
(mean$\pm$std)
of different defenses under 6 attacks on CIFAR-10, ImageNet-12, FEMNIST, and CIFAR-100.}
\label{tbl:main_experiments}
\begin{center}
\resizebox{.9\textwidth}{!}{
\input{tabulars/main_experiments_4x1}
}
\end{center}
\end{table}
\textbf{Evaluated attacks.} 
We consider six representative attacks
BitFlip \cite{allen2020safeguard}, LabelFlip \cite{allen2020safeguard}, LIE \cite{baruch2019lie}, Min-Max \cite{shejwalkar2021dnc}, Min-Sum \cite{shejwalkar2021dnc} and IPM \cite{xie2020ipm}.
The detailed hyperparameter setting of the attacks are shown in \cref{apptbl:attack_hyperparams} in \cref{appsec:setup}.

\textbf{Baselines.}
We consider 6 robust AGRs:
 \cite{blanchard2017krum},
Bulyan \cite{guerraoui2018bulyan},
Median \cite{yin2018mediantrmean},
RFA \cite{pillutla2019geometric},
DnC \cite{shejwalkar2021dnc},
RBTM \cite{el2021collaborative}.
Among the above six defenses, Bulyan, Median, and RBTM are conservative, and Multi-Krum, RFA, and DnC are radical.
We compare each AGR with its variant with GAIN\xspace.
The detailed hyperparameter settings of the robust AGRs are listed in \cref{apptbl:defense_hyperparams} in \cref{appsec:setup}.

\textbf{Evaluation.}
We use top-1 accuracy, i.e., the proportion of correctly predicted testing samples to total testing samples, to evaluate the performance of global models.
We run each experiment for 5 times and report the mean and standard deviation of the highest accuracy during the training process.

\textbf{Other settings.}
We utilize AlexNet \cite{krizhevsky2017alexnet}, SqueezeNet \cite{iandola2016squeezenet}, ResNet-18 \cite{he2016resnet} and a four-layer CNN \cite{caldas2018leaf} for CIFAR-10, CIFAR-100, ImageNet-12 and FEMNIST, respectively.
The number of Byzantine clients of all datasets is set to $f=0.2\cdotn$.
For the partition of set $\{1,...,d\}$, we randomly partition $\{1,...,d\}$ into $p$ disjoint subsets with equal size.
Please refer to \cref{apptable:default_setup} in \cref{appsec:setup} for more details.


\subsection{Experiment Results}
\label{subsec:results}

\textbf{Main results.}
\cref{tbl:main_experiments} illustrates the results of different defenses against popular attacks on CIFAR-10, CIFAR-100, ImageNet-12 and FEMNIST.
From these tables, we observe that:
\begin{itemize}
    \item[(1)] Integrating current defenses into our GAIN\xspace generally outperform all their original versions on all datasets, which verifies the efficacy of our proposed GAIN\xspace.
    For example, GAIN\xspace improves the accuracy of Median by 15.93\% under Min-Sum attack on CIFAR-10.
    \item[(2)] The improvement of DnC+GAIN\xspace to DnC is relatively mild on CIFAR-10.
    Our interpretation is that when the dataset is relatively small and simple, DnC is capable of obtaining a rational gradient estimation.
    Nevertheless, on larger and more complex datasets, i.e., FEMNIST and ImageNet-12, DnC fails to achieve satisfactory performance under Byzantine attacks.
    \item[(3)] We find that although RFA collapses on FEMNIST, integrating into our GAIN\xspace can still improve it to satisfactory performance.
    Our illustration is that although the aggregated gradient of RFA deviates from the optimal gradient, it can still assist in identifying honest gradients when combined with GAIN\xspace.
    As a result, GAIN\xspace-RFA is still effective on FEMNIST.
    \item[(4)] Note that the improvement of GAIN on conservative methods is greater. 
    We contribute this phenomenon to the gradient heterogeneity due to non-IID data.
    Excluding honest gradients deviates the aggregated gradients from the average of honest gradients, thus degrading the performance of conservative methods.
    When the non-IID degree increases, the gradient heterogeneity increases.
    As a result, the impact of excluding honest gradients may even be larger than incorporating Byzantine gradients.
    Therefore, the improvement on the conservative AGRs is greater.
\end{itemize}

\textbf{Number of sub-vectors.}
We study the influence of sub-vector number $p$ on the heterogeneous CIFAR-10 dataset.
\cref{fig:ngroups} shows the performance and honest ratio of a conservative AGR (Bulyan) and a radical AGR (Multi-Krum) across $p=\{100, 1000\}$.
The results show that for both conservative and radical AGRs, GAIN\xspace with a larger sub-vector number $p$ can select a higher proportion of honest clients and achieve better performance.
When the sub-vector number $p$ increases, our GAIN\xspace can better handle the identification failure and the integrity failure, which corresponds to our theoretical analysis in \cref{sec:theoretical}.


\begin{figure}[t]
\centering
\includegraphics[width=0.3\textwidth]{figures/ngroups_legend.pdf}
\\
\begin{subfigure}[]{0.23\textwidth}
\centering
\includegraphics[width=\textwidth]{figures/ngroups_bulyan_performance.pdf}
\caption{Performance of a\\ conservative AGR.}
\label{fig:ngroups_bulyan_performance}
\end{subfigure}
\begin{subfigure}[]{0.23\textwidth}
\centering
\includegraphics[width=\textwidth]{figures/ngroups_bulyan_selection.pdf}
\caption{Honest ratio of a\\ conservative AGR.}
\label{fig:ngroups_bulyan_selection}
\end{subfigure}
\begin{subfigure}[]{0.23\textwidth}
\centering
\includegraphics[width=\textwidth]{figures/ngroups_mkrum_performance.pdf}
\caption{Performance of a\\ radical AGR.}
\label{fig:ngroups_mkrum_performance}
\end{subfigure}
\begin{subfigure}[]{0.23\textwidth}
\centering
\includegraphics[width=\textwidth]{figures/ngroups_mkrum_selection.pdf}
\caption{Honest ratio of a\\ radical AGR.}
\label{fig:ngroups_mkrum_selection}
\end{subfigure}
\caption{The behaviors of a conservative AGR (Bulyan) and a radical AGR (Multi-Krum) across sub-vector number $p=100,1000$ under the attack of $20\%$ Byzantines in the non-IID setting on CIFAR-10 dataset. More detailed setups are covered in \cref{appsec:other_setup}.
}
\label{fig:ngroups}
\end{figure}


\textbf{Results on different levels of non-IID.}
We discuss the impact of non-IID level of data distributions.
We modify the concentration parameter $\beta$ to change the non-IID level.
A smaller $\beta$ implies a higher non-IID level.
\cref{tbl:non_iid} demonstrates the accuracy of different defenses under LIE attack on CIFAR-10 dataset across $\beta=\{0.3, 0.7\}$.
Other setups follow the default setup of the main experiments as illustrated in \cref{subsec:experimental_setups} and \cref{appsec:setup}.
As shown in \cref{tbl:non_iid}, all the existing AGRs that combined with GAIN\xspace achieve better performances than their original versions, which validates that integrating into our GAIN\xspace can effectively defend against Byzantine attacks under different non-IID levels.
Moreover, when the level of non-IID is higher, the improvement on robust AGRs is more significant.
The results further confirm that our GAIN\xspace can overcome the failures aggravated under a higher non-IID level.
\begin{table}[h]
\caption{Accuracy (mean$\pm$std) of different defenses against LIE attack under different non-IID levels on CIFAR-10.
A smaller $\beta$ implies a higher non-IID level.
}
\label{tbl:non_iid}
\begin{center}
\scalebox{1.0}{
\input{tabulars/noniid_level}
}
\end{center}
\end{table}

\textbf{Results on different number of Byzantine clients.}
We also conduct experiments across different number of Byzantine clients.
Other setups follow the default setup of the main experiments in \cref{subsec:experimental_setups} and \cref{appsec:setup}.
\cref{tbl:attacker_number} demonstrates the results of different defenses under LIE attack across $f=\{5, 15\}$ Byzantine clients on CIFAR-10 dataset.
As shown in \cref{tbl:attacker_number}, our GAIN\xspace outperforms the corresponding baselines across all Byzantine client numbers.

\begin{table}[h]
\caption{Accuracy (mean$\pm$std) of different defenses against LIE attack with different Byzantine client numbers $f=\{5, 15\}$ on CIFAR-10.
The number of total clients is $n=50$.
}
\label{tbl:attacker_number}
\begin{center}
\scalebox{1.0}{
\input{tabulars/attacker_number}
}
\end{center}
\end{table}

\textbf{Results on different number of clients.}
We further analyze the efficacy of our GAIN\xspace under different number of clients.
Detailed setups can be found in \cref{appsec:further_analysis}.
And the experimental results are shown in \cref{tbl:client_number} in \cref{appsec:further_analysis}.
All results demonstrate that AGRs that combine with our GAIN\xspace consistently outperform all their original versions, which validates that integrating with our GAIN\xspace can effectively defend against Byzantine across different number of clients.


\section{Conclusion}
\label{sec:conclusion}

In this work, we identify two root causes of performance degradation of robust AGRs in the non-IID setting.
The first cause is the integrity failure of conservative AGRs.
Conservative AGRs aggregate only few honest gradients,
which is unreliable due to the gradient heterogeneity in the non-IID setting.
The second cause is the identification failure of radical AGRs.
Radical AGRs inevitably introduce Byzantine gradients into aggregation due to the curse of dimensionality aggravated by the non-IIDness.
Both failures result in a sharp deviation of the aggregated gradient.
Motivated by the above discoveries, we propose a novel GrAdient decomposItioN (GAIN\xspace) method that can be combined with most existing defenses and overcome both failures.
We also provide convergence analysis for integrating existing robust AGRs into GAIN\xspace.
Empirical studies on three real-world datasets justify the efficacy of our  proposed GAIN\xspace.

\clearpage










