marginparsep has been altered.
topmargin has been altered.
marginparwidth has been altered.
marginparpush has been altered.
The page layout violates the ICML style. Please do not change the page layout,
or include packages like geometry, savetrees, or fullpage, which change it for
you. We’re not able to reliably undo arbitrary changes to the style. Please
remove the offending package(s), or layout-changing commands and try again.

Aspis: Robust Detection for Distributed Learning

Konstantinos Konstantinidis 1  Aditya Ramamoorthy 1

###### Abstract

State-of-the-art machine learning models are routinely trained on large-scale
distributed clusters. Crucially, such systems can be compromised when some of
the computing devices exhibit abnormal (_Byzantine_) behavior and return
arbitrary results to the _parameter server_ (PS). This behavior may be
attributed to a plethora of reasons, including system failures and
orchestrated attacks. Existing work suggests _robust aggregation_ and/or
computational _redundancy_ to alleviate the effect of distorted gradients.
However, most of these schemes are ineffective when an adversary knows the
task assignment and can choose the attacked workers judiciously to induce
maximal damage. Our proposed method Aspis assigns gradient computations to
worker nodes using a subset-based assignment which allows for multiple
consistency checks on the behavior of a worker node. Examination of the
calculated gradients and post-processing (clique-finding in an appropriately
constructed graph) by the central node allows for efficient detection and
subsequent exclusion of adversaries from the training process. We prove the
Byzantine resilience and detection guarantees of Aspis under weak and strong
attacks and extensively evaluate the system on various large-scale training
scenarios. The principal metric for our experiments is the test accuracy, for
which we demonstrate a significant improvement of about 30% compared to many
state-of-the-art approaches on the CIFAR-10 dataset. The corresponding
reduction of the fraction of corrupted gradients ranges from 16% to 99%.

††footnotetext:  1Department of Electrical and Computer Engineering, Iowa
State University, Ames, IA 50011 USA. Correspondence to: Konstantinos
Konstantinidis<EMAIL_ADDRESS>Aditya Ramamoorthy<EMAIL_ADDRESS>

##  1 Introduction

The increased sizes of datasets and associated model complexities have
established distributed training setups as the de facto method for training
models at scale. A typical setup consists of one central machine (_parameter
server_ or PS) and multiple worker machines. The PS coordinates the protocol
by communicating parameters and maintaining the global copy of the model. The
workers compute gradients of the loss function with respect to the
optimization parameters and transmit them to the PS. The PS then updates the
model. This is an iterative process and is repeated until convergence. Several
frameworks including MXNet Chen et al. (2015), CNTK Seide & Agarwal (2016) and
PyTorch Paszke et al. (2019) support this architecture.

Despite the speedup benefits of such distributed settings, they are prone to
so-called _Byzantine_ failures, i.e., when a set of workers return malicious
or erroneous computations. Faulty workers may modify their portion of the data
and/or models arbitrarily. This can happen on purpose due to adversarial
attacks or inadvertently due to hardware or software failures, such as bit-
flipping in the memory or communication media. For example, Kim et al. (2014)
showed that bit-flips in commodity DRAM can happen merely through frequent
data access of the same address. Reference Rakin et al. (2019) exposes the
vulnerability of neural networks to such failures and identifies weight
parameters that could maximize accuracy degradation. As a result, the
distorted gradients can derail the optimization and lead to low test accuracy.
Devising training algorithms that are resilient to such failures and which can
efficiently _aggregate_ the received gradients has inspired a series of works
Gupta & Vaidya (2019); Alistarh et al. (2018); Chen et al. (2017); Blanchard
et al. (2017).

In order to alleviate the malicious effects, some existing papers use majority
voting and median-based defenses Damaskinos et al. (2019); Yin et al. (2019;
2018); Xie et al. (2018); Blanchard et al. (2017); Chen et al. (2017). Other
works replicate the gradient tasks across the cluster Konstantinidis &
Ramamoorthy (2021); Yu et al. (2019); Rajput et al. (2019); Chen et al.
(2018); Data et al. (2018). Finally, some schemes try to rank and/or detect
the Byzantines Regatti et al. (2020); Xie et al. (2019b); Chen et al. (2018).

###  1.1 Contributions

In this work, we present _Aspis_ , our detection-based Byzantine resilience
scheme for distributed training. Aspis uses a combination of redundancy and
robust aggregation. Unlike previous methods, the redundant subset-based
assignment for gradient computations is judiciously chosen such that the PS
can perform global consistency checks on the behavior of the workers by
examining the returned gradients. By performing clique-finding in appropriate
graphs, the PS can perform _detection_ as a first line of defense to exclude
adversaries from further being considered during the aggregation. Note that we
make no assumption of privacy and our work as well as compared methods do not
apply to federated learning.

Aspis has the following salient features: (i) Under weak attacks where the
Byzantines act independently (without significant collusion) they will always
be detected by the proposed novel clique-based algorithm. (ii) Furthermore,
Aspis is resilient to stronger attacks where adversaries collude in optimal
ways; these are much stronger than those considered in prior work. In
particular, instead of simulating a random set of adversaries Rajput et al.
(2019); Chen et al. (2018), we have crafted a non-trivial attack designed
explicitly for our system such that the adversaries can evade detection and
potentially corrupt more gradient values.

For both weak and strong attacks we provide theoretical guarantees on the
fraction of corrupted gradients for Aspis. Comparisons with other methods
indicate reductions in the fraction of corrupted gradients ranging from 16% to
99%.

Finally, we present exhaustive top-1 classification accuracy results on the
CIFAR-10 dataset for a variety of gradient distortion attacks coupled with
choice/behavior patterns of the adversarial nodes. Our results indicate an
average 30% accuracy increase on CIFAR-10 Krizhevsky (2009) under the most
sophisticated attacks. In summary, the performance gap between Aspis and other
methods is especially stark in the strong attack scenario.

###  1.2 Related Work

Existing papers consider a wide range of assumptions regarding the maximum
number of adversaries, their ability to collude, their possession of knowledge
involving the data assignment and the defense protocol, and whether the
adversarial machines are chosen at random or systematically. In this work, we
will assume strong adversarial models as in prior work Konstantinidis &
Ramamoorthy (2021); Baruch et al. (2019); Xie et al. (2018); Yin et al.
(2018); El Mhamdi et al. (2018); Shen et al. (2016).

The first category of related prior work is called _robust aggregation_
Damaskinos et al. (2019); Yin et al. (2019; 2018); Xie et al. (2018);
Blanchard et al. (2017); Chen et al. (2017). These methods provide robustness
guarantees up to a constant fraction of the nodes being adversarial. However,
this fraction is usually very small and the guarantees are limited (_e.g.,_
only guaranteeing that the output of the aggregator has positive inner product
with the true gradient El Mhamdi et al. (2018); Blanchard et al. (2017)),
which compromises their practicality. Also, they require significant
asymptotic complexity Xie et al. (2018) and strict assumptions such as
convexity of the loss function that need to be adjusted for each individual
training algorithm. Some popular robust aggregators are based on _trimmed
mean_ Xie et al. (2018); Yin et al. (2018); El Mhamdi et al. (2018) and return
a subset of the values which are closest to the median element-wise. _Auror_
in Shen et al. (2016) runs _k-means_ clustering on the gradients and outputs
the mean of the largest cluster. In _signSGD_ Bernstein et al. (2019), workers
retain only the sign information and the PS uses majority voting aggregation.
_Krum_ in Blanchard et al. (2017) determines a single honest worker whose
gradient minimizes the distance to its $k\in\mathbb{N}$ nearest neighbors.
Krum may converge to an _ineffectual_ model in non-convex high dimensional
problems and _Bulyan_ El Mhamdi et al. (2018) is proposed as an alternative.
However, Bulyan is designed to defend only up to a small fraction of corrupted
workers.

The second category is based on _redundancy_ and it establishes resilience by
assigning each gradient task to more than one node Konstantinidis &
Ramamoorthy (2021); Yu et al. (2019); Rajput et al. (2019); Chen et al.
(2018); Data et al. (2018). Existing techniques are sometimes combined with
robust aggregation Rajput et al. (2019). Fundamentally, these methods require
higher computation load per worker but they come with stronger guarantees of
correcting the erroneous gradients. It is important to note that most schemes
in this category can be made to fail by a powerful _omniscient_ adversary
which can mount judicious attacks Konstantinidis & Ramamoorthy (2021). _DRACO_
Chen et al. (2018) builds on Raviv et al. (2018); Tandon et al. (2017) and
uses majority vote and Fourier decoders to filter out the adversarial effects.
With $q$ Byzantines, it guarantees recovery as if the system had no
adversaries, when each task is replicated $r\geq 2q+1$ times; it is not
applicable if this bound is violated. Nonetheless, this requirement is very
restrictive for the common assumption that up to half of the workers can be
Byzantine. _DETOX_ in Rajput et al. (2019) extends DRACO and performs multiple
stages of gradient filtering requiring smaller redundancy. However, its
resilience guarantees depend heavily on a “random choice” of the adversaries.
Subsequent work in Konstantinidis & Ramamoorthy (2021) has crafted simple
attacks to make this aggregator fail under a more careful choice of
adversaries. _ByzShield_ in Konstantinidis & Ramamoorthy (2021) borrows ideas
from combinatorial design theory Van Lint & Wilson (2001) to redundantly
assign the tasks and minimize the distortion fraction. Despite ByzShield’s
accuracy improvements, its authors have not designed an attack tailored to
their method. In this work, we propose a worst-case attack that targets Aspis
and prove that it is optimal.

A third category focuses on _ranking_ and/or _detection_ Regatti et al.
(2020); Chen et al. (2018); Xie et al. (2019b). _Zeno_ in Xie et al. (2019b)
ranks each worker using a score that depends on the estimated loss and the
magnitude of the update. Zeno requires strict assumptions on the smoothness of
the loss function and the variance of the gradient estimates in order to
tolerate an adversarial majority in the cluster. Similarly, _ByGARS_ Regatti
et al. (2020) computes reputation scores for the nodes based on an auxiliary
dataset; these scores are used to weigh the contribution of each gradient to
the model update. Its convergence result depends on the assumption of a
strongly convex loss function. In contrast, our method does not rely on such
restrictive assumptions. Also, these works have not used or constructed worst-
case attacks that would evaluate the methods in adversarial settings.

Figure 1: Aggregation of gradients on a cluster.

##  2 Distributed Training Formulation

The formulation we discuss is standard in distributed deep learning. Assume a
loss function $l_{i}(\mathbf{w})$ for the $i^{\mathrm{th}}$ sample where
$\mathbf{w}\in\mathbb{R}^{d}$ is the parameter set of the model.111The paper’s
heavily-used notation is summarized in Appendix Table 6. We use _mini-batch
Stochastic Gradient Descent_ (SGD) to minimize the loss over the entire
dataset, i.e.,

$\min_{\mathbf{w}}L(\mathbf{w})=\min_{\mathbf{w}}\frac{1}{n}\sum\limits_{i=1}^{n}l_{i}(\mathbf{w})$

where $n$ is the dataset size. Initially, $\mathbf{w}$ is randomly set to
$\mathbf{w}_{0}$ ($\mathbf{w}_{t}$ is the model state at the end of iteration
$t$). A random _batch_ $B_{t}$ of $b$ samples is chosen to perform the update
in the $t^{\mathrm{th}}$ iteration. Thus,

$\mathbf{w}_{t+1}=\mathbf{w}_{t}-\eta_{t}\frac{1}{|B_{t}|}\sum\limits_{i\in
B_{t}}\nabla l_{i}(\mathbf{w}_{t})$ (1)

where $\eta_{t}$ is the learning rate of the $t^{\mathrm{th}}$ iteration. The
workers, denoted $U_{1},U_{2},\dots,U_{K}$, compute gradients on subsets of
the batch. The training is _synchronous_ , i.e., the PS waits for all workers
to return before performing an update. It stores the dataset and the model and
coordinates the protocol.

Task assignment: Each batch $B_{t}$ is split into $f$ disjoint files
$\\{B_{t,i}\\}_{i=0}^{f-1}$. These files are then assigned to the workers
according to our placement policy. Computational redundancy is introduced by
assigning a given file to $r>1$ workers; we will occasionally use the term
_group_ (of the assigned workers) to refer to a file. It follows that each
worker is responsible for $l=fr/K$ files ($l$ is the _computation load_). We
let $\mathcal{N}(U_{j})$ to be the set of files assigned to worker $U_{j}$ and
$\mathcal{N}(B_{t,i})$ to be the group of workers that are assigned file
$B_{t,i}$. Our placement scheme is such that $\mathcal{N}(B_{t,i})$ uniquely
identifies the file $B_{t,i}$; thus, we will sometimes refer to the file
$B_{t,i}$ by its worker assignment, $\mathcal{N}(B_{t,i})$. The actual
placement algorithm will be presented in Section 3.

Adversary model: We assume that at most $q$ workers can be adversarial, i.e.,
they can return arbitrary values to the PS. The workers know the data
assignment of all nodes, the parameters $\mathbf{w}_{t}$ and the defense at
every iteration (_omniscient_ attack); they can also collude. The adversarial
machines may change at every single iteration. We will suppose that $q<K/2$.
We emphasize that our attack setting is more powerful than random failures
considered in related redundancy-based work Rajput et al. (2019); Chen et al.
(2018). For each assigned file $B_{t,i}$ a worker $U_{j}$ will return the
value $\hat{\mathbf{g}}_{t,i}^{(j)}$ to the PS. Then,

$\hat{\mathbf{g}}_{t,i}^{(j)}=\left\\{\begin{array}[]{ll}\mathbf{g}_{t,i}&\text{
if }U_{j}\text{ is honest},\\\ \mathbf{*}&\text{otherwise},\\\
\end{array}\right.$ (2)

where $\mathbf{g}_{t,i}$ is the sum of the loss gradients on all samples in
file $B_{t,i}$, i.e.,

$\mathbf{g}_{t,i}=\sum\limits_{j\in B_{t,i}}\nabla l_{j}(\mathbf{w}_{t})$

and $\mathbf{*}$ is any arbitrary vector in $\mathbb{R}^{d}$. Within this
setup, we examine multiple adversarial scenarios.

Training: We will refer to Figure 1 for this exposition. There are $K=6$
machines and $f=4$ distinct files (represented by colored circles) replicated
$r=3$ times.222Some arrows and ellipses have been omitted from Figure 1;
however, all files will be going through detection. Each of the workers is
assigned to $l=2$ files and computes the sum of gradients (or an distorted
value) on each of them. The “d” ellipses refer to detection operations the PS
performs immediately after receiving all the gradients.

The algorithm starts with the assignment of files to workers. Subsequently,
each worker $U_{i}$ will compute all $l$ file gradients that involve its
assigned files $\mathcal{N}(U_{i})$ and return them to the PS. In every
iteration, the PS will initially run our detection algorithm in an effort to
identify the $q$ adversaries and will act differently depending on the
detection outcome.

  * •

_Case 1: Successful detection_. The PS will ignore all detected faulty
machines and keep only the gradients from the remaining workers. Assume that
$h$ workers $U_{i_{1}},U_{i_{2}},\dots,U_{i_{h}}$ have been identified as
honest. For each of the $f$ files if there is at least one honest worker that
processed it, the PS will pick one of the “honest” gradient values. The chosen
gradients are then averaged for the update (_cf._ Eq. (1)). For instance, in
Figure 1, assume that $U_{1}$, $U_{2}$ and $U_{4}$ have been identified as
faulty. During aggregation, the PS will ignore the red file as all 3 copies
have been compromised. For the orange file, it will pick either the gradient
computed by $U_{5}$ or $U_{6}$ as both of them are honest.

  * •

_Case 2: Unsuccessful detection_. During aggregation, the PS will perform a
majority vote across the computations of each file. Recall that each file has
been processed by $r$ workers. For each such file $B_{t,i}$, the PS decides a
majority value $\mathbf{m}_{i}$

$\mathbf{m}_{i}:=\mathrm{majority}\left\\{\hat{\mathbf{g}}_{t,i}^{(j)}:U_{j}\in\mathcal{N}(B_{t,i})\right\\}.$
(3)

Assume that $r$ is odd and let $r^{\prime}=\frac{r+1}{2}$. Under the rule in
Eq. (3), the gradient on a file is distorted only if at least $r^{\prime}$ of
the computations are performed by Byzantines. Following the majority vote, we
will further filter the gradients using coordinate-wise median and will be
referring to the combination of these two steps as _robust aggregation_ ; a
similar setup was considered in Konstantinidis & Ramamoorthy (2021); Rajput et
al. (2019). For example, in Figure 1, all returned values for the red file
will be evaluated by a majority vote function on the PS which decides a single
output value; a similar voting is done for the other 3 files. After the voting
process, Aspis applies coordinate-wise median on the “winning” gradients
$\mathbf{m}_{i}$, $i=0,1,\dots,f-1$.

Input: Dataset of $n$ samples, batchsize $b$, computation load $l$, redundancy
$r$,
number of files $f$, maximum iterations $T$, file assignments
$\\{\mathcal{N}(U_{i})\\}_{i=1}^{K}$.

1 The PS randomly initializes model’s parameters to $\mathbf{w}_{0}$.

2 for  _$t=1$ to $T$_ do

3 PS chooses a random batch $B_{t}\subseteq\\{1,2,\dots,n\\}$ of $b$ samples,
partitions it into $f$ files $\\{B_{t,i}\\}_{i=0}^{f-1}$ and assigns them to
workers according to $\\{\mathcal{N}(U_{i})\\}_{i=1}^{K}$. It then transmits
$\mathbf{w}_{t}$ to all workers.

4 for  _each worker $U_{j}$_ do

5 if  _$U_{j}$ is honest_ then

6 for  _each file $i\in\mathcal{N}(U_{j})$_ do

7 $U_{j}$ computes the sum of gradients
$\hat{\mathbf{g}}_{t,i}^{(j)}=\sum\limits_{k\in B_{t,i}}\nabla
l_{k}(\mathbf{w}_{t}).$

8 end for

9

10 else

11 $U_{j}$ constructs $l$ adversarial vectors
$\hat{\mathbf{g}}_{t,i_{1}}^{(j)},\hat{\mathbf{g}}_{t,i_{2}}^{(j)},\dots,\hat{\mathbf{g}}_{t,i_{l}}^{(j)}.$

12 end if

13 $U_{j}$ returns
$\hat{\mathbf{g}}_{t,i_{1}}^{(j)},\hat{\mathbf{g}}_{t,i_{2}}^{(j)},\dots,\hat{\mathbf{g}}_{t,i_{l}}^{(j)}$
to the PS.

14 end for

15 PS runs a detection algorithm to identify the adversaries.

16 if  _detection is successful_ then

17 Let $H$ be the detected honest workers. Initialize a non-corrupted gradient
set as $\mathcal{G}=\emptyset$.

18 for  _each file in $\\{B_{t,i}\\}_{i=0}^{f-1}$_ do

19 PS chooses the gradient of a worker in $\mathcal{N}(B_{t,i})\cap H$ (if
non-empty) and adds it to $\mathcal{G}$.

20 end for

21
$\mathbf{w}_{t+1}=\mathbf{w}_{t}-\eta_{t}\frac{1}{|\mathcal{G}|}\sum\limits_{\mathbf{g}\in\mathcal{G}}\mathbf{g}.$

22 else

23 for  _each file in $\\{B_{t,i}\\}_{i=0}^{f-1}$_ do

24 PS determines the $r$ workers in $\mathcal{N}(B_{t,i})$ which have
processed $B_{t,i}$ and computes
$\mathbf{m}_{i}=\mathrm{majority}\left\\{\hat{\mathbf{g}}_{t,i}^{(j)}:j\in\mathcal{N}(B_{t,i})\\}\right\\}.$

25 end for

26 PS updates the model via
$\mathbf{w}_{t+1}=\mathbf{w}_{t}-\eta_{t}\times\mathrm{median}\\{\mathbf{m}_{i}:i=0,1,\dots,f-1\\}.$

27 end if

28

29 end for

Algorithm 1 Proposed Aspis aggregation algorithm to alleviate Byzantine
effects.

The details of this procedure are described in Algorithm 1. In both cases, we
ensure that there are no floating point precision issues in our
implementation, i.e., all honest workers assigned to $B_{t,i}$ will return the
exact same gradient. In general, even if such issues arise they can easily be
handled. In Case 1, if the honest gradients for a file were different the PS
could average them. In Case 2, we could cluster the gradients and compute the
average of the largest cluster.

Metrics: We are interested in two main metrics, the fraction of distorted
files and the top-1 test accuracy of the final trained model. We evaluate
these metrics for the various competing methods.

Input: Batch size $b$, computation load $l$, redundancy $r$ and worker set
$\mathcal{U}$, $|\mathcal{U}|=K$.

1 PS partitions batch $B_{t}$ into $f=\binom{K}{r}$ disjoint files of $b/f$
samples each  $B_{t}=\left\\{B_{t,i}:i=0,1,\dots,f-1\right\\}.$

2 PS constructs all subsets $S_{0},S_{1},\dots,S_{\binom{K}{r}-1}$ of
$\mathcal{U}=\\{U_{1},U_{2},\dots,U_{K}\\}$ such that $\forall i,|S_{i}|=r$.

3 for  _$i=0$ to $f-1$_ do

4 PS identifies all workers in group
$S_{i}=\\{U_{j_{1}},U_{j_{2}},\dots,U_{j_{r}}\\}$ and assigns the file indexed
with $i$ in $B_{t}$ to all of them. Formally,
$\mathcal{N}(U_{j})=\mathcal{N}(U_{j})\cup\\{B_{t,i}\\}$ for
$j\in\\{j_{1},j_{2},\dots,j_{r}\\}$.

5 end for

Algorithm 2 Aspis subset-based file assignment.

##  3 Task Assignment

In this section, we propose our technique which determines the allocation of
gradient tasks to workers in Aspis. Let $\mathcal{U}$ be the set of workers.
Our scheme has $|\mathcal{U}|\leq f$ (i.e., fewer workers than files).

To allocate the batch of an iteration, $B_{t}$, to the $K$ workers, first, we
will partition $B_{t}$ into $f=\binom{K}{r}$ disjoint files
$B_{t,0},B_{t,1},\dots,B_{t,f-1}$; recall that $r$ is the redundancy.
Following this, we associate each file with exactly one of the subsets
$S_{0},S_{1},\dots,S_{\binom{K}{r}-1}$ of $\\{U_{1},U_{2},\dots,U_{K}\\}$ each
of cardinality $r$, essentially using a bijection. Each file contains $b/f$
samples. The details are specified in Algorithm 2. The following example
showcases the proposed protocol of Algorithm 2.

######  Example 1.

Consider $K=7$ workers $U_{1},U_{2}\dots,U_{7}$ and $r=3$. Based on our
protocol, the $f=\binom{7}{3}=35$ files of each batch $B_{t}$ are associated
one-to-one with 3-subsets of $\mathcal{U}$, e.g., the subset
$S_{0}=\\{U_{1},U_{2},U_{3}\\}$ corresponds to file $B_{t,0}$ and will be
processed by $U_{1}$, $U_{2}$ and $U_{3}$.

######  Remark 1.

Our task assignment ensures that every pair of workers processes
$\binom{K-2}{r-2}$ files. Moreover, the number of adversaries is $q<K/2$.
Thus, upon receiving the gradients from the workers, the PS can examine them
for consistency and flag certain nodes as adversarial if their computed
gradients differ from $q+1$ or more of the other nodes. We use this intuition
to detect and mitigate the adversarial effects and to compute the fraction of
corrupted files.

##  4 Adversarial Detection

The PS will run our detection method in every iteration as our model assumes
that the adversaries can be different across different steps. The following
analysis applies to any iteration; thus, the iteration index $t$ will be
omitted from most of the notation used in this section. Let the current set of
adversaries be $A\subset\\{U_{1},U_{2},\dots,U_{K}\\}$ with $|A|=q$; also, let
$H$ be the honest worker set. The set $A$ is unknown but our goal is to
provide an estimate $\hat{A}$ of it. Ideally, the two sets should be
identical. In general, depending on the adversarial behavior, we will be able
provide a set $\hat{A}$ such that $\hat{A}\subseteq A$. For each file, there
is a group of $r$ workers which have processed it and there are ${r\choose 2}$
pairs of workers in each group. Each such pair may or may not agree on the
gradient value for the file. For an iteration, let us encode the agreement of
workers $U_{j_{1}},U_{j_{2}}$ on a common file $i$ of them as

$\alpha_{i}^{(j_{1},j_{2})}:=\left\\{\begin{array}[]{ll}1&\text{if
}\hat{\mathbf{g}}_{i}^{(j_{1})}=\hat{\mathbf{g}}_{i}^{(j_{2})},\\\
0&\text{otherwise},\end{array}\right.$ (4)

where the iteration subscript $t$ is skipped for the computed gradients. Then,
across all files, let us denote the total number of agreements between a pair
of workers $U_{j_{1}},U_{j_{2}}$ by

$\alpha^{(j_{1},j_{2})}:=\sum_{i\in\mathcal{N}(U_{j_{1}})\cap\mathcal{N}(U_{j_{2}})}\alpha_{i}^{(j_{1},j_{2})}.$
(5)

Since the placement is known, the PS can always perform the above computation.
Next, we form an undirected graph $\mathbf{G}$ whose vertices correspond to
all workers $\\{U_{1},U_{2},\dots,U_{K}\\}$. An edge $(U_{j_{1}},U_{j_{2}})$
exists in $\mathbf{G}$ only if the computed gradients of $U_{j_{1}}$ and
$U_{j_{2}}$ match in all their ${{K-2}\choose{r-2}}$ common groups.

A _clique_ in an undirected graph is defined as a subset of vertices in which
there is an edge between any pair of them. A _maximal clique_ is one that
cannot be enlarged by adding additional vertices to it. A _maximum clique_ is
a clique such that there is no clique with more vertices in the given graph.
We note that the set of honest workers $H$ will pair-wise agree everywhere. In
particular, this implies that the subset $H$ forms a clique (of size $K-q$)
within $\mathbf{G}$. The clique containing the honest workers may not be
maximal. However, it will have a size at least $K-q$. Let the maximum clique
on $\mathbf{G}$ be $M_{\mathbf{G}}$. Any worker $U_{j}$ with
$\deg(U_{j})<K-q-1$ will not belong to a maximum clique and can straight away
be eliminated as a “detected” adversary.

Input: Computed gradients $\hat{\mathbf{g}}_{t,i}^{(j)}$, $i=0,1,\dots,f-1$,
$j=1,2,\dots,K$, redundancy $r$ and empty graph $\mathbf{G}$ with worker
vertices $\mathcal{U}$.

1 for  _each pair $(U_{j_{1}},U_{j_{2}}),j_{1}\neq j_{2}$ of workers_ do

2 PS computes the number of agreements $\alpha^{(j_{1},j_{2})}$ of the pair
$U_{j_{1}},U_{j_{2}}$ on the gradient value.

3 if  _$\alpha^{(j_{1},j_{2})}={{K-2}\choose{r-2}}$_ then

4 Connect vertex $U_{j_{1}}$ to vertex $U_{j_{2}}$ in $\mathbf{G}$.

5 end if

6

7 end for

8

9PS enumerates all $k$ maximum cliques
$M_{\mathbf{G}}^{(1)},M_{\mathbf{G}}^{(2)},\dots,M_{\mathbf{G}}^{(k)}$ in
$\mathbf{G}$.

10if  _there is a unique maximum clique $M_{\mathbf{G}}$ ($k=1$)_ then

11 PS determines the honest workers $H=M_{\mathbf{G}}$ and the adversarial
machines $\hat{A}=\mathcal{U}-M_{\mathbf{G}}$.

12else

13 PS declares unsuccessful detection.

14 end if

Algorithm 3 Proposed Aspis graph-based detection.

The essential idea of our detection is to run a clique-finding algorithm on
$\mathbf{G}$ (summarized in Algorithm 3). If we find a unique maximum clique,
we declare it to be the set of honest workers; the gradients from the detected
adversaries are ignored. On the other hand, if there is more than one maximum
clique, we resort to the robust aggregation technique discussed in Section 2.
Let us denote the number of distorted tasks upon Aspis detection and
aggregation by $c^{(q)}$ and its maximum value (under the worst-case attack)
by $c_{\mathrm{max}}^{(q)}$. The _distortion fraction_ is
$\epsilon:=c^{(q)}/f$. Clique-finding is well-known to be an NP-complete
problem Karp (1972). Nevertheless, there are fast practical algorithms that
have excellent performance on graphs even up to hundreds of nodes Cazals &
Karande (2008); Etsuji et al. (2006). Specifically, the authors of Etsuji et
al. (2006) have shown that their proposed algorithm which enumerates all
maximal cliques has similar complexity as other methods Robson (1986); Tarjan
& Trojanowski (1977) which are used to find a single maximum clique. We
utilize this algorithm which is proven to be optimal. Our extensive
experimental evidence suggests that clique-finding is not a computation
bottleneck for the size and structure of the graphs that Aspis uses. We have
experimented with clique-finding on a graph of $K=100$ workers and $r=5$ for
different values of $q$; in all cases, enumerating all maximal cliques took no
more than 15 milliseconds. These experiments and asymptotic complexity of
entire protocol are addressed in Appendix Section A.1.

(a) Unique max-clique, detection succeeds.

(b) Two max-cliques, detection fails.

Figure 2: Detection graph $\mathbf{G}$ for $K=7$ workers among which $U_{1}$,
$U_{2}$ and $U_{3}$ are the adversaries.

###  4.1 Weak Adversarial Strategy

We first consider a class of weak attacks where the Byzantine nodes attempt to
distort the gradient on any file that they participate in. For instance, a
node may try to return arbitrary gradients on all its files. A more
sophisticated strategy (but still weak) for the node would be to match the
result with other adversarial nodes that process the same file. In both cases,
it is clear that the Byzantine node will disagree with at least $K-q$ honest
nodes and thus the degree of the node in $\mathbf{G}$ will be at most
$q-1<K-q-1$ and it will not be part of the maximum clique. Thus, each of the
adversaries will be detected and their returned gradients will not be
considered further. The algorithm declares the (unique) maximum clique as
honest and proceeds to aggregation (_cf._ Section 2). The only files that can
be distorted in this case are those that consist exclusively of adversarial
nodes.

Figure 2(a) (corresponding to Example 1) shows an example where in a cluster
of size $K=7$, the $q=3$ adversaries are $A=\\{U_{1},U_{2},U_{3}\\}$ and the
remaining workers are honest with $H=\\{U_{4},U_{5},U_{6},U_{7}\\}$. In this
case, the unique maximum clique is $M_{\mathbf{G}}=H$ and detection is
successful. Under this attack, the number of distorted tasks are those whose
all copies have been compromised, i.e., $c^{(q)}=\binom{q}{r}$.

######  Remark 2.

We emphasize that even though we call this attack “weak” this is the attack
model considered in several prior works Rajput et al. (2019); Chen et al.
(2018). To our best knowledge, most of them have not considered the
adversarial problem from the lens of detection.

(a) Optimal attacks.

(b) Weak attacks.

Figure 3: Distortion fraction of optimal and weak attacks for $(K,r)=(50,3)$
and comparison.

###  4.2 Optimal Adversarial Strategy

Our second scenario is strong and involves adversaries which collude in the
“best” way possible while knowing the full details of our detection algorithm.
In this discussion, we provide an upper bound on the number of files that can
be corrupted in this case and demonstrate a strategy that the adversarial
workers can follow to achieve this upper bound.

Let us index the $q$ adversaries in $A=\\{A_{1},A_{2},\dots,A_{q}\\}$ and the
honest workers in $H$. We say that two workers $U_{j_{1}}$ and $U_{j_{2}}$
disagree if there is no edge between them in $\mathbf{G}$. The non-existence
of an edge between $U_{j_{1}}$ and $U_{j_{2}}$ only means that they disagree
in _at least one_ of the $\binom{K-2}{r-2}$ files that they jointly
participate in. For corrupting the gradients, each adversary has to disagree
on the computations with a subset of the honest workers. An adversary may also
disagree with other adversaries. Let $D_{i}$ denote the set of disagreement
workers for adversary $A_{i},i=1,2,\dots,q$, where $D_{i}$ can contain members
from $A$ and from $H$.

Upon formation of $\mathbf{G}$ we know that a worker $U_{j}$ will be flagged
as adversarial if $deg(U_{j})<K-q-1$. Therefore to avoid detection, a
_necessary_ condition is that $|D_{j}|\leq q$. We now upper bound the number
of files that can be corrupted under any possible strategy employed by the
adversaries. We fall back to robust aggregation in case of more than one
maximum clique in $\mathbf{G}$. Then, a gradient can only be corrupted if a
majority of the workers computing it are adversarial and agree on a wrong
value.

For a given file $F$, let $A^{\prime}\subseteq A$ with $|A^{\prime}|\geq
r^{\prime}$ be the set of “active adversaries” in it, i.e.,
$A^{\prime}\subseteq F$ consists of Byzantines that collude to create a
majority that distorts the gradient on it. In this case, the remaining workers
in $F$ belong to $\cap_{i\in A^{\prime}}D_{i}$, where we note that
$|\cap_{i\in A^{\prime}}D_{i}|\leq q$. Let
$X_{j},j=r^{\prime},r^{\prime}+1\dots,r$ denote the subset of files where the
set of active adversaries is of size $j$; note that $X_{j}$ depends on the
disagreement sets $D_{i},i=1,2,\dots,q$. Formally,

$\displaystyle X_{j}$ $\displaystyle=$ $\displaystyle\\{F:\exists
A^{\prime}\subseteq A\cap F,|A^{\prime}|=j,$ (6)
$\displaystyle\qquad\text{~{}and~{}}\forall~{}U_{j}\in F\setminus
A^{\prime},U_{j}\in\cap_{i\in A^{\prime}}D_{i}\\}.\quad$

Then, for a given choice of disagreement sets, the number of files that can be
corrupted is given by $|\cup_{j=r^{\prime}}^{r}X_{j}|$. We obtain an upper
bound on the maximum number of corrupted files by maximizing this quantity
with respect to the choice of $D_{i},i=1,2,\dots,q$, i.e.,

$c_{\mathrm{max}}^{(q)}=\max\limits_{D_{i},|D_{i}|\leq
q,i=1,2,\dots,q}|\cup_{j=r^{\prime}}^{r}X_{j}|$ (7)

where the maximization is over the choices of the disagreement sets
$D_{1},D_{2},\dots,D_{q}$. An intuitive adversarial strategy based on Eq. (6)
would be to maximize the set $\bigcap\limits_{i\in A^{\prime}\cap F}D_{i}$ for
every possible file $F$. In order to achieve this, for all groups $F$, the
adversaries will need to fix a subset of $q$ non-adversaries, say $D\subset
H$, which will be the set of workers with which all adversaries will disagree,
i.e., $D_{i}=D$ for $i=1,2,\dots,q$. We present the following theorem (see
Appendix Section A.2 for proof).

######  Theorem 1.

Consider a training cluster of $K$ workers with $q$ adversaries using
Algorithm 2 to assign the $f=\binom{K}{r}$ files to workers and Algorithm 3
for adversary detection. Under an optimal adversary model the maximum number
of files that can be corrupted is

$c_{\mathrm{max}}^{(q)}=\frac{1}{2}{2q\choose r}.$ (8)

Furthermore, if all adversaries fix a set $D\subset H$ of honest workers with
which they will consistently disagree on the gradient (by distorting it), this
upper bound can be achieved.

In particular, the proposed attack is optimal and there is no other attack
that can corrupt more files under the Aspis algorithm. One such attack is
carried out in Figure 2(b) for the setup of Example 1. The adversaries
$A=\\{U_{1},U_{2},U_{3}\\}$ consistently disagree with the workers in
$D=\\{U_{4},U_{5},U_{6}\\}\subset H$. The ambiguity as to which of the two
maximum cliques ($\\{U_{1},U_{2},U_{3},U_{7}\\}$ or
$\\{U_{4},U_{5},U_{6},U_{7}\\}$) is the honest one makes an accurate detection
impossible; robust aggregation will be performed instead.

##  5 Distortion Fraction Evaluation

We have performed simulations of the fraction of distorted files (defined as
$\epsilon=c^{(q)}/f$) incurred by Aspis and other competing aggregators. The
main motivation of this analysis is that our deep learning experiments (_cf._
Section 6.2) as well as prior work Konstantinidis & Ramamoorthy (2021) show
that $\epsilon$ serves as a surrogate of the model’s convergence with respect
to accuracy. In addition, our simulations show that Aspis enjoys values of
$\epsilon$ which are as much as 99% lower for the same $q$ compared to other
techniques and this attests to our theoretical robustness guarantees. This
comparison involves our work and state-of-the-art schemes under the best- and
worst-case choice of the $q$ adversaries with respect to the achievable value
of $\epsilon$. We compare our work with _baseline_ approaches which do not
involve redundancy or majority voting. Their aggregation is applied directly
to the $K$ gradients returned by the workers ($f=K$,
$c_{\mathrm{max}}^{(q)}=q$ and $\epsilon=q/K$).

Let us first discuss the scenario of an _optimal_ attack. For Aspis, we used
the proposed attack from Section 4.2 and the corresponding computation of
$c^{(q),Aspis}$ of Theorem 1. _DETOX_ in Rajput et al. (2019) employs a
redundant assignment followed by majority voting and offers robustness
guarantees which crucially rely on a “random choice” of the Byzantines.
Konstantinidis & Ramamoorthy (2021) have demonstrated the importance of a
careful task assignment and observed that redundancy is not sufficient to
yield Byzantine resilience dividends. They proposed an optimal choice of the
$q$ Byzantines that maximizes $\epsilon^{DETOX}$ which we used in our
experiments. In short, DETOX splits the $K$ workers into $K/r$ groups. All
workers within a group process the same subset of the batch, specifically
containing $br/K$ samples. This phase is followed by majority voting on a
group-by-group basis. The authors of Konstantinidis & Ramamoorthy (2021)
suggested choosing the Byzantines such that at least $r^{\prime}$ workers in
each group are adversarial in order to distort the corresponding gradients. In
this case, $c^{(q),DETOX}=\lfloor\frac{q}{r^{\prime}}\rfloor$ and
$\epsilon^{DETOX}=\lfloor\frac{q}{r^{\prime}}\rfloor\times r/K$. We also
compare with the distortion fraction incurred by ByzShield Konstantinidis &
Ramamoorthy (2021) under a worst-case scenario. For this scheme, there is no
known optimal attack and its authors performed an exhaustive combinatorial
search to find the $q$ adversaries that maximize $\epsilon^{ByzShield}$ among
all possible options; we follow the same process here to simulate ByzShield’s
distortion fraction computation and utilize their scheme based on _mutually
orthogonal Latin squares_. The reader can refer to Figure 3(a) and Appendix
Tables 1, 2 and 3 for our results. Aspis achieves major reductions in
$\epsilon$; for instance, $\epsilon^{Aspis}$ is reduced by up to 99% compared
to both $\epsilon^{Baseline}$ and $\epsilon^{DETOX}$ in Figure 3(a).

We will next introduce the utilized _weak_ attacks. For our scheme, we will
make an arbitrary choice of $q$ adversaries which carry out the method
introduced in Section 4.1, i.e., they will distort all files and a successful
detection is possible. As discussed, the fraction of corrupted gradients is
$\epsilon^{Aspis}=\binom{q}{r}/\binom{K}{r}$ in that case. For DETOX, a simple
benign attack is used. To that end, let the $K/r$ files be
$B_{t,0},B_{t,1},\dots,B_{t,K/r-1}$. Initialize $A=\emptyset$ and choose the
$q$ Byzantines as follows: for $i=0,1,\dots,q-1$, among the remaining workers
in $\\{U_{1},U_{2},\dots,U_{K}\\}-A$ add a worker from the group $B_{t,i\mod
K/r}$ to the adversarial set $A$. Then,

$c^{(q),DETOX}=\left\\{\begin{array}[]{ll}q-\frac{K}{r}(r^{\prime}-1)&\text{if
}q>\frac{K}{r}(r^{\prime}-1),\\\ 0&\text{otherwise}.\end{array}\right.$

The results on this scenario are in Figure 3(b).

For baseline schemes, there is no notion of “weak” or “optimal” attack with
respect to the choice of the $q$ Byzantines; hence we can choose any subset of
them achieving $\epsilon^{Baseline}=q/K$.

(a) Median-based defenses.

(b) _Bulyan_ -based defenses.

(c) _Multi-Krum_ -based defenses.

Figure 4: _ALIE_ distortion under optimal attack scenarios (CIFAR-10), $K=15$.

(a) Median-based defenses.

(b) _Bulyan_ -based defenses.

(c) _Multi-Krum_ -based defenses.

Figure 5: _Reversed gradient_ distortion under optimal attack scenarios
(CIFAR-10), $K=15$.

##  6 Large-scale Deep Learning Experiments

###  6.1 Experiment Setup

We have evaluated the performance of our method and competing techniques in
classification tasks on Amazon EC2 clusters. The project is written in PyTorch
Paszke et al. (2019) and uses the MPICH library for communication between the
different nodes. We worked with the CIFAR-10 dataset Krizhevsky (2009) using
the ResNet-18 He et al. (2016) model. We used clusters of $K=15$ and $21$
workers and redundancy $r=3$. We simulated values of $q=2,4,6$ during
training. Detailed information about the implementation can be found in
Appendix Section A.3.

There are two different dimensions we experimentally evaluate with respect to
the adversarial setup:
1) Choice/orchestration of the adversaries: This involves the different ways
in which adversaries are chosen and can work together to inflict damage (_cf._
weak and optimal attacks in Section 4).
2) Gradient distortion methods: This dimension is concerned with the method an
adversary uses to distort the gradient value (_cf._ Algorithm 1). We use a
variety of state-of-the-art methods for distorting the computed gradients.
_ALIE_ Baruch et al. (2019) involves communication among the Byzantines in
which they jointly estimate the mean $\mu_{i}$ and standard deviation
$\sigma_{i}$ of the batch’s gradient for each dimension $i$ and subsequently
use them to construct a distorted gradient that attempts to distort the median
of the results. Another powerful attack is _Fall of Empires (FoE)_ Xie et al.
(2019a) which performs “inner product manipulation” to make the inner product
between the true gradient and the robust estimator to be negative even when
their distance is upper bounded by a small value. _Reversed gradient_
distortion returns $-c\boldsymbol{\mathbf{g}}$ for $c>0$, to the PS instead of
the true gradient $\boldsymbol{\mathbf{g}}$. The ALIE algorithms is, to the
best of our knowledge, the most sophisticated attack in literature.

Competing methods: We compare Aspis against the baseline implementations of
median-of-means Minsker (2015), Bulyan El Mhamdi et al. (2018) and Multi-Krum
Blanchard et al. (2017). If $c_{\mathrm{max}}^{(q)}$ is the number of
adversarial computations then Bulyan requires at least
$4c_{\mathrm{max}}^{(q)}+3$ total number of computations while the same number
for Multi-Krum is $2c_{\mathrm{max}}^{(q)}+3$. These constraints make these
methods inapplicable for larger values of $q$ for which our method is robust.
The second class of comparisons is with methods that use redundancy and
specifically DETOX Rajput et al. (2019) for which we show that it can easily
fail under malicious scenarios for large $q$. We compare with median-based
techniques since they originate from robust statistics and are the base for
many aggregators. DETOX is the most related redundancy-based work that is
based on coding-theoretic techniques. Finally, Multi-Krum is a highly-cited
aggregator that combines the intuitions of majority-based and squared-
distance-based methods.

Note that for a baseline scheme all choices of $A$ are equivalent in terms of
the value of $\epsilon$. In our comparisons with DETOX we will consider two
attack scenarios with respect to the choice of the adversaries. For the
_optimal_ choice in DETOX, we will use the method proposed in Konstantinidis &
Ramamoorthy (2021) and compare with the attack introduced in Section 4.2. For
the _weak_ one, we will choose the adversaries such that $\epsilon$ is
minimized in DETOX and compare its performance with the scenario of Section
4.1.

Figure 6: _FoE_ optimal attack and median-based defenses (CIFAR-10), $K=15$

Figure 7: _Reversed gradient_ weak attack and median-based defenses
(CIFAR-10), $K=15$.

Figure 8: _ALIE_ weak attack and median-based defenses (CIFAR-10), $K=15$.

(a) Median-based defenses.

(b) _Bulyan_ -based defenses.

(c) _Multi-Krum_ -based defenses.

Figure 9: _ALIE_ distortion under optimal attack scenarios (CIFAR-10), $K=21$.

###  6.2 Experimental Results

####  6.2.1 Comparison under Optimal Attacks

We compare the different defense algorithms under optimal attack scenarios.
Figure 4(a) compares our scheme Aspis with the baseline implementation of
coordinate-wise median ($\epsilon=0.133,0.267$ for $q=2,4$, respectively) and
DETOX with median-of-means ($\epsilon=0.2,0.4$ for $q=2,4$, respectively)
under the ALIE attack. Aspis converges faster and achieves at least a 35%
average accuracy boost (at the end of the training) for both values of $q$
($\epsilon^{Aspis}=0.004,0.062$ for $q=2,4$, respectively).333Please refer to
Appendix Tables 1 and 2 for the values of the distortion fraction $\epsilon$
each scheme incurs. In Figures 4(b) and 4(c) we observe similar trends in our
experiments with Bulyan and Multi-Krum where Aspis significantly outperforms
these techniques. For the current setup, Bulyan is not applicable for $q=4$
since $K=15<4c_{\mathrm{max}}^{(q)}+3=4q+3=19$. Also, neither Bulyan nor
Multi-Krum can be paired with DETOX for $q\geq 1$ since the inequalities
$f\geq 4c_{\mathrm{max}}^{(q)}+3$ and $f\geq 2c_{\mathrm{max}}^{(q)}+3$ cannot
be satisfied. Please refer to Section 6.1 and Section 5 for more details on
these requirements. Also, note that the accuracy of most competing methods
fluctuates more than in the results presented in the corresponding papers
Rajput et al. (2019) and Baruch et al. (2019). This is expected as we consider
stronger attacks compared to those papers, i.e., optimal deterministic attack
on DETOX and, in general, up to 27% adversarial workers in the cluster. Also,
we have done multiple experiments with different random seeds to demonstrate
the stability and superiority of our accuracy results compared to other
methods (against median-based defenses in Appendix Figure 10, Bulyan in Figure
11 and Multi-Krum in Figure 12); we point the reader to Appendix Section A.3.3
for this analysis. This analysis is clearly missing from most prior work,
including that of ALIE Baruch et al. (2019), and their presented results are
only a snapshot of a single experiment which may or may not be reproducible as
is. The results for the reversed gradient attack are shown in Figures 5(a),
5(b) and 5(c). Given that this is a much weaker attack Konstantinidis &
Ramamoorthy (2021); Rajput et al. (2019) all of the schemes considered,
including the baseline methods, are expected to perform well; indeed in most
of the cases, the model converges to approximately 80% accuracy. However,
DETOX fails to converge to high accuracy for $q=4$ as in the case of ALIE; one
explanation is that $\epsilon^{DETOX}=0.4$ for $q=4$. Under the Fall of
Empires (FoE) distortion (_cf._ Figure 8) our method still enjoys an accuracy
advantage over the baseline and DETOX schemes which becomes more important as
the number of Byzantines in the cluster increases.

####  6.2.2 Comparison under Weak Attacks

For baseline schemes, the discussion of weak versus optimal choice of the
adversaries is not very relevant as any choice of the $q$ Byzantines can
overall distort at most $q$ out of the $K$ gradients. Hence, for weak
scenarios, we chose to compare mostly with DETOX. The accuracy is reported on
Figures 8 and 8 according to which Aspis shows an improvement under attacks on
the more challenging end of the spectrum (ALIE). According to Appendix Table
11(b), Aspis enjoys a fraction $\epsilon^{Aspis}=0.044$ while
$\epsilon^{Baseline}=0.4$ and $\epsilon^{DETOX}=0.2$ for $q=6$.

Our experiments on a larger cluster of $K=21$ workers under the ALIE attack
can be found in Figure 9.

##  7 Conclusions and Future Work

In this work we have presented Aspis, a Byzantine-resilient distributed scheme
that uses redundancy and robust aggregation in novel ways to detect
adversarial behavior by the workers. Our theoretical analysis and numerical
experiments clearly indicate the superior performance of Aspis compared to
state-of-the-art. Our experiments show that Aspis requires increased
computation and communication time as compared to prior work, e.g., note that
each worker has to transmit $l$ gradients instead of $1$ in related work
Rajput et al. (2019); Chen et al. (2018) (see Appendix Section A.3.4 for
details). We emphasize however, that under strong attacks (optimal Byzantine
behavior) Aspis converges to high accuracy while competing methods will never
converge irrespective of how long the algorithm runs for (please refer to
Figures 4, 5(a) and 8); for a strong distortion attack like ALIE, this is
evident even under weak adversarial strategies with respect to the Byzantine
node behavior (cf. Figure 8).

Our experiments involve clusters of up to $21$ workers. As we scale our
solution to more workers, the total number of files and the computation load
$l$ of each worker will also scale; this increases the memory needed to store
the gradients during aggregation. For complex neural networks, the memory to
store the model and the intermediate gradient computations is by far the most
memory-consuming aspect of the algorithm. For these reasons, our scheme is
mostly suitable to training large datasets using fairly compact models that do
not require too much memory. Also, there are opportunities for reducing the
time overhead. For instance, utilizing GPUs and communication-related
algorithmic improvements are worth exploring. Finally, convergence analysis is
under investigation and space limitations do not allow us to discuss it here.

## References

  * Alistarh et al. (2018) Alistarh, D., Allen-Zhu, Z., and Li, J.  Byzantine stochastic gradient descent.  In _Advances in Neural Information Processing Systems_ , December 2018\.
  * Baruch et al. (2019) Baruch, G., Baruch, M., and Goldberg, Y.  A Little Is Enough: Circumventing defenses for distributed learning.  In _Advances in Neural Information Processing Systems_ , pp. 8635–8645, December 2019.
  * Bernstein et al. (2019) Bernstein, J., Zhao, J., Azizzadenesheli, K., and Anandkumar, A.  signSGD with majority vote is communication efficient and fault tolerant.  _arXiv_ , 2019.  1810.05291.
  * Blanchard et al. (2017) Blanchard, P., El Mhamdi, E. M., Guerraoui, R., and Stainer, J.  Machine learning with adversaries: Byzantine tolerant gradient descent.  In _Advances in Neural Information Processing Systems_ , pp. 119–129, December 2017.
  * Boyer & Moore (1991) Boyer, R. S. and Moore, J. S.  _MJRTY—A Fast Majority Vote Algorithm_.  Springer Netherlands, Dordrecht, 1991.
  * Cazals & Karande (2008) Cazals, F. and Karande, C.  A note on the problem of reporting maximal cliques.  _Theoretical Computer Science_ , 407(1):564–568, November 2008.
  * Chen et al. (2018) Chen, L., Wang, H., Charles, Z., and Papailiopoulos, D.  DRACO: Byzantine-resilient distributed training via redundant gradients.  In _Proceedings of the 35th International Conference on Machine Learning_ , pp. 903–912, July 2018.
  * Chen et al. (2015) Chen, T., Li, M., Li, Y., Lin, M., Wang, N., Wang, M., Xiao, T., Xu, B., Zhang, C., and Zhang, Z.  MXNet: A flexible and efficient machine learning library for heterogeneous distributed systems.  _arXiv_ , 2015.  1512.01274.
  * Chen et al. (2017) Chen, Y., Su, L., and Xu, J.  Distributed statistical machine learning in adversarial settings: Byzantine gradient descent.  _Proc. ACM Meas. Anal. Comput. Syst._ , 1(2), December 2017\.
  * Damaskinos et al. (2019) Damaskinos, G., El Mhamdi, E. M., Guerraoui, R., Guirguis, A. H. A., and Rouault, S. L. A.  Aggregathor: Byzantine machine learning via robust gradient aggregation.  In _Conference on Systems and Machine Learning (SysML) 2019_ , pp. 19, March 2019.
  * Data et al. (2018) Data, D., Song, L., and Diggavi, S.  Data encoding for Byzantine-resilient distributed gradient descent.  In _2018 56th Annual Allerton Conference on Communication, Control, and Computing (Allerton)_ , pp. 863–870, October 2018.
  * El Mhamdi et al. (2018) El Mhamdi, E. M., Guerraoui, R., and Rouault, S.  The hidden vulnerability of distributed learning in Byzantium.  In _Proceedings of the 35th International Conference on Machine Learning_ , pp. 3521–3530, July 2018.
  * Etsuji et al. (2006) Etsuji, T., Akira, T., and Haruhisa, T.  The worst-case time complexity for generating all maximal cliques and computational experiments.  _Theoretical Computer Science_ , 363(1):28–42, October 2006.
  * Gupta & Vaidya (2019) Gupta, N. and Vaidya, N. H.  Byzantine fault-tolerant parallelized stochastic gradient descent for linear regression.  In _2019 57th Annual Allerton Conference on Communication, Control, and Computing (Allerton)_ , pp. 415–420, September 2019.
  * Hagberg et al. (2008) Hagberg, A. A., Schult, D. A., and Swart, P. J.  Exploring network structure, dynamics, and function using networkx.  In _Proceedings of the 7th Python in Science Conference_ , pp. 11–15, August 2008.
  * He et al. (2016) He, K., Zhang, X., Ren, S., and Sun, J.  Deep residual learning for image recognition.  In _IEEE Conference on Computer Vision and Pattern Recognition (CVPR)_ , pp. 770–778, June 2016.
  * Karp (1972) Karp, R. M.  _Reducibility among Combinatorial Problems_.  Springer US, Boston, MA, 1972.
  * Kim et al. (2014) Kim, Y., Daly, R., Kim, J., Fallin, C., Lee, J. H., Lee, D., Wilkerson, C., Lai, K., and Mutlu, O.  Flipping bits in memory without accessing them: An experimental study of dram disturbance errors.  In _Proceeding of the 41st Annual International Symposium on Computer Architecuture_ , pp. 361––372, June 2014.
  * Konstantinidis & Ramamoorthy (2021) Konstantinidis, K. and Ramamoorthy, A.  ByzShield: An efficient and robust system for distributed training.  In _Machine Learning and Systems 3 (MLSys 2021)_ , April 2021.
  * Krizhevsky (2009) Krizhevsky, A.  Learning multiple layers of features from tiny images.  2009\.
  * Minsker (2015) Minsker, S.  Geometric median and robust estimation in Banach spaces.  _Bernoulli_ , 21(4):2308–2335, November 2015\.
  * Paszke et al. (2019) Paszke, A., Gross, S., Massa, F., Lerer, A., Bradbury, J., Chanan, G., Killeen, T., Lin, Z., Gimelshein, N., Antiga, L., Desmaison, A., Kopf, A., Yang, E., DeVito, Z., Raison, M., Tejani, A., Chilamkurthy, S., Steiner, B., Fang, L., Bai, J., and Chintala, S.  PyTorch: An imperative style, high-performance deep learning library.  In _Advances in Neural Information Processing Systems_ , pp. 8024–8035, December 2019.
  * Rajput et al. (2019) Rajput, S., Wang, H., Charles, Z., and Papailiopoulos, D.  DETOX: A redundancy-based framework for faster and more robust gradient aggregation.  In _Advances in Neural Information Processing Systems_ , pp. 10320–10330, December 2019.
  * Rakin et al. (2019) Rakin, A. S., He, Z., and Fan, D.  Bit-flip attack: Crushing neural network with progressive bit search.  In _2019 IEEE/CVF International Conference on Computer Vision (ICCV)_ , pp. 1211–1220, October 2019.
  * Raviv et al. (2018) Raviv, N., Tandon, R., Dimakis, A., and Tamo, I.  Gradient coding from cyclic MDS codes and expander graphs.  In _Proceedings of the 35th International Conference on Machine Learning_ , pp. 4302–4310, July 2018.
  * Regatti et al. (2020) Regatti, J., Chen, H., and Gupta, A.  ByGARS: Byzantine sgd with arbitrary number of attackers.  _arXiv_ , 2020.  2006.13421.
  * Robson (1986) Robson, J.  Algorithms for maximum independent sets.  _Journal of Algorithms_ , 7(3):425–440, September 1986.
  * Seide & Agarwal (2016) Seide, F. and Agarwal, A.  CNTK: Microsoft’s open-source deep-learning toolkit.  In _Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining_ , pp. 2135, August 2016.
  * Shen et al. (2016) Shen, S., Tople, S., and Saxena, P.  Auror: Defending against poisoning attacks in collaborative deep learning systems.  In _Proceedings of the 32nd Annual Conference on Computer Security Applications_ , pp. 508––519, December 2016.
  * Tandon et al. (2017) Tandon, R., Lei, Q., Dimakis, A. G., and Karampatziakis, N.  Gradient coding: Avoiding stragglers in distributed learning.  In _Proceedings of the 34th International Conference on Machine Learning_ , pp. 3368–3376, August 2017.
  * Tarjan & Trojanowski (1977) Tarjan, R. E. and Trojanowski, A. E.  Finding a maximum independent set.  _SIAM Journal on Computing_ , 6(3):537–546, 1977\.
  * Van Lint & Wilson (2001) Van Lint, J. H. and Wilson, R. M.  _A Course in Combinatorics_.  Cambridge University Press, New York, 2001.
  * Xie et al. (2018) Xie, C., Koyejo, O., and Gupta, I.  Generalized Byzantine-tolerant SGD.  _arXiv_ , 2018.  1802.10116.
  * Xie et al. (2019a) Xie, C., Koyejo, O., and Gupta, I.  Fall of Empires: Breaking byzantine-tolerant sgd by inner product manipulation.  In _35th Conference on Uncertainty in Artificial Intelligence, UAI 2019_ , pp. 6893–6901, July 2019a.
  * Xie et al. (2019b) Xie, C., Koyejo, S., and Gupta, I.  Zeno: Distributed stochastic gradient descent with suspicion-based fault-tolerance.  In _Proceedings of the 36th International Conference on Machine Learning_ , pp. 6893–6901, June 2019b.
  * Yin et al. (2018) Yin, D., Chen, Y., Kannan, R., and Bartlett, P.  Byzantine-robust distributed learning: Towards optimal statistical rates.  In _Proceedings of the 35th International Conference on Machine Learning_ , pp. 5650–5659, July 2018.
  * Yin et al. (2019) Yin, D., Chen, Y., Ramchandran, K., and Bartlett, P. L.  Defending against saddle point attack in Byzantine-robust distributed learning.  In _Proceedings of the 36th International Conference on Machine Learning_ , pp. 7074–7084, June 2019.
  * Yu et al. (2019) Yu, Q., Li, S., Raviv, N., Kalan, S. M. M., Soltanolkotabi, M., and Avestimehr, S.  Lagrange coded computing: Optimal design for resiliency, security and privacy.  _arXiv_ , 2019.  1806.00939.

##  Appendix A Appendix

###  A.1 Asymptotic Complexity

If the gradient computation has linear complexity (assuming $\mathcal{O}(1)$
cost for the gradient computation with respect to one model parameter) and
since each worker is assigned to $l$ files of $b/f$ samples each, the gradient
computation cost at the worker level is $\mathcal{O}((lb/f)d)$ ($K$ such
computations in parallel). In our schemes, however, $b$ is a constant multiple
of $f$ and in general $r<l=\binom{K-1}{r-1}$; hence, the complexity becomes
$\mathcal{O}(ld)$ which is similar to other redundancy-based schemes in
Konstantinidis & Ramamoorthy (2021); Rajput et al. (2019); Chen et al. (2018).
The clique-finding problem that follows as part of our detection is NP-
complete. However, our experimental evidence suggests that for the kind of
graphs we construct this computation takes a infinitesimal fraction of the
execution time. The NetworkX package Hagberg et al. (2008) which we use for
enumerating all maximal cliques is based on the algorithm of Etsuji et al.
(2006) and has asymptotic complexity $\mathcal{O}(3^{K/3})$. We provide
extensive simulations of the clique enumeration time under the Aspis file
assignment for $K=100$ and redundancy $r=5$ (_cf._ Tables 44(a), 44(b) for
weak and optimal attack as introduced in Section 4, respectively). We
emphasize that this value of $K$ exceeds by far the typical values of $K$ of
prior work and the number of servers would suffice for the majority of
challenging training tasks. Even in this case, the cost of enumerating all
cliques is negligible. For this experiment, we used an EC2 instance of type
i3.16xlarge. The complexity of robust aggregation varies significantly
depending on the operator. For example, majority voting can be done in time
which scales linearly with the number of votes using _MJRTY_ proposed in Boyer
& Moore (1991). In our case, this is $\mathcal{O}(Kd)$ as the PS needs to use
the $d$-dimensional input from all $K$ machines. Krum Blanchard et al. (2017),
Multi-Krum Blanchard et al. (2017) and Bulyan El Mhamdi et al. (2018) are
applied to all $K$ workers by default and require
$\mathcal{O}(K^{2}(d+\mathrm{log}K))$.

Table 1: Distortion fraction of optimal and weak attacks for
$(K,f,l,r)=(15,455,91,3)$ and comparison.

$q$ | $\epsilon^{Aspis}$ | $\epsilon^{Baseline}$ | $\epsilon^{DETOX}$ | $\epsilon^{ByzShield}$
---|---|---|---|---
$2$ |  0.004 |  0.133 |  0.2 |  0.04
$3$ |  0.022 |  0.2 |  0.2 |  0.12
$4$ |  0.062 |  0.267 |  0.4 |  0.2
$5$ |  0.132 |  0.333 |  0.4 |  0.32
$6$ |  0.242 |  0.4 |  0.6 |  0.48
$7$ |  0.4 |  0.467 |  0.6 |  0.56

1(a) Optimal attacks.

$q$ | $\epsilon^{Aspis}$ | $\epsilon^{Baseline}$ | $\epsilon^{DETOX}$
---|---|---|---
$2$ |  0.002 |  0.133 |  0
$3$ |  0.002 |  0.2 |  0
$4$ |  0.009 |  0.267 |  0
$5$ |  0.022 |  0.333 |  0
$6$ |  0.044 |  0.4 |  0.2
$7$ |  0.077 |  0.467 |  0.4

1(b) Weak attacks.

Table 2: Distortion fraction of optimal and weak attacks for
$(K,f,l,r)=(21,1330,190,3)$ and comparison.

$q$ | $\epsilon^{Aspis}$ | $\epsilon^{Baseline}$ | $\epsilon^{DETOX}$ | $\epsilon^{ByzShield}$
---|---|---|---|---
$2$ |  0.002 |  0.095 |  0.143 |  0.02
$3$ |  0.008 |  0.143 |  0.143 |  0.06
$4$ |  0.021 |  0.19 |  0.286 |  0.1
$5$ |  0.045 |  0.238 |  0.286 |  0.16
$6$ |  0.083 |  0.286 |  0.429 |  0.24
$7$ |  0.137 |  0.333 |  0.429 |  0.33
$8$ |  0.211 |  0.381 |  0.571 |  0.43
$9$ |  0.307 |  0.429 |  0.571 |  0.51
$10$ |  0.429 |  0.476 |  0.714 |  0.59

2(a) Optimal attacks.

$q$ | $\epsilon^{Aspis}$ | $\epsilon^{Baseline}$ | $\epsilon^{DETOX}$
---|---|---|---
$2$ |  0.001 |  0.095 |  0
$3$ |  0.001 |  0.143 |  0
$4$ |  0.003 |  0.19 |  0
$5$ |  0.008 |  0.238 |  0
$6$ |  0.015 |  0.286 |  0
$7$ |  0.026 |  0.333 |  0
$8$ |  0.042 |  0.381 |  0.143
$9$ |  0.063 |  0.429 |  0.286
$10$ |  0.09 |  0.476 |  0.429

2(b) Weak attacks.

Table 3: Distortion fraction of optimal and weak attacks for
$(K,f,l,r)=(24,2024,253,3)$ and comparison.

$q$ | $\epsilon^{Aspis}$ | $\epsilon^{Baseline}$ | $\epsilon^{DETOX}$ | $\epsilon^{ByzShield}$
---|---|---|---|---
$2$ |  0.001 |  0.083 |  0.125 |  0.031
$3$ |  0.005 |  0.125 |  0.125 |  0.063
$4$ |  0.014 |  0.167 |  0.25 |  0.125
$5$ |  0.03 |  0.208 |  0.25 |  0.188
$6$ |  0.054 |  0.25 |  0.375 |  0.281
$7$ |  0.09 |  0.292 |  0.375 |  0.375
$8$ |  0.138 |  0.333 |  0.5 |  0.5
$9$ |  0.202 |  0.375 |  0.5 |  0.5
$10$ |  0.282 |  0.417 |  0.625 |  0.531
$11$ |  0.38 |  0.458 |  0.625 |  0.625

3(a) Optimal attacks.

$q$ | $\epsilon^{Aspis}$ | $\epsilon^{Baseline}$ | $\epsilon^{DETOX}$
---|---|---|---
$2$ |  0 |  0.083 |  0
$3$ |  0 |  0.125 |  0
$4$ |  0.002 |  0.167 |  0
$5$ |  0.005 |  0.208 |  0
$6$ |  0.01 |  0.25 |  0
$7$ |  0.017 |  0.292 |  0
$8$ |  0.028 |  0.333 |  0
$9$ |  0.042 |  0.375 |  0.125
$10$ |  0.059 |  0.417 |  0.25
$11$ |  0.082 |  0.458 |  0.375

3(b) Weak attacks.

Table 4: Clique enumeration time in Aspis graph of $K=100$ vertices and
redundancy $r=5$.

$q$ |  Time (milliseconds)
---|---
5 |  9
15 |  7
25 |  5
35 |  5
45 |  5

4(a) Adversaries carry out weak attack.

$q$ |  Time (milliseconds)
---|---
5 |  11
15 |  11
25 |  9
35 |  8
45 |  6

4(b) Adversaries carry out optimal attack.

###  A.2 Proof of Theorem 1

With $X_{j}$ given in (6), assuming $q\geq r^{\prime}$, the number of
distorted files is upper bounded by

$\displaystyle|\cup_{j=r^{\prime}}^{r}X_{j}|$
$\displaystyle\leq\sum_{j=r^{\prime}}^{r}|X_{j}|\text{~{}(by the union
bound).}$ (9)

For that, recall that $r^{\prime}=r(r+1)/2$ and that an adversarial majority
of at least $r^{\prime}$ distorted computations for a file is needed to
corrupt that particular file. Note that $X_{j}$ consists of those files where
the active adversaries $A^{\prime}$ are of size $j$; these can be chosen in
$\binom{q}{j}$ ways. The remaining workers in the file belong to $\cap_{i\in
A^{\prime}}D_{i}$ where $|\cap_{i\in A^{\prime}}D_{i}|\leq q$. Thus, the
remaining workers can be chosen in at most $\binom{q}{r-j}$ ways. It follows
that

$\displaystyle|X_{j}|\leq\binom{q}{j}\binom{q}{r-j}.$ (10)

Therefore,

$\displaystyle c_{\mathrm{max}}^{(q)}$ $\displaystyle\leq$
$\displaystyle{q\choose r^{\prime}}{q\choose r-r^{\prime}}+{q\choose
r^{\prime}+1}{q\choose r-(r^{\prime}+1)}$ (11) $\displaystyle+\cdots$
$\displaystyle+{q\choose r-1}{q\choose r-(r-1)}+{q\choose r}$ $\displaystyle=$
$\displaystyle\sum_{i=r^{\prime}}^{q}{{q}\choose{i}}{{q}\choose{r-i}}$ (12)
$\displaystyle=$
$\displaystyle\sum_{i=0}^{q}{{q}\choose{i}}{{q}\choose{r-i}}-\sum_{i=0}^{r^{\prime}-1}{{q}\choose{i}}{{q}\choose{r-i}}$
(13) $\displaystyle=$ $\displaystyle\frac{1}{2}{2q\choose r}.$ (14)

Eq. (12) follows from the convention that ${n\choose k}=0$ when $k>n$ or
$k<0$. Eq. (14) follows from Eq. (13) using the following observations

  * •

$\sum_{i=0}^{q}{{q}\choose{i}}{{q}\choose{r-i}}=\sum_{i=0}^{r}{{q}\choose{i}}{{q}\choose{r-i}}={2q\choose
r}$ in which the first equality is straightforward to show by taking all
possible cases: $q<r$, $q=r$ and $q>r$.

  * •

By symmetry,
$\sum_{i=0}^{r^{\prime}-1}{{q}\choose{i}}{{q}\choose{r-i}}=\sum_{i=r^{\prime}}^{q}{{q}\choose{i}}{{q}\choose{r-i}}=\frac{1}{2}{2q\choose
r}$.

The upper bound in Eq. (11) is met with equality when all adversaries choose
the same disagreement set which is a $q$-sized subset of the honest workers,
i.e., $D_{i}=D\subset H$ for $i=1,\dots,q$. In this case, it can be seen that
the sets $X_{j},j=r^{\prime},\dots,r$ are disjoint, so that (9) is met with
equality. Moreover, (10) is also an equality. This finally implies that (11)
is also an equality, i.e., this choice of disagreement sets saturates the
upper bound.

It can also be seen that in this case the adversarial strategy yields a graph
$\mathbf{G}$ with multiple maximum cliques. To see this, we note that the
adversaries in $A$ agree with all the computed gradients in $H\setminus D$.
Thus, they form of a clique of $M_{\mathbf{G}}^{(1)}$ of size $K-q$ in
$\mathbf{G}$. Furthermore, the honest workers in $H$ form another clique
$M_{\mathbf{G}}^{(2)}$ which is also of size $K-q$. Thus, the detection
algorithm cannot select one over the other and the adversaries will evade
detection; and the fallback robust aggregation strategy will apply.

Table 5: Parameters used for training. Figure |  Schemes |  Learning rate schedule
---|---|---
4(a) |  1,2,5,6 |  $(0.01,0.7)$
4(a) |  3,4 |  $(0.1,0.95)$
4(b) |  1 |  $(0.001,0.95)$
4(c) |  1,2 |  $(0.01,0.7)$
5(a) |  1,2 |  $(0.1,0.7)$
5(a) |  3,4 |  $(0.1,0.95)$
5(a) |  5,6 |  $(0.01,0.7)$
5(b) |  1 |  $(0.1,0.7)$
5(c) |  1,2 |  $(0.01,0.975)$
8 |  1,2 |  $(0.1,0.7)$
8 |  3,4 |  $(0.1,0.95)$
8 |  5,6 |  $(0.01,0.95)$
8 |  1 |  $(0.1,0.95)$
8 |  2 |  $(0.01,0.7)$
8 |  1 |  $(0.01,0.7)$
8 |  2 |  $(0.1,0.95)$
8 |  3 |  $(0.01,0.7)$
9(a) |  1,2 |  $(0.01,0.7)$
9(a) |  3 |  $(0.1,0.95)$
9(b) |  2 |  $(0.01,0.7)$
9(c) |  2 |  $(0.01,0.95)$

###  A.3 Experiment Setup Details

####  A.3.1 Cluster Setup

We used clusters of $K=15$ and $21$ workers arranged in various setups within
Amazon EC2. Initially, we used a PS of type i3.16xlarge and several workers of
type c5.4xlarge to setup a distributed cluster. However, this requires
training data to be transmitted from the PS to every single machine based on
our current implementation; an alternative approach one can follow is to setup
shared storage space accessible by all machines to store the training data.
Also, some instances were automatically terminated by AWS per the AWS _spot
instance_ policy
limitations;444https://docs.aws.amazon.com/AWSEC2/latest/UserGuide/spot-
interruptions.html this incurred some delays in resuming the experiments that
were stopped. In order to facilitate our evaluation and to avoid these issues
we decided to simulate the PS and the workers for the rest of the experiments
on a single instance of type x1.16xlarge. We emphasize that the choice of the
EC2 setup does not affect any of the numerical results in this paper since in
all cases we used a single virtual machine image with the same dependencies.

####  A.3.2 Dataset Preprocessing and Hyperparameter Tuning

The images have been normalized using standard values of mean and standard
deviation for the dataset. The value used for momentum (for gradient descent)
was set to $0.9$ and we trained for $16$ epochs in all experiments. The number
of epochs is precisely the invariant we maintain across all experiments, i.e.,
all schemes process the training data the same number of times. The batch size
and the learning rate are chosen independently for each method; the number of
iterations are adjusted accordingly to account for the number of epochs. We
followed the advice of the authors of DETOX and chose $(K,b)=(15,480)$ and
$(K,b)=(21,672)$ for the DETOX and baseline schemes. For Aspis, we used
$(K,b)=(15,14560)$ (32 samples per file) and $(K,b)=(21,3990)$ (3 samples per
file) for the ALIE experiments and $b=1365$ (3 samples per file) for the
remaining experiments except for the FoE optimal attack $q=4$ (_cf._ Figure 8)
for which $b=14560$ performed better. In Table 5, a learning rate schedule is
denoted by $(x,y)$; this notation signifies the fact that we start with a rate
equal to $x$ and every $z$ iterations we set the rate equal to $x\times
y^{t/z}$, where $t$ is the index of current iteration and $z$ is set to be the
number of iterations occurring between two consecutive checkpoints in which we
store the model (points in the accuracy figures). We will also index the
schemes in order of appearance in the corresponding figure’s legend.
Experiments which appear in multiple figures are not repeated in Table 5 (we
ran those training processes once). In order to pick the optimal
hyperparameters for each scheme, we performed an extensive grid search
involving different combinations of $(x,y)$. In particular, the values of $x$
we tested are 0.1, 0.01 and 0.001 and for $y$ we tried 1, 0.975, 0.95, 0.7 and
0.5. For each method, we ran 3 epochs for each such combination and chose the
one which was giving the lowest value of average cross-entropy loss (principal
criterion) and the highest value of top-1 accuracy (secondary criterion).

(a) $q=2$ adversaries.

(b) $q=4$ adversaries.

Figure 10: _ALIE_ optimal attack and median-based defenses (CIFAR-10), $K=15$
with different random seeds.

(a) $q=2$ adversaries.

(b) $q=4$ adversaries.

Figure 11: _ALIE_ optimal attack and _Bulyan_ -based defenses (CIFAR-10),
$K=15$ with different random seeds.

(a) $q=2$ adversaries.

(b) $q=4$ adversaries.

Figure 12: _ALIE_ optimal attack and _Multi-Krum_ -based defenses (CIFAR-10),
$K=15$ with different random seeds.

####  A.3.3 Error Bars

In order to examine whether the choice of the random seed affects the accuracy
of the trained model we have performed the experiments for the ALIE distortion
for two different seeds for the values $q=2,4$ for every scheme; we used $428$
and $50$ as random seeds. These tests have been performed for the case of
$K=15$ workers. In Figure 10(a), for a given method we report the minimum
accuracy, the maximum accuracy and their average for each evaluation point. We
repeat the same process in Figures 11(a) and 12(a) when comparing with Bulyan
and Multi-Krum, respectively. The corresponding experiments for $q=4$ are
shown in the Figures 10(b), 11(b) and 12(b).

Given the fact that these experiments take a significant amount of time and
that they are computationally expensive, we chose to perform this consistency
check for a subset of our experiments. Nevertheless, these results indicate
that prior schemes Rajput et al. (2019); Damaskinos et al. (2019); El Mhamdi
et al. (2018) are very sensitive to the choice of the random seed and
demonstrate an unstable behavior in terms of convergence. In all of these
cases the achieved value of accuracy at the end of the 16 epochs of training
is small compared to Aspis. On the other hand, the accuracy results for Aspis
are almost identical for both choices of the random seed.

####  A.3.4 Computation and Communication Overhead

Our scheme provides robustness under powerful attacks and sophisticated
distortion methods at the expense of increased computation and communication
time. Note that each worker has to perform $l$ forward/backward propagation
computations and transmit $l$ gradients per iteration. In related baseline El
Mhamdi et al. (2018); Blanchard et al. (2017) and redundancy-based methods
Rajput et al. (2019); Chen et al. (2018) each worker is responsible for a
single such computation. Experimentally, we have observed that Aspis needs up
to $5\times$ overall training time compared to other schemes to complete the
same number of training epochs. We emphasize that the training time incurred
by each scheme depends on a wide range of parameters including the utilized
defense, the batch size and the number of iterations and can vary
significantly. We believe that implementation-related improvements such as
utilizing GPUs can alleviate some of the overhead. Communication-related
algorithmic improvements are also worth exploring. Finally, our implementation
natively supports resuming from a checkpoint (trained model) and hence, when
new data becomes available we can only use that data to perform more epochs of
training.

####  A.3.5 Software

Our implementation of the Aspis algorithm used for the experiments builds on
the ByzShield’s Konstantinidis & Ramamoorthy (2021) PyTorch skeleton and has
been provided along with dependency information and instructions
555https://www.dropbox.com/sh/8bf4itlb3tz8o4n/AABKp6PaGlr_M8tRVmIRM6Pba?dl=0.
The implementation of ByzShield is available at
https://github.com/kkonstantinidis/ByzShield and uses the standard Github
license. We utilized the NetworkX package Hagberg et al. (2008) for the
clique-finding; its license is 3-clause BSD. The CIFAR-10 dataset Krizhevsky
(2009) comes with the MIT license; we have cited its technical report, as
required.

Table 6: Main notation of the paper. Symbol |  Meaning
---|---
$K$ |  number of workers
$q$ |  number of adversaries
$r$ |  redundancy (number of workers each file is assigned to)
$b$ |  batchsize
$B_{t}$ |  samples of batch of $t^{\mathrm{th}}$ iteration
$f$ |  number of files (alternatively called _groups_ or _tasks_)
$U_{j}$ |  $j^{\mathrm{th}}$ worker
$l$ |  computation load (number of files per worker)
$\mathcal{N}(U_{j})$ |  set of files of worker $U_{j}$
$\mathcal{N}(B_{t,i})$ |  set of workers assigned to file $B_{t,i}$
$\mathbf{g}_{t,i}$ |  true gradient of file $B_{t,i}$ with respect to $\mathbf{w}$
$\hat{\mathbf{g}}_{t,i}^{(j)}$ |  returned gradient of $U_{j}$ for file $B_{t,i}$ with respect to $\mathbf{*}{w}$
$\mathbf{m}_{i}$ |  majority gradient for file $B_{t,i}$
$\mathcal{U}$ |  worker set $\\{U_{1},U_{2},...,U_{K}\\}$
$\mathbf{G}$ |  graph indicating the agreements of pairs of workers in all of their common gradient tasks
$A$ |  set of adversaries
$M_{\mathbf{G}}$ |  maximum clique in $\mathbf{G}$
$c^{(q)}$ |  number of distorted gradients after detection and aggregation
$c_{\mathrm{max}}^{(q)}$ |  maximum number of distorted gradients after detection and aggregation (worst-case)
$D_{i}$ |  disagreement set (of workers) for $i^{\mathrm{th}}$ adversary
$r^{\prime}$ |  $(r+1)/2$, i.e., minimum number of distorted copies needed to corrupt majority vote for a file
$\epsilon$ |  $c^{(q)}/f$, i.e., fraction of distorted gradients after detection and aggregation
$X_{j}$ |  subset of files where the set of active adversaries is of size $j$


# Properties of sequence of linear functionals on $BV$ with applications

L-E. Persson, V. Tsagareishvili and G. Tutberidze  L-E. Persson, UiT-The
Arctic University of Norway, P.O. Box 385, N-8505, Narvik, Norway and
Department of Mathematics and Computer Science, Karlstad University, 65188
Karlstad, Sweden<EMAIL_ADDRESS>and<EMAIL_ADDRESS>V.
Tsagareishvili, Department of Mathematics, Faculty of Exact and Natural
Sciences, Ivane Javakhishvili Tbilisi State University, Chavchavadze str. 1,
Tbilisi 0128, Georgia<EMAIL_ADDRESS>G.Tutberidze, The University of
Georgia, School of science and technology, 77a Merab Kostava St, Tbilisi 0128,
Georgia<EMAIL_ADDRESS>and<EMAIL_ADDRESS>
###### Abstract.

This paper is devoted to investigating the sequence of some linear functionals
in the space $BV$ of finite variation functions. We prove that under certain
conditions this sequence is bounded. We also prove that this result is sharp.
In particular, the obtained results can be used to study convergence of some
general Fourier series. Moreover, the obtained conditions seem to be new and
useful also for classical orthonormal systems.

2020 Mathematics Subject Classification. 42C10, 46B07

Key words and phrases: Sequence of linear functionals, Banach spaces, Fourier
coefficients, Fourier series, Orthonormal series.

##  1\. INTRODUCTION

In order not to disturb the discussion in this introduction and the proofs of
our main result we have collected all notations, definitions and other
preliminaries in Section 2.

In this paper we prove a new convergence result for a special sequence of
linear functionals $\\{U_{n}\\}=\\{U_{n}(f)\\},$ defined by (2)-(4) and where
usually $f\in BV$ on $(0,1).$ See Theorem 1. We also prove that this result
is, in a sense, sharp. See Theorem 2.

The study of functionals has a rich history and many powerful and interesting
results are obtained, see e.g. the monographs [1, 2, 4, 5, 12, 13, 30] and the
references therein. And this interest seems only to increase and one reason is
absolutely the fact that such developments are powerful for various
applications.

For our investigation it is important to remind about the fact that from
Banach’s Theorem (see e.g.[2]) it follows that if $f\in L_{2}(0,1),\
\left(f\nsim 0\right),$ then there exists an ONS such that the Fourier series
of this function $f$ is not convergent on $[0,1]$ with respect to this system.
Thus, it is clear that the Fourier coefficients of functions of bounded
variation do not in general satisfy condition in Theorem B (the Menchov-
Rademacher Theorem).

Another motivation for this paper is to use our main result to obtain some new
results concerning convergence/divergence of general Fourier series. Some
other results for this case can be found in [6, 7, 8, 9, 10, 14, 16, 17, 18,
19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29]. See also the monograph [11].

The main results Theorems 1 and 2 are presented and proved in Section 3. The
new applications concerning convergence of general Fourier series can be found
Section 4. See Theorem 3, Corollary 1, Theorem 4 and Theorem 5.

##  2\. PRELIMINARIES

Let $\\{\varphi_{n}\\}$ be an orthonormal system (ONS) on $\left[0,1\right].$

We denote by $BV$ the class of all functions of bounded variation on $(0,1)$
and write $V\left(f\right)$ for the total variation of a function $f$ on
$\left[0,1\right]$.

By $A$ we denote the Banach space of absolutely convergent functions with the
norm ${{\left\|f\right\|}_{A}}$ defined by

${{\left\|f\right\|}_{A}}\,:=\,{{\left\|f\right\|}_{C}}\,+\,\int\limits_{0}^{1}{\left|\frac{df}{dx}\right|dx.}$
(1)

We will investigate the linear functionals $\\{U_{n}(f)\\}$ defined by

${U}_{n}(f):=\int_{0}^{1}f(x)Q_{n}(d,a,x)dx,$ (2)

where $f\in L_{2},$ $a=\\{a_{n}\\}\in l_{2}$ is an arbitrary sequence of
numbers and

${{Q}_{n}}(d,a,x):=\sum\limits_{k=1}^{n}{{{d}_{k}}{{a}_{k}}{\log
k}{{\varphi}_{k}}(x).}$ (3)

Here $\\{d_{n}\\}$ denote a sequence of real number such that

$\displaystyle d_{n}=O\left(\frac{\sqrt{n}}{\log^{2}(n+1)}\right).$ (4)

For this investigation of the functionals $\\{{U}_{n}(f)\\}$ we need the
following important Lemma (see [9]).

######  Lemma 1.

If $f\in L_{2}\left(0,1\right)$ takes only finite values on $\left[0,1\right]$
and $h\in L_{2}\left(0,1\right)$ is an arbitrary function, then

$\displaystyle\int_{0}^{1}f\left(x\right)h\left(x\right)dx$ $\displaystyle=$
$\displaystyle\sum_{i=1}^{n-1}\left(f\left(\frac{i}{n}\right)-f\left(\frac{i+1}{n}\right)\right)\int_{0}^{i/n}h\left(x\right)dx$
$\displaystyle+$
$\displaystyle\sum_{i=1}^{n}\int_{\left(i-1\right)/n}^{i/n}\left(f\left(x\right)-f\left(\frac{i}{n}\right)\right)h\left(x\right)dx$
$\displaystyle+$ $\displaystyle f\left(1\right)\int_{0}^{1}h\left(x\right)dx.$

We denote

$\displaystyle B_{n}\left(d,a\right)=\max_{1\leq
i<n}\left|\int_{0}^{i/n}Q_{n}\left(d,a,x\right)dx\right|.$ (6)

We say that the sequence of functionals $\\{U_{n}(f)\\}$ is bounded on the
space $V,$ if, for any $\\{a_{n}\\}\in l_{2},$

$\underset{n\to\infty}{\mathop{\limsup}}\left|{{U}_{n}}(f)\right|<+\infty.$

We also need the following result of S.Banach (see e.g. [2]):

######  Theorem A .

Let $f\in L_{2}$ be an arbytrary (non-zero) function. Then there exists an ONS
$\\{{\varphi}_{n}\\}$ such that

$\limsup_{n\rightarrow\infty}\left|\sum_{k=1}^{n}C_{k}(f)\varphi_{k}(x)\right|=+\infty\
\ \text{a.e. on}\ \ [0,1],$

where $C_{k}(f)$ are the Fourier coefficients of the function $f\in L_{2}$
with respect to the system $\\{{\varphi}_{k}\\}$ and defined as follows

${{C}_{k}}(f):=\int\limits_{0}^{1}{f(x){{\varphi}_{k}}(x)dx.}$ (7)

Moreover, we recall the following well-known result of Menshov and Rademacher
(see e.g. [11] Ch.9, p.332).

######  Theorem B.

If $\\{\varphi_{n}\\}$ is an ONS on $\left[0,1\right]$ and a number sequence
$\\{c_{n}\\}$ satisfies the condition

$\displaystyle\sum_{n=1}^{\infty}c_{n}^{2}\log_{2}^{2}n<+\infty,$

then the series

$\displaystyle\sum_{n=1}^{\infty}c_{n}\varphi_{n}\left(x\right)$

converges a.e. on $\left[0,1\right]$.

##  3\. The Main Results

Our first main result reads:

######  Theorem 1.

If, for any $\\{a_{n}\\}\in l_{2},$

$\displaystyle\qquad B_{n}\left(d,a\right)=O\left(1\right),$ (8)

then the sequence of functionals $\\{U_{n}(f)\\}$ is bounded on the space $BV$
for every $f\in BV.$

###### Proof.

By using Lemma 1, when $h\left(x\right)=Q_{n}\left(d,a,x\right)$ we have

$\displaystyle\int_{0}^{1}f(x)Q_{n}(d,a,x)dx$ $\displaystyle=$
$\displaystyle\sum_{i=1}^{n-1}\left(f\left(\frac{i}{n}\right)-f\left(\frac{i+1}{n}\right)\right)\int_{0}^{i/n}Q_{n}(d,a,x)dx$
(9)
$\displaystyle+\sum_{i=1}^{n}\int_{\left(i-1\right)/n}^{i/n}\left(f\left(x\right)-f\left(\frac{i}{n}\right)\right)Q_{n}(d,a,x)dx$
$\displaystyle+f\left(1\right)\int_{0}^{1}Q_{n}(d,a,x)dx:=A_{1}+A_{2}+A_{3}.$

Let $f\in BV$, then we get (see (6))

$\displaystyle\left|A_{1}\right|$ $\displaystyle\leq\max_{1\leq
i<n}\left|\int_{0}^{i/n}Q_{n}(d,a,x)dx\right|\ \cdot\
\sum_{i=1}^{n-1}\left|f\left(\frac{i}{n}\right)-f\left(\frac{i+1}{n}\right)\right|$
$\displaystyle\leq V(f)B_{n}(d,a).$

Hence, from condition (8) it follows that

$\left|A_{1}\right|=O(1)V(f).$

By applying Hölder’s inequality and (4) , we get (since $\\{a_{n}\\}\in
l_{2}$)

$\displaystyle\left|A_{2}\right|$
$\displaystyle\leq\sum_{i=1}^{n}\sup_{x\in\left[\frac{i-1}{n},\frac{i}{n}\right]}\left|f(x)-f\left(\frac{i}{n}\right)\right|\int_{\left(i-1\right)/n}^{i/n}\left|Q_{n}(d,a,x)\right|dx$
$\displaystyle\leq V(f)\max_{1\leq i\leq
n}\int_{\left(i-1\right)/n}^{i/n}\left|Q_{n}(d,a,x)\right|dx$
$\displaystyle\leq
V(f)\frac{1}{\sqrt{n}}\left(\int_{0}^{1}Q_{n}^{2}(d,a,x)dx\right)^{1/2}$
$\displaystyle=\frac{V(f)}{\sqrt{n}}\left(\int_{0}^{1}\left(\sum_{k=1}^{n}d_{k}a_{k}\log
k\varphi_{k}(x)\right)^{2}dx\right)^{1/2}$
$\displaystyle=\frac{V(f)}{\sqrt{n}}\left(\sum_{k=1}^{n}d_{k}^{2}a_{k}^{2}\log^{2}k\right)^{1/2}$
$\displaystyle=V(f)\cdot\frac{\max\limits_{1\leq k\leq
n}|d_{k}|}{\sqrt{n}}\cdot\log
n\left(\sum_{k=1}^{n}a_{k}^{2}\right)^{1/2}=O(1)V(f).$

By using (6) and Cauchy’s inequality, for any $\\{a_{n}\\}\in l_{2}$ we find
that

$\displaystyle\left|A_{3}\right|$
$\displaystyle=O(1)\left|\int_{0}^{1}Q_{n}(d,a,x)dx\right|$ $\displaystyle\leq
O(1)\left(\left|\int_{0}^{1-1/n}Q_{n}(d,a,x)dx\right|+\left|\int_{1-1/n}^{1}Q_{n}(d,a,x)dx\right|\right)$
$\displaystyle\leq
O(1)\left(B_{n}(d,a)+\frac{1}{\sqrt{n}}\left(\int_{0}^{1}Q_{n}^{2}(d,a,x)dx\right)^{1/2}\right)=O(1).$

Taking into consideration in (9) the above estimates of $|A_{1}|,$ $|A_{2}|$
and $|A_{3}|$ we have that

$\left|\int_{0}^{1}f(x)\sum_{k=1}^{n}d_{k}a_{k}\log
k\varphi_{k}(x)\right|=O(1).$

It follows that

$\left|U_{n}(f)\right|\leq M(f),$ (10)

where $M(f)$ is a constant which does not depend on $n$ and the proof is
complete.

∎

Next we state a result which, in particular, show that the statement in
Theorem 1 is, in a sense, sharp.

######  Theorem 2.

If for some $\\{b_{n}\\}\in l_{2}$

$\limsup_{n\rightarrow\infty}B_{n}(d,b)=+\infty,$

then there exists a function $g\in A$, such that

$\limsup_{n\rightarrow\infty}\left|U_{n}(g)\right|=+\infty.$

###### Proof.

First we suppose that

$\limsup_{n\rightarrow\infty}\left|\int_{0}^{1}Q_{n}\left(d,b,x\right)dx\right|=+\infty.$

Then, if $g(x)=1,\text{ }x\in[0,1],$ we have

$\limsup_{n\rightarrow\infty}\left|\int_{0}^{1}g(x)Q_{n}\left(d,b,x\right)dx\right|=+\infty.$

Obviously $g\in A.$ Theorem 2 holds in this case.

Next we suppose that

$\displaystyle\left|\int_{0}^{1}Q_{n}\left(d,b,x\right)dx\right|=O(1).$ (11)

Let $1\leq i_{n}<n$ be an integer, such that

$B_{n}\left(d,b\right)=\max_{1\leq
i<n}\left|\int_{0}^{i/n}Q_{n}\left(d,b,x\right)dx\right|=\left|\int_{0}^{i_{n}/n}Q_{n}\left(d,c,x\right)dx\right|.$

Suppose that for some sequence $b=\\{b_{k}\\}\in l_{2}$

$\displaystyle\limsup_{n\rightarrow\infty}B_{n}(d,b)=+\infty.$ (12)

Consider the following sequence of test functions:

$f_{n}\left(x\right)=\left\\{\begin{array}[]{ccc}0,&\text{when}&x\in\left[0,\frac{i_{n}}{n}\right]\\\
1,&\text{when}&x\in\left[\frac{i_{n}+1}{n},1\right]\\\ \text{continuous and
linear,
}&\text{when}&x\in\left[\frac{i_{n}}{n},\frac{i_{n}+1}{n}\right].\end{array}\right.$

Then (see (1))

$\left\|f_{n}\right\|_{A}=\int_{0}^{1}\left|f_{n}^{{}^{\prime}}\left(x\right)\right|dx+\left\|f_{n}\left(x\right)\right\|_{C}\leq
2.$

Furthermore,

$\displaystyle\left|\sum_{i=1}^{n-1}\left(f_{n}\left(\frac{i}{n}\right)-f_{n}\left(\frac{i+1}{n}\right)\right)\int_{0}^{i/n}Q_{n}\left(d,b,x\right)dx\right|$
(13)
$\displaystyle=\left|\int_{0}^{{i_{n}}/n}Q_{n}\left(d,b,x\right)dx\right|=B_{n}\left(d,b\right).$

Then, if $x\in\left[\frac{i-1}{n},\frac{i}{n}\right]$ we find that

$\left|f_{n}\left(x\right)-f_{n}\left(\frac{i}{n}\right)\right|\left\\{\begin{array}[]{ccc}\leq
1,&\text{if}&i=i_{n}+1,\\\ 0,&\text{if}&i\neq i_{n}+1,\\\ \end{array}\right.$

and it implies that (since $\\{b_{n}\\}\in l_{2}$)

$\displaystyle\left|\sum_{i=1}^{n}\int_{\left(i-1\right)/n}^{i/n}\left(f\left(x\right)-f\left(\frac{i}{n}\right)\right)Q_{n}\left(d,b,x\right)dx\right|$
(14)
$\displaystyle\leq\sum_{i=1}^{n}\sup_{x\in\left[\frac{i-1}{n},\frac{i}{n}\right]}\left|f\left(x\right)-f\left(\frac{i}{n}\right)\right|\int_{\left(i-1\right)/n}^{i/n}\left|Q_{n}(d,b,x)\right|dx$
$\displaystyle\leq V(f)\underset{1\leq i\leq
n}{\mathop{\max}}\,\int\limits_{{(i-1)}/{n}}^{{i}/{n}}{\left|Q_{n}(d,b,x)\right|dx}$
$\displaystyle=O(1)\frac{1}{\sqrt{n}}\left(\int_{0}^{1}Q_{n}^{2}(d,b,x)dx\right)^{1/2}$
$\displaystyle=O(1)\frac{1}{\sqrt{n}}\max_{1\leq k\leq n}d_{k}\log
n{{\left(\sum\limits_{k=1}^{n}{b_{k}^{2}}\right)}^{\frac{1}{2}}}=O(1).$

Consequently, by using (1) when $f\left(x\right)=f_{n}\left(x\right)$ and
$Q_{n}\left(d,a,x\right)=Q_{n}\left(d,b,x\right),$ and combining (11), (13),
(14), we get that

$\left|\int_{0}^{1}f_{n}\left(x\right)Q_{n}\left(d,b,x\right)\right|dx\geq
B_{n}(d,b)-O\left(1\right)-O(1).$

From here and from (12) we have, that

$\limsup_{n\rightarrow\infty}{\left|\int_{0}^{1}f_{n}\left(x\right)Q_{n}\left(d,b,x\right)dx\right|}=+\infty.$

Finally, we note that since

$U_{n}\left(f\right)=\int_{0}^{1}f\left(x\right)Q_{n}\left(d,b,x\right)dx$

is a sequence of linear bounded functionals on $A$, then by the Banach-
Steinhaus theorem, there exists a function $g\in A$ such that

$\displaystyle\limsup_{n\rightarrow\infty}|U_{n}(g)|=\limsup_{n\rightarrow\infty}{\left|\int_{0}^{1}g\left(x\right)Q_{n}\left(d,b,x\right)dx\right|}=+\infty.$
(15)

The proof is complete.

∎

##  4\.  Applications concerning convergence of general Fourier series

Our first application reads:

######  Theorem 3.

If condition (8) of Theorem 1 holds then, for any function $f\in BV,$

$\sum_{k=1}^{\infty}d_{k}^{2}C_{k}^{2}(f)\log^{2}k<+\infty.$

###### Proof.

By using condition (8) of Theorem 1, and using equation (10) and (7) we have
that

$\displaystyle\sum_{k=1}^{n}d_{k}C_{k}(f)\log k$
$\displaystyle=\int_{0}^{1}f(x)\sum_{k=1}^{n}d_{k}\log k\varphi_{k}(x)dx$
$\displaystyle=\int_{0}^{1}f(x)Q_{n}(d,a,x)dx.$

Hence,

$\sum_{k=1}^{n}d_{k}a_{k}C_{k}(f)\log k=U_{n}(f).$

Since

$\left|U_{n}(f)\right|=O(1)$

it follows that

$\sum_{k=1}^{n}d_{k}a_{k}\log kC_{k}(f)=O(1).$

Now, if we suppose that for any $\\{a_{k}\\}\in l_{2},$

$\underset{n\to\infty}{\mathop{\limsup}}\,\,\left|{{U}_{n}}(f)\right|<+\infty,$

then the following series

$\sum_{k=1}^{\infty}d_{k}a_{k}\log kC_{k}(f)$ (16)

is convergent.

This means that $\\{d_{k}C_{k}(f)\log k\\}\in l_{2},$ or

$\sum_{k=1}^{\infty}d_{k}^{2}C_{k}^{2}(f)\log^{2}k<+\infty.$

The proof is complete.

∎

In particular, Theorem A and Theorem 1 imply the following new result:

######  Corollary 1.

If condition (8) of Theorem 1 holds for any function $f\in BV,$ then the
following series

$\sum_{k=1}^{\infty}d_{k}C_{k}(f)\varphi_{k}(x)$

is convergent a.e. on $[0,1].$

######  Remark.

If condition (8) of Theorem Theorem B is fulfilled and $d_{k}=1,$
$k=1,2,\dots,$ then, for any $f\in BV$ the series

$\sum_{k=1}^{\infty}C_{k}(f)\varphi_{k}(x)$

is convergent a.e. on $[0,1].$

Next, we state the following result showing that Theorem 3 is, in a sense,
sharp.

######  Theorem 4.

For any function $g\in A$ $(g\neq 0)$ there exists an ONS $\\{\varphi_{n}\\}$
such that for some $\\{a_{n}\\}\in l_{2}$ and $d_{k}=1,$ $k=1,2,\dots$

$\displaystyle\limsup_{n\rightarrow\infty}\sum_{k=1}^{n}C_{k}^{2}(f)\log^{2}k=\limsup_{n\rightarrow\infty}\left|U_{n}(g)\right|=+\infty.$
(17)

###### Proof.

Let $g$ be an arbitrary function. According to the Banach Theorem there exists
an ONS $\\{\varphi_{n}\\}$ such that

$\displaystyle\limsup_{n\rightarrow\infty}\left|\sum_{k=1}^{n}C_{k}(g)\varphi_{k}(x)\right|=+\infty\
\ \text{a.e. on}\ [0,1].$ (18)

Consequently, by using (18) and Theorem A, we conclude that

$\displaystyle\sum_{k=1}^{\infty}C_{k}^{2}(g)\log^{2}k=+\infty.$ (19)

Indeed, suppose the contrary to (17) namely that for arbitrary $\\{a_{n}\\}\in
l_{2}$

$\limsup_{n\rightarrow\infty}\left|U_{n}(g)\right|<+\infty.$

Then as it follows from (16) when $d_{k}=1,$ $k=1,2,\dots$ for any
$\\{a_{n}\\}\in l_{2}$ that the series

$\sum_{k=1}^{\infty}a_{k}\log kC_{k}(g)$

is convergent. Thus, $\\{C_{k}(g)\log k\\}\in l_{2}$ or

$\sum_{k=1}^{\infty}C_{k}^{2}(g)\log^{2}k<+\infty,$

which contradicts (19).

This contradiction shows that (17) holds so the proof is complete.

∎

Finally, we state the following efficiency result:

######  Theorem 5.

Let $\\{\varphi_{n}\\}$ be an ONS such that uniformly with respect to
$x\in[0,1]$ it holds that

$\displaystyle\int_{0}^{x}\varphi_{n}(x)dx=O\left(\frac{1}{n}\right).$ (20)

Then for any $a=\\{a_{n}\\}\in l_{2},$

$\displaystyle
B_{n}(d,a)\leq\max_{x\in[0,1]}\left|\int_{0}^{x}\sum_{k=1}^{n}d_{k}a_{k}\log
k\varphi_{k}(u)du\right|=O(1).$ (21)

###### Proof.

According to (20) and by the Cauchy inequality we get (see (4))

$\displaystyle B_{n}(d,a)$
$\displaystyle\leq\max_{x\in[0,1]}\left|\int_{0}^{x}\sum_{k=1}^{n}d_{k}a_{k}\log
k\varphi_{k}(u)du\right|$
$\displaystyle=\max_{x\in[0,1]}\left|\sum_{k=1}^{n}d_{k}a_{k}\log
k\int_{0}^{x}\varphi_{k}(u)du\right|=O(1)\left|\sum_{k=1}^{n}a_{k}d_{k}\log
k\frac{1}{k}\right|$
$\displaystyle=O(1)\left(\sum_{k=1}^{n}a_{k}^{2}\right)^{1/2}\left(\sum_{k=1}^{n}d_{k}^{2}\log^{2}k\frac{1}{k^{2}}\right)^{1/2}$
$\displaystyle=O(1)\left(\sum_{k=1}^{n}\frac{k}{\log^{4}(k+1)}\frac{\log^{2}k}{k^{2}}\right)^{1/2}=O(1).$

Hence, (21) is proved so the proof is complete.

∎

Remark: Consequently, the functionals defined by (2) are bounded e.g. when
$\\{\varphi_{n}\\}$ is the trigonometric or Walsh system.

Final remark. We pronounce that some other convergence/divergence result of
one-dimensional Vilinkin-Fourier series can be found in the new book [18]. We
hope that our (Functional) approach can be used to contribute to solving some
of the open questions raised in this book. In this connection we also mention
the new paper [19], which is related to the famous Carleson paper [3].

## References

  * [1] N.I. Akhiezer and I.M. Glazman, Theory of liner operators in Hilbert Spaces, Dover Publishers, 1993, 400 pp.
  * [2] S. Banach, Theorie des operations lineaires, American Mathematical Society 1978, 259 pp.
  * [3] L. Carleson, On convergence and growth of partial sums of Fourier series, Acta Math 116 (1966), no.1, 135-157.
  * [4] N. Dunford and J. schwartz, Liner operators, part I-II. Wiley, New York, 1988, 2592 pp.
  * [5] R.E. Edvards, Functional Analysis: Theory and Applications, Dover Publisher, 783 pp.
  * [6] L. Gogoladze and G. Cagareishvili, General Fourier coefficients and convergence almost everywhere, Izv. Ross. Akad. Nauk. Ser. Math.85 (2021), no.2, 60-72 and Izv. Math. 85 (2021), no.2, 228-240.
  * [7] L. Gogoladze and G. Cagareishvili, On the absolute convergence of general Fourier series, Publ. Math. Debrecen, 100(2022), no.3-4, 277-294.
  * [8] L. Gogoladze and G. Tsagareishvili, Optimal convergence factors for general Fourier coefficients, Contemp. Math. Anal. (to appear).
  * [9] L. Gogoladze and V. Tsagareishvili, Fourier coefficients of continuous functions, Math. Notes 91 (2012), no.5-6, 645-656.
  * [10] L.Gogoladze and V.Tsagareishvili. Differentiable functions and general orthonormal systems, Mosc. Math.J. 19 (2019), no.4, 695-707
  * [11] B.S. Kashin and A.A. Saakyan, Orthogonal Series, Translations of Mathematical Monographs, American Mathematical Society, 2005, 451 pp.
  * [12] L.V. Kantorovich and G.P. Akilov, Functional Analysis, Pergamon Press, Oxford, 1982, 604 pp.
  * [13] A.H. Kolmogorov and C.B.Fomin, Elements The Theory of Functions, Martin Fine Books, 2012, 280 pp.
  * [14] J.M. Mclaughlin, Integrated orthonormal series, Pacific J. Math. 42 (1972), 469-475.
  * [15] A. M. Olevskii, Divergent Fourier series, Izv. Akad. Nauk SSSR Ser. Mat. 27 (1963), 343-366.
  * [16] L. E. Persson, G. Tephnadze and G. Tutberidze, On the boundedness of subsequences of Vilenkin-Fejér means on the martingale Hardy spaces, Oper. Matrices, 14 (2020), no.1, 283-294.
  * [17] L. E. Persson, G. Tephnadze and P. Wall, On an approximation of 2-dimensional Walsh-Fourier series in the martingale Hardy spaces, Ann. Funct. Anal. 9 (2018), no.1, 137-150.
  * [18] L. E. Persson, G. Tephnadze and F. Weisz, Martingale Hardy Spaces and Summability of one-dimensional Vilenkin-Fourier Series, book manuscript, Birkhäuser/Springer, 2022, 626 pp.
  * [19] L.-E. Persson, F. Schipp, G. Tephnadze and F. Weisz, An analogy of the Carleson-Hunt theorem with respect to Vilenkin systems, J. Fourier Anal. Appl. 28 48 (2022), 1-29.
  * [20] G. Tephnadze, On the partial sums of Vilenkin-Fourier series, J. Contemp. Math. Anal. 54 (2019), no.6, 23-32.
  * [21] G. Tephnadze, On the partial sums of Walsh-Fourier series, Colloq. Math. 141 (2015), no.2, 227-242.
  * [22] G. Tephnadze, On the convergence of partial sums with respect to Vilenkin system on the martingale Hardy spaces, J. Contemp. Math. Anal. 53 (2018), no.5, 294-306.
  * [23] V.Tsagareishvili, Some properties of general orthonormal systems, Colloq. Math. 162 (2020), no.2, 201-209.
  * [24] V.Tsagareishvili, Some particular properties of general orthonormal systems, Period. Math. Hungar. 81 (2020), no.1, 149-157.
  * [25] V.Tsagareishvili, General orthonormal systems and absolute convergence, Izv. Ros. Acad. Nauk. Ser. Math. 84 (2020), no.4, 208-220 and Izv. Math. 84 (2020), no. 4, 816-828.
  * [26] V.Tsagareishvili. On the majorants of general Fourier coefficients and best approximations, Publ. Math. Debrecen 102 (2023), no.3-4, 475-494.
  * [27] V. Tsagareishvili and G. Tutberidze, Multipliers of absolute convergence, Mat. Zametki 105 (2019), no.3, 433-443 and Mat. Notes 107 (2019), no.3-4, 439-448.
  * [28] V. Tsagareishvili and G. Tutberidze, Absolute convergence factors of Lipshitz class functions for general Fourier series, Georgian Math. J. 29 (2022), no.2, 309-315.
  * [29] V. Tsagareishvili and G. Tutberidze, Some problems of convergence of general Fourier series, Izv. Math. Acad. Nauk Armenii Math. 57 (2022), no.6, 70-80.
  * [30] K. Yosida , Functional Analysis, Springer verlag, Berlin, 1995, 501 pp.