cli short = CLI, long = Command Line Interface, class = abbrev

# Complete Verification via Multi-Neuron
Relaxation Guided Branch-and-Bound

Claudio Ferrari, Mark Niklas Müller, Nikola Jovanović, Martin Vechev
Department of Computer Science, ETH Zurich, Switzerland
{claudio.ferrari, mark.mueller, nikola.jovanovic<EMAIL_ADDRESS>

###### Abstract

State-of-the-art neural network verifiers are fundamentally based on one of
two paradigms: either encoding the whole verification problem via tight multi-
neuron convex relaxations or applying a Branch-and-Bound (BaB) procedure
leveraging imprecise but fast bounding methods on a large number of easier
subproblems. The former can capture complex multi-neuron dependencies but
sacrifices completeness due to the inherent limitations of convex relaxations.
The latter enables complete verification but becomes increasingly ineffective
on larger and more challenging networks. In this work, we present a novel
complete verifier which combines the strengths of both paradigms: it leverages
multi-neuron relaxations to drastically reduce the number of subproblems
generated during the BaB process and an efficient GPU-based dual optimizer to
solve the remaining ones. An extensive evaluation demonstrates that our
verifier achieves a new state-of-the-art on both established benchmarks as
well as networks with significantly higher accuracy than previously
considered. The latter result (up to 28% certification gains) indicates
meaningful progress towards creating verifiers that can handle practically
relevant networks.

##  1 Introduction

Recent years have witnessed substantial interest in methods for certifying
properties of neural networks, ranging from stochastic approaches (Cohen et
al., 2019) which construct a robust model from an underlying base classifier
to deterministic ones (Gehr et al., 2018; Katz et al., 2017; Xu et al., 2020)
that analyze a given network as is (the focus of our work).

#### Key Challenge: Scalable and Precise Non-Linearity Handling

Deterministic verification methods can be categorized as complete or
incomplete. Recent incomplete verification methods based on propagating and
refining a single convex region (Müller et al., 2022; Dathathri et al., 2020;
Tjandraatmadja et al., 2020) are limited in precision due to fundamental
constraints imposed by convex relaxations. Traditional complete verification
approaches based on SMT solvers (Ehlers, 2017) or a single mixed-integer
linear programming encoding of a property (Tjeng et al., 2019; Katz et al.,
2017) suffer from worst-case exponential complexity and are often unable to
compute sound bounds in reasonable time-frames. To address this issue, a
Branch-and-Bound approach (Bunel et al., 2020) has been popularized recently:
anytime-valid bounds are computed by recursively splitting the problem domain
into easier subproblems and deriving bounds on each of these via cheap and
less precise methods (Xu et al., 2021; Wang et al., 2021; Palma et al., 2021;
Henriksen & Lomuscio, 2021). This approach has proven effective on (smaller)
networks where there are relatively few unstable activations and splitting a
problem simplifies it substantially. However, for larger networks or those not
regularized to be amenable to certification this strategy becomes increasingly
ineffective as the larger number of unstable activations makes individual
splits less effective, which is exacerbated by the relatively loose underlying
bounding methods.

#### This Work: Branch-and-Bound guided by Multi-Neuron Constraints

In this work, we propose a novel certification method and verifier, called
Multi-Neuron Constraint Guided BaB (MN-BaB), which aims to combine the best of
both worlds: it leverages the tight multi-neuron constraints proposed by
Müller et al. (2022) within a BaB framework to yield an efficient GPU-based
dual method. The key insight is that the significantly increased precision of
the underlying bounding method substantially reduces the number of domain
splits (carrying exponential cost) required to certify a property. This
improvement is especially pronounced for larger and less regularized networks
where additional splits of the problem domain yield diminishing returns. We
release all code and scripts to reproduce our experiments at
https://github.com/eth-sri/mn-bab.

Main Contributions:

  * •

We present a novel verification framework, MN-BaB, which leverages tight
multi-neuron constraints and a GPU-based dual solver in a BaB approach.

  * •

We develop a novel branching heuristic, ACS, based on information obtained
from analyzing our multi-neuron constraints.

  * •

We propose a new class of branching heuristics, CAB, applicable to all BaB-
based verifiers, that correct the expected bound improvement of a branching
decision for the incurred computational cost.

  * •

Our extensive empirical evaluation demonstrates that we improve on the state
of the art in terms of certified accuracy by as much as 28% on challenging
networks.

##  2 Background

In this section, we review the necessary background for our method (discussed
next).

###  2.1 Neural Network Verification

The neural network verification problem can be defined as follows: given a
network $f:\mathcal{X}\to\mathcal{Y}$, an input region
$\mathcal{D}\subseteq\mathcal{X}$, and a linear property
$\mathcal{P}\subseteq\mathcal{Y}$ over the output neurons $y\in\mathcal{Y}$,
prove $f({\bm{x}})\in\mathcal{P},$ $\forall{\bm{x}}\in\mathcal{D}$. We
instantiate this problem with the challenging $\ell_{\infty}$-norm bounded
perturbations and set $\mathcal{D}$ to the $\ell_{\infty}$ ball around an
input point ${\bm{x}}_{0}$ of radius $\epsilon$:
$\mathcal{D}_{\epsilon}({\bm{x}}_{0})=\\{{\bm{x}}\in\mathcal{X}\mid||{\bm{x}}-{\bm{x}}_{0}||_{\infty}\leq\epsilon\\}$.

For ease of presentation, we consider neural networks of $L$ fully-connected
layers with ReLU activation functions (we note that MN-BaB can handle a wide
range of layers including convolutional, residual, batch-normalization, and
average-pooling layers). We focus on ReLU networks as the BaB framework only
yields complete verifiers for piecewise linear activation functions but remark
that our approach is applicable to a wide class of activations including ReLU,
Sigmoid, Tanh, MaxPool, and others. We denote the number of neurons in the
$i$${}^{\text{th}}$ layer as $d_{i}$ and the corresponding weights and biases
as ${\bm{W}}^{(i)}\in\mathds{R}^{d_{i}\times d_{i-1}}$ and
${\bm{b}}^{(i)}\in\mathds{R}^{d_{i}}$ for $i\in\\{1,...,L\\}$. Further, the
neural network is defined as $f({\bm{x}}):=\hat{{\bm{z}}}^{(L)}({\bm{x}})$
where
$\hat{{\bm{z}}}^{(i)}({\bm{x}}):={\bm{W}}^{(i)}{\bm{z}}^{(i-1)}({\bm{x}})+{\bm{b}}^{(i)}$
and ${\bm{z}}^{(i)}({\bm{x}}):=\max(0,\hat{{\bm{z}}}^{(i)}({\bm{x}}))$. For
readability, we omit the dependency of intermediate activations on ${\bm{x}}$.

Since we can encode any linear property over output neurons into an additional
affine layer, we can simplify the general formulation
$f({\bm{x}})\in\mathcal{P}$ to $f({\bm{x}})>\mathbf{0}$. The property can now
be verified by proving that a lower bound to the following optimization
problem is greater $0$:

$\displaystyle\min_{{\bm{x}}\in\mathcal{D}_{\epsilon}({\bm{x}}_{0})}$
$\displaystyle f({\bm{x}})=\hat{{\bm{z}}}^{(L)}$ (1) $\displaystyle s.t.$
$\displaystyle\hat{{\bm{z}}}^{(i)}={\bm{W}}^{(i)}{\bm{z}}^{(i-1)}+{\bm{b}}^{(i)}$
$\displaystyle{\bm{z}}^{(i)}=\max(\mathbf{0},\hat{{\bm{z}}}^{(i)})$

A method is called sound if every property it proves actually holds (no false
positives). A method is called complete if it can prove every property that
actually holds (no false negatives).

###  2.2 Branch-and-Bound for Verification

Bunel et al. (2020) successfully applied the Branch-and-Bound (BaB) approach
(lan, 1960) to neural network verification. It consists of a bounding method
that computes sound upper and lower bounds on the optimization objective of
Eq. 1 and a branching method that recursively splits the problem into
subproblems with added constraints, allowing for increasingly tighter bounds.
If an upper bound (primal solution) $<0$ is found, this represents a
counterexample and allows to terminate the procedure. If a lower bound $>0$ is
obtained, the property is verified on the corresponding (sub-)domain. If a
lower bound $>0$ is derived on all subdomains, the property is verified. An
ideal splitting procedure minimizes the total time required for bounding,
which is often well approximated by the number of considered subproblems. A
simple approach is to split the input domain, however, this is inefficient for
high-dimensional input spaces. Splitting a ReLU activation node into its
positive and negative phases has been shown to be far more efficient (Bunel et
al., 2020) and ultimately yields a complete verifier (Wang et al., 2021).
Hence, we focus solely on ReLU branching strategies.

###  2.3 Linear Constraints

$x$$y$$l_{x}$$u_{x}$$y\leq\frac{u_{x}}{u_{x}-l_{x}}(x-l_{x})$$y\geq\alpha
x$Y1.0e0]pt$y=\max(0,x)$ Figure 1: Illustration of the DeepPoly relaxation of
a ReLU activation $y=\max(x,0)$ given the neuron-wise bounds
$x\in[l_{x},u_{x}]$ and parametrized by $\alpha\in[0,1]$.

The key challenge in neural network verification Eq. 1 is handling the non-
linear activations. Stable ReLUs, i.e., those which we can show to be always
active ($\hat{z}\geq 0$) or inactive ($\hat{z}\leq 0$), can be replaced by
linear functions. Unstable ReLUs, i.e., those that can be either active or
inactive depending on the exact $x\in\mathcal{D}$, have to be approximated
using a convex relaxation of their input-output set. We build on the convex
relaxation introduced in DeepPoly (Singh et al., 2019b) and shown in Fig. 1.
Its key property is the single linear upper and lower bound, which allows for
efficient bound computation.

###  2.4 Multi-Neuron Constraints

2-neuronsingle-neuron$x_{1}$$x_{2}$$y_{2}$$x_{1}$$x_{2}$$y_{2}$

Figure 2: Comparison of multi-neuron and single-neuron constraints projected
into $y_{2}$-$x_{1}$-$x_{2}$-space. Reproduced from Müller et al. (2022).

All convex relaxations that consider ReLU neurons individually are
fundamentally limited in their precision by the so-called (single-neuron)
convex relaxation barrier (Salman et al., 2019). It can be overcome by
considering multiple neurons jointly (Singh et al., 2019a; Tjandraatmadja et
al., 2020; Müller et al., 2022; Palma et al., 2021), thereby capturing
interactions between these neurons and obtaining tighter bounds, illustrated
in Fig. 2. We leverage the multi-neuron constraints from Müller et al. (2022),
expressed as a conjunction of linear constraints over the joint input and
output space of a ReLU layer.

###  2.5 Constrained Optimization via Lagrange Multipliers

To express constraints as part of the optimization problem, we use the
technique of Lagrange multipliers. Given a constrained minimization problem
$\min_{{\bm{x}}}f({\bm{x}}),\,s.t.\;{\bm{g}}({\bm{x}})\leq\mathbf{0}$, we can
bound the objective value with:

$\min_{{\bm{x}}}f({\bm{x}})\geq\min_{{\bm{x}}}\max_{\bm{\lambda}\geq\mathbf{0}}f({\bm{x}})+\bm{\lambda}{\bm{g}}({\bm{x}})$

If a constraint is satisfied, i.e., $g({\bm{x}})_{j}\leq 0$, $\lambda_{j}=0$
maximizes the (inner) objective, else, i.e., $g({\bm{x}})_{j}>0$, increasing
$\lambda_{j}$ allows the objective to grow unboundedly, shifting the minimum
over ${\bm{x}}$ until the constraint is satisfied. Hence, if $\lambda_{j}>0$
after optimization, the constraint is active, i.e., it is actively enforced
and currently satisfied with equality.

##  3 A Multi-Neuron Relaxation Based BaB Framework

In this section, we describe the two key components of MN-BaB: (i) an
efficient bounding method leveraging multi-neuron constraints, as well as
constrained optimization via lagrange multipliers (Section 3.1), and (ii) a
branching method tailored to it (Section 3.2).

###  3.1 Efficient Multi-Neuron Bounding

We build on the approach of Singh et al. (2019b), extended by Wang et al.
(2021) of deriving a lower bound $\underline{f}$ as a function of the network
inputs and a set of optimizable parameters. Crucially, we tighten these
relatively loose bounds significantly by enforcing precise multi-neuron
constraints via Lagrange multipliers. To enable this, we develop a method
capable of integrating any linear constraint over arbitrary neurons anywhere
in the network into the optimization objective. At a high level, we derive
linear upper and lower bounds of the form
${\bm{z}}^{(i)}\,\stackanchor[-1pt]{$\lessgtr$}{$-$}\,{\bm{a}}{\bm{z}}^{(i-1)}+c$
for every layer’s output in terms of its inputs ${\bm{z}}^{(i-1)}$. Then,
starting with a linear expression in the last layer’s outputs ${\bm{z}}^{(L)}$
which we aim to bound, we use the linear bounds derived above, to replace
${\bm{z}}^{(L)}$ with symbolic bounds depending only on the previous layer’s
values ${\bm{z}}^{(L-1)}$. We proceed in this manner recursively until we
obtain an expression only in terms of the networks inputs. Below, we describe
this backsubstitution process for ReLU and affine layers.

#### Affine Layer

Assume any affine layer
$\hat{{\bm{z}}}^{(i)}=\textbf{W}^{(i)}{\bm{z}}^{(i-1)}+\textbf{b}^{(i)}$ and a
lower bound
$\underline{f}=\hat{{\bm{a}}}^{(i)}\hat{{\bm{z}}}^{(i)}+\hat{{c}}^{(i)}$ with
respect to its outputs. We then substitute the affine expression for
$\hat{{\bm{z}}}^{(i)}$ to obtain:

$\underline{f}=\underbrace{\hat{{\bm{a}}}^{(i)}\textbf{W}^{(i)}}_{{\bm{a}}^{(i-1)}}{\bm{z}}^{(i-1)}+\underbrace{\hat{{\bm{a}}}^{(i)}\textbf{b}^{(i)}+\hat{{c}}^{(i)}}_{{c}^{(i-1)}}={\bm{a}}^{(i-1)}{\bm{z}}^{(i-1)}+{c}^{(i-1)}$
(2)

#### ReLU Layer

Let $\underline{f}={\bm{a}}^{(i)}{\bm{z}}^{(i)}+{c}^{(i)}$ be a lower bound
with respect to the output of a ReLU layer
${{\bm{z}}}^{(i)}=\max(0,\hat{{\bm{z}}}^{(i)})$ and $\textbf{l}^{(i)}$ and
$\textbf{u}^{(i)}$ bounds on its input s.t.
$\textbf{l}^{(i)}\leq\hat{{\bm{z}}}^{(i)}\leq\textbf{u}^{(i)}$, obtained by
recursively applying this bounding procedure or using a cheaper but less
precise bounding method (Singh et al., 2018; Gowal et al., 2018). The
backsubstitution through a ReLU layer now consists of three distinct steps:
1) enforcing multi-neuron constraints,  2) enforcing single-neuron constraints
to replace the dependence on ${{\bm{z}}}^{(i)}$ by $\hat{{\bm{z}}}^{(i)}$, and
3) enforcing split constraints,  which we describe in detail below.

Enforcing Multi-Neuron Constraints We compute multi-neuron constraints as
described in Müller et al. (2022), although our approach is applicable to any
linear constraints in the input-output space of ReLU activations, written as:

$\begin{bmatrix}{\bm{P}}^{(i)}&\hat{{\bm{P}}}^{(i)}&-\textbf{p}^{(i)}\end{bmatrix}\begin{bmatrix}{\bm{z}}^{(i)}\\\
\hat{{\bm{z}}}^{(i)}\\\ 1\end{bmatrix}\leq 0.\vspace{-1mm}$ (3)

where $\hat{{\bm{z}}}^{(i)}$ are the pre- and ${\bm{z}}^{(i)}$ the post-
activation values and ${\bm{P}}^{(i)}$, $\hat{{\bm{P}}}^{(i)}$, and
$-\textbf{p}^{(i)}$ the constraint parameters. We enforce these constraints
using Lagrange multipliers (see Section 2.5), yielding sound lower bounds for
all $\mathbf{\bm{\gamma}}^{(i)}\in{(\mathds{R}^{\geq 0})}^{e_{i}}$, where
$e_{i}$ denotes the number of multi-neuron constraints in layer $i$.

$\displaystyle{\bm{a}}^{(i)}{\bm{z}}^{(i)}+{c}^{(i)}$
$\displaystyle\geq\max_{\bm{\gamma}^{(i)}\geq
0}{\bm{a}}^{(i)}{\bm{z}}^{(i)}+{c}^{(i)}+\bm{\gamma}^{(i)\top}({\bm{P}}^{(i)}{\bm{z}}^{(i)}+\hat{{\bm{P}}}^{(i)}\hat{{\bm{z}}}^{(i)}-\textbf{p}^{(i)})$
$\displaystyle=\max_{\bm{\gamma}^{(i)}\geq
0}\underbrace{({\bm{a}}^{(i)}+\bm{\gamma}^{(i)\top}{\bm{P}}^{(i)})}_{{\bm{a}}^{\prime(i)}}{\bm{z}}^{(i)}+\underbrace{\bm{\gamma}^{(i)\top}\hat{{\bm{P}}}^{(i)}\hat{{\bm{z}}}^{(i)}+\bm{\gamma}^{(i)\top}(-\textbf{p}^{(i)})+{c}^{(i)}}_{c^{\prime(i)}}$

Note that this approach can be easily extended to linear constraints over any
activations in arbitrary layers if applied in the last affine layer at the
very beginning of the backsubstitution process.

Enforcing Single-Neuron Constraints We now apply the single-neuron DeepPoly
relaxation with parametrized slopes $\alpha$ collected in ${\bm{D}}$ (see
below):

$\displaystyle\max_{\bm{\gamma}^{(i)}\geq
0}{\bm{a}}^{\prime(i)}{\bm{z}}^{(i)}+{c}^{\prime(i)}\ $
$\displaystyle\geq\max_{\begin{subarray}{c}0\leq\bm{\alpha}^{(i)}\leq 1\\\
\bm{\gamma}^{(i)}\geq
0\end{subarray}}{\bm{a}}^{\prime(i)}({\bm{D}}^{(i)}\hat{{\bm{z}}}^{(i)}+\underline{{\bm{b}}}^{(i)})+{c}^{\prime(i)}$
$\displaystyle=\max_{\begin{subarray}{c}0\leq\bm{\alpha}^{(i)}\leq 1\\\
\bm{\gamma}^{(i)}\geq
0\end{subarray}}\underbrace{{\bm{a}}^{\prime(i)}{\bm{D}}^{(i)}}_{{\bm{a}}^{\prime\prime(i)}}\hat{{\bm{z}}}^{(i)}+\underbrace{{\bm{a}}^{\prime(i)}\underline{{\bm{b}}}^{(i)}+{c}^{\prime(i)}}_{{c}^{\prime\prime(i)}}$

The intercept vector $\underline{{\bm{b}}}$ and the diagonal slope matrix
${\bm{D}}$ are defined as:

$D_{j,j}=\begin{cases}1&\text{if ${l_{j}}\geq 0$ or node $j$ is positively
split}\\\ 0&\text{if ${u_{j}}\leq 0$ or node $j$ is negatively split}\\\
\alpha_{j}&\text{if ${l_{j}}<0<u_{j}$ and $a_{j}\geq 0$}\\\
\frac{u_{j}}{u_{j}-l_{j}}&\text{if $l_{j}<0<u_{j}$ and $a_{j}<0$}\end{cases}$
$\underline{b}_{j}=\begin{cases}-\frac{u_{j}l_{j}}{u_{j}-l_{j}}&\text{if
$l_{j}<0<u_{j}$ and $a_{j}<0$}\\\ 0&\text{otherwise}\end{cases}$

Where we drop the layer index $i$ for readability and $\alpha_{j}$ is the
lower bound slope parameter illustrated in Fig. 1. Note how, depending on
whether the sensitivity $a^{(i)}_{j}$ of $\underline{f}$ w.r.t. $z^{(i)}_{j}$
has positive or negative sign, we substitute $z^{(i)}_{j}$ for its lower or
upper bound, respectively.

Enforcing Split Constraints We encode split constraints of the form
$\hat{z}^{(i)}_{j}\geq 0$ or $\hat{z}^{(i)}_{j}\leq 0$ using the diagonal
split matrix ${\bm{S}}$. How the splits are determined will be described in
Section 3.2. For readability, we again dropping the layer index $i$:

$S_{j,j}=\begin{cases}-1&\text{positive split: $\hat{z}_{j}\geq 0$}\\\
1&\text{negative split: $\hat{z}_{j}<0$}\\\ 0&\text{no split}\end{cases}$ (4)
${\bm{S}}^{(i)}\hat{{\bm{z}}}^{(i)}\leq 0$

We again enforce these constraints using Lagrange multipliers:

$\displaystyle\max_{\begin{subarray}{c}0\leq\bm{\alpha}^{(i)}\leq 1\\\
\bm{\gamma}^{(i)}\geq
0\end{subarray}}{\bm{a}}^{\prime\prime(i)}\hat{{\bm{z}}}^{(i)}+c^{\prime\prime(i)}$
$\displaystyle\geq\max_{\begin{subarray}{c}0\leq\bm{\alpha}^{(i)}\leq 1\\\
\bm{\beta}^{(i)}\geq 0\\\ \bm{\gamma}^{(i)}\geq
0\end{subarray}}\underbrace{({\bm{a}}^{\prime\prime(i)}+\bm{\beta}^{(i)\top}{\bm{S}}^{(i)})}_{{\bm{a}}^{\prime\prime\prime(i)}}\hat{{\bm{z}}}^{(i)}+\underbrace{c^{\prime\prime(i)}}_{c^{\prime\prime\prime(i)}}$

Putting everything together, the backsubstitution operation through a ReLU
layer is:

$\begin{split}\min_{x\in\mathcal{D}}{\bm{a}}^{(i)}{\bm{z}}^{(i)}+{c}^{(i)}\geq\min_{x\in\mathcal{D}}\max_{\begin{subarray}{c}0\leq\bm{\alpha}^{(i)}\leq
1\\\ \bm{\beta}^{(i)}\geq 0\\\ \bm{\gamma}^{(i)}\geq
0\end{subarray}}&\underbrace{(({\bm{a}}^{(i)}+\bm{\gamma}^{(i)\top}{\bm{P}}^{(i)}){\bm{D}}^{(i)}+\bm{\beta}^{(i)\top}{\bm{S}}^{(i)}+\bm{\gamma}^{(i)\top}\hat{{\bm{P}}}^{(i)})}_{\hat{{\bm{a}}}^{(i)}}\hat{{\bm{z}}}^{(i)}\\\
&+\underbrace{({\bm{a}}^{(i)}+\bm{\gamma}^{(i)\top}{\bm{P}}^{(i)})^{\prime}\underline{b}^{(i)}+\bm{\gamma}^{(i)\top}(-\textbf{p}^{(i)})+{c}^{(i)}}_{\hat{{c}}^{(i)}}\\\
\end{split}$ (5)

Full backsubstitution through all layers leads to an optimizable lower bound
on $\underline{f}$:

$\min_{{\bm{x}}\in\mathcal{D}}f(x)\geq\min_{{\bm{x}}\in\mathcal{D}}\max_{\begin{subarray}{c}0\leq\bm{\alpha}\leq
1\\\ 0\leq\bm{\beta}\\\
0\leq\bm{\gamma}\end{subarray}}{\bm{a}}^{(0)}{\bm{x}}+{c}^{(0)}\geq\max_{\begin{subarray}{c}0\leq\bm{\alpha}\leq
1\\\ 0\leq\bm{\beta}\\\
0\leq\bm{\gamma}\end{subarray}}\min_{{\bm{x}}\in\mathcal{D}}{\bm{a}}^{(0)}{\bm{x}}+{c}^{(0)}$

where the second inequality holds due to weak duality. We denote all
$\alpha_{j}^{(i)}$ from every layer of the backsubstitution process with
$\bm{\alpha}$ and define $\bm{\beta}$ and $\bm{\gamma}$ analogously. The inner
minimization over ${\bm{x}}$ has a closed form solution if $\mathcal{D}$ is an
$l_{p}$-ball of radius $\epsilon$ around ${\bm{x}}_{0}$, given by Hölder’s
inequality:

$\max_{\begin{subarray}{c}0\leq\bm{\alpha}\leq 1\\\ 0\leq\bm{\beta}\\\
0\leq\bm{\gamma}\end{subarray}}\min_{{\bm{x}}\in\mathcal{D}}{\bm{a}}^{(0)}{\bm{x}}+{c}^{(0)}\geq\max_{\begin{subarray}{c}0\leq\bm{\alpha}\leq
1\\\ 0\leq\bm{\beta}\\\
0\leq\bm{\gamma}\end{subarray}}{\bm{a}}^{(0)}{\bm{x}}_{0}-||{\bm{a}}^{(0)\top}||_{q}\,\epsilon+c^{(0)}$
(6)

where $q$ is defined $s.t.$ $\frac{1}{p}+\frac{1}{q}=1$. Since these bounds
are sound for any $0\leq\bm{\alpha}\leq 1$, and $\bm{\beta},\bm{\gamma}\geq
0$, we tighten them by using (projected) gradient ascent to optimize these
parameters.

We compute all intermediate bounds ($\textbf{l}^{(i)}$, $\textbf{u}^{(i)}$)
using the same bounding procedure, leading to two full parameter sets for
every neuron in the network. To reduce memory requirements, we share parameter
sets between all neurons in the same layer, but keep separate sets for upper
and lower bounds.

#### Upper Bounding the Minimum Objective

Showing an upper bound on the minimum optimization objective precluding
verification ($\overline{f}<0$) allows us to terminate the BaB process early.
Propagating any input ${\bm{x}}\in\mathcal{D}$ through the network yields a
valid upper bound, hence, we use the input that minimizes Eq. 6:

$x_{i}=\begin{cases}(x_{0})_{i}+\epsilon&\text{if $a^{(0)}_{i}<0$}\\\
(x_{0})_{i}-\epsilon&\text{if $a^{(0)}_{i}\geq 0$}\end{cases}.\vspace{-2mm}$

###  3.2 Multi-Neuron Constraint Guided Branching

Generally, the BaB approach is based on recursively splitting an optimization
problem into easier subproblems to derive increasingly tighter bounds.
However, the benefit of different splits can vary widely, making an effective
branching heuristic which chooses splits that minimize the total number of
required subproblems a key component of any BaB framework (Bunel et al.,
2020). Typically, a score is assigned based on the expected bound improvement
and the most promising split is chosen. Consequently, the better this score
captures the actual bound improvement, the better the resulting decision. Both
the commonly used BaBSR (Bunel et al., 2020) and the more recent FSB (De Palma
et al., 2021) approximate bound improvements under a DeepPoly style
backsubstitution procedure. As neither considers the impact of multi-neuron
constraints, the scores they compute might not be suitable proxies for the
bound improvements obtained with our method. To overcome this issue, we
propose a novel branching heuristic, _A ctive Constraint Score Branching_
(ACS), considering multi-neuron constraints. Further, we introduce _C ost
Adjusted Branching_ (CAB), which corrects the expected bound improvement with
the potentially significantly varying expected computational cost.

#### Active Constraint Score Branching

The value of a Lagrange parameter $\gamma$ provides valuable information about
the constraint it enforces. Concretely, $\gamma>0$ indicates that a constraint
is active, i.e., the optimal solution fulfills it with equality. Further, for
a constraint $g(x)\leq 0$, a larger $\partial_{x}\gamma g(x)$ indicates a
larger sensitivity of the final bound to violations of this constraint. We
compute this sensitivity for our multi-neuron constraints with respect to both
ReLU outputs and inputs as $\bm{\gamma}^{\top}{{\bm{P}}}$ and
$\bm{\gamma}^{\top}\hat{{\bm{P}}}$, respectively, where ${{\bm{P}}}$ and
$\hat{{\bm{P}}}$ are the multi-neuron constraint parameters. We then define
our branching score for a neuron $j$ in layer $i$ as the sum over all
sensitivities with respect to its input or output:

$s_{i,j}=|\bm{\gamma}^{(i)\top}{\bm{P}}^{(i)}|_{j}+|\bm{\gamma}^{(i)\top}\hat{{\bm{P}}}^{(i)}|_{j},$
(7)

Intuitively, splitting the node with the highest cumulative sensitivity makes
its encoding exact and effectively tightens all of these high sensitivity
constraints. We can efficiently compute those scores without an additional
backsubstitution pass.

#### Cost Adjusted Branching

Any complete method will decide every property eventually. Hence, its runtime
is a key performance metric. Existing branching heuristics ignore this aspect
and only consider the expected improvement in bound-tightness, but not the
sometimes considerable differences in computational cost. We propose Cost
Adjusted Branching, scaling the expected bound improvement (approximated with
the branching score) with the inverse of the cost expected for the split, and
then picking the branching decision yielding the highest expected bound
improvement per cost. The true cost of a split consists of the direct cost of
the next branching step and the change of cumulative cost for all consecutive
steps. We find a local approximation considering just the former component,
similar to only considering the one-step bound improvement, to be a good
proxy. We approximate this direct cost by the number of floating-point
operations required to compute the new bounds, refer to App. B for a more
detailed description. Note that any approximation of the expected cost can be
used to instantiate CAB.

#### Enforcing Splits

Once the ReLU node to split on has been determined, two subproblems for the
negative and positive splits of the corresponding node are generated. This is
done by setting the corresponding entries in Eq. 4. As the intermediate bounds
for all layers up to and including the one that was split remain unchanged, we
do not recompute them.

###  3.3 Soundness and Completeness

The soundness of the BaB approach follows directly from the soundness of the
underlying bounding method discussed in Section 3.1. To show completeness, it
is sufficient to consider the limit case where all ReLU nodes are split and
the network becomes linear, making DeepPoly relaxations exact. To also obtain
exact bounds, all split constraints have to be enforced. This can be done by
computing optimal $\bm{\beta}$ for the now convex optimization problem (Wang
et al., 2021). It follows that a property holds if and only if the exact
bounds thus obtained are positive on all subproblems. We conclude that MN-BaB
is a complete verifier.

##  4 Experimental Evaluation

We now present an extensive evaluation of our method. First, and perhaps
surprisingly, we find that existing MILP-based verification tools (Singh et
al., 2019c; Müller et al., 2022) are more effective in verifying robustness on
many established benchmark networks than what is considered state-of-the-art.
This highlights that next-generation verifiers should focus on and be
benchmarked using less regularized and more accurate networks. We take a step
in this direction by proposing and comparing on such networks, before
analyzing the effectiveness of the different components of MN-BaB in an
extensive ablation study.

#### Experimental Setup

We implement a GPU-based version of MN-BaB in PyTorch (Paszke et al., 2019)
and evaluate all benchmarks using a single NVIDIA RTX 2080Ti, 64 GB of memory,
and 16 CPU cores. We attempt to falsify every property with an adversarial
attack, before beginning certification. For every subproblem, we first lower-
bound the objective using DeepPoly and then compute refined bounds using the
method described in Section 3.

#### Benchmarks

We benchmark MN-BaB on a wide range of networks (see Table 3 in App. A) on the
MNIST (Deng, 2012) and CIFAR10 datasets (Krizhevsky et al., 2009). We also
consider three new residual networks, ResNet6-A, ResNet6-B, and ResNet8-A.
ResNet6-A and ResNet6-B have the same architecture but differ in
regularization strength while ResNet8-A has an additional residual block. All
three were trained with adversarial training (Madry et al., 2018) using PGD,
the GAMA loss (Sriramanan et al., 2020) and MixUp data augmentation (Zhang et
al., 2021). ResNet6-A and ResNet8-A were trained using $8$-steps and
${\epsilon}=4/255$, whereas $20$-steps and ${\epsilon}=8/255$ were used for
ResNet6-B.We compare against $\beta$-Crown (Wang et al., 2021), a BaB-based
state-of-the-art complete verifier, oval (Palma et al., 2021; De Palma et al.,
2021; Bunel et al., 2020), a BaB framework based on a different class of
multi-neuron constraints, and ERAN Singh et al. (2019c); Müller et al. (2022)
combining the incomplete verifier PRIMA, whose tight multi-neuron constraints
we leverage in our method, and a (partial) MILP encoding.

Table 1: Natural accuracy [%] (Acc.), verified accuracy [%] (Ver.) and its
empirical upper bound [%] and average runtime [s] of the first 1000 images of
the test set.

Dataset Model Acc. $\epsilon$ ERAN oval $\beta$-Crown MN-BaB (ours) BaBSR +CAB
MN-BaB (ours) ACS +CAB Upper Bound Ver. Time Ver. Time Ver. Time Ver. Time
Ver. Time MNIST ConvSmall 98.0 0.12 73.2 38.4 69.8 26.2 71.6† 46 71.0 21.3
70.3 26.2 73.2 ConvBig 92.9 0.30 78.6 6.0 $-$ $-$ 77.7† 78 78.3 20.8 77.2 46.2
78.6 ConvSuper 97.7 0.18 0.5 142.0 $-$ $-$ $-$ $-$ 19.2 86.2 17.6 90.9 37.3
CIFAR10 ConvSmall 63.0 2/255 47.2 54.4 46.2 17.7 46.3† 18 46.1 16.4 45.8 18.0
48.1 ConvBig 63.1 2/255 48.2 128.1 50.6 42.0 50.3† 55 49.4 49.5 51.5 37.0 55.0
ResNet6-A ‡ 84.0 1/255 45.0 114.6 • • 52.0 263.4 48.0 202.7 55.0 170.7 75.0
ResNet6-B ‡ 79.0 1/255 66.0 48.6 • • 67.0 105.7 65.0 51.1 67.0 37.8 71.0
ResNet8-A ‡ 83.0 1/255 11.0 362.5 • • 18.0 497.3 19.0 390.7 23.0 371.0 70.0
$\dagger$ We report numbers from Wang et al. (2021). $-$ Errors prevent
reporting reliable numbers. ‡ Due to long runtimes, we evaluated only on the
first 100 samples of the test set. • oval does not support ResNet
architectures.

#### Comparison to State-of-the-Art Methods

In Table 1, we compare the verified accuracy and runtime of MN-BaB with that
of state-of-the-art tools ERAN, $\beta$-Crown, and oval. Perhaps surprisingly,
we find that both MNIST and the smallest CIFAR10 benchmark network established
over the last years (Singh et al., 2019b) can be verified completely or almost
completely in less than $50$s per sample using ERAN, making them less relevant
as benchmarks for new verification tools. On these networks, all three BaB
methods (including ours) are outperformed to a similar degree, with the
reservation that we could not evaluate oval on MNIST ConvBig due to runtime
errors. On the remaining unsolved networks where complete verification via a
MILP encoding does not scale, MN-BaB consistently obtains the highest
certified accuracy and for all but one also the lowest runtime. On ConvSuper
we were not able to find configurations for oval and $\beta$-Crown that did
not run out of memory. Comparing the BaB methods, we observe an overall trend
that more precise but also expensive underlying bounding methods are most
effective on larger networks, where additional splits are less efficient, and
complex inter-neuron interactions can be captured by the precise multi-neuron
constraints. On these networks, the more complex interactions also lead to
more active Multi-Neuron Constraints (MNCs) and hence more informative ACS
scores.

Figure 3: Ratio of subproblems required per property without and with MNCs.

Figure 4: Ratio of subproblems required per property with BaBSR and ACS.

Figure 5: Effect of Cost Adjusted Branching on mean verification time with
ACS.

#### Ablation Study

Table 2: Verified accuracy [%] (Ver.) and avg. runtime [s] on the first 100
images of the test set for $\epsilon=1/255$).

Model | Acc. |  Upper Bound |  Branching Method |  MNCs | MN-BaB
---|---|---|---|---|---
Ver | Time
ResNet6-A | 84 | 75 | No Branching | no | 30 | 0.4
|  |  | No Branching | yes | 39 | 13.2
|  |  | BaBSR | no | 42 | 247.1
|  |  |  BaBSR +CAB | no | 46 | 219.3
|  |  | FSB | yes | 45 | 239.7
|  |  | BaBSR | yes | 47 | 212.8
|  |  |  BaBSR +CAB | yes | 48 | 202.7
|  |  | ACS | yes | 51 | 186.4
|  |  |  ACS +CAB | yes | 55 | 170.7
ResNet6-B | 79 | 71 | No Branching | no | 58 | 0.7
|  |  | No Branching | yes | 61 | 4.1
|  |  | BaBSR | no | 61 | 78.3
|  |  |  BaBSR +CAB | no | 63 | 64.9
|  |  | FSB | yes | 64 | 67.0
|  |  | BaBSR | yes | 63 | 65.5
|  |  |  BaBSR +CAB | yes | 65 | 51.1
|  |  | ACS | yes | 65 | 52.0
|  |  |  ACS +CAB | yes | 67 | 37.8

To analyze the individual components of MN-BaB, we consider the weakly and
heavily regularized ResNet6-A and ResNet6-B, respectively, with identical
architecture. Concretely, we show the effect different bounding procedures and
branching approaches have in the two settings in Table 2. As verified accuracy
and mean runtime are very coarse performance metrics, we also analyze the
ratio of runtimes and number of subproblems required for verification on a
per-property level, filtering out those where both methods verify before any
branching occurred (Figs. 5, 5 and 5). Overall, we observe that the number of
visited subproblems required for certification can be reduced by two to three
orders of magnitude by leveraging precise multi-neuron constraints and then
again by another one to two orders of magnitude by our novel branching
heuristic, ACS. Our cost-adjusted branching yields an additional speed up of
around $50\%$.

Figure 6: Per property verification times using MN-BaB over those without MNCs
and using BaBSR.

The trend of MN-BaB succeeding on more challenging networks is confirmed here.
Leveraging MNCs enables us to verify $20$% more samples while being around
$22$% faster (see Table 2) on ResNet6-A while on the more heavily regularized
ResNet6-B we only verify $6$% more samples. When analyzing on a per-property
level, shown in Fig. 6, the trend is even more pronounced. For easy problems,
leveraging MNCs and ACS has little impact (points in the lower left-hand
corner). However, it completely dominates on the harder properties where only
using single-neuron constraints and BaBSR takes up to $33$ times longer
(points below the diagonal).

#### Effectiveness of Multi-Neuron Constraints

In Fig. 5, we show the ratio between the number of subproblems required to
prove the same lower bound on the final objective (either $0$, if both methods
certify, or the smaller of the two lower bounds at termination) with and
without MNCs over the quantile of properties for ResNet6-A (blue) and
ResNet6-B (orange). We observe that using MNCs reduces the number of
subproblems for both networks by between two and three orders of magnitude.
Despite the higher per bounding-step cost, this leads to the use of MNCs
increasing the number of verified samples by up to $12\%$ while reducing
average certification times (see Table 2).

#### Effectiveness of ACS Branching

In Fig. 5, we show the ratio between the number of subproblems considered when
using BaBSR vs. ACS over the quantile of properties. We observe that ACS
yields significantly fewer subproblems on most ($75\%$) or all properties on
ResNet6-A and ResNet6-B, respectively, leading to an additional reduction by
between one and two orders of magnitude and showing the effectiveness of our
novel ACS branching heuristic. Average verification times are reduced by
$12\%$ and $21\%$ on ResNet6-A and ResNet6-B, respectively. Note that the
relatively small improvements in timings are due to timeouts for both methods
yielding equally high runtimes which dominate the mean. FSB is consistently
outperformed by ACS, certifying $12$% less samples on ResNet6-A.

#### Effectiveness of Cost Adjusted Branching

In Fig. 5, we show the per property verification times with ACS \+ CAB over
those with ACS. Using CAB is faster (points below the dashed line) for all
properties, sometimes significantly so, leading to an average speedup of
around $50\%$. Analyzing the results in Table 2, we observe that CAB is
particularly effective in combination with the ACS scores and multi-neuron
constraints, where bounding costs vary more significantly.

##  5 Related Work

#### Neural Network Verification Beyond the Single Neuron Convex Barrier

After the so-called (Single Neuron) Convex Barrier has been described by
Salman et al. (2019) for incomplete relaxation-based methods, a range of
approaches has been proposed that consider multiple neurons jointly to obtain
tighter relaxations. Singh et al. (2019a) and Müller et al. (2022) derive
joint constraints over the input-output space of groups of neurons and refine
their relaxation using the intersection of these constraints. Tjandraatmadja
et al. (2020) merge the ReLU and preceding affine layer to consider multiple
inputs but only one output at a time. While the two approaches are
theoretically incomparable, the former yields empirically better results
(Müller et al., 2022).

Early complete verification methods relied on off-the-shelf SMT (Katz et al.,
2017; Ehlers, 2017) or MILP solvers (Dutta et al., 2018; Tjeng et al., 2019).
However, these methods do not scale beyond small networks. In order to
overcome these limitations, Bunel et al. (2020) formulated a BaB style
framework for complete verification and showed it contains many previous
methods as special cases. The basic idea is to recursively split the
verification problem into easier subproblems on which cheap incomplete methods
can show robustness. Since then, a range of partially (Xu et al., 2021) or
fully (Wang et al., 2021; Palma et al., 2021) GPU-based BaB frameworks have
been proposed. The most closely related, Palma et al. (2021), leverages the
multi-neuron constraints from Tjandraatmadja et al. (2020) but yields an
optimization problem of different structure, as constraints only ever include
single output neurons.

#### Branching

Most ReLU branching methods proposed to date use the bound improvement of the
two child subproblems as the metric to decide which node to branch on next.
Full strong branching (Applegate et al., 1995) exhaustively evaluates this for
all possible branching decisions. However, this is intractable for all but the
smallest networks. Lu & Kumar (2020) train a GNN to imitate the behavior of
full strong branching at a fraction of the cost, but transferability remains
an open question and collecting training data to imitate is costly. Bunel et
al. (2020) proposed an efficiently computable heuristic score, locally
approximating the bound improvement of a branching decision using the method
of Wong & Kolter (2018). Henriksen & Lomuscio (2021) refine this approach by
additionally approximating the indirect effect of the branching decision,
however, this requires using two different bounding procedures. De Palma et
al. (2021) introduced filtered-smart-branching (FSB), using BaBSR to select
branching candidates and then computing a more accurate heuristic score only
for the selected candidates. Instead of targeting the largest bound
improvement, Kouvaros & Lomuscio (2021) aim to minimize the number of unstable
neurons by splitting the ReLU node with the most other ReLU nodes depending on
it.

##  6 Conclusion

We propose the complete neural network verifier MN-BaB. Building on the
Branch-and-Bound methodology, MN-BaB leverages tight multi-neuron constraints,
a novel branching heuristic and an efficient dual solver, able to utilize
massively parallel hardware accelerators, to enable the verification of
particularly challenging networks. Our thorough empirical evaluation shows how
MN-BaB is particularly effective in verifying challenging networks with high
natural accuracy and practical relevance, reaching a new state-of-the-art in
several settings.

##  7 Ethics Statement

Most machine learning based systems can be both employed with ethical as well
as malicious purposes. Methods such as ours that enable the certification of
robustness properties of neural networks are a step towards more safe and
trustworthy AI systems and can hence amplify any such usage. Further,
malicious actors might aim to convince regulators that the proposed approach
is sufficient to show robustness to perturbations encountered during real
world application, which could lead to insufficient regulation in safety
critical domains.

##  8 Reproducibility Statement

We will make all code and trained networks required to reproduce our
experiments available during the review process as supplementary material and
provide instructions on how to run them. Upon publication, we will also
release them publicly. We explain the basic experimental setup in Section 4
and provide more details in Section A. All datasets used in the experiments
are publicly available. Random seeds are fixed where possible and provided in
the supplementary material.

## References

  * lan (1960) An automatic method of solving discrete programming problems.  _Econometrica_ , 28(3), 1960.  ISSN 00129682, 14680262.
  * Applegate et al. (1995) David Applegate, Robert Bixby, Vašek Chvátal, and William Cook.  Finding cuts in the tsp (a preliminary report).  Technical report, Citeseer, 1995.
  * Bunel et al. (2020) Rudy Bunel, P Mudigonda, Ilker Turkaslan, P Torr, Jingyue Lu, and Pushmeet Kohli.  Branch and bound for piecewise linear neural network verification.  _Journal of Machine Learning Research_ , 21(2020), 2020\.
  * Cohen et al. (2019) Jeremy M. Cohen, Elan Rosenfeld, and J. Zico Kolter.  Certified adversarial robustness via randomized smoothing.  In _Proc. of ICML_ , volume 97, 2019.
  * Dathathri et al. (2020) Sumanth Dathathri, Krishnamurthy Dvijotham, Alexey Kurakin, Aditi Raghunathan, Jonathan Uesato, Rudy Bunel, Shreya Shankar, Jacob Steinhardt, Ian J. Goodfellow, Percy Liang, and Pushmeet Kohli.  Enabling certification of verification-agnostic networks via memory-efficient semidefinite programming.  In _Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurIPS 2020, December 6-12, 2020, virtual_ , 2020.
  * De Palma et al. (2021) Alessandro De Palma, Rudy Bunel, Alban Desmaison, Krishnamurthy Dvijotham, Pushmeet Kohli, Philip HS Torr, and M Pawan Kumar.  Improved branch and bound for neural network verification via lagrangian decomposition.  _ArXiv preprint_ , abs/2104.06718, 2021.
  * Deng (2012) Li Deng.  The mnist database of handwritten digit images for machine learning research.  _IEEE Signal Processing Magazine_ , 29(6), 2012.
  * Dutta et al. (2018) Souradeep Dutta, Susmit Jha, Sriram Sankaranarayanan, and Ashish Tiwari.  Output range analysis for deep feedforward neural networks.  In _NASA Formal Methods Symposium_. Springer, 2018.
  * Ehlers (2017) Ruediger Ehlers.  Formal verification of piece-wise linear feed-forward neural networks.  In _International Symposium on Automated Technology for Verification and Analysis_. Springer, 2017.
  * Gehr et al. (2018) Timon Gehr, Matthew Mirman, Dana Drachsler-Cohen, Petar Tsankov, Swarat Chaudhuri, and Martin Vechev.  Ai2: Safety and robustness certification of neural networks with abstract interpretation.  In _2018 IEEE Symposium on Security and Privacy (SP)_. IEEE, 2018\.
  * Gowal et al. (2018) Sven Gowal, Krishnamurthy Dvijotham, Robert Stanforth, Rudy Bunel, Chongli Qin, Jonathan Uesato, Relja Arandjelovic, Timothy Mann, and Pushmeet Kohli.  On the effectiveness of interval bound propagation for training verifiably robust models.  _ArXiv preprint_ , abs/1810.12715, 2018.
  * Henriksen & Lomuscio (2021) Patrick Henriksen and Alessio Lomuscio.  Deepsplit: An efficient splitting method for neural network verification via indirect effect analysis.  In _Proceedings of the 30th International Joint Conference on Artificial Intelligence (IJCAI21), To appear_ , 2021.
  * Katz et al. (2017) Guy Katz, Clark Barrett, David L Dill, Kyle Julian, and Mykel J Kochenderfer.  Reluplex: An efficient smt solver for verifying deep neural networks.  In _International Conference on Computer Aided Verification_. Springer, 2017.
  * Kouvaros & Lomuscio (2021) Panagiotis Kouvaros and Alessio Lomuscio.  Towards scalable complete verification of relu neural networks via dependency-based branching.  In _Proceedings of the 30th International Joint Conference on Artificial Intelligence (IJCAI21), To Appear_ , 2021.
  * Krizhevsky et al. (2009) Alex Krizhevsky, Geoffrey Hinton, et al.  Learning multiple layers of features from tiny images.  2009\.
  * Lu & Kumar (2020) Jingyue Lu and M. Pawan Kumar.  Neural network branching for neural network verification.  In _Proc. of ICLR_ , 2020.
  * Madry et al. (2018) Aleksander Madry, Aleksandar Makelov, Ludwig Schmidt, Dimitris Tsipras, and Adrian Vladu.  Towards deep learning models resistant to adversarial attacks.  In _Proc. of ICLR_ , 2018.
  * Müller et al. (2022) Mark Niklas Müller, Gleb Makarchuk, Gagandeep Singh, Markus Püschel, and Martin Vechev.  Prima: General and precise neural network certification via scalable convex hull approximations.  _Proc. ACM Program. Lang._ , 6(POPL), jan 2022.  doi: 10.1145/3498704.  URL https://doi.org/10.1145/3498704.
  * Palma et al. (2021) Alessandro De Palma, Harkirat S. Behl, Rudy R. Bunel, Philip H. S. Torr, and M. Pawan Kumar.  Scaling the convex barrier with active sets.  In _Proc. of ICLR_ , 2021.
  * Paszke et al. (2019) Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, Alban Desmaison, Andreas Köpf, Edward Yang, Zachary DeVito, Martin Raison, Alykhan Tejani, Sasank Chilamkurthy, Benoit Steiner, Lu Fang, Junjie Bai, and Soumith Chintala.  Pytorch: An imperative style, high-performance deep learning library.  In _Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, NeurIPS 2019, December 8-14, 2019, Vancouver, BC, Canada_ , 2019.
  * Salman et al. (2019) Hadi Salman, Greg Yang, Huan Zhang, Cho-Jui Hsieh, and Pengchuan Zhang.  A convex relaxation barrier to tight robustness verification of neural networks.  In _Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, NeurIPS 2019, December 8-14, 2019, Vancouver, BC, Canada_ , 2019.
  * Singh et al. (2018) Gagandeep Singh, Timon Gehr, Matthew Mirman, Markus Püschel, and Martin T. Vechev.  Fast and effective robustness certification.  In _Advances in Neural Information Processing Systems 31: Annual Conference on Neural Information Processing Systems 2018, NeurIPS 2018, December 3-8, 2018, Montréal, Canada_ , 2018.
  * Singh et al. (2019a) Gagandeep Singh, Rupanshu Ganvir, Markus Püschel, and Martin T. Vechev.  Beyond the single neuron convex barrier for neural network certification.  In _Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, NeurIPS 2019, December 8-14, 2019, Vancouver, BC, Canada_ , 2019a.
  * Singh et al. (2019b) Gagandeep Singh, Timon Gehr, Markus Püschel, and Martin Vechev.  An abstract domain for certifying neural networks.  _Proceedings of the ACM on Programming Languages_ , 3(POPL), 2019b.
  * Singh et al. (2019c) Gagandeep Singh, Timon Gehr, Markus Püschel, and Martin T. Vechev.  Boosting robustness certification of neural networks.  In _Proc. of ICLR_ , 2019c.
  * Sriramanan et al. (2020) Gaurang Sriramanan, Sravanti Addepalli, Arya Baburaj, and Venkatesh Babu R.  Guided adversarial attack for evaluating and enhancing adversarial defenses.  In _Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurIPS 2020, December 6-12, 2020, virtual_ , 2020.
  * Tjandraatmadja et al. (2020) Christian Tjandraatmadja, Ross Anderson, Joey Huchette, Will Ma, Krunal Patel, and Juan Pablo Vielma.  The convex relaxation barrier, revisited: Tightened single-neuron relaxations for neural network verification.  In _Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurIPS 2020, December 6-12, 2020, virtual_ , 2020.
  * Tjeng et al. (2019) Vincent Tjeng, Kai Y. Xiao, and Russ Tedrake.  Evaluating robustness of neural networks with mixed integer programming.  In _Proc. of ICLR_ , 2019.
  * Wang et al. (2021) Shiqi Wang, Huan Zhang, Kaidi Xu, Xue Lin, Suman Jana, Cho-Jui Hsieh, and J Zico Kolter.  Beta-crown: Efficient bound propagation with per-neuron split constraints for neural network robustness verification.  In _ICML 2021 Workshop on Adversarial Machine Learning_ , 2021.
  * Wong & Kolter (2018) Eric Wong and J. Zico Kolter.  Provable defenses against adversarial examples via the convex outer adversarial polytope.  In _Proc. of ICML_ , volume 80, 2018.
  * Xu et al. (2020) Kaidi Xu, Zhouxing Shi, Huan Zhang, Yihan Wang, Kai-Wei Chang, Minlie Huang, Bhavya Kailkhura, Xue Lin, and Cho-Jui Hsieh.  Automatic perturbation analysis for scalable certified robustness and beyond.  In _Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurIPS 2020, December 6-12, 2020, virtual_ , 2020.
  * Xu et al. (2021) Kaidi Xu, Huan Zhang, Shiqi Wang, Yihan Wang, Suman Jana, Xue Lin, and Cho-Jui Hsieh.  Fast and complete: Enabling complete neural network verification with rapid and massively parallel incomplete verifiers.  In _Proc. of ICLR_ , 2021.
  * Zhang et al. (2021) Linjun Zhang, Zhun Deng, Kenji Kawaguchi, Amirata Ghorbani, and James Zou.  How does mixup help with robustness and generalization?  In _Proc. of ICLR_ , 2021.

##  Appendix A Experiment Details

Table 3: Overview of the experimental configuration for every network. Dataset | Model | Training | Timeout | Batch sizes |  #Activation Layers |  #Activation Nodes
---|---|---|---|---|---|---
MNIST | ConvSmall | NOR | 360 | [100, 200, 400] | 3 | 3 604
| ConvBig | DiffAI | 2000 | [2, 2, 4, 8, 12, 20] | 6 | 34 688
| ConvSuper | DiffAI | 360 | [1, 2, 2, 3, 4, 8] | 6 | 88 500
CIFAR10 | ConvSmall | PGD | 360 | [100, 150, 250] | 3 | 4 852
| ConvBig | PGD | 500 | [3, 3, 6, 6, 8, 16] | 6 | 62 464
| ResNet6-A | PGD | 600 | [4, 4, 8, 12, 16, 100] | 6 | 10 340
| ResNet6-B | PGD | 600 | [4, 8, 32, 64, 128, 256] | 6 | 10 340
| ResNet8-A | PGD | 600 | [2, 2, 2, 4, 8, 16, 32, 64] | 8 | 11 364

In Table 3 we show the per-sample timeout and the batch sizes that were used
in the experiments. The timeouts for the first 4 networks were chosen to
approximately match the average runtimes reported by Wang et al. (2021), to
facilitate comparability.

Since we keep intermediate bounds of neurons before the split layer fixed, as
described in Section 3.2, the memory requirements for splitting at different
layers can vary. We exploit this fact and choose batch sizes for our bounding
procedure depending on the layer where the split occurred.

In order to falsify properties more quickly, we run a strong adversarial
attack with the following parameters before attempting certification: We apply
two targeted versions (towards all classes) of PGD (Madry et al., 2018) using
margin loss (Gowal et al., 2018) and GAMA loss (Sriramanan et al., 2020), both
with $5$ restarts, $50$ steps, and $10$ step output diversification
(TashiroSE20).

###  A.1 Architectures

In this section, we provide an overview of all the architectures evaluated in
Section 4. The architectures of the convolutional networks for MNIST and
CIFAR10 are detailed in Table 4. The architectures of both ResNet6-A and
ResNet6-B are given in Table 5

Table 4: Network architectures of the convolutional networks for CIFAR10 and
MNIST. All layers listed below are followed by an activation layer. The output
layer is omitted. ‘Conv c h$\times$w/s/p’ corresponds to a 2D convolution with
c output channels, an h$\times$w kernel size, a stride of s in both
dimensions, and an all-around zero padding of p.

ConvSmall | ConvBig | ConvSuper
---|---|---
Conv 16 4$\times$4/2/0 |  Conv 32 3$\times$3/1/1 |  Conv 32 3$\times$3/1/0
Conv 32 4$\times$4/2/0 |  Conv 32 4$\times$4/2/1 |  Conv 32 4$\times$4/1/0
FC 100 |  Conv 64 3$\times$3/1/1 |  Conv 64 3$\times$3/1/0
|  Conv 64 4$\times$4/2/1 |  Conv 64 4$\times$4/1/0
|  FC 512 |  FC 512
|  FC 512 |  FC 512

Table 5: Network architecture of the ResNet6 and ResNet8. All layers listed
below are followed by a ReLU activation layer, except if they are followed by
a ResAdd layer. The output layer is omitted. ‘Conv c h$\times$w/s/p’
corresponds to a 2D convolution with c output channels, an h$\times$w kernel
size, a stride of s in both dimensions, and an all-around zero padding of p.

ResNet6 | ResNet8
---|---
Conv 16 3$\times$3/1/1 |  Conv 16 3$\times$3/2/1
Conv 32 1$\times$1/2/0 |  Conv 32 3$\times$3/2/1 | Conv 32 1$\times$1/2/0 |  Conv 32 3$\times$3/2/1
|  Conv 32 3$\times$3/1/1 |  |  Conv 32 3$\times$3/1/1
ResAdd | ResAdd
Conv 64 1$\times$1/2/0 |  Conv 64 3$\times$3/2/1 | Conv 64 1$\times$1/2/0 |  Conv 64 3$\times$3/2/1
|  Conv 64 3$\times$3/1/1 |  |  Conv 64 3$\times$3/1/1
ResAdd | ResAdd
FC 100 | Conv 128 1$\times$1/2/0 |  Conv 128 3$\times$3/2/1
|  |  |  Conv 128 3$\times$3/1/1
|  | ResAdd
|  |  FC 100

##  Appendix B Split-Cost Computation for CAB

Recall that for CAB, we normalize the branching score obtained with an
arbitrary branching heuristic with the (approximate) cost of the corresponding
split. The true cost of a split consists of the direct cost of the next
branching step and the change of cumulative cost for all consecutive steps. As
a local approximation, we just consider the former component.

We approximate this direct cost by the number of floating-point operations
required to compute the new bounds. This is computed as the sum of floating-
point operations required for bounding all intermediate bounds that are
recomputed. Our bounding approach only enforces constraints on neurons
preceding the neurons included in the bounding objective. Hence, we only
recompute intermediate bounds for layers after the layer where the split
occurs, as discussed in Section 3.2.

To compute the cost of recomputing the lower (or upper) bound of one
intermediate node, we add up all floating point operations needed to perform
the backsubstitution described in Section 3.1. As backsubstitution is just a
series of matrix multiplications, the number of required floating point
operations can be deduced from the sizes of the multiplied matrices.

Thus if we split on layer $k$ of an $L$ layer network and the cost of
backsubstituion from layer $i$ is $C_{i}$ and the number of nodes is $d_{i}$,
the final cost of the split is:

$\sum_{i=k+1}^{L}2d_{i}C_{i}$

Where the factor $2$ comes from the fact that for intermediate bounds we need
to recompute both lower and upper bounds. The cost $C_{i}$ of a full
backsubstitution from layer $i$ can be computed as the sum over the cost of
backsubstituting through all preceding layers $C_{i}=\sum_{j=0}^{i-1}c_{j}$,
where the cost for a single layer can be computed as follows:

  * •

ReLU layer: $c_{j}=d_{j}+p_{j}$, where $p_{j}$ is the number of multi-neuron
constraints.

  * •

Linear layer: $c_{j}=\\#W_{j}$, where $\\#W_{j}$ is the number of elements in
the weight matrix.

  * •

Conv layer: $c_{j}=d_{j}k_{j}^{2}$, where $k_{j}$ is the kernel size.


# Ed-Fed: A generic federated learning framework with resource-aware client
selection for edge devices

Zitha Sasindran, Harsha Yelchuri, T. V. Prabhakar  Department of Electronic
Systems Engineering
Indian Institute of Science
Bengaluru, India, 560012.
Email: {zithas, harshay<EMAIL_ADDRESS>
###### Abstract

Federated learning (FL) has evolved as a prominent method for edge devices to
cooperatively create a unified prediction model while securing their sensitive
training data local to the device. Despite the existence of numerous research
frameworks for simulating FL algorithms, they do not facilitate comprehensive
deployment for automatic speech recognition tasks on heterogeneous edge
devices. This is where Ed-Fed, a comprehensive and generic FL framework, comes
in as a foundation for future practical FL system research. We also propose a
novel resource-aware client selection algorithm to optimise the waiting time
in the FL settings. We show that our approach can handle the straggler devices
and dynamically set the training time for the selected devices in a round. Our
evaluation has shown that the proposed approach significantly optimises
waiting time in FL compared to conventional random client selection methods.

##  I Introduction

With the advances in hardware and software technologies, edge devices are
becoming increasingly powerful and intelligent. This enables the researchers
to bring machine intelligence from cloud-based data centres to edge devices
such as mobile phones. For instance, Google Pixel’s “Now Playing” option which
allows us to recognise any song without internet and “recorder” app with on-
device speaker diarization show how powerful the mobile phones are becoming.
Federated learning (FL) [1] introduces an additional dimension in the machine
learning community in which models are collaboratively trained on edge
devices, with the data remaining local to the device, in contrast to the
centralised training approach, and hence ensures the data privacy of the
users. A general FL setting consists of a set of clients (edge devices) and a
server. The server randomly chooses a subset of the devices from the available
ones that want to take part in the FL round. A copy of the global model, which
the server maintains, is first sent to this subset of clients. These clients
use their data in the device to train models locally, and then send the
updated weights back to the server. In conventional FL, the server cannot move
on to the next step until it has received updates from every client. As a
result, FL performance is constrained by the variability in waiting time
experienced by each client due to model training on the device or
communication delay during the transfer of model weights to the server. These
slowdowns caused by the clients with weaker network connections or limited
computation capabilities is known as “straggler effect”. Once the server gets
the updates from all the selected clients, the weights are aggregated using a
strategy. This process is repeated for several rounds until the global model
achieves the desired accuracy.

The random client selection approach for FL works well when there are no
straggler devices. Prioritising for resource rich devices every time will
result in the inability of straggler devices to participate in the FL process,
and can lead to a loss of generalisation in the global model and fairness in
the learning process. To address this challenge, a more sophisticated client
selection algorithm is needed that considers the presence of stragglers while
minimising waiting time. Hence the algorithm should aim to balance the
participation of straggler devices with less waiting time and fairness in the
FL process. Current FL frameworks face several challenges when it comes to
deployment on edge devices such as mobile phones. These devices often have
limited memory and computational resources, which makes it difficult to store
and execute complex models. To overcome the existing challenges and make FL a
practical and scalable solution for edge devices, it is important to develop
FL frameworks that are designed specifically for these devices, taking into
account their computational, privacy, and power constraints.

We provide a methodology for training the models on the device, along with an
efficient client selection algorithm to handle straggler devices and FL
functionalities, allowing them to be deployed on edge devices for FL settings.
We also monitor the client devices’ resources to ensure that they continue to
function seamlessly even in dynamic environments. Since this work is related
to client selection, we do not consider asynchronous federated learning
approaches. In this paper, we focus on the use case of automatic speech
recognition (ASR), demonstrating how our FL framework can be used to improve
the accuracy and robustness of speech recognition models. We summarise our
contributions as follows:

  * •

We present Ed-Fed, an end-to-end FL framework for edge devices with a
resource-aware time-optimised client selection algorithm.

  * •

We provide a complete methodology for training entire or fine tuned models on
mobile phones with support for FL related functionalities.

  * •

We formulate a client selection algorithm by considering the computation,
storage, power, and phone-specific capabilities of the client devices with
ability to handle stragglers, optimise the waiting time and adaptively assign
the training time for devices based on the these information.

  * •

We demonstrate the implementation with deployments on multiple mobile phones
to quantify the waiting time in client selection.

  * •

We present an extensive evaluation of our framework on both simulations and
mobile phone settings using a custom created audio corpus with a heterogeneous
set of speakers.

This paper is organised as follows. We provide a brief literature survey in
Section II. Then, we discuss briefly about our Ed-Fed framework for FL
settings in Section III. In Section IV, we discuss our proposed resource-aware
client selection algorithm used in the server, followed by the framework
evaluation in Section V and results in Section VI. Finally, concluding remarks
are presented in Section VII.

##  II Related works

FL Framework Recently, there has been a lot of interest in training ASR models
in FL settings [2, 3, 4, 5, 6]. Implementing ASR for federated settings in
mobile phones is a challenge in itself due to the complex model architectures
and dynamic nature of the speech signals, as well as the limited resources
available in mobile devices. Furthermore, due to factors such as noisy
backgrounds, multiple accented speech, and different voice characteristics
such as gender, pitch, phonation, loudness and tempo, the local speech data
available on devices are non-IID in nature. This further complicates the
training of ASR models. Several FL frameworks, including TensorFlow-Federated
(TFF) [7], and LEAF [8], support only the simulation of FL systems and do not
propose an edge device deployment. Flower framework [9], on the other hand,
supports extending FL settings to edge devices. However, we can see that the
ASR task with the flower framework is also limited to system-level simulations
[2]. Moreover, they provide only transfer learning techniques [10] but not
entire retraining of the model from scratch. To the best of our knowledge, no
existing framework has provided a comprehensive implementation of ASR on-
device training, as well as FL settings for mobile phones.

Client selection  We focus mainly on bandit based client selection techniques
in FL. In [11], the authors formulated the client selection as a traditional
multi-arm bandit based problem to select clients with better quality of data
to improve the FL accuracy. The authors proposed upper confidence bound based
client selection in [12, 13] with the goal of reducing the overall time
consumption of FL training including transmission time and local computation
time. In [14], the authors intelligently select clients by exploiting the data
correlations among clients to improve FL learning performance. However, none
of these studies used actual computation resource information from the devices
to explain training latency. Meanwhile, [15] took a similar approach to ours,
taking into account resource information and grouping clients accordingly.
Even though the clients with similar resources are selected together, the need
for adaptive setting training epochs is needed to control the stragglers.
Furthermore, they did not take the battery information into account, which is
critical.

##  III Ed-Fed framework

This section provides a detailed overview of our Ed-Fed framework. We first
discuss the methodology for facilitating on-device training and weight
updation of models in the clients, followed by a brief overview on the
communication protocol and the server-side algorithms used.

###  III-A Client

It is critical to develop a better methodology for converting a larger global
model to a memory efficient and optimised version suitable for edge devices.
We use TensorFlow [16] to create a well-optimised Flatbuffer format based
conversion, which allows for significant model size reduction. We use the
signature functions in Tensorflow to interface with the optimised model and
perform operations such as training, inference, loading and saving the
checkpoint weights, as described in [17, 18]. Furthermore, we build extra
signature functions specifically for FL configuration to aid in efficient
communication between clients and server. Figure 1 depicts the optimised model
with eight signature functions that allow us to successfully train the model
on the device, and perform FL related functions in the mobile devices. Along
with the existing signature functions such as train, evaluate, save, load, and
calculate_loss, we build three new signature functions:

  * •

Get_1D_weights: reshapes an N-dimensional weight tensor from each node in the
model graph to a 1-D array and returns a list of 1-D arrays.

  * •

Get_nodenames_shapes: returns all the node names as well as the actual tensor
shapes.

  * •

Set_weights: reshape the aggregated 1-D weight array to N-D tensor and reloads
it into the model.

Figure 1: Optimised model created for on-device training and FL setup

One key functionality of these signatures is packing and unpacking the weights
into 1-D and N-D arrays respectively. In [19], the authors explained that
important sensitive data can be decoded if an intruder gets access to weights
during communication. But if the weights are packed into a 1-D array, private
information like shape of the weight matrices of each layer which can give
useful insights about the model architecture and data patterns are hidden.
These three main signatures, Get_1D_weights, Get_nodenames_shapes and
Set_weights not only facilitate in implementing Ed-Fed framework but also
induce privacy to the framework.

Due to the limited resources available in the edge devices, we prevent
repeated storing of checkpoints after each epoch of training. Instead, we
update a single checkpoint throughout the training. Hence, the optimised model
(tflite) generated with the signature functions has all the functionalities
which include support for training the models efficiently on the device as
well as FL-based weight updation. The optimised model is utilised in our
android application and our simulation systems, hence facilitating end-to-end
real-time FL.

###  III-B Communication protocol

We use the gRPC [20] communication protocol to ensure efficient communication
between the server and clients. gRPC, like many RPC systems, is built on the
concept of establishing a service, which describes the methods that can be
called remotely with their input and return types. Protocol buffers are the
most common interface definition language (IDL) used by gRPC to describe both
the service interface and the message structure of the payloads. In our
framework, three RPCs were used. “CommunicatedText” is the first, which is
used to send the current context of the client and server. “GetGlobalWeights”
is the second, which is used to send the current global FL weights to the
clients who have been chosen for training. The final one is “GetFLWeights,”
which is used to share the aggregated weights between the server and client.

###  III-C Server

On the server side, there are two major components: the Client selection with
fairness and Aggregation strategy. Client selection involves selecting $k$
clients out of $N$ available clients. In case of waiting time optimised client
selection algorithms, the clients should be selected in such a way that the
overall waiting time of the clients is minimised, while ensuring fairness in
the selection of clients. More about the client selection algorithms is
discussed in further sections.

The weight aggregation is an integral part of FL. The server strategy
algorithms aggregates the weights ($w_{t}^{i}$) obtained from the selected $k$
clients by choosing algorithms such as FedAvg [1], FedProx [21], etc., and the
updated weights are sent back to the clients. Typically, in real-world
settings the client’s local data will not be representative of the global data
distribution because of the noisy background or the different voice
characteristics. Hence, simply aggregating weights from such clients with low
quality data will lead to a deviation from the global model. An improved
solution is to generate a weighted aggregation of the models, with a weighting
coefficient reflecting the quality of the model [2]. A client with a higher
word error rate (WER) denotes poor performance of the global model. In such
cases, we assign a lower weighting coefficient to that model during the
aggregation. We use a weighted WER-based strategy in our Ed-Fed setting and is
denoted as follows:

$\displaystyle w_{t+1}\leftarrow\sum_{i=1}^{k}\alpha_{i}w^{i}_{t+1}$ (1)
$\displaystyle\alpha_{i}=\frac{\exp(1-{WER}_{i})}{\sum_{j=1}^{k}\exp(1-{WER}_{j})}$
(2)

where the weights $\alpha_{i}$’s are calculated using the softmax distribution
obtained from the WER values from multiple clients.

Once clients are selected for training, the server notifies them to start
training. The clients begin their training, and once they complete their
training, they send their updated weight to the server. The server then
aggregates them through a weight aggregation strategy. The aggregation
strategy considers the uncertainties in the quality and quantity of data by
using the WER based weighting used by each client obtained during the training
process.

##  IV Resource-aware time-optimised client selection

###  IV-A Need for waiting time optimisation

Figure 2: Scenario 1: Slow vs Fast client.

Figure 3: Scenario 2: One client with insufficient battery life.

Waiting time is the amount of time the client waits for server to fulfill the
request. This is mainly observed when the clients send their updated weights
and request the aggregated weights to be returned by the server. Since client
platforms have different training times, the server cannot compute the
aggregated weights until responses are obtained from all clients, leading to
higher waiting times for clients with faster computing capabilities.

To quantify the waiting time, we considered two common scenarios : (1) Select
one fast client and one slow client and (2) Select one client with
insufficient battery life made to run more number of epochs. Figure 3 shows
client 1 having higher compute capabilities which has waited for a significant
amount of time for the slower client 2 to finish its training process. Figure
3 presents the results of the experiment (Scenario 2). We can see that client
1 switches off in the middle of training, making client 2 wait for an infinite
amount of time.

Considering all these problems, we created a resource-aware time-optimized
client selection algorithm which takes the resources of the clients into
consideration and assigns work adaptively to each client depending on that
client’s resources. Our approach has three important phases, a resource
information extraction, neural reward generation and a resource-aware time-
optimised algorithm for clients.

###  IV-B Resource information

We aim to investigate the relationship between the resource availability and
the fluctuations in the training time. We also aim to assess the impact of
training on battery drain, which is crucial in real-world scenarios to prevent
device shutdown during extended usage. The different resources which we
considered for estimating the training time and battery drain of a particular
phone are (1) memory-related information, (2) power-related information, (3)
CPU-usage-related information (CI), and, (4) phone-specific information (PI).
Memory-related information is captured using: (a) total RAM ($TR$), and, (b)
available RAM ($AR$). In case of power-related information, (a) available
battery charge ($AC$) and (b) battery status ($BS$) are used. For $CI$, the
average usage of CPU across multiple cores is used. In order to find the $PI$,
we used the Antutu score. The breakup of these resources into individual
components is important because each of these can individually effect the
training time. All these resources together form the context information of
the client device, i.e., $c=\left[TR,AR,AC,BS,CI,PI\right]$. Obtaining context
information from the phone before each FL round is important as time taken to
complete the training process depends on it. We make use of this information
by training a neural network to understand these dependencies and predict the
expected training time and battery charge consumption based on a context
vector. Once, we get to estimate these two parameters of each client, we can
group clients together in a manner that minimises the waiting time of each
client.

###  IV-C Neural reward generator

Data: $\text{Number of training rounds}~{}T,\text{exploration parameters}$

$~{}\\{\alpha_{t}\\}_{t\in T},\text{Hidden layer size}~{}m,\text{Context
vectors at }t^{th}$

$\text{ round: }\\{c_{t,s}|s\in\\{1\cdots N\\}\\}$

$\text{{Initialisation:}}~{}\text{Randomly
initialise}~{}\boldsymbol{\theta_{0}^{s}},$
$\mathbf{Z}_{0,s}=\lambda\mathbf{I}~{}\forall s\in{1\cdots N}$

for  _t=1 _ to_ T_ do

for  _s=1 _ to_ N_ do

$\left[\hat{b\\_t}_{t,s},\hat{d}_{t,s}\right]\leftarrow
f_{s}(\mathbf{c_{t,s}};\boldsymbol{\theta}_{t-1}^{s})$

$U_{t,s}\leftarrow-\hat{b\\_t}_{t,s}+\alpha_{t}\sqrt{\nabla{f_{s}(\mathbf{c_{t,s}};\boldsymbol{\theta}_{t-1}^{s})}^{T}\mathbf{Z}_{t-1,s}^{-1}\nabla{f_{s}(\mathbf{c_{t,s}};\boldsymbol{\theta}_{t-1}^{s})}/m}$

end for

$S_{t}\leftarrow\text{Top}~{}min(k,|U_{t}|)~{}\text{clients from}~{}U_{t}$

$\text{Run the clients}~{}s\in S_{t}~{}\text{and get the true
}$$\left[{b\\_t}_{t,s},{d}_{t,s}\right]$

$\text{Update}~{}\mathbf{Z}_{t,s}\leftarrow\mathbf{Z}_{t-1,s}+\nabla{f_{s}(\mathbf{c_{t,s}};\boldsymbol{\theta}_{t-1}^{s})}^{T}\nabla{f_{s}(\mathbf{c_{t,s}};\boldsymbol{\theta}_{t-1}^{s})}/m$

$\mathbf{D}_{t,s}\leftarrow\mathbf{D}_{t-1,s}\cup(\mathbf{c_{t,s}},\left[{b\\_t}_{t,s},{d}_{t,s}\right])$

$\boldsymbol{\theta}_{t}^{s}\leftarrow\text{TrainNN}\left(\mathbf{D}_{t,s},\boldsymbol{\theta}_{t-1}^{s}\right)$

end for

Algorithm 1 NeuralUCB-m

In this section, our goal is to learn the training time, and battery drop
based on the given resources. Further, use these values to learn a better
client selection by removing straggler clients or by doing an adaptive setting
of the training time for clients. We will first give a brief overview of the
basic contextual combinatorial multi-armed bandits (CC-MAB) problem using
neural upper confidence bound (NeuralUCB)[22] policy. We will then use this in
our FL framework setting to optimise the overall waiting time, based on the
context information.

We formulate our client selection problem as a CC-MAB setting with $N$ arms in
which the agent interacts with the arms for $T$ rounds. Initially, the true
rewards generated by the arms are unknown, and the agent observes only the $N$
context vectors from corresponding arms:
$\\{\mathbf{c_{t,s}}\in\mathbb{R}^{d}|s\in\\{1\cdots N\\}\\}$. Let
$\mathbf{S}\subseteq 2^{N}$ be the set of all proper subsets of $N$ available
arms in the setting. At each round $t$, the agent predicts the rewards
$\\{\hat{r}_{t,s}\\}_{s\in\mathbf{S_{t}}}$ using a reward estimating function
$(f)$ parameterised by $\boldsymbol{\theta}$, such that
$\hat{r}_{t,s}=f(\mathbf{c_{t,s}};\boldsymbol{\theta})$. Then, the agent
selects a subset, $\mathbf{S_{t}}\in\mathbf{S}$ containing $k$ arms based on
the calculated rewards. In most cases, the agent is aware of the parametric
form of the reward estimating function that is being used. In linear upper
confidence bound problems (LinUCB)[23], for example, the reward is calculated
as $\hat{r}_{t,s}=\boldsymbol{\theta_{*}}^{T}\mathbf{c_{t,s}}$. After playing
the arms in $\mathbf{S_{t}}$, the agent observes the true rewards given as
$\\{r_{t,s}\\}_{s\in\mathbf{S_{t}}}$. The goal of the agent is to maximise the
expected reward, which is equivalent to minimising $R_{T}$, the cumulative
regret over $T$ rounds:

$R_{T}=\mathbb{E}\left[\sum_{t=1}^{T}\left(\sum_{s\in\mathbf{S^{*}_{t}}}r_{t,s}-\sum_{s\in\mathbf{S_{t}}}\hat{r}_{t,s}\right)\right]$
(3)

where $\mathbf{S^{*}_{t}}$ is the set of $k$ optimal arms with maximum true
rewards at round $t$.

Unlike the classical linear contextual bandit where the reward estimating
function $f(\mathbf{c_{t,s}};\boldsymbol{\theta})$ is linear, we utilises a
neural network to deal with the intricate relationship between context
features and rewards. The neural network based reward estimating function
$f(\mathbf{c_{t,s}};\boldsymbol{\theta})$ estimates the expected reward of an
action based on past observations, and is parameterised as:

$f(\mathbf{c_{t,s}};\boldsymbol{\theta})=\sqrt{m}\mathbf{W_{L}}\sigma\left(\mathbf{W_{L-1}}\sigma\left(\cdots\sigma\left(\mathbf{W_{1}}\left(\mathbf{c_{t,s}}\right)\right)\right)\right)$
(4)

where $L$ is the total number of hidden layers, $m$ is the hidden layer size
(assumed to be same for all the layers for convenience), $\sigma$ is the
activation function, and $\mathbf{W_{l}}$ corresponds to the weight matrix in
$l^{\text{th}}$ layer. Here $\boldsymbol{\theta}$ is the vectorised weight
matrices from all the hidden layers in the neural network and is given as
$\boldsymbol{\theta}=\left[\text{vec}(\mathbf{W_{1}}^{T}),\text{vec}(\mathbf{W_{2}}^{T})\cdots\text{vec}(\mathbf{W_{L}}^{T})\right]$.

Our proposed approach for client selection considers the clients or edge
devices participating in FL as the arms with resource information discussed in
Section IV-B as the context vectors. We also observe that using a single
reward generation model $f(\mathbf{c_{t,s}};\boldsymbol{\theta}_{t-1})$ for
multiple client devices (NeuralUCB-s) may lead to performance degradation if
the edge devices have different intrinsic characteristics such as age and
usage history. For example, consider two identical phones, one of which has
been in use for 5 years and the other of which is brand new. However, if we
calculate the training time and battery drop of both phones under similar
contexts, they do not match. We see that the older phone performs badly and
drains faster due to the aging of batteries. Also, it is dependent on how
extensively the phone is used over time. If we use a single model, we miss out
on these relationships, and the model gets confused if such clients exist in
our rounds with degradation in performance. On the other hand, personalised
reward generation models
$f_{s}(\mathbf{c_{t,s}};\boldsymbol{\theta}_{t-1}^{s})$ (NeuralUCB-m), can
better adapt to the unique characteristics of each client device and provide
more accurate results. In our approach, the neural network predicts the
training time per batch of samples and also the drop in battery percentage
given the resource information as the context vector, i.e.,
$\left[\hat{b\\_t}_{t,s},\hat{d}_{t,s}\right]=f_{s}(\mathbf{c_{t,s}};\boldsymbol{\theta}_{t-1}^{s})$.
We use the negative of training time per batch ($-\hat{b\\_t}_{t,s}$) for each
arm as the reward in the UCB setting and the battery drop is used for
straggler handling. Once the training is completed for round $t$, the clients
will send their $\left[{b\\_t}_{t,s},{d}_{t,s}\right]$ along with the updated
weights. Then, $(\mathbf{c_{t,s}},\left[{b\\_t}_{t,s},{d}_{t,s}\right])$ will
be added to the corresponding clients’ dataset ($\mathbf{D}_{t,s}$) and will
be used for training the neural network.

The detailed algorithm for neural combinatorial contextual bandits is shown in
Algorithm 1.

TABLE I: Details about mobile phone hardware. Device Model | RAM | CPU | OS | SoC
---|---|---|---|---
OnePlus 7T-1 | 4.0$|$8 GB | Octa-core Max 2.96 GHz | Oxygen 11 (Android 11) | Snapdragon 855 Plus
OnePlus 7T-2 | 4.1$|$8 GB | Octa-core Max 2.96 GHz | Oxygen 11 (Android 11) | Snapdragon 855 Plus
OnePlus 5T | 3.6$|$6 GB | Octa-core Max 2.45 GHz | Oxygen 9 (Android 9 ) | Snapdragon 835
Xiaomi 11 Pro | 4.8$|$8 GB | Octa-core Max 2.05 GHz | MIUI 13 (Android 11) | Helio G96

Data: $\text{Context vectors of clients at }t^{th}\text{ round:
}\\{c_{t,s}|s\in\\{1\cdots N\\}\\}$ $\text{Number of samples at round t:
}(n_{t,1},n_{t,2}..,n_{t,N}),$ $\text{Number of clients to be selected:
}k,\text{Minimum}$ and maximum number of epochs to run in a FL $\text{round:
}(e_{min},e_{max}),\text{Batch size: }bs,$ Battery  threshold $\gamma.$

Result: $\text{k clients along with their respective }e_{t,i}$

for  _i=1 _to_ N_ do

$\hat{b\\_t}_{t,i},~{}\hat{d}_{t,i}\leftarrow
f_{i}(\mathbf{c_{t,i}};\boldsymbol{\theta}_{t-1}^{i})$ ;

/* Step 1 */

$b_{max_{t,i}}\leftarrow\lfloor(AC_{t,i}-\gamma)/\hat{d}_{t,i}\rfloor$;

$e_{max_{t,i}}\leftarrow
min(e_{max},\lfloor(b_{max_{t,i}}/(n_{t,i}/bs))\rfloor$) ;

/* Step 2 */

if  _$e_{max_{t,i}}\geq e_{min}$_ then /* Step 3 */

$P_{t}.append(c_{t,i})$;

end if

end for

$S_{t}\leftarrow\text{NeuralUCB-m}(P_{t})$;

/* Step 4 */

$m_{t}\leftarrow 0$;

foreach  _client $i$ in $S_{t}$_ do

$m_{t}\leftarrow min(m_{t},e_{max_{t,i}}*(n_{t,i}/bs)*\hat{b\\_t}_{t,i})$ ;

/* Step 5 */

end foreach

foreach  _client $i$ in $S_{t}$_ do

$e_{t,i}\leftarrow\lfloor(m_{t}/\hat{b\\_t}_{t,i})*(bs/n_{t,i})\rfloor$ ;

/* Step 6 */

end foreach

Algorithm 2 Resource-aware time-optimised algorithm for client selection

(a) OnePlus 5T

(b) OnePlus 7T - 1

(c) OnePlus 7T - 2

(d) Xiaomi 11 Pro

Figure 4: Effect of RAM on training time

###  IV-D Resource-aware time-optimised algorithm for client selection

Initially, all the available clients $\\{s\in\\{1\cdots N\\}\\}$ who wish to
participate in $t^{th}$ FL round, express their interest by sending their
context vectors $\\{c_{t,s}\\}$ and number of samples available for training
($n_{t,i}$) to the server. The server then selects $k$ clients based on
Algorithms 1 and 2 and notifies the selected clients about their selection
along with the number of epochs ($e_{t,i}$) they need to run in that round
which is computed using Algorithm 2. The methodology is as follows:

  1. Step 1

Calculate: (a) time taken to complete training a batch of data
($\hat{b\\_t}_{t,i}$), (b) drop in battery on training a batch of data
($\hat{d}_{t,i}$), and (c) the maximum number of batches ($b_{max_{t,i}}$),
each client can run while maintaining the battery above $\gamma\%$.

  2. Step 2

Calculate the maximum number of epochs ($e_{max_{t,i}}$) each client can run
from $b_{max_{t,i}}$, $n_{t,i}$, $e_{max}$ and $bs$

  3. Step 3

Filter out the clients who can run a minimum of $e_{min}$ epochs into a set
($P_{t}$)

  4. Step 4

Create a set ($S_{t}$) by picking $min(k,|P_{t}|)$ clients of $P_{t}$ using
Algorithm 1.

  5. Step 5

Calculate the time taken to run $e_{max_{t,i}}$ epochs for each client and
take the minimum of all these times ($m_{t}$). $m_{t}$ will be the maximum
time the FL round can happen while ensuring that no client switches off in
this time.

  6. Step 6

Calculate the number of epochs ($e_{t,i}$) each client can run in $m_{t}$
time.

  7. Step 7

Notify each client of $S_{t}$ about their selection for that FL round along
with their respective $e_{t,i}$.

Thus, this algorithm ensures to adaptively choose the number of training
epochs for the chosen clients while taking into account the available
resources and minimising the waiting time for each client during FL rounds.

##  V Ed-Fed framework setup

We explain the entire setup used for evaluating Ed-Fed framework in both
simulation and mobile environments.

###  V-A Setup for system-based evaluation

In this section, we present the simulation settings used for evaluating our
Ed-Fed framework for ASR tasks. The objective of this experiment to make the
global model robust to multiple accents by learning from different accented
clients.

We use an end-to-end acoustic model similar to DeepSpeech2 [24] architecture,
collectively trained on datasets such as Librispeech [25], commonvoice [26]
and tedlium [27] as our initial global model. For FL experiments, we created
an audio corpus using a text-to-speech (TTS) system [28] for 15 different
accented speakers to simulate unique clients. Each speech sample is about 8-10
seconds, with an average label length limited to 150 characters. We run the FL
experiments by associating one speaker data to one client. To evaluate the
global model’s accuracy, we created a test set consisting of speech samples
from various speakers.

The simulation environment uses a single server and multiple python clients.
We conduct a series of experiments, where we use our Ed-Fed framework to train
the baseline ASR model on our audio corpus. We repeated the experiment for
different values of k varying from 3 to 5. Each experiment is run for $T=5$
rounds with a fixed k and the k clients are randomly chosen from a pool of 10
readily available clients. We use the server strategy algorithm explained in
Section III-C to aggregate the weights from the selected k clients. We train
the model with 25 samples and a validation set of 10 samples. All of our
experiments were carried out using NVIDIA RTX 3090 and 3080 GPUs on a 10-core
Intel i9-10900K CPU.

###  V-B Mobile phone based Evaluation

With this set of experiments, we discuss the technical details associated with
running Ed-Fed on edge devices. We present results from deploying our
framework on our custom-built android application which allows the user to
record speech samples. These recorded samples gets stored into the local
memory of the application.

We save the datasets for training and testing in the storage cache of the
mobile phone. We train the model with 25 samples and a validation set of 10
samples. We host our python Ed-Fed server with WER based aggregation strategy
on a local machine. The Ed-Fed clients are the Android mobile phones listed in
Table I. We use the optimised model mentioned in Section III-A for the on-
device personalisation of the ASR model.

##  VI Results

Figure 5: Battery vs training time

(a) LinUCB

(b) NeuralUCB single model

(c) NeuralUCB multiple models

Figure 6: Training loss vs FL rounds for different reward generator functions
Figure 7: Comparison of UCB based client selection algorithms TABLE II: Client
selection evaluation

Approach | Experiments | Clients | $AC$ | $BS$ | $e_{min}$ | $e_{max}$ | $\hat{b\\_t}_{t,i}$ | $b_{max_{t,i}}$ | $e_{max_{t,i}}$ |  | $m_{t}$
---
(minutes)
$e_{t,i}$ |  | Actual time
---
per batch (seconds)
| Waiting time
---
(minutes)
Our Client Selection | Scenario 1 | Client 1 | 100 | 1 | 1 | 7 | 431.93 | 46 | 7 | 146.57 | 4 | 430 | 7.42
Client 2 | 100 | 1 | 1 | 7 | 251.25 | 46 | 7 | 7 | 233
Scenario 2 | Client 1 | 60 | 0 | 1 | 7 | 251.25 | 18 | 3 | 51.86 | 3 | 233 | 14.25
Client 2 | 100 | 0 | 1 | 7 | 130.36 | 50 | 7 | 4 | 132
Random Client Selection | Scenario 1 | Client 1 | X | 7 | 430 | 114.92
Client 2 | 7 | 233
Scenario 2 | Client 1 | 7 | 233 | $\infty$
Client 2 | 7 | 132

###  VI-A Effect of resources on the training time

Figure 4 depicts the results of an experiment to show the effect of varying
RAM on training time with the help of two scenarios: one with background apps
running alongside our FL android application (less $AR$) and other with no
background apps (high $AR$). We observe that with decrease in available RAM,
there is a significant increase in training time per batch, across all the
mobile phones. This is especially noticeable in Figure 4(a) and Figure 4(d),
where we see a jump of 49 and 33 seconds in training time respectively. Figure
5 presents the results obtained during the experiment conducted to check the
effect of the battery percentage on the phone’s training time. We can infer
from the figures that training time shoots up abruptly when in lower battery
bands ($\gamma=20\%$), whereas it is almost constant in the upper battery
bands for all the phones except Xiaomi 11 Pro. This is particularly evident in
the OnePlus 5T phone where training time increased 2.4 times the regular time
in lower battery bands.

###  VI-B Neural reward generator

For our contextual bandits experiment, we chose $N=4$ clients and the number
of rounds $T=475$. We ran multiple iterations of on-device training on the $N$
mobile devices to generate the context vectors containing the resource
information and noted down the time taken per batch and the battery drop. We
use the experimental setup described in [23] for LinUCB. The neural networks
used in the NeuralUCB-s and NeuralUCB-m share the same architecture,
consisting of a simple fully connected feedforward network with two hidden
layers of 32 and 16 units, respectively with ReLu activations. The input to
the network is a d dimensional context vector, and the outputs are the time
and battery drop. For NeuralUCB-s and LinUCB, we use a single reward
generating function for all the clients. As a result the context vector
$c=\left[TR,AR,AC,BS,CI,PI\right]$ contains all six features as discussed in
Section IV-B. In contrast, we do not need to provide the total RAM (TR) and
phone-specific information (PI) as features in the NeuralUCB-m approach with
personalised models for each client device. Hence, $d=4$ is used in this case.
We do a grid search over $\\{0.01,0.1,1.0,10\\}$ for the exploration term
multiplier $\alpha_{t}=\alpha$ for all the experiments, and tuned the
parameter in such a way that the fairness achieved is similar across all the
algorithms. For LinUCB, we selected $\alpha=10.0$ and a value of $0.01$ for
NeuralUCB based algorithms.

Figure 6 trace the model’s mean square error loss over rounds. We can see that
neural network-based algorithms outperform LinUCB. Figure 6(a) demonstrates
that linear models are unable to accurately estimate the output and learn
feature representations from the data. Comparing the results of NeuralUCB-s
and NeuralUCB-m from Figures 6(b) and 6(c) respectively, we can observe that
both loss curves looks similar with NeuralUCB-m performing slightly better
over a long run. Figure 7 plots the overall regret of all the algorithms
against rounds. We present the findings based on an average of five repeated
experiments using various random dataset shuffles. Further, we can also infer
from Figure 7 that NeuralUCB-m with disjoint personalised models for each
client appears to outperform all other algorithms.

Figure 8: Scenario 1: Slow vs Fast client.

Figure 9: Scenario 2: One client with insufficient battery life.

Figure 10: Trend of WER for various values of k

Figure 11: Performance of Ed-Fed on mobile phones

###  VI-C Resource-aware time-optimised client selection

Figure 9 and Figure 9 are the results obtained when we redo the experiments of
Scenario 1 and Scenario 2 of Section IV-A with our client selection algorithm
using our neural reward generator at $t=476$. Table II contains the detailed
information of these two experiments. In Scenario 1, our algorithm identified
that client 1 has weaker computing capabilities based on the
$\hat{b\\_t}_{t,i}$ values computed. Since, client 1 has weaker computing
capabilities, our algorithm assigns a smaller $e_{t,1}$ of 4 epochs in
contrast to the 7 epochs given by random client selection approach. Thereby,
reducing the overall waiting time to 7.42 minutes when compared to random
client selection’s 114.92 minutes. In Scenario 2, it is clear from
$e_{max_{t,i}}$ values of the Table II that client 1 has weak battery
resources. Our client selection algorithm deduced that client 1 cannot run 7
epochs and prevented the whole FL round from stopping by assigning a smaller
$e_{t,1}$ of 3 epochs unlike random client selection. Further, our algorithm
adjusted $e_{t,2}$ with respect to $e_{t,1}$ by giving it a value of 4 and
reduced the waiting time even more. Whereas, the random client selection
without any knowledge of resource information asks the client 1 to run
$e_{max}$ epochs. This leads to power shutdown of client 1, thereby making
client 2 wait for infinite amount of time.

###  VI-D Ed-Fed framework evaluation

Figure 11 displays the results obtained by choosing various values of k for
each FL experiment. The figure shows three line plots, each corresponding to
different values of k. Each line plot shows how the global model performs on
the global test set after each round of FL. The global test set consists of 15
unseen speech samples each from 10 speakers with 4 different accents. We can
deduce from the figure that as k increases, the WER of the global model
decreases.

Figure 11 depicts the findings obtained on deployment of our Ed-Fed framework
on multiple phones. The experiment is carried for 5 rounds on 4 mobile
devices. In each round, 2 clients are selected. The round 0 in the figure
refers to the initial global weights. All the checkpoints that are obtained at
the end of each FL round are put to the test on a global test set. As could be
predicted, the WER declines as the number of FL rounds grow.

##  VII CONCLUSIONS AND FUTURE DIRECTIONS

In this work, we present Ed-Fed, a first-of-its-kind end-to-end federated
learning framework that will serve as a foundation for future research in
practical FL systems. We also propose a client selection algorithm that takes
into account factors such as computation, storage, power, and device-specific
capabilities to handle stragglers, optimise waiting time, and adapt training
time based on resource information. The framework has been thoroughly tested
in simulations and on actual edge devices, and in the future, we plan to
incorporate communication latency parameters to measure waiting time.

## References

  * [1] McMahan, B., et al. “Communication-efficient learning of deep networks from decentralized data”, Artificial intelligence and statistics. PMLR, 2017.
  * [2] Yan, G. et al. “End-to-end speech recognition from federated acoustic models.” ICASSP 2022-2022 IEEE Int. Conf. on Acoustics, Speech and Signal Processing (ICASSP). IEEE, 2022.
  * [3] Cui, X., Songtao L., and Brian K., “Federated acoustic modeling for automatic speech recognition.”, IEEE Int. Conf. on Acoustics, Speech and Signal processing (ICASSP), 2021.
  * [4] Yu, W., Freiwald, J., Tewes, S., Huennemeyer, F. and Kolossa, D.,“ Federated learning in ASR: Not as easy as you think”, In Speech Communication, 14th ITG Conference (pp. 1-5), 2021.
  * [5] Guliani, D., Beaufays, F. and Motta, G.,“Training speech recognition models with federated learning: A quality/cost framework”, In IEEE Int. Conf. on Acoustics, Speech and Signal Processing (ICASSP), 2021.
  * [6] Dimitrios D., Kenichi K., Robert G.,Yashesh G., and Eskimez, S E., “A federatedapproach in training acoustic models,” inProc. Interspeech, 2020.
  * [7] Google. “Tensorflow federated: Machine learning on decentralized data.”, https://www.tensorflow.org/federated, 2020. accessed 25-Mar-20.
  * [8] Caldas, S., Duddu, S. M. K., Wu, P., Li, T., Konecn y, J., McMahan, H. B., Smith, V., and Talwalkar, A., “Leaf:A benchmark for federated settings”, arXiv preprint arXiv:1812.01097, 2018.
  * [9] Beutel, D. J., et al. “Flower: A friendly federated learning research framework”, arXiv preprint arXiv:2007.14390 (2020).
  * [10] Mathur, A., Beutel, D. J., de Gusmao, P. P. B., Fernandez-Marques, J., Topal, T., Qiu, X., … & Lane, N. D. (2021). On-device federated learning with flower. arXiv preprint arXiv:2104.03042.
  * [11] Lai, Fan, et al. “Oort: Efficient Federated Learning via Guided Participant Selection.” OSDI. 2021.
  * [12] Xia, Wenchao, et al. “Multi-armed bandit-based client scheduling for federated learning.”, IEEE Transactions on Wireless Communications (2020).
  * [13] Yoshida, N., et al. “Mab-based client selection for federated learning with uncertain resources in mobile networks.” 2020 IEEE Globecom Workshops.
  * [14] Cao, Hangrui, et al. “Birds of a Feather Help: Context-aware Client Selection for Federated Learning.” Int. Workshop on Trustable, Verifiable and Auditable Federated Learning in Conjunction with AAAI (FL-AAAI). 2022.
  * [15] Banerjee, S., Vu, X. S., Bhuyan, M.,“Optimized and Adaptive Federated Learning for Straggler-Resilient Device Selection”, In 2022 International Joint Conference on Neural Networks (IJCNN) (pp. 1-9).
  * [16] Abadi, M. et.al., “TensorFlow: a system for Large-Scale machine learning”, In 12th USENIX symposium on operating systems design and implementation.
  * [17] Tflite, “On-device model personalization”, https://blog.tensorflow.org/2019/12/example -on-device-model-personalization.html, 2020.
  * [18] Sasindran, Z., Suresh, R.R., Rao, P. and Prabhakar, T.V., “Training end-to-end speech-to-text models on mobile phones.”, arXiv preprint arXiv:2112.03871,2021.
  * [19] Carlini, N., Liu, C. and Kos, J. ,Erlingsson, U., and Song, D., “The secret sharer: Measuring unintended neural networkmemorization & extracting secrets”, URL http://arxiv.org/abs/1802.08232.
  * [20] Foundation, C. N. C, “ grpc: A high performance, opensource universal rpc framework”, URL https://grpc.io. Accessed: 2020-03-25.
  * [21] Li, T., Sahu, A.K., Zaheer, M., Sanjabi, M., Talwalkar, A. and Smith, V., “Federated optimization in heterogeneous networks”, Proceedings of Machine Learning and Systems, pp.429-450, 2020.
  * [22] Zhou, D., Li, L., and Gu, Q, “Neural contextual bandits with ucb-based exploration” In International Conference on Machine Learning, 2020.
  * [23] Li, L., Chu, W., Langford, J., and Schapire, R. E.“ A contextual-bandit approach to personalized news article recommendation”, In Int. Conf. on World wide web.
  * [24] Amodei, D., et al. “Deep speech 2: End-to-end speech recognition in english and mandarin.” Int. Conf. on machine learning, PMLR, 2016.
  * [25] Panayotov, V., Chen, G., Povey, D. and Khudanpur, S.,“ Librispeech: an asr corpus based on public domain audio books”, IEEE Int. Conf. on Acoustics, Speech and Signal processing (ICASSP), 2015.
  * [26] Ardila, R., et al. “Common voice: A massively-multilingual speech corpus.” arXiv preprint arXiv:1912.06670 (2019).
  * [27] Hernandez, F. et. al..,“ TED-LIUM 3: twice as much data and corpus repartition for experiments on speaker adaptation”, In Int. Conf. on Speech and computer, 2018.
  * [28] Flood, J., “NaturalReader: A New Generation Text Reader”,. Developmental Disabilities Bulletin, 35, pp.44-55, 2017.