measure for uniform distribution on the unit sphere implies
$\mathbb{P}\left[|\widehat{\mathbf{s}}_{i}^{\top}\widehat{\mathbf{y}}|\geq
t\right]=\mathbb{P}\left[|s_{1}|\geq t\right]\leq 2e^{-dt^{2}/2}$. A
subsequent union bound gives us
$\mathbb{P}\left[\max_{i\in[D]}|\widehat{\mathbf{s}}_{i}^{\top}\widehat{\mathbf{y}}|\geq
t\right]\leq 2De^{-dt^{2}/2}$. Choosing $t=2\sqrt{\frac{\log(2D)}{d}}$ gives
us
$\mathbb{P}\left[\left\lVert\mathbf{S}^{\top}\mathbf{y}\right\rVert_{\infty}\geq
2\sqrt{\frac{\lambda\log(2D)}{D}}\left\lVert\mathbf{y}\right\rVert_{2}\right]\leq\frac{1}{2D}$.
This completes the proof. ∎

######  Lemma I.2.

For $\mathbf{S}=\mathbf{P}\mathbf{D}\mathbf{H}\in\mathbb{R}^{d\times D}$, with
probability at least $1-\frac{1}{2D}$, the near-democratic embedding
satisfies,

$\left\lVert\mathbf{x}_{nd}\right\rVert_{\infty}\leq
2\sqrt{\frac{\log\left(2D\right)}{D}}\left\lVert\mathbf{y}\right\rVert_{2}.$
(69)

###### Proof.

For the purposes of this proof, let
$\mathbf{w}=\mathbf{P}^{\top}\mathbf{y}=[w_{1},\ldots,w_{D}]^{\top}\in\mathbb{R}^{D}$
and $\mathbf{u}=\mathbf{H}\mathbf{D}\mathbf{w}=[u_{1},\ldots,u_{N}]^{\top}$.
Note that $u_{j}$ is of the form $\sum_{i=1}^{D}a_{i}w_{i}$ with each
$a_{i}=\pm\frac{1}{\sqrt{D}}$ chosen i.i.d. A Chernoff-type argument gives
$\mathbb{P}[u_{j}>t]=\mathbb{P}\left[e^{\lambda u_{j}}>e^{\lambda
t}\right]\leq e^{-\lambda t}\prod_{i=1}^{D}\mathbb{E}\left[e^{\lambda
a_{i}w_{i}}\right]$. This implies $\mathbb{E}\left[e^{\lambda
a_{i}w_{i}}\right]=\frac{1}{2}e^{\frac{\lambda}{\sqrt{D}}w_{i}}+\frac{1}{2}e^{-\frac{\lambda}{\sqrt{D}}w_{i}}=\cosh\left(\frac{\lambda
w_{i}}{\sqrt{D}}\right)\leq e^{\lambda^{2}w_{i}^{2}/(2D)}$, where the last
inequality follows from a bound on hyperbolic cosine. This gives us
$\mathbb{P}\left[u_{j}>t\right]\leq
e^{\frac{\lambda^{2}}{2D}\left\lVert\mathbf{w}\right\rVert_{2}^{2}-\lambda
t}$. Letting $\lambda=tD/\left\lVert\mathbf{w}\right\rVert_{2}^{2}$ yields
$\mathbb{P}\left[u_{j}>t\right]\leq
e^{-t^{2}D/(2\left\lVert\mathbf{w}\right\rVert_{2}^{2})}$. Similarly,
$\mathbb{P}\left[u_{j}<-t\right]\leq
e^{-t^{2}D/(2\left\lVert\mathbf{w}\right\rVert_{2}^{2})}$. Since
$\left\lVert\mathbf{u}\right\rVert_{\infty}=\max_{j\in[D],s\in\\{\pm
1\\}}su_{j}$, union bound gives
$\mathbb{P}\left[\left\lVert\mathbf{H}\mathbf{D}\mathbf{w}\right\rVert_{\infty}>t\right]\leq
e^{-\frac{t^{2}D}{2\left\lVert\mathbf{w}\right\rVert_{2}^{2}}+\log(2D)}$.
Setting $t=2\left\lVert\mathbf{w}\right\rVert_{2}\sqrt{\frac{\log(2D)}{D}}$
yields

$\mathbb{P}\left[\left\lVert\mathbf{H}\mathbf{D}\mathbf{w}\right\rVert_{\infty}\leq
2\left\lVert\mathbf{w}\right\rVert_{2}\sqrt{\frac{\log(2D)}{D}}\right]\geq
1-\frac{1}{2D}.$

As
$\mathbf{w}=\mathbf{P}^{\top}\mathbf{y}\implies\left\lVert\mathbf{w}\right\rVert_{2}=\left\lVert\mathbf{y}\right\rVert_{2}$,
this completes the proof. ∎

The above lemmas imply that with high probability, near-democratic embeddings
satisfy $\left\lVert\mathbf{x}_{nd}\right\rVert_{\infty}\leq O(\frac{\log
D}{D})$. Lemma I.3 utilizes this fact to give the worst-case quantization
error of Near-Democratic Quantization as decribed in (16).

######  Lemma I.3 (Worst-case $\ell_{2}$-error of near-democratic
quantization).

Given the frame
$\mathbf{S}=\mathbf{P}\mathbf{D}\mathbf{H}\in\mathbb{R}^{d\times D}$ and a
uniform scalar quantizer $\text{Q}_{U,B}$, for any
$\mathbf{y}\in\mathbb{R}^{d}$ such that
$\left\lVert\mathbf{y}\right\rVert_{2}\leq 1$, let
$\widetilde{\mathbf{y}}=\text{Q}_{ND,D}(\mathbf{y})=\mathbf{S}\cdot\text{Q}_{U,B}(\mathbf{x}_{nd})$.
Then, for $\lambda=D/d$,

$\sup_{\left\lVert\mathbf{y}\right\rVert_{2}\leq
1}\left\lVert\widetilde{\mathbf{y}}-\mathbf{y}\right\rVert_{2}\leq
2^{\left(2-\frac{B}{\lambda}\right)}\sqrt{\log(2D)}.$ (70)

###### Proof.

The proof is similar to that of Lemma G.5 and makes use of Lemma I.2. ∎

##  Appendix J Proof of Theorem 5.4

We refer to Lemma I.3 from App. I that gives the worst-case quantization error
for near-democratic quantizer whose input is a vector on the unit sphere
$\mathbb{S}^{d-1}$. We consider $\mathbf{S}$ to be the randomized Hadamard
construction $\mathbf{P}\mathbf{D}\mathbf{H}$. Since we compute the near-
democratic embedding of $\mathbf{s}_{nd}$ that satisfies
$\lVert\mathbf{s}_{nd}\rVert_{2}=1$, Lemma I.3 states that with probability at
least $1-\frac{1}{2D}$,

$\left\lVert\widetilde{\mathbf{X}}-\text{Q}_{ND,B}\left(\frac{\mathbf{W}^{\dagger}\mathbf{X}}{\lVert\mathbf{W}^{\dagger}\mathbf{X}\rVert_{2}}\right)\right\rVert_{2}\leq
2^{\left(2-\frac{B}{\lambda}\right)}\sqrt{\log(2D)},$ (71)

where $\lambda=D/d$ is the aspect ratio of $\mathbf{S}$ usually taken to be as
close to $1$ as possible so that a Hadamard matrix of size $D\times D$ can be
constructed.

The proof of Thm. 5.4 is similar to the proof of Thm. 5.3 provided in App. H,
except for the analysis of the quantization error term $A_{1}$ in (65). Term
$A_{1}$ is again decomposed as in (E) for naive quantizers to get the term
$\frac{2}{d}\widehat{\gamma}^{2}\lVert\mathbf{W}^{\dagger}\mathbf{X}\rVert_{2}^{2}\cdot\left\lVert\widetilde{\mathbf{X}}-\frac{\mathbf{W}^{\dagger}\mathbf{x}}{\lVert\mathbf{W}^{\dagger}\mathbf{X}\rVert_{2}}\right\rVert_{2}^{2}$,
which is subsequently upper bounded as,

$\displaystyle\frac{2}{d}\widehat{\gamma}^{2}\lVert\mathbf{W}^{\dagger}\mathbf{X}\rVert_{2}^{2}\cdot\left\lVert\widetilde{\mathbf{X}}-\frac{\mathbf{W}^{\dagger}\mathbf{x}}{\lVert\mathbf{W}^{\dagger}\mathbf{X}\rVert_{2}}\right\rVert_{2}^{2}$
$\displaystyle\leq\frac{2}{d}\cdot\frac{d\widehat{b}^{4}}{\left(\widehat{b}^{2}+\frac{\sigma^{2}}{d}\xi\right)}\cdot
2^{2\left(2-\frac{B}{\lambda}\right)}\log(2D)+O_{P}\left(\frac{1}{D}\right)$
$\displaystyle\leq\frac{32b^{4}\log(2\lambda
d)}{b^{2}+\frac{\sigma^{2}}{d}\xi}\cdot
2^{-\frac{2B}{\lambda}}+O_{P}\left(\frac{1}{\sqrt{d}}\right)$

Proceeding as before, a uniform upper bound over all models in
$\frac{1}{d}\lVert\boldsymbol{\theta}\rVert_{2}^{2}\leq c^{2}$ can be obtained
as,

$\mathbb{P}\left(R(\widetilde{\boldsymbol{\theta}},\boldsymbol{\theta})>\frac{2c^{2}\sigma^{2}}{\sigma^{2}+c^{2}\sigma_{m}^{2}}+\frac{64c^{4}\sigma_{M}^{2}\log(2\lambda
d)}{\sigma^{2}+c^{2}\sigma_{M}^{2}}\cdot
2^{-\frac{2B}{\lambda}}+\frac{C_{nd}}{\sqrt{d}}\right)\to 0$ (72)

as $d\to\infty$ for some constant $C_{nd}$ independent of $d$.

##  Appendix K Non-asymptotic lower bound for finite dimension $d$

To remove the asymptoticity in our lower bound result, we note that the only
step that makes use of the fact $d\to\infty$ is the proof of Lemma 4.2. More
specifically, we consider (B) that splits the Bayes’ error over the whole of
$\mathbb{R}^{d}$ as the sum of integrals over the parameter space
$\boldsymbol{\Theta}$ and $\mathbb{R}^{d}\setminus\boldsymbol{\Theta}$ as,

$\int_{\boldsymbol{\theta}\in\mathbb{R}^{d}}R({\mathsf{Q}}(\mathbf{X}),\boldsymbol{\theta})dF(\boldsymbol{\theta})\leq\sup_{\boldsymbol{\theta}\in\boldsymbol{\Theta}}R({\mathsf{Q}}(\mathbf{X}),\boldsymbol{\theta})+\int_{\boldsymbol{\theta}\in\overline{\boldsymbol{\Theta}}}R({\mathsf{Q}}(\mathbf{X}),\boldsymbol{\theta})dF(\boldsymbol{\theta})$
(73)

Recalling (B) from App. B, when $\boldsymbol{\theta}\sim{\cal
N}\left(\mathbf{0},c^{2}\delta^{2}\mathbf{I}_{d}\right)$ for a fixed
$\delta\in(0,1)$, the second term tends to zero as $d\to\infty$. However, when
$d\centernot\rightarrow\infty$, this term can be upper bounded as before, i.e.

$\displaystyle\int_{\boldsymbol{\theta}\in\overline{\boldsymbol{\Theta}}}R({\mathsf{Q}}(\mathbf{X}),\boldsymbol{\theta})dF(\boldsymbol{\theta})$
$\displaystyle\leq\frac{2}{d}\sqrt{2}\exp\left(-\frac{d(1-\delta^{2})^{2}}{16\delta^{4}}\right)O(d)+2c^{2}\exp\left(-\frac{d(1-\delta^{2})^{2}}{8\delta^{4}}\right)$

This gives us, for a fixed $\delta\in(0,1)$,

$\sup_{\boldsymbol{\theta}\in\boldsymbol{\Theta}}R({\mathsf{Q}}(\mathbf{X}),\boldsymbol{\theta})\geq\int_{\boldsymbol{\theta}\in\mathbb{R}^{d}}R({\mathsf{Q}}(\mathbf{X}),\boldsymbol{\theta})dF(\boldsymbol{\theta})-\frac{2}{d}\sqrt{2}\exp\left(-\frac{d(1-\delta^{2})^{2}}{16\delta^{4}}\right)O(d)-2c^{2}\exp\left(-\frac{d(1-\delta^{2})^{2}}{8\delta^{4}}\right)$
(74)

Moreover, for the choice of prior $\boldsymbol{\theta}\sim{\cal
N}\left(\mathbf{0},c^{2}\delta^{2}\mathbf{I}_{d}\right)$, Lem. 4.3 can be
modified to lower bound the first term in (74) as,

$\displaystyle\int_{\boldsymbol{\theta}\in\mathbb{R}^{d}}R({\mathsf{Q}}(\mathbf{X}),\boldsymbol{\theta})dF(\boldsymbol{\theta})\geq\frac{c^{2}\delta^{2}\sigma^{2}}{\sigma^{2}+c^{2}\delta^{2}\sigma_{M}^{2}}+\frac{c^{4}\sigma_{m}^{2}}{\sigma^{2}+c^{2}\delta^{2}\sigma_{m}^{2}}\cdot
2^{-2B}-$
$\displaystyle\frac{2}{d}\sqrt{2}\exp\left(-\frac{d(1-\delta^{2})^{2}}{16\delta^{4}}\right)O(d)$
$\displaystyle-$ $\displaystyle
2c^{2}\exp\left(-\frac{d(1-\delta^{2})^{2}}{8\delta^{4}}\right)$ (75)

Note that (K) holds true for any $\delta\in(0,1)$. The particular choice of
$\delta\in(0,1)$ can be optimized to maximize the right hand side expression
so as to ensure that the lower bound is tight. It is worthwhile to note that
since the last two terms are exponentially decaying in $d$ while the first two
terms are independent of $d$, for large enough (but finite) $d$, the lower
bound is non-negative.

##  Appendix L Extension to $2$-Layer scalar output ReLU Neural Networks

A scalar output $2$-layer neural network can be represented as:

$f(\mathbf{x})=\mathbf{w}^{\top}\left(\widetilde{\mathbf{W}}\mathbf{x}\right)_{+}=\sum_{j=1}^{m}\left(\widetilde{W}_{j}^{\top}\mathbf{x}\right)_{+}w_{j}\in\mathbb{R}.$
(76)

Here, $(\cdot)_{+}=\max\\{\cdot,0\\}$ is the ReLU activation. For the analysis
in this section, $\widetilde{\mathbf{W}}\in\mathbb{R}^{m\times d}$ denotes the
weight matrix for the first layer. $\mathbf{x}\in\mathbb{R}^{d}$ is the input,
$m$ is the number of neurons in the first (hidden) layer.
$\widetilde{W}_{1}^{\top},\ldots,\widetilde{W}_{m}^{\top}\in\mathbb{R}^{d}$
denote the rows of the weight matrix $\widetilde{\mathbf{W}}$, whereas
$w_{1},\ldots,w_{m}\in\mathbb{R}$ denote the weights of the second dense
layer. Note that for every $j$, we have $w_{j}=\lvert
w_{j}\rvert\cdot\text{Sign}(w_{j})$. Consequently, (76) can be re-parametrized
by absorbing $\lvert w_{j}\rvert$ within the $(\cdot)_{+}$ function and
setting $W_{j}=\widetilde{W}_{j}\lvert w_{j}\rvert$ as,

$\displaystyle
f(\mathbf{x})=\sum_{j=1}^{m}\left(W_{j}^{\top}\mathbf{x}\right)_{+}\cdot\text{Sign}(w_{j})$
$\displaystyle=\sum_{j:(W_{j}^{\top}\mathbf{x})_{+}\geq
0}\left(W_{j}^{\top}\mathbf{x}\right)_{+}-\sum_{j:(W_{j}^{\top}\mathbf{x})_{+}<0}\left(W_{j}^{\top}\mathbf{x}\right)_{+}$
(77)

Let us denote the set $\\{j:(W_{j}^{\top}\mathbf{x})_{+}\geq 0\\}$ as $M_{+}$
and $\\{j:(W_{j}^{\top}\mathbf{x})_{+}<0\\}$ as $M_{-}$. Suppose we quantize
the weights to get $\widehat{\mathbf{W}}$ and $\widehat{\mathbf{w}}$ instead
of $\mathbf{W}$ and $\mathbf{w}$. The output of the quantized neural network
can be written as
$\widehat{f}(\mathbf{x})=\sum_{j=1}^{m}\left(\widehat{W}_{j}^{\top}\mathbf{x}\right)_{+}\cdot\text{Sign}(\widehat{w}_{j})$.
We then have the error in the scalar output of the quantized neural network
as,

$\displaystyle\left\lvert\widehat{f}(\mathbf{x})-f(\mathbf{x})\right\rvert$
$\displaystyle=\left\lvert\sum_{j\in
M_{+}}\left[\left(W_{j}^{\top}\mathbf{x}\right)_{+}-\left(\widehat{W}_{j}^{\top}\mathbf{x}\right)_{+}\right]-\sum_{j\in
M_{-}}\left[\left(W_{j}^{\top}\mathbf{x}\right)_{+}-\left(\widehat{W}_{j}^{\top}\mathbf{x}\right)_{+}\right]\right\rvert$
$\displaystyle\leq\sum_{j\in
M_{+}}\left\lvert\left(W_{j}^{\top}\mathbf{x}\right)_{+}-\left(\widehat{W}_{j}^{\top}\mathbf{x}\right)_{+}\right\rvert+\sum_{j\in
M_{-}}\left\lvert\left(W_{j}^{\top}\mathbf{x}\right)_{+}-\left(\widehat{W}_{j}^{\top}\mathbf{x}\right)_{+}\right\rvert$
$\displaystyle\leq\sum_{j=1}^{m}\left\lvert\left(W_{j}^{\top}\mathbf{x}\right)_{+}-\left(\widehat{W}_{j}^{\top}\mathbf{x}\right)_{+}\right\rvert$
$\displaystyle=\sum_{j=1}^{m}\left\lvert\left(\left(W_{j}-\widehat{W}_{j}\right)^{\top}\mathbf{x}\right)_{+}\right\rvert$
$\displaystyle\leq\sum_{j=1}^{m}\left\lVert
w_{j}-\widehat{w}_{j}\right\rVert_{2}\cdot\left\lVert\mathbf{x}\right\rVert_{2}\leq\sqrt{m}\sqrt{\sum_{j=1}^{m}\left\lVert
w_{j}-\widehat{w}_{j}\right\rVert_{2}^{2}}\cdot\left\lVert\mathbf{x}\right\rVert_{2}=\sqrt{m}\left\lVert\mathbf{W}-\widetilde{\mathbf{W}}\right\rVert_{F}\left\lVert\mathbf{x}\right\rVert_{2}.$

The last inequality follows when we do layer-wise quantization of the weights.
We essentially vectorize $\mathbf{W}\in\mathbb{R}^{m\times d}$ and apply DQ or
NDQ for quantizing the resultant vector.

For simplicity, we assume $\left\lVert\mathbf{x}\right\rVert_{2}\leq 1$ and
$\left\lVert\text{Vec}\left(\mathbf{W}\right)\right\rVert_{2}\leq 1$. From
Lemma I.3, if we use NDQ with a randomized Hadamard frame (with $\lambda=1$)
to quantize $\text{Vec}(\mathbf{W})$ with a bit-budget of $B$-bits per weight
(which we do in our numerical simulations), we get
$\left\lVert\mathbf{W}-\widetilde{\mathbf{W}}\right\rVert_{F}\leq
2^{\left(2-B\right)}\sqrt{\log(2md)}$. Then, to ensure that
$\left\lvert\widehat{f}(\mathbf{x})-f(\mathbf{x})\right\rvert\leq\epsilon$ for
some error tolerance $\epsilon>0$, it suffices to ensure that

$\displaystyle 4\sqrt{m}\cdot 2^{-B}\sqrt{\log\left(2md\right)}\leq\epsilon$
$\displaystyle\implies$ $\displaystyle
B\geq\log_{2}\left(\frac{4}{\epsilon}\right)+\frac{1}{2}\log_{2}m+\frac{1}{2}\log_{2}\log_{2}md\implies$
$\displaystyle
B_{*}(\epsilon)\leq\log_{2}\left(\frac{4}{\epsilon}\right)+\frac{1}{2}\log_{2}m+\frac{1}{2}\log_{2}\log_{2}md$
(78)

(L) gives us an upper bound on the minimum number of bits required to achieve
a given error $\epsilon$. It is worthwhile to note that we can make this
tighter by getting rid of the $\log_{2}\log_{2}md$ term if we use DQ with
random orthonormal frame.