# Universal Approximation in Dropout Neural Networks

Oxana A. Manita<EMAIL_ADDRESS>
Mark A. Peletier<EMAIL_ADDRESS>
Jacobus W. Portegies<EMAIL_ADDRESS>
Jaron Sanders<EMAIL_ADDRESS>
Albert Senen–Cerda<EMAIL_ADDRESS>
Department of Mathematics & Computer Science
Eindhoven University of Technology
Eindhoven, The Netherlands

###### Abstract

We prove two universal approximation theorems for a range of dropout neural
networks. These are feed-forward neural networks in which each edge is given a
random $\\{0,1\\}$-valued filter, that have two modes of operation: in the
first each edge output is multiplied by its random filter, resulting in a
random output, while in the second each edge output is multiplied by the
expectation of its filter, leading to a deterministic output. It is common to
use the random mode during training and the deterministic mode during testing
and prediction.

Both theorems are of the following form: Given a function to approximate and a
threshold $\varepsilon>0$, there exists a dropout network that is
$\varepsilon$-close in probability and in $L^{q}$. The first theorem applies
to dropout networks in the random mode. It assumes little on the activation
function, applies to a wide class of networks, and can even be applied to
approximation schemes other than neural networks. The core is an algebraic
property that shows that deterministic networks can be exactly matched in
expectation by random networks. The second theorem makes stronger assumptions
and gives a stronger result. Given a function to approximate, it provides
existence of a network that approximates in both modes simultaneously. Proof
components are a recursive replacement of edges by independent copies, and a
special first-layer replacement that couples the resulting larger network to
the input.

The functions to be approximated are assumed to be elements of general normed
spaces, and the approximations are measured in the corresponding norms. The
networks are constructed explicitly. Because of the different methods of
proof, the two results give independent insight into the approximation
properties of random dropout networks. With this, we establish that dropout
neural networks broadly satisfy a universal-approximation property.

Keywords: Neural Networks; Approximation; Dropout; Random Neural Network.

MSC2020: 41A30; 68T05.

##  1 Introduction

###  1.1 Universal approximation in Neural Networks

The class of functions that are generated by neural networks satisfies a
‘universal approximation property’: any given function can be approximated to
arbitrary precision by such a neural network (Cybenko, 1989; Leshno et al.,
1993). This property partially explains why neural networks are so effective
as approximators of implicitly given functions.

It is commonly observed that the training of such networks improves upon
introducing _dropout_ , the random ‘dropping’ of edges (Goodfellow et al.,
2016, Sec. 7.9). Dropout converts a deterministic network into a random one.
In this paper we address the question that this observation implicitly raises:
Does this randomness interfere with the universal approximation property? Or,
to formulate it in the affirmative: does the class of dropout neural networks
still satisfy universal approximation?

To provide a first quantification of this question, let us explain the
expectation–variance split, which in the context of dropout goes back to the
theoretical analysis by Wager et al. (2013). We will think of a dropout neural
network as a function $\Psi:\mathbb{R}^{d}\times\mathbb{R}^{n}\to\mathbb{R}$
together with a $\\{0,1\\}^{n}$-valued random variable $f$. We call the
components of $f$ filter variables. We think of $\mathbb{R}^{d}$ as data space
and $\mathbb{R}^{n}$ as parameter space (the space of weights and biases for
the neural network). The parameters get multiplied elementwise with the vector
of filter variables $f$. That means that when
$\zeta:\mathbb{R}^{d}\to\mathbb{R}$ is a function we want to approximate, we
try to approximate it with the stochastic function that maps $x$ to
$\Psi(x,w\odot f)$. For fixed $x$, the expectation–variance split reads

$\mathbb{E}\left[\bigl{(}\Psi(x,w\odot
f)-\zeta(x)\bigr{)}^{2}\right]=\bigl{(}\mathbb{E}[\Psi(x,w\odot
f)]-\zeta(x)\bigr{)}^{2}+\mathbb{V}[\Psi(x,w\odot f)].$ (1)

Here $\odot$ denotes element-wise multiplication, and throughout the paper
$\mathbb{P}$, $\mathbb{E}$, $\mathbb{V}$ stand for probability, expectation,
variance with respect to the filter variables $f$, respectively. As both terms
on the right-hand side are nonnegative, both terms have to be small in order
to have a good approximation. Is this possible?

Foong et al. (2020) showed that deep Rectified Linear Unit (ReLU) neural
networks with node-dropout still can approximate functions arbitrary well, by
showing that both the expectation term and the variance term in the
expectation–variance split can be made arbitrary small (see their Theorem 3).
In fact, the two terms are arbitrary small uniformly over $x$ in the unit cube
in $\mathbb{R}^{d}$. With this statement, Foong et al. effectively showed a
universal-approximation result.

In this paper we show two universal-approximation results for wider classes of
dropout neural networks. Where Foong et al. made specific use of the
properties of ReLU activation, we show that the property of universal
approximation does not require more of the activation functions in dropout
networks than in the underlying deterministic ones (Leshno et al., 1993). In
addition, our main theorems allow for very general classes of filters,
including the original node-based dropout (Hinton et al., 2012), the edge-
based dropconnect (Wan et al., 2013), and many others. With Theorem 1 below we
show that the class of dropout networks can _exactly_ match a given
deterministic network, at least in expectation. With Theorem 15 below we show
that we can construct networks that approximate a given function arbitrarily
well, both as a random network and as a deterministic filtered network.
Finally, we provide control of the error both in probability and in $L^{q}$.

###  1.2 Approximation by random neural networks

In a deterministic context, a universal-approximation theorem for some class
$\mathsf{C}$ is a density statement, stating that any function $\zeta$ can be
approximated to arbitrary precision by neural networks in $\mathsf{C}$, where
the approximation is measured in some seminormed function space
$(\mathcal{F},\|\cdot\|_{\mathcal{F}})$. Such approximation statements can be
generalized to a stochastic context in multiple ways. We will focus on two of
these, approximation in probability and in $L^{q}$ for $q\in[1,\infty)$.

Universal approximation in probability is the property that for every function
$\zeta\in\mathcal{F}$ to approximate, and every $\epsilon>0$, there exists a
neural network $\Psi$, a weight vector $w$ and a random vector $f$ (all with
certain extra properties to make the statement nontrivial), such that

$\mathbb{P}\left[\|\zeta(\cdot)-\Psi(\cdot,w\odot
f)\|_{\mathcal{F}}>\epsilon\right]<\epsilon.$

A stronger statement involves approximation in $L^{q}$ for $q\in[1,\infty)$:
there exist $\Psi$, $w$ and $f$ such that

$\mathbb{E}\left[\left\|\zeta(\cdot)-\Psi(\cdot,w\odot
f)\right\|_{\mathcal{F}}^{q}\right]^{\frac{1}{q}}<\epsilon.$

In this article we indeed show such universal approximation statements for
certain classes of deep dropout neural networks.

We prove two main classes of approximation results, corresponding to the two
main ways that dropout networks are used in practice. In the first class of
results the network is a random object as described above, and the same
network is used during training and prediction; we call this _random-
approximation_ dropout.111This has also been called _Monte Carlo dropout_
because of the close connection with Monte Carlo estimation of integrals
(Gallicchio and Scardapane, 2020). In the second class of results the network
is trained with random networks of the form $\Psi(\cdot,w\odot f)$, but for
prediction the deterministic network $\Psi(\cdot,w\odot{\mathbb{E}}f)$ is used
in which the filters are replaced by their expectations. We call this type of
dropout _expectation-replacement_.

###  1.3 Main results 1: Random-approximation

We start with uniform _random-approximation_ , that is the property that any
function $\zeta$ in an appropriate set can be approximated by random networks
of the form $\Psi(\cdot,w\odot f)$. At the highest level the proof strategy is
the same as in Foong et al. and consists of the following three steps. Given a
function $\zeta\in\mathcal{F}$ to be approximated:

  1. 1.

Approximate $\zeta$ by a neural network $\Psi(\cdot,w)$ using classical
deterministic universal approximation results (e.g. Leshno et al. (1993));

  2. 2.

Use $\Psi(\cdot,w)$ to construct a larger, random dropout neural network
$\tilde{\Psi}(\cdot,\tilde{w}\odot\tilde{f})$ that matches $\Psi(\cdot,w)$ in
expectation;

  3. 3.

Construct an even larger random neural network
$\widehat{\Psi}(\cdot,\widehat{w}\odot\widehat{f})$ consisting of many
independent copies of the network
$\tilde{\Psi}(\cdot,\tilde{w}\odot\tilde{f})$ to obtain an approximation of
$\zeta$ that is close in expectation and also has small variance.

We consider Step 1 as given by existing results, and Step 3 is a standard
procedure. The novelty of this paper for _random-approximation_ lies in Step
2, which we describe in the rest of this section.

Step 2 is based on an algebraic property of common classes of neural networks,
which is illustrated by the following simpler version of the central theorem.
We write $2^{n}$ for the collection of subsets of
$\overline{1,n}=\\{1,\dots,n\\}$, and for any such a subset $U$, we write
$\mathbf{1}_{U}\in\\{0,1\\}^{n}$ for the vector with entries $(1_{j\in
U})_{j\in\overline{1,n}}$.

###### Theorem 1

Let $\Psi:\mathbb{R}^{d}\times\mathbb{R}^{n}\to\mathbb{R}$ be any given
function. Let $(f^{U})_{U\in 2^{n}}$ be a collection of $\\{0,1\\}^{n}$-valued
random variables indexed by subsets $U\in 2^{n}$ such that for every $U$

$\mathbb{P}[f^{U}=(1,\dots,1)]>0.$

Then there exist constants $(a_{U})_{U\in 2^{n}}$, independent of $w$, such
that for all $w$,

$\mathbb{E}\left[\sum_{U\in
2^{n}}a_{U}\Psi\bigl{(}\cdot,(w\odot\mathbf{1}_{U})\odot
f^{U}\bigr{)}\right]=\Psi(\cdot,w).$ (2)

This theorem should be read as follows. The right-hand side in (2) plays the
role of a deterministic function that we want to approximate. The left-hand
side is the expectation of a linear combination of many copies of
$\Psi(\cdot,w)$. Each copy has two ‘dropout’ modifications: the vector
$\mathbf{1}_{U}$ implements a deterministic dropout, and the random filter
variables $f^{U}$ a stochastic one. With a view to generality, the random
filter vector $f^{U}$ is allowed to be a different random vector for each
subset $U$ of edges, but note that the distribution of $f^{U}$ on
$\\{0,1\\}^{n}$ can be completely unrelated to the subset
$U\subset\overline{1,n}$; the subset $U$ only serves as label.

The theorem establishes the following fact: for _any_ collection of random
filter variables $f^{U}$, for _any_ function $\Psi$, for _any_ parameter point
$w$, the function $\Psi(\cdot,w)$ can be matched exactly by the expectation of
a sum of filtered versions of the same function. The important caveat is that
one needs to take into account all reduced versions of the functions $\Psi$,
i.e., the whole hierarchy of deterministically modified versions indexed by
subsets $U$.

Theorem 1 suggests a special role for ‘classes of networks’, with the property
that given a ‘network’ $\Psi(\cdot,w)$ we can in some sense define a new
(random) network $\tilde{\Psi}(\cdot,\tilde{w}\odot\tilde{f})$ by

$\tilde{\Psi}(\cdot,\tilde{w}\odot\tilde{f}):=\sum_{U\in
2^{n}}a_{U}\Psi(\cdot,w\odot\mathbf{1}_{U}\odot f^{U}).$ (3)

To formalize this, we assume that we have chosen a set $\mathsf{DDNN}$ (a ‘set
of random neural networks’), which can be any collection of tuples
$(n,\Psi,f)$ that satisfy the following properties:

  * (i)

$n\in\mathbb{N}$ is a natural number;

  * (ii)

$\Psi:\mathbb{R}^{d}\times\mathbb{R}^{n}\to\mathbb{R}$ is a function such that
for every $w\in\mathbb{R}^{n}$, $\Psi(\cdot,w)\in\mathcal{F}$;

  * (iii)

$f$ is a $\\{0,1\\}^{n}$-valued random variable such that

$\mathbb{P}[f=(1,\dots,1)]>0.$ (4)

Moreover, we assume that $\mathsf{DDNN}$ is closed under linear, independent
combinations. By this we mean that whenever $a,b\in\mathbb{R}$ and
$(m,\Phi,f)$ and $(n,\Psi,g)$ are in $\mathsf{DDNN}$, then also
$(m+n,a\Phi+b\Psi,h)\in\mathsf{DDNN}$ where $h$ is an $\\{0,1\\}^{m+n}$-valued
random variable that is the independent concatenation of $f$ and $g$, and
$a\Phi+b\Psi:\mathbb{R}^{d}\times\mathbb{R}^{m+n}\to\mathbb{R}$ is given by

$(x,(w_{1},w_{2}))\mapsto a\Phi(x,w_{1})+b\Psi(x,w_{2}).$

This closure assumption implies that a definition of the form (3) is
meaningful.

The range of possible classes $\mathsf{DDNN}$ satisfying these requirements is
vast. Typical examples are neural networks with node-dropout, as originally
introduced by Hinton et al. (2012), and _dropconnect_ , as introduced by Wan
et al. (2013), but many other choices also are possible. Note that the
function $\Psi$ may be extremely general, implying that there are no
restrictions on e.g. the form of the activation function or the structure of
the network. In fact, nothing in the requirements on $\mathsf{DDNN}$ restricts
to functions $\Psi$ generated by neural networks; other approximation
methodologies may also be used, for instance based on Fourier or wavelet
expansions. See Section 2 for a detailed description of $\mathsf{DDNN}$.

By combining Theorem 1 with the law of large numbers we then find Corollary 2
below, which expresses the following insight: if the class $\mathsf{DDNN}$ is
rich enough to approximate any function in $\mathcal{F}$ when all filter
variables are set to 1, then any function in $\mathcal{F}$ can also be
approximated by a (random) dropout neural network in $\mathsf{DDNN}$.

###### Corollary 2

Let $\zeta\in\mathcal{F}$ and $\epsilon>0$. Assume there exists a
$(m,\Phi,g)\in\mathsf{DDNN}$ and a $v\in\mathbb{R}^{m}$ such that
$\|\Phi(\cdot,v)-\zeta\|_{\mathcal{F}}<\epsilon/2$. Then there exists a
$(n,\Psi,f)\in\mathsf{DDNN}$ and a $w\in\mathbb{R}^{n}$ such that

$\mathbb{P}[\|\Psi(\cdot,w\odot f)-\zeta\|{}_{\mathcal{F}}>\epsilon]<\epsilon$
(5)

and

$\mathbb{E}\left[\left\|\Psi(\cdot,w\odot
f)-\zeta\right\|_{\mathcal{F}}^{q}\right]^{\frac{1}{q}}<\epsilon.$

Section 4 is devoted to these results, but develops them in more generality.
There we also give some examples and calculate the coefficients $a_{U}$
explicitly for the case of independent Bernoulli filters.

###  1.4 Main results 2: Expectation-replacement

In the previous section we considered dropout neural network to be a random
object, both during training and during prediction. By contrast, it is common
practice to choose the filter variables during prediction to be
_deterministic_ and equal to their expectations; see e.g. Section 7.12 in
Goodfellow et al. (2016)’s paper. We call this _expectation-replacement_
dropout, and Corollary 2 above does not say anything about this situation. In
fact, we show in Example 5 that the construction at the heart of Corollary 2
may lead to networks that are ‘bad approximators’ in this specific sense:
given a function $\zeta$, the constructed networks approximate $\zeta$ with
high probability with random filters, but do not approximate $\zeta$ at all
when replacing the filters by their expectations.

To address this, we describe in Section 4 the construction of dropout neural
networks that approximate not only in probability and in $L^{q}$, but also in
this expectation-replacement sense. As in the case of Corollary 2, the
construction builds on existing density results for deterministic networks: we
start with a given deterministic neural network $\Psi(\cdot,w)$ that is close
to a given function $\zeta$. Differently from Corollary 2, however, the
nonlinearity of $\Psi$ forces us to apply the law of large numbers to each
edge (or weight in this context) separately, instead of simultaneously for the
whole network.

In the construction in Section 4 we therefore iteratively replace each edge in
the deterministic neural network $\Psi$ by a set of parallel edges, with edge-
weights $w$ taken from the original edge, and with independent filter
variables on each of them. In this way we can use the law of large numbers to
obtain convergence estimates for each edge separately, and then combine these
estimates into a single convergence estimate for the whole network.

The convergence estimate for a single edge arises from the following statement
(which is a simplified version of Lemma 13). It describes how the error
encountered by averaging $N$ independently filtered edges can be controlled in
probability. At the same time it also allows for small perturbations of the
inputs to this edge. This latter perturbation freedom is needed in order to
apply this lemma progressively, moving from edge to edge through the network.

###### Lemma 3

Consider any continuous function $\sigma:\mathbb{R}^{m}\to\mathbb{R}^{m}$ and
let $W\in\mathbb{R}^{m\times n}$, $b\in\mathbb{R}^{m}$. Let
$\\{F^{i}\\}_{i\in\overline{1,N}}$ be a collection of independent copies of a
random matrix $F\in\\{0,1\\}^{m\times n}$. Then for every $K>0$ there exists a
$\delta>0$ such that

$\sup_{x\in\overline{B(0,K)}}\sup_{(\tilde{x}^{i})\in
B(x,\delta)^{N}}\biggl{|}\sigma\biggl{(}\frac{1}{N}\sum_{i=1}^{N}(W\odot
F^{i})\tilde{x}^{i}+b\biggr{)}-\sigma\Bigl{(}(W\odot{\mathbb{E}}F^{i})x+b\Bigr{)}\biggr{|}$
(6)

converges to zero in probability as $N\to\infty$.

In Section 4 this construction is described in detail. A separate part of this
description is how to connect the resulting dropout neural network to the
inputs of the original layer; for this we introduce a single additional layer
that implements this connection.

The main Theorem 15 allows for a wide range of choices of activation functions
and filter-variable distributions. The following is a simple, concrete
corollary for a ReLU activation function.

###### Corollary 4

Take $\mathcal{F}$ to be the space of continuous functions
$\mathbb{R}^{d}\to\mathbb{R}$, and endow it with a seminorm
$\|\cdot\|_{\mathcal{F}}$ equal to supremum of the function on the unit cube.
Then for every $\zeta\in\mathcal{F}$ and every $\epsilon>0$ there exists a
dropconnect ReLU neural network $(\Psi,f)$ and a parameter vector $w$ such
that

$\mathbb{P}\Bigl{[}\Bigl{\|}\Psi(\cdot,w\odot
f)-\zeta\Bigr{\|}_{\mathcal{F}}>\epsilon\Bigr{]}<\epsilon$ (7)

and

$\mathbb{E}\left[\left\|\Psi(\cdot,w\odot
f)-\zeta\right\|_{\mathcal{F}}^{q}\right]^{\frac{1}{q}}<\epsilon,$

while

$\left\|\Psi(\cdot,w\odot\mathbb{E}[f])-\zeta\right\|_{\mathcal{F}}<\epsilon.$

Note that where the construction of the previous section applied to a very
wide class of functions $\Psi$—not only those generated by neural networks—the
construction underlying Corollary 4 depends in a detailed manner on the fact
that $\Psi$ has the structure of a neural network.

###  1.5 Random-approximation _vs._ expectation-replacement dropout

Using a _random_ neural network to approximate a given _deterministic_
function is non-trivial; the variance of the network needs to be reduced while
matching the expectation, as described in Section 1.3.

In expectation-replacement dropout, however, the networks used in prediction
are deterministic, and this difficulty is absent. In fact, the difference
between training and prediction is the reason we include expectation-
replacement in this paper.

This difference between training and prediction poses an intriguing question.
Suppose that the dropout training algorithm yields a parameter point $w^{*}$.
During this training, the algorithm has observed random networks
$\Psi(\cdot,w\odot f)$, but it has never observed the deterministic network
$\Psi(\cdot,w\odot\mathbb{E}f)$. Why, then, should the result $w^{*}$ of the
dropout training then generate a good deterministic network
$\Psi(\cdot,w^{*}\odot\mathbb{E}f)$? Example 5 confirms that this method may
fail badly.

At the same time, expectation-replacement dropout is both very widespread and
very successful; see e.g. Section 7.12 in Goodfellow et al. (2016)’s paper, or
Labach et al. (2019)’s paper. How can these two observations be reconciled?

The results of Section 4 and e.g. Corollary 4 provide a partial answer to this
question. We show that dropout neural network have sufficient representational
capacity to approximate well simultaneously in probability, in $L^{q}$, _and_
in the expectation-replacement sense. While this does not explain why any
given training algorithm finds parameter points that approximate well in the
expectation-replacement sense, at least it shows that the contrast between
random training and deterministic prediction is not an obstacle to good
performance.

###  1.6 Related literature

The universal approximation property for neural networks is one of the
fundamental properties and essentially determines whether the whole training
process of the network makes sense: if the algorithmically generated functions
don’t form a dense set in the function space of interest, the approximation
problem is ill-posed. Therefore establishing the universal approximation
property for different classes of networks has been an active research area in
the last decades. However, most classes of networks for which there is a
universal approximation property established do not include, for example,
node-dropout or dropconnect neural network.s

The first universal approximation theorem for neural networks with a sigmoidal
activation function can be found in Cybenko (1989)’s paper, and this canonical
work led to much follow-up research. Several years later Hornik (1991) showed
that the universal approximation property relies more on a neural network’s
architecture than on the specific use of sigmoid activation functions.
Moreover, Leshno et al. (1993) established that deep, feed-forward neural
networks require a nonpolynomial activation function in order for a universal
approximation theorem to hold. Makovoz (1996, 1998) used the so-called
probabilistic method to prove the existence of a deterministic function that
suitably approximates a target function in deterministic neural networks.

Approximately at the same time the study of random networks started. White
(1989)’s paper on “QuickNet” is one of the first works where universal
approximation is mentioned (but not proved) side by side with a neural network
algorithm in which random hidden nodes are placed.

The class of networks with random weights and biases, called Random Vector
Functional-Link Nets, was introduced in 1994 by Pao et al. (1994). Igelnik and
Pao (1995) proved a universal approximation property of these networks, by
showing that the span of the node functions is almost surely asymptotically
dense in the many-node limit. This result does not apply to dropout schemes
since in the dropout setup the randomness is applied after choosing
coefficients.

Gelenbe et al. (1999a, b) introduced a class of neural networks that relies on
a fixed neural network topology on top of which neurons forward positive and
negative signals (spikes) at random points in time based on their own
“potential”. Specifically, they gave a constructive proof of the universal
approximation theorem for such stochastic neural networks networks in steady
state. This class of networks also doesn’t cover the node-dropout or
dropconnect cases due to the different dynamics assumed; moreover a dropout
neural network is trained randomly, but typically operated deterministically.

Rahimi and Recht (2008) investigated uniform approximation of functions with
random bases. This is a particular case of a so-called random feature method,
in which the parameters are split in two groups: parameters in one group are
taken randomly (and not tuned), and the other part is trained to achieve best
approximation. Therefore these results also don’t cover node-dropout or
dropconnect since for the latter algorithms all parameters are trained.

Another commonly used class of neural networks is the _mixture of experts_
model. The idea is that for different input regions different, typically
simpler, networks (learners) are used for prediction. The choice is performed
by the _gating network_ ; training of the model consists then of training
individual learners together with training the gating network. Nguyen et al.
(2016) proved a universal approximation theorem for a mixture-of-experts
model, and Nguyen (2017) subsequently generalized their findings to allow for
so-called Gaussian gating.

De Bie et al. (2018) considered a network architecture that can handle
probability measures as input and output. They proved the universal
approximation in Wasserstein metric for continuous maps from the space of
measures into itself. Our results are more specific, and not covered by this
result, since we study a different (more restricted) approximation scheme.

As mentioned in the introduction, Foong et al. (2020) show a universal
approximation property for random-approximation dropout networks (see their
Theorem 3). We recover this result as Corollary 2 when identifying $h\equiv
0$. Another difference is that we allow for activation functions other than
ReLU activation functions, and consider a stronger sense of approximation.

Finally, we refer interested readers to the following surveys to fully
complete their picture of known results. A survey of approximation-theoretic
problems was written by Pinkus (1999); a recent survey by Elbrächter et al.
(2020) contains a comparison of approximation properties for finite-width and
finite-depth networks. Several uniform approximation results for random neural
networks can be found in Timotheou (2010)’s Section 5.4. Approximation
literature for random neural networks was also summarized by Yin (2019).

###  1.7 Structure of this paper

Definitions of dropout neural networks are given in Section 2. In Section 3 we
show universal approximation results for random-approximation dropout, whereas
Section 4 is devoted to universal approximation results for expectation-
replacement dropout. We discuss our results in Section 5 and conclude in
Section 6.

##  2 Specification of dropout neural networks

In the introduction, we considered general functions
$\Psi:\mathbb{R}^{d}\times\mathbb{R}^{n}\to\mathbb{R}$ together with a
$\\{0,1\\}^{n}$-valued random variable $f$ (Section 1.3), and more specific
functions $\Psi$ that arise from a neural network (Section 1.4). In this
section, we specify this neural network structure and introduce the
corresponding notation.

###  2.1 Neural networks

We specify a (feedforward) neural network as a special type of parametrized
function $\Psi:\mathbb{R}^{d}\times\mathbb{R}^{n}\to\mathbb{R}$ from an input
vector space $\mathbb{R}^{d}$ to $\mathbb{R}$, parametrized by vectors in
$\mathbb{R}^{n}$. The function is special in that it is assumed to be the
composition of multiple functions of much simpler type

$\Psi(\cdot,w)=\Psi_{L}\left(\cdot,w^{(L)}\right)\circ\Psi_{L-1}\left(\cdot,w^{(L-1)}\right)\circ\cdots\circ\Psi_{1}\left(\cdot,w^{(1)}\right).$
(8)

Here, $L$ is an integer, the parameter $w$ is the concatenation of the
individual parameter vectors $w^{(j)}=(W^{(j)},b^{(j)})$ for
$j=\overline{1,L}$, which in turn consist of a $d_{j}\times d_{j-1}$ _weight
matrix_ $W^{(j)}$ and a bias vector $b^{(j)}\in\mathbb{R}^{d_{j}}$. We set
$d_{0}=d$ and $d_{L}=1$.

In (8) every $\Psi_{j}$ is a function from $\mathbb{R}^{d_{j-1}}$ to
$\mathbb{R}^{d_{j}}$ given by

$\Psi_{j}(x,w^{(j)}):=\sigma_{j}\left(W^{(j)}x+b^{(j)}\right),$ (9)

where the function $\sigma_{j}:\mathbb{R}\to\mathbb{R}$ is called the
_activation function_. The activation function is applied elementwise.

###  2.2 Dropout neural networks

A dropout neural network consists of a neural network
$\Psi:\mathbb{R}^{d}\times\mathbb{R}^{n}\to\mathbb{R}$ as above together with
a random vector $f\in\\{0,1\\}^{n}$. The components of $f$ are called filter
variables. The network $\Psi$, the filter variables $f$, and a parameter
vector $w\in\mathbb{R}^{n}$ together form a stochastic function from
$\mathbb{R}^{d}$ to $\mathbb{R}$ given by

$x\mapsto\Psi(x,w\odot f).$

For the constructions later in the article, we recall what we precisely mean
by random variables. Throughout the article,
$(\Omega,\mathcal{F}_{\Omega},\mathbb{P})$ is an arbitrary, rich enough,
probability space. Whenever we write _random variable_ , _random vector_ or
_random matrix_ , we mean a measurable function defined on this probability
space.

####  2.2.1 Node-dropout

In the original version of dropout filter variables acted on _nodes_ of the
network (Hinton et al., 2012). In this paper the filter variables act on edges
instead. The original version, which we call _node-dropout_ , can be
represented in the edge-based version of this paper as follows.

The filter variables are partitioned into various blocks: filter variables are
in the same block if and only if they multiply an element in the same column
in the same weight matrix, or they multiply elements of the same bias vector.
Filter variables in the same block always attain the same value, i.e., with
probability one. Filter variables in different blocks are independent. We will
use the convention that filter variables that multiply biases are always on,
whereas filter variables that multiply elements of weight matrices are on,
i.e., equal to $1$, with probability $1-p$ for some $0\leq p<1$.

We can understand node-dropout from the previous description in the notation
of (9). For any $j=1,\dots,L$, choose probabilities $p^{j}$, and let
$f_{1}^{j},\ldots,f_{d_{j}}^{j}$ be independent Bernoulli filters with
probability $1-p^{j}$. Let $D_{j}\in\mathbb{R}^{d_{j}\times d_{j}}$ be the
diagonal matrix with entries $f_{1}^{j},\ldots,f_{d_{j}}^{j}$ in the diagonal.
If we then arranging all nodes per block, then node-dropout implements for
$j=1,\ldots,L$,

$\Psi_{j}(\cdot,w^{(j)}\odot
f^{(j)})=\sigma_{j}\left(W^{(j)}D^{j}(\cdot)+b^{(j)}\right).$ (10)

Note that if $p^{1}>0$ then with positive probability an input is masked. For
this reason we call the case $p^{1}>0$ node-dropout _with_ dropout on the
inputs. We call the case $p^{1}=0$ node-dropout _without_ dropout on the
inputs.

####  2.2.2 Dropconnect

Dropconnect is another dropout regularization scheme (Wan et al., 2013).
Although Wan et al. (2013) also allowed for dropout of biases, we will use the
term _dropconnect_ for the dropout neural network in which only the matrices
$W^{(j)}$ are filtered. This is achieved by choosing the filter variables
multiplying the biases to be equal to $1$ with probability one.

We can understand dropconnect in the notation of (9). For $j=1,\ldots,L$, let
$F^{(j)}\in\mathbb{R}^{d_{j+1}\times d_{j}}$ be random matrices composed of
entries $(F^{j})_{ik}$, all of which are mutually independent Bernoulli random
variables with the same success probability $1-p$. Dropconnect then implements
for $j=1,\ldots,L$,

$\Psi_{j}(\cdot,w^{(j)}\odot f^{(j)})=\sigma_{j}\left((W^{(j)}\odot
F^{(j)})(\cdot)+b^{(j)}\right).$ (11)

##  3 Universal approximation for random approximation dropout

The aim of this section is to derive the abstract universal approximation
statement for random-approximation dropout already mentioned in the
introduction (Corollary 2).

###  3.1 Key approximation result

The following theorem is Theorem 1 in the introduction, extended with a
convergence statement.

###### Theorem 5

Let $(\mathcal{F},\|\cdot\|_{\mathcal{F}})$ be a seminormed vector space of
functions from $\mathbb{R}^{d}$ to $\mathbb{R}$. Let
$\Psi:\mathbb{R}^{d}\times\mathbb{R}^{n}\to\mathbb{R}$ be a given function
such that $\Psi(\cdot,w)\in\mathcal{F}$ for every $w\in\mathbb{R}^{n}$. Let
$(f^{U})_{U\in 2^{n}}$ be a collection of $\\{0,1\\}^{n}$-valued random
variables indexed by subsets $U\in 2^{n}$, such that for every $U$

$\mathbb{P}[f^{U}=(1,\dots,1)]>0.$ (12)

Then there exist constants $(a_{U})_{U\in 2^{n}}$ independent of $w$ such that

$\mathbb{E}\left[\sum_{U\in 2^{n}}a_{U}\Psi(\cdot,(w\odot\mathbf{1}_{U})\odot
f^{U})\right]=\Psi(\cdot,w).$ (13)

In particular, by the weak law of large numbers, if $f^{i,U}$ are independent
copies of $f^{U}$, then as $M\to\infty$,

$\frac{1}{M}\sum_{i=1}^{M}\sum_{U\in
2^{n}}a_{U}\Psi(\cdot,(w\odot\mathbf{1}_{U})\odot f^{i,U})\to\Psi(\cdot,w)$
(14)

in probability in $(\mathcal{F},\|\cdot\|_{\mathcal{F}})$ and in $L^{q}$ for
every $q\in[1,\infty)$.

A proof of Theorem 5 can be found in Appendix A.1. The main observation in
Theorem 5 is the existence of the constants $(a_{U})_{U\in 2^{n}}$. This
purely algebraic statement follows by induction, as explained by Lemma 17 in
Appendix A.1. From Theorem 5, it follows that one can see a dropout neural
network as a linear combination of dropout networks with weights
$(w\odot\mathbf{1}_{U})_{U\in 2^{n}}$, such that the linear combination equals
the original neural network in expectation as shown in (13).

To get a dropout neural network that is close to the original network in
probability, in (14) one makes a large average of independent copies of the
dropout network that approximates the original network in expectation. The
convergence in probability of (14) follows then from the weak law of large
numbers. The convergence in $L^{q}$ finally follows because the expectation is
uniformly bounded in $\mathcal{F}$ for any realization of the filter variables
$f^{i,U}$, so that the convergence in probability immediately implies the
convergence in $L^{q}$ by dominated convergence.

###  3.2 Examples

We further illustrate the construction of Theorem 5 with the following
examples:

######  Example 1 (One-hidden-layer dropconnect networks)

Consider the function $\Psi:\mathbb{R}^{d}\times\mathbb{R}^{n}\to\mathbb{R}$
given by

$\Psi(x,w):=\sum_{j=1}^{N}c^{j}\sigma(w^{j}x+b^{j})$ (15)

where the activation function $\sigma:\mathbb{R}\to\mathbb{R}$ is continuous
with $\sigma(x)\to 0$ as $x\to-\infty$ and $\sigma(x)\to 1$ as $x\to\infty$.
In (15) we have biases $b_{j}\in\mathbb{R}$ and weights made up from the
constants $c^{j}\in\mathbb{R}$ and the $1\times d$-matrices $w^{j}$.

The well-known result by Cybenko (1989) implies that the class of all such
functions is dense in $C([0,1]^{d})$ endowed with the supremum norm. An
example of an approximation by functions in (15) is depicted in Figure 1.

$x$$1$$\sigma$$\sigma$$+$$\Psi(x,w)=\displaystyle\sum_{j=1}^{n}c^{j}\sigma(w^{j}x+b^{j})$$w^{1}$$w^{2}$$b^{1}$$b^{2}$$c^{1}$$c^{2}$$-10$$0$$10$$-0.5$$0$$0.5$$x$Truth
$\zeta(x)$Cybenko NN $\Psi(x,v)$ Figure 1: A Cybenko neural network as in
(15), trained to approximate a function $\zeta$; here, $n=2,d=1$, and
$\zeta(x)=\sin{(x+3)}\exp{|x-3|}$.
$1$$\sigma$$\sigma$$+$$1$$\sigma$$\sigma$$+$$\times$$1$$\sigma$$\sigma$$+$$1$$\sigma$$\sigma$$+$$\times$$x$$+$$\displaystyle\sum_{U\in
2^{n}}a^{U}\Psi(x,(w\odot 1_{U})\odot
f^{U})$$a^{00}$$a^{01}$$a^{10}$$a^{11}$$-10$$0$$10$$-0.5$$0$$0.5$$x$Truth
$\zeta(x)$$\sum_{U\in 2^{n}}a^{U}\Psi(x,(w\odot 1_{U})\odot
f^{U})$$\Psi(x,w\odot 1_{00}\odot f^{00})$$\Psi(x,w\odot 1_{01}\odot
f^{01})$$\Psi(x,w\odot 1_{10}\odot f^{10})$$\Psi(x,w\odot 1_{11}\odot f^{11})$
Figure 2: A single realization of the random neural network in (13) using
Dropconnect. Based off the trained Cybenko neural network in Figure 1, for
simplicity, we only apply dropout to the weights $w^{j}$ of (15), which we
denote by $w$ and correspond to the edges joining the nodes connected to the
input $x$. With $n=2$ and $d=1$, there are four different random neural
networks with their respective independent filters. All of them use as base
$\Psi(\cdot,w)$ in Figure 1. In this realization, some of the edges are
filtered, which are depicted with red crosses. The explicit coefficients
$a_{U}$ used for dropconnect are computed in Section 3.4.

We suppose that the distribution of the filters follows the case of
dropconnect, as described in Section 2.2.2. Theorem 5 directly yields that by
choosing appropriate weights $c^{j,U}$ and weight matrices $w^{j,U}$, the one-
hidden-layer dropconnect network given by

$\frac{1}{M}\sum_{i=1}^{M}\sum_{U\in
2^{n}}\sum_{j=1}^{N}a_{U}c^{j,U}g^{j,U}\sigma\left((w^{j,U}\odot
f^{j,U})x+b^{j}\right)$ (16)

can be chosen to be close to $\Psi$ in $L^{q}$ for large $M$. Here $g^{j,U}$
are independent Bernouilli random variables, and $f^{j,U}$ are random vectors
with independently Bernoulli-distributed components, all with success
probability $1-p$. This result is illustrated by Figures 2 and 3, where for
simplicity we have used filters only on the weights $w^{j,U}$, while leaving
the biases $b^{j}$ and $c^{j}$ with constant filters $1$. Figure 2 shows a
single realization of the neural network in (13) with dropconnect while in
Figure 3 a ‘blow up’—the average of $M$ independent copies of the network in
(16)—of the previous construction is depicted.

$1$$\sigma$$\sigma$$+$$1$$\sigma$$\sigma$$+$$\times$$1$$\sigma$$\sigma$$+$$1$$\sigma$$\sigma$$+$$\times$$+$$a^{00}$$a^{01}$$a^{10}$$a^{11}$$1$$\sigma$$\sigma$$+$$1$$\sigma$$\sigma$$+$$1$$\sigma$$\sigma$$+$$\times$$1$$\sigma$$\sigma$$+$$\times$$\times$$+$$a^{00}$$a^{01}$$a^{10}$$a^{11}$$\ldots$$\ldots$$+$$+$$\ldots$$\ldots$_et
cetera_ ($M$ i.i.d. copies)$x$$+$$\displaystyle\sum_{i=1}^{M}\sum_{U\in
2^{n}}\frac{a^{U}}{M}\Psi(x,(w\odot 1_{U})\odot
f^{U,i})$$\tfrac{1}{M}$$\tfrac{1}{M}$$\tfrac{1}{M}$$\tfrac{1}{M}$$-10$$0$$10$$-1$$-0.5$$0$$0.5$$x$Truth
$\zeta(x)$$\sum_{i=1}^{M}\sum_{U\in 2^{n}}\frac{a^{U}}{M}\Psi(x,(w\odot
1_{U})\odot f^{U,i})$$\sum_{U\in 2^{n}}a^{U}\Psi(x,(w\odot 1_{U})\odot
f^{U,1})$$\sum_{U\in 2^{n}}a^{U}\Psi(x,(w\odot 1_{U})\odot
f^{U,128})$$\sum_{U\in 2^{n}}a^{U}\Psi(x,(w\odot 1_{U})\odot f^{U,256})$
Figure 3: An approximation of $\zeta$ with a large neural network using
dropconnect, based off the base Cybenko neural network in (15) depicted in
Figure 1. Adding many independent copies of the network from Figure 2, we are
leveraging the law of large numbers as in (16). Different independent copies
of the network may have a different realization of the filters, which is here
depicted by the red crosses on the edges.

In a similar way, we can also consider more general dropconnect networks.

######  Example 2 (Dropconnect networks)

Consider a deep neural network
$\Psi:\mathbb{R}^{d}\times\mathbb{R}^{n}\to\mathbb{R}$ as introduced in (8)
with dropconnect filters as described in Section 2.2.2. Here, the filter
variables, i.e., the components of $f^{i,U}$ in (8), are i.i.d. Bernoulli
distributed with success probability $1-p$ if they multiply elements of the
weight matrices $W^{(j)}$, and are equal to $1$ if they multiply biases
$b^{(j)}$.

Let $w\in\mathbb{R}^{n}$. We choose for $\mathcal{F}$ the vector space of
continuous functions on $\mathbb{R}^{d}$, endowed with the supremum seminorm
over the closed unit cube. Then the dropconnect random network in (14) is for
large $M$ close to the network $\Psi(\cdot,w)$ in $L^{q}$.

######  Example 3 (Node-dropout networks)

Consider again the deep neural network in (8) with node-dropout as described
in Section 2.2.1. The random neural network in (14) is then again a node-
dropout neural network. In this way, we recover Foong et al. (2020)’s Theorem
3 (with $h\equiv 0$), which for ReLU activation functions and a target
function $\zeta$ bounds

$\sup_{x\in[0,1]^{d}}\operatorname{Var}(\zeta(x)-\Psi(x,w\odot f)).$ (17)

When $\mathcal{F}$ is the space of continuous functions with supremum norm,
(17) can be bounded by a constant times the square of the $L^{2}$-norm. Hence,
Theorem 5 approximates in a stronger sense, namely, in $L^{q}$ for any
$q\in[1,\infty)$. Moreover, Theorem 5 also allows for activation functions
other than ReLU.

######  Example 4 (Dropout networks with dropout on _input_)

In contrast, if there is also dropout on the input, then the neural network in
(14) is _not_ again a dropout neural network with dropout on the inputs.
Results by Foong et al. (2020) imply that in general neural networks with
dropout on the _input_ cannot satisfy a universal approximation property.

We remark that this kind of stochastic network is _not_ a dropout neural
network as defined in Section 2.2 as the following example shows: Suppose that
$\Psi_{1},\Psi_{2}:\mathbb{R}^{d}\times\mathbb{R}^{n}\to\mathbb{R}$ are two
different dropout neural networks with weights $w_{1},w_{2}$ and with
respective filter random variables $f,g$ with values in $\\{0,1\\}^{n}$. Then
we can define the dropout neural network $\Psi$ with value

$\Psi(x,(w_{1}\odot f,w_{2}\odot g))=\Psi_{1}(x,w_{1}\odot
f)+\Psi_{2}(x,w_{1}\odot g).$ (18)

Suppose that, additionally, we add independent filters $h_{1}$ and $h_{2}$
with values in $\\{0,1\\}^{d}$ to $\Psi_{1},\Psi_{2}$ for their respective
inputs. Then, $\Psi_{1}(x\odot h_{1},w_{1})+\Psi_{2}(x\odot h_{2},w_{2})$ is
not necessarily of the type $\Psi(x\odot h,(w_{1},w_{2}))$ for some random
variable $h$ with values in $\\{0,1\\}^{d}$.

As the above examples illustrate, a crucial aspect of whether a certain class
of dropout neural networks (such as dropconnect or node-dropout) satisfy a
universal approximation property, is whether linear, independent combinations
of such networks are again networks in the same class. On the other hand, many
details of the neural networks, such as them being a composition of simpler
functions, are irrelevant for the proof of Theorem 5.

###  3.3 The classes $\mathsf{DDNN}$

In the introduction we introduced classes $\mathsf{DDNN}$ of tuples
$(n,\Psi,f)$ that are closed under linear, independent combinations as the
basic objects with which we want to approximate a given function
$\zeta\in\mathcal{F}$.

The convergence statement (14) of Theorem 5 then immediately implies Corollary
6, which was already given as Corollary 2. It expresses that if the class
$\mathsf{DDNN}$ is rich enough to approximate any function in $\mathcal{F}$
when all filter variables are set to 1 in the event in (4), then for every
function in $\mathcal{F}$ there exists a dropout neural network such that with
high probability with regards to the filter variables, the dropout neural
network also approximates the function.

###### Corollary 6

Let $\zeta\in\mathcal{F}$ and $\epsilon>0$. Assume there exists a
$(m,\Phi,f)\in\mathsf{DDNN}$ and a $v\in\mathbb{R}^{m}$ such that
$\|\Phi(\cdot,v)-\zeta\|_{\mathcal{F}}<\epsilon/2$. Then there exists a
$(n,\Psi,g)\in\mathsf{DDNN}$ and a $w\in\mathbb{R}^{n}$ such that

$\mathbb{P}[\|\Psi(\cdot,w\odot g)-\zeta\|{}_{\mathcal{F}}>\epsilon]<\epsilon$
(19)

and

$\mathbb{E}\left[\left\|\zeta(\cdot)-\Psi(\cdot,w\odot
g)\right\|_{\mathcal{F}}^{q}\right]^{\frac{1}{q}}<\epsilon.$

This corollary can be combined with deterministic universal approximation
properties of certain classes of neural networks to obtain concrete universal
approximation properties of dropout neural networks. For instance, because
both the class of node-dropout networks and the class of dropconnect networks
defined in Sections 2.2.1 and 2.2.2 form examples of a set $\mathsf{DDNN}$, we
obtain the following universal approximation property by combining Corollary 6
with the universal approximation result in Leshno et al. (1993)’s Proposition
1.

###### Corollary 7

Assume $\mu$ is a nonnegative probability measure on $\mathbb{R}^{n}$ with
compact support, absolutely continuous with respect to the Lebesgue measure.
Take $\mathcal{F}=L^{r}(\mu)$ for some $r\in[1,\infty)$. Assume that the
activation function $\sigma:\mathbb{R}\to\mathbb{R}$ is not equal to a
polynomial almost everywhere. Then for every $\epsilon>0$ there exists a one-
hidden-layer dropconnect neural network $(n,\Psi,g)$ such that

$\mathbb{P}[\|\Psi(\cdot,w\odot g)-\zeta\|{}_{L^{r}(\mu)}>\epsilon]<\epsilon,$
(20)

and

$\mathbb{E}\left[\left\|\zeta(\cdot)-\Psi(\cdot,w\odot
h)\right\|_{L^{r}(\mu)}^{q}\right]^{\frac{1}{q}}<\epsilon.$

There also exists a one-hidden-layer node-dropout neural network with the same
properties.

Certainly, many variations of the above corollary can be constructed.

To further illustrate Corollary 6, in Figure 4 we look at the approximation in
probability of our construction from Theorem 5.

$-10$$-5$$0$$5$$10$$-0.5$$-0.25$$0$$0.25$$0.5$$z$Truth $\zeta(x)$Cybenko NN
$\Phi(x,v)$Cybenko NN $\Phi(x,v)\pm\varepsilon$Constructions $\Psi(x,w\odot
f)$ Figure 4: An illustration of function approximation in probability with
our construction. Here, $M=256$, and $20$ independent runs of the construction
are shown in red. Here, $\epsilon=0.1$ was chosen for illustrative purposes.
Most of the runs lie within $\epsilon$ distance around the Cybenko neural
network from (15), which we approximate with our construction in (16).
Altogether, we are approximating the target function $\zeta$.

###  3.4 Explicit computation of coefficients

To further illustrate Theorem 5, we will compute the coefficients $a_{U}$ in
(13) explicitly for a special case of dropout neural networks for which the
filter variables are partitioned into independent blocks. All variables in one
block $i$ are all simultaneously off with probability $p_{i}$ and
simultaneously on with probability $1-p_{i}$. Both node-dropout and
dropconnect are special cases.

###### Proposition 8

Let $f$ be a $\\{0,1\\}^{n}$-valued random variable with a distribution
specified as follows. Let $\overline{1,n}=I_{1}\cup\ldots\cup I_{r}$ be a
disjoint partition and suppose that $f_{i}=f_{j}$ whenever $i,j\in I_{s}$ for
any $i,j\in\overline{1,n}$ and $s\in\overline{1,r}$. Let
$f=(f_{I_{1}},\ldots,f_{I_{r}})$ denote the random variables ordered as blocks
and suppose that $\mathbb{P}(f_{I_{s}}=1)=1-p_{s}>0$ for all
$s\in\overline{1,r}$ and that $\\{f_{I_{i}}\\}_{i\in\overline{1,r}}$ are
mutually independent. Then we have

$\Psi(\cdot,w)=\sum_{V\in 2^{r}}\prod_{i\in
V}\left(\frac{1}{1-p_{i}}\right)\prod_{i\in\overline{1,r}\setminus
V}\left(-\frac{p_{i}}{1-p_{i}}\right){\mathbb{E}}{}\Big{[}\Psi(\cdot,(w\odot\mathbf{1}_{\iota(V)})\odot
f^{V})\Big{]}$

where $\iota:2^{r}\to 2^{n}$ is the embedding characterized by $j\in\iota(V)$
if $j\in I_{i}$ for some $i\in V$.

We prove Proposition 8 in Appendix A.3. Note that as $p_{i}\to 1$, the
coefficients $a_{U}$ become large. From this fact, together with the
observation that the sum is taken over the large set $2^{r}$, it is clear that
the construction is computationally strenuous. Still, small examples in the
case of dropconnect are shown in Figures 2, 3 and 4.

###  3.5 Why the results in this section are only for random-approximation
dropout

In this section, we have shown a random-approximation universal approximation
result, i.e., a universal approximation result that is relevant when the
dropout neural network is also used at prediction time with a stochastic
output. In practice, the filter variables are usually replaced by their
average values at prediction time. The following example shows that the
construction in this section can lead to a bad approximation when doing
expectation-replacement.

###### Example 5

Let $\sigma$ be the standard ReLU activation function. The approximation
procedure in Corollary 6 would yield that the function
$\zeta:\mathbb{R}\to\mathbb{R}$ given by $\zeta(x):=\sigma(x-1)$ can be well
approximated by an average of many independent copies of the dropout neural
network

$x\mapsto 4f_{1}\sigma(f_{2}x-1)$

where $f_{1}$ and $f_{2}$ are i.i.d. Bernoulli random variables with success
probability $1/2$. However, replacing $f_{1}$ and $f_{2}$ by $1/2$, we just
obtain the function

$x\mapsto 2\sigma(x/2-1)$

which is not a good approximation to the function $\zeta$ at all.

##  4 Use of average filter variables for prediction

We will now approximate a neural network by a larger dropout neural network
that is also close to the original neural network if the filter variables are
replaced by their expected values. The replacement of the filter random
variables $f$ by their expected values $\mathbb{E}[f]$ is common practice
after having trained dropout neural networks for prediction. Informally, the
main Theorem 15 below states that for any base neural network $\Psi(\cdot,w)$,
there exists a larger neural network $\mathsf{NN}_{\Gamma,\Xi}(\cdot,v)$ and
filter variables $f$ such that

$\mathsf{NN}_{\Gamma,\Xi}(x,v\odot
f)\approx\Psi(x,w)\approx\mathsf{NN}_{\Gamma,\Xi}(x,v\odot\mathbb{E}[f]).$
(21)

### Global variables

In order to improve readability of this section, we fix for the entire section
a few (otherwise arbitrary) variables. Throughout this section:

  * •

The base neural network $\Psi$ is assumed to be a fixed $(L-1)$-hidden layer
neural network as described in Section 2.1. We assume that its activation
functions $\sigma_{j}$ are continuous. We also keep the weights $W^{(j)}$ and
biases $b^{(j)}$ fixed.

  * •

We fix a number $R>0$, which will play the role of the radius of a ball in the
input space.

  * •

We fix a number $\beta\in(0,1)$ and assume that for every random filter matrix
$F$ in this section, each one entry is on with a probability that is larger
than or equal to $\beta$, i.e., for all $r,c$,

$\mathbb{P}[F_{rc}=1]\geq\beta>0.$

  * •

We fix a number $Q>1$, whose role will become clear later.

S2pt

$x$$\sigma_{1}$$\sigma_{1}$$\sigma_{2}$$\sigma_{2}$$\sigma_{2}$$\sigma_{2}$$\sigma_{3}$$\sigma_{3}$$\sigma_{3}$$\sigma_{4}$$\Psi(x,w)$$(W^{(1)},b^{(1)})$$(W^{(2)},b^{(2)})$$(W^{(3)},b^{(3)})$$(W^{(4)},b^{(4)})$$\Shortstack{.}$$x$$\Shortstack{..}$$\Shortstack{....}$$\Shortstack{...}$$\Shortstack{.}$$\Psi(x,w)$

Figure 5: An example base neural network $\Psi$ where $L=4$. The top diagram
indicates the individual activation functions and the dimensions of each layer
of nodes: $d=d_{0}=1$, $d_{1}=2$, $d_{2}=4$, $d_{3}=3$, and $d_{4}=1$. The set
of all arrows connecting layer $k-1$ of nodes to layer $k$ correspond to the
parameters $(W^{(k)},b^{(k)})$. The bottom diagram shows the same network,
with the edges between layers compressed to single arrows; this compressed
notation is the basis for the diagram in Figure 6 below.

###  4.1 Heuristic description of the construction

In this section we describe the construction of the larger dropout neural
network $\mathsf{NN}_{\Gamma,\Xi}$ in heuristic terms; the full details are
given in the subsequent sections. The construction starts at the last layer of
the base neural network $\Psi$, which is a function
$\Psi_{L}:\mathbb{R}^{d_{L-1}}\to\mathbb{R}^{d_{L}}$ given by

$x\mapsto\sigma_{L}\bigl{(}W^{(L)}x+b^{(L)}\bigr{)}.$ (22)

We construct the last layer of the larger dropout neural network such that it
remains close to (22) as follows. Let $N\in\mathbb{N}$ and consider any
collection $\\{F^{(L),i}\\}_{i\in\overline{1,N}}$ of i.i.d. random filter
matrices such that for each $i$, $F^{(L),i}$ has the same dimension as
$W^{(L)}$. By the law of large numbers, we can expect that the function

$x\mapsto\sigma_{L}\biggl{(}\frac{1}{N}\sum_{i=1}^{N}\Bigl{(}\bigl{(}W^{(L)}\div\mathbb{E}[F^{(L),i}]\bigr{)}\odot
F^{(L),i}\Bigr{)}x+b^{(L)}\biggr{)}$ (23)

will be close to the function $\Psi_{L}$ for sufficiently large $N$. Here we
write $\div$ for element-wise division.

Viewed as a one-layer neural network, the function (23) is a one-layer dropout
neural network with $N$ times as many edges as $\Psi_{L}$, and it can replace
(22), i.e., $\Psi_{L}$, while staying close to $\Psi_{L}$.

A further adaptation is necessary, however, because in (23) each copy
$W^{(L)}\div\mathbb{E}[F^{(L),i}]$ takes the _same_ input
$x\in\mathbb{R}^{d_{L-1}}$. To make (23) a _bona fides_ dropout network,
different edges should take different inputs, and therefore we generalize (23)
to

$(\mathbb{R}^{d_{L-1}})^{N}\ni(x^{i})_{i\in\overline{1,N}}\mapsto\sigma_{L}\biggl{(}\frac{1}{N}\sum_{i=1}^{N}\Bigl{(}\bigl{(}W^{(L)}\div\mathbb{E}[F^{(L),i}]\bigr{)}\odot
F^{(L),i}\Bigr{)}x^{i}+b^{(L)}\biggr{)}.$ (24)

By precomposing each of the inputs $x^{i}$ with $\Psi^{(L-1)}$, and performing
the same construction as above (copying the input to these copies of
$\Psi^{(L-1)}$), we can inductively create our larger dropout neural network
$\mathsf{NN}_{\Gamma,\Xi}$ that will be close to $\Psi$.

There are now three points of attention:

  * •

The intuitive statement ‘repeating this construction’ needs a formalization by
an inductive construction. This requires a mathematical object that can record
the intermediate stages of the construction.

  * •

We need to show inductively that the resulting intermediate neural networks
are close to (a network closely related to) the original network. In
particular, we need to introduce a mathematical specification of ‘close’ that
is compatible with an inductive argument.

  * •

The input space to the neural network in this construction grows with each
step, whereas we still aim to have a final neural network with data space
$\mathbb{R}^{d}$. This requires us to deal with the first layer of the network
differently.

These points are the topics of the subsequent sections.

###  4.2 Dropout-trees

We will encode the intermediate stages of our inductive construction by a
mathematical object that we will refer to as a _dropout-tree_. The idea is
that we start with a root, then attach incoming edges labeled with random
filter matrices to it (creating leaves), and then recursively attach even more
edges to the leaves. To be consistent with the numbering of layers in Section
2.1, here, we will prefer to speak about the _level_ $j$ of a vertex or an
edge in a tree rather than its depth $L-j$ (the latter is also established
jargon in graph theory, and this aligns our notation with that of the neural
network). In this numbering, the root is therefore at level $L$.

###### Definition 9

A vertex $v$ of a rooted tree is at _level_ $j\in\\{0,1,\ldots,L\\}$ if the
path from $v$ to the root $v_{0}$ has length $L-j$. An edge $e=(u,v)$ of a
rooted tree is at _level_ $j\in\\{0,1,\ldots,L\\}$ if its target vertex $v$ is
at level $j$.

From now on we will write $\sigma_{v}$ for $\sigma_{\mathsf{level}(v)}$,
$W^{v}$ for $W^{(\mathsf{level}(v))}$, $b^{v}$ for $b^{(\mathsf{level}(v))}$,
_et cetera_. This simplifies the notation at only a minor cost of abuse of
notation.

###### Definition 10

A _dropout-tree_ $\Gamma$ of an $(L-1)$-hidden layer neural network $\Psi$ is
a directed graph $\mathcal{G}$ together with a labeling of the edges such
that:

  * •

the graph $\mathcal{G}$ is connected and acyclic;

  * •

one of the vertices, say $v_{0}$, is designated as the _root_ ;

  * •

the depth of the tree is at most $L-1$;

  * •

all directed edges point towards the root;

  * •

every edge $e$ is labeled with a random matrix $F^{e}$; for each $e$

    * (a)

$F^{e}$ has the same dimension as $W^{\mathsf{target}(e)}$

    * (b)

$F^{e}$’s entries are $\\{0,1\\}$-valued

    * (c)

for all $r,c$, $\mathbb{P}[F^{e}_{rc}=1]\geq\beta>0$;

  * •

for every vertex $v$ that is not a leaf, $\\{F^{e}\\}_{e\in\mathsf{into}(v)}$
is a collection of mutually independent, identically distributed random
matrices.

For convenience we recall some terminology. A directed edge points from a
_source_ to a _target_ , and for an edge $e$ we identify them by
$\mathsf{source}(e)$ and $\mathsf{target}(e)$; we write $\mathsf{into}(v)$ for
the set of all edges with target vertex $v$. In the trees in this paper, all
edges point towards the root of the tree. A vertex $v$ is a _child_ of a
vertex $w$ if there is an edge pointing from $v$ to $w$; $w$ then is the
_parent_ of $v$. A _leaf_ is a vertex without children.

Dropout-trees can be constructed iteratively by starting from the trivial
dropout-tree consisting only of a root and then performing a so-called _$\mu$
-input-copy_ construction. This allows us to inductively create a larger
dropout-tree from a smaller dropout-tree.

###### Definition 11

Let $\Gamma$ be a dropout-tree and let $\ell$ be a leaf of $\Gamma$ at level
$k$. Let $\mu$ be a distribution of a random matrix
$F\in\\{0,1\\}^{d_{k}\times d_{k-1}}$ that satisfies for all $r,c$,
$\mathbb{P}[F_{rc}=1]\geq\beta>0$. A dropout-tree $\Gamma^{\prime}$ is a
_$\mu$ -input-copy to the leaf $\ell$ of $\Gamma$_ if one can obtain
$\Gamma^{\prime}$ from $\Gamma$ by: (a) attaching child vertices to $\ell$,
and (b) labeling each edge going into $\ell$ by an independent copy of $F$.
The _size of a $\mu$-input-copy to $\ell$ at $\Gamma$_ refers to the number of
children of $\ell$ in $\Gamma^{\prime}$.

Let us describe the precise meaning of procedure (b) in Definition 11. For
that, it may be useful to recall that random matrices are nothing but
measurable functions defined on the probability space
$(\Omega,\mathcal{F}_{\Omega},\mathbb{P})$. The procedure (b) precisely means
that the sigma-algebras generated by the filter variables $F^{e}$ with
$e\in\mathsf{into}(\ell)$ are independent, and that for every
$e\in\mathsf{into}(\ell)$ the law of $F^{e}$ equals $\mu$. In particular, this
condition allows for some correlation between filter variables labeling edges
in the dropout-tree that do not go into $\ell$. Moreover, in general there can
be many different dropout trees $\Gamma^{\prime}$ that are $\mu$-input-copies
of $\Gamma$.

We will now describe how a dropout-tree encodes a dropout neural network.

####  4.2.1 Dropout neural networks encoded by dropout-trees

Each dropout-tree $\Gamma$ will induce a stochastic function
$\Phi^{v_{0}}_{\Gamma}$—a dropout neural network—as follows. For any edge
$e=(u,v)$ of $\Gamma$, let

$V^{e}_{\Gamma}:=W^{e}\div\mathbb{E}[F^{e}]$ (25)

be rescaled weights for the dropout neural network. We define

$\Phi^{v}_{\Gamma}:=\begin{cases}\sigma_{v}\Bigl{(}\frac{1}{\\#\mathsf{into}(v)}\sum_{e\in\mathsf{into}(v)}(V^{e}\odot
F^{e})\Phi^{\mathsf{source}(e)}_{\Gamma}+b^{v}\Bigr{)}&\textnormal{if
}v\textnormal{ is not a leaf},\\\
\mathrm{Identity}_{\mathbb{R}^{d_{v}}}&\textnormal{if $v$ is a
leaf}.\end{cases}$

Figure 6 illustrates this construction, based on the network $\Psi$ depicted
in Figure 5.

###  4.3 Dropout neural networks induced by dropout-trees are close to their
deterministic counterpart

We will give an inductive argument that $\Phi^{v_{0}}_{\Gamma}$ is close to
$\Phi^{v_{0}}_{\Gamma_{\mathsf{det}}}$. Here, $\Gamma_{\mathsf{det}}$ denotes
the same dropout-tree as $\Gamma$ except for the fact that we have replaced
each and every filter variable deterministically by its expectation. Loosely
speaking, the inductive argument implies that dropout neural networks induced
by dropout-trees are close to their deterministic counterparts.

As a technical preparation, we define a sequence of radii
$R_{0},R_{1},\dots,R_{L}$. The idea is that these provide bounds on the output
after applying several layers, no matter the choice of filter variables or
weights in the upcoming construction. Given the radius $R>0$ defined at the
start of this section, we set

$R_{0}:=\frac{Q}{\beta}R+1$

and then choose $R_{j}$ inductively such that for all $j\in\overline{1,L}$,
$x\in B(0,\allowbreak\beta^{-1}\|W^{(j)}\|_{\mathrm{HS}}R_{j-1}+1)$ it holds
that

$\Bigl{|}\Psi_{j}\Bigl{(}x,\bigl{(}I,b^{(j)}\bigr{)}\Bigr{)}\Bigr{|}<R_{j}-1.$
(26)

for all $j=\overline{1,L}$, where $\beta\in(0,1)$ and $Q>1$ were two of the
global variables that we defined at the beginning of the section. Here
$\|\cdot\|_{\mathrm{HS}}$ denotes the Hilbert–Schmidt norm of a matrix and $I$
denotes an identity matrix of the corresponding size.

We denote the input space to a network induced by a dropout-tree $\Gamma$ by
$\mathsf{Inp}_{\Gamma}$. That is, $\mathsf{Inp}_{\Gamma}$ is the vector space

$(x^{\ell}\in\mathbb{R}^{d_{\mathsf{level}(\ell)}}\ |\
\ell\in\mathsf{leaves}(\Gamma)).$

We endow $\mathsf{Inp}_{\Gamma}$ with the norm

$\|(x^{\ell})\|_{\mathsf{Inp}_{\Gamma}}:=\max_{l\in\mathsf{leaves}(\Gamma)}\|x^{\ell}\|_{\mathbb{R}^{d_{\mathsf{level}(\ell)}}}.$

We define $\mathsf{In}_{\Gamma}:\mathbb{R}^{d}\to\mathsf{Inp}_{\Gamma}$ to be
the collection of functions, indexed by leaves $\ell$ of $\Gamma$, that are
generated by those layers in the base network $\Psi$ that are _not_
represented in $\Gamma$ at leaf $\ell$:

$\mathsf{In}_{\Gamma}^{\ell}(x):=\left(\Psi_{\mathsf{level}(\ell)}(\cdot,(W^{(\mathsf{level}(\ell))},b^{(\mathsf{level}(\ell))}))\circ\dots\circ\Psi_{1}(\cdot,(W^{(1)},b^{(1)}))\right)(x).$
(27)

Note that by the definitions (26) of the radii $R_{j}$ we have

$\mathsf{In}_{\Gamma}^{\ell}\bigl{(}\,\overline{B(0,R)}\,\bigr{)}\subset
B(0,R_{\mathsf{level}(\ell)}-1).$ (28)

We say that a dropout-tree $\Gamma$ satisfies property
$\mathsf{ApProp}_{\Gamma}(\delta,\epsilon)$ if

$\mathbb{P}\Bigl{[}\sup_{x\in\overline{B(0,R)}}\sup_{\tilde{x}\in\overline{B(\mathsf{In}_{\Gamma}(x),\delta)}}\bigl{|}\Phi^{v_{0}}_{\Gamma}(\tilde{x})-\Phi^{v_{0}}_{\Gamma_{\det}}(\mathsf{In}_{\Gamma}(x))\bigr{|}>\frac{\epsilon}{2}\Bigr{]}<\Bigl{(}\frac{\epsilon}{4R_{L}}\Bigr{)}^{q}.$
(29)

We will prove Lemma 12: its message is that one can always construct a full
dropout-tree that satisfies $\mathsf{ApProp}_{\Gamma}(\delta,\epsilon)$ for
some $\delta>0$, by copying inputs at vertices.

###### Lemma 12

Let $\Gamma$ be a dropout-tree and let $\ell$ be a leaf of $\Gamma$ at level
$k>1$. Let $\mu$ be the distribution of a random matrix
$F\in\\{0,1\\}^{d_{k}\times d_{k-1}}$ that satisfies for all $r,c$,
$\mathbb{P}[F_{rc}=1]\geq\beta>0$. The following now holds: if $\Gamma$
satisfies $\mathsf{ApProp}_{\Gamma}(\delta,\epsilon)$ in (29) for some
$\delta,\epsilon>0$, then for every sufficiently large $\mu$-input-copy
$\Gamma^{\prime}$ at $\ell$ there exists a $\delta^{\prime}>0$ such that
$\Gamma^{\prime}$ satisfies
$\mathsf{ApProp}(\Gamma^{\prime})(\delta^{\prime},\epsilon)$.

The proof of Lemma 12 is relegated to Section B.1. There, we show that Lemma
12 follows from Lemma 13, which is displayed next and proved in Section B.2.

###### Lemma 13

Consider any continuous function $\sigma:\mathbb{R}^{m}\to\mathbb{R}^{m}$ and
let $W\in\mathbb{R}^{m\times n}$, $b\in\mathbb{R}^{m}$. Let
$\\{F^{i}\\}_{i\geq 1}$ be a sequence of mutually independent copies of a
random matrix $F\in\mathbb{R}^{m\times n}$ that satisfies: for
$r\in\overline{1,m}$ and $c\in\overline{1,n}$, $0<\mathbb{E}[F_{rc}]<\infty$
and $0\leq F_{rc}\leq M<\infty$ w.p. one. Let $V:=W\div\mathbb{E}[F]$. The
following now holds: for every $0\leq K<\infty$ and $\rho>0$ there exists a
$\delta>0$ such that

$\mathbb{P}\Bigl{[}\sup_{x\in\overline{B(0,K)}}\sup_{(\tilde{x}^{i})\in\overline{B(x,\delta)}^{N}}\Bigl{|}\sigma\Bigl{(}\frac{1}{N}\sum_{i=1}^{N}(V\odot
F^{i})\tilde{x}^{i}+b\Bigr{)}-\sigma(Wx+b)\Bigr{|}>\rho\Bigr{]}\to 0$ (30)

as $N\to\infty$.

###  4.4 Replacing the first layer

Assume now that we have constructed a full dropout-tree, that is, a dropout-
tree of which all leaves are at level $1$ (i.e., at depth $L-1$). This means
that we have constructed suitable replacements for almost every layer of the
neural network, except for the first layer. This layer contains the edges that
have the global input as source. Replacing the first layer requires a
different construction: if we would outright drop edges in the first layer,
then we can not control the error with the current technique. We now describe
how we replace the first layer.

For every leaf $\ell$ in the full dropout-tree, we precompose every input at
$\ell$ with a stochastic function
$\Xi^{\ell}:\mathbb{R}^{d_{0}}\to\mathbb{R}^{d_{1}}$. We record this
information in what we call a _precomposition_ for a dropout-tree. Figure 6
illustrates this precomposition.

###### Definition 14

A _precomposition_ for a full dropout-tree $\Gamma$ is a map
$\Xi:\mathbb{R}^{d_{0}}\to\mathbb{R}^{d_{1}}$ from leaves to stochastic
functions.

Let
$\Delta:\mathbb{R}^{d_{0}}\to(\mathbb{R}^{d_{0}})^{\mathsf{leaves}_{\Gamma}}$
be the diagonal map sending $x$ to copies of $x$. The neural network induced
by the full dropout-tree $\Gamma$ and a precomposition $\Xi$ that we consider
is given by

$\mathsf{NN}_{\Gamma,\Xi}:=\Phi^{v_{0}}_{\Gamma,\Xi}\circ\Delta$ (31)

where

$\Phi^{v}_{\Gamma,\Xi}=\begin{cases}\sigma_{v}\Bigl{(}\frac{1}{\\#\mathsf{into}(v)}\sum_{e\in\mathsf{into}(v)}(V^{e}\odot
F^{e})\Phi^{\mathsf{source}(e)}_{\Gamma,\Xi}+b^{e}\Bigr{)}&\textnormal{if
}v\textnormal{ is not a leaf},\\\ \Xi^{v}&\textnormal{if $v$ is a
leaf}.\end{cases}$ (32)

We also define $\mathsf{NN}^{\mathsf{avg-filt}}_{\Gamma,\Xi}$ as being almost
the same neural network as $\mathsf{NN}_{\Gamma,\Xi}$, with the only
difference being that we replace each random filter variable $F^{e}$ in (32)
with its expectation $\mathbb{E}[F^{e}]$. Recall for (31) that $v_{0}$
designates the root of the dropout-tree, and note that (32) constructs the
neural network recursively (layer by layer).

S2pt

$\Shortstack{.}$$\mathsf{NN}_{\Gamma,\Xi}(x)$$\Shortstack{...}$$\Shortstack{...}$$\Shortstack{...}$$\Shortstack{....}$$\Shortstack{....}$$\Shortstack{..}$$\Shortstack{..}$$\Shortstack{..}$$\Shortstack{..}$$\Shortstack{.}$$\Shortstack{.}$$\Delta$$x$
$\sigma_{4}$ $\sigma_{3}$ $\sigma_{2}$ $\sigma_{1}$ $\sigma_{0}$
$\underbrace{\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\ }{}$ $\Xi$ root
level $3$ level $2$ leaves at level $1$ level $0$ copying

Figure 6: An illustration of how we use the base neural network $\Psi$ from
Figure 5 and a dropout-tree (indicated with thicker arrows) to ultimately
construct the larger neural network $\mathsf{NN}_{\Gamma,\Xi}$ in which edges
are being dropped stochastically. Here, $L=4$.

###### Example 6

One natural precomposition $\Xi$ is the assignment of the function
$\Psi^{1}(\cdot,(W^{(1)},b^{(1)}))$ to every leaf. This precomposition yields
a neural network in which edges in the first layer, i.e., the input edges of
the neural network, are never dropped. In this case,
$\mathsf{NN}^{\mathsf{avg-filt}}_{\Gamma,\Xi}(w)$ actually coincides with the
original neural network $\Psi(\cdot,w)$.

####  4.4.1 Precompositions in which inputs are dropped

We will now construct precompositions that allow for the possibility of
dropping edges in the first layer and applying e.g. the ReLU function to them
immediately. Concretely, we will add a zeroth layer with an activation
function $\sigma_{0}:\mathbb{R}\to\mathbb{R}$. We assume that
$\sigma_{0}(0)=0$ and that $\sigma_{0}$ has one-sided derivatives $\sigma_{-}$
and $\sigma_{+}$ in the point $0\in\mathbb{R}$:

$\sigma_{-}:=\lim_{\alpha\downarrow
0}\frac{\sigma_{0}(-\alpha)-\sigma_{0}(0)}{\alpha},\quad\sigma_{+}:=\lim_{\alpha\downarrow
0}\frac{\sigma_{0}(+\alpha)-\sigma_{0}(0)}{\alpha}.$ (33)

Define the sign function

$S(x)=\begin{cases}-&\textnormal{if }x<0,\\\ +&\textnormal{if }x\geq
0\end{cases}$ (34)

component-wise. If $x\neq 0$, then
$\sigma_{S(-x)}+\sigma_{S(x)}=\sigma_{-}+\sigma_{+}$ does not depend on $x$—a
critical fact that we will leverage in our construction.

###### Example 7

Consider a zeroth layer that is the identity function, i.e.,
$\sigma_{0}(y)=y$. Then $\sigma_{\pm}=1$. Choosing $\sigma_{0}$ as the
identity function is allowed here, and means that the layer is not adapted.

###### Example 8

Consider a zeroth layer with ReLU activation function,
$\sigma_{0}:=\mathrm{ReLU}(z):=z\mathds{1}[z\geq 0]$. Then $\sigma_{-}=0$ and
$\sigma_{+}=1$.

Here are the precompositions that we employ: we call $\Xi$ an _$(\alpha,N)$
-precomposition associated to a set of distributions
$\\{\mu^{\ell},\nu^{\ell}\\}_{l\in\mathrm{leaves}(\Gamma)}$_ if for each leaf
$\ell$,

$\Xi^{\ell}(x):=\sigma_{1}\Bigl{(}\frac{1}{N}\sum_{i=1}^{2N}(-1)^{i}(V^{\ell}\odot
F^{\ell,i})\sigma_{0}\bigl{(}(-1)^{i}\alpha(I\odot
G^{\ell,i})x\bigr{)}+b^{\ell}\Bigr{)}$ (35)

where element-wise

$V^{\ell}_{rc}=\frac{W^{(1)}_{rc}}{\alpha\bigl{(}\sigma_{-}+\sigma_{+}\bigr{)}\,\mathbb{E}[F^{\ell}_{rc}]\,\mathbb{E}[G^{\ell}_{cc}]},$
(36)

and $\\{F^{\ell,i}\\}_{i\geq 1}$, $\\{G^{\ell,i}\\}_{i\geq 1}$ are sequences
of mutually independent copies of random matrices $F^{\ell},G^{\ell}$ that
have distributions $\mu^{\ell}$, $\nu^{\ell}$, respectively. Furthermore, the
$F^{\ell}$ are presumed to have the same size as $W^{(1)}$, and the $G^{\ell}$
to have size $d_{0}\times d_{0}$. Note that these assumptions allow us to
place unit mass on any particular outcome and thus to replace
$F^{\ell},G^{\ell}$ by deterministic counterparts.

The idea of (35) is that it represents two layers of a dropout neural network
that satisfies the approximation properties we are after. The functions
$\sigma_{1}$, $\sigma_{0}$ can be understood as their activation functions,
the matrices $V^{\ell}$, $\alpha I$ as their weights, $b^{\ell}$ as a bias,
and the matrices $F^{\ell}$, $G^{\ell}$ as describing which edges and inputs
are randomly removed. By scaling the weights $V^{\ell}$ by $1/(2N)$ and
generating $2N$ independent copies of the first layer, we are preparing for an
application of the law of large numbers. Furthermore, by allowing for
arbitrarily small $\alpha$, we are preparing for a linearization of
$\sigma_{0}$ around $0$. Finally, the alternatingly positive and negative
multiplicative factors $(-1)^{i}$ allow us to cover directional derivatives
such as that of the ReLU activation function. All together, the construction
allows us to prove the following theorem.

###### Theorem 15

Fix $0<\epsilon<1$. Let $\Gamma$ be a full dropout-tree satisfying
$\mathsf{ApProp}_{\Gamma}(\delta,\epsilon)$ for some $\delta>0$. Let $\Xi$ be
an $(\alpha,N)$-precomposition associated to a set of distributions
$\\{\mu^{\ell},\nu^{\ell}\\}_{\ell\in\mathrm{leaves}(\Gamma)}$. Assume that
for every $\ell$, if $F$ is a matrix of filter variables distributing
according to $\mu^{\ell}$ or $\nu^{\ell}$, then for every $r,c$,

$\mathbb{P}[F_{rc}=1]\geq\beta>0.$

Let $\sigma_{0}:\mathbb{R}\to\mathbb{R}$ be a continuous function with one-
sided derivatives $\sigma_{-}$ and $\sigma_{+}$ in $0$, such that
$\sigma_{-}+\sigma_{+}\neq 0$ and such that $\sigma_{0}(0)=0$. Assume moreover
that $\sigma_{-}$ and $\sigma_{+}$ satisfy the following inequality with
respect to the global variable $Q$:

$4\frac{|\sigma_{-}|+|\sigma_{+}|}{|\sigma_{-}+\sigma_{+}|}<Q.$ (37)

The following inequalities now hold for $\alpha>0$ small enough and
$N\in\mathbb{N}$ large enough:

$\mathbb{P}\Bigl{[}\sup_{x\in\overline{B(0,R)}}\bigl{|}\mathsf{NN}_{\Gamma,\Xi}(x)-\Psi(x,w)\bigr{|}>\epsilon\Bigr{]}<\epsilon$
(38)

and

$\mathbb{E}\Bigl{[}\sup_{x\in\overline{B(0,R)}}\bigl{|}\mathsf{NN}_{\Gamma,\Xi}(x)-\Psi(x,w)\bigr{|}^{q}\Bigr{]}^{1/q}<\epsilon,$
(39)

while

$\sup_{x\in\overline{B(0,R)}}\Bigl{|}\mathsf{NN}^{\mathsf{avg-
filt}}_{\Gamma,\Xi}(x)-\Psi(x,w)\Bigr{|}<\epsilon.$ (40)

An important consequence of Theorem 15 is that we obtain for instance a
universal approximation result for dropconnect neural networks with ReLU
activation functions that also guarantees a good approximation when filter
variables are replaced by their averages, as formalized by Corollary 4 in the
introduction. Theorem 15 is proven in Section B.3. There, we show that Theorem
15 follows from the following Lemma 16, which in turn is proven in Section B.4
using compactness arguments and the law of large numbers.

###### Lemma 16

Let $\sigma_{0}:\mathbb{R}\to\mathbb{R}$ be a continuous function with
$\sigma(0)=0$ and with two one-sided derivatives $\sigma_{-}$ and $\sigma_{+}$
in $0$ satisfying $|\sigma_{-}+\sigma_{+}|>0$. Let $\Xi$ be an
$(\alpha,N)$-precomposition associated to a set of distributions
$\\{\mu^{\ell},\nu^{\ell}\\}_{l\in\mathrm{leaves}(\Gamma)}$ such that for all
$\ell,r,c$, $\mathbb{E}[F^{\ell}_{rc}]>0,\mathbb{E}[G^{\ell}_{rc}]>0$, $0\leq
F^{\ell}_{rc}\leq M$ w.p. one, and $0\leq G^{\ell}_{rc}\leq M<\infty$ w.p.
one. The following now holds: for every leaf $\ell$, $0\leq K<\infty$, and
$\rho>0$, for $\alpha$ small enough and $N$ large enough,

$\mathbb{P}\Bigr{[}\sup_{x\in\overline{B(0,K)}}\bigl{|}\Xi^{\ell}(x)-\Psi_{1}(x;(W^{(1)},b^{(1)}))\bigr{|}>\rho\Bigr{]}<\rho$
(41)

and

$\sup_{x\in\overline{B(0,K)}}\bigl{|}\Xi^{\ell,\mathsf{avg-
filt}}(x)-\Psi_{1}(x;(W^{(1)},b^{(1)}))\bigr{|}<\rho$ (42)

where $\Xi^{\ell,\mathsf{avg-filt}}$ denotes the function $\Xi^{\ell}$ in (35)
but with each filter variable $F^{\ell,i}$ replaced by its expectation
$\mathbb{E}[F^{\ell}]$ .

##  5 Discussion

In this article, we showed that dropout neural networks are rich enough for a
universal approximation property to hold, both for random-approximation and
expectation-replacement dropout. It is further evidence that the
representational capacity of neural networks is so large that approximations
are possible despite significant additional constraints. In the case of
dropout in general, these additional constraints are the implicit symmetry
constraints enforced by the turning on and off of the filter variables: in
dropconnect, for instance, for most realizations of the filter variables, the
output of the dropconnect neural network still approximates the original
neural network well after the filter variables are randomly permuted. Despite
the enforced invariance with respect to this operation, there is enough room
in the parameter space for the weights of the network to have a good
approximation for the overwhelming majority of realizations of the filter
variables.

Our proof of the universal approximation property for random-approximation
dropout explicitly works with this symmetry. By this, we mean the following.
The universal approximation property that we show even works when edges from
the input nodes are dropped out at random. The output in the first hidden
layer is then inherently _random_ , and in no way close to deterministic. This
is in contrast with for instance the universal approximation property by Foong
et al. (2020) in which the layers are all very close to deterministic. Yet
even though the values in the nodes are random, we do have a good
understanding of the _distribution_ of the values in the nodes, and two
stochastic realizations are most likely almost permutations of each other. By
blowing up the first layer, i.e., repeating it many times in parallel, we then
know the output very well up to this permutation symmetry and this turns out
to be enough for us to show a universal approximation property.

###  5.1 Limitations of our results

Our results and methods have several limitations.

We only show the _existence_ of dropout neural networks close to a given
function. It is a completely separate question whether an algorithm such as
dropout stochastic gradient descent would actually be able to find such an
approximation. The main message of our result is that at least there is no
theoretical obstruction to approximating functions with dropout neural
networks.

In the proofs, we used very explicitly that filter variables only take on the
values zero or one, while other forms of dropout also exist (for instance with
Gaussian filter variables). Our algebraic proof does not readily generalize to
this more general case, but it is possible that parts of the proof could be
reused.

We also see that universal approximation goes hand in hand with blowing up the
size of the neural network. As illustrated by the explicit computations in
Section 3.4, one would likely need so many nodes that the constructions in the
article are not feasible in practice.

##  6 Conclusion

We showed two types of universal approximation results for dropout neural
networks, one for random-approximation dropout, in which case the random
filter variables are also used at prediction time, and one for expectation-
replacement dropout, in which case the filter variables are replaced by their
averages at prediction time. Our results allow for dropout of edges from the
input layer, allow for a wide class of distributions on filter variables,
including dropout of edges from the input layer, and for a wide class of
activation functions.

By making the difference between random-approximation and expectation-
replacement dropout explicit, our results also highlight the following
mystery: How is it that expectation-replacement dropout performs so well on
prediction time?

## Acknowledgments

J.W. Portegies was supported by the Electronic Component Systems for European
Leadership Joint Undertaking under grant agreement No 737459 (project
Productive 4.0). This Joint Undertaking receives support from the European
Union Horizon 2020 research and innovation program and Germany, Austria,
France, Czech Republic, Netherlands, Belgium, Spain, Greece, Sweden, Italy,
Ireland, Poland, Hungary, Portugal, Denmark, Finland, Luxembourg, Norway,
Turkey.

## References

  * Cybenko (1989) George Cybenko.  Approximation by superpositions of a sigmoidal function.  _Mathematics of control, signals and systems_ , 2(4):303–314, 1989.
  * De Bie et al. (2018) Gwendoline De Bie, Gabriel Peyré, and Marco Cuturi.  Stochastic deep networks.  _arXiv preprint arXiv:1811.07429_ , 2018.
  * Elbrächter et al. (2020) Dennis Elbrächter, Dmytro Perekrestenko, Philipp Grohs, and Helmut Bölcskei.  Deep neural network approximation theory.  _IEEE Transactions on Information Theory, submitted Jan. 2019, revised_ , June 2020.  URL http://www.nari.ee.ethz.ch/pubs/p/deep-it-2019.
  * Foong et al. (2020) Andrew Foong, David Burt, Yingzhen Li, and Richard Turner.  On the expressiveness of approximate inference in Bayesian neural networks.  _Advances in Neural Information Processing Systems_ , 33, 2020.
  * Gallicchio and Scardapane (2020) Claudio Gallicchio and Simone Scardapane.  Deep randomized neural networks.  In _Recent Trends in Learning From Data_ , pages 43–68. Springer, 2020.
  * Gelenbe et al. (1999a) Erol Gelenbe, Zhi-Hong Mao, and Yan-Da Li.  Function approximation with spiked random networks.  _IEEE Transactions on Neural Networks_ , 10(1):3–9, 1999a.
  * Gelenbe et al. (1999b) Erol Gelenbe, Zhi-Wong Mao, and Yan-Da Li.  Approximation by random networks with bounded number of layers.  In _Neural Networks for Signal Processing IX: Proceedings of the 1999 IEEE Signal Processing Society Workshop (Cat. No. 98TH8468)_ , pages 166–175. IEEE, 1999b.
  * Goodfellow et al. (2016) Ian Goodfellow, Yoshua Bengio, and Aaron Courville.  _Deep learning_.  MIT press, 2016.
  * Hinton et al. (2012) Geoffrey E. Hinton, Nitish Srivastava, Alex Krizhevsky, Ilya Sutskever, and Ruslan R. Salakhutdinov.  Improving neural networks by preventing co-adaptation of feature detectors.  _arXiv preprint arXiv:1207.0580_ , 2012.
  * Hornik (1991) Kurt Hornik.  Approximation capabilities of multilayer feedforward networks.  _Neural networks_ , 4(2):251–257, 1991.
  * Igelnik and Pao (1995) Boris Igelnik and Yoh-Han Pao.  Stochastic choice of basis functions in adaptive function approximation and the functional-link net.  _IEEE Transactions on Neural Networks_ , 6(6):1320–1329, 1995.
  * Labach et al. (2019) Alex Labach, Hojjat Salehinejad, and Shahrokh Valaee.  Survey of dropout methods for deep neural networks.  _arXiv preprint arXiv:1904.13310_ , 2019.
  * Leshno et al. (1993) Moshe Leshno, Vladimir Ya Lin, Allan Pinkus, and Shimon Schocken.  Multilayer feedforward networks with a nonpolynomial activation function can approximate any function.  _Neural networks_ , 6(6):861–867, 1993.
  * Makovoz (1996) Yuly Makovoz.  Random approximants and neural networks.  _Journal of Approximation Theory_ , 85(1):98–109, 1996.
  * Makovoz (1998) Yuly Makovoz.  Uniform approximation by neural networks.  _Journal of Approximation Theory_ , 95(2):215–228, 1998.
  * Nguyen (2017) Hien Nguyen.  A universal approximation theorem for Gaussian-gated mixture of experts models.  _Available at SSRN 2946964_ , 2017.
  * Nguyen et al. (2016) Hien D. Nguyen, Luke R. Lloyd-Jones, and Geoffrey J. McLachlan.  A universal approximation theorem for mixture-of-experts models.  _Neural computation_ , 28(12):2585–2593, 2016\.
  * Pao et al. (1994) Yoh-Han Pao, Gwang-Hoon Park, and Dejan J. Sobajic.  Learning and generalization characteristics of the random vector functional-link net.  _Neurocomputing_ , 6(2):163–180, 1994.
  * Pinkus (1999) Allan Pinkus.  Approximation theory of the MLP model in neural networks.  _Acta numerica_ , 8:143–195, 1999.
  * Rahimi and Recht (2008) Ali Rahimi and Benjamin Recht.  Uniform approximation of functions with random bases.  In _2008 46th Annual Allerton Conference on Communication, Control, and Computing_ , pages 555–561. IEEE, 2008.
  * Timotheou (2010) Stelios Timotheou.  The random neural network: a survey.  _The computer journal_ , 53(3):251–267, 2010\.
  * Wager et al. (2013) Stefan Wager, Sida Wang, and Percy S Liang.  Dropout training as adaptive regularization.  In _Advances in Neural Information Processing Systems_ , pages 351–359, 2013.
  * Wan et al. (2013) Li Wan, Matthew Zeiler, Sixin Zhang, Yann Le Cun, and Rob Fergus.  Regularization of neural networks using Dropconnect.  In _International Conference on Machine Learning_ , pages 1058–1066, 2013.
  * White (1989) Halbert White.  An additional hidden unit test for neglected nonlinearity in multilayer feedforward networks.  In _Proceedings of the international joint conference on neural networks_ , volume 2, pages 451–455. Washington, DC, 1989.
  * Yin (2019) Yonghua Yin.  Random neural network methods and deep learning.  _Probability in the Engineering and Informational Sciences_ , pages 1–31, 2019.

##  A Proofs of Section 3

###  A.1 Proof of Theorem 5

We require the following algebraic lemma, which lies at the heart of Theorem
5, as it implies the existence of the constants $(a_{U})$.

###### Lemma 17

Let $\Psi:\mathbb{R}^{d}\times\mathbb{R}^{n}\to\mathbb{R}$ be a function. Let
$(f^{U})$ be a collection of $\\{0,1\\}^{n}$-valued random variables indexed
by subsets $U\subset\overline{1,n}$, such that for every $U$

$\mathbb{P}[f^{U}=(1,\dots,1)]>0.$

Then for every subset $V\subset\overline{1,n}$, it holds that

$\begin{split}\Psi(\cdot,w\odot\mathbf{1}_{V})\in\mathrm{span}\left\\{\mathbb{E}\left[\Psi(\cdot,(w\odot\mathbf{1}_{U})\odot
f^{U})\right]:U\in 2^{n}\right\\}\end{split}$

where for any subset $S\in 2^{d}$, i.e., $S\subset\\{1,\dots,d\\}$, we denote
by $\mathbf{1}_{S}$ the characteristic function of $S$.

Proof  The proof is by induction on the cardinality of $V$ and follows from
the equality

$\displaystyle\Bigl{(}\sum_{S:V\subset
S}\mathbb{P}[f^{V}=\mathbf{1}_{S}]\Bigr{)}\Psi(\cdot,w\odot\mathbf{1}_{V})$
$\displaystyle=\mathbb{E}\Bigl{[}\Psi(\cdot,(w\odot\mathbf{1}_{V})\odot
f^{V})\Bigr{]}$ $\displaystyle\phantom{=}-\sum_{S:V\setminus
S\neq\emptyset}\mathbb{P}[f^{V}=\mathbf{1}_{S}]\Psi(\cdot,w\odot\mathbf{1}_{S\cap
V}).$ (43)

In particular, for the base case in which $V$ is empty, the last term
vanishes. In the induction step, the functions
$\Psi(\cdot,w\odot\mathbf{1}_{S\cap V})$ are by the induction hypothesis all
in the required span.

Proof (of Theorem 5) By Lemma 17, we can find constants $a_{U}$ for $U\in
2^{n}$ such that (13) holds. We look now at (14). By the law of large numbers,
convergence in probability in the normed vector space
$(\mathcal{F},\|\cdot\|)$ follows. Moreover, for any $V\in 2^{n}$ we have

$\|\Psi(\cdot,(w\odot\mathbf{1}_{V})\odot
f^{V})\|{}_{\mathcal{F}}\leq\max_{U\in
2^{n}}\|\Psi(\cdot,(w\odot\mathbf{1}_{U})\odot
f^{U})\|{}_{\mathcal{F}}=:C_{w},$ (44)

so that for any $q\in[1,\infty)$ and $M$,

$\mathbb{E}\Bigl{[}\Bigl{\|}\frac{1}{M}\sum_{i=1}^{M}\sum_{U\in
2^{n}}a_{U}\Psi(\cdot,(w\odot\mathbf{1}_{U})\odot
f^{i,U})\Bigr{\|}_{\mathcal{F}}^{q}\Bigr{]}^{\frac{1}{q}}\leq\max_{U\in
2^{n}}|a_{U}|C_{w}.$ (45)

With uniform boundedness for all $M$, we can use the dominated convergence
theorem which implies then convergence in $L^{q}$ of the $\mathcal{F}$-valued
random variables as $M\to\infty$.

###  A.2 Proof of Corollary 6

Proof  Let $\zeta\in\mathcal{F}$ and let $\epsilon>0$. Assume there exists a
$(m,\Phi,f)\in\mathsf{DDNN}$ and a $v\in\mathbb{R}^{m}$ such that
$\|\Phi(\cdot,v)-\zeta\|_{\mathcal{F}}<\epsilon$. Define
$\eta:=\epsilon-\|\Phi(\cdot,v)-\zeta\|_{\mathcal{F}}>0$. Define the
collection $(f^{U})$ of $\\{0,1\\}^{m}$-valued filter variables, each being
specifically an independent copy of $f$. By Theorem 5, there exist constants
$(a_{U})$, a number $M\in\mathbb{N}$ and $2^{m}M$ independent copies
$(f^{i,U})$ of $f$ such that

$\mathbb{P}\Bigl{[}\Bigl{\|}\frac{1}{M}\sum_{i=1}^{M}\sum_{U\in
2^{m}}a_{U}\Phi(\cdot,(v\odot\mathbf{1}_{U})\odot
f^{i,U})-\Phi(\cdot,v)\Bigr{\|}_{\mathcal{F}}>\eta\Bigr{]}<\eta$

and

$\mathbb{E}\Bigl{[}\Bigl{\|}\frac{1}{M}\sum_{i=1}^{M}\sum_{U\in
2^{m}}a_{U}\Phi(\cdot,(v\odot\mathbf{1}_{U})\odot
f^{i,U})-\Phi(\cdot,v)\Bigr{\|}_{\mathcal{F}}^{q}\Bigr{]}^{1/q}<\eta.$

Hence by the triangle inequality, in fact

$\mathbb{P}\Bigl{[}\Bigl{\|}\frac{1}{M}\sum_{i=1}^{M}\sum_{U\in
2^{m}}a_{U}\Phi(\cdot,(v\odot\mathbf{1}_{U})\odot
f^{i,U})-\zeta\Bigr{\|}_{\mathcal{F}}>\epsilon\Bigr{]}<\epsilon$

and

$\mathbb{E}\Bigl{[}\Bigl{\|}\frac{1}{M}\sum_{i=1}^{M}\sum_{U\in
2^{m}}a_{U}\Phi(\cdot,(v\odot\mathbf{1}_{U})\odot
f^{i,U})-\zeta\Bigr{\|}_{\mathcal{F}}^{q}\Bigr{]}^{1/q}<\epsilon.$

We then define the tuple $(n,\Psi,g)\in\mathsf{DDNN}$ as an independent finite
linear combination of $2^{m}M$ copies of $(m,\Phi,f)$, with coefficients
$a_{U}/M$. Setting $\tilde{v}\in\mathbb{R}^{2^{m}m}$ to be the concatenation
of the $2^{m}$ modified vectors
$(v\odot\mathbf{1}_{U})_{U\subset\overline{1,m}}$, we then set
$w\in\mathbb{R}^{2^{m}Mm}$ to be the subsequent concatenation of $M$ copies of
$\tilde{v}$. The combination of $(n,\Psi,g)$ and $w$ achieves the assertion.

###  A.3 Proof of Proposition 8

As we have seen in Lemma 17 , we can find the map $\Psi(\cdot,w)$ in the span
of $\mathbb{E}[\Psi(\cdot,(w\odot\mathbf{1}_{V})\odot f^{V}]$ for $V\in
2^{n}$. We will look now at specific cases where we can explicitly compute the
linear combination. In particular we will look in the case that we use
_dropout_ (Hinton et al., 2012), that is, we drop nodes independently with the
same probability, and _dropconnect_ (Wan et al., 2013), where we drop
individual weights independently with the same probability.

In both cases the filter variables $f_{i}$ take the same values for some
disjoint subsets of $\overline{1,n}$, where $n$ is the number of weights where
we apply filters. That is, if we have a disjoint set decomposition
$\overline{1,n}=I_{1}\cup\ldots\cup I_{r}$ with $I_{k}\cap I_{s}=\emptyset$
whenever $k\neq s$, then $f_{i}=f_{j}$ for all $i,j\in I_{k}$ and
$f_{i},f_{l}$ are independent if they belong to disjoint sets, $f_{i}\in
I_{k}$ and $f_{l}\in I_{s}$ with $s\neq k$. In this section we drop the index
$U\in 2^{n}$ of the random variable $f^{U}$ for notational convenience as they
are identically distributed. We will use this property to obtain an explicit
decomposition in (13) and in a more general setting where the probability of
the filters may differ depending on which disjoint set they belong to. For
$K,S\in 2^{n}$, we denote $K\subseteq S$ to be the usual set inclusion, that
is, $i\notin K$ whenever $i\notin S$ for all $i\in\overline{1,n}$ holds.

We need the following lemmas:

###### Lemma 18

Let $1\geq q_{1},\ldots,q_{r}>0$ and $r\in\mathbb{N}$. For $K\in 2^{r}$,

$\mu_{K}:=\sum_{S:K\subseteq S}\prod_{i\in
S}q_{i}\prod_{i\in\overline{1,r}\setminus S}(1-q_{i})\prod_{i\in
K}\Bigl{(}\frac{1}{q_{i}}\Bigr{)}\prod_{i\in S\backslash
K}\Bigl{(}1-\frac{1}{q_{i}}\Bigr{)}$ (46)

satisfies

$\mu_{K}=\begin{cases}1&\text{ if }K=\overline{1,r}\\\ 0&\text{ otherwise.}\\\
\end{cases}$ (47)

Proof  Let $x_{1},\ldots,x_{r}$ be free variables. For $S\in 2^{r}$ we denote
the monomial $x^{S}=\prod_{i\in S}x_{i}$. We will prove the identity by
comparing coefficients of two equal polynomials. We have

$q(x_{1},\ldots,x_{r})=\prod_{i=1}^{r}(q_{i}x_{i}+(1-q_{i}))=\sum_{S\in
2^{r}}x^{S}\prod_{i\in S}q_{i}\prod_{i\in\overline{1,r}\setminus S}(1-q_{i})$
(48)

where we have expanded all $|2^{r}|$ monomials appearing in the decomposition
of $q$. Now we set $x_{i}=(1/q_{i})y_{i}-(1-q_{i})/q_{i}$ in (48). We have

$\displaystyle
q\Bigl{(}\frac{1}{q_{1}}y_{1}-\frac{1-q_{1}}{q_{1}},\ldots,\frac{1}{q_{r}}y_{r}-\frac{1-q_{r}}{q_{r}}\Bigr{)}$
$\displaystyle=\prod_{i=1}^{r}\Bigl{(}q_{i}\Bigl{(}\frac{1}{q_{i}}y_{i}-\frac{1-q_{i}}{q_{i}}\Bigr{)}+(1-q_{i})\Bigr{)}$
$\displaystyle=\prod_{i=1}^{r}y_{i}=y^{\overline{1,r}}.$ (49)

On the other hand, if we substitute $x_{i}=(1/q_{i})y_{i}-(1-q_{i})/q_{i}$ in
the monomials $x^{S}$ in (48) we have

$\displaystyle\sum_{S\in 2^{r}}x^{S}\prod_{i\in
S}q_{i}\prod_{i\in\overline{1,r}\setminus S}(1-q_{i})$
$\displaystyle=\sum_{S\in 2^{r}}\prod_{i\in
S}\Bigl{(}\frac{1}{q_{i}}y_{i}-\frac{1-q_{i}}{q_{i}}\Bigr{)}q_{i}\prod_{i\in\overline{1,r}\setminus
S}(1-q_{i})$ $\displaystyle=\sum_{S\in 2^{r}}\sum_{K\in 2^{r}:K\subseteq
S}\prod_{i\in S}q_{i}\prod_{i\in\overline{1,r}\setminus S}(1-q_{i})\prod_{i\in
K}y_{i}\Bigl{(}\frac{1}{q_{i}}\Bigr{)}\prod_{i\in S\setminus
K}\Bigl{(}-\frac{1-q_{i}}{q_{i}}\Bigr{)}$ $\displaystyle=\sum_{K\in
2^{r}}y^{K}\sum_{S:K\subseteq S}\prod_{i\in
S}q_{i}\prod_{i\in\overline{1,r}\setminus S}(1-q_{i})\prod_{i\in
K}\Bigl{(}\frac{1}{q_{i}}\Bigr{)}\prod_{i\in S\backslash
K}\Bigl{(}1-\frac{1}{q_{i}}\Bigr{)}$ $\displaystyle=\sum_{K\in
2^{r}}\mu_{K}y^{K}$ (50)

so that we must have $\mu_{K}=1$ if $K=\overline{1,r}$ and zero otherwise.

Let $\overline{1,n}=I_{1}\cup\ldots,\cup I_{r}$ be a disjoint partition of
$\overline{1,n}$, i.e., $I_{j}\cap I_{i}=\emptyset$ if $i\neq j$. We consider
$S\in 2^{r}$ also as an element of $2^{n}$ via the inclusion $\iota:2^{r}\to
2^{n}$ given by $j\in\iota(S)$ if $j\in I_{i}$ and $i\in S$, i.e., we consider
the index $i$ as the set of all indices $j\in I_{i}$. Note then that
$\iota(\overline{1,r})=\overline{1,n}$. Recall now that the filter random
variable with values in $\\{0,1\\}^{n}$ are denoted by
$f=(f_{1},\cdots,f_{n})$ . We suppose now that the filter random variables
satisfy that $f_{i}=f_{j}$ whenever $i,j\in I_{s}$ for some
$s\in\overline{1,r}$. We denote by $B_{s}$ the $\\{0,1\\}$ valued random
variable corresponding to the $I_{s}$ part of $\overline{1,n}$. We suppose
that $\mathbb{P}(B_{s}=1)=q_{s}=1-p_{s}$ for all $s\in\overline{1,r}$, where
$q_{s}$ is the probability of success and $p_{s}$ the dropping probability.
Moreover, we suppose that the $(B_{s})_{s\in\overline{1,r}}$ are mutually
independent. With this notation we have:

${\mathbb{E}}{}\big{[}\Psi(\cdot,w\odot f)\big{]}=\sum_{L\in 2^{r}}\prod_{i\in
L}q_{i}\prod_{i\in\overline{1,r}\setminus
L}(1-q_{i})\Psi(\cdot,w\odot\mathbf{1}_{\iota(L)}).$ (51)

In the following Lemma, we embed $2^{r}$ into $2^{n}$ as blocks according to a
partition of $\overline{1,n}$ using $\iota$:

###### Lemma 19

For $S\in 2^{r}$,

$\displaystyle{\mathbb{E}}{}\big{[}\Psi(\cdot,(w\odot\mathbf{1}_{\iota(S)})\odot
f)\big{]}$ $\displaystyle=\sum_{K\in 2^{r}:K\subseteq S}\prod_{i\in
K}q_{i}\prod_{i\in S\setminus
K}(1-q_{i})\Psi\left(\cdot,w\odot\mathbf{1}_{\iota(K)}\right).$ (52)

Proof  Let $S\in 2^{r}$. Observe that
$f=\sum_{s=1}^{r}\mathds{1}[B_{s}=1]\mathbf{1}_{I_{s}}$ and note in particular
that

$g:=\mathbf{1}_{\iota(S)}\odot f=\bigl{(}\sum_{s\in S}+\sum_{s\in
S^{c}}\bigr{)}\mathds{1}[B_{s}=1]\mathbf{1}_{\iota(S)\cap I_{s}}=\sum_{s\in
S}\mathds{1}[B_{s}=1]\mathbf{1}_{I_{s}}.$ (53)

Hence, $g$ depends only on $(B_{s})_{s\in S}$ and is thus moreover independent
of $(B_{t})_{t\in S^{c}}$ by assumption. Consequently $\Psi(\cdot,w\odot g)$
also depends only on $(B_{s})_{s\in S}$ and is also independent of
$(B_{t})_{t\in S^{c}}$. The result then follows.

To see this in detail, suppose that $S=\\{s_{1},\ldots,s_{m}\\}$ and
$S^{c}=\\{t_{1},\ldots,t_{r-m}\\}$ say. Use the law of the unconscious
statistician together with (i) independence to conclude that

$\displaystyle\mathbb{E}[\Psi(\cdot,w\odot g)]$
$\displaystyle\overset{\textnormal{(\ref{eqn:Random_variable_g})}}{=}\sum_{b_{1}=0}^{1}\cdots\sum_{b_{r}=0}^{1}\Psi(\cdot,w\odot\sum_{s\in
S}\mathds{1}[b_{s}=1]\mathbf{1}_{I_{s}})\mathbb{P}[B_{1}=b_{1},\ldots,B_{r}=b_{r}]$
$\displaystyle\overset{\textnormal{(i)}}{=}\sum_{b_{s_{1}}=0}^{1}\cdots\sum_{b_{s_{m}}=0}^{1}\Psi(\cdot,w\odot\sum_{i=1}^{m}\mathds{1}[b_{s_{i}}=1]\mathbf{1}_{I_{s_{i}}})\mathbb{P}[\cap_{i=1}^{m}\\{B_{s_{i}}=b_{s_{i}}\\}]$
$\displaystyle\phantom{=}\times\underbrace{\sum_{b_{t_{1}}=0}^{1}\cdots\sum_{b_{t_{r-m}}=0}^{1}\mathbb{P}[\cap_{j=1}^{r-m}\\{B_{t_{j}}=b_{t_{j}}\\}]}_{=1\textnormal{
as an axiom of the pdf}}.$ (54)

Substitute

$\mathbb{P}[\cap_{i=1}^{m}\\{B_{s_{i}}=b_{s_{i}}\\}]\overset{\textnormal{(i)}}{=}\prod_{i=1}^{m}\mathbb{P}[B_{s_{i}}=b_{s_{i}}]=\prod_{i=1}^{m}q_{s_{i}}^{b_{s_{i}}}(1-q_{s_{i}})^{1-b_{s_{i}}}$
(55)

and then apply the change of variables
$K(b_{s_{1}},\ldots,b_{s_{m}})=\cup_{i=1}^{m}\\{s_{i}:b_{s_{i}}=1\\}$ to
identify the right-hand side of (52).

We can now prove Proposition 8:

Proof (of Proposition 8) In the same notation as in Lemma 18 and Lemma 19, we
use that $q_{s}=1-p_{s}$ is the success probability. Then, we can write

$\displaystyle\sum_{V\in 2^{r}}\prod_{i\in
V}\Bigl{(}\frac{1}{q_{i}}\Bigr{)}\prod_{i\in\overline{1,r}\setminus
V}\Bigl{(}1-\frac{1}{q_{i}}\Bigr{)}{\mathbb{E}}{}(\Psi(\cdot,(w\odot\mathbf{1}_{\iota(V)})\odot
f)$ $\displaystyle\overset{\textnormal{({{Lemma\leavevmode\nobreak\
\ref{lemma:example_expectation_subset}}})}}{=}\sum_{V\in 2^{r}}\prod_{i\in
V}\Bigl{(}\frac{1}{q_{i}}\Bigr{)}\prod_{i\in\overline{1,r}\setminus
V}\Bigl{(}1-\frac{1}{q_{i}}\Bigr{)}\sum_{K:K\subseteq V\in 2^{r}}\prod_{i\in
K}q_{i}\prod_{i\in V\setminus
K}(1-q_{i})\Psi(\cdot,w\odot\mathbf{1}_{\iota(K)})$ $\displaystyle=\sum_{V\in
2^{r}}\sum_{K:K\subseteq V\in 2^{r}}\prod_{i\in
V}\Bigl{(}\frac{1}{q_{i}}\Bigr{)}\prod_{i\in\overline{1,r}\setminus
V}\Bigl{(}1-\frac{1}{q_{i}}\Bigr{)}\prod_{i\in K}q_{i}\prod_{i\in V\setminus
K}(1-q_{i})\Psi(\cdot,w\odot\mathbf{1}_{\iota(K)})$ $\displaystyle=\sum_{K\in
2^{r}}\Psi(\cdot,w\odot\mathbf{1}_{\iota(K)})\sum_{V:K\subseteq V\in
2^{r}}\Bigl{(}\frac{1}{q_{i}}\Bigr{)}\prod_{i\in\overline{1,r}\setminus
V}\Bigl{(}1-\frac{1}{q_{i}}\Bigr{)}\prod_{i\in K}q_{i}\prod_{i\in V\setminus
K}(1-q_{i})$ $\displaystyle=\sum_{K\in
2^{r}}\Psi(\cdot,w\odot\mathbf{1}_{\iota(K)})\mu_{K}$
$\displaystyle\overset{\textnormal{({{Lemma\leavevmode\nobreak\
\ref{lemma:example_mu_identity}}})}}{=}\Psi(\cdot,w\odot\mathbf{1}_{\iota(\overline{1,r})})$
$\displaystyle=\Psi(\cdot,w).$ (56)

Note finally that we obtain Proposition 8 after substituting $q_{s}=1-p_{s}$.

##  B Proofs of Section 4

###  B.1 Proof of Lemma 12

Let $\Gamma$ be a dropout tree. Let $\ell$ be a leaf of $\Gamma$ at level
$k>1$. Let $\mu$ be the distribution of a random matrix
$F\in\\{0,1\\}^{d_{k}\times d_{k-1}}$ that satisfies for all $r,c$,
$\mathbb{P}[F_{rc}=1]\geq\beta>0$. Assume that $\Gamma$ satisfies
$\mathsf{ApProp}_{\Gamma}(\delta,\epsilon)$, i.e.,

$\mathbb{P}\Bigl{[}\sup_{x\in\overline{B(0,R)}}\sup_{\tilde{x}\in\overline{B(\mathsf{In}_{\Gamma}(x),\delta)}}\bigl{|}\Phi^{v_{0}}_{\Gamma}((\tilde{x}^{\ell})_{\ell})-\Phi^{v_{0}}_{\Gamma_{\det}}(\mathsf{In}_{\Gamma}(x))\bigr{|}>\frac{\epsilon}{2}\Bigr{]}<\Bigl{(}\frac{\epsilon}{4R_{L}}\Bigr{)}^{q}.$

Define $\kappa>0$ by

$\kappa:=\Bigl{(}\frac{\epsilon}{4R_{L}}\Bigr{)}^{q}-\mathbb{P}\Bigl{[}\sup_{x\in\overline{B(0,R)}}\sup_{\tilde{x}\in\overline{B(\mathsf{In}_{\Gamma}(x),\delta)}}\bigl{|}\Phi^{v_{0}}_{\Gamma}(x)-\Phi^{v_{0}}_{\Gamma_{\det}}(\tilde{x})\bigr{|}>\frac{\epsilon}{2}\Bigr{]}.$

By Lemma 13, there exists an $\eta>0$ and an $N_{0}\in\mathbb{N}$ such that
for all $N\geq N_{0}$, if $F^{i}$ are independent, identically distributed
filter matrices distributed according to $\mu$, and if $V$ is given by (25),
then

$\mathbb{P}\Bigl{[}\sup_{z\in\overline{B(0,R_{k})}}\sup_{(\tilde{z})^{i}\in
B(x,\eta)^{N}}\Bigl{|}\sigma_{k}\bigl{(}\frac{1}{N}\sum_{i=1}^{N}(V\odot
F^{i})\tilde{z}^{i}+b^{(k)}\bigr{)}-\sigma_{k}\bigl{(}W^{(k)}z+b^{(k)}\bigr{)}\Bigr{|}>\delta\Bigr{]}<\kappa.$

Now let $\Gamma^{\prime}$ be a $\mu$-input-copy of $\Gamma$ at $\ell$ of size
$N\geq N_{0}$. Choose $\delta^{\prime}:=\min(\delta,\eta)$.

Consider the event $\mathcal{A}$ that

$\sup_{x\in\overline{B(0,R)}}\sup_{\tilde{x}\in\overline{B(\mathsf{In}_{\Gamma}(x),\delta)}}\bigl{|}\Phi^{v_{0}}_{\Gamma}((\tilde{x}^{\ell})_{\ell})-\Phi^{v_{0}}_{\Gamma_{\det}}(\mathsf{In}_{\Gamma}(x))\bigr{|}>\frac{\epsilon}{2},$

which (informally) means that the tree $\Gamma$ provides a bad approximation.
Consider also the event $\mathcal{B}$ that

$\sup_{z\in\overline{B(0,R_{k-1})}}\sup_{(\tilde{z}^{m})\in
B(z,\eta)^{N}}\Bigl{|}\sigma_{k}\bigl{(}\sum_{e\in\mathsf{into}(\ell)}(V^{e}\odot
F^{e})\tilde{z}^{m}+b^{e}\bigr{)}-\sigma_{k}(W^{e}z+b^{e})\Bigr{|}>\delta.$

Here, $\mathsf{into}(\ell)$ refers to the dropout-tree $\Gamma^{\prime}$. This
event (informally) means that the added part provides a bad approximation.
Note that

$\mathbb{P}[\mathcal{A}\cup\mathcal{B}]\leq\mathbb{P}[\mathcal{A}]+\mathbb{P}[\mathcal{B}]<\mathbb{P}[\mathcal{A}]+\kappa=\Bigl{(}\frac{\epsilon}{4R_{L}}\Bigr{)}^{q}.$

Next, let us show that on $(\mathcal{A}\cup\mathcal{B})^{c}$ one has

$\sup_{x\in\overline{B(0,R)}}\sup_{\tilde{x}\in\overline{B(\mathsf{In}_{\Gamma^{\prime}}(x),\delta^{\prime})}}\bigl{|}\Phi^{v_{0}}_{\Gamma^{\prime}}((\tilde{x}^{\ell})_{\ell})-\Phi^{v_{0}}_{\Gamma_{\det}}(\mathsf{In}_{\Gamma^{\prime}}(x))\bigr{|}\leq\frac{\epsilon}{2}.$
(57)

To do this, suppose that $(\mathcal{A}\cup\mathcal{B})^{c}$ holds and
$x\in\overline{B(0,R)}$. For every leaf $m\in\mathsf{children}(\ell)$ in
$\Gamma^{\prime}$ define $z:=\mathsf{In}_{\Gamma^{{}^{\prime}}}^{m}(x)$
(recall the definition from (27)) and note that $z\in\overline{B(0,R_{k-1})}$.
Let $\tilde{x}\in B(\mathsf{In}_{\Gamma^{\prime}}(x),\delta^{\prime})$. For
every leaf $m\in\mathsf{children}(\ell)$ define
$\tilde{z}^{m}:=\tilde{x}^{m}\in B(z,\eta)$ by the choice of
$\delta^{\prime}$. Since $\mathcal{B}^{c}$ holds,

$\Bigl{|}\sigma_{k}\Bigl{(}\sum_{e\in\mathsf{into}(\ell)}(V^{e}\odot
F^{e})\tilde{z}^{i}+b^{e}\Bigr{)}-\sigma_{k}(W^{e}z+b^{e})\Bigr{|}\leq\delta,$

or, in other words,

$\sigma_{k}\bigl{(}\sum_{e\in\mathsf{into}(\ell)}(V^{e}\odot
F^{e})\tilde{z}^{i}+b^{e}\bigr{)}\in\overline{B(\mathsf{In}_{\Gamma}^{\ell}(x),\delta)}.$

Together with $\mathcal{A}^{c}$ this implies (57).

Finally, by the law of total probability, we estimate

$\displaystyle\mathbb{P}\Bigl{[}\sup_{x\in\overline{B(0,R)}}\sup_{\tilde{x}\in\overline{B(\mathsf{In}_{\Gamma^{\prime}}(x),\delta^{\prime})}}\bigl{|}\Phi^{v_{0}}_{\Gamma^{\prime}}((\tilde{x}^{\ell})_{\ell})-\Phi^{v_{0}}_{\Gamma_{\det}}(\mathsf{In}_{\Gamma^{\prime}}(x))\bigr{|}>\frac{\epsilon}{2}\Bigr{]}$
$\displaystyle=\mathbb{P}\Bigl{[}\sup_{x\in\overline{B(0,R)}}\sup_{\tilde{x}\in\overline{B(\mathsf{In}_{\Gamma^{\prime}}(x),\delta^{\prime})}}\bigl{|}\Phi^{v_{0}}_{\Gamma^{\prime}}((\tilde{x}^{\ell})_{\ell})-\Phi^{v_{0}}_{\Gamma_{\det}}(\mathsf{In}_{\Gamma^{\prime}}(x))\bigr{|}>\frac{\epsilon}{2}\Big{|}\mathcal{A}\cup\mathcal{B}\Bigr{]}\mathbb{P}[\mathcal{A}\cup\mathcal{B}]$
$\displaystyle\phantom{=}+\mathbb{P}\Bigl{[}\sup_{x\in\overline{B(0,R)}}\sup_{\tilde{x}\in\overline{B(\mathsf{In}_{\Gamma^{\prime}}(x),\delta^{\prime})}}\bigl{|}\Phi^{v_{0}}_{\Gamma^{\prime}}((\tilde{x}^{\ell})_{\ell})-\Phi^{v_{0}}_{\Gamma_{\det}}(\mathsf{In}_{\Gamma^{\prime}}(x))\bigr{|}>\frac{\epsilon}{2}\Big{|}(\mathcal{A}\cup\mathcal{B})^{c}\Bigr{]}\mathbb{P}[(\mathcal{A}\cup\mathcal{B})^{c}]$
$\displaystyle<\Bigl{(}\frac{\epsilon}{4R_{L}}\Bigr{)}^{q}+0=\Bigl{(}\frac{\epsilon}{4R_{L}}\Bigr{)}^{q}.$
(58)

This completes the proof of Lemma 12.

$\Box$

###  B.2 Proof of Lemma 13

Let $0\leq K<\infty$ and $\rho>0$ be fixed. For every $N<\infty$, the suprema
in (30) over $x,(\tilde{x}^{i})$ are in fact attained—say at
$X_{*},(\tilde{X}_{*}^{i})$—because $\sigma$ is continuous and the
optimization domain is closed and bounded. We need to now be careful because
$X_{*},(\tilde{X}_{*}^{i})$ depend on the collection
$\\{F^{i}\\}_{i\in\overline{1,N}}$.

Recall that the continuity of $\sigma$ implies that $\sigma$ is also uniformly
continuous on each compact set, i.e., for every $\zeta>0$ there exists an
$\eta_{\zeta}>0$ such that for all $x,y$ from this compact set

$|x-y|<\eta_{\zeta}\Rightarrow|\sigma(y)-\sigma(x)|<\zeta.$ (59)

Define $\bar{X}_{*}:=(1/N)\sum_{i=1}^{N}\tilde{X}_{*}^{i}$. Then uniform
continuity of $\sigma$ implies that

$\bigl{|}\sigma\bigl{(}W\bar{X}_{*}+b\bigr{)}-\sigma(Wx+b)\bigr{|}\leq\sup_{x\in\overline{B(0,K)}}\sup_{y\in\overline{B(x,\delta)}}\bigl{|}\sigma\bigl{(}Wy+b\bigr{)}-\sigma(Wx+b)\bigr{|}=:\gamma_{\delta}<\infty.$
(60)

Moreover, $\gamma_{\delta}$ is independent of $N$. Remark also that

$\sup_{f\in\\{0,1\\}^{m\times
n}}\sup_{y\in\overline{B(0,\delta)}}\frac{1}{\mathbb{E}[F]}\bigl{|}\bigl{(}W\odot
f-W\odot\mathbb{E}[F]\bigr{)}y\bigr{|}=:c_{\delta}<\infty$ (61)

where $f$ stands for all possible deterministic realizations of the filters
$F$. Again, $c_{\delta}$ is independent of $N$. Finally, by construction there
exists a compact set $\mathcal{C}\subset\mathbb{R}^{m}$ such that the points

$\frac{1}{N}\sum_{i=1}^{N}(V\odot F^{i})\tilde{X}_{*}^{i}+b,\quad
W\bar{X}_{*}+b$ (62)

lie in $\mathcal{C}$ with probability one.

First, fix $\zeta=\rho/2$. From uniform continuity of $\sigma$ on the compact
set $\mathcal{C}$ there exists $\eta_{\zeta}>0$ such that (59) holds for all
$x,y\in\mathcal{C}$. Second, observe that $\gamma_{\delta}\to 0$ and
$c_{\delta}\to 0$ as $\delta\to 0$. Hence we can choose $\delta$ and fix it
such that

$0<\zeta<\rho-\gamma_{\delta}\quad\textnormal{and}\quad
c_{\delta}<\eta_{\zeta}.$ (63)

Combining (60) with the triangle inequality and using (63), we arrive at

$\displaystyle\textnormal{LHS
}\eqref{eqn:Probability_bound_for_the_last_layer}\leq\mathbb{P}\Bigl{[}\underbrace{\Bigl{|}\sigma\bigl{(}\frac{1}{N}\sum_{i=1}^{N}(V\odot
F^{i})\tilde{X}_{*}^{i}+b\bigr{)}-\sigma\bigl{(}W\bar{X}_{*}+b\bigr{)}\Bigr{|}}_{=:Z}>\rho-\gamma_{\delta}.\Bigr{]},$
(64)

Consider now the event

$\mathcal{E}=\Bigl{\\{}\Bigl{|}\frac{1}{N}\sum_{i=1}^{N}(V\odot
F^{i})\tilde{X}_{*}^{i}-W\bar{X}_{*}\Bigr{|}<\eta_{\zeta}\Bigr{\\}}.$ (65)

Then by the law of total probability and uniform continuity,

$\displaystyle\mathbb{P}[Z>\rho-\gamma_{\delta}]$
$\displaystyle=\mathbb{P}[Z>\rho-\gamma_{\delta}|\mathcal{E}]\mathbb{P}[\mathcal{E}]+\mathbb{P}[Z>\rho-\gamma_{\delta}|\mathcal{E}^{\mathrm{c}}]\mathbb{P}[\mathcal{E}^{\mathrm{c}}]$
$\displaystyle\leq\mathds{1}[\zeta>\rho-\gamma_{\delta}]\mathbb{P}[\mathcal{E}]+\mathbb{P}[\mathcal{E}^{\mathrm{c}}]\overset{\textnormal{(\ref{eqn:Choice_of_delta_for_Lemma_18})}}{=}\mathbb{P}[\mathcal{E}^{\mathrm{c}}].$
(66)

We proceed by bounding $\mathbb{P}[\mathcal{E}^{\mathrm{c}}]$. Use the
triangle inequality twice to establish that for any $x\in\overline{B(0,K)}$,

$\displaystyle\Bigl{|}\frac{1}{N}\sum_{i=1}^{N}(V\odot
F^{i})\tilde{X}_{*}^{i}-W\bar{X}_{*}\Bigr{|}$
$\displaystyle=\Bigl{|}\frac{1}{N\mathbb{E}[F]}\sum_{i=1}^{N}\bigl{(}(W\odot
F^{i})-W\odot\mathbb{E}[F]\bigr{)}\bigl{(}x+(\tilde{X}_{*}^{i}-x)\bigr{)}\Bigr{|}$
$\displaystyle\leq\Bigl{|}\frac{1}{N\mathbb{E}[F]}\sum_{i=1}^{N}\bigl{(}(W\odot
F^{i})-W\odot\mathbb{E}[F]\bigr{)}x\Bigr{|}+\Bigl{|}\frac{1}{N\mathbb{E}[F]}\sum_{i=1}^{N}\bigl{(}(W\odot
F^{i})-W\odot\mathbb{E}[F]\bigr{)}(\tilde{X}_{*}^{i}-x)\Bigr{|}$
$\displaystyle\overset{\textnormal{(\ref{eqn:Definition_of_c_delta})}}{\leq}\Bigl{|}\frac{1}{N\mathbb{E}[F]}\sum_{i=1}^{N}\bigl{(}(W\odot
F^{i})-W\odot\mathbb{E}[F]\bigr{)}x\Bigr{|}+c_{\delta}.$ (67)

Note now additionally that by Khinchin’s weak law of large numbers,

$\frac{1}{N}\sum_{i=1}^{N}W\odot
F^{i}\overset{\mathbb{P}}{\to}W\odot\mathbb{E}[F]\quad\textnormal{as}\quad
N\to\infty.$ (68)

Therefore, using (63), we get as $N\to\infty$

$\mathbb{P}[\mathcal{E}^{\mathrm{c}}]\overset{\textnormal{(\ref{eqn:Bound_on_the_filtered_optimizer})}}{\leq}\mathbb{P}\Bigl{[}\Bigl{|}\frac{1}{N\mathbb{E}[F]}\sum_{i=1}^{N}\bigl{(}(W\odot
F^{i})-W\odot\mathbb{E}[F]\bigr{)}x\Bigr{|}\geq\eta_{\zeta}-c_{\delta}\Bigr{]}\overset{\textnormal{(\ref{eqn:Khincins_WLLN_applied_to_sum_W_odot_Fi})}}{\to}0.$
(69)

Bounding (66) by (69) completes the proof. $\Box$

###  B.3 Proof of Theorem 15

We start by showing that for $\alpha$ small enough and for $N$ large enough,

$\mathbb{P}\Bigl{[}\sup_{x\in\overline{B(0,R)}}\bigl{|}\mathsf{NN}_{\Gamma,\Xi}(x)-\Psi(x,w)\bigr{|}>\frac{\epsilon}{2}\Bigr{]}<\Bigl{(}\frac{\epsilon}{4R_{L}}\Bigr{)}^{q}.$
(70)

Afterwards, we deduce the three assertions (38)–(40) from (70).

_Proof of ( 70)._ Recall that the assumption
$\mathsf{ApProp}_{\Gamma}(\delta,\epsilon)$ means that

$\mathbb{P}\Bigl{[}\sup_{x\in\overline{B(0,R)}}\sup_{\tilde{x}\in\overline{B(\mathsf{In}_{\Gamma}(x),\delta)}}\bigl{|}\Phi^{v_{0}}_{\Gamma,\Xi}(\tilde{x})-\Phi^{v_{0}}_{\Gamma_{\det},\Xi}(\mathsf{In}_{\Gamma}(x))\bigr{|}>\frac{\epsilon}{2}\Bigr{]}<\Bigl{(}\frac{\epsilon}{4R_{L}}\Bigr{)}^{q}.$

Define therefore $\kappa>0$ by

$\kappa:=\frac{1}{\\#\mathsf{leaves}(\Gamma)}\Bigl{(}\Bigl{(}\frac{\epsilon}{4R_{L}}\Bigr{)}^{q}-\mathbb{P}\Bigl{[}\sup_{x\in\overline{B(0,R)}}\sup_{\tilde{x}\in\overline{B(\mathsf{In}_{\Gamma}(x),\delta)}}\bigl{|}\Phi^{v_{0}}_{\Gamma,\Xi}(\tilde{x})-\Phi^{v_{0}}_{\Gamma_{\det},\Xi}(\mathsf{In}_{\Gamma}(x))\bigr{|}>\frac{\epsilon}{2}\Bigr{]}\Bigr{)}.$
(71)

Observe now that the function $\Psi_{1}$ is continuous, and the function
$\Phi_{\Gamma_{\det}}^{v_{0}}$ is continuous on
$(\mathbb{R}^{d_{1}})^{\mathsf{leaves}(\Gamma)}$. Since this implies uniform
continuity on compact sets (see (59)), there exists a $\zeta>0$ such that
whenever a function $g:\overline{B(0,R)}\to\mathsf{Inp}_{\Gamma}$ satisfies

$\sup_{x\in\overline{B(0,R)}}\;\sup_{\ell\in\mathsf{leaves}(\Gamma)}\;\bigl{|}g^{\ell}(x)-\Psi_{1}(x;(W^{(1)},b^{(1)}))\bigr{|}<\zeta,$

then we also have

$\sup_{x\in\overline{B(0,R)}}\Bigl{|}\Phi^{v_{0}}_{\Gamma_{\det}}(g(x))-\Psi(x,w)\Bigr{|}<\epsilon.$
(72)

Now choose

$\rho:=\min\left(\delta/2,\kappa,\zeta\right)\qquad\text{and}\qquad K:=R,$

which we use as parameters for Lemma 16. This choice ensures that for $\alpha$
small enough and $N$ large enough, for all leaves $\ell$ of $\Gamma$, by
inequality (41)

$\mathbb{P}\Bigr{[}\sup_{x\in\overline{B(0,R)}}\bigl{|}\Xi^{\ell}(x)-\Psi_{1}(x;(W^{(1)},b^{(1)}))\bigr{|}>\delta/2\Bigr{]}<\kappa$
(73)

and by inequality (42)

$\sup_{x\in\overline{B(0,R)}}\bigl{|}\Xi^{\ell,\mathsf{avg-
filt}}(x)-\Psi_{1}(x;(W^{(1)},b^{(1)}))\bigr{|}<\zeta.$ (74)

Consider now the event $\mathcal{A}$ that there exists a leaf $\ell$ of
$\Gamma$ such that

$\sup_{x\in\overline{B(0,R)}}|\Xi^{\ell}(x)-\Psi_{1}(x;(W^{(1)},b^{(1)}))|>\delta/2.$

From the law of total probability, it follows that

$\displaystyle\mathbb{P}\Bigl{[}\sup_{x\in\overline{B(0,R)}}\bigl{|}\mathsf{NN}_{\Gamma,\Xi}(x)-\Psi(x,w)\bigr{|}>\frac{\epsilon}{2}\Bigr{]}$
$\displaystyle=\mathbb{P}\Bigl{[}\sup_{x\in\overline{B(0,R)}}\bigl{|}\mathsf{NN}_{\Gamma,\Xi}(x)-\Psi(x,w)\bigr{|}>\frac{\epsilon}{2}\Big{|}\mathcal{A}\Bigr{]}\mathbb{P}[\mathcal{A}]$
$\displaystyle\phantom{=}+\mathbb{P}\Bigl{[}\sup_{x\in\overline{B(0,R)}}\bigl{|}\mathsf{NN}_{\Gamma,\Xi}(x)-\Psi(x,w)\bigr{|}>\frac{\epsilon}{2}\Big{|}\mathcal{A}^{c}\Bigr{]}\mathbb{P}[\mathcal{A}^{c}].$
(75)

Observe that

$\mathbb{P}\Bigl{[}\sup_{x\in\overline{B(0,R)}}\bigl{|}\mathsf{NN}_{\Gamma,\Xi}(x)-\Psi(x,w)\bigr{|}>\frac{\epsilon}{2}\Big{|}\mathcal{A}\Bigr{]}\leq
1,$ (76)

and by (i) Boole’s inequality

$\displaystyle\mathbb{P}[\mathcal{A}]$
$\displaystyle=\mathbb{P}\Bigl{[}\cup_{\ell\in\mathsf{leaves}(\Gamma)}\bigl{\\{}\sup_{x\in\overline{B(0,R)}}|\Xi^{\ell}(x)-\Psi_{1}(x;(W^{(1)},b^{(1)}))|>\delta/2\bigr{\\}}\Bigr{]}$
$\displaystyle\overset{\textnormal{(i)}}{\leq}\sum_{\ell\in\mathsf{leaves}(\Gamma)}\mathbb{P}\Bigl{[}\sup_{x\in\overline{B(0,R)}}|\Xi^{\ell}(x)-\Psi_{1}(x;(W^{(1)},b^{(1)}))|>\delta/2\Bigr{]}\overset{\textnormal{(\ref{eqn:Theorem_15_proof_kappa_bound})}}{\leq}\kappa\cdot\\#\mathsf{leaves}(\Gamma).$
(77)

Furthermore,

$\displaystyle\mathbb{P}\Bigl{[}\sup_{x\in\overline{B(0,R)}}\bigl{|}\mathsf{NN}_{\Gamma,\Xi}(x)-\Psi(x,w)\bigr{|}>\frac{\epsilon}{2}\Big{|}\mathcal{A}^{c}\Bigr{]}$
$\displaystyle\overset{\textnormal{(\ref{eq:bound_for_g_to_input})}}{\leq}\mathbb{P}\Bigl{[}\sup_{x\in\overline{B(0,R)}}\sup_{\tilde{x}\in\overline{B(\mathsf{In}_{\Gamma}(x),\delta)}}\bigl{|}\Phi^{v_{0}}_{\Gamma,\Xi}(\tilde{x})-\Phi^{v_{0}}_{\Gamma_{\det},\Xi}(\mathsf{In}_{\Gamma}(x))\bigr{|}>\frac{\epsilon}{2}\Bigr{]}.$
(78)

By bounding (75) using (76)–(78) and $\mathbb{P}[\mathcal{A}^{c}]\leq 1$, we
find that

$\displaystyle\mathbb{P}\Bigl{[}\sup_{x\in\overline{B(0,R)}}\bigl{|}\mathsf{NN}_{\Gamma,\Xi}(x)-\Psi(x,w)\bigr{|}>\frac{\epsilon}{2}\Bigr{]}$
$\displaystyle<\kappa\cdot\\#\mathsf{leaves}(\Gamma)+\mathbb{P}\Bigl{[}\sup_{x\in\overline{B(0,R)}}\sup_{\tilde{x}\in\overline{B(\mathsf{In}_{\Gamma}(x),\delta)}}\bigl{|}\Phi^{v_{0}}_{\Gamma,\Xi}(\tilde{x})-\Phi^{v_{0}}_{\Gamma_{\det},\Xi}(\mathsf{In}_{\Gamma}(x))\bigr{|}>\frac{\epsilon}{2}\Bigr{]}\cdot
1$
$\displaystyle\overset{\textnormal{(\ref{eqn:Definition_of_kappa})}}{=}\Bigl{(}\frac{\epsilon}{4R_{L}}\Bigr{)}^{q}$
(79)

This shows (70).

Next, we prove that (38)–(40) follow from (70).

_Proof of ( 38)._ This inequality follows from (70) since $R_{L}\geq 1$ by
construction and $q\geq 1$ by assumption.

_Proof of ( 40)._ This inequality is a direct consequence of inequality (72)
by choosing $g^{\ell}:=\Xi^{\ell,\mathsf{avg-filt}}$ and using (74).

_Proof of ( 39)._ We will prove that by the definition of $R_{j}$ in (26), for
all $x\in\overline{B(0,R)}$

$\bigl{|}\mathsf{NN}_{\Gamma,\Xi}(x)\bigr{|}^{q}<R_{L}^{q}\quad\textnormal{w.p.\
one,}\quad\textnormal{and}\quad\bigl{|}\Psi(x,w)\bigr{|}^{q}<R_{L}^{q}.$ (80)

Namely, if (80) holds true, then (39) follows.

To see the implication, consider the event $\mathcal{D}$ for which

$\sup_{x\in\overline{B(0,R)}}\bigl{|}\mathsf{NN}_{\Gamma,\Xi}(x)-\Psi(x,w)\bigr{|}>\frac{\epsilon}{2},$
(81)

and apply the law of total expectation:

$\displaystyle\mathbb{E}\Bigl{[}\sup_{x\in\overline{B(0,R)}}\bigl{|}\mathsf{NN}_{\Gamma,\Xi}(x)-\Psi(x,w)\bigr{|}^{q}\Bigr{]}$
(82)
$\displaystyle=\mathbb{E}\Bigl{[}\sup_{x\in\overline{B(0,R)}}\bigl{|}\mathsf{NN}_{\Gamma,\Xi}(x)-\Psi(x,w)\bigr{|}^{q}\Big{|}\mathcal{D}\Bigr{]}\mathbb{P}[\mathcal{D}]+\mathbb{E}\Bigl{[}\sup_{x\in\overline{B(0,R)}}\bigl{|}\mathsf{NN}_{\Gamma,\Xi}(x)-\Psi(x,w)\bigr{|}^{q}\Big{|}\mathcal{D}^{c}\Bigr{]}\mathbb{P}[\mathcal{D}^{c}].$

By the triangle inequality,

$\mathbb{E}\Bigl{[}\sup_{x\in\overline{B(0,R)}}\bigl{|}\mathsf{NN}_{\Gamma,\Xi}(x)-\Psi(x,w)\bigr{|}^{q}\Big{|}\mathcal{D}\Bigr{]}\overset{\textnormal{(\ref{eqn:Inductive_claim_for_the_proof_of_Theorem_15})}}{\leq}(2R_{L})^{q}.$
(83)

On the other hand,

$\mathbb{E}\Bigl{[}\sup_{x\in\overline{B(0,R)}}\bigl{|}\mathsf{NN}_{\Gamma,\Xi}(x)-\Psi(x,w)\bigr{|}^{q}\Big{|}\mathcal{D}^{c}\Bigr{]}\overset{\textnormal{(\ref{eqn:Event_D_for_Theorem_15})}}{\leq}\Bigl{(}\frac{\epsilon}{2}\Bigr{)}^{q}.$
(84)

Bound now (82) using (70), (83), (84), and the elementary bound
$\mathbb{P}[\mathcal{D}^{c}]\leq 1$ to obtain

$\mathbb{E}\Bigl{[}\sup_{x\in\overline{B(0,R)}}\bigl{|}\mathsf{NN}_{\Gamma,\Xi}(x)-\Psi(x,w)\bigr{|}^{q}\Bigr{]}<(2R_{L})^{q}\Bigl{(}\frac{\epsilon}{4R_{L}}\Bigr{)}^{q}+\Bigl{(}\frac{\epsilon}{2}\Bigr{)}^{q}\leq\epsilon^{q}.$

That would prove (39). What remains is to prove (80).

_Proof of ( 80)._ Observe immediately that the right inequality in (80)
follows immediately as $0<\beta<1$ and $Q>1$ (recall the definition of $\Psi$
in (8)). Next, we will prove the left inequality in (80) by mathematical
induction (recall the recursion in (31) and (32) that defines
$\mathsf{NN}_{\Gamma,\Xi}$).

_Base case._ Recall from (31) and (32) that the induction starts with the
functions

$\Xi^{\ell}(x):=\sigma_{1}\Bigl{(}\frac{1}{N}\sum_{i=1}^{2N}(-1)^{i}(V^{\ell}\odot
F^{\ell,i})\sigma_{0}\bigl{(}(-1)^{i}\alpha(I\odot
G^{\ell,i})x\bigr{)}+b^{\ell}\Bigr{)}$ (85)

where element-wise

$V^{\ell}_{rc}=\frac{W^{(1)}_{rc}}{\alpha\bigl{(}\sigma_{-}+\sigma_{+}\bigr{)}\mathbb{E}[F_{rc}^{\ell}]\mathbb{E}[G^{\ell}_{cc}]}.$
(86)

We are now going to prove that for every $x\in\overline{B(0,R)}$, the point

$\frac{1}{N}\sum_{i=1}^{2N}(-1)^{i}(V^{\ell}\odot
F^{\ell,i})\sigma_{0}\bigl{(}(-1)^{i}\alpha(I\odot
G^{\ell,i})x\bigr{)}\in\overline{B\bigl{(}0,\beta^{-1}\|W^{(1)}\|_{\mathrm{HS}}R_{0}\bigr{)}}\quad\textnormal{w.p.\
one}.$ (87)

In particular, by the definition of $R_{1}$ in (26) (which implicitly deals
with the bias $b^{\ell}$), this implies that for all $x\in\overline{B(0,R)}$,

$\bigl{|}\Xi^{\ell}(x)\bigr{|}\leq R_{1}-1.$

Start by noting that there exists an $\alpha_{0}>0$ such that for all
$0<\alpha\leq\alpha_{0}$ and all $\xi\in[-R,R]\subset\mathbb{R}$ we have

$|\sigma_{0}(\alpha\xi)|\leq 2(|\sigma_{-}|+|\sigma_{+}|)\alpha|\xi|.$ (88)

It follows from the bound (88) that for all $x\in\overline{B(0,R)}$ and all
$i\in\overline{1,2N}$,

$\Bigl{|}\frac{1}{\alpha(\sigma_{-}+\sigma_{+})\mathbb{E}[G^{\ell}_{cc}]}\sigma_{0}\bigl{(}\alpha(I\odot
G^{\ell,i})x\bigr{)}_{c}\Bigr{|}<2\frac{|\sigma_{-}|+|\sigma_{+}|}{|\sigma_{-}+\sigma_{+}|}\frac{1}{\beta}|x_{c}|\quad\textnormal{w.p.\
one}.$

Since we assumed in (37) that

$4\frac{|\sigma_{-}|+|\sigma_{+}|}{|\sigma_{-}+\sigma_{+}|}<Q$

it follows that for all $x\in\overline{B(0,R)}$ and all $i\in\overline{1,2N}$,

$\Bigl{|}2\frac{\mathbb{E}[I\odot
G^{\ell}]^{-1}}{\alpha(\sigma_{-}+\sigma_{+})}\sigma_{0}\bigl{(}\alpha(I\odot
G^{\ell,i})x\bigr{)}\Bigr{|}<\frac{Q}{\beta}R<R_{0}\quad\textnormal{w.p.\
one}.$

Therefore, for every $x\in\overline{B(0,R)}$,

$\begin{split}&\Bigl{|}\frac{1}{N}\sum_{i=1}^{2N}(-1)^{i}(V^{\ell}\odot
F^{\ell,i})\sigma_{0}\bigl{(}(-1)^{i}\alpha(I\odot
G^{\ell,i})x\bigr{)}\Bigr{|}\\\
&=\Bigl{|}\frac{1}{2N}\sum_{i=1}^{2N}(-1)^{i}((W^{(1)}\odot
F^{\ell,i})\div\mathbb{E}[F^{\ell,i}])\frac{2\mathbb{E}[I\odot
G^{\ell,i}]^{-1}}{\alpha(\sigma_{-}+\sigma_{+})}\sigma_{0}\bigl{(}(-1)^{i}\alpha(I\odot
G^{\ell,i})x\bigr{)}\Bigr{|}\\\
&\leq\frac{1}{2N}\sum_{i=1}^{2N}\|(W^{(1)}\odot
F^{\ell,i})\div\mathbb{E}[F^{\ell,i}]\|_{\mathrm{HS}}R_{0}\leq\frac{1}{\beta}\|W^{(1)}\|_{\mathrm{HS}}R_{0}\quad\textnormal{w.p.\
one}.\end{split}$

This proves (87).

_Inductive step._ In the definition of $\mathsf{NN}_{\Gamma,\Xi}$ we defined
for $v$ not a leaf in $\Gamma$,

$\Phi^{v}_{\Gamma,\Xi}=\sigma_{v}\Bigl{(}\frac{1}{\\#\mathsf{into}(v)}\sum_{e\in\mathsf{into}(v)}(V^{e}\odot
F^{e})\Phi^{\mathsf{source}(e)}_{\Gamma,\Xi}+b^{e}\Bigr{)}.$

By an inductive argument we find that for all $x\in\overline{B(0,R)}$, it
holds that

$\Bigl{|}\frac{1}{\\#\mathsf{into}(v)}\sum_{e\in\mathsf{into}(v)}(V^{e}\odot
F^{e})\Phi^{\mathsf{source}(e)}_{\Gamma,\Xi}(x)\Bigr{|}\leq\beta^{-1}\|W^{e}\|_{\mathrm{HS}}R_{\mathsf{level}(v)-1}\quad\textnormal{w.p.\
one}.$

so that by definition of $R_{\mathsf{level}{(v)}}$ it holds that

$|\Phi^{v}_{\Gamma,\Xi}(x)|<R_{\mathsf{level}{(v)}}\quad\textnormal{w.p.\
one}.$

In particular,

$\bigl{|}\mathsf{NN}_{\Gamma,\Xi}(x)\bigr{|}^{q}=\bigl{|}\Phi^{v_{0}}_{\Gamma,\Xi}(x)\bigr{|}^{q}<R_{L}^{q}\quad\textnormal{w.p.\
one}.$

This proves (80). With that, Theorem 15 is proven. $\Box$

###  B.4 Proof of Lemma 16

_Proof of ( 41)._ Let $0\leq K<\infty$, $\ell$ be a leaf of $\Gamma$, and
$\rho>0$. Recall that

$\Psi_{1}(x;(W^{(1)},b^{(1)}))=\sigma_{1}\bigl{(}W^{(1)}x+b^{(1)}\bigr{)},$
(89)

and for $x\in\overline{B(0,K)}$, define

$Z_{N}^{\ell}(x)=\frac{1}{N}\sum_{i=1}^{2N}(-1)^{i}(V^{\ell}\odot
F^{\ell,i})\sigma_{0}\bigl{(}(-1)^{i}\alpha(I\odot
G^{\ell,i})x+b\bigr{)}+b^{\ell}$ (90)

so that $\Xi^{\ell}(x)=\sigma_{1}(Z_{N}^{\ell}(x))$. Note that the weights $W$
are fixed and therefore uniformly bounded.

Continuity of $\sigma_{0}$ and $\sigma_{1}$, boundedness of $F$ and $G$,
positivity of $\mathbb{E}[F^{\ell}_{rc}]$ and $\mathbb{E}[G^{\ell}_{rc}]$, and
compactness of the optimization domain imply that the supremum of the
optimization problem is attained—say at $X_{*}\in\overline{B(0,K)}$. Just like
in Appendix B.2, note that $X_{*}$ is random and depends on the collections
$\\{F^{\ell,i}\\}_{i\in\overline{1,2N}}$,
$\\{G^{\ell,i}\\}_{i\in\overline{1,2N}}$. Summarizing:

$\displaystyle\mathbb{P}\Bigl{[}\sup_{x\in\overline{B(0,K)}}\bigl{|}\sigma_{1}(Z_{N}^{\ell}(x))-\sigma_{1}(W^{(1)}x+b^{(1)})\bigr{|}>\rho\Bigr{]}$
$\displaystyle=\mathbb{P}\Bigl{[}\bigl{|}\sigma_{1}(Z_{N}^{\ell}(X_{*}))-\sigma_{1}(W^{(1)}X_{*}+b^{(1)})\bigr{|}>\rho\Bigr{]}.$
(91)

Note that here we slightly abuse the notation by using $|\cdot|$ sign not only
for absolute value of numbers, but also, as in the last formula, for the
Euclidean norm of the vector.

By construction, there exists a compact set $\mathcal{C}$ so that the points

$Z_{N}^{\ell}(X_{*}),\quad W^{(1)}X_{*}+b^{(1)}$ (92)

lie in $\mathcal{C}$ with probability one. The uniform continuity of
$\sigma_{1}$ on $\mathcal{C}$ implies that for each $\zeta>0$ there exists
$\eta_{\zeta}>0$ such that (59) holds for $\sigma_{1}$ and all
$x,y\in\mathcal{C}$. Fix $\zeta=\rho$ and introduce the event

$\mathcal{D}(X_{*})=\bigl{\\{}\|Z_{N}^{\ell}(X_{*})-(W^{(1)}X_{*}+b^{(1)})\|_{2}<\eta_{\rho}\bigr{\\}}.$
(93)

By the law of total probability

$\displaystyle\mathbb{P}\Bigl{[}|\sigma_{1}(Z_{N}^{\ell}(X_{*}))-\sigma_{1}(W^{(1)}X_{*}+b^{(1)})|>\rho\Bigr{]}$
$\displaystyle=\mathbb{P}\Bigl{[}|\sigma_{1}(Z_{N}^{\ell}(X_{*}))-\sigma_{1}(W^{(1)}X_{*}+b^{(1)})|>\rho\,|\,\mathcal{D}(X_{*})\Bigr{]}\mathbb{P}\Bigl{[}\mathcal{D}(X_{*})\Bigr{]}$
$\displaystyle\phantom{=}+\mathbb{P}\Bigl{[}|\sigma_{1}(Z_{N}^{\ell}(X_{*}))-\sigma_{1}(W^{(1)}X_{*}+b^{(1)})|>\rho\,|\,\mathcal{D}^{\mathrm{c}}(X_{*})\Bigr{]}\mathbb{P}\Bigl{[}\mathcal{D}^{\mathrm{c}}(X_{*})\Bigr{]}\leq\mathbb{P}\Bigl{[}\mathcal{D}^{\mathrm{c}}(X_{*})\Bigr{]}.$
(94)

We will next prove that for all $x\in\overline{B(0,K)}$,

$\mathbb{P}\Bigl{[}\mathcal{D}^{\mathrm{c}}(x)\Bigr{]}\to 0$ (95)

as $\alpha\downarrow 0$ and $N\to\infty$. Together with (94), this implies the
result.

Let $x\in\overline{B(0,K)}$. Component-wise,

$\displaystyle\bigl{(}Z_{N}^{\ell}(x)-(W^{(1)}x+b^{(1)})\bigr{)}_{r}$ (96)
$\displaystyle=\Bigr{(}\sum_{i=1}^{2N}\frac{(-1)^{i}}{N}(V^{\ell}\odot
F^{\ell,i})\sigma_{0}\bigl{(}(-1)^{i}\alpha(I\odot
G^{\ell,i})x\bigr{)}+b^{\ell}-(W^{(1)}x+b^{(1)})\Bigr{)}_{r}$
$\displaystyle=\sum_{i=1}^{2N}\sum_{c=1}^{d_{0}}\frac{(-1)^{i}}{N}V^{\ell}_{rc}F^{\ell,i}_{rc}\sigma_{0}\bigl{(}(-1)^{i}\alpha(I\odot
G^{\ell,i})x\bigr{)}_{c}+b^{(1)}_{r}-\sum_{c}W^{(1)}_{rc}x_{c}+b^{(1)}_{r}.$

Substituting (36) into (96), using the triangle inequality, and rearranging
terms, we find that

$\displaystyle\bigl{|}\bigl{(}Z_{N}^{\ell}(x)-(W^{(1)}x+b^{(1)})\bigr{)}_{r}\bigr{|}$
$\displaystyle\leq\sum_{c=1}^{d_{0}}\Bigl{|}\frac{W^{(1)}_{rc}}{\tfrac{1}{2}(\sigma_{-}+\sigma_{+})\mathbb{E}[G^{\ell}_{cc}]}\Bigl{(}\tfrac{1}{2N}\sum_{i=1}^{2N}\frac{F^{\ell
i}_{rc}}{\mathbb{E}[F^{\ell}_{rc}]}(-1)^{i}\sigma_{0}\bigl{(}(-1)^{i}\alpha(I\odot
G^{\ell,i})x\bigr{)}_{c}\Bigr{)}-W^{(1)}_{rc}x_{c}\Bigr{|}.$ (97)

Note that the assumptions of the lemma imply that

$\Bigl{|}\frac{W^{(1)}_{rc}}{\tfrac{1}{2}(\sigma_{-}+\sigma_{+})\mathbb{E}[G^{\ell}_{cc}]}\Bigr{|}\leq
C_{w,G,\sigma}<+\infty.$

We focus now on the term within brackets in (97). Let $\delta_{1}>0$ and
consider the event

$\mathcal{E}_{F,N}(\delta_{1})=\Bigl{\\{}\Bigl{|}\tfrac{1}{2N}\sum_{i=1}^{2N}\frac{F^{\ell
i}}{\mathbb{E}[F^{\ell}_{rc}]}-1\Bigr{|}<\delta_{1}\Bigr{\\}}.$ (98)

There exists $C_{1}>0$ such that, conditional on
$\mathcal{E}_{F,N}(\delta_{1})$,

$\displaystyle\Bigl{|}$
$\displaystyle\tfrac{1}{2N}\sum_{i=1}^{2N}\frac{F^{\ell
i}}{\mathbb{E}[F^{\ell}_{rc}]}(-1)^{i}\sigma_{0}\bigl{(}(-1)^{i}\alpha(I\odot
G^{\ell,i})x\bigr{)}_{c}-\tfrac{1}{2N}\sum_{i=1}^{2N}(-1)^{i}\sigma_{0}\bigl{(}(-1)^{i}\alpha(I\odot
G^{\ell,i})x\bigr{)}_{c}\Bigr{|}$
$\displaystyle\leq\Bigl{|}\tfrac{1}{2N}\sum_{i=1}^{2N}\Bigl{(}\frac{F^{\ell
i}}{\mathbb{E}[F^{\ell}_{rc}]}-1\Bigr{)}(-1)^{i}\sigma_{0}\bigl{(}(-1)^{i}\alpha(I\odot
G^{\ell,i})x\bigr{)}_{c}\Bigr{|}\leq C_{1}\delta_{1}$ (99)

since the argument of $\sigma_{0}$ is uniformly bounded, and $\sigma_{0}$ is
continuous. Moreover, there exists $C_{2}>0$ such that conditional on
$\mathcal{E}_{F,N}(\delta_{1})$,

$\displaystyle\bigl{|}\bigl{(}Z_{N}^{\ell}(x)-(W^{(1)}x+b^{(1)})\bigr{)}_{r}\bigr{|}$
(100)
$\displaystyle\leq\sum_{c=1}^{d_{0}}\Bigl{|}\frac{W^{(1)}_{rc}}{\tfrac{1}{2}(\sigma_{-}+\sigma_{+})\mathbb{E}[G^{\ell}_{cc}]}\Bigl{(}\tfrac{1}{2N}\sum_{i=1}^{2N}\tfrac{1}{\alpha}\Bigl{(}(-1)^{i}\sigma_{0}\bigl{(}(-1)^{i}\alpha(I\odot
G^{\ell,i})x\bigr{)}_{c}\Bigr{)}\Bigr{)}-W^{(1)}_{rc}x_{c}\Bigr{|}+C_{2}\delta_{1}.$

Note that $C_{1},C_{2}$ are independent of $N,\delta_{1}$.

Recall now that by (33) and (34) we can find for each $\gamma>0$ an $\alpha>0$
such that for all $y\in\mathbb{R}^{d_{0}}$, $c$,

$\Bigl{|}\frac{1}{\alpha}\Bigl{(}\sigma_{0}\bigl{(}\alpha
y\bigr{)}\Bigr{)}_{c}-\sigma_{S(y_{r})}y_{c}\Bigr{|}<\gamma.$ (101)

Recall furthermore that $\max_{rc}G^{\ell}_{rc}\leq M<\infty$ with probability
one by assumption. Together, this implies that we can find for each $\gamma>0$
an $\alpha>0$ such that for all $x\in\overline{B(0,K)}$, $c$,

$\mathbb{P}\Bigl{[}\Bigl{|}\frac{1}{\alpha}\Bigl{(}\pm\sigma_{0}\bigl{(}\pm\alpha
I\odot G^{\ell,i}x\bigr{)}\Bigr{)}_{c}-\sigma_{S(\pm G^{\ell
i}_{cc}x_{c})}G^{\ell i}_{cc}x_{c}\Bigr{|}<\gamma\Bigr{]}=1$ (102)

Fix $\gamma\in(0,\delta_{1})$ and corresponding $\alpha>0$. Then there exists
a constant $C_{3}>0$, independent of $\delta_{1},\gamma,N$, such that
conditional on $\mathcal{E}_{F,N}(\delta_{1})$,

$\displaystyle\bigl{|}\bigl{(}Z_{N}^{\ell}(x)-(W^{(1)}x+b^{(1)})\bigr{)}_{r}\bigr{|}$
(103)
$\displaystyle\leq\sum_{c=1}^{d_{0}}\Bigl{|}\frac{W^{(1)}_{rc}}{\tfrac{1}{2}(\sigma_{-}+\sigma_{+})\mathbb{E}[G^{\ell}_{cc}]}\Bigl{(}\tfrac{1}{2N}\sum_{i=1}^{2N}\sigma_{S((-1)^{i}G^{\ell
i}_{cc}x_{c})}G^{\ell
i}_{cc}x_{c}\Bigr{)}-W^{(1)}_{rc}x_{c}\Bigr{|}+C_{3}\delta_{1}$
$\displaystyle\overset{\textnormal{(i)}}{=}\sum_{c\in\overline{1,d_{0}}:x_{c}>0}\Bigl{|}\frac{W^{(1)}_{rc}}{\tfrac{1}{2}(\sigma_{-}+\sigma_{+})\mathbb{E}[G^{\ell}_{cc}]}\Bigl{(}\tfrac{1}{2N}\sum_{i=1}^{2N}\sigma_{S((-1)^{i}G^{\ell
i}_{cc}x_{c})}G^{\ell
i}_{cc}x_{c}\Bigr{)}-W^{(1)}_{rc}x_{c}\Bigr{|}+C_{3}\delta_{1}.$

To conclude (i), we used the fact that $\sigma_{\pm}\cdot 0=0$. By assumption
$G^{\ell i}_{cc}\geq 0$ with probability one, so if moreover $|x_{c}|>0$, then
$S((-1)^{i}G^{\ell i}_{cc}x_{c})=S((-1)^{i}x_{c})$ with probability one—recall
its definition in (34). Thus there exists $C_{4}$ independent of
$\delta_{1},\gamma,N$ such that conditional on the event
$\mathcal{E}_{F,N}(\delta_{1})\cap\mathcal{E}_{G,N}(\delta_{1})$,

$\displaystyle\bigl{|}Z_{N}^{\ell}(x)-(W^{(1)}x+b^{(1)})\bigr{|}_{r}$
$\displaystyle\leq\sum_{c\in\overline{1,d_{0}}:|x_{c}|>0}\Bigl{|}\frac{W^{(1)}_{rc}}{\tfrac{1}{2}(\sigma_{-}+\sigma_{+})}\frac{1}{2N}\sum_{i=1}^{2N}\sigma_{S((-1)^{i}x_{c})}x_{c}-W^{(1)}_{rc}x_{c}\Bigr{|}+C_{4}\delta_{1}=C_{4}\delta_{1}.$
(104)

The last equality holds because the sum is only of over $c$ such that
$|x_{c}|>0$.

All that remains is to prove that

$\mathbb{P}[\mathcal{E}_{F,N}(\delta_{1})\cap\mathcal{E}_{G,N}(\delta_{1})]\to
1\quad\textnormal{as}\quad N\to\infty.$ (105)

This fact follows immediately from the independence of $F,G$, and a subsequent
application of Khinchin’s weak law of large numbers (which may be applied
since $F,G$’s expectations are bounded). Note that $\delta_{1}$ is an
arbitrary parameter: choosing it such that $C_{4}\delta_{1}<\eta_{\zeta}$, and
then choosing $N$ sufficiently large completes the proof of (41).

_Proof of ( 42)._ The assertion (39) is proven for any
$(\alpha,N)$-precomposition associated with some distributions
$\mu^{\ell},\nu^{\ell}$ with finite nonzero mean. In particular, the same
argument shows that (39) holds when $F^{\ell}$ and $G^{\ell}$ are taken
deterministic and equal to the expectations of the corresponding random
variables (see also the discussion following (36)). This proves (42). $\Box$