# A Simplified Convergence Theory for Byzantine Resilient Stochastic Gradient
Descent††thanks: This work has been published in the EURO Journal on
Computational Optimization. See https://doi.org/10.1016/j.ejco.2022.100038 for
the final version.

Lindon Roberts  Mathematical Sciences Institute, Building 145, Science Road,
Australian National University, Canberra ACT 2601, Australia
(first.last@anu.edu.au). School of Mathematics and Statistics, Carslaw
Building, University of Sydney, Camperdown NSW 2006, Australia
(lindon.roberts@sydney.edu.au).  Edward Smyth  Mathematical Sciences
Institute, Building 145, Science Road, Australian National University,
Canberra ACT 2601, Australia (first.last@anu.edu.au).

###### Abstract

In distributed learning, a central server trains a model according to updates
provided by nodes holding local data samples. In the presence of one or more
malicious servers sending incorrect information (a Byzantine adversary),
standard algorithms for model training such as stochastic gradient descent
(SGD) fail to converge. In this paper, we present a simplified convergence
theory for the generic Byzantine Resilient SGD method originally proposed by
Blanchard et al. [NeurIPS 2017]. Compared to the existing analysis, we shown
convergence to a stationary point in expectation under standard assumptions on
the (possibly nonconvex) objective function and flexible assumptions on the
stochastic gradients.

Keywords: stochastic optimization, distributed learning, Byzantine resilience.

Mathematics Subject Classification (2020): 90C15, 65K05, 68T07

##  1 Introduction

Distributed learning is a branch of machine learning in which large datasets
are stored on several client devices, and a central server controls the
learning process [32, 15]. In this setting, the local data is never shared or
transferred across clients, or shared with the central server, and the actual
optimization can be performed either by the central server or separately on
each client [9, 6]. In the first case, learning is performed by the central
server requesting (stochastic) gradient information from each client and
aggregating this information within its optimization procedure [23, 26].

From a mathematical optimization perspective, distributed learning presents
several challenges including communication overheads [20, 10] and
asynchronicity [23]. This may be further complicated in the case of federated
learning, where the client datasets are assumed to be heterogeneous [27].
Here, we consider the case of distributed learning in the presence of
adversarial attacks; the reliance on many clients and network communication
makes this a more relevant concern than in traditional learning. Specifically,
we consider the case of Byzantine adversaries, which alter the gradient
information sent from (potentially multiple) clients to the server, for
example through data poisoning [2, 7], where individual clients’ datasets are
altered, or model update poisoning [1], where the information sent to the
central server is directly corrupted. The goal of adversarial attacks can be
untargeted, attempting to decrease the model’s accuracy overall [2], or
targeted, aiming to change the model’s behavior on only a specific subset of
inputs [7, 1]. A comprehensive taxonomy of adversarial attacks is given in
[16, Section 5].

In the presence of adversarial attacks, standard optimization methods such as
stochastic gradient descent (SGD) can fail [3], and so the development of
optimization algorithms which are Byzantine resilient is of critical
importance to the success of distributed learning. Where the individual
clients’ datasets are i.i.d., algorithms such as SGD can be made Byzantine
resilient using robust averaging techniques. In this paper, we introduce a
simplified convergence analysis of Byzantine Resilient SGD (BRSGD) [3] for
nonconvex learning problems. Our analysis covers the same range of approaches
for aggregating gradient information from i.i.d. client datasets, but uses
more standard smoothness assumptions on the objective function and the non-
corrupted stochastic gradients. As a trade-off, we show convergence to first-
order optimality in expectation, rather than almost surely as in [3]. We also
show a convergence rate of $\mathcal{O}(1/K^{(1-p)/2})$ when the learning rate
sequence is chosen as $\mathcal{O}(k^{-p})$ for $p\in(1/2,1)$, which was not
provided in [3].

#### Related Work

A general analysis of SGD in a federated learning setting (which generalizes
distributed learning) for nonconvex objectives can be found in [19]. In the
case of Byzantine resilient SGD for i.i.d. client datasets, several different
robust averaging techniques have been proposed. These include the geometric
median [8, 28, 22], coordinate-wise medians and trimmed means [30, 31],
neighborhood-based averaging [3], iterative filtering [25, 31] and
combinations of multiple such approaches [14].

The types of convergence theory of these different methods varies. Convergence
only for strongly convex objectives is considered in [8, 22, 30], and in [25]
for the full population loss (rather than the empirical loss). For nonconvex
objectives, high probability convergence to approximate first- and second-
order optimal points is given in [30] and [31] respectively.

Alternatively, [3] considers BRSGD applied to nonconvex objectives with
decreasing learning rates, which proves almost sure convergence to stationary
points rather than to a neighborhood, similar to the standard SGD setting [5].
This analysis applies to a generic robust aggregator satisfying specific
assumptions. Different aggregations methods which satisfy this assumption have
been proposed in [3, 28, 14].

We conclude by noting that [29, 11, 12] consider the case of Byzantine
resilient federated learning in the case of non-i.i.d. datasets and have
developed specific robust aggregators suited for this setting (with associated
convergence theory). This is a more difficult problem, made visible for
instance by [11] requiring a maximum of 25% of clients be corrupted (rather
than approximately 50% for the i.i.d. case).

#### Contributions

In this paper, we present a simplified convergence result for BRSGD. Unlike
the original analysis in [3] (which was based on the analysis of SGD in [4]),
we use standard smoothness assumptions on the objective, closer in spirit to
the standard analysis of SGD [5]. For the (non-corrupted) stochastic gradient
estimates, we use a general expected smoothness assumption based on [17].
Under these conditions, we prove the convergence of BRSGD to stationary points
in expectation: we note that this is weaker than the almost-sure result from
[3], coming from our more standard problem assumptions and simpler analysis.
Our result and proof technique has some similarities to [24, Lemma 4.3], which
shows almost sure convergence of standard SGD under general expected
smoothness conditions on stochastic gradients.

As described above, since BRSGD in [3] is a generic framework, our results are
applicable to any aggregation function satisfying the same assumptions,
including all those in [3, 28, 14].

#### Structure

We begin by describing the general model of distributed learning with
Byzantine adversaries and describe the BRSGD method in Section 2. Our new
convergence analysis is given in Section 3. The corresponding convergence
rates are shown in Section 4, and we conclude in Section 5.

#### Notation

We use $\|\cdot\|$ to be the Euclidean norm and $\langle\cdot,\cdot\rangle$ to
be the corresponding inner product on $\mathbb{R}^{d}$, and let
$[m]:=\\{1,\ldots,m\\}$.

##  2 Problem & Byzantine Resilient SGD

We begin by describing the Byzantine adversarial model problem and the
Byzantine resilient SGD algorithm from [3].

###  2.1 Byzantine Adversarial Model Problem

In the distributed learning problem, our data is split across $m$ nodes (or
devices) while our model is centralized [16]. For our $i^{\text{th}}$ node,
$\\{((x_{i})_{j},(y_{i})_{j})\\}_{j=1}^{n_{i}}$ is our dataset, where $n_{i}$
is the number of data-points stored at that node. We will assume that each
element is drawn from a distribution that is common across all nodes,
$((x_{i})_{j},(y_{i})_{j})\sim\Omega$. As this distribution is theoretical, we
replace our unknown distribution with the known empirical distribution
$\Omega^{\prime}_{i}$, where we select each element of our dataset with
probability $\frac{1}{n_{i}}$. Having been given this dataset, from a space of
functions parametrized by $w\in\mathbb{R}^{d}$, we wish to find a model
function $f$ for which $f(x)\approx y$, for all $i\in[m]$ and
$(x,y)\sim\Omega^{\prime}_{i}$. Hence, we look for a function $f(\cdot;w)$
that minimizes the average empirical risk across our $m$ nodes:

$\min_{w\in\mathbb{R}^{d}}F(w):=\frac{1}{m}\sum^{m}_{i=1}F_{i}(w),$ (2.1)

where $F_{i}$ is the empirical risk of the model $f(w)$ on the $i^{\text{th}}$
node. Specifically:

$F_{i}(w):=\frac{1}{n_{i}}\sum^{n_{i}}_{j=1}l((y_{i})_{j},f((x_{i})_{j};w)).$
(2.2)

where $l(\cdot,\cdot)$ is a loss function that quantifies the difference
between the two values. Note that both the loss function and the model remain
constant across the nodes.

We solve (2.1) with iterative methods converging to a neighbourhood of
stationary points of our problems. These iterative methods involve each node
sending an estimation of the gradient of our function at the current point to
the central server. We model component failure or corruption by setting some
of our nodes to be Byzantine adversaries [3], who may send arbitrary values to
the central server. In our problem, of our $m$ nodes, $q$ will be Byzantine
adversaries as defined below. Typically we require $q<m/2$, however there are
slight differences in some methods.

######  Definition 2.1 (Byzantine Adversaries).

Let $\\{(g_{1})_{k},(g_{2})_{k},...,(g_{m})_{k}\\}$ be the set of correct
local gradient estimators calculated by each node for the $k^{\text{th}}$
iteration of an algorithm. If $q$ out of $m$ vectors are Byzantine
adversaries, then, the set of correct vectors at every iteration are partially
replaced by vectors
$\\{(\tilde{g}_{1})_{k},(\tilde{g}_{2})_{k},...,(\tilde{g}_{m})_{k}\\}$,
according to:

$(\tilde{g}_{i})_{k}:=\begin{cases}(B_{i})_{k},&\text{if}\ \text{the
$i^{\text{th}}$ node is Byzantine,}\\\
(g_{i})_{k},&\text{otherwise.}\end{cases}$ (2.3)

The indices of the adversaries may change across iterations and the value of
the Byzantine gradient, $(B_{i})_{k}$, may be a function dependent on
$\\{(g_{1})_{k},(g_{2})_{k},...,(g_{m})_{k}\\}$, the current value of the
model $x_{k}$, the current step-size $\alpha_{k}$, or any previous
information.

In the taxonomy of [16, Section 5], this framework corresponds to dynamic,
white box adversaries using within-update collusion, where the adversary
functions via data poisoning or model update poisoning.

###  2.2 BRSGD Algorithm

We now outline the Byzantine Resilient SGD (BRSGD) algorithm framework for
solving (2.1) in the presence of Byzantine adversaries. In iteration $k$ of
this method, initially from [3], the central server initially collects the
(possibly corrupted) local gradient information
$(\tilde{g}_{i})_{k}\in\mathbb{R}^{d}$ from each node $i\in[m]$. It then
aggregates these $m$ vectors to produce a final gradient estimate
$A_{k}\in\mathbb{R}^{d}$ using some aggregation function $\text{\sc
Agg}\left((\tilde{g}_{1})_{k},(\tilde{g}_{2})_{k},...,(\tilde{g}_{m})_{k}\right)$:
we will later give specific requirements on Agg. We then take a gradient
descent-type step with a pre-specified learning rate $\alpha_{k}>0$. The full
BRSGD method is given in Algorithm 1.

1:Initial point $w_{0}\in\mathbb{R}^{d}$, sequence of learning rates
$\\{\alpha_{k}\\}^{\infty}_{k=0}$ with $\alpha_{k}>0$ for all $k$, gradient
aggregation function $\text{\sc
Agg}:\underbrace{\mathbb{R}^{d}\times\cdots\times\mathbb{R}^{d}}_{\text{$m$
times}}\to\mathbb{R}^{d}$.

2:for $k=0,1,2,\ldots$ do

3: for machines $i=1,2,...,m$ in parallel do

4: if $i$ is a non-Byzantine node then

5: Compute local stochastic gradient $(\tilde{g}_{i})_{k}=(g_{i})_{k}$, where
$(g_{i})_{k}\in\mathbb{R}^{d}$ is the (stochastic) gradient estimate at node
$i$.

6: else

7: Set $(\tilde{g}_{i})_{k}=(B_{i})_{k}$, where $(B_{i})_{k}\in\mathbb{R}^{d}$
is the attack gradient.

8: end if

9: end for

10: Aggregate received gradient information: $A_{k}=\text{\sc
Agg}\left((\tilde{g}_{1})_{k},(\tilde{g}_{2})_{k},...,(\tilde{g}_{m})_{k}\right)$.

11: Set $w_{k+1}=w_{k}-\alpha_{k}A_{k}$.

12:end for

Algorithm 1 Byzantine Resilient Stochastic Gradient Descent (BRSGD) [3]

Since the non-corrupted local gradient estimators $(g_{i})_{k}$ can be
stochastic gradient estimates, we also outline our formal stochastic approach
to this problem. We introduce a probability space,
$(\mathbb{P},\mathcal{F},\Omega)$, with an associated filtration
$(\mathcal{F}_{k})_{k\in\mathbb{N}}$ to model our gradient information as an
adapted process on a filtration, based on framework from [21]. Our sample
space will be
$\Omega^{\prime}:=\Omega_{1}^{\prime}\times\Omega_{2}^{\prime}\times...\times\Omega_{m}^{\prime}$.
Let the random variable modelling the sample drawn at the $i^{th}$ node for
the $k^{th}$ iterate be $(\zeta_{k})_{i}:=(\zeta_{k})_{i}(\omega)$. The value
of the gradient estimator at the $i^{th}$ node for the $k^{th}$ iterate will
be modelled by $g_{i}(w_{k}):=G(w_{k},(\zeta_{k})_{i})$, where $G(w,\zeta)$ is
the random variable modelling gradient updates at point $w$ and it will be
denoted $G(w)$. Since our datasets are assumed to be i.i.d., our function
$G(w_{k},\zeta)$ is not dependent on the node, and hence, we have the
following property:

$\mathbb{E}[g_{1}(w_{k})]=\mathbb{E}[g_{2}(w_{k})]=\cdots=\mathbb{E}[g_{m}(w_{k})].$
(2.4)

Our filtration $\mathcal{F}_{k}$ will be the $\sigma$-algebra generated by our
previous random variables, i.e.
$\mathcal{F}_{k}=\sigma\left(\bigcup^{k-1}_{i=0}\bigcup^{m}_{j=1}\sigma((\zeta_{i})_{j})\right)$
and let $\mathcal{F}:=\bigcup^{\infty}_{n=1}\mathcal{F}_{k}$. Therefore, both
our aggregated and individual gradient estimates are an adapted processes on
the filtration. Furthermore, the iterates of our algorithm will have the
property:

$\mathbb{E}_{k}[w_{k}]=w_{k},$ (2.5)

where we denote the conditional expectation of a random variable with respect
to filtration as $\mathbb{E}_{k}[\cdot]:=\mathbb{E}[\cdot|\mathcal{F}_{k}]$.

#### Choice of aggregation function

For our convergence theory to hold, the aggregation function Agg must satisfy
the following assumption, from [3].

######  Assumption 2.2 ($\alpha$-Byzantine Resilience).

Let $A_{k}:=\text{\sc
Agg}\left((\tilde{g}_{1})_{k},(\tilde{g}_{2})_{k},...,(\tilde{g}_{m})_{k}\right)$.
Then there exists a constant $\alpha\in[0,\pi/2)$ such that for all $k$ we
have

  1. 1.

$\langle\mathbb{E}_{k}[A_{k}],\nabla
F(w_{k})\rangle\geq(1-\sin(\alpha))\|\nabla F(w_{k})\|^{2}$, and

  2. 2.

For $r=2,3,4$, $\mathbb{E}_{k}[\|A_{k}\|^{r}]$ bounded above by a linear
combination of terms:
$\mathbb{E}_{k}[\|G(w_{k})\|^{r_{1}}]\cdot\mathbb{E}_{k}[\|G(w_{k})\|^{r_{2}}]\cdot...\cdot\mathbb{E}_{k}[\|G(w_{k})\|^{r_{n}}]$
with $r_{1}+r_{2}+...+r_{n}=r$.

######  Remark 2.3.

We note that while [3] requires $r=2,3,4$ in Assumption 2.2(2), our
convergence result only requires $r=2$. In fact, our result requires only the
weaker condition

$\displaystyle\mathbb{E}_{k}[\|A_{k}\|^{2}]\leq
E\mathbb{E}_{k}[\|G(w_{k})\|^{2}],$ (2.6)

for some constant $E$. The $r=2$ case of Assumption 2.2(2) implies (2.6) via

$\displaystyle\mathbb{E}_{k}[\|A_{k}\|^{2}]\leq
C_{1}\mathbb{E}_{k}[\|G(w_{k})\|^{2}]+C_{2}\mathbb{E}_{k}[\|G(w_{k})\|]^{2}\leq(C_{1}+C_{2})\mathbb{E}_{k}[\|G(w_{k})\|^{2}],$
(2.7)

for some constants $C_{1},C_{2}>0$, and where the second inequality follows
from Jensen’s inequality for conditional expectations.

The works [3, 28, 14] give multiple examples of suitable functions Agg which
satisfy Assumption 2.2, where $\alpha$ typically depends on Agg, the number of
clients $m$ and the number of corrupted clients $q$. Specifically, the Agg
functions proposed in these works are:

  * •

Krum [3], which returns the vector from
$\\{(\tilde{g}_{1})_{k},(\tilde{g}_{2})_{k},...,(\tilde{g}_{m})_{k}\\}$ that
minimizes the distance between it and its nearest neighbours;

  * •

Variations of the median [28], including the marginal (i.e. component-wise)
median, the geometric median

$\displaystyle\text{\sc
Agg}\left((\tilde{g}_{1})_{k},(\tilde{g}_{2})_{k},...,(\tilde{g}_{m})_{k}\right)=\operatorname*{arg\,min}_{g\in\mathbb{R}^{d}}\sum_{i=1}^{m}\|g-(\tilde{g}_{i})_{k}\|,$
(2.8)

and the ‘mean-around-median’, the (component-wise) mean of the closest vectors
to the marginal median;

  * •

Bulyan [14], which uses an existing Agg function such as the above to generate
a set of candidate gradients and then apply a ‘mean-around-median’ aggregation
to that set.

###  2.3 Existing Convergence Theory

We now describe the underlying assumptions and state the existing convergence
theory for BRSGD (Algorithm 1) as given in [3]. The requirements on the
objective (2.1) are based on [4]:

######  Assumption 2.4.

The objective function $F$ is $C^{3}$, bounded below, and there exist
constants $D,\epsilon\geq 0$ and $0\leq\beta<\frac{\pi}{2}$ such that, for all
$w\in\mathbb{R}^{d}$ with $\|w\|^{2}\geq D$, we have:

$\|\nabla F(w)\|\geq\epsilon,\quad\text{and}\quad\frac{\langle
w,\nabla{F}(w)\rangle}{\|w\|\cdot\|\nabla{F}(w)\|}\geq\cos(\beta).$ (2.9)

Next, the requirement on the stochastic gradients is given by the following
two assumptions.

######  Assumption 2.5.

The gradient estimator $G(w_{k})$ is unbiased,
$\mathbb{E}_{k}[G(w_{k})]=\nabla F(w_{k})$, and for all $r\in\\{2,3,4\\}$,
there exist non-negative constants $A_{r}$ and $B_{r}$ such that
$\mathbb{E}_{k}[\|G(w_{k})\|^{r}]\leq A_{r}+B_{r}\|w_{k}\|^{r}$.

We are now able to state the main convergence result from [3].

######  Theorem 2.6 (Proposition 2, [3]).

Suppose that Assumptions 2.2, 2.4 and 2.5 hold, with $\alpha+\beta<\pi/2$
(with $\alpha$ from Assumption 2.2 and $\beta$ from Assumption 2.4), and

$\displaystyle\eta(m,q)\sqrt{\mathbb{E}[\|G(w,\zeta)-\nabla
F(w)\|^{2}]}\leq\sin(\alpha)\|\nabla F(w)\|,$ (2.10)

where $m>2q+2$ and

$\displaystyle\eta(m,q):=\sqrt{2\left(m-q+\frac{q(m-q-2)+q^{2}(m-q-1)}{m-2q-2}\right)}.$
(2.11)

If we run Algorithm 1 with learning rates satisfying
$\sum_{k=0}^{\infty}\alpha_{k}=\infty$ and
$\sum_{k=0}^{\infty}\alpha_{k}^{2}<\infty$. Then $\lim_{k\to\infty}\|\nabla
F(w_{k})\|=0$ almost surely.

We conclude by noting the technical condition $\alpha+\beta<\pi/2$, relating
the errors in the stochastic gradients and the smoothness of the objective. We
do not need a condition like this in our analysis. The condition (2.10)
relates the stochastic gradients to the aggregation function (provided there
are not too many adversaries). Although our analysis does not require this
condition explicitly, similar conditions are required to show Byzantine
resilience of aggregation functions such as Krum [3] and the geometric median
[28].

##  3 New Convergence Analysis

We now present our new, simplified analysis of BRSGD. Compared to Theorem 2.6,
our result uses simpler and more common assumptions on both the objective $F$
and the stochastic gradient estimator $G(w,\zeta)$, and a specific choice of
learning rate. As a result, the conclusion is weaker: we get convergence to
stationary points in expectation rather than almost surely. It has the same
requirements on the aggregating function Agg.

In particular, we note that Theorem 2.6 requires (2.9), essentially that $F$
is ‘convex enough’ outside a certain bounded region. This has the downside,
for example, of excluding the model space of neural networks with soft-max
activation functions, a common model space in distributed learning, as the
activation function has flat asymptotes [4].

######  Assumption 3.1.

Each term in the objective function $F$ is $L$-smooth (i.e. continuously
differentiable and $\nabla F$ is $L$-Lipschitz continuous) and bounded below
by some $F_{\text{low}}$.

The key implication of $F$ being $L$-smooth is the upper bound

$F(y)\leq F(x)+\langle\nabla
F(x),y-x\rangle+\frac{L}{2}\|y-x\|^{2},\qquad\forall x,y\in\mathbb{R}^{d}.$
(3.1)

For our stochastic gradient estimator, we will use a version of the expected
smoothness property [17, Assumption 3.2]. We note that [17] shows that
variants of SGD including minibatching, importance sampling, gradient
combinations and their combinations all satisfy expected smoothness.

######  Assumption 3.2.

(Expected Smoothness) For all $k$, the gradient estimator $G(w_{k})$ is
unbiased:

$\mathbb{E}_{k}[G(w_{k})]=\nabla F(w_{k}),$ (3.2)

and there exist non-negative constants $A$, $B$ and $C$ (independent of $k$),
such that:

$\mathbb{E}_{k}[\|G(w_{k})\|^{2}]\leq 2A(F(w_{k})-F_{\text{low}})+B\|\nabla
F(w_{k})\|^{2}+C.$ (3.3)

To prove our result, we will need the below technical lemma, a generalization
of [17, Lemma 2], which corresponds to the case of $a_{k}\equiv a$ for all
$k$.

######  Lemma 3.3.

Let $\\{r_{k}\\}_{n\in\mathbb{N}}$, $\\{d_{k}\\}_{n\in\mathbb{N}}$ be
positive-valued sequences, $\\{a_{k}\\}_{n\in\mathbb{N}\cup\\{-1\\}}$ be a
non-increasing, positive-valued sequence and $L$, $A$ and $C$ be positive
constants such that, for all $k\in\mathbb{N}$,

$\frac{a_{k}}{2}r_{k}\leq(1+a_{k}^{2}LA)d_{k}-d_{k+1}+\frac{LCa^{2}_{k}}{2}.$
(3.4)

Then, the following identity holds:

$\min_{0\leq k\leq
K-1}r_{k}\leq\frac{2d_{0}}{a_{-1}KW_{K-1}}+\frac{LC}{KW_{K-1}}\sum^{K-1}_{k=0}a_{k}W_{k},$
(3.5)

where $W_{k}$ is a weighting sequence defined by $W_{-1}=1$ and
$W_{k}=W_{k-1}\frac{a_{k}}{a_{k-1}(1+LAa_{k}^{2})}$ for $k\geq 0$.

###### Proof.

We begin by taking (3.4) and multiplying through by $\frac{W_{k}}{a_{k}}$ for
each $k\in\mathbb{N}$. Thus,

$\frac{1}{2}r_{k}W_{k}\leq(1+a_{k}^{2}LA)d_{k}\frac{W_{k}}{a_{k}}-d_{k+1}\frac{W_{k}}{a_{k}}+\frac{LCa_{k}W_{k}}{2}.$
(3.6)

Noting that $\frac{W_{k}(1+a_{k}^{2}LA)}{a_{k}}=\frac{W_{k-1}}{a_{k-1}}$, we
simplify:

$\frac{1}{2}r_{k}W_{k}\leq
d_{k}\frac{W_{k-1}}{a_{k-1}}-d_{k+1}\frac{W_{k}}{a_{k}}+\frac{LCa_{k}W_{k}}{2}.$
(3.7)

This allows us to apply a telescoping sum, adding together the first $K-1$
inequalities we receive:

$\frac{1}{2}\sum^{K-1}_{k=0}r_{k}W_{k}\leq\frac{d_{0}}{a_{-1}}-\frac{W_{K-1}d_{K}}{a_{K-1}}+\frac{LC}{2}\sum^{K-1}_{k=0}a_{k}W_{k}.$
(3.8)

Let $\hat{W}:=\sum^{K-1}_{k=0}W_{k}$ and divide through by $\hat{W}$ on both
sides:

$\displaystyle\frac{1}{2\hat{W}}\sum^{K-1}_{k=0}r_{k}W_{k}$
$\displaystyle\leq\frac{d_{0}}{a_{-1}\hat{W}}-\frac{W_{K-1}d_{K}}{a_{K-1}\hat{W}}+\frac{LC}{2\hat{W}}\sum^{K-1}_{k=0}a_{k}W_{k},$
(3.9)
$\displaystyle\frac{1}{2\hat{W}}\sum^{K-1}_{k=0}r_{k}W_{k}+\frac{W_{K-1}d_{K}}{a_{K-1}\hat{W}}$
$\displaystyle\leq\frac{d_{0}}{a_{-1}\hat{W}}+\frac{LC}{2\hat{W}}\sum^{K-1}_{k=0}a_{k}W_{k}.$
(3.10)

To simplify further we note:

$\frac{1}{2}\min_{0\leq k\leq K-1}r_{k}=\frac{1}{2\hat{W}}\left(\min_{0\leq
k\leq
K-1}r_{k}\right)\sum^{K-1}_{k=0}W_{k}\leq\frac{1}{2\hat{W}}\sum^{K-1}_{k=0}r_{k}W_{k}+\frac{w_{K-1}d_{K}}{a_{K-1}\hat{W}},$
(3.11)

where (3.11) holds as $W_{K-1}$, $d_{K}$, $a_{K-1}$ and $\hat{W}$ are all
strictly positive. Hence:

$\frac{1}{2}\min_{0\leq k\leq
K-1}r_{k}\leq\frac{d_{0}}{a_{-1}\hat{W}}+\frac{LC}{2\hat{W}}\sum^{K-1}_{k=0}a_{k}W_{k}.$
(3.12)

We now note $\frac{a_{k}}{a_{k-1}}\leq 1$, as
$\\{a_{k}\\}_{n\in\mathbb{N}\cup\\{-1\\}}$ is non-increasing. Furthermore,
$\frac{1}{1+LAa_{k}^{2}}\leq 1$, as $L,A\ \text{and}\ a_{k}>0$. Therefore:

$W_{k}=W_{k-1}\frac{a_{k}}{a_{k-1}}\frac{1}{(1+LAa_{k}^{2})}\leq W_{k-1},$
(3.13)

and hence, $\\{W_{n}\\}_{\\{n\in\mathbb{N}\cup\\{-1\\}\\}}$ is non-increasing.
Using this, we note:

$\frac{1}{\hat{W}}=\frac{1}{\sum^{K-1}_{k=0}W_{k}}\leq\frac{1}{\sum^{K-1}_{k=0}\min_{0\leq
k\leq K-1}W_{k}}=\frac{1}{KW_{K-1}}.$ (3.14)

Substituting (3.14) into the right-hand side of (3.12) and multiplying by 2
provides our result. ∎

We are now ready to prove our main result.

######  Theorem 3.4.

Suppose that Assumptions 2.2, 3.1 and 3.2 hold. If we run Algorithm 1 with
learning rate sequence that satisfies: $\\{\alpha_{k}\\}_{k\in\mathbb{N}}$ is
non-increasing, $\alpha_{0}\leq\frac{1-\sin(\alpha)}{LB^{\prime}}$,
$\sum_{k=0}^{\infty}\alpha_{k}^{2}<\infty$, and
$\lim_{k\to\infty}\frac{1}{k\alpha_{k-1}}=0$ (where $B^{\prime}=B{E}$; $L$,
$B$ and $E$ are defined in Assumptions 3.1 and 3.2, and (2.6)—a consequence of
Assumption 2.2(2)—respectively, and $\alpha$ comes from Assumption 2.2(1)),
then

$\lim_{K\to\infty}\left(\min_{0\leq k\leq K-1}\mathbb{E}[\|\nabla
F(w_{k})\|]\right)=0.$ (3.15)

###### Proof.

We begin by applying (3.1) and simplifying using
$w_{k+1}=w_{k}-\alpha_{k}A_{k}$:

$\displaystyle F(w_{k+1})$ $\displaystyle\leq F(w_{k})+\langle\nabla
F(w_{k}),w_{k+1}-w_{k}\rangle+\frac{L}{2}\|w_{k+1}-w_{k}\|^{2},$ (3.16)
$\displaystyle=F(w_{k})-\alpha_{k}\langle\nabla
F(w_{k}),A_{k}\rangle+\frac{L\alpha_{k}^{2}}{2}\|A_{k}\|^{2}.$ (3.17)

We then take the expectation of the above conditioned on $\mathcal{F}_{k}$
from our filtration:

$\displaystyle\mathbb{E}_{k}[F(w_{k+1})]\leq F(w_{k})-\alpha_{k}\langle\nabla
F(w_{k}),\mathbb{E}_{k}[A_{k}]\rangle+\frac{L\alpha_{k}^{2}}{2}\mathbb{E}_{k}[\|A_{k}\|^{2}].$
(3.18)

To simplify, we apply Assumption 2.2(2) to get:

$(1-\sin(\alpha))\|\nabla F(w_{k})\|^{2}\leq\langle\nabla
F(w_{k}),\mathbb{E}_{k}[A_{k}]\rangle,$ (3.19)

and, for some constant ${E}$,

$\mathbb{E}_{k}[\|A_{k}\|^{2}]\leq{E}\mathbb{E}_{k}[\|G(w_{k})\|^{2}].$ (3.20)

Applying (3.19) and (3.20), and subtracting $F_{\text{low}}$ from both sides,
we simplify:

$\displaystyle\mathbb{E}_{k}[F(w_{k+1})]-F_{\text{low}}$ $\displaystyle\leq
F(w_{k})-F_{\text{low}}-\alpha_{k}\langle\nabla
F(w_{k}),\mathbb{E}_{k}[A_{k}]\rangle+\frac{L\alpha_{k}^{2}}{2}\mathbb{E}_{k}[\|A_{k}\|^{2}],$
(3.21) $\displaystyle\leq
F(w_{k})-F_{\text{low}}-\alpha_{k}(1-\sin(\alpha))\|\nabla F(w_{k})\|^{2}$
(3.22)
$\displaystyle\quad+\frac{L\alpha_{k}^{2}}{2}{E}\mathbb{E}_{k}[\|G(w_{k})\|^{2}].$
(3.23)

We now simplify using Assumption 3.2:

${E}\mathbb{E}_{k}[\|G(w_{k})\|^{2}]\leq{E}\left(2A(F(w_{k})-F_{\text{low}})+B\|\nabla
F(w_{k})\|^{2}+C\right).$ (3.24)

Collecting terms, we will rewrite the upper bound for our final term as:

${E}\mathbb{E}_{k}[\|G(w_{k})\|^{2}\leq
2A^{\prime}(F(w_{k})-F_{\text{low}})+B^{\prime}\|\nabla
F(w_{k})\|^{2}+C^{\prime}.$ (3.25)

Thus:

$\displaystyle\mathbb{E}_{k}[F(w_{k+1})]-F_{\text{low}}$
$\displaystyle\leq(1+L\alpha_{k}^{2}A^{\prime})(F(w_{k})-F_{\text{low}})$
(3.26)
$\displaystyle\quad-\left(\alpha_{k}\left(1-\sin(\alpha)\right)-\frac{L\alpha_{k}^{2}B^{\prime}}{2}\right)\|\nabla
F(w_{k})\|^{2}+\frac{L\alpha_{k}^{2}C^{\prime}}{2}.$ (3.27)

Taking total expectations and using the Tower Property:

$\displaystyle\mathbb{E}[F(w_{k+1})-F_{\text{low}}]$
$\displaystyle\leq(1+L\alpha_{k}^{2}A^{\prime})\mathbb{E}[(F(w_{k})-F_{\text{low}})]$
(3.28)
$\displaystyle\quad-\left(\alpha_{k}\left(1-\sin(\alpha)\right)-\frac{L\alpha_{k}^{2}B^{\prime}}{2}\right)\mathbb{E}[\|\nabla
F(w_{k})\|^{2}]+\frac{L\alpha_{k}^{2}C^{\prime}}{2}.$ (3.29)

Defining $\delta_{k}:=\mathbb{E}[F(w_{k})-F_{\text{low}}]$, (3.29) becomes:

$\alpha_{k}\left(1-\sin(\alpha)-\frac{LB^{\prime}\alpha_{k}}{2}\right)\mathbb{E}[\|\nabla
F(w_{k})\|^{2}]\leq(1+L\alpha_{k}^{2}A^{\prime})\delta_{k}-\delta_{k+1}+\frac{L\alpha_{k}^{2}C^{\prime}}{2}.$
(3.30)

Furthermore, our requirements on the learning rate sequence $\alpha_{k}$
guarantee
$1-\sin(\alpha)-\frac{LB^{\prime}\alpha_{k}}{2}\geq\frac{1-\sin(\alpha)}{2}$,
hence we define $r_{k}:=(1-\sin(\alpha))\mathbb{E}[\|\nabla F(w_{k})\|^{2}]$
and get:

$\frac{\alpha_{k}}{2}r_{k}\leq(1+L\alpha_{k}^{2}A^{\prime})\delta_{k}-\delta_{k+1}+\frac{L\alpha_{k}^{2}C^{\prime}}{2}.$
(3.31)

We now apply Lemma 3.3 to our problem using the following weighting sequence:

$W_{k}:=\begin{cases}1,&\text{if}\ k=-1,\\\
W_{k-1}\frac{\alpha_{k}}{\alpha_{k-1}(1+LA^{\prime}\alpha_{k}^{2})},&\text{otherwise.}\end{cases}$
(3.32)

Hence:

$\min_{0\leq k\leq
K-1}r_{k}\leq\frac{2\delta_{0}}{\alpha_{-1}KW_{K-1}}+\frac{LC^{\prime}}{KW_{K-1}}\sum^{K-1}_{k=0}\alpha_{k}W_{k},$
(3.33)

where we define $\alpha_{-1}:=\alpha_{0}$ for convenience.

We now show $\lim_{K\to\infty}\left(\min_{0\leq k\leq K-1}r_{k}\right)=0$. To
do this, we return to the definition of our weighting sequence and note:

$W_{k}=\frac{\alpha_{k}}{\alpha_{-1}}\prod^{k}_{j=0}\frac{1}{1+LA^{\prime}\alpha_{j}^{2}}.$
(3.34)

Hence:

$\displaystyle\min_{0\leq k\leq K-1}r_{k}$
$\displaystyle\leq\frac{2\delta_{0}}{\alpha_{-1}}\left(\frac{\alpha_{-1}}{K\alpha_{K-1}}\prod^{K-1}_{k=0}(1+LA^{\prime}\alpha_{k}^{2})\right)$
$\displaystyle\quad+LC^{\prime}\left(\frac{\alpha_{-1}}{K\alpha_{K-1}}\prod^{K-1}_{k=0}(1+LA^{\prime}\alpha_{k}^{2})\right)\sum^{K-1}_{k=0}\left(\frac{\alpha_{k}^{2}}{\alpha_{-1}}\prod^{k}_{j=0}\frac{1}{1+LA^{\prime}\alpha_{j}^{2}}\right).$
(3.35)

In order to simplify, we will bound a pair of infinite products and a
summation. We will first show that:

$\prod^{\infty}_{k=0}(1+LA^{\prime}\alpha_{k}^{2})<\infty.$ (3.36)

Recall that, for a sequence of positive real numbers
$\\{y_{n}\\}_{n\in\mathbb{N}}$, $\prod^{\infty}_{k=0}y_{k}$ converges if and
only if $\sum^{\infty}_{k=0}\log(y_{k})$ converges. From our specification of
$\alpha_{k}$, we know $\sum^{\infty}_{k=0}\alpha_{k}^{2}<\infty$. Let:

$Q:=\sum^{\infty}_{k=0}\alpha_{k}^{2}.$ (3.37)

When $y>-1$, $\log(1+y)\leq y$. Hence:

$\displaystyle\sum^{\infty}_{k=0}\log(1+LA^{\prime}\alpha_{k}^{2})$
$\displaystyle\leq\sum^{\infty}_{k=0}LA^{\prime}\alpha_{k}^{2}\leq
LA^{\prime}Q.$ (3.38)

Therefore, $P:=\prod^{\infty}_{k=0}(1+LA^{\prime}\alpha_{k}^{2})<\infty$.
Secondly, we note that, for all $k\in\mathbb{N}$:

$\prod^{k}_{j=0}\frac{1}{1+LA^{\prime}\alpha_{k}^{2}}\leq 1,$ (3.39)

as, $LA^{\prime}\alpha_{k}^{2}>0$, for all $k\in\mathbb{N}$. This, in turn,
allows us to simplify another summation. Specifically:

$\displaystyle\sum^{\infty}_{k=0}\left(\frac{\alpha_{k}^{2}}{\alpha_{-1}}\prod^{k}_{j=0}\frac{1}{1+LA^{\prime}\alpha_{j}^{2}}\right)$
$\displaystyle\leq\frac{1}{\alpha_{-1}}\sum^{\infty}_{k=0}\alpha_{k}^{2}=\frac{Q}{\alpha_{-1}}.$
(3.40)

We now take the limit of both sides of (3.35) and recover our result.

$\displaystyle\lim_{K\to\infty}$ $\displaystyle\left(\min_{0\leq k\leq
K-1}r_{k}\right)$
$\displaystyle\leq\lim_{K\to\infty}\left(\frac{2\delta_{0}}{\alpha_{-1}}\left(\frac{\alpha_{-1}}{K\alpha_{K-1}}\prod^{K-1}_{k=0}(1+LA^{\prime}\alpha_{k}^{2})\right)\right)$
(3.41)
$\displaystyle\quad+\lim_{K\to\infty}\left(LC^{\prime}\left(\frac{\alpha_{-1}}{K\alpha_{K-1}}\prod^{K-1}_{k=0}(1+LA^{\prime}\alpha_{k}^{2})\right)\sum^{K-1}_{k=0}\left(\frac{\alpha_{k}^{2}}{\alpha_{-1}}\prod^{k}_{j=0}\frac{1}{1+\alpha_{j}^{2}LA^{\prime}}\right)\right),$
(3.42)
$\displaystyle\leq{2\delta_{0}\left(\lim_{K\to\infty}\frac{1}{K\alpha_{K-1}}\right)\prod_{k=0}^{\infty}(1+LA^{\prime}\alpha_{k}^{2})}$
$\displaystyle\quad{+LC^{\prime}\alpha_{-1}\left(\lim_{K\to\infty}\frac{1}{K\alpha_{K-1}}\right)\left(\prod_{k=0}^{\infty}(1+LA^{\prime}\alpha_{k}^{2})\right)\left(\sum^{\infty}_{k=0}\left(\frac{\alpha_{k}^{2}}{\alpha_{-1}}\prod^{k}_{j=0}\frac{1}{1+LA^{\prime}\alpha_{j}^{2}}\right)\right)},$
(3.43)
$\displaystyle={(2\delta_{0}P+LC^{\prime}PQ)\lim_{K\to\infty}\frac{1}{K\alpha_{K-1}}},$
(3.44)

where $P$ is defined after (3.38). By assumption, we have
$\lim_{K\to\infty}\frac{1}{K\alpha_{K-1}}=0$, therefore:

$\lim_{K\to\infty}\left(\min_{0\leq k\leq
K-1}(1-\sin(\alpha))\mathbb{E}[\|\nabla F(w_{k})\|^{2}]\right)=0.$ (3.45)

Our result then follows from Jensen’s inequality, $\mathbb{E}[\|\nabla
F(w)\|]^{2}\leq\mathbb{E}[\|\nabla F(w)\|^{2}]$. ∎

We note that our assumptions on the learning rate sequence
$\\{\alpha_{k}\\}_{k}$ allows for sequences which decay as $\alpha_{k}\sim
k^{-p}$ for any $p\in(1/2,1)$.

###  3.1 Iterate Selection

The above result shows that there is a subsequence of iterates which converges
in expectation. We now give a probabilistic procedure to select a single
iterate with small expected gradient, inspired by the analysis in [18, Theorem
6.1]. In this context, we assume that Algorithm 1 has been run for $K$
iterations, and we randomly select an iterate from $w_{0},\ldots,w_{K-1}$
according to a specific probability distribution depending on the learning
rate sequence $\alpha_{k}$. However, compared to [18, Corollary 6.1], the
choice of $\alpha_{k}$ does not depend on $K$, and so Algorithm 1 can always
be continued from its previous endpoint if the desired accuracy is not
achieved.

This analysis requires only small modifications of Lemma 3.3 and Theorem 3.4,
which we present here.

######  Lemma 3.5.

Suppose the assumptions of Lemma 3.3 hold, including the definition of the
weighting sequence $W_{k}$. If, for any $K\geq 0$, we define the random
variable $R_{K}\in\\{0,\ldots,K-1\\}$ by

$\displaystyle\mathbb{P}(R_{K}=k):=\frac{W_{k}}{\sum^{K-1}_{i=0}W_{i}},\quad
k=0,...,K-1,$ (3.46)

then

$\mathbb{E}[r_{R_{K}}]\leq\frac{2d_{0}}{a_{-1}KW_{K-1}}+\frac{LC}{KW_{K-1}}\sum^{K-1}_{k=0}a_{k}W_{k}.$
(3.47)

###### Proof.

The proof of this result is identical to that of Lemma 3.3, except that (3.11)
is replaced by

$\displaystyle\frac{1}{2}\mathbb{E}[r_{R_{K}}]=\frac{1}{2\hat{W}}\sum^{K-1}_{k=0}r_{k}W_{k}\leq\frac{1}{2\hat{W}}\sum^{K-1}_{k=0}r_{k}W_{k}+\frac{w_{K-1}d_{K}}{a_{K-1}\hat{W}},$
(3.48)

from which we conclude

$\displaystyle\frac{1}{2}\mathbb{E}[r_{R_{K}}]\leq\frac{d_{0}}{a_{-1}\hat{W}}+\frac{LC}{2\hat{W}}\sum^{K-1}_{k=0}a_{k}W_{k},$
(3.49)

in place of (3.12). ∎

######  Corollary 3.6.

Suppose that the assumptions of Theorem 3.4 hold, and for any $K\geq 0$ we
define the random variable $R_{K}$ as per (3.46). Then

$\lim_{K\to\infty}\mathbb{E}[\|\nabla F(w_{R_{K}})\|]=0.$ (3.50)

###### Proof.

The proof of this result is identical to that of Theorem 3.4, but we replace
(3.33) with

$\displaystyle\mathbb{E}[r_{R_{K}}]\leq\frac{2\delta_{0}}{\alpha_{-1}KW_{K-1}}+\frac{LC^{\prime}}{KW_{K-1}}\sum^{K-1}_{k=0}\alpha_{k}W_{k},$
(3.51)

which follows from Lemma 3.5. Hence instead of (3.44) we reach

$\displaystyle\lim_{K\to\infty}\mathbb{E}[r_{R_{K}}]$
$\displaystyle\leq(2\delta_{0}P+LC^{\prime}PQ)\lim_{K\to\infty}\frac{1}{K\alpha_{K-1}}=0,$
(3.52)

from which the result follows by Jensen’s inequality,
$(1-\sin(\alpha))\mathbb{E}[\|\nabla F(w_{R_{K}})\|]^{2}\leq r_{R_{K}}$. ∎

##  4 Convergence Rate

The previous section gives a convergence analysis for Algorithm 1 under
general assumptions on the decreasing learning rate sequence $\alpha_{k}$. We
now specialize these results to give a convergence rate for the case
$\alpha_{k}\sim k^{-p}$ for $p\in(1/2,1)$.

######  Corollary 4.1.

Suppose the assumptions of Theorem 3.4 hold, and the learning rate sequence is
given by

$\displaystyle\alpha_{k}=\frac{1-\sin(\alpha)}{LB^{\prime}(k+1)^{p}},\qquad
k=0,1,2,\ldots,$ (4.1)

for some $p\in(1/2,1)$. Then

$\displaystyle\min_{0\leq k\leq K-1}\mathbb{E}[\|\nabla F(w_{k})\|]$
$\displaystyle\leq\left(\frac{e^{LA^{\prime}Q_{K}}\left(2\delta_{0}+LC^{\prime}Q_{K}\right)}{(1-\sin(\alpha))K\alpha_{K-1}}\right)^{1/2},$
(4.2)

where $Q_{K}:=\sum_{k=0}^{K-1}\alpha_{k}^{2}$, $A^{\prime}:=AE$,
$C^{\prime}:=CE$ (with $A$ and $C$ from Assumption 3.2 and $E$ from (2.6)),
and $\delta_{0}:=F(w_{0})-F_{\text{low}}$.

In particular, this means that

$\displaystyle\min_{0\leq k\leq K-1}\mathbb{E}[\|\nabla
F(w_{k})\|]=\mathcal{O}\left(e^{A^{\prime}/(2L(B^{\prime})^{2})}\left(2\delta_{0}+\frac{C^{\prime}}{L(B^{\prime})^{2}}\right)^{1/2}(LB^{\prime})^{1/2}\frac{1}{K^{(1-p)/2}}\right),$
(4.3)

as $K\to\infty$ (considering the dependency in terms of $K$, $\delta_{0}$,
$A^{\prime}$, $B^{\prime}$, $C^{\prime}$, and $L$).

###### Proof.

We continue from (3.35) in the proof of Theorem 3.4, where after applying
(3.39) we have

$\displaystyle\min_{0\leq k\leq K-1}r_{k}$
$\displaystyle\leq\frac{2\delta_{0}}{K\alpha_{K-1}}\prod^{K-1}_{k=0}(1+LA^{\prime}\alpha_{k}^{2})+\left(\frac{LC^{\prime}}{K\alpha_{K-1}}\prod^{K-1}_{k=0}(1+LA^{\prime}\alpha_{k}^{2})\right)\sum^{K-1}_{k=0}\alpha_{k}^{2},$
(4.4)

where $r_{k}:=(1-\sin(\alpha))\mathbb{E}[\|\nabla F(w_{k})\|^{2}]$. By the
same reasoning leading to (3.38) we get

$\displaystyle\sum_{k=0}^{K-1}\log(1+LA^{\prime}\alpha_{k}^{2})\leq
LA^{\prime}Q_{K},$ (4.5)

and so $\prod^{K-1}_{k=0}(1+LA^{\prime}\alpha_{k}^{2})\leq
e^{LA^{\prime}Q_{K}}$, giving

$\displaystyle\min_{0\leq k\leq K-1}r_{k}$
$\displaystyle\leq\frac{e^{LA^{\prime}Q_{K}}\left(2\delta_{0}+LC^{\prime}Q_{K}\right)}{K\alpha_{K-1}}.$
(4.6)

Jensen’s inequality gives $\mathbb{E}[\|\nabla
F(w)\|]^{2}\leq\mathbb{E}[\|\nabla F(w)\|^{2}]$, and we recover (4.2).

Now since $\alpha_{k}=\alpha_{0}(k+1)^{-p}$ we have

$\displaystyle
Q_{K}\leq\alpha_{0}^{2}+\int_{1}^{K-1}\alpha_{0}^{2}k^{-2p}dk\leq\alpha_{0}^{2}+\int_{1}^{K}\alpha_{0}^{2}k^{-2p}dk=\frac{\alpha_{0}^{2}}{2p-1}\left(2p-2+\frac{1}{K^{2p-1}}\right).$
(4.7)

So for $K$ large, we have
$Q_{K}=\mathcal{O}(\alpha_{0}^{2})=\mathcal{O}\left(\frac{1}{L^{2}(B^{\prime})^{2}}\right)$
and $K\alpha_{K-1}=\mathcal{O}\left(\frac{K^{1-p}}{LB^{\prime}}\right)$, which
gives second result. ∎

######  Remark 4.2.

Identical results to Corollary 4.1 hold when considering $\mathbb{E}[\|\nabla
F(w_{R_{K}})\|]$ instead of $\min_{k\leq K}\mathbb{E}[\|\nabla F(w_{k})\|]$,
following the reasoning in Section 3.1.

Our convergence rate result Corollary 4.1 essentially gives $\min_{k\leq
K}\mathbb{E}[\|\nabla
F(w_{k})\|]=\mathcal{O}\left(\frac{1}{K^{(1-p)/2}}\right)$. In the best case,
$p\to 1/2$, this convergence rate approaches $\mathcal{O}(K^{-1/4})$, or
equivalently requiring $K=\mathcal{O}(\epsilon^{-4})$ to achieve optimality
level $\mathbb{E}[\|\nabla F(w_{k})\|]\leq\epsilon$ (or alternatively
$\mathbb{E}[\|\nabla F(w_{R_{K}})\|]\leq\epsilon$). This matches the standard
worst-case complexity of stochastic gradient descent for nonconvex functions
[13].

##  5 Conclusion

Having algorithms for distributed learning in the presence of Byzantine
adversaries is an important part of improving the utility of distributed
learning. In this work we presented a simplified analysis of Byzantine
resilient SGD (BRSGD) as developed in [3], proving convergence in expectation
and corresponding convergence rates under more realistic assumptions on the
objective function and the (non-corrupted) stochastic gradient estimators.
Since BRSGD is a generic algorithm, allowing the use of any aggregation
function satisfying Assumption 2.2, our analysis applies to all the specific
choices given in [3, 28, 14]. Directions for future work include extending our
analysis to more flexible learning rate regimes and other Byzantine resilient
learning algorithms not based on the framework from [3], such as those in [30,
31].

## References

  * [1] A. N. Bhagoji, S. Chakraborty, P. Mittal, and S. Calo, Analyzing federated learning through an adversarial lens, arXiv preprint arXiv:1811.12470, (2019).
  * [2] B. Biggio, B. Nelson, and P. Laskov, Poisoning attacks against support vector machines, in Proceedings of the 29th International Conference on Machine Learning, 2012.
  * [3] P. Blanchard, E. M. El Mhamdi, R. Guerraoui, and J. Stainer, Machine learning with adversaries: Byzantine tolerant gradient descent, in Advances in Neural Information Processing Systems, I. Guyon, U. V. Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett, eds., vol. 30, Curran Associates, Inc., 2017.
  * [4] L. Bottou, On-line learning and stochastic approximations, in On-Line Learning in Neural Networks, Cambridge University Press, New York, 1999, pp. 9–42.
  * [5] L. Bottou, F. E. Curtis, and J. Nocedal, Optimization methods for large-scale machine learning, SIAM Review, 60 (2018), pp. 223–311.
  * [6] J. Chen, R. Monga, S. Bengio, and R. Jozefowicz, Revisiting distributed synchronous SGD, in International Conference on Learning Representations Workshop Track, 2016.
  * [7] X. Chen, C. Liu, B. Li, K. Lu, and D. Song, Targeted backdoor attacks on deep learning systems using data poisoning, arXiv preprint arXiv:1712.05526, (2017).
  * [8] Y. Chen, L. Su, and J. Xu, Distributed statistical machine learning in adversarial settings: Byzantine gradient descent, Proceedings of the ACM on Measurement and Analysis of Computing Systems, 1 (2017), pp. 1–25.
  * [9] C.-t. Chu, S. Kim, Y.-a. Lin, Y. Yu, G. Bradski, K. Olukotun, and A. Ng, Map-reduce for machine learning on multicore, in Advances in Neural Information Processing Systems, B. Schölkopf, J. Platt, and T. Hoffman, eds., vol. 19, MIT Press, 2006.
  * [10] L. Dai, B. Diao, C. Li, and Y. Xu, A distributed SGD algorithm with global sketching for deep learning training acceleration, arXiv preprint arXiv:2108.06004, (2021).
  * [11] D. Data and S. Diggavi, Byzantine-resilient SGD in high dimensions on heterogeneous data, arXiv preprint arXiv:2005.07866, (2020).
  * [12] D. Data and S. Diggavi, Byzantine-resilient high-dimensional SGD with local iterations on heterogeneous data, in Proceedings of the 38th International Conference on Machine Learning, M. Meila and T. Zhang, eds., vol. 139 of Proceedings of Machine Learning Research, PMLR, 18–24 Jul 2021, pp. 2478–2488.
  * [13] Y. Drori and O. Shamir, The complexity of finding stationary points with stochastic gradient descent, in Proceedings of the 37th International Conference on Machine Learning, H. D. III and A. Singh, eds., vol. 119 of Proceedings of Machine Learning Research, PMLR, 13–18 Jul 2020, pp. 2658–2667.
  * [14] E. M. El Mhamdi, R. Guerraoui, and S. Rouault, The hidden vulnerability of distributed learning in Byzantium, in Proceedings of the 35th International Conference on Machine Learning, J. Dy and A. Krause, eds., vol. 80 of Proceedings of Machine Learning Research, PMLR, 10–15 Jul 2018, pp. 3521–3530.
  * [15] Z. Jia, M. Zaharia, and A. Aiken, Beyond data and model parallelism for deep neural networks., in Proceedings of Machine Learning and Systems, A. Talwalkar, V. Smith, and M. Zaharia, eds., vol. 1, 2019, pp. 1–13.
  * [16] P. Kairouz, H. B. McMahan, B. Avent, A. Bellet, M. Bennis, A. N. Bhagoji, K. Bonawitz, Z. Charles, G. Cormode, R. Cummings, R. G. L. D’Oliveira, H. Eichner, S. E. Rouayheb, D. Evans, J. Gardner, Z. Garrett, A. Gascón, B. Ghazi, P. B. Gibbons, M. Gruteser, Z. Harchaoui, C. He, L. He, Z. Huo, B. Hutchinson, J. Hsu, M. Jaggi, T. Javidi, G. Joshi, M. Khodak, J. Konečný, A. Korolova, F. Koushanfar, S. Koyejo, T. Lepoint, Y. Liu, P. Mittal, M. Mohri, R. Nock, A. Özgür, R. Pagh, M. Raykova, H. Qi, D. Ramage, R. Raskar, D. Song, W. Song, S. U. Stich, Z. Sun, A. T. Suresh, F. Tramèr, P. Vepakomma, J. Wang, L. Xiong, Z. Xu, Q. Yang, F. X. Yu, H. Yu, and S. Zhao, Advances and open problems in federated learning, arXiv preprint arXiv:1912.04977, (2021).
  * [17] A. Khaled and P. Richtárik, Better theory for SGD in the nonconvex world, arXiv preprint arXiv:2002.03329, (2020).
  * [18] G. Lan, Lectures on optimization methods for machine learning.  https://cpb-us-w2.wpmucdn.com/sites.gatech.edu/dist/f/330/files/2019/08/LectureOPTML.pdf, 2019\.
  * [19] Z. Li and P. Richtárik, A unified analysis of stochastic gradient methods for nonconvex federated optimization, arXiv preprint arXiv:2006.07013, (2020).
  * [20] Y. Lin, S. Han, H. Mao, Y. Wang, and W. Dally, Deep gradient compression: Reducing the communication bandwidth for distributed training, 2018\.
  * [21] C. Paquette and K. Scheinberg, A stochastic line search method with expected complexity analysis, SIAM Journal on Optimization, 30 (2020), pp. 349–376.
  * [22] K. Pillutla, S. M. Kakade, and Z. Harchaoui, Robust aggregation for federated learning, arXiv preprint arXiv:1912.13445, (2019).
  * [23] J. Regatti, G. Tendolkar, Y. Zhou, A. Gupta, and Y. Liang, Distributed SGD generalizes well under asynchrony, in 2019 57th Annual Allerton Conference on Communication, Control, and Computing (Allerton), IEEE Press, 2019, p. 863–870.
  * [24] O. Sebbouh, R. M. Gower, and A. Defazio, Almost sure convergence rates for stochastic gradient descent and stochastic heavy ball, arXiv preprint arXiv:2006.07867, (2021).
  * [25] L. Su and J. Xu, Securing distributed gradient descent in high dimensional statistical learning, arXiv preprint arXiv:1804.10140, (2019).
  * [26] C. H. Teo, S. Vishwanthan, A. J. Smola, and Q. V. Le, Bundle methods for regularized risk minimization, Journal of Machine Learning Research, 11 (2010), pp. 311–365.
  * [27] J. Wang, Z. Charles, Z. Xu, G. Joshi, H. B. McMahan, B. A. y Arcas, M. Al-Shedivat, G. Andrew, S. Avestimehr, K. Daly, D. Data, S. Diggavi, H. Eichner, A. Gadhikar, Z. Garrett, A. M. Girgis, F. Hanzely, A. Hard, C. He, S. Horvath, Z. Huo, A. Ingerman, M. Jaggi, T. Javidi, P. Kairouz, S. Kale, S. P. Karimireddy, J. Konecny, S. Koyejo, T. Li, L. Liu, M. Mohri, H. Qi, S. J. Reddi, P. Richtarik, K. Singhal, V. Smith, M. Soltanolkotabi, W. Song, A. T. Suresh, S. U. Stich, A. Talwalkar, H. Wang, B. Woodworth, S. Wu, F. X. Yu, H. Yuan, M. Zaheer, M. Zhang, T. Zhang, C. Zheng, C. Zhu, and W. Zhu, A field guide to federated optimization, arXiv preprint arXiv:2107.06917, (2021).
  * [28] C. Xie, O. Koyejo, and I. Gupta, Generalized byzantine-tolerant SGD, arXiv preprint arXiv:1802.10116, (2018).
  * [29] , SLSGD: Secure and efficient distributed on-device machine learning, in Joint European Conference on Machine Learning and Knowledge Discovery in Databases, Würzburg, Germany, 2019, pp. 213–228.
  * [30] D. Yin, Y. Chen, R. Kannan, and P. Bartlett, Byzantine-robust distributed learning: Towards optimal statistical rates, in Proceedings of the 35th International Conference on Machine Learning, J. Dy and A. Krause, eds., vol. 80 of Proceedings of Machine Learning Research, PMLR, 2018, pp. 5650–5659.
  * [31] , Defending against saddle point attack in Byzantine-robust distributed learning, in Proceedings of the 36th International Conference on Machine Learning, K. Chaudhuri and R. Salakhutdinov, eds., vol. 97 of Proceedings of Machine Learning Research, PMLR, 09–15 Jun 2019, pp. 7074–7084.
  * [32] M. Zinkevich, M. Weimer, L. Li, and A. Smola, Parallelized stochastic gradient descent, in Advances in Neural Information Processing Systems, J. Lafferty, C. Williams, J. Shawe-Taylor, R. Zemel, and A. Culotta, eds., vol. 23, Curran Associates, Inc., 2010.


11institutetext: United States Military Academy, West Point NY 10996, USA
11email<EMAIL_ADDRESS>

# ArxNet Model and Data: Building Social Networks from Image Archives

Haley Seaward  Jasmine Talley  David Beskow

###### Abstract

A corresponding explosion in digital images has accompanied the rapid adoption
of mobile technology around the world. People and their activities are
routinely captured in digital image and video files. By their very nature,
these images and videos often portray social and professional connections.
Individuals in the same picture are often connected in some meaningful way.
Our research seeks to identify and model social connections found in images
using modern face detection technology and social network analysis. The
proposed methods are then demonstrated on the public image repository
associated with the 2022 Emmy’s Award Presentation.

###### Keywords:

face detection network science social network

##  1 Introduction and Background

The increased use of photography in the 20th century led to the phrase “a
picture is worth a thousand words,” first recorded used circa 1911. Images
contain a wealth of information. Images of people portray emotion,
personality, economic status, and other information about the people and
events that are etched into pixels. Pictures also record human relationships.
Images that contain more than one person often indicate some level of
connection or relationship among the individuals captured in a still photo or
motion images. These could be family, business, friendship, acquaintance, or
other types of social ties. These connections can be captured if we have a
method to identify the individuals in the image. This capability came in the
form of Face Detection. While face detection research had an early start in US
intelligence organizations in the 1960s [11], it became usable in the late
1990s and scientists now had the method to identify unique individuals in
images. With face detection technology in hand, some past research has focused
on building social networks from a family picture archive [16] and from movies
[14]. Our research will focus on building these networks on event data using
modern open-source facial detection software. Additionally, our algorithms
become computationally scalable by incorporating efficient search algorithms.
This algorithm is demonstrated on a specific public event, the 2022 Emmy’s
Awards held on 12 September 2022. The algorithm as well as the face detection
embeddings and resulting social network will be made public once this paper is
published.

##  2 Previous Work

Face detection is one of the most studied aspects of computer vision. Face
detection is used for a variety of different use cases and is the first step
in most human-computer and human-robot interaction [15]. Computer vision-based
faced detection began in the 1960s [4] but wasn’t practical on normal everyday
photos (photos “in the wild”) until the Viola-Jones algorithm using boosting
methods was developed in the late 1990s and early 2000s [13].

Face recognition involves several steps, each of which have a number of
different algorithms to address. Facial recognition generally involves the
following steps:

  1. 1.

Face detection (finding and segmenting the face(s) in the image)

  2. 2.

Face warping (given that faces can be at an infinite number of angles, this
step identifies facial landmarks and ‘warps’ the head so that the eyes, nose,
and mouth are centered)

  3. 3.

Encode the faces (create a mathematical representation of the face)

  4. 4.

Compare faces (recognize person by comparing encodings)

With the growth of mobile technology today, image archives can easily contain
millions of images. Using a brute force method for searching face embeddings
becomes computationally intractable, as we prove below. Several methods have
been developed to improve search. These include the k-dimensional tree (KD-
tree) [3], which is successful at low-dimension embeddings. Ball-tree [12] and
Locality Sensitive Hashing (LSH) [7] both work effectively at higher
dimensions. Other methods include Approximate Nearest Neighbors (ANN) [7]
which sacrifices some accuracy for speed [2]. We used the CPU version of FAISS
[8] and explored the use of both the default Flat L2 Search (also a brute-
force method) and the Inverted File with Product Quantization (IVFPQ)
indexing. The inverted file indexing creates inverted lists where each list
contains vectors that are close to a centroid and are efficient to search.
This also uses product quantization as a compression technique that reduces
the size of the index in memory, increasing the allowable index size.

Relatively few authors have looked at building relationship networks from
images. In 2003 Zhang et al used a Bayesian framework to annotate faces and
create a network from a family photo album by estimating face similarity,
working with missing features, and generating names for unlabeled faces by
comparing their similarities to a list of labeled faces [16]. Later, Weng,
Chu, and Wu created ‘RoleNet’, an algorithm that would automatically identify
movie scenes and create connections between the actors/characters that were
represented in that scene [14]. Zhang, Luo, and Loy expanded on this to
describe interpersonal relationships from the facial expressions of face
images in the wild [17]. This research was expanded on with networks
clustering in 2020 [10].

We used the Python face-recognition package created by Adam Geitgey to conduct
facial recognition [6]. Our pipeline used Histogram of Oriented Gradients
(HOG) [5] for face detection, face landmark orientation for face warping [9],
and Open Face [1] for facial encoding. We then used euclidean distance for
face recognition given the face emebedding.

Our research aims to build a relationship network of faces from a collection
of photos from a specific event. From this relationship network, network
science techniques such as centrality and clustering are used to understand
the strength of the resulting relationship network.

##  3 Data

Our research will use the pictures from the Emmy Award Show hosted in downtown
Los Angeles and held on Sept 12, 2022. These images were publicly available on
Getty Images (https://www.gettyimages.com/). There are a total of 2,828 images
from this event with 1,072 unique faces. A sample of these images is displayed
in Figure 1.

The Emmy’s Awards provides a well-known event with known celebrity faces and
known celebrity links or connections. These connections are often generated by
co-starring in past or present television shows. This resulting social network
will be released for open source once this paper is accepted/published.

Figure 1: Example Getty images from the 2022 Emmy Award Show

##  4 Methods

Given an archive of photos associated with a specific time, place, and event,
the ArxNet approach identifies unique faces in the images and then constructs
a network of co-occurring faces. This approach is illustrated in Figure 2. To
conduct this approach, we 1) conduct face recognition to extract all face
embeddings for each image in the archive, then 2) build an index for the
unique faces that we find, 3) build the edge list for unique co-occurring
faces, and finally 4) construct the graph from the edge list.

The example relationship network in Figure 2 begins with a photo of Ben
Stiller, his daughter, Ella Stiller, and Shawn Levy. The next photo includes
both Ben Stiller and his daughter again and introduces Laura Linney. The third
photo once again includes Ben Stiller and Ella Stiller, and introduces Martin
Short. The relationship diagram then follows Martin Short to the next photo
which includes Selena Gomez, Steve Martin, and of course Martin Short. The
last photo in this relationship diagram includes the same three faces, but
then adds a large crowd in the background. The identifiable faces in the
background of the last photo are then also included in the relationship
network. This example relationship network is simply a digestible snapshot of
the larger Gephi Relationship diagram which covers all the Getty Images from
the 2022 Emmy Award Show.

Figure 2: Illustrating the ArxNet Approach

Face recognition was conducted with Adam Geitgey’s pipeline [6]. We modified
his Face Recognition Docker Image to add compatibility with a Jupyter
environment. This pipeline uses Histogram of Oriented Gradients (HOG) [5] for
face detection, face landmark orientation for face warping [9], and OpenFace
[1] for facial encoding. At the end of this pipeline, each face is represented
with an embedding of length 128 that we store in a data structure where each
image name is associated with a list of the face embeddings found in it.

Face recognition was conducted using the euclidean distance between two face
embeddings. If the distance between the embeddings was less than 0.5, then the
embeddings were deemed to be the same face. While we conducted some
exploration of the right distance threshold, we found the default setting of
0.5 to be adequate for our use case.

Using the resulting data structure, we developed an algorithm that would build
the face co-occurrence network. This basic algorithmic approach is provided in
Algorithm 1. This algorithm takes each face for each picture, and first
searches an index to see if we’ve already seen the face before. If found, we
get the face indices and associate it with the picture. If the face is not
found, we add the face to our index. Once we’ve identified all of the faces in
the image, then we can associate them with a co-occurrence link. To do this we
identify all combinations of two faces from the set of faces in the picture.
For each combination, we add a link or edge to an edge list.

Algorithm 1 Basic ArxNet Algorithmic Approach

initialize index

for each picture do

for each face do

search index

if found then

get key

else

add face to index

end if

end for

if faces in picture $>1$ then

calculate all combinations of 2

for each combination do

append to edgelist

end for

end if

end for

For our initial algorithm for the Emmy Award data, we used a brute force
search algorithm in base Python with time complexity of $O(n^{2})$. For the
Getty Images dataset this ran in approximately 40 seconds on a standard
laptop. This method did not scale, as illustrated in Figure 3. In order to
improve the search speed, we leveraged the FAISS package created by the
Facebook Team [8]. We used the CPU version of FAISS and explored the use of
both the default Flat L2 Search (also a brute-force method) and the Inverted
File with Product Quantization (IVFPQ) indexing. The inverted file indexing
creates inverted lists where each list contains vectors that are close to a
centroid and are efficient to search. The increased speed of these is clear in
Figure 3. Using this method we were able to run the ArxNet Algorithm on 200K
images in approximately 50 seconds.

Figure 3: Demonstrating computational time complexity of different search
index

##  5 Results

The algorithm generates an edgelist and network representing co-occurring
faces. The resulting network reveals that there are 1072 unique faces, of
which 941 become nodes since they have relationships with at least one other
faces. The 941 nodes have a total of 3726 edges which connect the nodes
together of the Sept 12, 2022 Emmy Award show hosted in Downtown, Los Angeles.
This network contains 88 unique communities, of which 55 only contain two
nodes (or faces). The largest community contains 10% of the nodes (98/941
nodes).

Figure 4: Emmy’s ArxNet Relationship Diagram (colored by Louvain Cluster)

Another way to look at the diagram is by partitioning the diagram by edges and
then specifically through the attribute ‘images’. When the diagram is
partitioned this way, the image with the largest number of edges is Figure 2.
This image also comes from community 41 and is responsible for 2.07% of the
total edges in the relationship network, or 77/3726 edges.

Figure 5: Image with most edges

Figure 5 depicts actress, Zendaya accepting the Emmy for Outstanding Lead
Actress in a Drama Series for the television series “Euphoria”. The most
likely reason this photo is responsible for so many edges is because of its
location. There are numerous photos that are taken in this spot because this
is the spot in which Emmy award winners address the audience after winning an
award. Therefore, the people in the background of this photo are also in the
background of many other photos taken in this same location. Although these
people are in the background of numerous photos, it is still noteworthy that
Zendaya is the fifth person in this photo. Out of all the photos with these
people in the background, the photo with Zendaya is responsible for the most
edges. This reveals that Zendaya along with the four people in the background
share the most relationships with other faces in other photos.

##  6 Conclusion and Future Work

In this paper, we have addressed the previous work in the fields of face
recognition, search, and building community networks from image archives. We
have presented a technique that identifies faces via face embeddings, creates
relationships, and then groups relationships into communities. We validated a
threshold for the Euclidean distance threshold for determining the same face.
After validating the threshold, we built the relationship network. The network
connected 941 attendees of the 2022 Emmy Award Show. The output also revealed
the strongest communities and the single image that is responsible for the
most edges in the relationship network.

The limiting factor to this approach is that the algorithm creates
relationships between people in the foreground and the background of the
photos. This limitation is prevalent in the photo with the strongest edges.
This photo has four people in the background and one person in the foreground.
This skews the results because the algorithm gives equal weight to
relationships that consist of both faces in the foreground and relationships
that consist of both foreground and background faces. It is possible that the
people in the background and the foreground do have relationships, but it is
not fair to assume that these relationships are as strong as relationships
that are both foreground and backgrounds.

Social connections provide the foundation of social and organizational
interactions and evolution. Mapping these connections through facial co-
location in image archives can enable the study, understanding, and mapping of
these critical connections.

## References

  * [1] Amos, B., Ludwiczuk, B., Satyanarayanan, M.: Openface: A general-purpose face recognition library with mobile applications. Tech. Rep. CMU-CS-16-118, CMU School of Computer Science (2016)
  * [2] Arya, S., Mount, D.M., Netanyahu, N.S., Silverman, R., Wu, A.Y.: Optimal approximate nearest neighbors in high-dimensional spaces. Journal of the ACM (JACM) 45(6), 891–923 (1998)
  * [3] Bentley, J.L.: Multidimensional binary search trees used for associative searching. In: Communications of the ACM. vol. 18, pp. 509–517. ACM (1975)
  * [4] Bledsoe, W.W., Chan, H.: A man-machine facial recognition system—some preliminary results. Panoramic Research, Inc, Palo Alto, California., Technical Report PRI A 19, 1965 (1965)
  * [5] Dalal, N., Triggs, B.: Histograms of oriented gradients for human detection. In: Proceedings of the IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR). pp. 886–893. IEEE (2005)
  * [6] Geitgey, A.: face_recognition: A simple face recognition library for python. https://github.com/ageitgey/face_recognition (2016)
  * [7] Indyk, P., Motwani, R.: Approximate nearest neighbors: towards removing the curse of dimensionality. Proceedings of the thirtieth annual ACM symposium on Theory of computing pp. 604–613 (1998)
  * [8] Johnson, J., Douze, M., Jégou, H.: Billion-scale similarity search with GPUs. IEEE Transactions on Big Data 7(3), 535–547 (2019)
  * [9] Kazemi, V., Sullivan, J.: One millisecond face alignment with an ensemble of regression trees. In: Proceedings of the IEEE conference on computer vision and pattern recognition. pp. 1867–1874 (2014)
  * [10] Kulshreshtha, P., Guha, T.: Dynamic character graph via online face clustering for movie analysis. Multimedia Tools and Applications 79, 33103–33118 (2020)
  * [11] de Leeuw, K.M.M., Bergstra, J.: The history of information security: a comprehensive handbook. Elsevier (2007)
  * [12] Omohundro, S.M.: Five balltree construction algorithms. In: International Computer Science Institute Technical Report. vol. TR-89-063 (1989)
  * [13] Viola, P., Jones, M.: Rapid object detection using a boosted cascade of simple features. In: Proceedings of the 2001 IEEE computer society conference on computer vision and pattern recognition. CVPR 2001. vol. 1, pp. I–I. Ieee (2001)
  * [14] Weng, C.Y., Chu, W.T., Wu, J.L.: Rolenet: Movie analysis from the perspective of social networks. IEEE Transactions on Multimedia 11(2), 256–271 (2009)
  * [15] Zafeiriou, S., Zhang, C., Zhang, Z.: A survey on face detection in the wild: past, present and future. Computer Vision and Image Understanding 138, 1–24 (2015)
  * [16] Zhang, L., Chen, L., Li, M., Zhang, H.: Automated annotation of human faces in family albums. In: Proceedings of the eleventh ACM international conference on Multimedia. pp. 355–358 (2003)
  * [17] Zhang, Z., Luo, P., Loy, C.C., Tang, X.: From facial expression recognition to interpersonal relation prediction. International Journal of Computer Vision 126, 550–569 (2018)