Strong Lottery Ticket Hypothesis with $\varepsilon$–perturbation

Zheyang Xiong⋆ Fangshuo Liao⋆ Anastasios Kyrillidis

Rice University Rice University Rice University

###### Abstract

The strong Lottery Ticket Hypothesis (LTH) (Ramanujan et al., 2019; Zhou et
al., 2019) claims the existence of a subnetwork in a sufficiently large,
randomly initialized neural network that approximates some target neural
network without the need of training. We extend the theoretical guarantee of
the strong LTH literature to a scenario more similar to the original LTH, by
generalizing the weight change in the pre-training step to some perturbation
around initialization. In particular, we focus on the following open
questions: By allowing an $\varepsilon$-scale perturbation on the random
initial weights, can we reduce the over-parameterization requirement for the
candidate network in the strong LTH? Furthermore, does the weight change by
SGD coincide with a good set of such perturbation?

We answer the first question by first extending the theoretical result on
subset sum Lueker (1998) to allow perturbation on the candidates. Applying
this result to the neural network setting, we show that such
$\varepsilon$-perturbation reduces the over-parameterization requirement of
the strong LTH. To answer the second question, we show via experiments that
the perturbed weight achieved by the projected SGD shows better performance
under the strong LTH pruning.

##  1 Introduction

Pruning techniques for over-parameterized neural networks have drawn growing
attention in recent years (Han et al., 2015; Li et al., 2016; Wen et al.,
2016; He et al., 2017; Zhu and Gupta, 2017; Blalock et al., 2020; Wang et al.,
2019; Lee et al., 2018; Wang et al., 2020). Amongst them, the Lottery Ticket
Hypothesis (LTH) (Frankle and Carbin, 2019; Frankle et al., 2019) claims the
existence of a small (sparse) subnetwork within a large (dense) neural network
such that, when trained in isolation, achieves comparable or even better
performance than the original dense network. Such subnetworks can be
identified by pre-training the dense network and pruning it based on the
magnitude of the learned weights (Frankle and Carbin, 2019). Currently, to the
best of our knowledge, the LTH lacks of any rigorous theoretical guarantees
that justify superior performance of the subnetwork, especially under the
pretraining-based pruning; yet, it has been proven to be effective in
practice.

The Strong Lottery Ticket Hypothesis (Ramanujan et al., 2019; Zhou et al.,
2019) leverages a different pruning scheme: given a target dense neural
network, and a randomly initialized, sufficiently over-parameterized candidate
network, there exists a subnetwork in the latter that approximates the former
arbitrarily well without the need of training. While we usually require a
significant over-parameterization in the randomly initialized network, the
strong LTH enjoys extensive theoretical guarantees (Malach et al., 2020;
Pensia et al., 2020; Orseau et al., 2020). Yet, the same theory hardly applies
to the original LTH, as strong LTH assumes that the candidate weights pruned
are fixed at initialization. _The fact that LTH pruning is based on weights
modified by pre-training motivates us to analyze the approximation behavior
that emerges beyond the randomness in the candidate weights._

Further study on the pre-training process of the LTH shows that the winnning
lottery ticket emerges in the early stage of training (You et al., 2019), when
the loss have not converge to a desirably small value. This implies that
converging to small training loss is not necessarily the intent of the pre-
training steo in the LTH procedure; in other words, achieving small loss does
not necessarily explain how and why pre-training helps pruning in LTH.
Instead, one could hypothesize that the pre-training –based on loss
minimization– guide the weight perturbation to a direction that facilitate the
pruning process.

Based on this hypothesis, our work extends the theoretical guarantee of strong
LTH to a scenario more similar to the original LTH, by generalizing the weight
change achieved in the pre-training step to some perturbation around the
initialization. Our central question is as follows:

“By allowing an $\varepsilon$-scale perturbation on the random initial
weights, can we reduce the over-parameterization requirement for the candidate
network in the strong LTH? Furthermore, does the weight change by SGD coincide
with a good set of such perturbation?”

To be more specific, let $f_{\bm{\theta}}$ be a neural network with parameters
$\bm{\theta}\in\mathbb{R}^{d}$. Formally, an $\varepsilon$-perturbation is a
mapping $\mathcal{P}:\mathbb{R}^{d}\rightarrow\mathbb{R}^{d}$ such that the
maximum entrywise perturbation is bounded in absolute value by $\varepsilon$,
i.e., $\|\mathcal{P}(\bm{\theta})-\bm{\theta}\|_{\infty}\leq\varepsilon$. We
point out that this definition of perturbation generalizes to two existing
scenarios: when $\varepsilon=0$ –i.e., we allow no weight perturbation– the
question above reduces to the original strong LTH. When $\varepsilon=\infty$
–i.e., we allow arbitrarily large weight perturbation– the required over-
parameterization for the candidate network is at most the size of the target
network. In this case, we often use gradient based optimizers such as SGD to
find such weight perturbation, but often without the need of pruning. Yet,
both cases cover only one aspect in pruning and perturbation.

In this paper, we study the inter-dependence of the two aspects above by
treating $\varepsilon$ as a variable. In particular, we show that a larger
perturbation scale $\varepsilon$, which corresponds to a larger amount of
training, would alleviate the over-parameterization requirement, while keeping
the accuracy of the pruned neural network the same. Our contributions can be
summarized as below:

  * •

We consider a generalized version of the subset sum problem where each
candidate in the summation is allowed perturbation bounded by a fixed scale
$\varepsilon$. We extend the analysis of the subset sum (Lueker, 1998) to our
generalized version, and show that when a larger perturbation is allowed, the
required size of the candidate set can be reduced. We empirically validate our
theoretical result on the perturbed subset sum problem.

  * •

Applying the theoretical result above to neural networks, we prove that, when
an $\varepsilon$-scale perturbation is allowed, the strong LTH on randomly
initialized neural network requires less over-parameterization to achieve a
specific approximation error. In particular, the over-parameterization
decreases as $\varepsilon$ increases.

  * •

On neural networks, we empirically show that $i)$ the perturbation that
alleviates the overparameterization requirement of the strong LTH can be
obtained by projected SGD on the initialized weights; and, $ii)$ under fixed
overparameterization, neural networks with a larger freedom over the level of
perturbation achieves a higher accuracy after pruning. This result establish
the connection between the amount of pre-training and the accuracy of the
pruned network.

##  2 Related Works

Lotter Ticket Hypothesis. The Lottery Ticket Hypothesis is first proposed by
(Frankle and Carbin, 2019). Later works investigate this hypothesis under
different scenarios and from different perspectives. To name a few, (Yu et
al., 2019) studies the LTH in the reinforcement learning setting. (Sabatelli
et al., 2020) investigates the performance of lottery tickets in the setting
of transfer learning. (You et al., 2019) find that the lottery tickets can be
observed in the early phase of training. Moreover, a line of work (Lee et al.,
2018; Wang et al., 2020; Tanaka et al., 2020; Patil and Dovrolis, 2020)
propose pruning techniques without the need of pre-training. Noticeably,
(Tanaka et al., 2020) and (Patil and Dovrolis, 2020) even require no training
data. For a comprehensive survey on the LTH, we refer the readers to (Lange,
2020) and (da Cunha et al., 2022b).

Several works attempt to explain the LTH. (Evci et al., 2022) empirically
study the behavior of gradient flow in the pruned network. (Zhang et al.,
2021) assumes that the optimal mask is given, and proves that the pruned
network achieves faster convergence and better generalization when trained
from initialization. (Wolfe et al., 2021) provides a theoretical guarantee for
a pruning-after-training fashion. However, these works differ from ours in the
following: $i)$ they usually consider neuron pruning on small neural network
archictures (e.g., (Wolfe et al., 2021) focuses on a two-layer MLP with smooth
activations), while our work considers weight pruning of a deep ReLU neural
network; $ii)$ they consider minimizing the loss on a specific dataset, and
require an over-parameterization that scales quadratically with the number of
samples, while we approximate a target network with a fixed architecture in
terms of the function norm, and require an over-parameterization that scales
with the width of the target network.

Strong Lottery Ticket Hypothesis. The strong LTH originates from the empirical
observation that, by fixing the weights at initialization and learning the
mask over the weights, one can identify subnetworks that achieve comparable
accuracy to the dense one with learned weights (Zhou et al., 2019). (Ramanujan
et al., 2019) made this idea more concrete by proposing the edge-popup
algorithm to efficiently learn the mask. (Malach et al., 2020) first proved
such hypothesis under the assumption that the dense network’s size scales
polynomially with the target network’s width and depth. Leveraging the
advantage of weight decomposition and theoretical results on the subset sum
problem (Lueker, 1998), (Orseau et al., 2020) and (Pensia et al., 2020)
improved the over-parameterization requirement to a logarithm factor times the
size of the target network. Later work explores different variations of the
strong LTH: (da Cunha et al., 2022b) and (Burkholz, 2022) show that the strong
LTH holds in the case of convolutional neural networks. (Burkholz et al.,
2022) extends the strong LTH proof to a universial family of functions.
Finally, (Chijiwa et al., 2021) further reduces the over-parameterization
requirement by employing the iterative randomization.

##  3 Notations and Setup

Notation. We use standard lower case letters (e.g. $a$) to denote scalars,
bold lower-case letters (e.g. $\mathbf{a}$) to denote vectors, and bold upper-
case letters (e.g. $\mathbf{A}$) to denote matrices. For a vector
$\mathbf{a}$, we use $\left\|\mathbf{a}\right\|_{2}$ to denote its $\ell_{2}$
(Euclidean) norm, and $\left\|\mathbf{a}\right\|_{\infty}$ to denote its
$\ell_{\infty}$ norm. For a matrix $\mathbf{A}$, we use
$\left\|\mathbf{A}\right\|_{\max}=\max_{ij}\left|A_{ij}\right|$ to denote its
$\max$ norm. We use $\mathbb{P}\left(\cdot\right)$ to denote the probability
of an event, and $\mathbb{E}\left[\cdot\right]$ to denote the expectation of a
random variable. Moreover, $\texttt{Unif}\left(I\right)$ denotes the uniform
distribution on the interval $I$, $\texttt{Geom}\left(\cdot\right)$ denotes
the geometric distribution, and $\texttt{Bin}\left(\cdot,\cdot\right)$ denotes
the binomial distribution. Lastly, we use $\sigma\left(a\right)=\max\\{0,a\\}$
to denote the ReLU activation.

Setup. Similar to (Pensia et al., 2020), our focus is to approximate an
$L$-layer, ReLU activated target multi-layer perceptron (MLP) $f(\mathbf{x})$
by pruning a $2L$-layer, ReLU activated candidate MLP $g(\mathbf{x})$. For
some input vector $\mathbf{x}\in\mathbb{R}^{d_{0}}$, we assume
$f(\mathbf{x})=f^{L}(\mathbf{x})$ has a fixed set of parameters
$\\{\mathbf{W}^{\ell}\\}_{\ell=1}^{L}$, represented by:

$\displaystyle f^{\ell}(\mathbf{x})$
$\displaystyle=\begin{cases}\mathbf{W}^{L}f^{L-1}(\mathbf{x}),&\text{if
}\ell=L,\\\
\sigma\left(\mathbf{W}^{\ell}f^{\ell-1}(\mathbf{x})\right),&\text{if
}\ell\in[L-1],\\\ \mathbf{x},&\text{if }\ell=0,\end{cases}$

where $\mathbf{W}^{\ell}\in\mathbb{R}^{d_{\ell}\times d_{\ell-1}}$. Similarly,
let $g(\mathbf{x})=g^{2L}(\mathbf{x})$ with parameters
$\\{\mathbf{U}_{\ell}\\}_{\ell=1}^{2L}$, represented by:

$\displaystyle g^{\ell}(\mathbf{x})$
$\displaystyle=\begin{cases}\mathbb{U}^{2L}g^{2L-1}(\mathbf{x}),&\text{if
}\ell=2L,\\\
\sigma\left(\mathbb{U}^{\ell}g^{\ell-1}(\mathbf{x})\right),&\text{if
}\ell\in[2L-1],\\\ \mathbf{x},&\text{if }\ell=0,\end{cases}$

where $\mathbf{U}^{\ell}\in\mathbb{R}^{\hat{d}_{\ell}\times\hat{d}_{\ell-1}}$.
In particular, $g$ is a neural network with twice the depth of $f$. We
consider the pruning and $\varepsilon$-perturbation of $g(\mathbf{x})$ with a
set of masks for the weights
$\mathcal{S}=\\{\mathbf{S}^{\ell}\\}_{\ell=1}^{2L}$ and perturbation matrices
$\mathcal{Y}=\\{\mathbf{Y}^{\ell}\\}_{i=\ell}^{L}$, denoted as
$g_{\mathcal{S},\mathcal{Y}}(\mathbf{x})=g_{\mathcal{S},\mathcal{Y}}^{2L}(\mathbf{x})$:

$\displaystyle
g_{\mathcal{S},\mathcal{Y}}^{\ell}(\mathbf{x})=\begin{cases}(\mathbf{S}^{\ell}\odot(\mathbb{U}^{\ell}+\mathbf{Y}^{\ell}))g_{\mathcal{S},\mathcal{Y}}^{\ell-1}(\mathbf{x}),&\text{if
}\ell=2L,\\\
\sigma\left((\mathbf{S}^{\ell}\odot(\mathbb{U}^{\ell}+\mathbf{Y}^{\ell}))g_{\mathcal{S},\mathcal{Y}}^{\ell-1}(\mathbf{x})\right),&\text{if
}\ell\in[L-1],\\\ \mathbf{x},&\text{ if }\ell=0.\end{cases}$

Intuitively, $g_{\mathcal{S},\mathcal{Y}}$ is constructed such that, in each
layer of $g_{\mathcal{S},\mathcal{Y}}$, the weight matrix $\mathbf{U}^{\ell}$
is first applied with a perturbation matrix $\mathbf{Y}^{\ell}$ and then
pruned by applying the mask $\mathbf{S}^{\ell}$ Let
$\mathcal{F}_{\mathcal{Y}}$ denote the feasible set of the perturbation
$\mathcal{Y}$. We make the following assumption:

######  Assumption 1.

We assume the following condition for $f,g$ and $\mathcal{F}_{\mathcal{Y}}$:

  1. (a)

For all $\ell\in\\{0\\}\cup[L]$, the weight matrix $\mathbf{W}^{\ell}$ of the
target neural network $f$ satisfies $\left\|\mathbf{W}^{\ell}\right\|\leq 1$
and $\left\|\mathbf{W}^{\ell}\right\|_{\max}\leq\frac{1}{2}$.

  2. (b)

The initialization of $g$ satisfies
$\mathbf{U}^{2\ell}_{ij}\sim\texttt{Unif}[-1,1]$, and
$\mathbf{U}^{2\ell-1}_{ij}=1$ if $i\leq\nicefrac{{\hat{d}_{2(\ell-1)}}}{{2}}$
and $\mathbf{U}^{2\ell-1}_{ij}=-1$ if
$i>\nicefrac{{\hat{d}_{2(\ell-1)}}}{{2}}$ for all $\ell\in[L]$ and
$j\in[\hat{d}_{2\ell-3}]$.

  3. (c)

The feasible set of $\mathcal{Y}$ is defined as:

$\displaystyle\mathcal{F}_{\mathcal{Y}}=\left\\{\mathcal{Y}:\forall\ell\in[L],\left\|\mathbf{Y}^{2\ell-1}\right\|_{\max}=0\wedge\left\|\mathbf{Y}^{2\ell}\right\|_{\max}\leq\varepsilon\right\\}.$

Remark 1. Assumption 3(a) is similar to (Pensia et al., 2020). In particular,
the also assume that $\left\|\mathbf{W}^{\ell}\right\|\leq 1$ for all $\ell$.
We additional assume that
$\left\|\mathbf{W}^{\ell}\right\|_{\max}\leq\frac{1}{2}$ to facilitate the
application of our subset sum result in Theorem (3). This condition can be
easily satisfied by most initialization methods. Assumption 3(b) states the
initialization scheme for the candidate MLP $g$. Intuitively, for weights in
layers with odd indices, we initialize the top half to $1$ and the lower half
to $-1$, and for weights in layers with even indices, we initialize entries
uniformly at random from $[-1,1]$. Although different from (Pensia et al.,
2020), we show in later section that this initialization does not affect the
difficulty of the approximation, and is only for the convenience of analysis.
Assumption 3(c) defines the feasible set. In our setting, we only allow
weights in layers with even indices to be perturbed. We show in later section
that this feasible set is sufficient to establish the dependence of the over-
parameterization on the perturbation scale $\varepsilon$.

To represent the functional approximation of $f$ using
$g_{\mathcal{S},\mathcal{Y}}$, we focus on the approximation error defined as:

$\displaystyle\min_{\mathcal{Y}\in\mathcal{F}_{\mathcal{Y}},\mathcal{S}}\sup_{\mathbf{x}:\|\mathbf{x}\|\leq
1}\left\|f(\mathbf{x})-g_{\mathcal{S},\mathcal{Y}}\left(\mathbf{x}\right)\right\|.$
(1)

##  4 Subset Sum with $\varepsilon$-Perturbation

For each layer in the target network, (Pensia et al., 2020) constructed a two-
layer subnetwork with block structure, such that each block approximates a
single entry in the weight matrix of the target network. In particular, they
obtain a logarithmic-scale over-parameterization by formulating the
approximation as a subset sum problem (Lueker, 1998; da Cunha et al., 2022a)
Given a candidate set of values $\\{x_{i}\\}_{i=1}^{n}$ of size $n$ and a
target value $z$, the solution to the subset sum problem finds the best
approximation of $z$ using the sum of a subset of $\\{x_{i}\\}_{i=1}^{n}$.
From an optimization perspective, the optimal approximation error
$\eta^{\star}$ is the solution to the following problem:

$\displaystyle\eta^{\star}=\min_{\bm{\delta}\in\\{0,1\\}^{n}}\left|\sum_{i=1}^{n}\delta_{i}x_{i}-z\right|,$
(2)

where $\delta_{i}\in\\{0,1\\}$ is the indicator variable on whether $x_{i}$ is
selected in the sum to approximate $z$.

From the perspective of strong LTH, we can treat $z$ as the weight entry in
the target network that we wish to approximate, and $\\{x_{i}\\}_{i=1}^{n}$ as
the weights in the candidate network we will prune. Here, $\delta_{i}=1$ means
that the $i$-th weight is kept, while $\delta_{i}=0$ means that the $i$-th
weight is pruned. (Lueker, 1998) shows that, with high probability over the
randomness of $\mathbf{x}_{i}\sim\texttt{Unif}\left([-1,1]\right)$, a
candidate set with size of the order $n=\Omega\left(\log\eta^{-1}\right)$ is
enough to guarantee that $\eta^{*}\leq\eta$ for all
$z\in[-\nicefrac{{1}}{{2}},\nicefrac{{1}}{{2}}]$.

As an extension to the strong LTH, our setup incorporates an
$\varepsilon$-perturbation on the weights of the random neural network. This
calls for the attention of extending the random subset sum problem in Equation
2 to a version with $\varepsilon$-perturbation added.

In particular, we consider the following joint minimization problem:

$\displaystyle\eta^{\star}=\min_{\bm{\delta}\in\\{0,1\\}^{n},\mathbf{y}\in[-\varepsilon,\varepsilon]^{n}}\left|\sum_{i=1}^{n}\delta_{i}\left(x_{i}+y_{i}\right)-z\right|.$
(3)

Figure 1: Diagram showing the effect of perturbation on the pruning scheme of
strong LTH (Pensia et al., 2020).

We denote the values that lead to the optimal approximation error as
$\bm{\delta}^{\star}$ and $\mathbf{y}^{\star}$, respectively. In words, the
above problem aims to select values from the set $\\{x_{i}\\}_{i=1}^{n}$ such
that, after potential entrywise perturbation by some tunable
$y_{i}\in[-\varepsilon,\varepsilon]$, the summation of the selected and
perturbed $\sum_{i=1}^{n}\delta_{i}\left(x_{i}+y_{i}\right)$ will approximate
$z$.

A central technical difficulty in our work is to extend the result of (Lueker,
1998) to incorporate such $\varepsilon$-perturbation. Intuitively, as the
perturbation scale $\varepsilon$ becomes larger, each candidate is susceptible
to a larger change in order to better approximate the objective $z$. This
implies that we should only require a smaller size for the candidate size.
This is indeed the case, as we show in the theorem below.

######  Theorem 1.

Given a candidate set $\\{x_{i}\\}_{i=1}^{n}$ with
$x_{i}\sim\texttt{Unif}\left([-1,1]\right)$ for all $i\in[n]$. Consider the
$\varepsilon$-perturbed random subset sum problem in Equation 3. Let the
number of candidates satisfy $n=K_{1}+K_{2}$ with

$\displaystyle
K_{1}=O\left(\frac{\log\eta^{-1}}{\log\left(\frac{5}{4}+\frac{\varepsilon}{2}\right)}\right)\quad;K_{2}=O\left(1+\frac{\log\eta^{-1}}{(1+\varepsilon)}\right)$

Then with probability at least
$1-\exp\left(-\frac{K_{2}(1+\varepsilon)^{2}}{8(3-\varepsilon)^{2}}\right)-\exp\left(-\frac{K_{1}}{18}\right)-\exp\left(-\max\\{\varepsilon,\eta\\}K_{1}\right)$
we have that all $z\in[-\nicefrac{{1}}{{2}},\nicefrac{{1}}{{2}}]$ has a
$2\eta$-approximation.

Sketch of proof: The proof of Theorem (3) is provided in Appendix (1).
Compared with the proof of (Lueker, 1998), we included the
$\varepsilon$-perturbation when constructing the recurrence of the size of the
target range that can be approximated. After introducing this
$\varepsilon$-perturbation, we cannot directly apply the techniques in
(Lueker, 1998). We sketch the proof below while omitting details and the
handling of edge cases of different $\varepsilon$:

  1. 1.

We start by defining an indicator function $f_{k,\eta}(z)$ corresponding to
the event that $z$ has an $\eta$-approximation by the first $k$ candidates. We
show that this indicator function can be recursively defined:
$f_{k+1,\eta}(z)$ can be written as a function of $f_{k,\eta}(z)$ and
$f_{k,\eta+\varepsilon}(z)$. However, this sequence is hard to control as it
involves the $f_{k,\eta+\varepsilon}(z)$. We further study the behavior of the
set where $f_{k,\eta+\varepsilon}(z)=1$, and, by introducing the notion of
$\varepsilon$-extensionm, we construct another sequence of indicator functions
$\\{\hat{f}_{k}\\}_{k=1}^{n}$ that lower bound $f_{k,\eta}$ yet shows the
advantage of large $\varepsilon$.

  2. 2.

As in (Lueker, 1998), we define $p_{k}$ to be the fraction of $z$ on the
interval $[-\nicefrac{{1}}{{2}},\nicefrac{{1}}{{2}}]$ such that
$\hat{f}_{k}=1$. Differently, we show that the expectation of $p_{k+1}-p_{k}$
is lower bounded by $\nicefrac{{1}}{{2}}(1-p_{k})(p_{k}+\varepsilon)$. This
demonstrates the expected growth $p_{k+1}$ enjoys from $p_{k}$. Noticeably,
this growth is larger when $\varepsilon$ is larger. Note that this property
implies a lower bound on the expectation of $p_{n}$. Next, we apply several
techniques to remove the expectation.

  3. 3.

We first show the lower bound on $K_{1}$ such that
$p_{K_{1}}\geq\nicefrac{{1}}{{4}}$ with a high probability. We do this by
partitioning the interval $[0,\nicefrac{{1}}{{4}}]$ into sub-intervals that
represents geometric grown. We then show that the sum of the number of steps
of growth that escapes these intervals can be represented as a binomial random
variable, which can be bounded by applying Hoeffding’s inequality.

  4. 4.

Next, starting from $p_{k}\geq\nicefrac{{1}}{{4}}$, we lower-bound the
summation of $Z_{k+1}=\frac{p_{k+1}-p_{k}}{p_{k}(1-p_{k})}$ using Azuma’s
inequality. To relate the summation of $Z_{k+1}$ to the growth of $p_{k}$, we
define a function $\psi(p)$ such that $\psi(p_{k+1})-\psi(p_{k})\geq Z_{k+1}$.
In this way, we arrive at a lower bound on
$\psi(p_{K_{1}+K_{2}})-\psi(\nicefrac{{1}}{{4}})$. Enforcing a lower bound on
$p_{K_{1}+K_{2}}$ gives a lower bound on $K_{2}$.

Remark 2. Notice that the lower bound on the candidate set $n$ depends on
$K_{1}$ and $K_{2}$, where $K_{1}$ scales inversely with
$\log(\nicefrac{{5}}{{4}}+\nicefrac{{\varepsilon}}{{2}})$ and $K_{2}$ scales
inversely with $1+6\varepsilon$. This implies that $n$ decreases monotonically
as $\varepsilon$ increases. We will utilize this result to analyze the
approximation error defined in Equation 5.

##  5 Strong Lottery Ticket Hypothesis with $\varepsilon$ Perturbation

The theoretical result above provides the “skeleton” of techniques on how to
incorporate perturbation into the approximation process for the subset sum
problem. In what follows, we demonstrate how to apply this “skeleton” into the
approximation of a target neural network. As in (Pensia et al., 2020), we
start with approximating a single weight entry using a two-layer ReLU neural
network.

We highlight the differences between our setting and the setting in (Pensia et
al., 2020) in Figure 1. Let the target weight be denoted by $w$. For each
input value $x$, passing through this weight entry gives an output $w\cdot x$.

The scheme considered by (Pensia et al., 2020) is represented in the upper
half of the figure, denoted by “Strong LTH”. In particular, they start with a
random two-layer ReLU activated neural network, and performs pruning by
applying mask $\mathbf{s}$ to the first layer111Applying mask to the second
layer weights achieves the same effect. weight $\mathbf{u}$ and arrives at
$\mathbf{s}\odot\mathbf{u}$. By choosing an optimal mask $\mathbf{s}$, for any
input $x$, they consider the output of the pruned network
$\mathbf{v}^{\top}\sigma\left(\mathbf{s}\odot\mathbf{u}x\right)$ as an
approximation of $w\cdot x$.

Our scheme is described in the lower half of the figure, denoted by “Strong
LTH with Perturbation”. Different from “Strong LTH”, we also apply changes to
the second layer weight $\mathbf{v}$ by adding a perturbation vector
$\mathbf{y}\in[-\varepsilon,\varepsilon]^{n}$ to it while performing the
pruning. With an optimal mask $\mathbf{s}$ and perturbation vector
$\mathbf{y}$, we consider
$\left(\mathbf{v}+\mathbf{y}\right)^{\top}\sigma\left(\mathbf{s}\odot\mathbf{u}x\right)$
as an approximation of $w\cdot x$. As a result of this difference, our scheme
potentially requires a smaller over-parameterization. In the lemma below, we
show that the over-parameterization in our setting enjoys a monotonic
decrease, as we increase $\varepsilon$.

######  Lemma 1.

Let $g:{\mathbb{R}}\rightarrow{\mathbb{R}}$ be a randomly initialized network
of the form $g(x)=\mathbb{v}^{\top}\sigma(\mathbb{u}x)$, where
$\mathbb{v},\mathbb{u}\in{\mathbb{R}}^{2n}$, $n=K_{1}+K_{2}$ with

$\displaystyle K_{1}$ $\displaystyle\geq
C_{1}\left(\frac{\log(\eta^{-1})}{\log(\frac{5}{4}+\frac{\varepsilon}{2})}\right);K_{2}\geq
C_{2}\left(\frac{\log(\eta^{-1}))}{1+\varepsilon}\right),$

where $u_{i}=1$ for $i\leq n$, $u_{i}=-1$ for $i\geq n+1$, and
$v_{i}^{\prime}s$ are drawn from $\texttt{Unif}[-1,1]$. Then there exist
$\mathbb{s}\in\\{0,1\\}^{2n},\mathbb{y}\in[-\varepsilon,+\varepsilon]^{2n}$
such that

$\displaystyle\sup_{x:|x|\leq
1}\left|wx-(\mathbb{v}+\mathbb{y})^{\top}\sigma((\mathbb{u}\odot\mathbb{s})x)\right|<\eta,\vspace{-0.7cm}$

with probability at least $1-\delta$ for all $w\in[-\frac{1}{2},\frac{1}{2}]$,
with

$\displaystyle\delta=\exp\left(-\tfrac{K_{2}(1+\varepsilon)^{2}}{8(3-\varepsilon)^{2}}\right)+\exp\left(-\tfrac{K_{1}}{18}\right)+$
$\displaystyle\exp\left(-\max\\{\varepsilon,\eta\\}K_{1}\right)$

###### Sketch of the Proof.

We defer the detailed proof to the appendix and sketch the proof here. Similar
to (Pensia et al., 2020), we decompose $wx$ into $wx=\sigma(wx)-\sigma(-wx)$.
By our construction, the first half of the entries in $\mathbf{u}$ are $1$ and
the second half are $-1$. Therefore, we decompose
$\mathbb{u},\mathbb{v},\mathbb{y},\mathbb{s}$ by

$\displaystyle\mathbb{u}=\begin{pmatrix}\mathbb{u}_{1}\\\
\mathbb{u}_{2}\end{pmatrix},\mathbb{v}=\begin{pmatrix}\mathbb{v}_{1}\\\
\mathbb{v}_{2}\end{pmatrix},\mathbb{s}=\begin{pmatrix}\mathbb{s}_{1}\\\
\mathbb{s}_{2}\end{pmatrix},\mathbb{y}=\begin{pmatrix}\mathbb{y}_{1}\\\
\mathbb{y}_{2}\end{pmatrix},$

where
$\mathbf{u}_{1}=\mathbb{1}_{n},\mathbf{u}_{2}=\mathbb{-1}_{n},\mathbf{v}_{1},\mathbf{v}_{2}\in{\mathbb{R}}^{n}$,
$\mathbf{s}_{1},\mathbf{s}_{2}\in\\{0,1\\}^{n}$, and
$\mathbf{y}_{1},\mathbf{y}_{2}\in[-\varepsilon,\varepsilon]^{n}$. This gives:

$\displaystyle(\mathbb{v}+\mathbb{y})^{\top}\sigma((\mathbb{u}\odot\mathbb{s})x)$
$\displaystyle=\underbrace{(\mathbb{v}_{1}+\mathbb{y}_{1})^{\top}\sigma((\mathbb{u}_{1}\odot\mathbb{s}_{1})x)}_{\tau_{1}}+$
$\displaystyle\underbrace{(\mathbb{v}_{2}+\mathbb{y}_{2})^{\top}\sigma((\mathbb{u}_{2}\odot\mathbb{s}_{2})x)}_{\tau_{2}}$

We then apply Theorem (3) twice: we first approximate $\sigma(wx)$ using
$\tau_{1}$ and then approximate $-\sigma(-wx)$ using $\tau_{2}$. Lastly, we
combine the two approximations and apply a union bound to complete the proof.
∎

Remark 3. Notice that the required number of hidden neurons (over-
parameterization) in Lemma (8) depends on $K_{1}$ and $K_{2}$, where $K_{1}$
scales inversely with
$\log\left(\nicefrac{{5}}{{4}}+\nicefrac{{\varepsilon}}{{2}}\right)$ and
$K_{2}$ scales inversely with $1+\varepsilon$. Therefore, both terms decreases
monotonically as $\varepsilon$ increases. In particular, when
$\varepsilon=O(\eta^{-1})$, both $K_{1}$ and $K_{2}$ reduce to a constant
term. This implies that, as long as the perturbation scale $\varepsilon$ is
large enough, a constant over-parameterization is able to approximate any
target weight arbitrarily well.

Remark 4. Another difference between Lemma (8) and Lemma 1 in (Pensia et al.,
2020) is that the latter assumes both $\mathbf{u}$ and $\mathbf{v}$ to be
randomly initialized, while we initialize $\mathbf{u}$ deterministically with
half $1$s and half $-1$s, and keep $\mathbf{v}$ to be randomly initialized.
Our initialization is only for the convenience of applying Theorem (3). Our
initialization is agnostic of the target weight $w$, so it does not alleviate
the difficulty of the approximation. Neither does it raise the difficulty,
since we can observe that, by setting $\varepsilon$ to zero, the requirement
on the over-parameterization reduces to $n=O\left(\log\eta^{-1}\right)$. This
is the same as Lemma 1 in (Pensia et al., 2020).

Lemma 8 highlights the idea of approximating a single weight entry by pruning
and perturbing a randomly initialized two-layer ReLU neural network. Next, we
extend this idea to the approximation of a deep neural network. The idea is to
approximate each layer in the target network using a two-layer ReLU MLP . Each
entry in the weight matrix of the target network is approximated by a
subnetwork of the MLP as in Lemma (8). Therefore, a concatenation of these
MLPs gives an approximation of the target network.

######  Theorem 2.

Consider approximating $f$ with $g$ as defined above. Assume that assumption
(3) holds. Also, assume that for $1\leq\ell\leq L$,

$\displaystyle K_{1}$
$\displaystyle=C_{1}d_{\ell-1}\left(\frac{\log\left(\frac{d_{\ell-1}d_{\ell}L}{\eta}\right)}{\log\left(\frac{5}{4}+\frac{\varepsilon}{2}\right)}\right);$
$\displaystyle K_{2}$
$\displaystyle=C_{2}d_{\ell-1}\left(\frac{\log\left(\frac{d_{\ell-1}d_{\ell}L}{\eta}\right)}{1+\varepsilon}\right)$
$\displaystyle\texttt{dim}(\mathbb{U}^{2\ell})=d_{\ell}\times\left(K_{1}+K_{2}\right),$
$\displaystyle\texttt{dim}(\mathbb{U}^{2\ell-1})=\left(K_{1}+K_{2}\right)\times
d_{\ell-1}.$

Then with probability at least $1-2d_{1}d_{2}L\delta$,

$\displaystyle\min_{\mathcal{S},\mathcal{Y}}\sup_{\mathbf{x}:\|\mathbf{x}\|_{\infty}\leq
1}\|f(\mathbf{x})-g_{\mathcal{S},\mathcal{Y}}\left(\mathbf{x}\right)\|<\eta,$

where $g_{\mathcal{S},\mathcal{Y}}$ is a pruning & $\varepsilon$-perturbation
of $g$, and

$\displaystyle\delta=\exp\left(-\tfrac{K_{2}(1+\varepsilon)^{2}}{8(3-\varepsilon)^{2}}\right)+\exp\left(-\tfrac{K_{1}}{18}\right)+$
$\displaystyle\exp\left(-\max\\{\varepsilon,\eta\\}K_{1}\right)$

###### Sketch of Proof.

We defer the detailed proof to the appendix and sketch the proof here. The
idea is the same as (Pensia et al., 2020): we approximate every entry in the
weight matrix in each layer of $f$ by applying lemma (8) up to some error. We
then notice that, given the assumption that
$\left\|\mathbf{W}^{\ell}\right\|\leq 1$, each layer in $f$ is $1$-Lipschitz.
Therefore, the corresponding approximation in $g_{\mathcal{S},\mathcal{Y}}$ is
also about $1$-Lipschitz. We use this Lipschitzness to control the error
during the forward propagation, and arrives at a bound on the error in
equation (5) ∎

Remark 5. Theorem (2) shows similar behavior with Lemma (8). The
overparameterization requirement depends on $K_{1}$ and $K_{2}$, both
decreasing monotonically as $\varepsilon$ increases. As long as
$\varepsilon=O\left(\max_{\ell\in[L]}\log\left(\nicefrac{{d_{\ell-1}d\ell
L}}{{\eta}}\right)\right)$, we only require the size of $g$ to be a constant
times the size of $f$ to arrive at an $\eta$-approximation of $f$. Moreover,
when $\varepsilon=0$, the required over-parameterization reduces to the same
form as in Theorem 1 of (Pensia et al., 2020).

##  6 Experiments

###  6.1 Approximating Neural Nets with SubsetSum and $\varepsilon$
Perturbation

We would like to see how the amount of weight perturbation affects the
required overparametrization. To explore this relationship, we approximate a
two-layer, $500$ hidden node target network $g$ by (Pensia et al., 2020). Each
weight was approximated using a subset sum of $n$ randomly initialized
candidates where each candidate was allowed to perturbed by at most
$\varepsilon$. In particular, for some given $(\varepsilon$, $\eta)$ and seed
$s$, we say $n\in\mathbb{N}$ satisfies the overparametrization requirement if:

$\displaystyle\forall w\in g,$
$\displaystyle~{}\exists\bm{\delta}\in\\{0,1\\}^{n},\bm{y}\in[-\varepsilon,\varepsilon]^{n}\text{
such that: }$
$\displaystyle\left|w-\sum_{i=1}^{n}\delta_{i}(x_{i}+y_{i})\right|\leq\eta,$
$\displaystyle x_{i}\sim\texttt{Unif}\left([l,u]\right)\forall i=1,...,n,$

where $l$ and $u$ are the bounds of weights $w$ in the target network,
$x_{i}$’s are generated randomly using seed $s$, and every set of $x_{i}$’s
are unique to $w$.

We randomly generate $10$ sets of $x_{i}$’s and record the minimum $n$ such
that $8$ of such sets leads to the required approximation error. We vary
$\eta$ from $10^{-2}$ to $10^{-4}$ and choose $\varepsilon$ such that
$\varepsilon/\eta$ varies between $0$ and $10$. Intuitively,
$\varepsilon/\eta$ gives the relative effectiveness of $\varepsilon$. With a
fixed $\varepsilon$, a smaller $\eta$ results in a larger $\varepsilon/\eta$,
and in the meantime makes the approximation easier. We are interested how such
$n$ changes as $\eta$ and $\varepsilon/\eta$ change. As $\varepsilon/\eta$
increase, we should expect a smaller size of the candidate set $n$.

This is indeed the case, since from Figure 2, we can observe that for fixed
$\eta$, $n$ decreases as $\varepsilon/\eta$ increases. More specifically, as
$\varepsilon$ increases, more changes in $\varepsilon$ are required to make a
decrease in the minimum over-parameterization requirement $n$, which coincides
with Theorem 3.

Figure 2: Change of the required size of the candidate set ($n$) v.s. relative
perturbation scale ($\nicefrac{{$\varepsilon$}}{{$\eta$}}$).

###  6.2 Perturbation Using Projected Gradient Descent

We would like to explore the relationship between the weight perturbation
achieved by (stochastic) gradient descent ((S)GD) and the desirable weight
perturbation for reducing the over-parameterization in the strong LTH
approximation. In particular, we hypothesize that

Weight perturbation using gradient-based methods constitutes a good solution
compared to the desirable perturbation $\bm{\delta}^{*}$ in Equation (3)

We propose a two-stage algorithm to validate this hypothesis. With a given
perturbation scale $\varepsilon$, we start with training an over-parameterized
neural network using projected gradient descent (PGD) to convergence. Note
that, by applying PGD, we guarantee that each value of the neural network
weight stays in an $\varepsilon$-neighborhood of initialization. This is
reflected in lines 3-5 in Algorithm 1: per iteration, we first complete a
regular (S)GD step (line 3), but we then truncate the updated value so that
every updated vaule lines in the interval $[-\varepsilon,\varepsilon]$ (line
4). We then apply the resulting update in line 5.

We run edge-popup (Ramanujan et al., 2019) for a range of pruning (sparsity)
levels (line 9 in Algorithm 1). This step is interpreted as applying a
standard pruning technique –initially designed to start from random
initialization, like edge-popup– but now on the perturbed initialization based
on PGD. We consider the best accuracy amongst all pruning levels (percentage
of weights pruned) to be the optimal approximation. We refer the readers to
Algorithm 1 for more detail. Here, $\min\\{\cdot\\}$ refers to the entrywise
minimum and $\text{abs}(\cdot)$ refers to the entrywise absolute value. Note
that, by applying the projection operation in line 4, we guarantee that
$\left\|\mathbf{W}_{t}-\mathbf{W}_{0}\right\|_{\max}\leq\varepsilon$ for all
$t\in[T]$.

Algorithm 1 PGD+StrongLTH

Input: Perturbation scale $\varepsilon$, neural network loss $\mathcal{L}$,
initial weight $\mathbf{W}_{0}$, learning rate $\\{\alpha_{t}\\}_{t=0}^{T-1}$

1:$\Delta\mathbf{W}\leftarrow 0$

2:for $t\in\\{0,\dots,T-1\\}$ do

3:
$\hat{\mathbf{W}}\leftarrow\Delta\mathbf{W}-\alpha_{t}\nabla\mathcal{L}(\mathbf{W}_{t})$

4:
$\Delta\mathbf{W}\leftarrow\texttt{sign}(\hat{\mathbf{W}})\cdot\min\\{\texttt{abs}(\hat{\mathbf{W}}),\varepsilon\\}$

5: $\mathbf{W}_{t+1}\leftarrow\mathbf{W}_{0}+\Delta\mathbf{W}$

6:end for

7:$\ell^{*}\leftarrow\infty\;,\mathcal{M}^{*}\leftarrow\text{None}$

8:for pruning level $s\in\\{0.1,0.2,\dots,0.9\\}$ do

9: $\ell,\mathcal{M}\leftarrow\texttt{Edge-
Popup}(\mathcal{L},\mathbf{W}_{T},s)$

10: if $\ell\leq\ell^{*}$ then

11: $\ell^{*}\leftarrow\ell\;,\mathcal{M}^{*}\leftarrow\mathcal{M}$

12: end if

13:end for

14:return Optimal loss $\ell^{*}$, mask $\mathbf{M}^{*}$ and sparsity level
$s$

Figure 3: Test accuracy for different pruning level $s$ and perturbation scale
$\varepsilon$. For each different perturbation scale (each column), the
highest accuracy is marked bold.

We train a four-layer multi-layer perceptron (MLP) on the MNIST dataset, with
each layer having $500$ hidden nodes. We use Algorithm 1 to train the network:
we use a learning rate of $0.03$ for PGD and train the network for $100$
epochs; for pruning we use edge-popup with a learning rate of $0.1$ and train
the network for $50$ epochs with cosine annealing. All weights in the network
are initialized from
$\texttt{Unif}\left([-\nicefrac{{1}}{{2}},\nicefrac{{1}}{{2}}]\right)$, and
$\varepsilon$ ranges from $0$ to $0.4$. The results are shown in Table 3 and
Figure 4.

(a)

(b)

Figure 4: Relationship between perturbation scale $\varepsilon$, optimal
sparsity $s^{\star}$ and the final accuracy. (a): best pruned accuracy across
different pruning level on the pruned network versus the perturbation scale.
(b): optimal sparsity in pruning versus the perturbation scale.

Figure 4 plots the relationship between the best accuracy among all sparsity
(pruning) levels and the perturbation scale Figure 4(a), as well as the
sparsity (pruning) level that achieves the best accuracy versus the
perturbation scale Figure 4(b). First, in Figure 4(a), one could see that as
the perturbation scale increases–where SGD has a larger freedom to find
optimize the parameters–the pruned accuracy increases. This observation
corroborates our hypothesis that SGD finds a good weight perturbation that
facilitate the pruning process. Figure 4(b) provides more insight into this
behavior: as the perturbation scale increases, the sparsity level that
achieves the best accuracy decreases, meaning that the best pruning will prune
a smaller number of weights. This is because as the perturbation scales
increases, weights learned by SGD are introduced with a dependence on each
other. Such dependence becomes stronger as the perturbation scale increases,
and will be interrupted by pruning a large number of weights.

Figure 3 gives a more detailed description of the results. In particular, the
best accuracy across all sparsity (pruning) levels for each perturbation scale
$\varepsilon$ is marked bold. In addition, we use different colors to mark
different behaviors our experiment demonstrate when varying $s$ and
$\varepsilon$. To be more specific, the region marked red represents the
behavior studied by the original strong LTH (Pensia et al., 2020), where no
perturbation is allowed ($\varepsilon=0$). In this case, the optimal accuracy
is achieved at a non-trival pruning level ($\sim$0.5). The region marked
purple represents standard training of neural network with different extent of
training. As $\varepsilon$ increases (more training allowed), the accuracy
also increases (higher $\varepsilon$ values allowed).

Finally, the orange region marks the scenario where the behavior is dominated
by SGD. In this region, the large perturbation scale allows SGD to establish a
strong dependence between the weight entries, such that any pruning will break
this dependence and result in a decrease in the accuracy. In particular, the
lowest accuracy (marked by dark orange) appears when we allow largest extend
of training, while enforcing the largest pruning level.

##  7 Concluding Remarks

Our work serves as a further step into understanding how the pre-training
process affects the accuracy of neural network pruning. We generalized the
weight change in the training process to some $\varepsilon$-perturbation
around the initialization, and provide theoretical guarantee to a more general
version of the strong Lottery Ticket Hypothesis (Ramanujan et al., 2019;
Pensia et al., 2020; Malach et al., 2020) by introducing the freedom of
$\varepsilon$-perturbation into the pruning process. We establish the
relationship between the perturbation scale $\varepsilon$ and the over-
parameterization requirement of the candidate network. As an intermediate step
of our analysis, we also provide the theoretical guarantee of a generalized
version of the subset sum problem (Lueker, 1998).

Moreover, we explored through experiments whether SGD could find a good
perturbation. By testing the a combination of the $\varepsilon$-bounded
projected gradient descent and the edge-popup algorithm, we give a positive
answer to the question above. We also observed that, as the perturbation scale
increases, the optimal accuracy of the pruned network appears at a lower
pruning level.

As a next step of our work, one could be interested in exploring the
theoretical guarantee for SGD’s property of finding a good perturbation. An
interesting starting point is the approximation of a weight vector
$\mathbf{w}$: given a set of input data points
$\\{\mathbf{x}_{i}\\}_{i=1}^{m}$, whether solving the optimization problem of
$\min_{\mathbf{U}}\sum_{i=1}^{m}\left\|\bm{1}^{\top}\mathbf{U}\mathbf{x}_{i}-\mathbf{w}^{\top}\mathbf{x}_{i}\right\|_{2}^{2}$
using gradient descent

$\displaystyle\mathbf{U}_{t+1}=\mathbf{U}_{t}-\alpha\frac{\partial}{\partial\mathbf{U}}\sum_{i=1}^{m}\left\|\bm{1}^{\top}\mathbf{U}_{t}\mathbf{x}_{i}-\mathbf{w}^{\top}\mathbf{x}_{i}\right\|_{2}^{2}$

will satisfy the descending property

$\displaystyle\left\|\mathbf{w}-\left(\mathbf{U}_{t+1}\odot\mathbf{S}_{t+1}\right)^{\top}\bm{1}\right\|_{2}<\left\|\mathbf{w}-\left(\mathbf{U}_{t}\odot\mathbf{S}_{t}\right)^{\top}\bm{1}\right\|_{2},$

where $\mathbf{S}_{t}$ is the optimal mask in iteration $t$

$\displaystyle\mathbf{S}_{t}=\text{argmin}_{\mathbf{S}}\left\|\mathbf{w}-\left(\mathbf{U}_{t}\odot\mathbf{S}\right)^{\top}\bm{1}\right\|_{2}.$

A theoretical analysis on this problem will derive a further connection
between the pre-training and the pruning process, and will potentially be an
important step in understanding the mystery of the Lottery Ticket Hypothesis.

## References

  * Blalock et al. (2020) Davis Blalock, Jose Javier Gonzalez Ortiz, Jonathan Frankle, and John Guttag.  What is the state of neural network pruning?, 2020.  URL https://arxiv.org/abs/2003.03033.
  * Burkholz (2022) Rebekka Burkholz.  Convolutional and residual networks provably contain lottery tickets.  In Kamalika Chaudhuri, Stefanie Jegelka, Le Song, Csaba Szepesvari, Gang Niu, and Sivan Sabato, editors, _Proceedings of the 39th International Conference on Machine Learning_ , volume 162 of _Proceedings of Machine Learning Research_ , pages 2414–2433. PMLR, 17–23 Jul 2022.  URL https://proceedings.mlr.press/v162/burkholz22a.html.
  * Burkholz et al. (2022) Rebekka Burkholz, Nilanjana Laha, Rajarshi Mukherjee, and Alkis Gotovos.  On the existence of universal lottery tickets.  In _International Conference on Learning Representations_ , 2022.  URL https://openreview.net/forum?id=SYB4WrJql1n.
  * Chijiwa et al. (2021) Daiki Chijiwa, Shin’ya Yamaguchi, Yasutoshi Ida, Kenji Umakoshi, and Tomohiro INOUE.  Pruning randomly initialized neural networks with iterative randomization.  In A. Beygelzimer, Y. Dauphin, P. Liang, and J. Wortman Vaughan, editors, _Advances in Neural Information Processing Systems_ , 2021.  URL https://openreview.net/forum?id=QCPY2eMXYs.
  * da Cunha et al. (2022a) Arthur da Cunha, Francesco d’Amore, Frédéric Giroire, Hicham Lesfari, Emanuele Natale, and Laurent Viennot.  Revisiting the random subset sum problem, 2022a.  URL https://arxiv.org/abs/2204.13929.
  * da Cunha et al. (2022b) Arthur da Cunha, Emanuele Natale, and Laurent Viennot.  Proving the lottery ticket hypothesis for convolutional neural networks.  In _International Conference on Learning Representations_ , 2022b.  URL https://openreview.net/forum?id=Vjki79-619-.
  * Evci et al. (2022) Utku Evci, Yani Ioannou, Cem Keskin, and Yann Dauphin.  Gradient flow in sparse neural networks and how lottery tickets win.  _Proceedings of the AAAI Conference on Artificial Intelligence_ , 36(6):6577–6586, Jun. 2022.  doi: 10.1609/aaai.v36i6.20611.  URL https://ojs.aaai.org/index.php/AAAI/article/view/20611.
  * Frankle and Carbin (2019) Jonathan Frankle and Michael Carbin.  The lottery ticket hypothesis: Finding sparse, trainable neural networks.  In _International Conference on Learning Representations_ , 2019.  URL https://openreview.net/forum?id=rJl-b3RcF7.
  * Frankle et al. (2019) Jonathan Frankle, Gintare Karolina Dziugaite, Daniel M. Roy, and Michael Carbin.  Stabilizing the lottery ticket hypothesis, 2019.  URL https://arxiv.org/abs/1903.01611.
  * Han et al. (2015) Song Han, Jeff Pool, John Tran, and William J. Dally.  Learning both weights and connections for efficient neural networks, 2015\.  URL https://arxiv.org/abs/1506.02626.
  * He et al. (2017) Yihui He, Xiangyu Zhang, and Jian Sun.  Channel pruning for accelerating very deep neural networks, 2017.  URL https://arxiv.org/abs/1707.06168.
  * Lange (2020) Robert Tjarko Lange.  The lottery ticket hypothesis: A survey.  _https://roberttlange.github.io/year-archive/posts/2020/06/lottery-ticket-hypothesis/_ , 2020\.  URL https://roberttlange.github.io/posts/2020/06/lottery-ticket-hypothesis/.
  * Lee et al. (2018) Namhoon Lee, Thalaiyasingam Ajanthan, and Philip H. S. Torr.  Snip: Single-shot network pruning based on connection sensitivity, 2018\.  URL https://arxiv.org/abs/1810.02340.
  * Li et al. (2016) Hao Li, Asim Kadav, Igor Durdanovic, Hanan Samet, and Hans Peter Graf.  Pruning filters for efficient convnets, 2016.  URL https://arxiv.org/abs/1608.08710.
  * Lueker (1998) George S. Lueker.  Exponentially small bounds on the expected optimum of the partition and subset sum problems.  _Random Structures & Algorithms_, 12(1):51–62, 1998.  doi: https://doi.org/10.1002/(SICI)1098-2418(199801)12:1¡51::AID-RSA3¿3.0.CO;2-S.  URL https://onlinelibrary.wiley.com/doi/abs/10.1002/%28SICI%291098-2418%28199801%2912%3A1%3C51%3A%3AAID-RSA3%3E3.0.CO%3B2-S.
  * Malach et al. (2020) Eran Malach, Gilad Yehudai, Shai Shalev-Schwartz, and Ohad Shamir.  Proving the lottery ticket hypothesis: Pruning is all you need.  In Hal Daumé III and Aarti Singh, editors, _Proceedings of the 37th International Conference on Machine Learning_ , volume 119 of _Proceedings of Machine Learning Research_ , pages 6682–6691. PMLR, 13–18 Jul 2020.  URL https://proceedings.mlr.press/v119/malach20a.html.
  * Orseau et al. (2020) Laurent Orseau, Marcus Hutter, and Omar Rivasplata.  Logarithmic pruning is all you need.  In H. Larochelle, M. Ranzato, R. Hadsell, M.F. Balcan, and H. Lin, editors, _Advances in Neural Information Processing Systems_ , volume 33, pages 2925–2934. Curran Associates, Inc., 2020.  URL https://proceedings.neurips.cc/paper/2020/file/1e9491470749d5b0e361ce4f0b24d037-Paper.pdf.
  * Patil and Dovrolis (2020) Shreyas Malakarjun Patil and Constantine Dovrolis.  Phew: Constructing sparse networks that learn fast and generalize well without training data, 2020.  URL https://arxiv.org/abs/2010.11354.
  * Pensia et al. (2020) Ankit Pensia, Shashank Rajput, Alliot Nagle, Harit Vishwakarma, and Dimitris Papailiopoulos.  _Optimal Lottery Tickets via SUBSETSUM: Logarithmic over-Parameterization is Sufficient_.  Curran Associates Inc., Red Hook, NY, USA, 2020.  ISBN 9781713829546.
  * Ramanujan et al. (2019) Vivek Ramanujan, Mitchell Wortsman, Aniruddha Kembhavi, Ali Farhadi, and Mohammad Rastegari.  What’s hidden in a randomly weighted neural network?, 2019.  URL https://arxiv.org/abs/1911.13299.
  * Sabatelli et al. (2020) Matthia Sabatelli, Mike Kestemont, and Pierre Geurts.  On the transferability of winning tickets in non-natural image datasets, 2020.  URL https://arxiv.org/abs/2005.05232.
  * Tanaka et al. (2020) Hidenori Tanaka, Daniel Kunin, Daniel L. K. Yamins, and Surya Ganguli.  Pruning neural networks without any data by iteratively conserving synaptic flow.  2020\.  doi: 10.48550/ARXIV.2006.05467.  URL https://arxiv.org/abs/2006.05467.
  * Wang et al. (2020) Chaoqi Wang, Guodong Zhang, and Roger Grosse.  Picking winning tickets before training by preserving gradient flow.  In _International Conference on Learning Representations_ , 2020.  URL https://openreview.net/forum?id=SkgsACVKPH.
  * Wang et al. (2019) Yulong Wang, Xiaolu Zhang, Lingxi Xie, Jun Zhou, Hang Su, Bo Zhang, and Xiaolin Hu.  Pruning from scratch, 2019.  URL https://arxiv.org/abs/1909.12579.
  * Wen et al. (2016) Wei Wen, Chunpeng Wu, Yandan Wang, Yiran Chen, and Hai Li.  Learning structured sparsity in deep neural networks, 2016.  URL https://arxiv.org/abs/1608.03665.
  * Wolfe et al. (2021) Cameron R. Wolfe, Qihan Wang, Junhyung Lyle Kim, and Anastasios Kyrillidis.  How much pre-training is enough to discover a good subnetwork?, 2021.  URL https://arxiv.org/abs/2108.00259.
  * You et al. (2019) Haoran You, Chaojian Li, Pengfei Xu, Yonggan Fu, Yue Wang, Xiaohan Chen, Richard G. Baraniuk, Zhangyang Wang, and Yingyan Lin.  Drawing early-bird tickets: Towards more efficient training of deep networks, 2019.  URL https://arxiv.org/abs/1909.11957.
  * Yu et al. (2019) Haonan Yu, Sergey Edunov, Yuandong Tian, and Ari S. Morcos.  Playing the lottery with rewards and multiple languages: lottery tickets in rl and nlp, 2019.  URL https://arxiv.org/abs/1906.02768.
  * Zhang et al. (2021) Shuai Zhang, Meng Wang, Sijia Liu, Pin-Yu Chen, and Jinjun Xiong.  Why lottery ticket wins? a theoretical perspective of sample complexity on sparse neural networks.  In M. Ranzato, A. Beygelzimer, Y. Dauphin, P.S. Liang, and J. Wortman Vaughan, editors, _Advances in Neural Information Processing Systems_ , volume 34, pages 2707–2720. Curran Associates, Inc., 2021.  URL https://proceedings.neurips.cc/paper/2021/file/15f99f2165aa8c86c9dface16fefd281-Paper.pdf.
  * Zhou et al. (2019) Hattie Zhou, Janice Lan, Rosanne Liu, and Jason Yosinski.  Deconstructing lottery tickets: Zeros, signs, and the supermask.  In H. Wallach, H. Larochelle, A. Beygelzimer, F. d'Alché-Buc, E. Fox, and R. Garnett, editors, _Advances in Neural Information Processing Systems_ , volume 32. Curran Associates, Inc., 2019.  URL https://proceedings.neurips.cc/paper/2019/file/1113d7a76ffceca1bb350bfe145467c6-Paper.pdf.
  * Zhu and Gupta (2017) Michael Zhu and Suyog Gupta.  To prune, or not to prune: exploring the efficacy of pruning for model compression, 2017.  URL https://arxiv.org/abs/1710.01878.

##  Appendix A Proof of Theorem 1

The subset sum problem considers finding $\bm{s}\in\\{0,1\\}^{n}$ that
minimizes $\ell(z,\bm{s})=|z-\sum_{i=1}^{n}s_{i}x_{i}|$ for a given $z$ and
given $x_{i}$’s. Previous work finds that, with
$n=\Omega(\log\nicefrac{{1}}{{\eta}})$, it holds with high probability that
there exists $\bm{s}\in\\{0,1\\}^{n}$ such that $\ell(z,\bm{s})\leq\eta$.
Alternatively, this problem can be started as finding the smallest $n$ such
that $\eta^{*}\leq\eta$ with

$\displaystyle\eta^{*}=\min_{\bm{s}\in\\{0,1\\}^{n}}\ell(z,\bm{s})$

In our case, we would like to give the freedom of each $x_{i}$ to be perturbed
for a small degree $\varepsilon$. In particular, we extend the definition of
$\ell$ to

$\displaystyle\ell(z,\bm{s},\mathbf{y})=\left|z-\sum_{i=1}^{n}s_{i}(x_{i}+y_{i})\right|$

and seeks condition of $n$ such that $\eta^{*}\leq\eta$ with

$\displaystyle\eta^{*}=\min_{\bm{s}\in\\{0,1\\}^{n},\mathbf{y}\in[-\varepsilon,\varepsilon]^{n}}\ell(z,\bm{s},\mathbf{y})$
(4)

If this condition is met for a fixed $z$, we say that such $z$ has an $\eta$
approximation.

######  Assumption 2.

Let the candidate values $x_{i}\sim\texttt{Unif}\left([-1,1]\right)$ for all
$i\in[n]$, and the target value
$z\in[-\nicefrac{{1}}{{2}},\nicefrac{{1}}{{2}}]$. Let
$0\leq\varepsilon\leq\eta\leq 1$ be given.

Notice that if $\varepsilon>1$, then by Hoeffding’s inequality,

$\displaystyle\mathbb{P}\left(\left|\sum_{i=1}^{n}x_{i}\right|\geq\frac{n\varepsilon}{2}\right)\leq\exp\left(-\frac{n\varepsilon^{2}}{2}\right)$

When $\left|\sum_{i=1}^{n}x_{i}\right|\leq\frac{n\varepsilon}{2}$ holds, we
have that $\left|\sum_{i=1}^{n}(x_{i}+y_{i})\right|$ can be anything in
$[-\nicefrac{{n\varepsilon}}{{2}},\nicefrac{{n\varepsilon}}{{2}}]$ by varing
$y_{i}$. Therefore, as long as $n=\frac{1}{\varepsilon^{2}}\log s^{-1}$, it
holds with probability at least $1-s$ that $\eta^{*}=0$ for all
$z\in[-\nicefrac{{1}}{{2}},\nicefrac{{1}}{{2}}]$. Thus, our focus is on the
case of $\varepsilon\leq 1$. Under this assumption, we attempts to prove the
following theorem

######  Theorem 3.

Let the number of candidates satisfy $n=K_{1}+K_{2}$ with

$\displaystyle
K_{1}=O\left(\frac{\log\eta^{-1}}{\log\left(\frac{5}{4}+\frac{\varepsilon}{2}\right)}\right)\quad;K_{2}=O\left(1+\frac{\log\eta^{-1}}{(1+\varepsilon)}\right)$

Then with probability at least
$1-\exp\left(-\frac{K_{2}(1+\varepsilon)^{2}}{8(3-\varepsilon)^{2}}\right)-\exp\left(-\frac{K_{1}}{18}\right)-\exp\left(-\max\\{\varepsilon,\eta\\}K_{1}\right)$
we have that all $z\in[-\nicefrac{{1}}{{2}},\nicefrac{{1}}{{2}}]$ has a
$2\eta$-approximation.

We define the indicator function for the existence of
$\hat{\eta}$-approximation within the first $k$ candidate.

$\displaystyle f_{k,\hat{\eta}}(z)=\mathbb{I}\left\\{\exists
s\in\\{0,1\\}^{k},y\in[-\varepsilon,\varepsilon]^{k}\text{ s.t.
}\left|\sum_{i=1}^{k}s_{i}(x_{i}+y_{i})-z\right|\leq\hat{\eta}\right\\}$

This indicator function has the following recurrence

$\displaystyle f_{0,\eta}=\mathbb{I}\left\\{|z|\leq\eta\right\\};\quad
f_{k+1,\eta}=f_{k,\eta}(z)+\left(1-f_{k,\eta}(z)\right)f_{k,\eta+\varepsilon}(z-x_{k+1})$

Define the following random variable (depending on $\\{x_{k}\\}_{i=1}^{k}$)

$\displaystyle
p_{k}=\int_{-\nicefrac{{1}}{{2}}}^{\nicefrac{{1}}{{2}}}f_{k,\eta}(z)dz$

This random variable denotes the portion of
$z\in[-\nicefrac{{1}}{{2}},\nicefrac{{1}}{{2}}]$ that can be approximated
within $\eta$ error.

######  Definition 1.

For a candidate set $\\{x_{i}\\}_{i=1}^{n}$, and some $k\in\\{0\\}\cup[n]$,
define its $(k,\eta)$-feasible set as

$\displaystyle\mathcal{F}_{k,\eta}=\left\\{z\in\left[-\nicefrac{{1}}{{2}},\nicefrac{{1}}{{2}}\right]:\exists
s\in\\{0,1\\}^{k}\text{ s.t.
}\left|\sum_{i=1}^{k}s_{i}x_{i}-z\right|\leq\hat{\eta}\right\\}$

By definition, $\mathcal{F}_{k,\eta}$ is the union of finitely many mutually
disjoint closed intervals on
$\left[-\nicefrac{{1}}{{2}},\nicefrac{{1}}{{2}}\right]$. Let $\mu$ denote the
Lebesgue measure on $\mathbb{R}$. Consider the following definition of
$\varepsilon$-extension of a set

######  Definition 2.

Let $I\subset[-\nicefrac{{1}}{{2}},\nicefrac{{1}}{{2}}]$ be a closed interval.
A set $S$ is called an $\varepsilon$-extension of I, denoted
$S\in\Xi_{\varepsilon}(I)$ if

  1. 1.

$S\subseteq[-\nicefrac{{1}}{{2}},\nicefrac{{1}}{{2}}]\setminus I$

  2. 2.

for all $s\in S$, we have that $\min_{a\in I}|s-a|\leq\varepsilon$

  3. 3.

$\mu(S)=\min\left\\{\varepsilon,1-\mu(I)\right\\}$

By definition, for each $I\subset[-\nicefrac{{1}}{{2}},\nicefrac{{1}}{{2}}]$,
there is at least one $\varepsilon$-extension of $I$, since we can choose

$\displaystyle
S=[-\nicefrac{{1}}{{2}},\nicefrac{{1}}{{2}}]\cup\begin{cases}[-\nicefrac{{1}}{{2}},\inf
I)\cup(\sup I,\sup I-\inf I+\varepsilon-\nicefrac{{1}}{{2}}]&\text{ if }\inf
I\leq\varepsilon-\frac{1}{2}\\\ [\inf I-\varepsilon,\inf I)&\text{
otherwise}\end{cases}$

Let $\mathcal{F}=\cup_{j=1}^{m}I_{j}$ be a finite union of closed intervals. A
set $S$ is called an $\varepsilon$-extension of $\mathcal{F}$, denoted by
$S\in\Xi_{\varepsilon}(\mathcal{F})$ if

  1. 1.

$S\subseteq\cup_{j=1}^{m}\cup_{\xi_{j}\in\Xi_{\varepsilon}(I_{j})}\xi_{j}\setminus\mathcal{F}$

  2. 2.

$\mu(S)=\min\\{\varepsilon,1-\mu(\mathcal{F})\\}$

By lemma 2, there is at least one $\varepsilon$-extension of $\mathcal{F}$.

######  Lemma 2.

There is at least one $\varepsilon$-extension for each $\mathcal{F}$ of the
form $\mathcal{F}=\cup_{j=1}^{m}I_{j}$.

###### Proof.

Suppose there is no $\varepsilon$-extension of some
$\mathcal{F}=\cup_{j=1}^{m}I_{j}$. Consider two cases:

Case 1: $\mu\left(\mathcal{F}\right)\geq 1-\varepsilon$. Since $\mathcal{F}$
has no $\varepsilon$-extension, there must be a subset $A$ of
$[-\nicefrac{{1}}{{2}},\nicefrac{{1}}{{2}}]$ with nonzero Lebesgue measure
such that every element in $A$ is at least $\varepsilon$ away from
$\mathcal{F}$. This is, however, a contradiction, since by
$\mu(\mathcal{F})\geq 1-\varepsilon$, every point in
$[-\nicefrac{{1}}{{2}},\nicefrac{{1}}{{2}}]$ must be within $\varepsilon$
distance of $\mathcal{F}$.

Case 2: $\mu\left(\mathcal{F}\right)\leq 1-\varepsilon$. Let
$S=\cup_{j=1}^{m}\cup_{\xi_{j}\in\Xi_{\varepsilon}(I_{j})}\xi_{j}$. Since
$\mathcal{F}$ has no $\varepsilon$-extension, we must have $\mu(S)<1$. This
implies that there exist $a\in[-\nicefrac{{1}}{{2}},\nicefrac{{1}}{{2}}]$ such
that $a\notin S$. Thus $\inf_{a^{\prime}\in\mathcal{F}}|a-a^{\prime}|\geq f$.
Let such $a^{\prime}$ be given, then if $a>a^{\prime}$,
$(a^{\prime},a^{\prime}+\varepsilon]$ is an $\varepsilon$-extension, and if
$a<a^{\prime}$, $[a^{\prime}-\varepsilon,a^{\prime})$ is an
$\varepsilon$-extension. This is a contradiction. ∎

Let $\\{S_{k}\\}_{k=0}^{n}$ be given such that
$S_{k}\in\Xi_{\varepsilon}\left(\mathcal{F}_{k,\eta}\right)$. Moreover, let
$g_{k}(z)=\mathbb{I}\left\\{z\in S_{k}\right\\}$. We define another recurrence
of indicator function

$\displaystyle\hat{f}_{k+1}(z)=\hat{f}_{k}(z)+\left(1-\hat{f}_{k}(z)\right)\left(\hat{f}_{k}(z-x_{k+1})+g_{k}(z-x_{k+1})\right);\quad\hat{f}_{0}(z)=f_{0,\eta}(z)$

######  Lemma 3.

The sequence $\left\\{\hat{f}_{k}\right\\}_{k=0}^{n}$ satisfies
$\hat{f}_{k}(z)\leq f_{k,\eta}(z)$ for all
$z\in\left[-\nicefrac{{1}}{{2}},\nicefrac{{1}}{{2}}\right]$.

###### Proof.

We show this by induction. For $k=0$, we have $\hat{f}_{0}(z)=f_{0,\eta}(z)$
by definition. Assume $\hat{f}_{k}(z)\leq f_{k,\eta}(z)$, we would like to
show $\hat{f}_{k+1}(z)\leq f_{k+1,\eta}(z)$. To do this, we first notice that,
by definition of $g_{k}$

$\displaystyle
f_{k,\eta+\varepsilon}\left(z\right)=f_{k,\eta}\left(z\right)+(1-f_{k,\eta}\left(z\right))\mathbb{I}\left\\{z\in\cup_{\xi_{k}\in\Xi_{\varepsilon}(\mathcal{F}_{k,\eta})}\right\\}\geq
f_{k,\eta}\left(z\right)+(1-f_{k,\eta}\left(z\right))g_{k}(z)$

Moreover, if $g_{k}(z)=1$, we must have $f_{k,\eta}(z)=0$. Therefore
$(1-f_{k,\eta}\left(z\right))g_{k}(z)=g_{k}(z)$. This implies that

$\displaystyle 1\geq f_{k,\eta+\varepsilon}\left(z\right)\geq
f_{k,\eta}\left(z\right)+g_{k}(z)\geq\hat{f}_{k}(z)+g_{k}(z)$

Using this, we have

$\displaystyle f_{k+1,\eta}(z)$
$\displaystyle=f_{k,\eta}(z)+(1-f_{k,\eta}(z))f_{k,\eta+\varepsilon}(z-x_{k+1})$
$\displaystyle\geq
f_{k,\eta}(z)+(1-f_{k,\eta}(z))\left(\hat{f}_{k}(z-x_{k+1})+g_{k}(z-x_{k+1})\right)$
$\displaystyle=\left(\hat{f}_{k}(z-x_{k+1})+g_{k}(z-x_{k+1})\right)+\left(1-\hat{f}_{k}(z-x_{k+1})-g_{k}(z-x_{k+1})\right)f_{k,\eta}(z)$
$\displaystyle\geq\left(\hat{f}_{k}(z-x_{k+1})+g_{k}(z-x_{k+1})\right)+\left(1-\hat{f}_{k}(z-x_{k+1})-g_{k}(z-x_{k+1})\right)\hat{f}_{k}(z)$
$\displaystyle=\hat{f}_{k}(z)+\left(1-\hat{f}_{k}(z)\right)\left(\hat{f}_{k}(z-x_{k+1})+g_{k}(z-x_{k+1})\right)$
$\displaystyle=\hat{f}_{k+1}(z)$

This completes the proof. ∎

Based on the definition of $\left\\{\hat{f}_{k}\right\\}_{k=0}^{n}$, we define
$\left\\{\tilde{p}_{k}\right\\}_{k=0}^{n}$ as

$\displaystyle\tilde{p}_{k}=\int_{-\nicefrac{{1}}{{2}}}^{\nicefrac{{1}}{{2}}}\hat{f}_{k}(z)dz$

Then by definition we have $\tilde{p}_{k}\leq p_{k}$, with
$\tilde{p}_{0}=p_{0}$. Moreover, we have

$\displaystyle\tilde{p}_{k+1}$
$\displaystyle=\int_{-\nicefrac{{1}}{{2}}}^{\nicefrac{{1}}{{2}}}\left(\hat{f}_{k}(z)+\left(1-\hat{f}_{k}(z)\right)\left(\hat{f}_{k}(z-x_{k+1})+g_{k}(z-x_{k+1})\right)\right)dz$
$\displaystyle\leq\tilde{p}_{k}+\int_{-\nicefrac{{1}}{{2}}}^{\nicefrac{{1}}{{2}}}\left(\hat{f}_{k}(z-x_{k+1})+g_{k}(z-x_{k+1})\right)dz$
$\displaystyle\leq\tilde{p}_{k}+\int_{-\nicefrac{{1}}{{2}}}^{\nicefrac{{1}}{{2}}}\left(\hat{f}_{k}(u)+g_{k}(u)\right)du$
$\displaystyle=2\tilde{p}_{k}+\mu(S_{k})$ $\displaystyle\leq
2\tilde{p}_{k}+\varepsilon$

Furthermore, by definition of $\tilde{p}_{k+1}$, we have $\tilde{p}_{k+1}\leq
1$. For $\tilde{p}_{k}$, we can compute its expectation with respect to
$\\{x_{i}\\}_{i=1}^{k}$ as

$\displaystyle\mathbb{E}\left[\tilde{p}_{k+1}\right]$
$\displaystyle=\tilde{p}_{k}+\frac{1}{2}\int_{-1}^{1}\int_{-\nicefrac{{1}}{{2}}}^{\nicefrac{{1}}{{2}}}\left(1-\hat{f}_{k}(z)\right)\left(\hat{f}_{k}(z-x)+g_{k}(z-x)\right)dzdx$
$\displaystyle=\tilde{p}_{k}+\frac{1}{2}\int_{-\nicefrac{{1}}{{2}}}^{\nicefrac{{1}}{{2}}}\left(1-\hat{f}_{k}(z)\right)dz\int_{-1}^{1}\left(\hat{f}_{k}(u)+g_{k}(u)\right)du$
$\displaystyle=\tilde{p}_{k}+\frac{1}{2}(1-\tilde{p}_{k})(\tilde{p}_{k}+\mu(S_{k}))$
$\displaystyle=\tilde{p}_{k}+\frac{1}{2}(1-\tilde{p}_{k})\min\left\\{1,\tilde{p}_{k}+\varepsilon\right\\}$

###  A.1 Growth up to $\nicefrac{{1}}{{4}}$

We define $K_{1}$ as below

$\displaystyle K_{1}=\begin{cases}\min\left\\{k\geq
0:p_{k}>\frac{1}{4}\right\\}&\text{ if }\frac{1}{4}\leq 1-\varepsilon\\\
0&\text{ otherwise}\end{cases}$

To upper bound $K_{1}$, we consider $\frac{1}{4}\leq 1-\varepsilon$.

######  Lemma 4.

For all $0\leq k\leq K$, it holds that

$\displaystyle\mathbb{P}\left(\tilde{p}_{k+1}\geq\frac{5}{4}\tilde{p}_{k}+\frac{1}{8}\varepsilon\mid\\{x_{i}\\}_{i=1}^{k}\right)\geq\frac{1}{6}$

###### Proof.

Given that $\tilde{p}_{k}\leq\frac{1}{4}$ , we can show that

$\displaystyle\mathbb{E}\left[\tilde{p}_{k+1}\right]=\tilde{p}_{k}+\frac{1}{2}(1-\tilde{p}_{k})(\tilde{p}_{k}+\varepsilon)\geq\frac{11}{8}\tilde{p}_{k}+\frac{3}{8}\varepsilon$

Moreover, recall that we have that $\tilde{p}_{k+1}\leq
2\tilde{p}_{k}+\varepsilon$. Thus, we can apply the reverse Markov’s
inequality

$\displaystyle\mathbb{P}\left(p_{k+1}\geq\frac{5}{4}\tilde{p}_{k}+\frac{1}{8}\varepsilon\mid\\{x_{i}\\}_{i=1}^{k}\right)$
$\displaystyle\geq\frac{\mathbb{E}\left[\tilde{p}_{k+1}\right]-\tfrac{5}{4}\tilde{p}_{k}-\tfrac{1}{8}\varepsilon}{\tilde{p}_{k+1}-\tfrac{5}{4}\tilde{p}_{k}-\tfrac{1}{8}\varepsilon}$
$\displaystyle\geq\frac{\frac{11}{8}\tilde{p}_{k}+\frac{3}{8}\varepsilon-\tfrac{5}{4}\tilde{p}_{k}-\tfrac{1}{8}\varepsilon}{2\tilde{p}_{k}+\varepsilon-\tfrac{5}{4}\tilde{p}_{k}-\tfrac{1}{8}\varepsilon}$
$\displaystyle=\frac{\tfrac{1}{8}\tilde{p}_{k}+\tfrac{1}{4}\varepsilon}{\tfrac{3}{4}\tilde{p}_{k}+\frac{7}{8}\varepsilon}$
$\displaystyle\geq\frac{1}{6}$

∎

######  Lemma 5.

With probability at least $1-\exp\left(-\frac{1}{18}K_{1}\right)$ we have that

$\displaystyle K\leq
O\left(\frac{\log\eta^{-1}}{\log\left(\frac{5}{4}+\frac{\varepsilon}{2}\right)}\right)$

###### Proof.

By using $\tilde{p}_{k}\leq\frac{1}{4}$, it thus follows from lemma (4) that

$\displaystyle\mathbb{P}\left(\tilde{p}_{k+1}\geq\tilde{p}_{k}\left(\frac{5}{4}+\frac{\varepsilon}{2}\right)\right)\geq\mathbb{P}\left(\tilde{p}_{k+1}\geq\frac{5}{4}\tilde{p}_{k}+\frac{1}{8}\varepsilon\mid\\{x_{i}\\}_{i=1}^{k}\right)\geq\frac{1}{6}$

Denote $\beta=\left(\frac{5}{4}+\frac{\varepsilon}{2}\right)$. As in previous
work, we define the following partition of the interval
$(0,\nicefrac{{1}}{{4}})$.

$\displaystyle I_{1}$ $\displaystyle=(0,\eta]$ $\displaystyle I_{i}$
$\displaystyle=\left(\beta^{i-1}\eta,\beta^{i}\eta\right]$ $\displaystyle
I_{i^{*}}$ $\displaystyle=\left(\beta^{i^{*}-1}\eta,\frac{1}{4}\right]$

where $i^{*}$ is the smallest integer such that
$\beta^{i^{*}}\eta\geq\frac{1}{4}$, that is

$\displaystyle
i^{*}=\left\lceil\frac{\log\nicefrac{{1}}{{4\eta}}}{\log\beta}\right\rceil$

For $i>1$, let $\hat{k}_{i}$ be given such that
$\tilde{p}_{\hat{k}_{i}}\geq\beta^{i-1}\eta$, let $\hat{Y}_{i}$ be the
smallest number of steps such that
$\tilde{p}_{\hat{k}_{i}+\hat{Y}_{i}}>\beta^{i}\eta$. Then we have that
$\hat{Y}_{i}\leq Y_{i}\sim\texttt{Geom}\left(\nicefrac{{1}}{{6}}\right)$,
since, according to lemma (4), we have

$\displaystyle\mathbb{P}\left(\tilde{p}_{k+1}\geq\beta\tilde{p}_{k}\mid\\{x_{i}\\}_{i=1}^{k}\right)\geq\frac{1}{6}$

Therefore, for all $K^{*}$, we have that

$\displaystyle\mathbb{P}\left(K\geq
K^{*}\right)\leq\mathbb{P}\left(\sum_{i=1}^{i^{*}}Y_{i}\geq
K^{*}\right)=\mathbb{P}\left(B_{K^{*}}\leq i^{*}\right)$

where $B_{K^{*}}\sim\texttt{Bin}\left(K^{*},\nicefrac{{4}}{{7}}\right)$. Given
that $\mathbb{E}[B_{K^{*}}]=\frac{1}{6}K^{*}$, we can apply the Hoeffding’s
inequality for binomial distribution

$\displaystyle\mathbb{P}\left(B_{K^{*}}\leq\frac{1}{6}K^{*}-t\right)\leq\exp\left(-\frac{2t^{2}}{K^{*}}\right)$

choose $K^{*}=12i^{*}$ and $t=\frac{1}{6}K^{*}$ gives that

$\displaystyle\mathbb{P}\left(K\leq
K^{*}\right)\geq\mathbb{P}\left(B_{K^{*}}\geq i^{*}\right)\geq
1-\exp\left(-\frac{1}{18}K^{*}\right)$

∎

###  A.2 Growth from $\nicefrac{{1}}{{4}}$ to
$1-\max\left\\{\varepsilon,\eta\right\\}$

Recall the recurrence

$\displaystyle\mathbb{E}\left[\tilde{p}_{k+1}\right]\geq\tilde{p}_{k}+\frac{1}{2}(1-\tilde{p}_{k})(\tilde{p}_{k}+\varepsilon)$

We define

$\displaystyle
Z_{k+1}=\frac{\tilde{p}_{k+1}-\tilde{p}_{k}(z)}{(1-\tilde{p}_{k})(\tilde{p}_{k}+\varepsilon)}$

Then we have $\mathbb{E}[Z_{k+1}]\geq\nicefrac{{1}}{{2}}$. Let
$Y_{k}=-\nicefrac{{k}}{{2}}+\sum_{i=K_{1}+1}^{K_{1}+k+1}Z_{i}$, then $Y_{k}$
is a submartingale. We bound $Z_{k+1}$ as follows

######  Lemma 6.

$\displaystyle 0\leq Z_{k+1}\leq\frac{2}{1+\varepsilon}$

###### Proof.

We notice that
$\tilde{p}_{k}\leq\tilde{p}_{k+1}\leq\min\left\\{2\tilde{p}_{k}+\varepsilon,1\right\\}$.
Consider two cases of $p_{k}$:

Case 1: $\tilde{p}_{k}\leq\frac{1-\varepsilon}{2}$. In this case, we have
$1-\tilde{p}_{k}\geq\frac{1+\varepsilon}{2}$

$\displaystyle
Z_{k+1}\leq\frac{2\tilde{p}_{k}+\varepsilon-\tilde{p}_{k}}{(1-\tilde{p}_{k})(\tilde{p}_{k}+\varepsilon)}=\frac{1}{1-\tilde{p}_{k}}\leq\frac{2}{1+\varepsilon}$

Case 2: $\tilde{p}_{k}\geq\frac{1-\varepsilon}{2}$. In this case, we use
$\tilde{p}_{k+1}\leq 1$. Moreover, we have
$\tilde{p}_{k}+\varepsilon\geq\frac{1+\varepsilon}{2}$:

$\displaystyle
Z_{k+1}\leq\frac{1-\tilde{p}_{k}}{(\tilde{p}_{k}+\varepsilon)(1-\tilde{p}_{k})}=\frac{1}{\tilde{p}_{k}+\varepsilon}\leq\frac{2}{1+\varepsilon}$

∎

Thus,

$\displaystyle\left|Y_{k+1}-Y_{k}\right|=\left|-\frac{1}{2}+Z_{K_{1}+k+2}\right|\leq\frac{|3-\varepsilon|}{2+2\varepsilon}$

Let $n=K_{1}+K_{2}+1$. Therefore, we can apply Azuma’s inequality to get that

$\displaystyle\mathbb{P}\left(\sum_{i=K_{1}+1}^{n}Z_{i}\geq\frac{K_{2}}{2}-t\right)$
$\displaystyle=\mathbb{P}\left(-\frac{K_{2}}{2}+\sum_{i=K_{1}+1}^{n}Z_{i}\geq-t\right)$
$\displaystyle=\mathbb{P}\left(Y_{n}-Y_{0}\geq-t\right)$ $\displaystyle\geq
1-\exp\left(-\frac{2\left(1+\varepsilon\right)t^{2}}{K_{2}\left(3-\varepsilon\right)^{2}}\right)$

Let $t=\frac{K_{2}}{4}$ gives that

$\displaystyle\mathbb{P}\left(\sum_{i=1}^{n}Z_{i}\geq\frac{K_{2}}{4}\right)\geq
1-\exp\left(-\frac{K_{2}(1+\varepsilon)^{2}}{8(3-\varepsilon)^{2}}\right)$

We use the following function to track the growth of $p_{k}$, but starting
from $\nicefrac{{1}}{{4}}$.

$\displaystyle\psi(p)=\frac{1}{1+\varepsilon}\left(\log\left(p+\varepsilon\right)-\log(1-p)\right)+\frac{16}{3}p$

######  Lemma 7.

For all $p_{k}\geq\frac{1}{4}$, we have that

$\displaystyle\psi(\tilde{p}_{k+1})\geq\psi(\tilde{p}_{k})+Z_{k+1}$

###### Proof.

We first notice that

$\displaystyle\psi(\tilde{p}_{k+1})-\psi(\tilde{p}_{k})=\int_{\tilde{p}_{k}}^{\tilde{p}_{k+1}}\psi^{\prime}(p)dp\geq\min_{p\in[\tilde{p}_{k},\tilde{p}_{k+1}]}\psi^{\prime}(p)(\tilde{p}_{k+1}-\tilde{p}_{k})$

It suffice to show that

$\displaystyle\min_{p\in[\tilde{p}_{k},\tilde{p}_{k+1}]}\geq\frac{1}{(\tilde{p}_{k}+\varepsilon)(1-\tilde{p}_{k})}$

The first- and second-order derivative of $\psi$ are

$\displaystyle\psi^{\prime}(p)=\frac{1}{1+\varepsilon}\left(\frac{1}{p+\varepsilon}+\frac{1}{1-p}\right)+\frac{16}{3}$
$\displaystyle\psi^{\prime\prime}(p)=\frac{1}{1+\varepsilon}\left(\frac{1}{(1-p)^{2}}-\frac{1}{\left(p+\varepsilon\right)^{2}}\right)$

Therefore, $\psi^{\prime}$ attains its minimum at
$p^{*}=\min\left\\{1,\frac{1-\varepsilon}{2}\right\\}$, and $\psi^{\prime}$
decreases monotonically on $(\nicefrac{{1}}{{4}},p^{*}]$ and increases
monotonically on $[p^{*},1]$. Notice that the function
$\frac{1}{(\tilde{p}_{k}+\varepsilon)(1-\tilde{p}_{k})}$ also decreases
monotonically on $(\nicefrac{{1}}{{4}},p^{*}]$ and increases monotonically on
$[p^{*},1]$. We consider two cases of $p_{k}$:

Case 1: $\tilde{p}_{k}\in(\nicefrac{{1}}{{4}},p^{*}]$. In this range the
function $\frac{1}{(\tilde{p}_{k}+\varepsilon)(1-\tilde{p}_{k})}$ decreases
monotonically. Thus it achieves its maximum at
$\tilde{p}_{k}=\nicefrac{{1}}{{4}}$ with a value of
$\frac{16}{3+12\varepsilon}$. However, since $0\leq p\leq 1$, we have

$\displaystyle\min_{p\in[p_{k},p_{k+1}]}\psi^{\prime}(p)\geq\psi^{\prime}(p^{*})\geq\frac{16}{3}$

Thus

$\displaystyle\min_{p\in[p_{k},p_{k+1}]}\psi^{\prime}(p)\geq\frac{1}{(\tilde{p}_{k}+\varepsilon)(1-\tilde{p}_{k})}$

Case 2: $\tilde{p}_{k}\in(p^{*},1]$. Notice that $\psi$ increases
monotonically on $(p^{*},1]$. Thus

$\displaystyle\min_{p\in[p_{k},p_{k+1}]}\psi^{\prime}(p)=\psi^{\prime}(p_{k})\geq\frac{1}{1+\varepsilon}\left(\frac{1}{p_{k}+\varepsilon}+\frac{1}{1-p_{k}}\right)=\frac{1}{\left(p_{k}+\varepsilon\right)(1-p_{k})}$

∎

Therefore, we have

$\displaystyle\psi(\tilde{p}_{n})\geq\psi(\tilde{p}_{K_{1}})+\sum_{i=K_{1}+1}^{n}Z_{i}$

Plugging in the value of $\psi(\tilde{p}_{n})$ and $\psi(\tilde{p}_{K_{1}})$,
and notice that $\psi$ increases monotonically with $p$

$\displaystyle-\frac{\log(1-\tilde{p}_{n})}{1+\varepsilon}$
$\displaystyle=\psi(\tilde{p}_{n})-\frac{\log\tilde{p}_{n}}{1+\varepsilon}-\frac{16}{3}\tilde{p}_{n}$
$\displaystyle\geq\psi(\tilde{p}_{K_{1}})+\sum_{i=K_{1}+1}^{n}Z_{i}-\frac{16}{3}$
$\displaystyle\geq\psi\left(\frac{1}{4}\right)+\sum_{i=K_{1}+1}^{n}Z_{i}-\frac{16}{3}$
$\displaystyle=-\frac{1}{1+\varepsilon}\left(\log
4+\log\frac{3}{4}\right)-4+\sum_{i=K_{1}+1}^{n}Z_{i}$
$\displaystyle\geq\sum_{i=K_{1}+1}^{n}Z_{i}-4$

Since $\sum_{i=K_{1}+1}^{n}Z_{i}\geq\frac{K_{2}}{4}$ with probability at least
$1-\exp\left(-\frac{K_{2}(1+\varepsilon)^{2}}{8(3-\varepsilon)^{2}}\right)$,
as long as
$K_{2}\geq\frac{2\log\eta^{-1}}{1+\varepsilon}+4=O(\frac{\log\eta^{-1}}{1+\varepsilon}+1)$,
we have that with high probability
$\sum_{i=K_{1}+1}^{n}Z_{i}\geq\frac{\log\eta^{-1}}{1+\varepsilon}+4$, which
implies that

$\displaystyle-\log(1-\tilde{p}_{n})\geq\log\max\left\\{\varepsilon,\eta\right\\}^{-1}=-\log(\max\left\\{\eta,\varepsilon\right\\})$

which implies that $\tilde{p}_{n}\geq
1-\max\left\\{\eta,\varepsilon\right\\}$. This shows that, with high
probability, for $K_{1},K_{2}$ defined above, $n=K_{1}+K_{2}+1$ candidates
guarantess that each point $z\in[-\nicefrac{{1}}{{2}},\nicefrac{{1}}{{2}}]$
either has an $\eta$ approximation or is $\max\\{\eta,\varepsilon\\}$ away
from an $\eta$ approximation. In the case of $\eta\geq\varepsilon$, we have
that each $z$ has a $2\eta$ approximation. Otherwise, if $\varepsilon>\eta$,
we need an additional set of candidates to grown from $1-\varepsilon$ to
$1-\eta$.

###  A.3 Growth from $1-\varepsilon$ to $1-\eta$ under $\varepsilon>\eta$

Consider another set of candidates $\\{\hat{x}_{i}\\}_{i=1}^{K_{3}}$. By
Hoeffding’s inequality, we have that

$\displaystyle\mathbb{P}\left(\left|\sum_{i=1}^{K_{3}}\hat{x}_{i}\right|\geq(K_{3}-1)\varepsilon+\eta\right)\leq\exp\left(-\frac{\left((K_{3}-1)\varepsilon+\eta\right)^{2}}{2K_{3}}\right)$

This implies that with probability at least
$1-\exp\left(-\frac{\left((K_{3}-1)\varepsilon+\eta\right)^{2}}{2K_{3}}\right)$,
for each $\hat{y}\in[\eta-\varepsilon,\varepsilon-\eta]$, there exists
$\mathbf{y}\in[-\varepsilon,\varepsilon]^{K_{3}}$ such that
$\hat{y}=\sum_{i=1}^{K^{\prime}}\left(x_{i}+y_{i}\right)$. This implies that
with probability at least
$1-\exp\left(-\frac{\left((K_{3}-1)\varepsilon+\eta\right)^{2}}{2K_{3}}\right)$,
for all $z\in[-\nicefrac{{1}}{{2}},\nicefrac{{1}}{{2}}]$ we have that $z$ has
an $\eta$ approximation. For convenience we can choose $K_{3}=K_{1}+1$, which
results in a success probability at least
$1-\exp\left(-\max\\{\varepsilon,\eta\\}K_{1}\right)$ Thus, as long as
$n=2K_{1}+K_{2}+1$ with

$\displaystyle
K_{1}=O\left(\frac{\log\eta^{-1}}{\log\left(\frac{5}{4}+\frac{\varepsilon}{2}\right)}\right)\quad;K_{2}=O\left(1+\frac{\log\eta^{-1}}{(1+\varepsilon)}\right)$

we have that with probability at least
$1-\exp\left(-\frac{K_{2}(1+\varepsilon)^{2}}{8(3-\varepsilon)^{2}}\right)-\exp\left(-\frac{K_{1}}{18}\right)-\exp\left(-\max\\{\varepsilon,\eta\\}K_{1}\right)$,
each point in $[-\nicefrac{{1}}{{2}},\nicefrac{{1}}{{2}}]$ either has $\eta$
approximation or lies with $\eta$ distance to a point with $\eta$
approximation. Therefore, each point in
$[-\nicefrac{{1}}{{2}},\nicefrac{{1}}{{2}}]$ has an $2\eta$ approximation.

##  Appendix B Proof of Theorem 2

######  Lemma 8.

Let $g:{\mathbb{R}}\rightarrow{\mathbb{R}}$ be a randomly initialized network
of the form $g(x)=\mathbb{v}^{\top}\sigma(\mathbb{u}x)$, where
$\mathbb{v},\mathbb{u}\in{\mathbb{R}}^{2n}$, $n=K_{1}+K_{2}$,

$\displaystyle K_{1}$ $\displaystyle\geq
C_{1}\left(\frac{\log((\eta^{-1}))}{\log(\frac{5}{4}+\frac{\varepsilon}{2})}\right),$
$\displaystyle K_{2}$ $\displaystyle\geq
C_{2}\left(\frac{\log((\eta^{-1})))}{1+\varepsilon}\right),$

where $u_{i}=1$ for $i\leq n$, $u_{i}=-1$ for $i\geq n+1$, and
$v_{i}^{\prime}s$ are drawn from $\texttt{Unif}[-1,1]$. Then, with probability
at least $1-\delta$, there exist
$\mathbb{s}\in\\{0,1\\}^{2n},\mathbb{y}\in[-\varepsilon,+\varepsilon]^{2n}$
such that

$\displaystyle\sup_{x:|x|\leq
1}\left|wx-(\mathbb{v}+\mathbb{y})^{\top}\sigma((\mathbb{u}\odot\mathbb{s})x)\right|<\eta,\vspace{-0.5cm}$

for all $w\in[-\frac{1}{2},\frac{1}{2}]$ with

$\displaystyle\delta=\exp\left(-\tfrac{K_{2}(1+\varepsilon)^{2}}{8(3-\varepsilon)^{2}}\right)+\exp\left(-\tfrac{K_{1}}{18}\right)+\exp\left(-\max\\{\varepsilon,\eta\\}K_{1}\right)$

###### Proof.

Note that $wx=\sigma(wx)-\sigma(-wx)$ and without loss of generality we assume
$w\geq 0$. The case of $w<0$ can be handled by changing $x$ to $-x$.
Furthermore, we decompose $\mathbb{u},\mathbb{v},\mathbb{y},\mathbb{s}$ by

$\displaystyle\mathbb{u}=\begin{pmatrix}\mathbb{u}_{1}\\\
\mathbb{u}_{2}\end{pmatrix},\mathbb{v}=\begin{pmatrix}\mathbb{v}_{1}\\\
\mathbb{v}_{2}\end{pmatrix},\mathbb{s}=\begin{pmatrix}\mathbb{s}_{1}\\\
\mathbb{s}_{2}\end{pmatrix},\mathbb{y}=\begin{pmatrix}\mathbb{y}_{1}\\\
\mathbb{y}_{2}\end{pmatrix},$

where
$\mathbf{u}_{1}=\mathbb{1}_{n},\mathbf{u}_{2}=\mathbb{-1}_{n},\mathbf{v}_{1},\mathbf{v}_{2}\in{\mathbb{R}}^{n}$,
$\mathbf{s}_{1},\mathbf{s}_{2}\in\\{0,1\\}^{n}$, and
$\mathbf{y}_{1},\mathbf{y}_{2}\in[-\varepsilon,\varepsilon]^{n}$. Then we have

$\displaystyle(\mathbb{v}+\mathbb{y})^{\top}\sigma((\mathbb{u}\odot\mathbb{s})x)$
$\displaystyle=(\mathbb{v}_{1}+\mathbb{y}_{1})^{\top}\sigma((\mathbb{u}_{1}\odot\mathbb{s}_{1})x)+(\mathbb{v}_{2}+\mathbb{y}_{2})^{\top}\sigma((\mathbb{u}_{2}\odot\mathbb{s}_{2})x)$

We use the first half of the RHS to approximate $\sigma(wx)$ and use the
second half of the RHS to approximate $-\sigma(-wx)$.

Approximating $\sigma(wx)$. Note that since $w\geq 0$, then for $x\leq 0$,
$(\mathbb{v}_{1}+\mathbb{y}_{1})^{\top}\sigma((\mathbb{u}_{1}\odot\mathbb{s}_{1})x)=\sigma(wx)=0$.
Consider $x>0$. By definition of $\mathbf{u}_{1}$, we have

$\displaystyle\vspace{-0.2cm}\mathbf{v}_{1}^{\top}\sigma\left(\mathbf{u}_{1}x\right)=\mathbf{v}_{1}^{\top}x=\left(\sum_{i=1}^{n}v_{1,i}\right)x.$

Now consider $\left(\sum_{i=1}^{n}v_{1,i}\right)$, Theorem 3 states that with
probability at least $1-\frac{\delta}{4}$,

$\displaystyle\forall w\in\left[0,\frac{1}{2}\right],$
$\displaystyle\exists\mathbf{s}_{1}\in\\{0,1\\}^{n},\mathbf{y}_{1}\in[-\varepsilon,\varepsilon]^{n}\text{
s.t. }\left|w-\sum_{i=1}^{n}s_{1,i}(v_{1,i}+y_{1,i})\right|<\frac{\eta}{2}.$

Since

$\displaystyle(\mathbf{v}_{1}+\mathbf{y}_{1})^{\top}(\mathbf{s}_{1}\odot\mathbf{u}_{1})=\sum_{i=1}^{n}s_{1,i}(v_{1,i}+y_{1,i}),$

with probability at least $1-\frac{\delta}{4}$, we have

$\displaystyle\forall w\in\left[0,\frac{1}{2}\right],$
$\displaystyle\exists\mathbf{s}_{1}\in\\{0,1\\}^{n},\mathbf{y}_{1}\in[-\varepsilon,\varepsilon]^{n}\text{
s.t.
}\left|w-(\mathbf{v}_{1}+\mathbf{y}_{1})^{\top}(\mathbf{s}_{1}\odot\mathbf{u}_{1})\right|<\frac{\eta}{2}.$

Since $|x|\leq 1$, with probability at least $1-\frac{\delta}{4}$, we have

$\displaystyle\forall w\in\left[0,\frac{1}{2}\right],$
$\displaystyle\exists\mathbf{s}_{1}\in\\{0,1\\}^{n},\mathbf{y}_{1}\in[-\varepsilon,\varepsilon]^{n}\text{
s.t.
}\left|wx-(\mathbf{v}_{1}+\mathbf{y}_{1})^{\top}(\mathbf{s}_{1}\odot\mathbf{u}_{1})x\right|<\frac{\eta}{2}.$

Recall that
$(\mathbb{v}_{1}+\mathbb{y}_{1})^{\top}\sigma((\mathbb{u}_{1}\odot\mathbb{s}_{1})x)=\sigma(wx)=0$
for $x\leq 0$. Also, for $x>0$, $\sigma(wx)=wx$ and
$(\mathbf{v}_{1}+\mathbf{y}_{1})^{\top}\sigma((\mathbf{u}_{1}\odot\mathbf{s}_{1})x)=(\mathbf{v}_{1}+\mathbf{y}_{1})^{\top}(\mathbf{s}_{1}\odot\mathbf{u}_{1})x$.
Therefore, with probability at least $1-\frac{\delta}{4}$, we have

$\displaystyle\forall
w\in\left[0,\frac{1}{2}\right],\exists\mathbf{s}_{1}\in\\{0,1\\}^{n},\mathbf{y}_{1}\in[-\varepsilon,\varepsilon]^{n}\text{
s.t.
}\left|\sigma(wx)-(\mathbf{v}_{1}+\mathbf{y}_{1})^{\top}\sigma((\mathbf{u}_{1}\odot\mathbf{s}_{1})x)\right|<\frac{\eta}{2}.$

Approximating $-\sigma(-wx)$. For $x\geq 0$,
$(\mathbb{v}_{2}+\mathbb{y}_{2})^{\top}\sigma((\mathbb{u}_{2}\odot\mathbb{s}_{2})x)=-\sigma(-wx)=0$.
Now, consider $x<0$. By definition of $\mathbf{u}_{2}$, it holds that

$\displaystyle\mathbf{v}_{2}^{\top}\sigma(\mathbf{u}_{2}x)=\left(\sum_{i=1}^{n}v_{2,i}\right)x.$

Therefore, similarly we have that with probability at least
$1-\frac{\delta}{4}$,

$\displaystyle\forall
w\in\left[0,\frac{1}{2}\right],\exists\mathbf{s}_{2}\in\\{0,1\\}^{n},\mathbf{y}_{2}\in[-\varepsilon,\varepsilon]^{n}:\quad\left|-\sigma(-wx)-(\mathbf{v}_{2}+\mathbf{y}_{2})^{\top}\sigma((\mathbf{u}_{2}\odot\mathbf{s}_{2})x)\right|<\frac{\eta}{2}.$

Hence by a union bound, with probability at least $1-\frac{\delta}{2}$,

$\displaystyle\min_{\mathbf{s},\mathbf{y}}\sup_{x:|x|\leq
1}\left|wx-(\mathbb{v}+\mathbb{y})^{\top}\sigma((\mathbb{u}\odot\mathbb{s})x)\right|$
$\displaystyle=$
$\displaystyle\min_{\mathbf{s}_{1},\mathbf{y}_{1},\mathbf{s}_{2},\mathbf{y}_{2}}\sup_{x:|x|\leq
1}\left|wx-\left((\mathbb{v}_{1}+\mathbb{y}_{1})^{\top}\sigma((\mathbb{u}_{1}\odot\mathbb{s}_{1})x)+(\mathbb{v}_{2}+\mathbb{y}_{2})^{\top}\sigma((\mathbb{u}_{2}\odot\mathbb{s}_{2})x)\right)\right|$
$\displaystyle=$
$\displaystyle\min_{\mathbf{s}_{1},\mathbf{y}_{1},\mathbf{s}_{2},\mathbf{y}_{2}}\sup_{x:|x|\leq
1}\left|\left(\sigma(wx)-\sigma(-wx)\right)-\left((\mathbb{v}_{1}+\mathbb{y}_{1})^{\top}\sigma((\mathbb{u}_{1}\odot\mathbb{s}_{1})x)+(\mathbb{v}_{2}+\mathbb{y}_{2})^{\top}\sigma((\mathbb{u}_{2}\odot\mathbb{s}_{2})x)\right)\right|$
$\displaystyle\leq$
$\displaystyle\min_{\mathbf{s}_{1},\mathbf{y}_{1}}\sup_{x:|x|\leq
1}\left|\sigma(wx)-(\mathbb{v}_{1}+\mathbb{y}_{1})^{\top}\sigma((\mathbb{u}_{1}\odot\mathbb{s}_{1})x)\right|+\min_{\mathbf{s}_{2},\mathbf{y}_{2}}\sup_{x:|x|\leq
1}\left|-\sigma(-wx)-(\mathbb{v}_{2}+\mathbb{y}_{2})^{\top}\sigma((\mathbb{u}_{2}\odot\mathbb{s}_{2})x)\right|$
$\displaystyle<$ $\displaystyle\eta.$

Note that for the case $w\leq 0$, the result has the same probability and the
approximation error, so by a union bound, the lemma hold with probability at
least $1-\delta$. ∎

######  Lemma 9.

Let $g:{\mathbb{R}}^{d_{1}}\rightarrow\mathbb{R}^{d_{2}}$ be a randomly
initialized network of the form
$g(\mathbb{x})=\mathbb{V}\sigma(\mathbb{U}\mathbb{x})$, where
$\mathbb{V}\in{\mathbb{R}}^{d_{2}\times
2n},\mathbb{U}\in{\mathbb{R}}^{2n\times d_{1}},n=K_{1}+K_{2}$,

$\displaystyle K_{1}$ $\displaystyle\geq
C_{1}d_{1}\left(\frac{\log\left(\frac{d_{1}d_{2}}{\eta}\right)}{\log\left(\frac{5}{4}+\frac{\varepsilon}{2}\right)}\right),$
$\displaystyle K_{2}$ $\displaystyle\geq
C_{2}d_{1}\left(\frac{\log\left(\frac{d_{1}d_{2}}{\eta}\right)}{1+\varepsilon}\right),$

where weights in $\mathbb{V}$ are drawn i.i.d. from $\texttt{Unif}[-1,1]$,
$\mathbf{U}=\begin{pmatrix}\mathbf{U}^{+}\\\ \mathbf{U}^{-}\end{pmatrix}$,
with $\mathbf{U}^{+}$ being a matrix of all $1$s and $\mathbf{U}^{-}$ being a
matrix of all $-1$s . Let
$\hat{g}(\mathbb{x})=(\mathbb{S}\odot(\mathbb{V}+\mathbf{Y}))\sigma((\mathbb{B}\odot\mathbb{U})\mathbb{x})$
be the pruned network for masks $\mathbb{S}\in\\{0,1\\}^{d_{2}\times 2n}$,
$\mathbb{B}\in\\{0,1\\}^{2n\times d_{1}}$ and perturbation matrix
$\mathbb{Y}\in[-\varepsilon,\varepsilon]^{2n\times d_{1}}$. Let the target
network be $f_{\mathbb{W}}(\mathbb{x})=\mathbb{W}\mathbb{x}$, then with
probability at least
$1-d_{1}d_{2}\left(\exp\left(-\frac{K_{2}(1+\varepsilon)^{2}}{8(3-\varepsilon)^{2}}\right)-\exp\left(-\frac{K_{1}}{18}\right)-\exp\left(-\max\\{\varepsilon,\eta\\}K_{1}\right)\right)$,
there exist $\mathbb{S},\mathbb{B},\mathbb{Y}$ such that

$\displaystyle\sup_{x:\|x\|_{\infty}\leq
1}\left\|f_{\mathbb{W}}(\mathbb{x})-\hat{g}(\mathbb{x})\right\|<\eta,\vspace{-0.5cm}$

for all $\mathbb{W}$ such that $\|\mathbb{W}\|_{\infty}\leq\frac{1}{2}$.

###### Proof.

Since $\mathbf{U}$ can be written as $\begin{pmatrix}\mathbf{U}^{+}\\\
\mathbf{U}^{-}\end{pmatrix}$, with $\mathbf{U}^{+}$ being a matrix of all $1$s
and $\mathbf{U}^{-}$ being a matrix of all $-1$s, we choose $\hat{\mathbf{B}}$
such that $\hat{\mathbf{B}}\odot\mathbf{U}$ is of the form

$\displaystyle\hat{\mathbf{B}}\odot\mathbf{U}=\begin{pmatrix}\mathbf{u}_{1}^{+}&0&\dots&0\\\
0&\mathbf{u}_{2}^{+}&\dots&0\\\ \vdots&\vdots&\ddots&\vdots\\\
0&0&\dots&\mathbf{u}_{d_{1}}^{+}\\\ \mathbf{u}_{1}^{-}&0&\dots&0\\\
0&\mathbf{u}_{2}^{-}&\dots&0\\\ \vdots&\vdots&\ddots&\vdots\\\
0&0&\dots&\mathbf{u}_{d_{1}}^{-}\\\ \end{pmatrix}$

where $\mathbf{u}_{j}^{+}=\bm{1}$ and $\mathbf{u}_{j}^{-}=-\bm{1}$. Moreover,
we decompose $\mathbf{S}\odot\left(\mathbf{V}+\mathbf{Y}\right)$ as

$\displaystyle\mathbb{S}=\begin{pmatrix}\mathbb{s}_{1,1}^{+\top}&\cdots&\mathbb{s}_{1,d_{1}}^{+\top}&\mathbb{s}_{1,1}^{-\top}&\cdots&\mathbb{s}_{1,d_{1}}^{-\top}\\\
\vdots&&\vdots&\vdots&&\vdots\\\
\mathbb{s}_{d_{2},1}^{+\top}&\cdots&\mathbb{s}_{d_{2},d_{1}}^{+\top}&\mathbb{s}_{d_{2},1}^{-\top}&\cdots&\mathbb{s}_{d_{2},d_{1}}^{-\top}\end{pmatrix}$
$\displaystyle\mathbb{V}=\begin{pmatrix}\mathbb{v}_{1,1}^{+\top}&\cdots&\mathbb{v}_{1,d_{1}}^{+\top}&\mathbb{v}_{1,1}^{-\top}&\cdots&\mathbb{v}_{1,d_{1}}^{-\top}\\\
\vdots&&\vdots&\vdots&&\vdots\\\
\mathbb{v}_{d_{2},1}^{+\top}&\cdots&\mathbb{v}_{d_{2},d_{1}}^{+\top}&\mathbb{v}_{d_{2},1}^{-\top}&\cdots&\mathbb{v}_{d_{2},d_{1}}^{-\top}\end{pmatrix}$
$\displaystyle\mathbb{Y}=\begin{pmatrix}\mathbb{y}_{1,1}^{+\top}&\cdots&\mathbb{y}_{1,d_{1}}^{+\top}&\mathbb{y}_{1,1}^{-\top}&\cdots&\mathbb{y}_{1,d_{1}}^{-\top}\\\
\vdots&&\vdots&\vdots&&\vdots\\\
\mathbb{y}_{d_{2},1}^{+\top}&\cdots&\mathbb{y}_{d_{2},d_{1}}^{+\top}&\mathbb{y}_{d_{2},1}^{-\top}&\cdots&\mathbb{y}_{d_{2},d_{1}}^{-\top}\end{pmatrix}$

where each
$\mathbb{s}_{i,j}^{\pm},\mathbb{v}_{i,j}^{\pm},\mathbb{y}_{i,j}^{\pm}\in{\mathbb{R}}^{n/d_{1}}$.
Then we have

$\displaystyle\left[(\mathbb{S}\odot(\mathbb{V}+\mathbf{Y}))\sigma((\hat{\mathbb{B}}\odot\mathbb{U})\mathbb{x})\right]_{i}$
$\displaystyle=\sum_{j=1}^{d_{1}}((\mathbb{v}_{i,j}^{+}+\mathbf{y}_{i,j}^{+})\odot\mathbb{s}_{i,j}^{+})^{\top}\sigma(\mathbb{u}_{j}^{+}x_{j})+$
$\displaystyle\quad\quad\quad\sum_{j=1}^{d_{1}}((\mathbb{v}_{i,j}^{-}+\mathbf{y}_{i,j}^{+})\odot\mathbb{s}_{i,j}^{+})^{\top}\sigma(\mathbb{u}_{j}^{-}x_{j})$

Letting $\mathbb{v}_{ij}=\begin{pmatrix}\mathbb{v}_{ij}^{+}\\\
\mathbb{v}_{ij}^{-}\end{pmatrix},\mathbb{s}_{ij}=\begin{pmatrix}\mathbb{s}_{ij}^{+}\\\
\mathbb{s}_{ij}^{-}\end{pmatrix},\mathbb{y}_{ij}=\begin{pmatrix}\mathbb{y}_{ij}^{+}\\\
\mathbb{y}_{ij}^{-}\end{pmatrix}$ and
$\mathbb{y}_{ij}=\begin{pmatrix}\mathbb{y}_{ij}^{+}\\\
\mathbb{y}_{ij}^{-}\end{pmatrix}$, we then have

$\displaystyle\left[(\mathbb{S}\odot(\mathbb{V}+\mathbf{Y}))\sigma((\hat{\mathbb{B}}\odot\mathbb{U})\mathbb{x})\right]_{i}$
$\displaystyle=\sum_{j=1}^{d_{1}}((\mathbb{v}_{i,j}+\mathbf{y}_{i,j})\odot\mathbb{s}_{i,j})^{\top}\sigma(\mathbb{u}_{j}x_{j})$

Now define the event

$\displaystyle
F_{i,j,\eta}:=\left\\{\sup_{w:|w|\leq\frac{1}{2}}\inf_{\begin{subarray}{c}\mathbb{s}_{i}\in\\{0,1\\}^{2n/d_{1}},\\\
\mathbb{y}_{i,j}\in[-\varepsilon,\varepsilon]^{2n/d_{1}}\end{subarray}}\sup_{x:|x|\leq
1}\left|wx-((\mathbb{v}_{i,j}+\mathbf{y}_{i,j})\odot\mathbb{s}_{i,j})^{\top}\sigma(\mathbb{u}_{j}x)\right|<\eta\right\\}.$

Define $F_{\eta}:=\bigcap_{i=1}^{d_{2}}\bigcap_{j=1}^{d_{1}}F_{i,j,\eta}$,
then

$\displaystyle{\mathbb{P}}\left(F_{\frac{\eta}{d_{1}d_{2}}}\right)\geq
1-d_{1}d_{2}\left(\exp\left(-\frac{K_{2}(1+\varepsilon)^{2}}{8(3-\varepsilon)^{2}}\right)-\exp\left(-\frac{K_{1}}{18}\right)-\exp\left(-\max\\{\varepsilon,\eta\\}K_{1}\right)\right).$

On event $F_{\frac{\eta}{d_{1}d_{2}}}$, we have

$\displaystyle\sup_{\|\mathbb{W}\|_{\infty}\leq\frac{1}{2}}\inf_{\mathbb{S},\mathbb{B},\mathbb{Y}}\sup_{\|\mathbb{x}\|_{\infty}\leq
1}\left\|\mathbb{W}\mathbb{x}-(\mathbb{S}\odot(\mathbb{V}+\mathbf{Y}))\sigma((\mathbb{B}\odot\mathbb{U})\mathbb{x})\right\|$
$\displaystyle\leq$
$\displaystyle\sup_{\|\mathbb{W}\|_{\infty}\leq\frac{1}{2}}\inf_{\mathbb{S},\mathbb{Y}}\sup_{\|\mathbb{x}\|_{\infty}\leq
1}\left\|\mathbb{W}\mathbb{x}-(\mathbb{S}\odot(\mathbb{V}+\mathbf{Y}))\sigma((\hat{\mathbb{B}}\odot\mathbb{U})\mathbb{x})\right\|$
$\displaystyle\leq$
$\displaystyle\sup_{\|\mathbb{W}\|_{\infty}\leq\frac{1}{2}}\inf_{\mathbb{S},\mathbb{Y}}\sup_{\|\mathbb{x}\|_{\infty}\leq
1}\sum_{i=1}^{d_{2}}\left|\sum_{j=1}^{d_{1}}w_{i,j}x_{j}-\sum_{j=1}^{d_{1}}((\mathbb{v}_{i,j}+\mathbf{y}_{i,j})\odot\mathbb{s}_{i,j})^{\top}\sigma(\mathbb{u}_{j}x_{j})\right|$
$\displaystyle\leq$
$\displaystyle\sup_{\|\mathbb{W}\|_{\infty}\leq\frac{1}{2}}\inf_{\mathbb{S},\mathbb{Y}}\sup_{\|\mathbb{x}\|_{\infty}\leq
1}\sum_{i=1}^{d_{2}}\sum_{j=1}^{d_{1}}\left|w_{i,j}x_{j}-((\mathbb{v}_{i,j}+\mathbf{y}_{i,j})\odot\mathbb{s}_{i,j})^{\top}\sigma(\mathbb{u}_{j}x_{j})\right|$
$\displaystyle<$ $\displaystyle d_{1}d_{2}\frac{\eta}{d_{1}d_{2}}$
$\displaystyle=$ $\displaystyle\eta.$

∎

With the help of this lemma, we are ready to prove theorem 2. Recall that our
goal is to approximate an $L$-layer, ReLU activated target multi-layer
perceptron (MLP) $f(\mathbf{x})$ by pruning a $2L$-layer, ReLU activated
candidate MLP $g(\mathbf{x})$. For some input vector
$\mathbf{x}\in\mathbb{R}^{d_{0}}$, we assume $f(\mathbf{x})=f^{L}(\mathbf{x})$
has a fixed set of parameters $\\{\mathbf{W}^{\ell}\\}_{\ell=1}^{L}$,
represented by:

$\displaystyle f^{\ell}(\mathbf{x})$
$\displaystyle=\begin{cases}\mathbf{W}^{L}f^{L-1}(\mathbf{x}),&\text{if
}\ell=L,\\\
\sigma\left(\mathbf{W}^{\ell}f^{\ell-1}(\mathbf{x})\right),&\text{if
}\ell\in[L-1],\\\ \mathbf{x},&\text{if }\ell=0,\end{cases}$

where $\mathbf{W}^{\ell}\in\mathbb{R}^{d_{\ell}\times d_{\ell-1}}$. Similarly,
let $g(\mathbf{x})=g^{2L}(\mathbf{x})$ with parameters
$\\{\mathbf{U}_{\ell}\\}_{\ell=1}^{2L}$, represented by:

$\displaystyle g^{\ell}(\mathbf{x})$
$\displaystyle=\begin{cases}\mathbb{U}^{2L}g^{2L-1}(\mathbf{x}),&\text{if
}\ell=2L,\\\
\sigma\left(\mathbb{U}^{\ell}g^{\ell-1}(\mathbf{x})\right),&\text{if
}\ell\in[2L-1],\\\ \mathbf{x},&\text{if }\ell=0,\end{cases}$

where $\mathbf{U}^{\ell}\in\mathbb{R}^{\hat{d}_{\ell}\times\hat{d}_{\ell-1}}$.
In particular, $g$ is a neural network with twice the depth of $f$. We
consider the pruning and $\varepsilon$-perturbation of $g(\mathbf{x})$ with a
set of masks for the weights
$\mathcal{S}=\\{\mathbf{S}^{\ell}\\}_{\ell=1}^{2L}$ and perturbation matrices
$\mathcal{Y}=\\{\mathbf{Y}^{i}\\}_{i=1}^{L}$, denoted as
$g_{\mathcal{S},\mathcal{Y}}(\mathbf{x})=g_{\mathcal{S},\mathcal{Y}}^{2L}(\mathbf{x})$:

$\displaystyle g_{\mathcal{S},\mathcal{Y}}^{\ell}(\mathbf{x})$
$\displaystyle=\begin{cases}(\mathbf{S}^{2L}\odot(\mathbb{U}^{2L}+\mathbf{Y}^{2L}))g_{\mathcal{S},\mathcal{Y}}^{2L-1}(\mathbf{x}),&\text{
if }\ell=2L,\\\
\sigma\left((\mathbf{S}^{\ell}\odot(\mathbb{U}^{\ell}+\mathbf{Y}^{\ell}))g_{\mathcal{S},\mathcal{Y}}^{\ell-1}(\mathbf{x})\right),&\text{
if }i\in[L-1],\\\ \mathbf{x},&\text{ if }\ell=0.\end{cases}$

Let $\mathcal{F}_{\mathcal{Y}}$ denote the feasible set of the perturbation
$\mathcal{Y}$. Also recall our assumptions for the setup

######  Assumption 3.

We assume the following condition for $f,g$ and $\mathcal{F}_{\mathcal{Y}}$:

  1. 1.

For all $\ell\in\\{0\\}\cup[L]$, the weight matrix $\mathbf{W}^{\ell}$ of the
target neural network $f$ satisfies $\|\mathbf{W}^{\ell}\|\leq 1$ and
$\left\|\mathbf{W}^{\ell}\right\|_{\infty}\leq\frac{1}{2}$.

  2. 2.

The initialization of $g$ satisfies
$\mathbf{U}^{2\ell}_{ij}\sim\texttt{Unif}[-1,1]$, and
$\mathbf{U}^{2\ell-1}_{ij}=1$ if $i\leq\nicefrac{{\hat{d}_{2(\ell-1)}}}{{2}}$
and $\mathbf{U}^{2\ell-1}_{ij}=-1$ if
$i>\nicefrac{{\hat{d}_{2(\ell-1)}}}{{2}}$ for all $\ell\in[L]$ and
$j\in[\hat{d}_{2\ell-3}]$.

  3. 3.

The feasible set of $\mathcal{Y}$ is defined as

$\displaystyle\mathcal{F}_{\mathcal{Y}}=\left\\{\mathcal{Y}:\forall\ell\in[L],\left\|\mathbf{Y}^{2\ell-1}\right\|_{\max}=0\text{
and }\left\|\mathbf{Y}^{2\ell}\right\|_{\max}\leq\varepsilon\right\\}.$

We focus on the approximation error defined as:

$\displaystyle\min_{\mathcal{Y}\in\mathcal{F}_{\mathcal{Y}},\mathcal{S}}\sup_{\mathbf{x}:\|\mathbf{x}\|\leq
1}\left\|f(\mathbf{x})-g_{\mathcal{S},\mathcal{Y}}\left(\mathbf{x}\right)\right\|.$
(5)

We state the theorem here for convenience.

######  Theorem 4.

Consider approximating $f$ with $g$ as defined above. Assume that assumption
(3) holds. Also, assume that for $1\leq\ell\leq L$,

$\displaystyle
K_{1}=C_{1}d_{\ell-1}\left(\frac{\log\left(\frac{d_{\ell-1}d_{\ell}L}{\eta}\right)}{\log\left(\frac{5}{4}+\frac{\varepsilon}{2}\right)}\right);$
$\displaystyle\quad
K_{2}=C_{2}d_{\ell-1}\left(\frac{\log\left(\frac{d_{\ell-1}d_{\ell}L}{\eta}\right)}{1+\varepsilon}\right)$
$\displaystyle\texttt{dim}(\mathbb{U}^{2\ell})=d_{\ell}\times\left(K_{1}+K_{2}\right);$
$\displaystyle\quad\texttt{dim}(\mathbb{U}^{2\ell-1})=\left(K_{1}+K_{2}\right)\times
d_{\ell-1}.$

Then with probability at least
$1-2d_{1}d_{2}L\left(\exp\left(-\frac{K_{2}(1+\varepsilon)^{2}}{8(3-\varepsilon)^{2}}\right)-\exp\left(-\frac{K_{1}}{18}\right)-\exp\left(-\max\\{\varepsilon,\eta\\}K_{1}\right)\right)$,

$\displaystyle\min_{\mathcal{S},\mathcal{Y}}\sup_{\mathbf{x}:\|\mathbf{x}\|_{\infty}\leq
1}\|f(\mathbf{x})-g_{\mathcal{S},\mathcal{Y}}\left(\mathbf{x}\right)\|<\eta,$

where $g_{\mathcal{S},\mathcal{Y}}$ is a pruning & $\varepsilon$-perturbation
of $g$.

###### Proof.

By Lemma 9, for $\ell$-th layer, with probability
$1-d_{1}d_{2}\left(\exp\left(-\frac{K_{2}(1+\varepsilon)^{2}}{8(3-\varepsilon)^{2}}\right)-\exp\left(-\frac{K_{1}}{18}\right)-\exp\left(-\max\\{\varepsilon,\eta\\}K_{1}\right)\right)$,
we have

$\sup_{\mathbf{W}^{\ell}\in{\mathbb{R}}^{d_{\ell}\times
d_{\ell-1}}:\|\mathbf{W}^{\ell}\|\leq
1,\|\mathbf{W}^{\ell}\|_{\infty}\leq\frac{1}{2}}\min_{S^{2\ell},S^{2\ell-1},\mathbf{Y}^{\ell}}\sup_{\mathbf{x}:\|\mathbf{x}\|\leq
1}\|\mathbf{W}^{\ell}\mathbf{x}-(\mathbf{S}^{2\ell}\odot\mathbf{U}^{2\ell})\sigma((\mathbf{S}^{2\ell-1}\odot(\mathbf{U}^{2\ell-1}+\mathbf{Y}^{\ell}))\mathbf{x})\|<\frac{\eta}{2L}.$
(6)

Since ReLU is $1$-Lipschitz, with same probability, we have

$\sup_{\mathbf{W}^{\ell}\in{\mathbb{R}}^{d_{\ell}\times
d_{\ell-1}}:\|\mathbf{W}^{\ell}\|\leq
1,\|\mathbf{W}^{\ell}\|_{\infty}\leq\frac{1}{2}}\min_{S^{2\ell},S^{2\ell-1},\mathbf{Y}^{\ell}}\sup_{\mathbf{x}:\|\mathbf{x}\|\leq
1}\|\sigma(\mathbf{W}^{\ell}\mathbf{x})-\sigma((\mathbf{S}^{2\ell}\odot\mathbf{U}^{2\ell})\sigma((\mathbf{S}^{2\ell-1}\odot(\mathbf{U}^{2\ell-1}+\mathbf{Y}^{\ell}))\mathbf{x}))\|<\frac{\eta}{2L}.$
(7)

Then with probability at least
$1-2d_{1}d_{2}L\left(\exp\left(-\frac{K_{2}(1+\varepsilon)^{2}}{8(3-\varepsilon)^{2}}\right)-\exp\left(-\frac{K_{1}}{18}\right)-\exp\left(-\max\\{\varepsilon,\eta\\}K_{1}\right)\right)$,
(6) and (7) hold simultaneously for every layer $1\leq\ell\leq L$. Equation
(7) implies for $1\leq\ell\leq L-1$,

$\displaystyle\left\|\sigma\left(\mathbf{W}^{\ell+1}g_{\mathcal{S},\mathcal{Y}}^{2\ell}(\mathbf{x})\right)-g_{\mathcal{S},\mathcal{Y}}^{2(\ell+1)}(\mathbf{x})\right\|\leq\frac{\eta}{2L}\left\|g_{\mathcal{S},\mathcal{Y}}^{2\ell}(\mathbf{x})\right\|$

Since $\left\|\mathbf{W}^{\ell}\right\|\leq 1$ for all $\ell\in[L]$, we have
that

$\displaystyle\left\|g_{\mathcal{S},\mathcal{Y}}^{2(\ell+1)}(\mathbf{x})\right\|\leq\frac{\eta}{2L}\left\|g_{\mathcal{S},\mathcal{Y}}^{2\ell}(\mathbf{x})\right\|+\left\|\sigma\left(\mathbf{W}^{\ell+1}g_{\mathcal{S},\mathcal{Y}}^{2\ell}(\mathbf{x})\right)\right\|\leq\left(1+\frac{\eta}{2L}\right)\left\|g_{\mathcal{S},\mathcal{Y}}^{2\ell}(\mathbf{x})\right\|$

This implies that, for all $\mathbf{x}$ such that
$\left\|\mathbf{x}\right\|\leq 1$,

$\displaystyle\left\|g_{\mathcal{S},\mathcal{Y}}^{2\ell}(\mathbf{x})\right\|\leq\left(1+\frac{\eta}{2L}\right)^{\ell-1}\left\|\mathbf{x}\right\|\leq\left(1+\frac{\eta}{2L}\right)^{\ell-1}$

Thus, we have that for all $\mathbf{x}$ such that
$\left\|\mathbf{x}\right\|\leq 1$

$\displaystyle\left\|f^{\ell+1}(\mathbf{x})-g_{\mathcal{S},\mathcal{Y}}^{2(\ell+1)}(\mathbf{x})\right\|$
$\displaystyle=\left\|\sigma\left(\mathbf{W}^{\ell+1}f^{\ell}(\mathbf{x})\right)-g_{\mathcal{S},\mathcal{Y}}^{2(\ell+1)}(\mathbf{x})\right\|$
$\displaystyle\leq\left\|\sigma\left(\mathbf{W}^{\ell+1}f^{\ell}(\mathbf{x})\right)-\sigma\left(\mathbf{W}^{\ell+1}g_{\mathcal{S},\mathcal{Y}}^{2\ell}(\mathbf{x})\right)\right\|+\left\|\sigma\left(\mathbf{W}^{\ell+1}g_{\mathcal{S},\mathcal{Y}}^{2\ell}(\mathbf{x})\right)-g_{\mathcal{S},\mathcal{Y}}^{2(\ell+1)}(\mathbf{x})\right\|$
$\displaystyle\leq\left\|f^{\ell}(\mathbf{x})-g_{\mathcal{S},\mathcal{Y}}^{2\ell}(\mathbf{x})\right\|+\frac{\eta}{2L}\left\|g_{\mathcal{S},\mathcal{Y}}^{2\ell}(\mathbf{x})\right\|$
$\displaystyle\leq\left\|f^{\ell}(\mathbf{x})-g_{\mathcal{S},\mathcal{Y}}^{2\ell}(\mathbf{x})\right\|+\left(1+\frac{\eta}{2L}\right)^{\ell-1}\frac{\eta}{2L}$

Solving the recurrence thus gives

$\displaystyle\left\|f(\mathbf{x})-g_{\mathcal{S},\mathcal{Y}}(\mathbf{x})\right\|$
$\displaystyle=\left\|f^{L}(\mathbf{x})-g_{\mathcal{S},\mathcal{Y}}^{2L}(\mathbf{x})\right\|$
$\displaystyle\leq\sum_{i=1}^{L-1}\left(1+\frac{\eta}{2L}\right)^{i-1}\frac{\eta}{2L}$
$\displaystyle=\frac{\eta}{2L}\frac{2L}{\eta}\left(\left(1+\frac{\eta}{2L}\right)^{L}-1\right)$
$\displaystyle<e^{\eta/2}-1$ $\displaystyle<\eta.$

∎