SPFQ: A Stochastic Algorithm and Its Error Analysis for Neural Network
  Quantization
Quantization is a widely used compression method that effectively reduces
redundancies in over-parameterized neural networks. However, existing
quantization techniques for deep neural networks often lack a comprehensive
error analysis due to the presence of non-convex loss functions and nonlinear
activations. In this paper, we propose a fast stochastic algorithm for
quantizing the weights of fully trained neural networks. Our approach leverages
a greedy path-following mechanism in combination with a stochastic quantizer.
Its computational complexity scales only linearly with the number of weights in
the network, thereby enabling the efficient quantization of large networks.
Importantly, we establish, for the first time, full-network error bounds, under
an infinite alphabet condition and minimal assumptions on the weights and input
data. As an application of this result, we prove that when quantizing a
multi-layer network having Gaussian weights, the relative square quantization
error exhibits a linear decay as the degree of over-parametrization increases.
Furthermore, we demonstrate that it is possible to achieve error bounds
equivalent to those obtained in the infinite alphabet case, using on the order
of a mere $\log\log N$ bits per weight, where $N$ represents the largest number
of neurons in a layer.
Jinjie Zhang, Rayan Saab
# SPFO: A Stochastic Algorithm and its Error Analysis

###### Abstract.

Quantization is a widely used compression method that effectively reduces redundancies in over-parameterized neural networks. However, existing quantization techniques for deep neural networks often lack a comprehensive error analysis due to the presence of non-convex loss functions and nonlinear activations. In this paper, we propose a fast stochastic algorithm for quantizing the weights of fully trained neural networks. Our approach leverages a greedy path-following mechanism in combination with a stochastic quantizer. Its computational complexity scales only linearly with the number of weights in the network, thereby enabling the efficient quantization of large networks. Importantly, we establish, for the first time, full-network error bounds, under an infinite alphabet condition and minimal assumptions on the weights and input data. As an application of this result, we prove that when quantizing a multi-layer network having Gaussian weights, the relative square quantization error exhibits a linear decay as the degree of over-parametrization increases. Furthermore, we demonstrate that it is possible to achieve error bounds equivalent to those obtained in the infinite alphabet case, using on the order of a mere \(\log\log N\) bits per weight, where \(N\) represents the largest number of neurons in a layer.

## 1. Introduction

Deep neural networks (DNNs) have shown impressive performance in a variety of areas including computer vision and natural language processing among many others. However, highly overparameterized DNNs require a significant amount of memory to store their associated weights, activations, and - during training - gradients. As a result, in recent years, there has been an interest in model compression techniques, including quantization, pruning, knowledge distillation, and low-rank decomposition [27, 11, 6, 14, 15]. Neural network quantization, in particular, utilizes significantly fewer bits to represent the weights of DNNs. This substitution of original, say, 32-bit floating-point operations with more efficient low-bit operations has the potential to significantly reduce memory usage and accelerate inference time while maintaining minimal loss in accuracy. Quantization methods can be categorized into two classes [22]: quantization-aware training and post-training quantization. Quantization-aware training substitutes floating-point weights with low-bit representations during the training process, while post-training quantization quantizes network weights only after the training is complete.

To achieve high-quality empirical results, quantization-aware training methods, such as those in [7, 5, 35, 9, 21, 37, 40], often require significant time for retraining and hyper-parameter tuning using the entire training dataset. This can make them impractical for resource-constrained scenarios. Furthermore, it can be challenging to rigorously analyze the associated error bounds as quantization-aware training is an integer programming problem with a non-convex loss function, making it NP-hard in general. In contrast, post-training quantization algorithms, such as [8, 36, 23, 38, 20, 26, 39, 25, 13], require only a small amount
of training data, and recent research has made strides in obtaining quantization error bounds for some of these algorithms [23, 38, 25] in the context of shallow networks.

In this paper, we focus on this type of network quantization and its theoretical analysis, proposing a fast stochastic quantization technique and obtaining theoretical guarantees on its performance, even in the context of deep networks.

### Related work

In this section, we provide a summary of relevant prior results concerning a specific post-training quantization algorithm, which forms the basis of our present work. To make our discussion more precise, let \(X\in\mathbb{R}^{m\times N_{0}}\) and \(w\in\mathbb{R}^{N_{0}}\) represent the input data and a neuron in a single-layer network, respectively. Our objective is to find a mapping, also known as a _quantizer_, \(\mathcal{Q}:\mathbb{R}^{N_{0}}\to\mathcal{A}^{N_{0}}\) such that \(q=Q(w)\in\mathcal{A}^{N_{0}}\) minimizes \(\|Xq-Xw\|_{2}\). Even in this simplified context, since \(\mathcal{A}\) is a finite discrete set, this optimization problem is an integer program and therefore NP-hard in general. Nevertheless, if one can obtain good approximate solutions to this optimization problem, with theoretical error guarantees, then those guarantees can be combined with the fact that most neural network activation functions are Lipschitz, to obtain error bounds on entire (single) layers of a neural network.

Recently, Lybrand and Saab [23] proposed and analyzed a greedy algorithm, called _greedy path following quantization_ (GPFQ), to approximately solve the optimization problem outlined above. Their analysis was limited to the ternary alphabet \(\mathcal{A}=\{0,\pm 1\}\) and a single-layer network with Gaussian random input data. Zhang et al. [38] then extended GPFQ to more general input distributions and larger alphabets, and they introduced variations that promoted pruning of weights. Among other results, they proved that if the input data \(X\) is either bounded or drawn from a mixture of Gaussians, then the relative square error of quantizing a generic neuron \(w\) satisfies

\[\frac{\|Xw-Xq\|_{2}^{2}}{\|Xw\|_{2}^{2}}\lesssim\frac{m\log N_{0}}{N_{0}} \tag{1}\]

with high probability. Extensive numerical experiments in [38] also demonstrated that GPFQ, with 4 or 5 bit alphabets, can achieve less than 1% loss in Top-1 and Top-5 accuracy on common neural network architectures. Subsequently, [25] introduced a different algorithm that involves a deterministic preprocessing step on \(w\) that allows quantizing DNNs via _memoryless scalar quantization_ (MSQ) while preserving the same error bound in (1). This algorithm is more computationally intensive than those of [23, 38] but does not require hyper-parameter tuning for selecting the alphabet step-size.

### Contributions and organization

In spite of recent progress in developing computationally efficient algorithms with rigorous theoretical guarantees, all technical proofs in [23, 38, 25] only apply for a single-layer of a neural network with certain assumed input distributions. This limitation naturally comes from the fact that a random input distribution and a deterministic quantizer lead to activations (i.e., outputs of intermediate layers) with dependencies, whose distribution is usually intractable after passing through multiple layers and nonlinearities.

To overcome this main obstacle to obtaining theoretical guarantees for multiple layer neural networks, in Section 2, we propose a new stochastic quantization framework, called stochastic path following quantization (SPFQ), which introduces randomness into the quantizer. We show that SPFQ admits an interpretation as a two-phase algorithm consisting of a data-alignment phase and a quantization phase. This allows us to propose two variants, summarized
in Algorithm 1 and Algorithm 2, which involve different data alignment strategies that are amenable to analysis.

Importantly, our algorithms are fast. For example, SPFQ with approximate data alignment has a computational complexity that only scales linearly in the number of parameters of the neural network. This stands in sharp contrast with quantization algorithms that require solving optimization problems, generally resulting in polynomial complexity in the number of parameters.

In Section 3, we present the first error bounds for quantizing an entire \(L\)-layer neural network \(\Phi\), under an infinite alphabet condition and minimal assumptions on the weights and input data \(X\). To illustrate the use of our results, we show that if the weights of \(\Phi\) are standard Gaussian random variables, then, with high probability, the quantized neural network \(\widetilde{\Phi}\) satisfies

\[\frac{\|\Phi(X)-\widetilde{\Phi}(X)\|_{F}^{2}}{\mathbb{E}_{\Phi}\|\Phi(X)\|_{ F}^{2}}\lesssim\frac{m(\log N_{\max})^{L+1}}{N_{\min}} \tag{2}\]

where we take the expectation \(\mathbb{E}_{\Phi}\) with respect to the weights of \(\Phi\), and \(N_{\min}\), \(N_{\max}\) represent the minimum and maximum layer width of \(\Phi\) respectively. We can regard the relative error bound in (2) as a natural generalization of (1).

In Section 4, we consider the finite alphabet case under the random network hypothesis. Denoting by \(N_{i}\) the number of neurons in the \(i\)-th layer, we show that it suffices to use \(b\leq C\log\log\max\{N_{i-1},N_{i}\}\) bits to quantize the \(i\)-th layer while guaranteeing the same error bounds as in the infinite alphabet case.

It is worth noting that we assume that \(\Phi\) is equipped with ReLU activation functions, i.e. \(\max\{0,x\}\), throughout this paper. This assumption is only made for convenience and concreteness, and we remark that the non-linearities can be replaced by any Lipschitz functions without changing our results, except for the values of constants.

Finally, we empirically test the developed method in Section 5, by quantizing the weights of several neural network architectures that are originally trained for classification tasks on the ImageNet dataset [10]. The experiments show only a minor loss of accuracy compared to unquantized models.

## 2. Stochastic Quantization Algorithm

In this section, we start with the notation that will be used throughout this paper and then introduce our stochastic quantization algorithm, and show that it can be viewed as a two-stage algorithm. This in turn will simplify its analysis.

### Notation and Preliminaries

We denote various positive absolute constants by C, c. We use \(a\lesssim b\) as shorthand for \(a\leq Cb\), and \(a\gtrsim b\) for \(a\geq Cb\). For any matrix \(A\in\mathbb{R}^{m\times n}\), \(\|A\|_{\max}\) denotes \(\max_{i,j}|A_{ij}|\).

#### 2.1.1. Quantization

An \(L\)-layer perceptron, \(\Phi:\mathbb{R}^{N_{0}}\to\mathbb{R}^{N_{L}}\), acts on a vector \(x\in\mathbb{R}^{N_{0}}\) via

\[\Phi(x):=\varphi^{(L)}\circ A^{(L)}\circ\cdots\circ\varphi^{(1)}\circ A^{(1)}(x) \tag{3}\]

where each \(\varphi^{(i)}:\mathbb{R}^{N_{i}}\to\mathbb{R}^{N_{i}}\) is an activation function acting entrywise, and \(A^{(i)}:\mathbb{R}^{N_{i-1}}\to\mathbb{R}^{N_{i}}\) is an affine map given by \(A^{(i)}(z):=W^{(i)\top}z+b^{(i)}\). Here, \(W^{(i)}\in\mathbb{R}^{N_{i-1}\times N_{i}}\) is a weight matrix and \(b^{(i)}\in\mathbb{R}^{N_{i}}\) is a bias vector. Since \(w^{\top}x+b=\langle(w,b),(x,1)\rangle\), the bias term \(b^{(i)}\) can simply be treated as an extra row to the weight matrix \(W^{(i)}\), so we will henceforth ignore it. For
theoretical analysis, we focus on infinite _mid-tread_ alphabets, with step-size \(\delta\), i.e., alphabets of the form

\[\mathcal{A}=\mathcal{A}_{\infty}^{\delta}:=\{\pm k\delta:k\in\mathbb{Z}\} \tag{4}\]

and their finite versions, mid-tread alphabets of the form

\[\mathcal{A}=\mathcal{A}_{K}^{\delta}:=\{\pm k\delta:0\leq k\leq K,k\in\mathbb{Z }\}. \tag{5}\]

Given \(\mathcal{A}=\mathcal{A}_{\infty}^{\delta}\), the associated _stochastic scalar quantizer_\(\mathcal{Q}_{\mathrm{StoQ}}:\mathbb{R}\to\mathcal{A}\) randomly rounds every \(z\in\mathbb{R}\) to either the minimum or maximum of the interval \([k\delta,(k+1)\delta]\) containing it, in such a way that \(\mathbb{E}(\mathcal{Q}_{\mathrm{StoQ}}(z))=z\). Specifically, we define

\[\mathcal{Q}_{\mathrm{StoQ}}(z):=\begin{cases}\lfloor\frac{z}{\delta}\rfloor \delta&\text{with probability}\,p\\ \big{(}\lfloor\frac{z}{\delta}\rfloor+1\big{)}\delta&\text{with probability}\,1-p \end{cases} \tag{6}\]

where \(p=1-\frac{z}{\delta}+\lfloor\frac{z}{\delta}\rfloor\). If instead of the infinite alphabet, we use \(\mathcal{A}=\mathcal{A}_{K}^{\delta}\), then whenever \(|z|\leq K\delta\), \(\mathcal{Q}_{\mathrm{StoQ}}(z)\) is defined via (6) while \(\mathcal{Q}_{\mathrm{StoQ}}(z)\) is assigned \(-K\delta\) and \(K\delta\) if \(z<-K\delta\) and \(z>K\delta\) respectively.

#### 2.1.2. Orthogonal projections

Given a subspace \(S\subseteq\mathbb{R}^{m}\), we denote by \(S^{\perp}\) its orthogonal complement in \(\mathbb{R}^{m}\), and by \(P_{S}\) the orthogonal projection of \(\mathbb{R}^{m}\) onto \(S\). In particular, if \(z\in\mathbb{R}^{m}\) is a nonzero vector, then we use \(P_{z}\) and \(P_{z^{\perp}}\) to represent orthogonal projections onto \(\mathrm{span}(z)\) and \(\mathrm{span}(z)^{\perp}\) respectively. Hence, for any \(x\in\mathbb{R}^{m}\), we have

\[P_{z}(x)=\frac{\langle z,x\rangle z}{\|z\|_{2}^{2}},\quad x=P_{z}(x)+P_{z^{\perp }}(x),\quad\text{and}\quad\|x\|_{2}^{2}=\|P_{z}(x)\|_{2}^{2}+\|P_{z^{\perp}}(x )\|_{2}^{2}. \tag{7}\]

Throughout this paper, we will also use \(P_{z}\) and \(P_{z^{\perp}}\) to denote the associated matrix representations satisfying

\[P_{z}x=\frac{zz^{\top}}{\|z\|_{2}^{2}}x\quad\text{and}\quad P_{z^{\perp}}x= \Big{(}I-\frac{zz^{\top}}{\|z\|_{2}^{2}}\Big{)}x. \tag{8}\]

#### 2.1.3. Convex order

We now introduce the concept of _convex order_ (see, e.g., [32]), which will be heavily used in our analysis.

**Definition 2.1**.: Let \(X,Y\) be \(n\)-dimensional random vectors such that

\[\mathbb{E}f(X)\leq\mathbb{E}f(Y) \tag{9}\]

holds for all convex functions \(f:\mathbb{R}^{n}\to\mathbb{R}\), provided the expectations exist. Then \(X\) is said to be smaller than \(Y\) in the _convex order_, denoted by \(X\leq_{\mathrm{cx}}Y\).

For \(i=1,2,\ldots,n\), define functions \(\phi_{i}(x):=x_{i}\) and \(\psi_{i}(x):=-x_{i}\). Since both \(\phi_{i}(x)\) and \(\psi_{i}(x)\) are convex, substituting them into (9) yields \(\mathbb{E}X_{i}=\mathbb{E}Y_{i}\) for all \(i\). Therefore, we obtain

\[X\leq_{\mathrm{cx}}Y\implies\mathbb{E}X=\mathbb{E}Y. \tag{10}\]

Clearly, according to Definition 2.1, \(X\leq_{\mathrm{cx}}Y\) only depends on the respective distributions of \(X\) and \(Y\). It can be easily seen that the relation \(\leq_{\mathrm{cx}}\) satisfies reflexivity and transitivity. In other words, one has \(X\leq_{\mathrm{cx}}X\) and that if \(X\leq_{\mathrm{cx}}Y\) and \(Y\leq_{\mathrm{cx}}Z\), then \(X\leq_{\mathrm{cx}}Z\). The convex order defined in Definition 2.1 is also called _mean-preserving spread_[31, 24], which is a special case of _second-order stochastic dominance_[16, 17, 32], see Appendix A for details.
### SPFQ

We start with a data set \(X\in\mathbb{R}^{m\times N_{0}}\) with (vectorized) data stored as rows and a pretrained neural network \(\Phi\) with weight matrices \(W^{(i)}\in\mathbb{R}^{N_{i-1}\times N_{i}}\) having neurons as their columns. Let \(\Phi^{(i)}\), \(\widetilde{\Phi}^{(i)}\) denote the original and quantized neural networks up to layer \(i\) respectively so that, for example, \(\Phi^{(i)}(x):=\varphi^{(i)}\circ W^{(i)}\circ\cdots\circ\varphi^{(1)}\circ W^ {(1)}(x)\). Assuming the first \(i-1\) layers have been quantized, define the _activations_ from \((i-1)\)-th layer as

\[X^{(i-1)}:=\Phi^{(i-1)}(X)\in\mathbb{R}^{m\times N_{i-1}}\quad\text{and}\quad \widetilde{X}^{(i-1)}:=\widetilde{\Phi}^{(i-1)}(X)\in\mathbb{R}^{m\times N_{i- 1}}, \tag{11}\]

which also serve as input data for the \(i\)-th layer. For each neuron \(w\in\mathbb{R}^{N_{i-1}}\) in layer \(i\), our goal is to construct a quantized vector \(q\in\mathcal{A}^{N_{i-1}}\) such that

\[\widetilde{X}^{(i-1)}q=\sum_{t=1}^{N_{i-1}}q_{t}\widetilde{X}_{t}^{(i-1)} \approx\sum_{t=1}^{N_{i-1}}w_{t}X_{t}^{(i-1)}=X^{(i-1)}w\]

where \(X_{t}^{(i-1)}\), \(\widetilde{X}_{t}^{(i-1)}\) are the \(t\)-th columns of \(X^{(i-1)}\), \(\widetilde{X}^{(i-1)}\). Following the GPFQ scheme in [23, 38], our algorithm selects \(q_{t}\) sequentially, for \(t=1,2,\ldots,N_{i-1}\), so that the approximation error of the \(t\)-th iteration, denoted by

\[u_{t}:=\sum_{j=1}^{t}w_{j}X_{j}^{(i-1)}-\sum_{j=1}^{t}q_{j}\widetilde{X}_{j}^{ (i-1)}\in\mathbb{R}^{m}, \tag{12}\]

is well-controlled in the \(\ell_{2}\) norm. Specifically, assuming that the first \(t-1\) components of \(q\) have been determined, the proposed algorithm maintains the error vector \(u_{t-1}=\sum\limits_{j=1}^{t-1}(w_{j}X_{j}^{(i-1)}-q_{j}\widetilde{X}_{j}^{(i -1)})\), and sets \(q_{t}\in\mathcal{A}\) probabilistically depending on \(u_{t-1}\), \(X_{t}^{(i-1)}\), and \(\widetilde{X}_{t}^{(i-1)}\). Note that (12) implies

\[u_{t}=u_{t-1}+w_{t}X_{t}^{(i-1)}-q_{t}\widetilde{X}_{t}^{(i-1)} \tag{13}\]

and using (7), one can get

\[c^{*} :=\arg\min_{c\in\mathbb{R}}\|u_{t-1}+w_{t}X_{t}^{(i-1)}-c \widetilde{X}_{t}^{(i-1)}\|_{2}^{2}\] \[=\arg\min_{c\in\mathbb{R}}\|P_{\widetilde{X}_{t}^{(i-1)}}(u_{t-1} +w_{t}X_{t}^{(i-1)})-c\widetilde{X}_{t}^{(i-1)}\|_{2}^{2}\] \[=\arg\min_{c\in\mathbb{R}}\left\|\frac{\langle\widetilde{X}_{t}^{ (i-1)},u_{t-1}+w_{t}X_{t}^{(i-1)}\rangle}{\|\widetilde{X}_{t}^{(i-1)}\|_{2}^{2 }}\widetilde{X}_{t}^{(i-1)}-c\widetilde{X}_{t}^{(i-1)}\right\|_{2}^{2}\] \[=\frac{\langle\widetilde{X}_{t}^{(i-1)},u_{t-1}+w_{t}X_{t}^{(i-1) }\rangle}{\|\widetilde{X}_{t}^{(i-1)}\|_{2}^{2}}.\]

Hence, a natural design of \(q_{t}\in\mathcal{A}\) is to quantize \(c^{*}\). Instead of using a deterministic quantizer as in [23, 38], we apply the stochastic quantizer in (6), that is

\[q_{t}:=\mathcal{Q}_{\text{StocQ}}(c^{*})=\mathcal{Q}_{\text{StocQ}}\Bigg{(} \frac{\langle\widetilde{X}_{t}^{(i-1)},u_{t-1}+w_{t}X_{t}^{(i-1)}\rangle}{\| \widetilde{X}_{t}^{(i-1)}\|_{2}^{2}}\Bigg{)}. \tag{14}\]
Putting everything together, the stochastic version of GPFQ, namely SPFQ in its basic form, can now be expressed as follows.

\[\begin{cases}u_{0}=0\in\mathbb{R}^{m},\\ q_{t}=\mathcal{Q}_{\text{StocQ}}\bigg{(}\frac{(\widetilde{X}_{t}^{(i-1)},u_{t-1} +w_{t}X_{t}^{(i-1)})}{\|\widetilde{X}_{t}^{(i-1)}\|_{2}^{2}}\bigg{)},\\ u_{t}=u_{t-1}+w_{t}X_{t}^{(i-1)}-q_{t}\widetilde{X}_{t}^{(i-1)}\end{cases} \tag{15}\]

where \(t\) iterates over \(1,2,\ldots,N_{i-1}\). In particular, the final error vector is

\[u_{N_{i-1}}=\sum_{j=1}^{N_{i-1}}w_{j}X_{j}^{(i-1)}-\sum_{j=1}^{N_{i-1}}q_{j} \widetilde{X}_{j}^{(i-1)}=X^{(i-1)}w-\widetilde{X}^{(i-1)}q \tag{16}\]

and our goal is to estimate \(\|u_{N_{i-1}}\|_{2}\).

### A two-phase pipeline

An essential observation is that SPFQ in (15) can be equivalently decomposed into two phases.

**Phase I**: Given inputs \(X^{(i-1)}\), \(\widetilde{X}^{(i-1)}\) and neuron \(w\in\mathbb{R}^{N_{i-1}}\) for the \(i\)-th layer, we first align the input data to the layer, by finding a real-valued vector \(\widetilde{w}\in\mathbb{R}^{N_{i-1}}\) such that \(\widetilde{X}^{(i-1)}\widetilde{w}\approx X^{(i-1)}w\). Similar to our discussion above (14), we adopt the same sequential selection strategy to obtain each \(\widetilde{w}_{t}\) and deduce the following update rules.

\[\begin{cases}\hat{u}_{0}=0\in\mathbb{R}^{m},\\ \widetilde{w}_{t}=\frac{\langle\widetilde{X}_{t}^{(i-1)},\hat{u}_{t-1}+w_{t}X _{t}^{(i-1)}\rangle}{\|\widetilde{X}_{t}^{(i-1)}\|_{2}^{2}},\\ \hat{u}_{t}=\hat{u}_{t-1}+w_{t}X_{t}^{(i-1)}-\widetilde{w}_{t}\widetilde{X}_{t }^{(i-1)}\end{cases} \tag{17}\]

where \(t=1,2\ldots,N_{i-1}\). Note that the approximation error is given by

\[\hat{u}_{N_{i-1}}=X^{(i-1)}w-\widetilde{X}^{(i-1)}\widetilde{w}. \tag{18}\]

**Phase II**: After getting the new weights \(\widetilde{w}\), we quantize \(\widetilde{w}\) using SPFQ with input \(\widetilde{X}^{(i-1)}\), i.e., finding \(\widetilde{q}\in\mathcal{A}^{N_{i-1}}\) such that \(\widetilde{X}^{(i-1)}\widetilde{q}\approx\widetilde{X}^{(i-1)}\widetilde{w}\). This process can be summarized as follows. For \(t=1,2,\ldots,N_{i-1}\),

\[\begin{cases}\widetilde{u}_{0}=0\in\mathbb{R}^{m},\\ \widetilde{q}_{t}=\mathcal{Q}_{\text{StocQ}}\Big{(}\widetilde{w}_{t}+\frac{ \langle\widetilde{X}_{t}^{(i-1)},\widetilde{u}_{t-1}\rangle}{\|\widetilde{X}_{ t}^{(i-1)}\|_{2}^{2}}\Big{)},\\ \widetilde{u}_{t}=\widetilde{u}_{t-1}+(\widetilde{w}_{t}-\widetilde{q}_{t}) \widetilde{X}_{t}^{(i-1)}.\end{cases} \tag{19}\]

Here, the quantization error is

\[\widetilde{u}_{N_{i-1}}=\widetilde{X}^{(i-1)}(\widetilde{w}-\widetilde{q}). \tag{20}\]

**Proposition 2.2**.: _Given inputs \(X^{(i-1)}\), \(\widetilde{X}^{(i-1)}\) and any neuron \(w\in\mathbb{R}^{N_{i-1}}\) for the \(i\)-th layer, the two-phase formulation given by (17) and (19) generate exactly same result as in (15), that is, \(\widetilde{q}=q\)._

Proof.: We proceed by induction on the iteration index \(t\). If \(t=1\), then (17), (19) and (15) imply that

\[\widetilde{q}_{1}=\mathcal{Q}_{\text{StocQ}}(\widetilde{w}_{1})=\mathcal{Q}_ {\text{StocQ}}\Big{(}\frac{\langle\widetilde{X}_{1}^{(i-1)},w_{1}X_{1}^{(i-1)} \rangle}{\|\widetilde{X}_{1}^{(i-1)}\|_{2}^{2}}\Big{)}=q_{1}.\]
For \(t\geq 2\), assume \(\widetilde{q}_{j}=q_{j}\) for \(1\leq j\leq t-1\) and we aim to prove \(\widetilde{q}_{t}=q_{t}\). Note that \(\hat{u}_{t-1}=\sum_{j=1}^{t-1}(w_{j}X_{j}-\widetilde{w}_{j}\widetilde{X}_{j})\) and \(\widetilde{u}_{t-1}=\sum_{j=1}^{t-1}(\widetilde{w}_{j}\widetilde{X}_{j}- \widetilde{q}_{j}\widetilde{X}_{j})=\sum_{j=1}^{t-1}(\widetilde{w}_{j} \widetilde{X}_{j}-q_{j}\widetilde{X}_{j})\) by our induction hypothesis. It follows that \(\hat{u}_{t-1}+\widetilde{u}_{t-1}=\sum_{j=1}^{t-1}(w_{j}X_{j}-q_{j}\widetilde {X}_{j})=u_{t-1}\). Thus, we get

\[\widetilde{q}_{t}=\mathcal{Q}_{\text{StocQ}}\Big{(}\frac{\langle\widetilde{X }_{t}^{(i-1)},\widetilde{u}_{t-1}+\hat{u}_{t-1}+w_{t}X_{t}^{(i-1)}\rangle}{\| \widetilde{X}_{t}^{(i-1)}\|_{2}^{2}}\Big{)}=\mathcal{Q}_{\text{StocQ}}\Big{(} \frac{\langle\widetilde{X}_{t}^{(i-1)},u_{t-1}+w_{t}X_{t}^{(i-1)}\rangle}{\| \widetilde{X}_{t}^{(i-1)}\|_{2}^{2}}\Big{)}=q_{t}.\]

This establishes \(\widetilde{q}=q\) and completes the proof. 

Based on Proposition 2.2, the quantization error (16) for SPFQ can be split into two parts:

\[u_{N_{i-1}}=X^{(i-1)}w-\widetilde{X}^{(i-1)}q=X^{(i-1)}w-\widetilde{X}^{(i-1) }\widetilde{w}+\widetilde{X}^{(i-1)}(\widetilde{w}-q)=\hat{u}_{N_{i-1}}+ \widetilde{u}_{N_{i-1}}.\]

Here, the first error term \(\hat{u}_{N_{i-1}}\) results from the data alignment in (17) to generate a new "virtual" neuron \(\widetilde{w}\) and the second error term \(\widetilde{u}_{N_{i-1}}\) is due to the quantization in (19). It follows that

\[\|u_{N_{i-1}}\|_{2}=\|\hat{u}_{N_{i-1}}+\widetilde{u}_{N_{i-1}}\|_{2}\leq\| \hat{u}_{N_{i-1}}\|_{2}+\|\widetilde{u}_{N_{i-1}}\|_{2}. \tag{21}\]

Thus, we can bound the quantization error for SPFQ by controlling \(\|\hat{u}_{N_{i-1}}\|_{2}\) and \(\|\widetilde{u}_{N_{i-1}}\|_{2}\).

```
Input: An \(L\)-layer neural network \(\Phi\) with weight matrices \(W^{(i)}\in\mathbb{R}^{N_{i-1}\times N_{i}}\), input data \(X\in\mathbb{R}^{m\times N_{0}}\)
1for\(i=1\)to\(L\)do
2 Generate \(X^{(i-1)}=\Phi^{(i-1)}(X)\in\mathbb{R}^{m\times N_{i-1}}\) and \(\widetilde{X}^{(i-1)}=\widetilde{\Phi}^{(i-1)}(X)\in\mathbb{R}^{m\times N_{i-1}}\)repeat For each column \(w\) of \(W^{(i)}\)Phase I: Find a solution \(\widetilde{w}\) to (22)Phase II: Obtain the quantized neuron \(\widetilde{q}\in\mathcal{A}^{N_{i-1}}\) via (19) until All columns of \(W^{(i)}\) are quantized Obtain the quantized \(i\)-th layer weights \(Q^{(i)}\in\mathcal{A}^{N_{i-1}\times N_{i}}\)Output: Quantized neural network \(\widetilde{\Phi}\)
```

**Algorithm 1**SPFQ with perfect data alignment

### SPFQ Variants

The two-phase formulation of SPFQ provides a flexible framework that allows for the replacement of one or both phases with alternative algorithms. Here, our focus is on replacing the first, "data-alignment", phase to eliminate, or massively reduce, the error bound associated with this step. Indeed, by exploring alternative approaches, one can improve the error bounds of SPFQ, at the expense of increasing the computational complexity. Below, we present two such alternatives to Phase I.

In Section 3 we derive an error bound associated with the second phase of SPFQ, namely quantization, which is independent of the reconstructed neuron \(\widetilde{w}\). Thus, to reduce the bound on \(\|u_{N_{i-1}}\|_{2}\) in (21), we can eliminate \(\|\hat{u}_{N_{i-1}}\|_{2}\) by simply choosing \(\widetilde{w}\) with \(\widetilde{X}^{(i-1)}\widetilde{w}=X^{(i-1)}w\). As this system of equations may admit infinitely many solutions, we opt for one with the minimal \(\|\widetilde{w}\|_{\infty}\). This choice is motivated by the fact that smaller weights can be accommodated by smaller quantization alphabets, resulting in bit savings in practical applications. In other
words, we replace Phase I with the optimization problem

\[\begin{split}\min_{\widetilde{w}\in\mathbb{R}^{N_{i-1}}}& \|\widetilde{w}\|_{\infty}\\ \text{s.t.}&\widetilde{X}^{(i-1)}\widetilde{w}=X^{(i- 1)}w.\end{split} \tag{22}\]

It is not hard to see that (22) can be formulated as a linear program and solved via standard linear programming techniques [1]. Alternatively, powerful tools like Cadzow's method [3, 4] can also be used to solve linearly constrained infinity-norm optimization problems like (22). Cadzow's method has computational complexity \(O(m^{2}N_{i-1})\), thus is a factor of \(m\) more expensive than our original approach but has the advantage of eliminating \(\|\hat{u}_{N_{i}-1}\|_{2}\).

With this modification, one then proceeds with Phase II as before. Given a minimum \(\ell_{\infty}\) solution \(\widetilde{w}\) satisfying \(\widetilde{X}^{(i-1)}\widetilde{w}=X^{(i-1)}w\), one can quantize it using (19) and obtain \(\widetilde{q}\in\mathcal{A}^{N_{i-1}}\). In this case, \(\widetilde{q}\) may not be equal to \(q\) in (15) and the quantization error becomes

\[X^{(i-1)}w-\widetilde{X}^{(i-1)}\widetilde{q}=\widetilde{X}^{(i-1)}( \widetilde{w}-\widetilde{q})=\widetilde{u}_{N_{i-1}} \tag{23}\]

where only Phase II is involved. We summarize this version of SPFQ in Algorithm 1.

The second approach we present herein aims to reduce the computational complexity associated with (22). To that end, we generalize the data alignment process in (17) as follows. Let \(r\in\mathbb{Z}^{+}\) and \(w\in\mathbb{R}^{N_{i-1}}\). For \(t=1,2,\ldots,N_{i-1}\), we perform (17) as before. Now however, for \(t=N_{i-1}+1,N_{i-1}+2,\ldots,rN_{i-1}\), we run

\[\begin{cases}\hat{v}_{t-1}=\hat{u}_{t-1}-w_{t}X_{t}^{(i-1)}+\widetilde{w}_{t} \widetilde{X}_{t}^{(i-1)},\\ \widetilde{w}_{t}=\frac{\langle\widetilde{X}_{t}^{(i-1)},\hat{v}_{t-1}+w_{t}X _{t}^{(i-1)}\rangle}{\|\widetilde{X}_{t}^{(i-1)}\|_{2}^{2}},\\ \hat{u}_{t}=\hat{v}_{t-1}+w_{t}X_{t}^{(i-1)}-\widetilde{w}_{t}\widetilde{X}_{ t}^{(i-1)}\end{cases} \tag{24}\]

Here, we use modulo \(N_{i-1}\) indexing for (the subscripts of) \(w,\widetilde{w},X^{(i-1)}\), and \(\widetilde{X}^{(i-1)}\). We call the combination of (17) and (24) the \(r\)-th order data alignment procedure, which costs \(O(rmN_{i-1})\) operations. Applying (19) to the output \(\widetilde{w}\) as before, the quantization error consists of two parts:

\[X^{(i-1)}w-\widetilde{X}^{(i-1)}\widetilde{q}=X^{(i-1)}w-\widetilde{X}^{(i-1 )}\widetilde{w}+\widetilde{X}^{(i-1)}(\widetilde{w}-\widetilde{q})=\hat{u}_{rN _{i-1}}+\widetilde{u}_{N_{i-1}}. \tag{25}\]

This version of SPFQ with order \(r\) is summarized in Algorithm 2. In Section 3, we prove that the data alignment error \(\hat{u}_{rN_{i-1}}=X^{(i-1)}w-\widetilde{X}^{(i-1)}\widetilde{w}\) decays exponentially in order \(r\).

## 3. Error Bounds for SPFQ with Infinite Alphabets

We can now begin analyzing the errors associated with the above variants of SPFQ. On the one hand, in Algorithm 1, since data is perfectly aligned by solving (22), we only have to bound the quantization error \(\widetilde{u}_{N_{i-1}}\) generated by procedure (19). On the other hand, Algorithm 2 has a faster implementation provided \(r<m\), but introduces an extra error \(\hat{u}_{rN_{i-1}}\) arising from the \(r\)-th order data alignment. Thus, to control the error bounds for this version of SPFQ, we first bound \(\widetilde{u}_{N_{i-1}}\) and \(\hat{u}_{rN_{i-1}}\) appearing in (23) and (25).

**Lemma 3.1** (Quantization error).: _Assuming that the first \(i-1\) layers have been quantized, let \(X^{(i-1)}\), \(\widetilde{X}^{(i-1)}\) be as in (11) and \(w\in\mathbb{R}^{N_{i-1}}\) be the weights associated with a neuron in the \(i\)-th layer, i.e. a column of \(W^{(i)}\in\mathbb{R}^{N_{i-1}\times N_{i}}\). Suppose \(\widetilde{w}\) is either the solution of (22) or
the output of (24). Quantize \(\widetilde{w}\) using (19) with alphabets \(\mathcal{A}=\mathcal{A}_{\infty}^{\delta}\) as in (4). Then, for any \(p\in\mathbb{N}\),_

\[\|\widetilde{u}_{N_{i-1}}\|_{2}\leq\delta\sqrt{2\pi pm\log N_{i-1}}\max_{1\leq j \leq N_{i-1}}\|\widetilde{X}_{j}^{(i-1)}\|_{2} \tag{26}\]

_holds with probability at least \(1-\frac{\sqrt{2}m}{N_{i-1}^{p}}\)._

Proof.: We first show that

\[\widetilde{u}_{t}\leq_{\mathrm{cx}}\mathcal{N}(0,\Sigma_{t}) \tag{27}\]

holds for all \(1\leq t\leq N_{i-1}\), where \(\Sigma_{t}\) is defined recursively as follows

\[\Sigma_{t}:=P_{\widetilde{X}_{t}^{(i-1)\perp}}\Sigma_{t-1}P_{\widetilde{X}_{t }^{(i-1)\perp}}+\frac{\pi\delta^{2}}{2}\widetilde{X}_{t}^{(i-1)}\widetilde{X} _{t}^{(i-1)\top}\quad\text{with}\quad\Sigma_{0}:=0.\]

At the \(t\)-th step of quantizing \(\widetilde{w}\), by (19), we have \(\widetilde{u}_{t}=\widetilde{u}_{t-1}+(\widetilde{w}_{t}-\widetilde{q}_{t}) \widetilde{X}_{t}^{(i-1)}\). Define

\[h_{t}:=\widetilde{u}_{t-1}+\widetilde{w}_{t}\widetilde{X}_{t}^{(i-1)}\quad \text{and}\quad v_{t}:=\frac{\langle\widetilde{X}_{t}^{(i-1)},h_{t}\rangle}{ \|\widetilde{X}_{t}^{(i-1)}\|_{2}^{2}}. \tag{28}\]

It follows that

\[\widetilde{u}_{t}=h_{t}-\widetilde{q}_{t}\widetilde{X}_{t}^{(i-1)} \tag{29}\]

and (19) implies

\[\widetilde{q}_{t}=\mathcal{Q}_{\mathrm{StocQ}}\Bigg{(}\frac{\langle\widetilde {X}_{t}^{(i-1)},h_{t}\rangle}{\|\widetilde{X}_{t}^{(i-1)}\|_{2}^{2}}\Bigg{)}= \mathcal{Q}_{\mathrm{StocQ}}(v_{t}). \tag{30}\]

Since \(\mathcal{A}=\mathcal{A}_{\infty}^{\delta}\), \(\mathbb{E}\mathcal{Q}_{\mathrm{StocQ}}(z)=z\) for all \(z\in\mathbb{R}\). Moreover, conditioning on \(\widetilde{u}_{t-1}\) in (28), \(h_{t}\) and \(v_{t}\) are fixed and thus one can get

\[\mathbb{E}(\mathcal{Q}_{\mathrm{StocQ}}(v_{t})|\widetilde{u}_{t-1})=v_{t} \tag{31}\]
and

\[\mathbb{E}(\widetilde{u}_{t}|\widetilde{u}_{t-1}) =\mathbb{E}(h_{t}-\widetilde{q}_{t}\widetilde{X}_{t}^{(i-1)}| \widetilde{u}_{t-1})\] \[=h_{t}-\widetilde{X}_{t}^{(i-1)}\mathbb{E}(\widetilde{q}_{t}| \widetilde{u}_{t-1})\] \[=h_{t}-\widetilde{X}_{t}^{(i-1)}\mathbb{E}(\mathcal{Q}_{\text{ StocQ}}(v_{t})|\widetilde{u}_{t-1})\] \[=h_{t}-v_{t}\widetilde{X}_{t}^{(i-1)}\] \[=h_{t}-\frac{\langle\widetilde{X}_{t}^{(i-1)},h_{t}\rangle}{\| \widetilde{X}_{t}^{(i-1)}\|_{2}^{2}}\widetilde{X}_{t}^{(i-1)}\] \[=\Bigg{(}I-\frac{\widetilde{X}_{t}^{(i-1)}\widetilde{X}_{t}^{(i-1 )\top}}{\|\widetilde{X}_{t}^{(i-1)}\|_{2}^{2}}\Bigg{)}h_{t}\] \[=P_{\widetilde{X}_{t}^{(i-1)\perp}}(h_{t}).\]

The identity above indicates that the approximation error \(\widetilde{u}_{t}\) can be split into two parts: its conditional mean \(P_{\widetilde{X}_{t}^{(i-1)\perp}}(h_{t})\) and a random perturbation. Specifically, applying (29) and (7), we obtain

\[\widetilde{u}_{t}=P_{\widetilde{X}_{t}^{(i-1)\perp}}(h_{t})+P_{\widetilde{X}_ {t}^{(i-1)}}(h_{t})-\widetilde{q}_{t}\widetilde{X}_{t}^{(i-1)}=P_{\widetilde{X }_{t}^{(i-1)\perp}}(h_{t})+R_{t}\widetilde{X}_{t}^{(i-1)} \tag{32}\]

where

\[R_{t}:=v_{t}-\widetilde{q}_{t}.\]

Further, combining (30) and (31), we have

\[\mathbb{E}(R_{t}|\widetilde{u}_{t-1})=v_{t}-\mathbb{E}(\widetilde{q}_{t}| \widetilde{u}_{t-1})=v_{t}-\mathbb{E}(\mathcal{Q}_{\text{StocQ}}(v_{t})| \widetilde{u}_{t-1})=0\]

and \(|R_{t}|=|v_{t}-\mathcal{Q}_{\text{StocQ}}(v_{t})|\leq\delta\). Lemma A.5 yields that, conditioning on \(\widetilde{u}_{t-1}\),

\[R_{t}\leq_{\text{cx}}\mathcal{N}\Big{(}0,\frac{\pi\delta^{2}}{2}\Big{)}. \tag{33}\]

Now, we are ready to prove (27) by induction on \(t\). When \(t=1\), we have \(h_{1}=\widetilde{w}_{1}\widetilde{X}_{1}^{(i-1)}\). We can deduce from (32) and (33) that \(\widetilde{u}_{1}=P_{\widetilde{X}_{1}^{(i-1)\perp}}(\widetilde{w}_{1} \widetilde{X}_{1}^{(i-1)})+R_{1}\widetilde{X}_{1}^{(i-1)}=R_{1}\widetilde{X}_{ 1}^{(i-1)}\) with \(R_{1}\leq_{\text{cx}}\mathcal{N}\Big{(}0,\frac{\pi\delta^{2}}{2}\Big{)}\). Applying Lemma A.3, we obtain \(\widetilde{u}_{1}\leq_{\text{cx}}\mathcal{N}(0,\Sigma_{1})\). Next, assume that (27) holds for \(t-1\) with \(t\geq 2\). By the induction hypothesis, we have \(\widetilde{u}_{t-1}\leq_{\text{cx}}\mathcal{N}(0,\Sigma_{t-1})\). Using Lemma A.3 again, we get

\[P_{\widetilde{X}_{t}^{(i-1)\perp}}(h_{t}) =P_{\widetilde{X}_{t}^{(i-1)\perp}}(\widetilde{u}_{t-1}+\widetilde {w}_{t}\widetilde{X}_{t}^{(i-1)})\] \[\leq_{\text{cx}}\mathcal{N}\Big{(}P_{\widetilde{X}_{t}^{(i-1) \perp}}(\widetilde{w}_{t}\widetilde{X}_{t}^{(i-1)}),P_{\widetilde{X}_{t}^{(i-1 )\perp}}\Sigma_{t-1}P_{\widetilde{X}_{t}^{(i-1)\perp}}\Big{)}\] \[=\mathcal{N}\Big{(}0,P_{\widetilde{X}_{t}^{(i-1)\perp}}\Sigma_{t- 1}P_{\widetilde{X}_{t}^{(i-1)\perp}}\Big{)}.\]

Additionally, conditioning on \(\widetilde{u}_{t-1}\), (33) implies

\[R_{t}\widetilde{X}_{t}^{(i-1)}\leq_{\text{cx}}\mathcal{N}\Big{(}0,\frac{\pi \delta^{2}}{2}\widetilde{X}_{t}^{(i-1)}\widetilde{X}_{t}^{(i-1)\top}\Big{)}.\]

Then we apply Lemma A.4 to (32) by taking

\[X=P_{\widetilde{X}_{t}^{(i-1)\perp}}(h_{t}),\,Y=\widetilde{u}_{t},\,W=\mathcal{ N}\Big{(}0,P_{\widetilde{X}_{t}^{(i-1)\perp}}\Sigma_{t-1}P_{\widetilde{X}_{t}^{(i-1) \perp}}\Big{)},\,Z=\mathcal{N}\Big{(}0,\frac{\pi\delta^{2}}{2}\widetilde{X}_{ t}^{(i-1)}\widetilde{X}_{t}^{(i-1)\top}\Big{)}.\]
It follows that

\[\widetilde{u}_{t} \leq_{\mathrm{cx}}W+Z\] \[=\mathcal{N}\Big{(}0,P_{\widetilde{X}_{t}^{(i-1)\perp}}\Sigma_{t-1} P_{\widetilde{X}_{t}^{(i-1)\perp}}+\frac{\pi\delta^{2}}{2}\widetilde{X}_{t}^{(i-1)} \widetilde{X}_{t}^{(i-1)\top}\Big{)}\] \[=\mathcal{N}(0,\Sigma_{t}).\]

Here, we used the independence of \(W\) and \(Z\), and the definition of \(\Sigma_{t}\). This establishes inequality (27) showing that \(\widetilde{u}_{t}\) is dominated by \(\mathcal{N}(0,\Sigma_{t})\) in the convex order, where \(\Sigma_{t}\) is defined recursively using orthogonal projections. So it remains to control the covariance matrix \(\Sigma_{t}\). Recall that \(\Sigma_{t}\) is defined as follows.

\[\Sigma_{t}=P_{\widetilde{X}_{t}^{(i-1)\perp}}\Sigma_{t-1}P_{\widetilde{X}_{t}^ {(i-1)\perp}}+\frac{\pi\delta^{2}}{2}\widetilde{X}_{t}^{(i-1)}\widetilde{X}_{ t}^{(i-1)\top}\quad\text{with}\quad\Sigma_{0}=0.\]

Then we apply Lemma B.1 with \(M_{t}=\Sigma_{t}\), \(z_{t}=\widetilde{X}_{t}^{(i-1)}\), and \(\alpha=\frac{\pi\delta^{2}}{2}\), and conclude that \(\Sigma_{t}\preceq\sigma_{t}^{2}I\) with \(\sigma_{t}^{2}=\frac{\pi\delta^{2}}{2}\max_{1\leq j\leq t}\|\widetilde{X}_{j} ^{(i-1)}\|_{2}^{2}\). Note that \(\widetilde{u}_{t}\leq_{\mathrm{cx}}\mathcal{N}(0,\Sigma_{t})\) and, by Lemma A.2, we have \(\mathcal{N}(0,\Sigma_{t})\leq_{\mathrm{cx}}\mathcal{N}(0,\sigma_{t}^{2}I)\). Then we deduce from the transitivity of \(\leq_{\mathrm{cx}}\) that \(\widetilde{u}_{t}\leq_{\mathrm{cx}}\mathcal{N}(0,\sigma_{t}^{2}I)\). It follows from Lemma B.2 that, for \(\gamma\in(0,1]\) and \(1\leq t\leq N_{i-1}\),

\[\mathrm{P}\bigg{(}\|\widetilde{u}_{t}\|_{\infty}\leq 2\sigma_{t}\sqrt{\log( \sqrt{2}m/\gamma)}\bigg{)}\geq 1-\gamma.\]

Picking \(\gamma=\sqrt{2}mN_{i-1}^{-p}\) and \(t=N_{i-1}\),

\[\|\widetilde{u}_{N_{i-1}}\|_{2}\leq\sqrt{m}\|\widetilde{u}_{N_{i-1}}\|_{\infty }\leq 2\sigma_{N_{i-1}}\sqrt{pm\log N_{i-1}}=\delta\sqrt{2\pi pm\log N_{i-1}} \max_{1\leq j\leq N_{i-1}}\|\widetilde{X}_{j}^{(i-1)}\|_{2}\]

holds with probability exceeding \(1-\sqrt{2}mN_{i-1}^{-p}\). 

Next, we deduce a closed-form expression of \(\hat{u}_{rN_{i-1}}\) showing that \(\|\hat{u}_{rN_{i-1}}\|_{2}\) decays polynomially with respect to \(r\).

**Lemma 3.2** (Data alignment error).: _Assuming that the first \(i-1\) layers have been quantized, let \(X^{(i-1)}\), \(\widetilde{X}^{(i-1)}\) be as in (11) and let \(w\in\mathbb{R}^{N_{i-1}}\) be a neuron in the \(i\)-th layer, i.e. a column of \(W^{(i)}\in\mathbb{R}^{N_{i-1}\times N_{i}}\). Applying the \(r\)-th order data alignment procedure in (17) and (24), we have_

\[\hat{u}_{N_{i-1}}=\sum_{j=1}^{N_{i-1}}w_{j}P_{\widetilde{X}_{N_{i-1}}^{(i-1) \perp}}\ldots P_{\widetilde{X}_{j+1}^{(i-1)\perp}}P_{\widetilde{X}_{j}^{(i-1) \perp}}(X_{j}^{(i-1)}) \tag{34}\]

_and_

\[\hat{u}_{rN_{i-1}}=(P^{(i-1)})^{r-1}\hat{u}_{N_{i-1}} \tag{35}\]

_where \(P^{(i-1)}:=P_{\widetilde{X}_{N_{i-1}}^{(i-1)\perp}}\ldots P_{\widetilde{X}_{2 }^{(i-1)\perp}}P_{\widetilde{X}_{1}^{(i-1)\perp}}\)._

Proof.: We first prove the following identity by induction on \(t\).

\[\hat{u}_{t}=\sum_{j=1}^{t}w_{j}P_{\widetilde{X}_{t}^{(i-1)\perp}}\ldots P_{ \widetilde{X}_{j+1}^{(i-1)\perp}}P_{\widetilde{X}_{j}^{(i-1)\perp}}(X_{j}^{(i-1 )}),\quad 1\leq t\leq N_{i-1}. \tag{36}\]
By (17), the case \(t=1\) is straightforward, since we have

\[\hat{u}_{1} =w_{1}X_{1}^{(i-1)}-\widetilde{w}_{1}\widetilde{X}_{1}^{(i-1)}\] \[=w_{1}X_{1}^{(i-1)}-\frac{\langle\widetilde{X}_{1}^{(i-1)},w_{1}X _{1}^{(i-1)}\rangle}{\|\widetilde{X}_{1}^{(i-1)}\|_{2}^{2}}\widetilde{X}_{1}^{( i-1)}\] \[=w_{1}X_{1}^{(i-1)}-P_{\widetilde{X}_{1}^{(i-1)}}(w_{1}X_{1}^{(i- 1)})\] \[=w_{1}P_{\widetilde{X}_{1}^{(i-1)\perp}}(X_{1}^{(i-1)})\]

where we apply the properties of orthogonal projections in (7) and (8). For \(2\leq t\leq N_{i-1}\), assume that (36) holds for \(t-1\). Then, by (17), one gets

\[\hat{u}_{t} =\hat{u}_{t-1}+w_{t}X_{t}^{(i-1)}-\widetilde{w}_{t}\widetilde{X}_ {t}^{(i-1)}\] \[=\hat{u}_{t-1}+w_{t}X_{t}^{(i-1)}-\frac{\langle\widetilde{X}_{t} ^{(i-1)},\hat{u}_{t-1}+w_{t}X_{t}^{(i-1)}\rangle}{\|\widetilde{X}_{t}^{(i-1)} \|_{2}^{2}}\widetilde{X}_{t}^{(i-1)}\] \[=\hat{u}_{t-1}+w_{t}X_{t}^{(i-1)}-P_{\widetilde{X}_{t}^{(i-1)}}( \hat{u}_{t-1}+w_{t}X_{t}^{(i-1)})\] \[=P_{\widetilde{X}_{t}^{(i-1)\perp}}(\hat{u}_{t-1}+w_{t}X_{t}^{(i- 1)}).\]

Applying the induction hypothesis, we obtain

\[\hat{u}_{t} =P_{\widetilde{X}_{t}^{(i-1)\perp}}(\hat{u}_{t-1})+w_{t}P_{ \widetilde{X}_{t}^{(i-1)\perp}}(X_{t}^{(i-1)})\] \[=\sum_{j=1}^{t-1}w_{j}P_{\widetilde{X}_{t}^{(i-1)\perp}}\dots P_{ \widetilde{X}_{j+1}^{(i-1)\perp}}P_{\widetilde{X}_{j}^{(i-1)\perp}}(X_{j}^{(i -1)})+w_{t}P_{\widetilde{X}_{t}^{(i-1)\perp}}(X_{t}^{(i-1)})\] \[=\sum_{j=1}^{t}w_{j}P_{\widetilde{X}_{t}^{(i-1)\perp}}\dots P_{ \widetilde{X}_{j+1}^{(i-1)\perp}}P_{\widetilde{X}_{j}^{(i-1)\perp}}(X_{j}^{(i -1)}).\]

This completes the proof of (36). In particular, if \(t=N_{i-1}\), then we obtain (34).

Next, we consider \(\hat{u}_{t}\) when \(t>N_{i-1}\). Plugging \(t=N_{i-1}+1\) into (24), and recalling that our indices (except for \(\hat{u}\)) are modulo \(N_{i-1}\), we have

\[\hat{u}_{N_{i-1}+1}=\hat{u}_{N_{i-1}}+\widetilde{w}_{1}\widetilde{X}_{1}^{(i- 1)}-\frac{\langle\widetilde{X}_{1}^{(i-1)},\hat{u}_{N_{i-1}}+\widetilde{w}_{1} \widetilde{X}_{1}^{(i-1)}\rangle}{\|\widetilde{X}_{1}^{(i-1)}\|_{2}^{2}} \widetilde{X}_{1}^{(i-1)}=P_{\widetilde{X}_{1}^{(i-1)\perp}}(\hat{u}_{N_{i-1}}).\]

Similarly, one can show that \(\hat{u}_{N_{i-1}+2}=P_{\widetilde{X}_{2}^{(i-1)\perp}}(\hat{u}_{N_{i-1}+1})=P_ {\widetilde{X}_{2}^{(i-1)\perp}}P_{\widetilde{X}_{1}^{(i-1)\perp}}\hat{u}_{N_{ i-1}}\). Repeating this argument for all \(N_{i-1}<t\leq rN_{i-1}\), we can derive (35). 

Combining Lemma 3.1 and Lemma 3.2, we can derive a recursive relation between the error in the current layer and that of the previous layer.

**Theorem 3.3**.: _Let \(\Phi\) be an L-layer neural network as in (3) where the activation function is \(\varphi^{(i)}(x)=\rho(x):=\max\{0,x\}\) for \(1\leq i\leq L\). Let \(\mathcal{A}=\mathcal{A}_{\infty}^{\delta}\) be as in (4) and \(p\in\mathbb{N}\). \((a)\) If we quantize \(\Phi\) using Algorithm 1, then, for each \(2\leq i\leq L\),_

\[\max_{1\leq j\leq N_{i}}\|X^{(i-1)}W_{j}^{(i)}-\widetilde{X}^{(i- 1)}Q_{j}^{(i)}\|_{2}\leq\delta\sqrt{2\pi pm\log N_{i-1}}\max_{1\leq j\leq N_{ i-1}}\|X_{j}^{(i-1)}\|_{2}\] \[+\delta\sqrt{2\pi pm\log N_{i-1}}\max_{1\leq j\leq N_{i-1}}\|X^ {(i-2)}W_{j}^{(i-1)}-\widetilde{X}^{(i-2)}Q_{j}^{(i-1)}\|_{2}.\]
_holds with probability at least \(1-\frac{\sqrt{2}mN_{i}}{N_{i-1}^{p}}\)._

\((b)\) _If we quantize \(\Phi\) using Algorithm 2, then, for each \(2\leq i\leq L\),_

\[\max_{1\leq j\leq N_{i}}\|X^{(i-1)}W_{j}^{(i)}-\widetilde{X}^{(i-1 )}Q_{j}^{(i)}\|_{2}\leq\delta\sqrt{2\pi pm\log N_{i-1}}\max_{1\leq j\leq N_{i-1 }}\|X_{j}^{(i-1)}\|_{2}\] \[+\Big{(}N_{i-1}\|W^{(i)}\|_{\max}\|P^{(i-1)}\|_{2}^{r-1}+\delta \sqrt{2\pi pm\log N_{i-1}}\Big{)}\max_{1\leq j\leq N_{i-1}}\|X^{(i-2)}W_{j}^{(i -1)}-\widetilde{X}^{(i-2)}Q_{j}^{(i-1)}\|_{2}\]

_holds with probability exceeding \(1-\frac{\sqrt{2}mN_{i}}{N_{i-1}^{p}}\). Here, \(P^{(i-1)}\) is defined in Lemma 3.2._

Proof.: \((a)\) Note that, for each \(1\leq j\leq N_{i}\), the \(j\)-th columns \(W_{j}^{(i)}\) and \(Q_{j}^{(i)}\) represent a neuron and its quantized version respectively. Applying (23) and (26), we obtain

\[\mathrm{P}\Big{(}\|X^{(i-1)}W_{j}^{(i)}-\widetilde{X}^{(i-1)}Q_{j}^{(i)}\|_{2 }\leq\delta\sqrt{2\pi pm\log N_{i-1}}\max_{1\leq j\leq N_{i-1}}\|\widetilde{X} _{j}^{(i-1)}\|_{2}\Big{)}\geq 1-\frac{\sqrt{2}m}{N_{i-1}^{p}}.\]

Taking a union bound over all \(j\),

\[\max_{1\leq j\leq N_{i}}\|X^{(i-1)}W_{j}^{(i)}-\widetilde{X}^{(i-1)}Q_{j}^{(i )}\|_{2}\leq\delta\sqrt{2\pi pm\log N_{i-1}}\max_{1\leq j\leq N_{i-1}}\| \widetilde{X}_{j}^{(i-1)}\|_{2}\]

holds with probability at least \(1-\frac{\sqrt{2}mN_{i}}{N_{i-1}^{p}}\). By the triangle inequality, we have

\[\max_{1\leq j\leq N_{i-1}}\|\widetilde{X}_{j}^{(i-1)}\|_{2} \leq\max_{1\leq j\leq N_{i-1}}\|X_{j}^{(i-1)}\|_{2}+\max_{1\leq j \leq N_{i-1}}\|X_{j}^{(i-1)}-\widetilde{X}_{j}^{(i-1)}\|_{2}\] \[=\max_{1\leq j\leq N_{i-1}}\|X_{j}^{(i-1)}\|_{2}+\max_{1\leq j \leq N_{i-1}}\|\rho(X^{(i-2)}W_{j}^{(i-1)})-\rho(\widetilde{X}^{(i-2)}Q_{j}^{( i-1)})\|_{2} \tag{37}\] \[\leq\max_{1\leq j\leq N_{i-1}}\|X_{j}^{(i-1)}\|_{2}+\max_{1\leq j \leq N_{i-1}}\|X^{(i-2)}W_{j}^{(i-1)}-\widetilde{X}^{(i-2)}Q_{j}^{(i-1)}\|_{2}\]

It follows that, with probability at least \(1-\frac{\sqrt{2}mN_{i}}{N_{i-1}^{p}}\),

\[\max_{1\leq j\leq N_{i}}\|X^{(i-1)}W_{j}^{(i)}-\widetilde{X}^{(i- 1)}Q_{j}^{(i)}\|_{2}\leq\delta\sqrt{2\pi pm\log N_{i-1}}\max_{1\leq j\leq N_{ i-1}}\|X_{j}^{(i-1)}\|_{2}\] \[+\delta\sqrt{2\pi pm\log N_{i-1}}\max_{1\leq j\leq N_{i-1}}\|X^{(i -2)}W_{j}^{(i-1)}-\widetilde{X}^{(i-2)}Q_{j}^{(i-1)}\|_{2}.\]
\((b)\) Applying Lemma 3.2 with \(w=W_{j}^{(i)}\) and using the fact that \(\|P\|_{2}\leq 1\) for any orthogonal projection \(P\), we have

\[\|\tilde{u}_{N_{i-1}}\|_{2} =\Big{\|}\sum_{k=1}^{N_{i-1}}W_{kj}^{(i)}P_{\widetilde{X}_{N_{i-1} }^{(i-1)\perp}}\ldots P_{\widetilde{X}_{k+1}^{(i-1)\perp}}P_{\widetilde{X}_{k}^ {(i-1)\perp}}(X_{k}^{(i-1)})\Big{\|}_{2}\] \[\leq\sum_{k=1}^{N_{i-1}}|W_{kj}^{(i)}|\Big{\|}P_{\widetilde{X}_{k} ^{(i-1)\perp}}(X_{k}^{(i-1)})\Big{\|}_{2}\] \[=\sum_{k=1}^{N_{i-1}}|W_{kj}^{(i)}|\Big{\|}P_{\widetilde{X}_{k}^{ (i-1)\perp}}(X_{k}^{(i-1)}-\widetilde{X}_{k}^{(i-1)})\Big{\|}_{2}\] \[\leq N_{i-1}\|W_{j}^{(i)}\|_{\infty}\max_{1\leq j\leq N_{i-1}}\|X _{j}^{(i-1)}-\widetilde{X}_{j}^{(i-1)}\|_{2}\] \[=N_{i-1}\|W_{j}^{(i)}\|_{\infty}\max_{1\leq j\leq N_{i-1}}\|\rho( X^{(i-2)}W_{j}^{(i-1)})-\rho(\widetilde{X}^{(i-2)}Q_{j}^{(i-1)})\|_{2} \tag{38}\] \[\leq N_{i-1}\|W^{(i)}\|_{\max}\max_{1\leq j\leq N_{i-1}}\|X^{(i-2) }W_{j}^{(i-1)}-\widetilde{X}^{(i-2)}Q_{j}^{(i-1)}\|_{2}.\]

Then it follows from (25), (26), (37), and (38) that

\[\|X^{(i-1)}W_{j}^{(i)}-\widetilde{X}^{(i-1)}Q_{j}^{(i)}\|_{2}\] \[\leq\|\hat{u}_{r_{N_{i-1}}}\|_{2}+\|\widetilde{u}_{N_{i-1}}\|_{2}\] \[\leq\|P^{(i-1)}\|_{2}^{r-1}\|\hat{u}_{N_{i-1}}\|_{2}+\delta\sqrt {2\pi pm\log N_{i-1}}\max_{1\leq j\leq N_{i-1}}\|\widetilde{X}_{j}^{(i-1)}\|_{2}\] \[\leq N_{i-1}\|W^{(i)}\|_{\max}\|P^{(i-1)}\|_{2}^{r-1}\max_{1\leq j \leq N_{i-1}}\|X^{(i-2)}W_{j}^{(i-1)}-\widetilde{X}^{(i-2)}Q_{j}^{(i-1)}\|_{2}+ \delta\sqrt{2\pi pm\log N_{i-1}}\] \[\times\Big{(}\max_{1\leq j\leq N_{i-1}}\|X_{j}^{(i-1)}\|_{2}+\max _{1\leq j\leq N_{i-1}}\|X^{(i-2)}W_{j}^{(i-1)}-\widetilde{X}^{(i-2)}Q_{j}^{(i-1 )}\|_{2}\Big{)}\]

holds with probability at least \(1-\sqrt{2}mN_{i-1}^{-p}\). By a union bound over all \(j\), we obtain that

\[\max_{1\leq j\leq N_{i}}\|X^{(i-1)}W_{j}^{(i)}-\widetilde{X}^{(i- 1)}Q_{j}^{(i)}\|_{2}\leq\delta\sqrt{2\pi pm\log N_{i-1}}\max_{1\leq j\leq N_{ i-1}}\|X_{j}^{(i-1)}\|_{2}\] \[+\Big{(}N_{i-1}\|W^{(i)}\|_{\max}\|P^{(i-1)}\|_{2}^{r-1}+\delta \sqrt{2\pi pm\log N_{i-1}}\Big{)}\max_{1\leq j\leq N_{i-1}}\|X^{(i-2)}W_{j}^{(i -1)}-\widetilde{X}^{(i-2)}Q_{j}^{(i-1)}\|_{2}\]

holds with probability exceeding \(1-\frac{\sqrt{2}mN_{i}}{N_{i-1}^{p}}\). 

Applying Theorem 3.3 inductively for all layers, one can obtain an error bound for quantizing the whole neural network.

**Corollary 3.4**.: _Let \(\Phi\) be an \(L\)-layer neural network as in (3) where the activation function is \(\varphi^{(i)}(x)=\rho(x):=\max\{0,x\}\) for \(1\leq i\leq L\). Let \(\mathcal{A}=\mathcal{A}_{\infty}^{\delta}\) be as in (4) and \(p\in\mathbb{N}\). \((a)\) If we quantize \(\Phi\) using Algorithm 1, then_

\[\max_{1\leq j\leq N_{L}}\|\Phi(X)_{j}-\widetilde{\Phi}(X)_{j}\|_{2}\leq\sum_{i= 0}^{L-1}(2\pi pm\delta^{2})^{\frac{L-i}{2}}\Big{(}\prod_{k=i}^{L-1}\log N_{k} \Big{)}^{\frac{1}{2}}\max_{1\leq j\leq N_{i}}\|X_{j}^{(i)}\|_{2} \tag{39}\]

_holds with probability at least \(1-\sum_{i=1}^{L}\frac{\sqrt{2}mN_{i}}{N_{i-1}^{p}}\)._
\((b)\) _If we quantize \(\Phi\) using Algorithm 2, then_

\[\max_{1\leq j\leq N_{L}}\|\Phi(X)_{j}-\widetilde{\Phi}(X)_{j}\|_{2}\leq \tag{40}\] \[\sum_{i=0}^{L-1}\delta\sqrt{2\pi pm\log N_{i}}\max_{1\leq j\leq N_{ i}}\|X_{j}^{(i)}\|_{2}\prod_{k=i+1}^{L-1}\Big{(}N_{k}\|W^{(k+1)}\|_{\max}\|P^{(k)} \|_{2}^{r-1}+\delta\sqrt{2\pi pm\log N_{k}}\Big{)}\]

_holds with probability at least \(1-\sum_{i=1}^{L}\frac{\sqrt{2}mN_{i}}{N_{i-1}^{p}}\). Here, \(P^{(k)}=P_{\widetilde{X}_{N_{k}}^{(k)\perp}}\ldots P_{\widetilde{X}_{2}^{(k) \perp}}P_{\widetilde{X}_{1}^{(k)\perp}}\) is defined in Lemma 3.2._

Proof.: (a) For \(1\leq j\leq N_{L}\), by (11), we have

\[\Phi(X)_{j}=X_{j}^{(L)}=\rho(X^{(L-1)}W_{j}^{(L)})\quad\text{and}\quad \widetilde{\Phi}(X)_{j}=\widetilde{X}_{j}^{(L)}=\rho(\widetilde{X}^{(L-1)}Q_ {j}^{(L)})\]

where \(W_{j}^{(L)}\) and \(Q_{j}^{(L)}\) are the \(j\)-th neuron in the \(L\)-th layer and its quantized version respectively. It follows from part (a) of Theorem 3.3 with \(i=L\) that

\[\max_{1\leq j\leq N_{L}}\|\Phi(X)_{j}-\widetilde{\Phi}(X)_{j}\|_ {2}=\max_{1\leq j\leq N_{L}}\|\rho(X^{(L-1)}W_{j}^{(L)})-\rho(\widetilde{X}^{( L-1)}Q_{j}^{(L)})\|_{2}\] \[\leq\max_{1\leq j\leq N_{L}}\|X^{(L-1)}W_{j}^{(L)}-\widetilde{X}^ {(L-1)}Q_{j}^{(L)}\|_{2}\] \[\leq\delta\sqrt{2\pi pm\log N_{L-1}}\max_{1\leq j\leq N_{L-1}}\|X _{j}^{(L-1)}\|_{2}\] \[+\delta\sqrt{2\pi pm\log N_{L-1}}\max_{1\leq j\leq N_{L-1}}\|X^{( L-2)}W_{j}^{(L-1)}-\widetilde{X}^{(L-2)}Q_{j}^{(L-1)}\|_{2}.\]

holds with probability at least \(1-\frac{\sqrt{2}mN_{L}}{N_{L-1}^{p}}\). Moreover, by applying part (a) of Theorem 3.3 with \(i=L-1\) to the result above, we obtain that

\[\max_{1\leq j\leq N_{L}}\|\Phi(X)_{j}-\widetilde{\Phi}(X)_{j}\|_ {2}\leq\delta\sqrt{2\pi pm\log N_{L-1}}\max_{1\leq j\leq N_{L-1}}\|X_{j}^{(L-1 )}\|_{2}+2\pi pm\delta^{2}\] \[\quad\times\sqrt{\log N_{L-1}\log N_{L-2}}\Big{(}\max_{1\leq j \leq N_{L-2}}\|X_{j}^{(L-2)}\|_{2}+\max_{1\leq j\leq N_{i-1}}\|X^{(i-2)}W_{j}^ {(i-1)}-\widetilde{X}^{(i-2)}Q_{j}^{(i-1)}\|_{2}\Big{)}\]

holds with probability at least \(1-\frac{\sqrt{2}mN_{L}}{N_{L-1}^{p}}-\frac{\sqrt{2}mN_{L-1}}{N_{L-2}^{p}}\). Repeating this argument inductively for \(i=L-2,L-3,\ldots,1\), one can derive

\[\max_{1\leq j\leq N_{L}}\|\Phi(X)_{j}-\widetilde{\Phi}(X)_{j}\|_{2}\leq\sum_{i =0}^{L-1}(2\pi pm\delta^{2})^{\frac{L-i}{2}}\Big{(}\prod_{k=i}^{L-1}\log N_{k} \Big{)}^{\frac{1}{2}}\max_{1\leq j\leq N_{i}}\|X_{j}^{(i)}\|_{2}\]

with probability at least \(1-\sum_{i=1}^{L}\frac{\sqrt{2}mN_{i}}{N_{i-1}^{p}}\).
(b) The proof of (40) is similar to the one we had in part (a) except that we need to use part (b) of Theorem 3.3 this time. Indeed, for the case of \(i=L\),

\[\max_{1\leq j\leq N_{L}}\|\Phi(X)_{j}-\widetilde{\Phi}(X)_{j}\|_{2} =\max_{1\leq j\leq N_{L}}\|\rho(X^{(L-1)}W_{j}^{(L)})-\rho(\widetilde{X}^{(L-1) }Q_{j}^{(L)})\|_{2}\] \[\leq\max_{1\leq j\leq N_{L}}\|X^{(L-1)}W_{j}^{(L)}-\widetilde{X}^ {(L-1)}Q_{j}^{(L)}\|_{2}\] \[\leq\delta\sqrt{2\pi pm\log N_{L-1}}\max_{1\leq j\leq N_{L-1}}\|X _{j}^{(L-1)}\|_{2}+\Big{(}N_{L-1}\|W^{(L)}\|_{\max}\|P^{(L-1)}\|_{2}^{r-1}\] \[+\delta\sqrt{2\pi pm\log N_{L-1}}\Big{)}\max_{1\leq j\leq N_{L-1} }\|X^{(L-2)}W_{j}^{(L-1)}-\widetilde{X}^{(L-2)}Q_{j}^{(L-1)}\|_{2}\]

holds with probability exceeding \(1-\frac{\sqrt{2}mN_{L}}{N_{L-1}^{r}}\). Then (40) follows by inductively using part (b) of Theorem 3.3 with \(i=L-1,L-2,\ldots,1\). 

**Remarks on the error bounds.** A few comments are in order regarding the error bounds associated with Corollary 3.4. First, let us consider the difference between the error bounds (39) and (40). As (40) deals with imperfect data alignment, it involves a term that bounds the mismatch between the quantized and unquantized networks. This term is controlled by the quantity \(\|P^{(k)}\|_{2}^{r-1}\), which is expected to be small when the order \(r\) is sufficiently large provided \(\|P^{(k)}\|_{2}<1\). In other words, one expects this term to be dominated by the error due to quantization. To get a sense for whether this intuition is valid, consider the case where \(\widetilde{X}_{1}^{(k)},\widetilde{X}_{2}^{(k)},\ldots,\widetilde{X}_{N_{k}}^ {(k)}\) are i.i.d. standard Gaussian vectors. Then Lemma B.3 implies that, with high probability,

\[\|P^{(k)}\|_{2}^{r-1}\lesssim\Big{(}1-\frac{c}{m}\Big{)}^{\frac{(r-1)N_{k}}{1 0}}=\Big{(}1-\frac{c}{m}\Big{)}^{\frac{-m}{c}.\frac{-c(r-1)N_{k}}{10m}}\leq e ^{-\frac{c(r-1)N_{k}}{10m}}\]

where \(c>0\) is a constant. In this case, \(\|P^{(k)}\|_{2}^{r-1}\) decays exponentially with respect to \(r\) with a favorable dependence on the overparametrization \(\frac{N}{m}\). In other words, here, even with a small order \(r\), the error bounds in (39) and (40) are quite similar.

Keeping this in mind, our next objective is to assess the quality of these error bounds. We will accomplish this by examining the _relative error_ connected to the quantization of a neural network. Specifically, we will concentrate on evaluating the relative error associated with (39) since a similar derivation can be applied to (40).

We begin with the observation that both absolute error bounds (39) and (40) in Corollary 3.4 only involve randomness due to the stochastic quantizer \(\mathcal{Q}_{\mathrm{StocQ}}\). In particular, there is no randomness assumption on either the weights or the activations. However, to evaluate the relative error, we suppose that each \(W^{(i)}\in\mathbb{R}^{N_{i-1}\times N_{i}}\) has i.i.d. \(\mathcal{N}(0,1)\) entries and \(\{W^{(i)}\}_{i=1}^{L}\) are independent. One needs to make an assumption of this type in order to facilitate the calculation, and more importantly, to avoid adversarial scenarios where the weights are chosen to be in the null-space of the data matrix \(\widetilde{X}^{(i)}\). We obtain the following corollary which shows that the relative error decays with the overparametrization of the neural network.

**Corollary 3.5**.: _Let \(\Phi\) be an \(L\)-layer neural network as in (3) where the activation function is \(\varphi^{(i)}(x)=\rho(x):=\max\{0,x\}\) for \(1\leq i\leq L\). Suppose the weight matrix \(W^{(i)}\) has i.i.d. \(\mathcal{N}(0,1)\) entries and \(\{W^{(i)}\}_{i=1}^{L}\) are independent. Let \(X\in\mathbb{R}^{m\times N_{0}}\) be the input data and \(X^{(i)}=\Phi^{(i)}(X)\in\mathbb{R}^{m\times N_{i}}\) be the output of the \(i\)-th layer defined in (11). Then the following inequalities hold._
\((a)\) _Let \(p\in\mathbb{N}\) with \(p\geq 2\). For \(1\leq i\leq L\),_

\[\max_{1\leq j\leq N_{i}}\|X_{j}^{(i)}\|_{2}\leq(4p)^{\frac{i}{2}}\Bigl{(}\prod_{ k=1}^{i-1}N_{k}\Bigr{)}^{\frac{1}{2}}\Bigl{(}\prod_{k=0}^{i-1}\log N_{k}\Bigr{)}^{ \frac{1}{2}}\|X\|_{F} \tag{41}\]

_holds with probability at least \(1-\sum_{k=1}^{i}\frac{2N_{k}}{N_{k-1}^{p}}\)._

\((b)\) _For \(1\leq i\leq L\), we have_

\[\mathbb{E}_{\Phi}\|X^{(i)}\|_{F}^{2}\geq\frac{\|X\|_{F}^{2}}{(2\pi)^{i}}\prod_ {k=1}^{i}N_{k} \tag{42}\]

_where \(\mathbb{E}_{\Phi}\) denotes the expectation with respect to the weights of \(\Phi\), that is \(\{W^{(i)}\}_{i=1}^{L}\)._

Proof.: \((a)\) Conditioning on \(X^{(i-1)}\), the function \(f(z):=\|\rho(X^{(i-1)}z)\|_{2}\) is Lipschitz with Lipschitz constant \(L_{f}:=\|X^{(i-1)}\|_{2}\leq\|X^{(i-1)}\|_{F}\) and \(\|X_{j}^{(i)}\|_{2}=\|\rho(X^{(i-1)}W_{j}^{(i)})\|_{2}=f(W_{j}^{(i)})\) with \(W_{j}^{(i)}\sim\mathcal{N}(0,I)\). Applying Lemma B.4 to \(f\) with \(X=W_{j}^{(i)}\), Lipschitz constant \(L_{f}\), and \(\alpha=\sqrt{2p\log N_{i-1}}\|X^{(i-1)}\|_{F}\), we obtain

\[\mathrm{P}\Bigl{(}\|X_{j}^{(i)}\|_{2}-\mathbb{E}(\|X_{j}^{(i)}\|_{2}\mid X^{( i-1)})\bigr{|}\leq\sqrt{2p\log N_{i-1}}\|X^{(i-1)}\|_{F}\,\Big{|}\,X^{(i-1)} \Bigr{)}\geq 1-\frac{2}{N_{i-1}^{p}}. \tag{43}\]

Using Jensen's inequality and the identity \(\mathbb{E}(\|\rho(X^{(i-1)}W_{j}^{(i)})\|_{2}^{2}\mid X^{(i-1)})=\frac{1}{2}\| X^{(i-1)}\|_{F}^{2}\), we have

\[\mathbb{E}(\|X_{j}^{(i)}\|_{2}\mid X^{(i-1)}) \leq\Bigl{(}\mathbb{E}(\|X_{j}^{(i)}\|_{2}^{2}\mid X^{(i-1)}) \Bigr{)}^{\frac{1}{2}}\] \[=\Bigl{(}\mathbb{E}(\|\rho(X^{(i-1)}W_{j}^{(i)})\|_{2}^{2}\mid X^ {(i-1)})\Bigr{)}^{\frac{1}{2}}\] \[=\frac{1}{\sqrt{2}}\|X^{(i-1)}\|_{F}.\]

It follows from the inequality above and (43) that, conditioning on \(X^{(i-1)}\),

\[\|X_{j}^{(i)}\|_{2}\leq\Bigl{(}\frac{1}{\sqrt{2}}+\sqrt{2p\log N_{i-1}}\Bigr{)} \|X^{(i-1)}\|_{F}\leq 2\sqrt{p\log N_{i-1}}\|X^{(i-1)}\|_{F}\]

holds with probability at least \(1-\frac{2}{N_{i-1}^{p}}\). Conditioning on \(X^{(i-1)}\) and taking a union bound over \(1\leq j\leq N_{i}\), with probability exceeding \(1-\frac{2N_{i}}{N_{i-1}^{p}}\), we have

\[\|X^{(i)}\|_{F}\leq\sqrt{N_{i}}\max_{1\leq j\leq N_{i}}\|X_{j}^{(i)}\|_{2}\leq 2 \sqrt{pN_{i}\log N_{i-1}}\|X^{(i-1)}\|_{F}. \tag{44}\]

Applying (44) for indices \(i,i-1,\ldots,1\) recursively, we obtain (41).
\((b)\) Applying Jensen's inequality and Proposition B.5, we have

\[\mathbb{E}(\|X_{j}^{(i)}\|_{2}^{2}\mid X^{(i-1)}) =\mathbb{E}(\|\rho(X^{(i-1)}W_{j}^{(i)})\|_{2}^{2}\mid X^{(i-1)})\] \[\geq\Big{(}\mathbb{E}(\|\rho(X^{(i-1)}W_{j}^{(i)})\|_{2}\mid X^{(i -1)})\Big{)}^{2}\] \[\geq\frac{\operatorname{tr}(X^{(i-1)}X^{(i-1)\top})}{2\pi}\] \[=\frac{\|X^{(i-1)}\|_{F}^{2}}{2\pi}.\]

By the law of total expectation, we obtain \(\mathbb{E}_{\Phi}\|X_{j}^{(i)}\|_{2}^{2}\geq\frac{1}{2\pi}\mathbb{E}_{\Phi}\|X ^{(i-1)}\|_{F}^{2}\) and thus

\[\mathbb{E}_{\Phi}\|X^{(i)}\|_{F}^{2}=\sum_{j=1}^{N_{i}}\mathbb{E}_{\Phi}\|X_{j }^{(i)}\|_{2}^{2}\geq\frac{N_{i}}{2\pi}\mathbb{E}_{\Phi}\|X^{(i-1)}\|_{F}^{2}. \tag{45}\]

Then (42) follows immediately by applying (45) recursively. 

Now we are ready to evaluate the relative error associated with (39). It follows from (39) and the Cauchy-Schwarz inequality that, with high probability,

\[\frac{\|\Phi(X)-\widetilde{\Phi}(X)\|_{F}^{2}}{\mathbb{E}_{\Phi} \|\Phi(X)\|_{F}^{2}} \leq\frac{N_{L}\max_{1\leq j\leq N_{L}}\|\Phi(X)_{j}-\widetilde{ \Phi}(X)_{j}\|_{2}^{2}}{\mathbb{E}_{\Phi}\|\Phi(X)\|_{F}^{2}}\] \[\leq\frac{N_{L}}{\mathbb{E}_{\Phi}\|\Phi(X)\|_{F}^{2}}\Big{(} \sum_{i=0}^{L-1}(2\pi pm\delta^{2})^{\frac{L-i}{2}}\Big{(}\prod_{k=i}^{L-1} \log N_{k}\Big{)}^{\frac{1}{2}}\max_{1\leq j\leq N_{i}}\|X_{j}^{(i)}\|_{2} \Big{)}^{2} \tag{46}\] \[\leq\frac{LN_{L}}{\mathbb{E}_{\Phi}\|\Phi(X)\|_{F}^{2}}\sum_{i=0 }^{L-1}(2\pi pm\delta^{2})^{L-i}\Big{(}\prod_{k=i}^{L-1}\log N_{k}\Big{)}\max _{1\leq j\leq N_{i}}\|X_{j}^{(i)}\|_{2}^{2}.\]

By Corollary 3.5, \(\max_{1\leq j\leq N_{i}}\|X_{j}^{(i)}\|_{2}^{2}\leq(4p)^{i}\|X\|_{F}^{2}\log N _{0}\prod_{k=1}^{i-1}(N_{k}\log N_{k})\) with high probability, and \(\mathbb{E}_{\Phi}\|\Phi(X)\|_{F}^{2}=\mathbb{E}_{\Phi}\|X^{(L)}\|_{F}^{2}\geq \frac{\|X\|_{F}^{2}}{(2\pi)^{L}}\prod_{k=1}^{L}N_{k}.\) Plugging these results into (46),

\[\frac{\|\Phi(X)-\widetilde{\Phi}(X)\|_{F}^{2}}{\mathbb{E}_{\Phi} \|\Phi(X)\|_{F}^{2}} \leq L(2\pi)^{L}\Big{(}\prod_{k=0}^{L}\log N_{k}\Big{)}\sum_{i=0 }^{L-1}\frac{(2\pi pm\delta^{2})^{L-i}(4p)^{i}}{\prod_{k=i}^{L-1}N_{k}} \tag{47}\] \[\lesssim\Big{(}\prod_{k=0}^{L}\log N_{k}\Big{)}\sum_{i=0}^{L-1} \prod_{k=i}^{L-1}\frac{m}{N_{k}}\]

gives an upper bound on the relative error of quantization method in Algorithm 1. Further, if we assume \(N_{\min}\leq N_{i}\leq N_{\max}\) for all \(i\), and \(2m\leq N_{\min}\), then (47) becomes

\[\frac{\|\Phi(X)-\widetilde{\Phi}(X)\|_{F}^{2}}{\mathbb{E}_{\Phi} \|\Phi(X)\|_{F}^{2}} \lesssim(\log N_{\max})^{L+1}\sum_{i=0}^{L-1}\Big{(}\frac{m}{N_{ \min}}\Big{)}^{L-i}\] \[\lesssim\frac{m(\log N_{\max})^{L+1}}{N_{\min}}.\]

This high probability estimate indicates that the squared error resulting from quantization decays with the overparametrization of the network, relative to the expected squared norm of the neural network's output. It may be possible to replace the expected squared norm by
the squared norm itself using another high probability estimate. However, we refrain from doing so as the main objective of this computation was to gain insight into the decay of the relative error in generic settings and the expectation suffices for that purpose.

## 4. Error Bounds for SPFQ with Finite Alphabets

Our goal for this section is to relax the assumption that the quantization alphabet used in our algorithms is infinite. We would also like to evaluate the number of elements \(2K\) in our alphabet, and thus the number of bits \(b:=\log_{2}(K)+1\) needed for quantizing each layer. Moreover, for simplicity, here we will only consider Algorithm 1. In this setting, to use a finite quantization alphabet, and still obtain theoretical error bounds, we must guarantee that the argument of the stochastic quantizer in (19) remains smaller than the maximal element in the alphabet. Indeed, if that is the case for all \(t=1,...,N_{i-1}\) then the error bound for our finite alphabet would be identical as for the infinite alphabet. It remains to determine the right size of such a finite alphabet. To that end, we start with Theorem 4.1, which assumes boundedness of all the aligned weights \(\widetilde{w}\) in the \(i\)-th layer, i.e., the solutions of (22), in order to generate an error bound for a finite alphabet of size \(K^{(i)}\gtrsim\sqrt{\log\max\{N_{i-1},N_{i}\}}\).

**Theorem 4.1**.: _Assuming that the first \(i-1\) layers have been quantized, let \(X^{(i-1)}\), \(\widetilde{X}^{(i-1)}\) be as in (11). Let \(p,K^{(i)}\in\mathbb{N}\) and \(\delta>0\) satisfying \(p\geq 3\). Suppose we quantize \(W^{(i)}\) using Algorithm 1 with \(\mathcal{A}=\mathcal{A}_{K^{(i)}}^{\delta}\) and suppose the resulting aligned weights \(\widetilde{W}^{(i)}\) from solving (22) satisfy_

\[\|\widetilde{W}^{(i)}\|_{\max}\leq\frac{1}{2}K^{(i)}\delta. \tag{48}\]

_Then_

\[\max_{1\leq j\leq N_{i}}\|X^{(i-1)}W_{j}^{(i)}-\widetilde{X}^{(i-1)}Q_{j}^{(i) }\|_{2}\leq\delta\sqrt{2\pi pm\log N_{i-1}}\max_{1\leq j\leq N_{i-1}}\| \widetilde{X}_{j}^{(i-1)}\|_{2} \tag{49}\]

_holds with probability at least \(1-\frac{\sqrt{2}mN_{i}}{N_{i-1}^{\prime}}-\sqrt{2}N_{i}\sum\limits_{t=2}^{N_{ i-1}}\exp\Bigl{(}-\frac{(K^{(i)})^{2}\|\widetilde{X}_{t}^{(i-1)}\|_{2}^{2}}{8\pi \max\limits_{1\leq j\leq t-1}\|\widetilde{X}_{j}^{(i-1)}\|_{2}^{2}}\Bigr{)}\)._

Proof.: Fix a neuron \(w:=W_{j}^{(i)}\in\mathbb{R}^{N_{i-1}}\) for some \(1\leq j\leq N_{i}\). By our assumption (48), the aligned weights \(\widetilde{w}\) satisfy \(\|\widetilde{w}\|_{\infty}\leq\frac{1}{2}K^{(i)}\delta\). Then, we perform the iteration (19) in Algorithm 1. At the \(t\)-th step, similar to (28), (30), and (32), we have

\[\widetilde{u}_{t}=P_{\widetilde{X}_{t}^{(i-1)\perp}}(h_{t})+(v_{t}-\widetilde {q}_{t})\widetilde{X}_{t}^{(i-1)}\]

where

\[h_{t}=\widetilde{u}_{t-1}+\widetilde{w}_{t}\widetilde{X}_{t}^{(i-1)},\quad v_ {t}=\frac{\langle\widetilde{X}_{t}^{(i-1)},h_{t}\rangle}{\|\widetilde{X}_{t}^ {(i-1)}\|_{2}^{2}},\quad\text{and}\quad\widetilde{q}_{t}=\mathcal{Q}_{\text{ \rm{StocQ}}}(v_{t}). \tag{50}\]

If \(t=1\), then \(h_{1}=\widetilde{w}_{1}\widetilde{X}_{1}^{(i-1)}\), \(v_{1}=\widetilde{w}_{1}\), and \(\widetilde{q}_{1}=\mathcal{Q}_{\text{\rm{StocQ}}}(v_{1})\). Since \(|v_{1}|=|\widetilde{w}_{1}|\leq\|\widetilde{w}\|_{\infty}\leq\frac{1}{2}K^{(i)}\delta\), we get \(|v_{1}-\widetilde{q}_{1}|\leq\delta\) and the proof technique used for the case \(t=1\) in Lemma 3.1 can be applied here to conclude that \(\widetilde{u}_{1}\leq_{\text{\rm{cx}}}\mathcal{N}(0,\sigma_{1}^{2}I)\) with \(\sigma_{1}^{2}=\frac{\pi\delta^{2}}{2}\|\widetilde{X}_{1}^{(i-1)}\|_{2}^{2}\). Next, for \(t\geq 2\), assume that \(\widetilde{u}_{t-1}\leq_{\text{\rm{cx}}}\mathcal{N}(0,\sigma_{t-1}^{2}I)\) holds where \(\sigma_{t-1}^{2}=\frac{\pi\delta^{2}}{2}\max_{1\leq j\leq t-1}\|\widetilde{X}_ {j}^{(i-1)}\|_{2}^{2}\) is defined as
in Lemma 3.1. It follows from (50) and Lemma A.3 that

\[|v_{t}|=\Big{|}\frac{(\widetilde{X}_{t}^{(i-1)},\widetilde{u}_{t-1})}{\| \widetilde{X}_{t}^{(i-1)}\|_{2}^{2}}+\widetilde{w}_{t}\Big{|}\leq\Big{|}\frac{ (\widetilde{X}_{t}^{(i-1)},\widetilde{u}_{t-1})}{\|\widetilde{X}_{t}^{(i-1)}\| _{2}^{2}}\Big{|}+\|\widetilde{w}\|_{\infty}\leq\Big{|}\frac{(\widetilde{X}_{t} ^{(i-1)},\widetilde{u}_{t-1})}{\|\widetilde{X}_{t}^{(i-1)}\|_{2}^{2}}\Big{|}+ \frac{1}{2}K^{(i)}\delta\]

with \(\frac{(\widetilde{X}_{t}^{(i-1)},\widetilde{u}_{t-1})}{\|\widetilde{X}_{t}^{( i-1)}\|_{2}^{2}}\leq_{\rm cx}\mathcal{N}\Big{(}0,\frac{\sigma_{t-1}^{2}}{\| \widetilde{X}_{t}^{(i-1)}\|_{2}^{2}}\Big{)}\). Then we have, by Lemma B.2, that

\[\mathrm{P}(|v_{t}|\leq K^{(i)}\delta)\geq\mathrm{P}\Big{(}\Big{|}\frac{( \widetilde{X}_{t}^{(i-1)},\widetilde{u}_{t-1})}{\|\widetilde{X}_{t}^{(i-1)}\| _{2}^{2}}\Big{|}\leq\frac{1}{2}K^{(i)}\delta\Big{)}\geq 1-\sqrt{2}\exp\Bigl{(}- \frac{(K^{(i)}\delta)^{2}}{16\sigma_{t-1}^{2}}\|\widetilde{X}_{t}^{(i-1)}\|_{ 2}^{2}\Big{)}.\]

On the event \(\{|v_{t}|\leq K^{(i)}\delta\}\), we can quantize \(v_{t}\) as if the quantizer \(\mathcal{Q}_{\rm StocQ}\) used the infinite alphabet \(\mathcal{A}_{\infty}^{\delta}\). So \(\widetilde{u}_{t}\leq_{\rm cx}\mathcal{N}(0,\sigma_{t}^{2}I)\). Therefore, applying a union bound,

\[\mathrm{P}\Big{(}\widetilde{u}_{N_{i-1}}\leq_{\rm cx}\mathcal{N}(0,\sigma_{N_{ i-1}}^{2}I)\Big{)}\geq 1-\sqrt{2}\sum_{t=2}^{N_{i-1}}\exp\Bigl{(}-\frac{(K^{(i)} \delta)^{2}}{16\sigma_{t-1}^{2}}\|\widetilde{X}_{t}^{(i-1)}\|_{2}^{2}\Big{)}. \tag{51}\]

Conditioning on the event above, that \(\widetilde{u}_{N_{i-1}}\leq_{\rm cx}\mathcal{N}(0,\sigma_{N_{i-1}}^{2}I)\), Lemma B.2 yields for \(\gamma\in(0,1]\)

\[\mathrm{P}\Big{(}\|\widetilde{u}_{N_{i-1}}\|_{\infty}\leq 2\sigma_{N_{i-1}} \sqrt{\log(\sqrt{2}m/\gamma)}\Big{)}\geq 1-\gamma.\]

Setting \(\gamma=\sqrt{2}mN_{i-1}^{-p}\) and recalling (23), we obtain that

\[\|X^{(i-1)}W_{j}^{(i)}-\widetilde{X}^{(i-1)}Q_{j}^{(i)}\|_{2}=\|\widetilde{u} _{N_{i-1}}\|_{2}\leq\sqrt{m}\|\widetilde{u}_{N_{i-1}}\|_{\infty}\leq 2\sigma_{N_{ i-1}}\sqrt{mp\log N_{i-1}} \tag{52}\]

holds with probability at least \(1-\frac{\sqrt{2}m}{N_{i-1}^{p}}\). Combining (51) and (52), for each \(1\leq j\leq N_{i}\),

\[\|X^{(i-1)}W_{j}^{(i)}-\widetilde{X}^{(i-1)}Q_{j}^{(i)}\|_{2}\leq 2\sigma_{N_{ i-1}}\sqrt{mp\log N_{i-1}}=\delta\sqrt{2\pi pm\log N_{i-1}}\max_{1\leq j \leq N_{i-1}}\|\widetilde{X}_{j}^{(i-1)}\|_{2}\]

holds with probability exceeding \(1-\frac{\sqrt{2}m}{N_{i-1}^{p}}-\sqrt{2}\sum_{t=2}^{N_{i-1}}\exp\Bigl{(}- \frac{(K^{(i)}\delta)^{2}}{16\sigma_{t-1}^{2}}\|\widetilde{X}_{t}^{(i-1)}\|_{2 }^{2}\Bigr{)}\). Taking a union bound over all \(1\leq j\leq N_{i}\), we have

\[\mathrm{P}\Big{(}\max_{1\leq j\leq N_{i}}\|X^{(i-1)}W_{j}^{(i)}- \widetilde{X}^{(i-1)}Q_{j}^{(i)}\|_{2}\leq\delta\sqrt{2\pi pm\log N_{i-1}} \max_{1\leq j\leq N_{i-1}}\|\widetilde{X}_{j}^{(i-1)}\|_{2}\Big{)}\] \[\geq 1-\frac{\sqrt{2}mN_{i}}{N_{i-1}^{p}}-\sqrt{2}N_{i}\sum_{t=2}^ {N_{i-1}}\exp\Bigl{(}-\frac{(K^{(i)}\delta)^{2}}{16\sigma_{t-1}^{2}}\| \widetilde{X}_{t}^{(i-1)}\|_{2}^{2}\Bigr{)}\] \[\geq 1-\frac{\sqrt{2}mN_{i}}{N_{i-1}^{p}}-\sqrt{2}N_{i}\sum_{t=2}^ {N_{i-1}}\exp\Bigl{(}-\frac{(K^{(i)})^{2}\|\widetilde{X}_{t}^{(i-1)}\|_{2}^{2}} {8\pi\max_{1\leq j\leq t-1}\|\widetilde{X}_{j}^{(i-1)}\|_{2}^{2}}\Bigr{)}.\]

Next, in Theorem 4.2, we show that provided the activations \(X^{(i-1)}\) and \(\widetilde{X}^{(i-1)}\) of the quantized and unquantized networks are sufficiently close, and provided the weights \(w\) follow a random distribution, one can guarantee the needed boundedness of the aligned weights \(\widetilde{w}\). This allows us to apply Theorem 4.1 and generate an error bound for finite alphabets. Our focus on random weights here enables us to avoid certain adversarial situations. Indeed, one can construct activations \(X^{(i-1)}\) and \(\widetilde{X}^{(i-1)}\) that are arbitrarily close to each other, along with adversarial weights \(w\) that together lead to \(\|\widetilde{w}\|_{\infty}\) becoming arbitrarily large. We demonstrate this contrived adversarial scenario in Proposition B.9. However, in generic cases
represented by random weights, as shown in Theorem 4.2, the bound on \(\widetilde{w}\) is not a major issue. Consequently, one can utilize a finite alphabet for quantization as desired.

**Theorem 4.2**.: _Assuming that the first \(i-1\) layers have been quantized, let \(X^{(i-1)}\), \(\widetilde{X}^{(i-1)}\) be as in (11). Suppose the weight matrix \(W^{(i)}\in\mathbb{R}^{N_{i-1}\times N_{i}}\) has i.i.d. \(\mathcal{N}(0,1)\) entries and_

\[\|\widetilde{X}^{(i-1)}-X^{(i-1)}\|_{2}\leq\epsilon^{(i-1)}\sigma_{1}^{(i-1)}< \sigma_{m}^{(i-1)}, \tag{53}\]

_where \(\epsilon^{(i-1)}\in(0,1)\), \(\sigma_{1}^{(i-1)}\) and \(\sigma_{m}^{(i-1)}\) are the largest and smallest singular values of \(X^{(i-1)}\) respectively. Let \(p,K^{(i)}\in\mathbb{N}\) and \(\delta>0\) such that \(p\geq 3\) and_

\[K^{(i)}\delta\geq 2\eta^{(i-1)}\sqrt{2p\log N_{i-1}}. \tag{54}\]

_where \(\eta^{(i-1)}:=\frac{\sigma_{1}^{(i-1)}}{\sigma_{m}^{(i-1)}-\epsilon^{(i-1)} \sigma_{1}^{(i-1)}}\). If we quantize \(W^{(i)}\) using Algorithm 1 with \(\mathcal{A}=\mathcal{A}_{K^{(i)}}^{\delta}\), then_

\[\max_{1\leq j\leq N_{i}}\|X^{(i-1)}W_{j}^{(i)}-\widetilde{X}^{(i-1)}Q_{j}^{(i )}\|_{2}\leq\delta\sqrt{2\pi pm\log N_{i-1}}\max_{1\leq j\leq N_{i-1}}\| \widetilde{X}_{j}^{(i-1)}\|_{2} \tag{55}\]

_holds with probability at least \(1-\frac{2N_{i}}{N_{i-1}^{p-1}}-\frac{\sqrt{2}mN_{i}}{N_{i-1}^{p}}-\sqrt{2}N_{ i}\sum_{t=2}^{N_{i-1}}\exp\Bigl{(}-\frac{(K^{(i)})^{2}\|\widetilde{X}_{j}^{(i-1)} \|_{2}^{2}}{8\pi\max_{1\leq j\leq t-1}\|\widetilde{X}_{j}^{(i-1)}\|_{2}^{2}} \Bigr{)}\)._

Proof.: Pick a neuron \(w:=W_{j}^{(i)}\in\mathbb{R}^{N_{i-1}}\) for some \(1\leq j\leq N_{i}\). Then we have \(w\sim\mathcal{N}(0,I)\) and since we are using Algorithm 1, we must work with the resulting \(\widetilde{w}\), the solution of (22). Applying Proposition B.11 to \(w\) with \(X=X^{(i-1)}\) and \(\widetilde{X}=\widetilde{X}^{(i-1)}\), we obtain

\[\mathrm{P}\Bigl{(}\|\widetilde{w}\|_{\infty}\leq\eta^{(i-1)}\sqrt{2p\log N_{i- 1}}\Bigr{)}\geq 1-\frac{2}{N_{i-1}^{p-1}},\]

so that using (54) gives

\[\mathrm{P}\Bigl{(}\|\widetilde{w}\|_{\infty}\leq\frac{1}{2}K^{(i)}\delta \Bigr{)}\geq 1-\frac{2}{N_{i-1}^{p-1}}. \tag{56}\]

Conditioning on the event \(\{\|\widetilde{w}\|_{\infty}\leq\frac{1}{2}K^{(i)}\delta\}\) and applying exactly the same argument in Theorem 4.1,

\[\|X^{(i-1)}W_{j}^{(i)}-\widetilde{X}^{(i-1)}Q_{j}^{(i)}\|_{2}\leq\delta\sqrt{2 \pi pm\log N_{i-1}}\max_{1\leq j\leq N_{i-1}}\|\widetilde{X}_{j}^{(i-1)}\|_{2} \tag{57}\]

holds with probability exceeding \(1-\frac{\sqrt{2}m}{N_{i-1}^{p}}-\sqrt{2}\sum_{t=2}^{N_{i-1}}\exp\Bigl{(}- \frac{(K^{(i)})^{2}\|\widetilde{X}_{j}^{(i-1)}\|_{2}^{2}}{8\pi\max_{1\leq j \leq t-1}\|\widetilde{X}_{j}^{(i-1)}\|_{2}^{2}}\Bigr{)}\). Combining (56) and (57), and taking a union bound over all \(1\leq j\leq N_{i}\), we obtain (55). 

Now we are about to approximate the number of bits needed for guaranteeing the derived bounds. Note that, in Theorem 4.2, we achieved the same error bound (55) as in Lemma 3.1, choosing proper \(\epsilon^{(i-1)}\in(0,1)\) and \(K^{(i)}\in\mathbb{N}\) such that (53) and (54) are satisfied and the associated probability in (55) is positive. This implies that the error bounds we obtained in Section 3 remain valid for our finite alphabets as well. In particular, by a similar argument we used to obtain (47), one can get the following approximations

\[\frac{\|\widetilde{X}^{(i-1)}-X^{(i-1)}\|_{F}^{2}}{\|X^{(i-1)}\|_{F}^{2}} \lesssim\Bigl{(}\prod_{k=0}^{i-1}\log N_{k}\Bigr{)}\sum_{j=0}^{i-2}\prod_{k=j} ^{i-2}\frac{m}{N_{k}}.\]
Due to \(\|X^{(i-1)}\|_{F}\leq\sqrt{m}\|X^{(i-1)}\|_{2}\) and \(\|\widetilde{X}^{(i-1)}-X^{(i-1)}\|_{2}\leq\|\widetilde{X}^{(i-1)}-X^{(i-1)}\|_{F}\), we have

\[\frac{\|\widetilde{X}^{(i-1)}-X^{(i-1)}\|_{2}^{2}}{\|X^{(i-1)}\|_{2 }^{2}} \leq\frac{m\|\widetilde{X}^{(i-1)}-X^{(i-1)}\|_{F}^{2}}{\|X^{(i-1) }\|_{F}^{2}}\] \[\lesssim m\Big{(}\prod_{k=0}^{i-1}\log N_{k}\Big{)}\sum_{j=0}^{i-2 }\prod_{k=j}^{i-2}\frac{m}{N_{k}}.\]

If \(\prod_{k=j}^{i-2}N_{k}\gtrsim m^{i-j}\prod_{k=0}^{i-1}\log N_{k}\) for \(0\leq j\leq i-2\), then it is possible to choose \(\epsilon^{(i-1)}\in(0,1)\) such that (53) holds. Moreover, since \(\sigma_{m}^{(i-1)}\leq\sigma_{1}^{(i-1)}\), we have \(\eta^{(i-1)}=\frac{\sigma_{1}^{(i-1)}}{\sigma_{m}^{(i-1)}-\epsilon^{(i-1)} \sigma_{1}^{(i-1)}}\geq(1-\epsilon^{(i-1)})^{-1}\) and thus (54) becomes

\[K^{(i)}\geq 2\delta^{-1}(1-\epsilon^{(i-1)})^{-1}\sqrt{2p\log N_{i-1}} \gtrsim\sqrt{\log N_{i-1}}. \tag{58}\]

Assuming columns of \(\widetilde{X}^{(i-1)}\) are similar in the sense of

\[\max_{1\leq j\leq t-1}\|\widetilde{X}^{(i-1)}_{j}\|_{2}\lesssim\sqrt{\log N_{ i-1}}\|\widetilde{X}^{(i-1)}_{t}\|_{2},\quad 2\leq t\leq N_{i-1},\]

we obtain that (55) holds with probability exceeding

\[1-\frac{2N_{i}}{N_{i-1}^{p-1}}-\frac{\sqrt{2}mN_{i}}{N_{i-1}^{p} }-\sqrt{2}N_{i}\sum_{t=2}^{N_{i-1}}\exp\Bigl{(}-\frac{(K^{(i)})^{2}\| \widetilde{X}^{(i-1)}_{t}\|_{2}^{2}}{8\pi\max_{1\leq j\leq t-1}\|\widetilde{X} ^{(i-1)}_{j}\|_{2}^{2}}\Bigr{)}\] \[\geq 1-\frac{2N_{i}}{N_{i-1}^{p-1}}-\frac{\sqrt{2}mN_{i}}{N_{i-1}^ {p}}-\sqrt{2}N_{i-1}N_{i}\exp\Bigl{(}-\frac{(K^{(i)})^{2}}{8\pi\log N_{i-1}} \Bigr{)}. \tag{59}\]

To make (59) positive, we have

\[K^{(i)}\gtrsim\log\max\{N_{i-1},N_{i}\}. \tag{60}\]

It follows from (58) and (59) that, in the \(i\)th layer, we only need a number of bits \(b^{(i)}\) that satisfies

\[b^{(i)}\geq\log_{2}K^{(i)}+1\gtrsim\log_{2}\log\max\{N_{i-1},N_{i}\}\]

to guarantee the performance of our quantization method using finite alphabets.

## 5. Experiments

In this section, we test the performance of SPFQ on the ImageNet classification task and compare it with the non-random scheme GPFQ in [38]. In particular, we adopt the version of SPFQ corresponding to (15) 1, i.e., Algorithm 2 with order \(r=1\). Note that the GPFQ algorithm runs the same iterations as in (15) except that \(\mathcal{Q}_{\text{StocQ}}\) is substituted with a non-random quantizer \(\mathcal{Q}_{\text{DetQ}}\), so the associated iterations are given by

Footnote 1: Code: [https://github.com/jayzhang0727/Stochastic](https://github.com/jayzhang0727/Stochastic) \(-\) Path \(-\) Following \(-\) Quantization.git

\[\begin{cases}u_{0}=0\in\mathbb{R}^{m},\\ q_{t}=\mathcal{Q}_{\text{DetQ}}\bigg{(}\frac{(\widetilde{X}^{(i-1)}_{t},u_{t-1} +w_{t}X^{(i-1)}_{t})}{\|\widetilde{X}^{(i-1)}_{t}\|_{2}^{2}}\bigg{)},\\ u_{t}=u_{t-1}+w_{t}X^{(i-1)}_{t}-q_{t}\widetilde{X}^{(i-1)}_{t}\end{cases} \tag{61}\]

where \(\mathcal{Q}_{\text{DetQ}}(z):=\operatorname*{argmin}_{p\in\mathcal{A}}|z-p|\). For ImageNet data, we consider ILSVRC-2012 [10], a 1000-category dataset with over 1.2 million training images and 50 thousand validation
images. Additionally, we resize all images to \(256\times 256\) and use the normalized \(224\times 224\) center crop, which is a standard procedure. The evaluation metrics we choose are top-1 and top-5 accuracy of the quantized models on the validation dataset. As for the neural network architectures, we quantize all layers of VGG-16 [33], ResNet-18 and ResNet-50 [18], which are pretrained 32-bit floating point neural networks provided by torchvision in PyTorch [28]. Moreover, we fuse the batch normalization (BN) layer with the convolutional layer, and freeze the BN statistics before quantization.

Since the major difference between SPFQ in (15) and GPFQ in (61) is the choice of quantizers, we will follow the experimental setting for alphabets used in [38]. Specifically, we use batch size \(m\), fixed bits \(b\in\mathbb{N}\) for all the layers, and quantize each \(W^{(i)}\in\mathbb{R}^{N_{i-1}\times N_{i}}\) with midtread alphabets \(\mathcal{A}=\mathcal{A}_{K}^{\delta}\) as in (5), where level \(K\) and step size \(\delta\) are given by

\[K=2^{b-1},\quad\delta=\delta^{(i)}:=\frac{C}{2^{b-1}N_{i}}\sum_{1\leq j\leq N_ {i}}\|W^{(i)}_{j}\|_{\infty}. \tag{62}\]

Here, \(C>0\) is a constant that is only dependent on bitwidth \(b\), determined by grid search with cross-validation, and fixed across layers, and across batch-sizes. One can, of course, expect to do better by using different values of \(C\) for different layers but we refrain from doing so, as our main goal here is to demonstrate the performance of SPFQ even with minimal fine-tuning.

In Table 1, for different combinations of \(m\), \(b\), and \(C\), we present the corresponding top-1/top-5 validation accuracy of quantized networks using SPFQ in the first column, while the second and third columns give the validation accuracy of unquantized models and the accuracy drop due to quantization respectively. We observe that, for all three models, the quantization accuracy is improved as the number of bits \(b\) increases, and SPFQ achieves less than 0.5% top-1 accuracy loss while using 6 bits.

Next, in Figure 1, we compare SPFQ against GPFQ by quantizing the three models in Table 1. These figures illustrate that GPFQ has better performance than that of SPFQ when \(b=3,4\) and \(m\) is small. This is not particularly surprising, as \(\mathcal{Q}_{\text{DetQ}}\) deterministically rounds its argument to the nearest alphabet element instead of performing a random rounding like \(\mathcal{Q}_{\text{StocQ}}\). However, as the batch size \(m\) increases, the accuracy gap between GPFQ and SPFQ diminishes. Indeed, for VGG-16 and ResNet-18, SPFQ outperforms GPFQ when \(b=6\). Further, we note that, for both SPFQ and GPFQ, one can obtain higher quantization

\begin{table}
\begin{tabular}{l|c|c|c|c c c} \hline \hline Model & \(m\) & \(b\) & \(C\) & Quant Acc (\%) & Ref Acc (\%) & Acc Drop (\%) \\ \hline \multirow{3}{*}{VGG-16} & & 4 & 1.02 & 70.48/89.77 & 71.59/90.38 & 1.11/0.61 \\  & 1024 & 5 & 1.23 & 71.08/90.15 & 71.59/90.38 & 0.51/0.23 \\  & & 6 & 1.26 & 71.24/90.37 & 71.59/90.38 & 0.35/0.01 \\ \hline \multirow{3}{*}{ResNet-18} & & 4 & 0.91 & 67.36/87.74 & 69.76/89.08 & 2.40/1.34 \\  & 2048 & 5 & 1.32 & 68.79/88.77 & 69.76/89.08 & 0.97/0.31 \\  & & 6 & 1.68 & 69.43/88.96 & 69.76/89.08 & 0.33/0.12 \\ \hline \multirow{3}{*}{ResNet-50} & & 4 & 1.10 & 73.37/91.61 & 76.13/92.86 & 2.76/1.25 \\  & 2048 & 5 & 1.62 & 75.05/92.43 & 76.13/92.86 & 1.08/0.43 \\ \cline{1-1}  & & 6 & 1.98 & 75.66/92.67 & 76.13/92.86 & 0.47/0.19 \\ \hline \hline \end{tabular}
\end{table}
Table 1. Top-1/Top-5 validation accuracy for SPFQ on ImageNet.
accuracy by taking larger \(m\) but the extra improvement that results from increasing the batch size rapidly decreases.

Figure 1. Top-1 and Top-5 validation accuracy for SPFQ (dashed lines) and GPFQ (solid lines) on ImageNet.
## Acknowledgements

The authors thank Yixuan Zhou for discussions on the numerical experiments in this paper. This work was supported in part by National Science Foundation Grant DMS-2012546 and a Simons Fellowship.
