for restriction to memoryless quantization schemes is ease of implementation
and their application to other problems, as we see in Chapter 4 and 5.

Thus our channel selection strategy $S$ is nonadaptive (recall definition 3.2)
and is simply denoted by the quantizer $Q$ we choose to use. Thus the
optimization error for a function $f$ and oracle $O$ when employing a first
order optimization $\pi$ and quantizer $Q$ is given by

$\mathcal{E}(f,O,\pi,Q)=\mathbb{E}\left[f(x_{T})\right]-\mathbb{E}\left[f(x^{\ast}\right].$

#####  3 Quantizer performance for finite precision optimization

Our overall optimization protocol throughout is the projected SGD (PSGD) (see
[15]). In fact, we establish lower bound showing roughly the optimality of
PSGD with our quantizers.

In PSGD the standard SGD updates are projected back to the domain using the
projection map $\Gamma_{\mathcal{X}}$ given by
$\Gamma_{\mathcal{X}}(y):=\min_{x\in\mathcal{X}}\|x-y\|_{2}.$ We use the
quantized PSGD algorithm described in Algorithm 1.

1:Require: $x_{0}\in\mathcal{X},\eta\in\mathbb{R}^{+}$, $T$ and access to
composed oracle $QO$ 2:for $t=0$ to $T-1$ do
$x_{t+1}=\Gamma_{\mathcal{X}}\left(x_{t}-\eta_{t}Q(\hat{g}(x_{t}))\right)$
3:Output: $\frac{1}{T}\cdot{\sum_{t=1}^{T}x_{t}}$ Algorithm 1: Quantized PSGD
with quantizer $Q$

The quantized output $Q(\hat{g}(x_{t}))$, too, constitutes a noisy oracle, but
it can be biased for mean square bounded oracles. Though biased first-order
oracles were considered in [45], the effect of quantizer-bias has not been
studied in the past. The performance of a quantizer $Q$, when it is used with
PSGD for mean square bounded oracles, is controlled by the worst-case $L_{2}$
norm $\alpha_{2}^{\tt m}(Q)$ of its output and the worst-case bias
$\beta_{2}^{\tt m}(Q)$ defined as444We omit the dependence on $B$ and $d$ from
our notation.

$\displaystyle\alpha_{2}^{\tt m}(Q)$
$\displaystyle:=\sup_{Y\in\mathbb{R}^{d}:\mathbb{E}\left[\|Y\|_{2}^{2}\right]\leq
B^{2}}\sqrt{\mathbb{E}\left[\|Q(Y)\|_{2}^{2}\right]},$
$\displaystyle\beta_{2}^{\tt m}(Q)$
$\displaystyle:=\sup_{Y\in\mathbb{R}^{d}:\mathbb{E}\left[\|Y\|_{2}^{2}\right]\leq
B^{2}}\|\mathbb{E}\left[Y-Q(Y)\right]\|_{2}.$ (4)

The corresponding quantities for almost surely bounded oracles are

$\displaystyle\alpha_{2}(Q)$
$\displaystyle:=\sup_{Y\in\mathbb{R}^{d}:\|Y\|_{2}\leq B\text{
a.s.}}\sqrt{\mathbb{E}\left[\|Q(Y)\|_{2}^{2}\right]},$
$\displaystyle\beta_{2}(Q)$
$\displaystyle:=\sup_{Y\in\mathbb{R}^{d}:\|Y\|_{2}\leq B\text{
a.s.}}\|\mathbb{E}\left[Y-Q(Y)\right]\|_{2}.$ (5)

Using a slight modification of the standard proof of convergence for PSGD, we
get the following result for convex functions.

######  Theorem 3.2.

Let the domain $\mathcal{X}$ satisfy 2. For any quantizer $Q$, the output
$x_{T}$ of optimization protocol $\pi$ given in Algorithm 1 satisfies

$\displaystyle\sup_{(f,O)\in\mathcal{O}_{{\tt c},2}}\mathcal{E}(f,O,\pi,Q)$
$\displaystyle\leq D\left(\frac{\alpha_{2}(Q)}{\sqrt{T}}+\beta_{2}(Q)\right),$
$\displaystyle\sup_{(f,O)\in\mathcal{O}_{{\tt c},2}^{\tt
m}}\mathcal{E}(f,O,\pi,Q)$ $\displaystyle\leq D\left(\frac{\alpha_{2}^{\tt
m}(Q)}{\sqrt{T}}+\beta_{2}^{\tt m}(Q)\right),$

when the parameter $\eta_{t}=\eta$, for all $t$, is set to
$D/(\alpha_{2}(Q)\sqrt{T})$ and $D/(\alpha_{2}^{\tt m}(Q)\sqrt{T})$,
respectively.

See Section 1 for the proof.

######  Remark 8 (Knowledge of time horizon in setting the learning rate.).

Note that the choice of learning rate $\eta_{t}$ in 3.2 requires the knowledge
of the time horizon $T$. In fact, all the convergence results in this thesis
require setting $\eta_{t}$ based on the time horizon. One could employ the
doubling trick –see, for instance, [70, Pg. 129] – to remove this restriction.
However, this would add a multiplicative $\sqrt{\log T}$ factor to the
convergence rate.

We have also have the following counterpart of the previous result for
strongly convex functions.

######  Theorem 3.3.

Let the domain $\mathcal{X}$ satisfy 2. For any quantizer $Q$, the output
$x_{T}$ of optimization protocol $\pi$ given in Algorithm 1 satisfies

$\displaystyle\sup_{(f,O)\in\mathcal{O}_{{\tt sc}}}\mathcal{E}(f,O,\pi,Q)$
$\displaystyle\leq D\left(\frac{\alpha_{2}(Q)^{2}}{D\gamma
T}+\beta_{2}(Q)\right).$

when the parameter $\eta_{t}$ is set to $2/\gamma(t+1)$.

See Section 2 for the proof.

######  Remark 9 (Choice of learning rate).

For the class of convex functions, we fix the parameter $\eta_{t}$ of
Algorithm 1 to a constant value $\eta$, for all $t$. $\eta$ is set to
$D/(\alpha_{2}(Q)\sqrt{T})$ and $D/(\alpha_{2}^{\tt m}(Q)\sqrt{T})$ for all
the results in Section 4 and Section 5, respectively. For the class of
strongly convex functions, we fix the parameter $\eta_{t}=2/\gamma(t+1)$ all
the results in Section 4.

####  4 Main results for almost surely bounded oracles

Our main results will be organized along two regimes: the high-precision and
the low-precision regime. For the high-precision regime, we seek to attain the
optimal, classic convergence rate of $1/\sqrt{T}$, for convex functions, and
$1/T$, for strongly convex functions, using the minimum precision possible.
For the low-precision regime, we seek to attain the fastest convergence rate
possible for a given, fixed precision $r$.

From our lower bounds on minmax optimization error of families
$\mathcal{O}_{{\tt c},2}$ and $\mathcal{O}_{{\tt sc}}$ under communication
constraints, which are derived in Theorem 4.4 and 4.6, we have the following
corollaries. Our corollaries show that there is no hope of getting the desired
convergence rate of $1/\sqrt{T}$ for convex function and $\ell_{2}$ lipschitz
function families ($\mathcal{O}_{{\tt c},2}$, $\mathcal{O}_{{\tt c},2}^{\tt
m}$) and $1/T$ for strongly convex function families $\mathcal{O}_{{\tt sc}}$
by using a precision of less than $d$.

######  Corollary 4.1.

Let
$\mathbb{X}_{2}(D)=\\{\mathcal{X}^{\prime}:\sup_{x,y\in\mathcal{X}^{\prime}}\|x-y\|_{2}\leq
D\\}$. Then, the precision $r$ must be at least $\Omega(d),$ for either one of
the following to hold:

$\displaystyle\displaystyle{\sup_{\mathcal{X}\in\mathbb{X}_{2}(D)}\mathcal{E}^{*}(\mathcal{X},\mathcal{O}_{{\tt
c},2},T,\mathcal{W}_{{\tt
com},r)}}\leq\frac{DB}{\sqrt{T}},\quad\displaystyle{\sup_{\mathcal{X}\in\mathbb{X}_{2}(D)}\mathcal{E}^{*}(\mathcal{X},\mathcal{O}_{{\tt
c},2}^{\tt m},T,\mathcal{W}_{{\tt com},r})}\leq\frac{DB}{\sqrt{T}},$
$\displaystyle\text{and}\displaystyle{\sup_{\mathcal{X}\in\mathbb{X}_{2}(D)}\mathcal{E}^{*}(\mathcal{X},\mathcal{O}_{{\tt
sc}},T,\mathcal{W}_{{\tt com},r)}}\leq\frac{B^{2}}{\gamma T}.$

Thus, from Corollary 4.1, our quantization schemes in high-precision regime
will use a precision of atleast $d$ bits.

#####  1 RATQ: Our quantizer for the $\ell_{2}$ ball

We propose Rotated Adaptive Tetra-iterated Quantizer (RATQ) to quantize any
random vector $Y$ with $\|Y\|_{2}^{2}\leq B^{2}$, which is what we need for
almost surely bounded oracles. RATQ first rotates the input vector, then
divides the coordinates of the rotated vectors into smaller groups, and
finally quantizes each subgroup-vector using a Coordinate-wise Uniform
Quantizer (CUQ). However, the dynamic-range used for each subvector is chosen
adaptively from a set of tetra-iterated levels. We call this adaptive
quantizer Adaptive Tetra-iterated Uniform Quantizer (ATUQ), and it is the main
workhorse of our construction. The encoder and decoder for RATQ are given in
Algorithm 2 and Algorithm 3, respectively. The details of all the components
involved are described below.

1:Input $Y\in\mathbb{R}^{d}$, rotation matrix R  2:Compute $\tilde{Y}=RY$
3:for $i\in[d/s]$ do
$\displaystyle{\tilde{Y}_{i}^{T}=[\tilde{Y}((i-1)s+1),\cdots\tilde{Y}(\min\\{is,d\\})]^{T}}$
4:Output: $\displaystyle{Q^{{\tt e}}_{{\tt at},R}(Y)=\\{Q^{{\tt e}}_{{\tt
at}}(\tilde{Y_{1}})\cdots Q^{{\tt e}}_{{\tt at}}(\tilde{Y}_{\left\lceil
d/s\right\rceil})\\}}$ Algorithm 2: Encoder $Q^{{\tt e}}_{{\tt at},R}(Y)$ for
RATQ 1:Input $\\{Z_{i},j_{i}\\}$ for $i\in[\left\lceil d/s\right\rceil]$,
rotation matrix R  2:$\hat{Y}^{T}=[Q^{{\tt d}}_{\tt at}(Z_{1},j_{1}),\cdots$,
$Q^{{\tt d}}_{{\tt at}}(Z_{\left\lceil d/s\right\rceil},j_{\left\lceil
d/s\right\rceil})]^{T}$ 3:Output: $Q^{{\tt d}}_{{\tt
at},R}(\\{Z_{i},j_{i}\\}_{i=1}^{\left\lceil d/s\right\rceil})=R^{-1}\hat{Y}$
Algorithm 3: Decoder $Q^{{\tt d}}_{{\tt at},R}(Z,j)$ for RATQ

###### Rotation and division into subvectors.

RATQ first rotates the input vector by multiplying it with a random Hadamard
matrix. Specifically, denoting by $H$ the $d\times d$ Walsh-Hadamard Matrix
(see [44])555We assume that $d$ is a power of $2$., define

$R:=\frac{1}{\sqrt{d}}\cdot HD,$ (6)

where $D$ is a diagonal matrix with each diagonal entry generated uniformly
from $\\{-1,+1\\}$. The input vector $y$ is multiplied by $R$ in the rotation
step. The matrix $D$ can be generated using shared randomness between the
encoder and decoder.

Next, the rotated vector of dimension $d$ is partitioned into $\left\lceil
d/s\right\rceil$ smaller subvectors. The $i^{th}$ subvector comprises the
coordinates $\\{(i-1)s+1,\cdots,\min\\{is,d\\}\\}$, for all $i\in[d/s].$ Note
that the dimension of all the sub vectors except the last one is $s$, with the
last one having a dimension of $d-s\lfloor d/s\rfloor$.

######  Remark 10.

As an aside, we remark that preprocessing the data by such a random transform
$R$ was used by [7] for Fast Johnson Lindestrauss transform.

We now describe the advantage of random rotation. The advantage of subvector
division will be clear once we describe the rest of the scheme.

######  Remark 11 (Advantage of random rotation).

While by almost sure assumption the input vector to the quantizer is inside
the Euclidean ball of radius $B$, to set the dynamic range666We mean the
interval $[-M,M].$, we need upper bounds for each coordinate of the vector.
After random rotation, each coordinate of the input vector is a centered
subgaussian random variable with a variance of $O(B^{2}/d)$, as opposed to a
variance factor of $O(B^{2})$, which is all that can be said for the original
input vector.

###### Coordinate-wise Uniform Quantizer (CUQ).

RATQ uses CUQ as a subroutine; we describe the latter for $d$ dimensional
inputs, but it will only be applied to subvectors of lower dimension in RATQ.
CUQ has a dynamic range $[-M,M]$ associated with it, and it uniformly
quantizes each coordinate of the input to $k$-levels as long as the component
is within the dynamic-range $[-M,M]$. Specifically, it partitions the interval
$[-M,M]$ into parts $I_{\ell}:=(B_{M,k}(\ell),B_{M,k}(\ell+1)]$,
$\ell\in\\{0,\ldots,k-1\\}$, where $B_{M,k}(\ell)$ are given by

$\displaystyle
B_{M,k}(\ell):=-M+\ell\cdot\frac{2M}{k-1},\quad\forall\,\ell\in\\{0,\ldots,k-1\\}.$

Then, for a coordinate $y\in(B_{M,k}(\ell),B_{M,k}(\ell+1)],$ CUQ randomly
outputs either $B_{M,k}(\ell)$ or $B_{M,k}(\ell+1)$ with probabilities such
that the output value equals the input $y$ in expectation. Note that each
output coordinate of the CUQ encoder takes $k+1$ values – $k$ of these symbols
correspond to the $k$ uniform levels and the additional symbol corresponds to
the overflow symbol $\emptyset$. Thus we need a total precision of
$d\left\lceil\log(k+1)\right\rceil$ bits to represent the output of the CUQ
encoder. The encoder and decoders used in CUQ are given in Algorithms 4 and 5,
respectively. In the decoder, we have set $B_{M,k}(\emptyset)$ to $0$.

1:Parameter $M\in\mathbb{R}^{+}$ and input $Y\in\mathbb{R}^{d}$ 2:for
$i\in[d]$ do 3: if $|Y(i)|>M$ then $Z(i)=\emptyset$ 4: else 5: for
$\ell\in\\{0,\ldots,k-1\\}$ do 6: if
${Y}(i)\in(B_{M,k}(\ell),B_{M,k+1}(\ell+1)]$ then 7:
${Z}(i)=\begin{cases}\ell+1,\quad
w.p.~{}\frac{{Y}(i)-B_{M,k}(\ell)}{B_{M,k}(\ell+1)-B_{M,k}(\ell)}\\\
\ell,\hskip 17.07182pt\quad
w.p.~{}\frac{B_{M,k}(\ell+1)-{Y}(i)}{B_{M,k}(\ell+1)-B_{M,k}(\ell)}\end{cases}$
8:Output: $Q^{{\tt e}}_{\tt u}(Y;M)=Z$ Algorithm 4: Encoder $Q^{{\tt e}}_{\tt
u}(Y;M)$ of CUQ 1:Parameter $M\in\mathbb{R}^{+}$, input
$\displaystyle{Z\in\\{0,\dots,k-1,\emptyset\\}^{d}}$ 2:Set
$\hat{Y}(i)=B_{M,k}(Z(i))$, for all $i\in[d]$ 3:Output: $Q^{{\tt d}}_{\tt
u}(Z;M)=\hat{Y}$ Algorithm 5: Decoder $Q^{{\tt d}}_{\tt u}(Z;M)$ of CUQ

###### Adaptive Tetra-iterated Uniform Quantizer (ATUQ).

The quantizer ATUQ is CUQ with its dynamic-range chosen in an adaptive manner.
In order to a quantize a particular input vector, it first chooses a dynamic
range from $[-M_{i},M_{i}]$, $1\leq i\leq h$. To describe these $M_{i}$s, we
first define the $i^{th}$ tetra-iteration for $e$, denoted by $e^{*i}$,
recursively as follows:

${{e^{*0}:=1}},\quad e^{*1}:=e,\quad e^{*i}:=e^{e^{*(i-1)}},\quad
i\in\mathbb{N}.$

Also, for any non negative number $b$, we define
$\ln^{*}b:=\inf\\{i\in\mathbb{N}:e^{*i}\geq b\\}.$ With this notation, the
values $M_{i}$s are defined in terms of $m$ and $m_{0}$ as follows:

$\displaystyle M_{i}^{2}=m\cdot
e^{*i}+m_{0},\quad\forall\,i\in\\{0,\ldots,h-1\\},$

where the parameters $m$ and $m_{0}$ will be set later. ATUQ finds the
smallest level $M_{i}$ which bounds the infinity norm of the input vector; if
no such $M_{i}$ exists, it simply uses $M_{h-1}$. It then uses CUQ with
dynamic range $[-M_{i},M_{i}]$ to quantize the input vector. In RATQ, we apply
ATUQ to each subvector. The decoder of ATUQ is simply the decoder of CUQ using
the dynamic range outputted by the ATUQ encoder.

Note that in order to represent the output of ATUQ for $d$ dimensional inputs,
we need a precision of at the most $\left\lceil\log
h\right\rceil+d\left\lceil\log(k+1)\right\rceil$ bits: $\left\lceil\log
h\right\rceil$ bits to represent the dynamic range and at the most
$d\left\lceil\log(k+1)\right\rceil$ bits to represent the output of CUQ. The
encoder and decoder for ATUQ are given in Algorithms 6 and 7, respectively.

1:Input $Y\in\mathbb{R}^{d}$ 2:if $\|Y\|_{\infty}>M_{h-1}$ then Set
$M^{*}=M_{h-1}$ 3:elseSet $j^{*}=\min\\{j:\|Y\|_{\infty}\leq M_{j}\\},$
$M^{*}=M_{j^{*}}$ 4:Set $Z=Q^{{\tt e}}_{\tt u}(Y;M^{*})$ 5:Output: $Q^{{\tt
e}}_{\tt at}(Y)=\\{Z,j^{*}\\}$ Algorithm 6: Encoder $Q^{{\tt e}}_{{\tt
at}}(Y)$ for ATUQ 1:Input $\\{Z,j\\}$ with
$Z\in\\{0,\dots,k-1,\emptyset\\}^{d}$ and $j\in\\{0,\dots h-1\\}$ 2:Output:
$Q^{{\tt d}}_{\tt at}(Z,j)=Q^{{\tt d}}_{\tt u}(Z;M_{j})$ Algorithm 7: Decoder
$Q^{{\tt d}}_{\tt at}(Z,j)$ for ATUQ

When ATUQ is applied to each subvector in RATQ, each of the $\left\lceil
d/s\right\rceil$ subvectors are represented using less than $\left\lceil\log
h\right\rceil+s\left\lceil\log(k+1)\right\rceil$ bits. Thus, the overall
precision for RATQ is less than777$\log$ denotes the logarithm to the base
$2$, $\ln$ denotes logarithm to the base $e$.

$\left\lceil d/s\right\rceil\cdot\left\lceil\log
h\right\rceil+d\left\lceil\log(k+1)\right\rceil$

bits. The decoder of RATQ is simply formed by collecting the output of the
ATUQ decoders for all the subvectors to form a $d$-dimensional vector, and
rotating it back using the matrix $R^{-1}$ (the inverse of the rotation matrix
used at the encoder).

######  Remark 12 (Advantage of division into subvectors).

The overall precision of RATQ allows us to understand the advantage of
clubbing multiple coordinates into subvectors. Since we use the same dynamic
range for all coordinates of a subvector, we save on coordinate-wise
communication of the dynamic range.

######  Remark 13 (Mean square error of ATUQ).

The per coordinate mean square error between the input to ATUQ and its output
roughly grows as

$\displaystyle O\left(\frac{\sum_{i\in[h]}M_{i}^{2}\cdot
p(M_{i-1})}{(k-1)^{2}}\right),$ (7)

where $p(M)$ is the probability of the $\ell_{\infty}$ norm of the input
vector exceeding $M$ and $k$ denotes the number of levels of the uniform
quantizer. This observation allows us to relate the mean square error to the
tail-probabilities of the $\ell_{\infty}$ norm of the input vector. In
particular, we exploit it to decide on the dimension $s$ of subvectors as well
as the growth rate of $M_{i}$s.

######  Remark 14 (Growth rate of Tetration).

A key distinguishing feature of RATQ is choosing the set of $M_{i}$s to grow
as a tetration, roughly as $M_{i+1}=e^{M_{i}}$. The large growth rate of a
tetration allows us to cover the complete range of each coordinate using only
a small number of dynamic ranges, which leads to an unbiased quantizer and
reduces the communication. Also, after random rotation, each coordinate of the
vector is a centered subgaussian random variable with a variance-parameter of
$O(B^{2}/d)$ (see Remark 11), which, despite the large growth rate of a
tetration, ensures that the per coordinate mean square error between the
quantized output and the input is almost a constant, as can be seen from (7).

###### Choice of parameters.

Throughout the remainder of this section, we set our parameters $m$, $m_{0}$,
and $h$ as follows

$\displaystyle m=\frac{3B^{2}}{d},\quad m_{0}=\frac{2B^{2}}{d}\cdot\ln
s,\quad\log h=\left\lceil\log(1+\ln^{\ast}(d/3))\right\rceil.$ (8)

In particular, this results in $M_{h-1}\geq B$ whereby, for an input $Y$ with
$\|Y\|_{2}^{2}\leq B^{2}$, RATQ outputs an unbiased estimate of $Y$.

We close with a remark on the computational complexity of RATQ.

######  Remark 15 (Computational complexity of RATQ).

Since $R$ is a Hadamard matrix, the matrix multiplication at the encoder and
the decoder requires $O(d\log d)$ real operations888Each addition,
subtraction, multiplication, or division operation on the real field will be
referred to as a real operation. Further, it takes $O(\log h)$ real operations
to find the dynamic-range for each subvector, whereby the overall complexity
for finding dynamic-ranges for $\left\lceil d/s\right\rceil$ subvectors is
$O(\left\lceil d/s\right\rceil\log h)$ real operations; we can represent each
of these dynamic-ranges as a $\log h$-bit binary string in another
$O(\left\lceil d/s\right\rceil\log h)$ real operations, too. Note that the
encoding complexity of CUQ for an input subvector of dimension $s$ is $s$ real
operations, and thus, the overall complexity of $\left\lceil d/s\right\rceil$
CUQ operations is $O(d)$ real operations. Finally, we need $O(d\log k)$ real
operations to represent the quantized values of $d$ coordinates to $k$ levels
$\log k$-bit binary strings. Putting it all together, the overall complexity
of the encoding procedure is $O(d\log d+d\log h/s+d\log k)$. By similar
arguments, the complexity of real operations at the decoder would also be
$O(d\log d+d\log h/s+d\log k)$.

Throughout the chapter, our choice of parameters $s$, $h$, and $k$ for RATQ,
which is roughly the optimal choice of these parameters for quantizing the
$\ell_{2}$ ball, would result in quantities $d\log h/s$ and $d\log k$ to be
much lesser than $d\log d$. Thus, for parameters as chosen in this chapter or
other reasonable choices of $s$, $h$, $k$, the encoding and decoding
complexity of RATQ is $O(d\log d)$. Note that the random rotation based
quantizer from [88] also has encoding and decoing complexity of $O(d\log d)$.

#####  2 RATQ in the high-precision regime

The following result shows that RATQ is unbiased for almost surely bounded
inputs and provides a bound for its worst-case second order moment; this
constitutes a key technical tool for characterizing the performance of RATQ.

######  Theorem 4.2 (Performance of RATQ).

Let $Q_{{\tt at},R}$ be the quantizer RATQ with $M_{j}$s set by (8). Then, for
all $s,k\in\mathbb{N}$,

$\displaystyle\alpha_{2}(Q_{{\tt at},R})$ $\displaystyle\leq
B\sqrt{\frac{9+3\ln s}{(k-1)^{2}}+1},\quad\beta_{2}(Q_{{\tt at},R})=0.$ (9)

The proof is deferred to Section 3.

Thus, $\alpha_{2}$ is lower when $s$ is small, but the overall precision
needed grows since the number of subvectors increases. The following choice of
parameters yields almost optimal performance:

$\displaystyle s=\log h,\quad\log(k+1)=\left\lceil\log(2+\sqrt{9+3\ln
s})\right\rceil.$ (10)

For these choices, we obtain the following.

######  Corollary 4.3.

The overall precision $r$ used by the quantizer $Q=Q_{{\tt at},R}$ with
parameters set as in (8), (10) satisfies

$r\leq d(1+\Delta_{1})+\Delta_{2},$

where
$\Delta_{1}=\left\lceil\log\left(2+\sqrt{9+3\ln\Delta_{2}}\right)\right\rceil$
and $\Delta_{2}=\left\lceil\log(1+\ln^{*}({d}/{3}))\right\rceil$.
Furthermore, the optimization protocol $\pi$ given in Algorithm 1 satisfies

$\sup_{(f,O)\in\mathcal{O}_{{\tt
c},2}}\mathcal{E}(f,O,\pi,Q)\leq\frac{\sqrt{2}DB}{\sqrt{T}}\text{and}$
$\sup_{(f,O)\in\mathcal{O}_{{\tt
sc}}}\mathcal{E}(f,O,\pi,Q)\leq\frac{2B^{2}}{\gamma T}.$

###### Proof.

By the description RATQ, it encodes the subgradients using a fixed-length code
of at the most $\left\lceil d/s\right\rceil\cdot\left\lceil\log
h\right\rceil+d\left\lceil\log(k+1)\right\rceil$ bits. Upon substituting $s$,
$\log h$, and $\log(k+1)$ as in (10) and (8), we obtain that the total
precision is bounded above by $d(1+\Delta_{1})+\Delta_{2}$.

For the second statement of the corollary, we have

$\displaystyle\sup_{(f,O)\in\mathcal{O}_{{\tt c},2}}\mathcal{E}(f,O,\pi,Q)$
$\displaystyle\leq D\left(\frac{\alpha_{2}(Q_{{\tt
at},R})}{\sqrt{T}}+\beta_{2}(Q_{{\tt at},R})\right)$
$\displaystyle\leq\frac{DB}{\sqrt{T}}\cdot\sqrt{\frac{9+3\ln
s}{(k-1)^{2}}+1}\hskip 2.84544pt$
$\displaystyle\leq\frac{\sqrt{2}DB}{\sqrt{T}},$

where the first inequality follows by Theorem 3.2, the second inequality
follows by upper bounding $\alpha_{2}(Q_{{\tt at},R})$ and $\beta_{2}(Q_{{\tt
at},R})$ using Theorem 4.2, and the third follows by substituting the
parameters in the corollary statement. The upper bound for the strongly convex
family follows in precisely the same manner. In particular, by combining
Theorem 3.3 with Theorem 4.2, we have

$\displaystyle\sup_{(f,O)\in\mathcal{O}_{{\tt sc}}}\mathcal{E}(f,O,\pi,Q)$
$\displaystyle\leq\frac{2B^{2}}{\gamma T}.$

∎

######  Remark 16.

The precision requirement in Corollary 4.3 matches the $d$-bit lower bound of
Corollary 4.1 upto a multiplicative factor of
$O\left(\log\log\log\ln^{*}(d/3)\right)$.

#####  3 RATQ in the low-precision regime

We present a general method for reducing precision to much below $d$. This
scheme is applicable when the output of the quantizer’s encoder is a $d$
length vector, where each coordinate is a separate fixed-length code. We
simply reduce the length of the output message vector from the quantizer’s
encoder by sub-sampling a subset of coordinates using shared randomness. The
decoder obtains the values of these coordinates using the decoder for the
original quantizer and sets the rest of the coordinate-values to zero. This
subsampling layer, which we call the Random Coordinate Sampler (RCS), can be
added to RATQ after applying random rotation. In particular, $RATQ$ we need
the parameter $s$ of these quantizers to be set to 1. This requirement of
setting $s=1$ ensures that the subsampled coordinates of the rotated vector
can be decoded separately. This is a randomized scheme and requires the
encoder and the decoder to share a random set $S\subset[d]$ distributed
uniformly over all subsets of $[d]$ of cardinality $\mu d$.

The encoder $Q^{{\tt e}}_{S}$ of RCS simply outputs the vector

$Q^{{\tt e}}_{S}(Y):=\\{Y(i),i\in S\\},$

and the decoder $Q^{{\tt d}}_{S}(\tilde{Y})$, when applied to a vector
$\tilde{Y}\in\mathbb{R}^{\mu d}$, outputs

$Q^{{\tt d}}_{S}(\tilde{Y}):=\mu^{-1}\sum_{i\in S}\tilde{Y}(i)e_{i},$

where $e_{i}$ denotes the $i$th element of standard basis for
$\mathbb{R}^{d}$.

We can compose RCS with RATQ with parameter $s=1$ by setting the encoder to
$Q^{{\tt e}}_{S}\circ Q^{{\tt e}}$, and setting the decoder to $Q^{{\tt
d}}\circ Q^{{\tt d}}_{S}$. Here we follow the convention that all
$0$-coordinates outputted by $Q^{{\tt d}}_{S}$ are decoded as $0$ by $Q^{{\tt
d}}$. Note that since we need to retain RATQ encoder output for only $\mu d$
coordinates, the overall precision of the quantizer is reduced by a factor of
$\mu$. We analyze the performance of this combined quantizer in the following
theorem.

######  Theorem 4.4.

Let $Q_{{\tt at},R}$ be RATQ with $s=1$ and $\tilde{Q}$ be the combination of
RCS and $Q_{{\tt at},R}$ as described above. Then,

$\mathbb{E}\left[\tilde{Q}(Y)|Y\right]=\mathbb{E}\left[Q_{{\tt
at},R}(RY)|Y\right]\quad\text{and}\quad\mathbb{E}\left[\|\tilde{Q}(Y)\|_{2}^{2}|Y\right]=\frac{1}{\mu}\mathbb{E}\left[\|Q_{{\tt
at},R}(RY)\|_{2}^{2}|Y\right],$

which further leads to

$\alpha_{2}(\tilde{Q})\leq\frac{\alpha_{2}(Q_{{\tt
at},R})}{\sqrt{\mu}}\quad\text{and}\quad\beta_{2}(\tilde{Q})=\beta_{2}(Q_{{\tt
at},R}).$

###### Proof.

By the description of $Q_{{\tt at},R}$, we have

$\tilde{Q}(Y)=\frac{1}{\mu}R^{-1}\sum_{i\in S}Q_{{\tt at},I}(RY)(i)e_{i},$

where $Q_{{\tt at},I}$ is the output vector formed by combining the $d$
quantized values outputted by ATUQ ($Q_{\tt at}$) when input is the rotated
vector. Namely,

$Q_{{\tt at},I}(RY)=[Q_{{\tt at}}(RY(1)),\cdots,Q_{{\tt at}}(RY(d))]^{T}.$

For the mean of $\tilde{Q}(Y)$, it holds that

$\displaystyle\mathbb{E}\left[\tilde{Q}(Y)|Y\right]$
$\displaystyle=\mathbb{E}\left[R^{-1}\sum_{i\in d}Q_{{\tt
at},I}(RY)(i)e_{i}\frac{1}{\mu}\mathbbm{1}_{i\in S}|Y\right]$
$\displaystyle=\sum_{i\in d}\mathbb{E}\left[R^{-1}Q_{{\tt
at},I}(RY)(i)e_{i}|Y\right]\cdot\frac{1}{\mu}\mathbb{E}\left[\mathbbm{1}_{i\in
S}|Y\right]$ $\displaystyle=\sum_{i\in d}\mathbb{E}\left[R^{-1}Q_{{\tt
at},I}(RY)(i)e_{i}|Y\right]$ $\displaystyle=\mathbb{E}\left[R^{-1}\sum_{i\in
d}Q_{{\tt at},I}(RY)(i)e_{i}|Y\right]$
$\displaystyle=\mathbb{E}\left[R^{-1}Q_{{\tt at},I}(RY)|Y\right]$
$\displaystyle=\mathbb{E}\left[Q_{{\tt at},R}(RY)|Y\right],$ (11)

where the second identity follows from the fact that randomness used to
generate a set $S$ is independent of the randomness used in the quantizer and
the randomness of $Y$; the third identity holds since $P(i\in S)=\mu$.

Next, moving to the computation of the second moment of the output of
$\tilde{Q}$, we have

$\displaystyle\mathbb{E}\left[\|\tilde{Q}(Y)\|_{2}^{2}|Y\right]$
$\displaystyle=\mathbb{E}\left[\|\frac{1}{\mu}R^{-1}\sum_{i\in S}Q_{{\tt
at},I}(RY)(i)e_{i}\|_{2}^{2}|Y\right]$
$\displaystyle=\frac{1}{\mu^{2}}\mathbb{E}\left[\|\sum_{i\in S}Q_{{\tt
at},I}(RY)(i)e_{i}\|_{2}^{2}|Y\right]$
$\displaystyle=\frac{1}{\mu^{2}}\sum_{i\in[d]}\mathbb{E}\left[Q_{{\tt
at},I}(RY)(i)^{2}|Y\right]\mathbb{E}\left[\mathbbm{1}_{i\in S}|Y\right]$
$\displaystyle=\frac{1}{\mu}\mathbb{E}\left[\|Q_{\tt
at}(RY)\|_{2}^{2}|Y\right]$
$\displaystyle=\frac{1}{\mu}\mathbb{E}\left[\|Q_{{\tt
at},R}(RY)\|_{2}^{2}|Y\right],$ (12)

where the second identity follows from the fact that $R$ is a unitary matrix
and the remaining steps follow simply by the description of the quantizers
used. It follows that

$\displaystyle\alpha(\tilde{Q})=\frac{1}{\sqrt{\mu}}\alpha(Q_{{\tt
at},R}),\quad\beta(\tilde{Q})=\beta(Q_{{\tt at},R}).$

∎

We now set the parameter $k$ to be a constant and sample roughly $r$
coordinates. Specifically, we set

$\displaystyle s$ $\displaystyle=1,\quad\log(k+1)=3,$ $\displaystyle\mu d$
$\displaystyle=\min\\{d,\lfloor
r/({3+\left\lceil\log(1+\ln^{*}({d}/{3}))\right\rceil})\rfloor\\}.$ (13)

For these choices, we have the following corollary.

######  Corollary 4.5.

For $r\geq 3+\left\lceil\log(1+\ln^{*}({d}/{3}))\right\rceil$, let $Q$ be the
composition of RCS and RATQ with parameters set as in (8), (13). Then, the
optimization protocol $\pi$ in Algorithm 1 satisfies

$\sup_{(f,O)\in\mathcal{O}_{{\tt
c},2}}\mathcal{E}(f,O,\pi,Q)\leq\frac{\sqrt{2}DB}{\sqrt{\mu T}},$
$\sup_{(f,O)\in\mathcal{O}_{{\tt
sc}}}\mathcal{E}(f,O,\pi,Q)\leq\frac{2B^{2}}{\mu\gamma T}.$

###### Proof.

When $Q$ is a composition of RCS and RATQ, from Theorem 5.3 $\alpha_{2}^{\tt
m}(Q)\leq\frac{1}{\sqrt{\mu}}\alpha(Q_{{\tt at},R}),\quad\beta_{2}^{\tt
m}(Q)\leq\beta(Q_{{\tt at},R}),$ which by Theorem 3.2 yields

$\displaystyle\sup_{(f,O)\in\mathcal{O}_{{\tt c},2}}\mathcal{E}(f,O,\pi,Q)$
$\displaystyle\leq D\left(\frac{\alpha_{2}(Q_{{\tt at},R})}{\sqrt{\mu
T}}+\beta_{2}(Q_{{\tt at},R})\right)$ $\displaystyle\leq\frac{DB}{\sqrt{\mu
T}}\cdot\sqrt{\frac{9}{(k-1)^{2}}+1}\hskip 2.84544pt$
$\displaystyle\leq\frac{\sqrt{2}DB}{\sqrt{T}}\cdot\frac{\sqrt{d}}{\sqrt{\min{\\{d,\lfloor
r/(3+\log\ln^{*}(d/3))\rfloor\\}}}},$

where the second inequality follows from Theorem 4.2 with $s=1$, and the final
inequality is obtained upon substituting the parameters as in the statement of
the result. Similarly, for strongly convex function family, the result follows
by combining Theorem 4.6 and 5.3.

∎

######  Remark 17.

Note that the convergence rate slows down by a $\mu$ specified in (13), which
matches the lower bounds in Theorem 4.4 (for $p=2$) and 4.6 upto a
multiplicative factor of $O(\log\ln^{*}(d/3))$

####  5 Main results for mean square bounded oracles

In this section, we present results only for the convex family. We do this to
avoid repetition since we can derive upper bounds for strongly convex family
precisely in the same manner as convex family, as seen from the previous
section.

With the mean square bounded assumption, we now need to quantize random
vectors $Y$ such that $\mathbb{E}\left[\|Y\|_{2}^{2}\right]\leq B^{2}$. We
take recourse to the standard gain-shape quantization paradigm in vector
quantization ($cf.$[34]).

######  Definition 5.1 (Gain-shape quantizer).

A Quantizer Q is defined to be a gain-shape quantizer if it has the following
form

$Q(Y)=Q_{g}(\|Y\|_{2})\cdot Q_{s}(Y/\|Y\|_{2}),$

where $Q_{g}$ is any $\mathbb{R}\rightarrow\mathbb{R}$ quantizer and $Q_{s}$
is any $\mathbb{R}^{d}\rightarrow\mathbb{R}^{d}$ quantizer.

Specifically, we separately quantize the gain $\|Y\|_{2}$ and the shape999For
the event $\|Y\|_{2}=0$, we follow the convention that $Y/\|Y\|_{2}=e_{1}$.
$Y/\|Y\|_{2}$ of $Y$, and form the estimate of $Y$ by simply multiplying the
estimates for the gain and the shape. Note that we already have a good shape
quantizer: RATQ. We only need to modify the parameters in (8) to make it work
for the unit sphere; we set

$\displaystyle m=\frac{3}{d},\quad m_{0}=\frac{2}{d}\cdot\ln s,\quad\log
h=\left\lceil\log(1+\ln^{\ast}(d/3))\right\rceil.$ (14)

We now proceed to derive the worst-case $\alpha$ and $\beta$ for a general
gain-shape. In order to make clear the dependence on $B$ and $d$, we refine
our notations for $\\{\alpha_{2}^{\tt m}(Q),\beta_{2}^{\tt m}(Q)\\}$ and
$\\{\alpha_{2}(Q),\beta_{2}(Q)\\}$, defined in (4) and (5), respectively, to
$\\{\alpha_{2}^{\tt m}(Q;B,d),\beta_{2}^{\tt m}(Q;B,d)\\}$ and
$\\{\alpha_{2}(Q;B,d),\beta_{2}(Q;B,d)\\}$.

######  Theorem 5.2.

Let $Q(Y)=Q_{1}(\|Y\|_{2})\cdot Q_{2}(Y/\|Y\|_{2}),$ where $Q_{1}$ is any gain
quantizer and $Q_{2}$ is any shape quantizer. Also, suppose $Q_{1}(\|Y\|_{2})$
and $Q_{2}(Y/\|Y\|_{2})$ are conditionally independent given $Y$. Then,

$\displaystyle\alpha_{2}^{\tt m}(Q;B,d)$ $\displaystyle\leq\alpha_{2}^{\tt
m}(Q_{1};B,1)\cdot\alpha_{2}(Q_{2};1,d).$

Furthermore, suppose that $Q_{2}$ satisfies

$\mathbb{E}\left[Q_{2}(y_{s})\right]=y_{s},\quad\forall y_{s}\quad
s.t.\quad\|y_{s}\|_{2}^{2}\leq 1.$

Then, we have101010The quantity on the right-side of this bound exceeds the
bias $\beta_{2}^{\tt m}(Q_{1};B,1)$. Nonetheless, in all our bounds for bias,
this is the quantity we have been handling.

$\displaystyle\beta_{2}^{\tt m}(Q;B,d)$
$\displaystyle\leq\sup_{Y\in\mathbb{R}^{d}:\mathbb{E}\left[\|Y\|_{2}^{2}\right]\leq
B^{2}}\mathbb{E}\left[\bigg{|}\mathbb{E}\left[Q_{1}(\|Y\|_{2})-\|Y\|_{2}\mid
Y\right]\bigg{|}\right].$

###### Proof.

Denote by $Y_{s}$ the shape of the vector $Y$ given by

$Y_{s}:=\frac{Y}{\|Y\|_{2}}.$

###### The worst-case second moment:

Towards evaluating $\alpha(Q;B,d)$, we have

$\displaystyle\mathbb{E}\left[\|Q(Y)\|_{2}^{2}\right]$
$\displaystyle=\mathbb{E}\left[Q_{1}(\|Y\|_{2})^{2}\|Q_{2}(Y_{s})\|_{2}^{2}\right]$
$\displaystyle=\mathbb{E}\left[\mathbb{E}\left[Q_{1}(\|Y\|_{2})^{2}\|Q_{2}(Y_{s})\|_{2}^{2}|Y\right]\right]$
$\displaystyle=\mathbb{E}\left[\mathbb{E}\left[Q_{1}(\|Y\|_{2})^{2}|Y\right]\mathbb{E}\left[\|Q_{2}(Y_{s})\|_{2}^{2}|Y\right]\right]$
$\displaystyle=\mathbb{E}\left[\mathbb{E}\left[Q_{1}(\|Y\|_{2})^{2}|Y\right]\mathbb{E}\left[\|Q_{2}(Y_{s})\|_{2}^{2}|Y_{s}\right]\right],$

where the third identity follows by conditional independence of
$Q_{1}(\|Y\|_{2})^{2}$ and $\|Q_{2}(Y_{s})\|_{2}^{2}$ given $Y$ and the fourth
follows from the law of iterated expectations.

Consider the random variable
$\mathbb{E}\left[\|Q_{2}(Y_{s})\|_{2}^{2}|Y_{s}\right]$. We claim that this is
less than $\alpha_{0}(Q_{2};1,d)$ almost surely. Towards this end, note that

$\mathbb{E}\left[\|Q_{2}(Y_{s})\|_{2}^{2}|Y_{s}=y\right]=\mathbb{E}\left[\|Q_{2}(y)\|_{2}^{2}\right],$

since the randomness used in implementation of $Q_{2}$ is independent of the
input random variable $Y$. Moreover, for any $y$ with $\|y\|_{2}^{2}\leq 1$,
we have from the definition of $\alpha_{2}(Q_{2};1,d)$ that
$\mathbb{E}\left[\|Q_{{2}}(y)\|_{2}^{2}\right]\leq\alpha_{2}(Q_{2};1,d)^{2}$.
Therefore, for any $Y$ with $\mathbb{E}\left[\|Y\|_{2}^{2}\right]\leq B^{2}$,
we have

$\displaystyle\mathbb{E}\left[\|Q(Y)\|_{2}^{2}\right]$
$\displaystyle=\mathbb{E}\left[\mathbb{E}\left[Q_{1}(\|Y\|_{2})^{2}|Y\right]\mathbb{E}\left[\|Q_{2}(Y_{s})\|_{2}^{2}|Y_{s}\right]\right]$
$\displaystyle\leq\mathbb{E}\left[\mathbb{E}\left[Q_{1}(\|Y\|_{2})^{2}|Y\right]\right]\cdot\alpha_{2}(Q_{2};1,d)^{2}$
$\displaystyle=\mathbb{E}\left[Q_{1}(\|Y\|_{2})^{2}\right]\cdot\alpha_{2}(Q_{2};1,d)^{2}$
$\displaystyle\leq\alpha_{2}^{\tt
m}(Q_{1};B,1)^{2}\cdot\alpha_{2}(Q_{2};1,d)^{2}.$ (15)

Taking the supremum of the left-side over all random vectors $Y$ with
$\mathbb{E}\left[\|Y\|_{2}^{2}\right]\leq B^{2}$ gives us the desired bound
for $\alpha_{2}^{\tt m}(Q;B,d)$.

###### The worst-case bias:

Towards evaluating $\beta_{2}^{\tt m}(Q;B,d)$, we note from our hypothesis
that
$\mathbb{E}\left[Q_{2}(Y_{s})|Y\right]=\mathbb{E}\left[Q_{2}(Y_{s})|Y_{s}\right]=Y_{s}$,
which further yields

$\displaystyle\mathbb{E}\left[Q(Y)-Y\right]$
$\displaystyle=\mathbb{E}\left[\mathbb{E}\left[Q_{1}(\|Y\|_{2})Q_{2}(Y_{s})-Y|Y\right]\right]$
$\displaystyle=\mathbb{E}\left[\mathbb{E}\left[Q_{1}(\|Y\|_{2})|Y\right]\mathbb{E}\left[Q_{2}(Y_{s})|Y\right]-Y\right]$
$\displaystyle=\mathbb{E}\left[\mathbb{E}\left[Q_{1}(\|Y\|_{2})|Y\right]Y_{s}-\|Y\|_{2}Y_{s}\right]$
$\displaystyle=\mathbb{E}\left[\mathbb{E}\left[Q_{1}(\|Y\|_{2})-\|Y\|_{2}|Y\right]Y_{s}\right],$
(16)

where the second identity uses conditional independence of $Q_{1}(\|Y\|_{2})$
and $Q_{2}(Y_{s})$. By using the conditional Jensen’s inequality, we get

$\displaystyle\|\mathbb{E}\left[Q(Y)-Y\right]\|_{2}$
$\displaystyle=\|\mathbb{E}\left[\mathbb{E}\left[Q_{1}(\|Y\|_{2})-\|Y\|_{2}|Y\right]Y_{s}\right]\|_{2}$
$\displaystyle\leq\mathbb{E}\left[\|\mathbb{E}\left[Q_{1}(\|Y\|_{2})-\|Y\|_{2}|Y\right]Y_{s}\|_{2}\right]$
$\displaystyle=\mathbb{E}\left[\bigg{|}\mathbb{E}\left[Q_{1}(\|Y\|_{2})-\|Y\|_{2}|Y\right]\bigg{|}\right].$

∎

We remark that quantizers proposed in most of the prior work can be cast in
this gain-shape framework. Most works simply state that gain is a single
parameter which can be quantized using a fixed number of bits; for instance, a
single double precision number is prescribed for storing the gain. However,
the quantizer is not specified. We carefully analyze this problem and
establish lower bounds when a uniform quantizer with a fixed dynamic range is
used for quantizing the gain. Further, we present our own quantizer which
significantly outperforms uniform gain quantization.

#####  1 Limitation of uniform gain quantization

We establish lower bounds for a general class of gain-shape quantizers
$Q(y)=Q_{g}(\|y\|_{2})Q_{s}(y/\|y\|_{2})$ of precision $r$ that satisfy the
following structural assumptions:

  1. 1.

(Independent gain-shape quantization) For any given $y\in\mathbb{R}^{d}$, the
output of the gain and the shape quantizers are independent.

  2. 2.

(Bounded dynamic-range) For any $y\in\mathbb{R}^{d}$, there exists a $M>0$
such that whenever $\|y\|_{2}>M$, $Q(y)$ has a fixed distribution
$P_{\emptyset}$.

  3. 3.

(Uniformity) There exists $m\in[M/{2^{r}},M]$ such that for every $t$ in
$[0,m]$,

    1. (a)

${\tt supp}(Q_{g}(t))\subseteq\\{0,m\\}$;

    2. (b)

If $P(Q_{g}(t)=m)>0$, then

$\frac{P(Q_{g}(t_{2})=m)}{P(Q_{g}(t_{1})=m)}\leq~{}\frac{t_{2}}{t_{1}},\quad\forall\,0\leq
t_{1}\leq t_{2}\leq m.$

The first two assumptions are perhaps clear and hold for a large class of
quantizers. The third one is the true limitation and is satisfied by different
forms of uniform gain quantizers. For instance, for the one-dimensional
version of CUQ with dynamic range $[0,M]$, which is an unbiased, uniform gain
quantizer with $k_{g}$ levels, it holds with $m=M/(k_{g}-1)$ (corresponding to
the innermost level $[0,M/(k_{g}-1)]$). It can also be shown to include a
deterministic uniform quantizer that rounds-off at the mid-point. The third
condition, in essence, captures the unbiasedness requirement that the
probability of declaring higher level is proportional to the value. Note that
$(t_{2}/t_{1})$ on the right-side can be replaced with any constant multiple
of $(t_{2}/t_{1})$. For easy reference, we will refer to these assumptions as
Structural Assumptions 1-3.

Below we present lower bounds for performance of any optimization protocol
using a gain-shape quantizer that satisfies the assumptions above. We present
separate results for high-precision and low-precision regimes, but both are
obtained using a general construction that exploits the admissibility of
heavy-tail distributions for mean square bounded oracles. This construction is
new and may be of independent interest.

######  Theorem 5.3.

Consider a gain-shape quantizer $Q$ satisfying Structural Assumptions 1-3.
Suppose that for $\mathcal{X}=\\{x:\|x\|_{2}\leq D/2\\}$ we can find an
optimization protocol $\pi$ which, using at most $T$ iterations, achieves
$\sup_{f,O\in\mathcal{O}}\mathcal{E}(f,O,\pi,Q)\leq\frac{3DB}{\sqrt{T}}.$
Then, we can find a universal constant $c$ such that the overall precision $r$
of the quantizer must satisfy

$r\geq c(d+\log T).$

######  Theorem 5.4.

Consider a gain-shape quantizer $Q$ satisfying Structural Assumptions 1-3.
Suppose that the number of bits $r_{g}$ used by the gain quantizer are fixed
independently of $T$. Then, for $\mathcal{X}=\\{x:\|x\|_{2}\leq D/2\\}$, there
exists $(f,O)\in\mathcal{O}$ such that for any optimization protocol $\pi$
using at most $T$ iterations, we must have

$\mathcal{E}(f,O,\pi,Q)\geq\frac{{{c(r_{g})}}DB}{T^{1/3}},$

where $c({r_{g}})$ is a constant depending only on the number of bits used by
the gain quantizer (but not on $T$).

The proofs of Theorems 5.3 and 5.4 are technical and long; we defer them to
Section 6.

######  Remark 18.

Thus, from Theorem 5.3, for any optimization algorithm to achieve the error of
$O(1/\sqrt{T})$ after $T$ iterations, when used a quantizer satisfying the
Structural Assumptions 1-3, the precision of the quantizer at every iteration
must scale at least as roughly $\log T$. Conversely, from Theorem 5.4, if we
use a quantizer with precision fixed independently of $T$, then any
optimization algorithm used with this quantizer must have error at least
$\Omega(1/T^{1/3})$.

#####  2 A-RATQ in the high-precision regime

Instead of quantizing the gain uniformly, we propose to use an adaptive
quantizer termed Adaptive Geometric Uniform Quantizer (AGUQ) for gain. AGUQ
operates similar to the one-dimensional ATUQ, except the possible dynamic-
ranges $M_{g,0},\ldots,M_{g,h}$ grow geometrically (and not using tetra-
iterations of ATUQ) as follows:

$\displaystyle M_{g,j}^{2}=B^{2}\cdot a_{g}^{j},\quad 0\leq j\leq h_{g}-1.$
(17)

Specifically, for a given gain $G\geq 0$, AGUQ first identifies the smallest
$j$ such that $G\leq M_{g,j}$ and then represents $G$ using the one-
dimensional version of CUQ with a dynamic range $[0,M_{g,j}]$ and $k_{g}$
uniform levels

$\displaystyle
B_{M_{g,j},k}(\ell):=\ell\cdot\frac{M_{g,j}}{k_{g}-1},\quad\forall\,\ell\in\\{0,\ldots,k-1\\}.$

As in ATUQ, if $G>M_{h_{g}-1}$, the overflow $\emptyset$ symbol is used and
the decoder simply outputs $0$. The overall procedure is the similar to
Algorithms (6) and (7) for $s=1,h=h_{g}$, and $M_{j}=M_{g,j}$, $0\leq j\leq
h_{g}-1$; the only changes is that now we restrict to nonnegative interval
$[0,M_{g,j}]$ for the one-dimensional version of CUQ with uniform levels
$k_{g}$.

The following result characterizes the performance of one-dimensional
quantizer AGUQ; it is the only component missing in the analysis of A-RATQ.

######  Lemma 5.5.

Let $Q_{{\tt a}}$ be the quantizer AGUQ described above, with $h_{g}\geq 2$.
Then,

$\displaystyle\alpha_{2}^{\tt m}(Q_{{\tt a}};B,1)\leq
B\sqrt{\frac{1}{4(k_{g}-1)^{2}}+{\frac{a_{g}(h_{g}-1)}{4(k_{g}-1)^{2}}}+1},$
$\displaystyle\beta_{2}^{\tt m}(Q_{{\tt a}};B,1)\leq\sup_{Y\geq 0\text{ a.s.
}:\mathbb{E}\left[Y^{2}\right]\leq
B^{2}}\mathbb{E}\left[\bigg{|}\mathbb{E}\left[Q_{a}(Y)-Y|Y\right]\bigg{|}\right]\leq\frac{B^{2}}{M_{g,h_{g}-1}}.$

Proof of this result, too, is deferred to Section 4. Note that we have derived
a bound for a quantity that is slightly larger than the bias of $Q_{\tt a}$,
since we want to use this result along with Theorem 5.2.

Thus, our overall quantizer termed the adaptive-RATQ (A-RATQ) is given by

$Q(Y):=Q_{a}(\|Y\|_{2})\cdot Q_{{\tt at},R}(Y/\|Y\|_{2}),$

where $Q_{a}$ denotes the one dimensional AGUQ and $Q_{{\tt at},R}$ denotes
the $d\text{-dimensional}$ RATQ. Note that we use independent randomness for
$Q_{a}(\|Y\|_{2})$ and $Q_{{\tt at},R}(Y/\|Y\|_{2})$, rendering them
conditionally independent given $Y$.

The parameters $s,k$ for RATQ and $a_{g},k_{g}$ for AGUQ are yet to be set. We
first present a result which holds for all choices of these parameters.

######  Theorem 5.6 (Performance of A-RATQ).

For $Q$ set to A-RATQ with parameters set as in (14), (17), we have

$\displaystyle\alpha_{2}^{\tt m}(Q;B,d)\leq
B\sqrt{\frac{1}{4(k_{g}-1)^{2}}+{\frac{a_{g}(h_{g}-1)}{4(k_{g}-1)^{2}}}+1}\cdot\sqrt{\frac{9+3\ln
s}{(k-1)^{2}}+1},$ $\displaystyle\beta_{2}^{\tt
m}(Q;B,d)\leq\frac{B^{2}}{M_{g,h_{g}-1}}.$

###### Proof.

###### The worst-case second moment of A-RATQ:

By Theorem 5.2 we have

$\displaystyle\alpha_{2}^{\tt m}(Q;B,d)$ $\displaystyle\leq\alpha_{2}^{\tt
m}(Q_{\tt a};B,1)\cdot\alpha_{2}(Q_{{\tt at},R};1,d)$
$\displaystyle\leq\alpha_{2}^{\tt m}(Q_{\tt a};B,1)\cdot\sqrt{\frac{9+3\ln
s}{(k-1)^{2}}+1}$ $\displaystyle\leq
B\sqrt{\frac{1}{4(k_{g}-1)^{2}}+{\frac{a_{g}(h_{g}-1)}{4(k_{g}-1)^{2}}}+1}\cdot\sqrt{\frac{9+3\ln
s}{(k-1)^{2}}+1},$

where the second inequality used Theorem 4.2 with $B=1$, and the third follows
by Lemma 5.5.

###### The worst-case bias of A-RATQ:

With parameters of RATQ set as in (14), we have that

$\displaystyle\mathbb{E}\left[Q_{{\tt at},R}(y)\right]=y,\quad\forall y\quad
s.t\quad\|y\|_{2}^{2}\leq 1.$

Therefore, by Theorem 5.2 it follows that

$\displaystyle\beta_{2}^{\tt m}(Q;B,d)$
$\displaystyle\leq\sup_{Y:\mathbb{E}\left[\|Y\|_{2}^{2}\right]\leq
B^{2}}\mathbb{E}\left[\bigg{|}\mathbb{E}\left[Q_{\tt
a}(\|Y\|_{2})-\|Y\|_{2}|Y\right]\bigg{|}\right]\leq\frac{B^{2}}{M_{g,h_{g}-1}},$

where the second inequality follows from Lemma 5.5. ∎

Note that RATQ yields an unbiased estimator; the bias in A-RATQ arises from
AGUQ since the gain is not bounded. Further, AGUQ uses a precision of
$\left\lceil\log h_{g}\right\rceil+\left\lceil\log(k_{g}+1)\right\rceil$ bits,
and therefore, the overall precision of A-RATQ is $\left\lceil\log
h_{g}\right\rceil+\left\lceil\log(k_{g}+1)\right\rceil+\left\lceil
d/s\right\rceil\left\lceil\log
h\right\rceil+d\left\lceil\log(k+1)\right\rceil$ bits.

In the high-precision regime, we set

$\displaystyle a_{g}$ $\displaystyle=2,\quad\log
h_{g}=\left\lceil\log(1+\frac{1}{2}\log T)\right\rceil,$
$\displaystyle\log(k_{g}+1)$
$\displaystyle=\left\lceil\log\left(2+\frac{1}{2}\sqrt{\log
T+1}\right)\right\rceil.$ (18)

######  Corollary 5.7.

Denote by $Q$ the quantizer A-RATQ with parameters set as in (14), (10), and
(18). Then, the overall precision $r$ used by $Q$ is less than

$d(1+\Delta_{1})+\Delta_{2}+\left\lceil\log\bigg{(}2+\sqrt{\log
T+1}\bigg{)}\right\rceil,$

where
$\Delta_{1}=\left\lceil\log\left(2+\sqrt{9+3\ln\Delta_{2}}\right)\right\rceil$
and $\Delta_{2}=\left\lceil\log(1+\ln^{*}({d}/{3}))\right\rceil$, the same as
Corollary 4.3. Furthermore, the optimization protocol $\pi$ given in algorithm
1 satisfies
$\sup_{(f,O)\in\mathcal{O}}\mathcal{E}(f,O,\pi,Q)\leq{3DB}/{\sqrt{T}}$.

###### Proof.

The proof is similar to the proof of Corollary 4.3. The first statement
follows by simply upper bounding the precision of the fixed-length code for
A-RATQ with parameters as in the statement. The second statement follows by
bounding $\sup_{(f,O)\in\mathcal{O}}\mathcal{E}(f,O,\pi,Q)$ using Theorem 3.2,
using the upper bounds for $\alpha$ and $\beta$ given in Theorem 5.6, and
finally substituting the parameters. ∎

######  Remark 19.

The precision used in Corollary 5.7 matches the lower bound in Corollary 4.1
upto an additive factor of $\log\log T$ (ignoring the mild factor of
$\log\log\log\ln^{*}(d/3)$), which is much lower than the $\log T$ lower bound
we established for uniform gain quantizers. Hence, the precision requirement
of A-RATQ in the high-precision regime is considerably smaller than the
precision requirement of uniform gain quantizers established in Theorem 5.3
for $\log T\gg d(1+\Delta_{1})$, while remaining roughly the same for $\log
T=O(d(1+\Delta_{1}))$.

#####  3 A-RATQ in the low-precision regime

In order to operate with a fixed precision $r$, we combine A-RATQ with RCS. We
simply combine RCS with RATQ as in Section 3 to limit the precision and use
AGUQ as the gain quantizer. Note that we use independent randomness in our
gain quantizer $Q_{a}(\|Y\|_{2})$ and our shape quantizer
$\tilde{Q}(Y/\|Y\|_{2})$, rendering them conditionally independent given $Y$.
We have the following theorem characterizing $\alpha$ and $\beta$ for this
quantizer.

######  Theorem 5.8.

Let $Q(Y)=Q_{a}(\|Y\|)\cdot\tilde{Q}(Y/\|Y\|_{2})$, where $\tilde{Q}$ is the
composition of RCS and RATQ described in Theorem 5.3 with parameters $m$,
$m_{0}$, and $h$ of RATQ as in (14) and $Q_{a}$ is AGUQ. Then,

$\displaystyle\alpha_{2}^{\tt m}(Q;B,d)$ $\displaystyle\leq
B\sqrt{\frac{1}{4(k_{g}-1)^{2}}+{\frac{a_{g}(h_{g}-1)}{4(k_{g}-1)^{2}}}+1}\cdot\frac{1}{\sqrt{\mu}}\sqrt{\frac{9+3\ln
s}{(k-1)^{2}}+1},$ $\displaystyle\beta_{2}^{\tt m}(Q;B,d)$
$\displaystyle\leq\frac{B^{2}}{M_{g,h_{g}-1}}.$

###### Proof.

###### The worst-case second moment:

Starting by applying Theorem 5.2, we have

$\displaystyle\alpha_{2}^{\tt m}(Q;B,d)$ $\displaystyle\leq\alpha_{2}^{\tt
m}(Q_{\tt a};B,1)\cdot\alpha_{2}(\tilde{Q};1,d)$
$\displaystyle\leq\alpha_{2}^{\tt m}(Q_{\tt
a};B,1)\cdot\frac{1}{\sqrt{\mu}}\alpha_{2}(Q_{{\tt at},R};1,d)$
$\displaystyle\leq
B\sqrt{\frac{1}{4(k_{g}-1)^{2}}+{\frac{a_{g}(h_{g}-1)}{4(k_{g}-1)^{2}}}+1}\cdot\frac{1}{\sqrt{\mu}}\sqrt{\frac{9+3\ln
s}{(k-1)^{2}}+1},$

where the second inequality follows by Theorem 5.3 and the third follows by
Theorem 4.2 and Lemma 5.5.

###### The worst-case bias:

With parameters of RATQ set as in (14), we have that

$\displaystyle\mathbb{E}\left[\tilde{Q}(y)\right]=y,\quad\forall y\quad
s.t\quad\|y\|_{2}^{2}\leq 1.$

Therefore, by Theorem 5.2 we get

$\displaystyle\beta_{2}^{\tt m}(Q;B,d)$
$\displaystyle\leq\sup_{Y:\mathbb{E}\left[\|Y\|_{2}^{2}\right]\leq
B^{2}}\mathbb{E}\left[\bigg{|}\mathbb{E}\left[Q_{\tt
a}(\|Y\|_{2})-\|Y\|_{2}|Y\right]\bigg{|}\right]$
$\displaystyle\leq\frac{B^{2}}{M_{g,h_{g}-1}},$

where the second inequality follows from Lemma 5.5.

∎

We divide the total precision $r$ into $r_{g}$ and $r_{s}$ bits: $r_{g}$ to
quantize the gain, $r_{s}$ to quantize the subsampled shape vector. We set

$\displaystyle s,k,\text{~{}and~{}}\mu d\text{~{}as in
\eqref{e:RATQ_RCS_params}, with $r_{s}$ replacing $r$,}$ $\displaystyle{\log
h_{g}}=\log(k_{g}+1)={\frac{r_{g}}{2}},~{}a_{g}=\left(\mu
T\right)^{\frac{1}{h_{g}+1}}$ (19)

That is, our shape quantizer simply quantizes $\mu d$ randomly chosen
coordinates of the rotated vector using ATUQ with $r_{s}$ bits, and the
remaining bits are used by the gain quantizer AGUQ. The result below shows the
performance of this quantizer.

######  Corollary 5.9.

For any $r$ with gain quantizer being assigned $r_{g}\geq 4$ bits and shape
quantizer being assigned $r_{s}\geq
3+\left\lceil\log(1+\ln^{*}({d}/{3}))\right\rceil$, let $Q$ be the combination
of RCS and A-RATQ with parameters set as in (14), (17), (19). Then for $\mu
T\geq 1$, the optimization protocol $\pi$ in Algorithm 1 can obtain

$\sup_{(f,O)\in\mathcal{O}}\mathcal{E}(f,O,\pi,Q)\leq
O\left(DB\left(\frac{d}{T\min\\{d,\frac{r_{s}}{\log\ln^{*}(d/3)}\\}}\right)^{\frac{1}{2}\cdot\frac{2^{r_{g}/2}-1}{2^{r_{g}/2}+1}}\right).$

###### Proof.

By using Theorem 3.2 to upper bound $\sup_{(f,O)\in\mathcal{O}_{{\tt
c},2}^{\tt m}}\mathcal{E}(f,O,\pi,Q)$ and then Theorem 5.8 to upper-bound
$\alpha$ and $\beta$, we get

$\displaystyle\sup_{(f,O)\in\mathcal{O}_{{\tt c},2}^{\tt
m}}\mathcal{E}(f,O,\pi,Q)$ $\displaystyle\leq D\left(\frac{1}{\sqrt{\mu
T}}\sqrt{\frac{B^{2}}{4(k_{g}-1)^{2}}+\frac{a_{g}(h_{g}-1)B^{2}}{4(k_{g}-1)^{2}}+B^{2}}\sqrt{\frac{9+3\ln
s}{(k-1)^{2}}+1}+\frac{B^{2}}{M_{g,h-1}}\right).$

By substituting the parameters as in the statement and using the fact that
$\mu T\geq 1$ completes the proof. ∎

######  Remark 20.

Our fixed precision quantizer in Corollary 5.9 establishes that using only a
constant number of bits for gain-quantization, we get very close to the lower
bound in Theorem 4.4. For instance, given access to a large enough precision
$r$, if we set $r_{g}$ to be $16$ bits, we get

$\sup_{(f,O)\in\mathcal{O}}\mathcal{E}(f,O,\pi,Q)\leq
O\left(DB\left(\frac{d}{T\min\\{d,\frac{r-16}{\log\ln^{*}(d/3)}\\}}\right)^{\frac{1}{2}\cdot\frac{255}{257}}\right).$

Here, the ratio of $d/(\min\\{d,\frac{r-16}{\log\ln^{*}(d/3)}\\})$ is very
close to the optimal ratio of $d/(\min\\{d,r\\})$, and the exponent
$255/(2\cdot 257)$ is close to the optimal exponent $1/2$.

######  Remark 21.

We remark that A-RATQ satisfies Assumptions (1) and (2) in Section 1 but not
(3), and breaches the lower bound for uniform gain quantizers established in
Section 1.

#####  4 A variable-length quantizer

So far in this thesis, we have restricted our quantizers to be fixed-length.
We now present a variable-length quantizer for mean square bounded oracles
which improves over the convergence rate of Corollary 5.9. The quantizer we
present is a gain-shape quantizer that uses RATQ as the shape quantizer but
uses a variable-length version of the gain quantizer called AGUQ+, an update
on AGUQ presented in the previous section.

AGUQ+ differs from AGUQ in two crucial aspects: 1) The number of uniform
levels of the uniform quantizer for different dynamic ranges is different.
Denote by $k_{g,j}$ the number of uniform levels corresponding to the range
$[0,M_{g,j}]$. We choose $k_{g,j}$ to grow geometrically. 2) AGUQ+ employs
entropic compression further to reduce the expected code-length of the
quantized representation. Besides the differences, the quantization in AGUQ+
is the same as that of AGUQ.

Specifically, AGUQ+ is once again an adaptive quantizer like AGUQ with dynamic
ranges growing in a goemetric manner, precisely in the same way as in (17).
For a given gain $G\geq 0$, AGUQ+ first identifies the smallest $j$ such that
$G\leq M_{g,j}$ and then represents $G$ using the one-dimensional version of
CUQ with a dynamic range $[0,M_{g,j}]$ and $k_{g,j}$ uniform levels

$\displaystyle
B_{M_{g,j}}(\ell):=\ell\cdot\frac{M_{g,j}}{k_{g,j}-1},\quad\forall\,\ell\in\\{0,\ldots,k_{g,j}-1\\}.$

As in AGUQ, if $G>M_{g,h_{g}-1}$, the overflow $\emptyset$ symbol is used and
the decoder simply outputs $0$.

Note that since we are quantizing unbounded random variables, it is difficult
to avoid bias. Nevertheless, we will make the effect of the bias negligible.
Specifically, for the application of communication-constrained optimization of
convex functions, it will be desirable to have a bias of at the most
$1/\sqrt{T}$. To achieve this, we set

$\displaystyle a_{g}=2,\quad h_{g}=1+\frac{1}{2}\log T,\quad
k_{g,j}+1=2^{j+1}.$ (20)

We now describe the variable length coding procedure. The variable-length bit
string itself is a concatenation of two separate bit strings. The first string
represents the non-uniform level $j$ in $\\{0,\cdots,h_{g}-1\\}$ using the
first $h_{g}$ symbols of the Huffman code for geometric distribution with
parameter $1/2$. The second string uses a fixed-length code of $k_{g,j}$ bits.
We will show that the total number of bits used for both the strings would be
$O(1)$ in expectation.

######  Remark 22 (Entropic compression in $AGUQ^{+}$).

$AGUQ^{+}$ improves over vanilla $AGUQ$ by exploiting that the probability of
a larger dynamic range being chosen decays exponentially with the dynamic
range level $j$. For concreteness, since $\mathbb{E}\left[Y^{2}\right]\leq
B^{2},$ we have by Markov’s inequality $P(|Y|>M_{g,j-1})\leq
B^{2}/M^{2}_{g,j-1}=a_{g}^{-j}=2^{-j+1}.$ This probability bound allows us to
use a code similar to that of Huffman code for geometric distribution and only
have a constant code-length.

The following result characterizes the performance of one-dimensional
quantizer AGUQ+.

######  Lemma 5.10.

Let $Q_{{\tt a^{+}}}$ be the quantizer AGUQ+ described above with parameters
set as in (17) and (20). Then, for $Y$ such that
$\mathbb{E}\left[Y^{2}\right]\leq B^{2},$ $Q_{\tt a^{+}}(Y)$ can be
represented using at the most $O(1)$ bits of precision in expectation,

$\displaystyle\alpha_{2}^{\tt m}(Q_{\tt a^{+}};B,1)\leq O\left(1\right),\text{
and }$ $\displaystyle\beta_{2}^{\tt m}(Q_{{\tt a^{+}}};B,1)\leq\sup_{Y\geq
0\text{ a.s. }:\mathbb{E}\left[Y^{2}\right]\leq
B^{2}}\mathbb{E}\left[\bigg{|}\mathbb{E}\left[Q_{a}(Y)-Y|Y\right]\bigg{|}\right]\leq
O\left(\frac{B}{\sqrt{T}}\right).$

The proof is deferred to Section 5

######  Remark 23.

Thus employing a gain-shape quantizer where the gain is quantized by AGUQ+ and
the shape is quantized by the subsampled version of RATQ along with PSGD
improves over the convergence guarantees of Corollary 5.9, and essentially has
the same order of convergence guarantees as that in Corollary 4.5. That is,
this particular gain-shape quantizer along with PSGD achieves roughly the
convergence rate of $O\left(\frac{DB}{\sqrt{T}}\cdot\frac{d}{r}\right)$, which
is the same as that in lower-bound for communication constrained optimization
of convex and $\ell_{2}$ lipschitz functions, $\mathcal{O}_{{\tt c},2}^{m}$,
as stated in Theorem 4.4. From Remark 7, the lower bound in Theorem 4.4 holds
for variable length quantizers, too, provided the gradient processing is done
in a nonadaptive manner. Thus employing a gain-shape quantizer where the gain
is quantized by AGUQ+ and the shape is quantized by the subsampled version of
RATQ along with PSGD is optimal for communication-constrained optimization of
$\mathcal{O}_{{\tt c},2}^{m}$ when nonadaptive, variable-length quantizers are
allowed.

####  6 Main proofs

#####  1  Proof of Theorem 3.2

We proceed as in the standard proof of convergence (see, for instance, [15]):
Denoting by $\Gamma_{\mathcal{X}}(x)$ the projection of $x$ on the set
$\mathcal{X}$ (in the Euclidean norm), the error at time $t$ can be bounded as

$\displaystyle\|x_{t}-x^{*}\|_{2}^{2}$
$\displaystyle=\|\Gamma_{\mathcal{X}}\big{(}x_{t-1}-\eta
Q(\hat{g}(x_{t-1}))\big{)}-x^{*}\|_{2}^{2}$
$\displaystyle\leq\|\big{(}x_{t-1}-\eta
Q(\hat{g}(x_{t-1}))\big{)}-x^{*}\|_{2}^{2}$
$\displaystyle=\|x_{t-1}-x^{*}\|_{2}^{2}+\|\eta
Q(\hat{g}(x_{t-1}))\|_{2}^{2}-2\eta(x_{t-1}-x^{*})^{T}Q(\hat{g}(x_{t-1}))$
$\displaystyle=\|x_{t-1}-x^{*}\|_{2}^{2}+\|\eta
Q(\hat{g}(x_{t-1}))\|_{2}^{2}-2\eta(x_{t-1}-x^{*})^{T}\big{(}Q(\hat{g}(x_{t-1}))-\hat{g}(x_{t-1})\big{)}$
$\displaystyle\quad-2\eta(x_{t-1}-x^{*})^{T}\hat{g}(x_{t-1}),$

where the first inequality is a well known property of the projection operator
$\Gamma$ (see, for instance, Lemma 3.1, [15]). By rearranging the terms, we
have

$\displaystyle 2\eta(x_{t-1}-x^{*})^{T}\hat{g}(x_{t-1})$
$\displaystyle\leq\|x_{t-1}-x^{*}\|_{2}^{2}-\|x_{t}-x^{*}\|_{2}^{2}+\|\eta
Q(\hat{g}(x_{t-1}))\|_{2}^{2}$ (21) $\displaystyle\hskip
28.45274pt-2\eta(x_{t-1}-x^{*})^{T}\left(Q(\hat{g}(x_{t-1}))-\hat{g}(x_{t-1})\right).$
(22)

Also, since $\mathbb{E}\left[\hat{g}(x_{t-1})|x_{t-1}\right]$ is a subgradient
at $x_{t-1}$ for the convex function $f$, upon taking expectation over the
randomness in the subgradient estimates as well as the quantizer output we get

$\displaystyle\mathbb{E}\left[f(x_{t-1})-f(x^{*})\right]\leq\mathbb{E}\left[(x_{t-1}-x^{*})^{T}\mathbb{E}\left[\hat{g}(x_{t-1})|x_{t-1}\right]\right],$
(23)

which with the previous bound yields

$\displaystyle 2\eta\mathbb{E}\left[f(x_{t-1})-f(x^{*})\right]$
$\displaystyle\leq\mathbb{E}\left[\|x_{t-1}-x^{*}\|_{2}^{2}\right]-\mathbb{E}\left[\|x_{t}-x^{*}\|_{2}^{2}\right]+\eta^{2}\mathbb{E}\left[\|Q(\hat{g}(x_{t-1}))\|_{2}^{2}\right]$
$\displaystyle\hskip
28.45274pt-2\eta\mathbb{E}\left[(x_{t-1}-x^{*})^{T}\big{(}Q(\hat{g}(x_{t-1}))-\hat{g}(x_{t-1})\big{)}\right].$

Next, by the Cauchy-Schwarz inequality and the assumption in (1), the third
term on the right-side above can be bounded further to obtain

$\displaystyle 2\eta\mathbb{E}\left[f(x_{t-1})-f(x^{*})\right]$
$\displaystyle\leq\mathbb{E}\left[\|x_{t-1}-x^{*}\|_{2}^{2}\right]-\mathbb{E}\left[\|x_{t}-x^{*}\|_{2}^{2}\right]+\eta^{2}\mathbb{E}\left[\|Q(\hat{g}(x_{t-1}))\|_{2}^{2}\right]$
$\displaystyle\hskip 56.9055pt+2\eta\cdot
D\cdot\mathbb{E}\left[\|\mathbb{E}\left[Q(\hat{g}(x_{t-1}))-\hat{g}(x_{t-1})|x_{t-1}\right]\|_{2}\right].$

Finally, we note that, by the definition of $\alpha$ and $\beta$, for
$L_{2}$-bounded oracles we have

$\displaystyle\mathbb{E}\left[\|Q(\hat{g}(x_{t-1}))\|_{2}^{2}\right]$
$\displaystyle\leq\alpha_{2}^{\tt m}(Q)^{2},$
$\displaystyle\|\mathbb{E}\left[Q(\hat{g}(x_{t-1}))-\hat{g}(x_{t-1})|x_{t-1}\right]\|_{2}$
$\displaystyle\leq\beta_{2}^{\tt m}(Q),$

which gives

$\displaystyle 2\eta\mathbb{E}\left[f(x_{t-1})-f(x^{*})\right]$
$\displaystyle\leq\mathbb{E}\left[\|x_{t-1}-x^{*}\|_{2}^{2}\right]-\mathbb{E}\left[\|x_{t}-x^{*}\|_{2}^{2}\right]+\eta^{2}\alpha_{2}^{\tt
m}(Q)^{2}+2\eta D\beta_{2}^{\tt m}(Q).$

Therefore, by summing from $t=2$ to $T+1$, dividing by $T$, and using
assumption that the domain $\mathcal{X}$ has diameter at the most $D$, we have

$\displaystyle 2\eta\mathbb{E}\left[f(\bar{x}_{T})-f(x^{*})\right]$
$\displaystyle\leq\frac{D^{2}}{T}+\eta^{2}\alpha_{2}^{\tt m}(Q)^{2}+2\eta
D\beta_{2}^{\tt m}(Q).$

The first statement of Theorem 3.2 follows upon dividing by $\eta$ and setting
the value of $\eta$ as in the statement. The second statement holds in a
similar manner by replacing $\alpha$ and $\beta$ with $\alpha_{2}$ and
$\beta_{2}$, respectively. ∎

#####  2 Proof of Theorem 3.3

Note that since the gradient descent step remains the same, (21) still holds.
Except now, instead of (23), we have a stronger inequality

$\displaystyle\mathbb{E}\left[f(x_{t-1})-f(x^{*})\right]\leq\mathbb{E}\left[(x_{t-1}-x^{*})^{T}\mathbb{E}\left[\hat{g}(x_{t-1})|x_{t-1}\right]\right]-\frac{\gamma}{2}\|x_{t-1}-x^{*}\|_{2}^{2},$
(24)

Combining (21) and (24), and then using the definition of $\alpha$, $\beta$ as
in the previous proof, we get

$\displaystyle 2\eta_{t-1}\mathbb{E}\left[f(x_{t-1})-f(x^{*})\right]$
$\displaystyle\leq\mathbb{E}\left[\|x_{t-1}-x^{*}\|_{2}^{2}\right]-\mathbb{E}\left[\|x_{t}-x^{*}\|_{2}^{2}\right]+\eta^{2}_{t-1}\alpha_{2}(Q)^{2}+2\eta_{t-1}D\beta_{2}(Q)$
$\displaystyle\hskip 28.45274pt-\frac{\gamma}{2}\|x_{t-1}-x^{*}\|_{2}^{2}.$

Then multiplying by $(t-1)/2\eta_{t-1}$, we get

$\displaystyle(t-1)\mathbb{E}\left[f(x_{t-1})-f(x^{*})\right]$
$\displaystyle\leq\frac{(t-1)\eta_{t-1}}{2}\alpha_{2}(Q)^{2}+\left(\frac{t-1}{2\eta_{t-1}}-\frac{(t-1)\gamma}{2}\right)\mathbb{E}\left[\|x_{t-1}-x^{*}\|_{2}^{2}\right]$
$\displaystyle\hskip
28.45274pt-\frac{t-1}{2\eta_{t-1}}\mathbb{E}\left[\|x_{t}-x^{*}\|_{2}^{2}\right]+(t-1)D\beta_{2}(Q).$

Substituting for $\eta_{t-1}$ as in the theorem statement, summing the
resultant inequality from $t=1$ to $T$, and then applying Jensen’s inequality
completes the proof.

#####  3 Proof of Theorem 4.2

###### Step 1: Analysis of CUQ.

We first prove a result for CUQ (with a dynamic range of $[-M,M]$) which will
bound the expected value of

$\sum_{i\in[d]}\big{(}Q_{{\tt
u}}(Y)(i)-{Y(i)}\big{)}^{2}\mathbbm{1}_{\\{|{Y(i)|}\leq M\\}},$

namely the mean square error when there is no overflow. This will be useful in
the analysis of RATQ, too.

######  Lemma 6.1.

For an $\mathbb{R}^{d}$-valued random variable $Y$ and $Q_{{\tt u}}$ denoting
the quantizer CUQ with parameters $M$ (with dynamic range $[-M,M]$) and $k$,
let $Q_{{\tt u}}(Y)$ be the quantized value of $Y$. Then,

$\displaystyle\mathbb{E}\left[\sum_{i\in[d]}\big{(}Q_{{\tt
u}}(Y)(i)-{Y(i)}\big{)}^{2}\mathbbm{1}_{\\{{|Y(i)|}\leq M\\}}\mid
Y\right]\leq\frac{dM^{2}}{(k-1)^{2}}\left(\frac{1}{d}\sum_{j\in[d]}\mathbbm{1}_{\\{{|Y(j)|}\leq
M\\}}\right).$

The proof is relatively straightforward with the calculations similar to [88,
Theorem 2]; it is deferred to Section 1.

Also, the quantizer AGUQ in Section 2 uses the one-dimensional CUQ with
dynamic range $[0,M]$ as a subroutine. The uniform levels for this variant of
CUQ are given by

$B_{M,k}(\ell)=\ell\cdot\frac{M}{k-1},\forall\ell\in[k-1].$

We have the following lemma for this variant of CUQ.

######  Lemma 6.2.

For an $\mathbb{R}$-valued random variable $Y$ which is almost surely
nonnegative and the quantizer $Q_{\tt u}$ with dynamic range $[0,M]$ and
parameter $k$, let $Q_{{\tt u}}(Y)$ denote the quantized value of $Y$. Then,

$\displaystyle\mathbb{E}\left[\big{(}Q_{{\tt
u}}(Y)-{Y}\big{)}^{2}\mathbbm{1}_{\\{{|Y|}\leq M\\}}\mid
Y\right]\leq\frac{M^{2}}{4(k-1)^{2}}\left(\mathbbm{1}_{\\{{|Y|}\leq
M\\}}\right).$

The proof is very similar to the proof of Lemma 6.1 and is deferred to Section
1.

###### Step 2: Mean square error for adaptive quantizers.

The quantizers RATQ and A-RATQ use ATUQ as subroutine; in addition, A-RATQ
uses AGUQ for gain quantization. Thus, in order to analyze RATQ and A-RATQ, we
need to analyze ATUQ and AGUQ first.

In this step we provide a general bound on the mean square error of adaptive
quantizers. We capture the performances of ATUQ and AGUQ in two separate
results below.

######  Lemma 6.3.

For an $\mathbb{R}^{d}$-valued random variable $Y$ and $Q$ denoting the
quantizer ATUQ with dynamic-range parameters $M_{j}$s, we have

$\displaystyle\mathbb{E}\left[\sum_{i\in[d]}\big{(}Q(Y)(i)-{Y(i)}\big{)}^{2}\mathbbm{1}_{\\{{|Y(i)|}\leq
M_{h-1}\\}}\right]\leq\frac{d}{(k-1)^{2}}\left(m+m_{0}+\sum_{j=1}^{h-1}M_{j}^{2}P\left(\|Y\|_{\infty}>M_{j-1}\right)\right).$

###### Proof.

Consider the events $A_{j}$s corresponding to different levels used by the
adaptive quantizer of the norm, defined as follows:

$\displaystyle A_{0}$ $\displaystyle:=\\{\|Y\|_{\infty}\leq m\\},$
$\displaystyle A_{j}$ $\displaystyle:=\\{M_{j-1}<\|Y\|_{\infty}\leq
M_{j}\\},\quad\forall j\in[h-2],$ $\displaystyle A_{h-1}$
$\displaystyle:=\\{M_{h-2}<\|Y\|_{\infty}\\}.$

By construction, $\sum_{j=0}^{h-1}\mathbbm{1}_{A_{j}}=1\text{ a.s.}$.
Therefore, we have

$\displaystyle\mathbb{E}\left[\sum_{i\in[d]}\big{(}Q(Y)(i)-{Y(i)}\big{)}^{2}\mathbbm{1}_{\\{{|Y(i)|}\leq
M_{h-1}\\}}\right]$
$\displaystyle=\mathbb{E}\left[\|Q(Y)-{Y}\|_{2}^{2}\mathbbm{1}_{A_{0}}\right]+\sum_{j=1}^{h-2}\mathbb{E}\left[\|Q(Y)-{Y}\|_{2}^{2}\mathbbm{1}_{A_{j}}\right]$
$\displaystyle\hskip 28.45274pt+\mathbb{E}\left[\sum_{i\in[d]}\big{(}Q_{{\tt
u}}(Y)(i)-{Y(i)}\big{)}^{2}\mathbbm{1}_{\\{{|Y(i)|}\leq
M_{h-1}\\}}\mathbbm{1}_{A_{h-1}}\right].$

Note that $\mathbbm{1}_{A_{0}}$ implies that we are using a $k$-level uniform
quantization with a dynamic range of $[-m,m]$. Therefore, this term can be
bounded by Lemma 6.1 as follows:

$\displaystyle\mathbb{E}\left[\|Q(Y)-{Y}\|_{2}^{2}\mathbbm{1}_{A_{0}}\right]\
\leq\frac{dm}{(k-1)^{2}}.$

Under the event $A_{j}$ with $j\in[h-1]$, we use a $k$-level uniform
quantization with a dynamic range of $[-M_{j},M_{j}].$ Therefore, by Lemma
6.1, we have

$\displaystyle\mathbb{E}\left[\|Q(Y)-{Y}\|_{2}^{2}\mathbbm{1}_{A_{j}}\right]\leq$
$\displaystyle\frac{dM_{j}^{2}}{(k-1)^{2}}\mathbb{E}\left[\mathbbm{1}_{A_{j}}\right]$
$\displaystyle\leq$
$\displaystyle\frac{dM_{j}^{2}}{(k-1)^{2}}P\left(\|{Y}\|_{\infty}>M_{j-1}\right).$

∎

Note that the proof above does note use specific form of $M_{j}$’s and
therefore applies as it is for the one-dimensional AGUQ gain quantizer used in
A-RATQ; the only change is the fact that instead of using Lemma 6.1 for
uniform quantization we use Lemma 6.2. This leads to the following lemma,
which will be useful later in the analysis of A-RATQ.

######  Lemma 6.4.

For an $\mathbb{R}$-valued random variable $Y$ which is almost surely
nonnegative and $Q$ denoting the quantizer AGUQ with dynamic-range parameters
$M_{g,j}$s, we have

$\displaystyle\mathbb{E}\left[(Q(Y)-{Y})^{2}\mathbbm{1}_{\\{|Y|\leq
M_{g,h-1}\\}}\right]\leq\frac{1}{4(k-1)^{2}}\left(B^{2}+\sum_{j=1}^{h-1}M_{g,j}^{2}P\left(|Y|>M_{g,j-1}\right)\right).$

The proof is similar to that of Lemma 6.3 and is omitted.

###### Step 3: Mean square error of ATUQ for a subgaussian input vector.

In our analysis, we need to evaluate the performance of ATUQ for subgaussian
input vectors.

######  Definition 6.5 ($cf.$ [13]).

A centered random variable $X$ is said to be subgaussian with variance factor
$v$ if for all $\lambda$ in $\mathbb{R}$, we have

$\ln\mathbb{E}\left[e^{\lambda X}\right]\leq\frac{\lambda^{2}v}{2}.$

The following well-known fact ($cf.$ [13, Chapter 2]) will be used throughout.

######  Lemma 6.6.

For a centered subgaussian random variable $X$ with variance factor $v$ the

$\displaystyle P(|X|>x)\leq 2e^{-x^{2}/2v},\quad\forall\,x>0,$
$\displaystyle\mathbb{E}\left[X^{2}\right]\leq
4v,\quad\mathbb{E}\left[X^{4}\right]\leq 32v^{2}.$

Next, consider the quantizer $Q_{{\tt at},I}$ which is similar to RATQ but
skips the rotation step. Specifically, $Q_{{\tt at},I}$ is obtained by
replacing the random matrix $R$ in the encoder and decoder of RATQ (given in
Algorithms 2 and 3, respectively) by the identity matrix $I$. Symbolically,
the quantizer $Q_{{\tt at},I}$ can be described as follows for the
$d$-dimensional input vector $Y$

$Q_{{\tt at},I}(Y)=[Q_{\tt at}(Y_{1})^{T},\cdots,Q_{\tt at}(Y_{\left\lceil
d/s\right\rceil})^{T}],$ (25)

where $Q_{\tt at}$ is the quantizer ATUQ and $Y_{i}$ is the $i^{th}$ subvector
of $Y$. Recall that the $i^{th}$ subvector $Y_{i}$ comprises the coordinates
$\\{(i-1)s+1,\cdots,\min\\{is,d\\}\\}$, for all $i\in[d/s].$ Also, recall that
the dimension of all the sub vectors except the last one is $s$, with the last
one having dimension $d-s\lfloor d/s\rfloor$.

Notice that like RATQ, $Q_{at,I}$ has parameters $k$, $h$, $s$, $m$, and
$m_{0}$ which need to be set. We set the parameters $m$ and $m_{0}$ to be $3v$
and $2v\ln s$, respectively, and prove a general lemma in terms of the other
parameters of $Q_{at,I}$ for a subgaussian input vector.

######  Lemma 6.7.

Consider $Y=[Y(1),\ldots,Y(d))]^{T},$ where for all $i$ in $[d]$, $Y(i)$ is a
centered subgaussian random variable with variance factor $v$. Let $Q$ denote
the quantizer $Q_{{\tt at},I}$ with parameters $m$ and $m_{0}$ set to $3v$ and
$2v\ln s$, respectively. Then, for every $s,k,h\in\mathbb{N}$, we have

$\frac{1}{d}\cdot\mathbb{E}\left[\sum_{i\in[d]}(Y(i)-Q(Y)(i))^{2}\mathbbm{1}_{\\{|Y(i)|\leq
M_{h-1}}\\}\right]\leq v\cdot\frac{9+3\ln s}{(k-1)^{2}}.$

###### Proof.

Since

$\displaystyle\mathbb{E}\left[\sum_{i\in[d]}(Y(i)-Q(Y)(i))^{2}\mathbbm{1}_{\\{|Y(i)|\leq
M_{h-1}}\\}\right]$
$\displaystyle=\sum_{i=1}^{\left\lceil\frac{d}{s}\right\rceil}\sum_{j=(i-1)s+1}^{\min\\{is,d\\}}\mathbb{E}\left[\left(Q_{{\tt
at}}(Y)(j)-Y(j)\right)^{2}\mathbbm{1}_{\\{|Y(j)|\leq M_{h-1}\\}}\right],$

by using Lemma 6.3 for each of the $\left\lceil d/s\right\rceil$ subvectors,
we get

$\displaystyle\mathbb{E}\left[\sum_{i\in[d]}(Y(i)-Q(Y)(i))^{2}\mathbbm{1}_{\\{|Y(i)|\leq
M_{h-1}}\\}\right]$ $\displaystyle\leq\frac{s}{(k-1)^{2}}\sum_{i\in
1}^{\lfloor\frac{d}{s}\rfloor}\left(m+m_{0}+\sum_{j\in[h-1]}M_{j}^{2}P\left(\|Y_{i,s}\|_{\infty}>M_{j-1}\right)\right)$
$\displaystyle\hskip
8.5359pt+\frac{(d-s\lfloor\frac{d}{s}\rfloor)}{(k-1)^{2}}\left(m+m_{0}+\sum_{j\in[h-1]}M_{j}^{2}P\left(\|Y_{\left\lceil
d/s\right\rceil,s}\|_{\infty}>M_{j-1}\right)\right).$

For all $i\in\lfloor d/s\rfloor$, it follows from the union bound that

$\displaystyle P\left(\|Y_{1,s}\|_{\infty}>M_{j-1}\right)\leq
2se^{\frac{-M_{j-1}^{2}}{2v}}.$

Also, since $d-s\lfloor d/s\rfloor\leq s$, we have

$\displaystyle P\left(\|Y_{\left\lceil
d/s\right\rceil,s}\|_{\infty}>M_{j-1}\right)\leq
2se^{\frac{-M_{j-1}^{2}}{2v}}.$

Using these tail bounds in the previous inequality, we get

$\displaystyle\mathbb{E}\left[\sum_{i\in[d]}(Y(i)-Q(Y)(i))^{2}\mathbbm{1}_{\\{|Y(i)|\leq
M_{h-1}}\\}\right]\leq\frac{d}{(k-1)^{2}}\left(m+m_{0}+2s\sum_{j\in[h-1]}M_{j}^{2}e^{\frac{-M_{j-1}^{2}}{2v}}\right).$

Setting $m=3v$ and $m_{0}=2v$, the summation on the right-side is bounded
further as

$\displaystyle 2s\left(\frac{3v}{s}\sum_{j=1}^{h-1}(e^{*j})\cdot
e^{-1.5{e^{*(j-1)}}}\right)+2s\left(\frac{2v}{s}\sum_{j=1}^{h-1}e^{-1.5{e^{*(j-1)}}}\right)$
$\displaystyle=6v\sum_{j=1}^{h-1}e^{-0.5{e^{*(j-1)}}}+4v\ln
s\sum_{j=1}^{h-1}e^{-1.5{e^{*(j-1)}}}$ $\displaystyle\leq
6v\sum_{j=1}^{\infty}e^{-0.5{e^{*(j-1)}}}+4v\ln
s\sum_{j=1}^{h-1}e^{-1.5{e^{*(j-1)}}}$ $\displaystyle\leq 6v+v\ln s,$

where we use a bound of $1$ for $\sum_{j=1}^{\infty}e^{-0.5{e^{*(j-1)}}}$,
whose validity can be seen as follows111111In fact, these bounds motivate the
use of tetration as our choice for $M_{j}$s.

$\displaystyle\sum_{j=1}^{\infty}e^{-0.5{e^{*(j-1)}}}$
$\displaystyle={e^{-0.5}}+{e^{-0.5e}}+{e^{-0.5e^{e}}}+\sum_{j=3}^{\infty}e^{-0.5{e^{*(j)}}}$
$\displaystyle\leq{e^{-0.5}}+{e^{-0.5e}}+{e^{-0.5e^{e}}}+\sum_{j=3}^{\infty}e^{-0.5{je^{e}}}$
$\displaystyle\leq{e^{-0.5}}+{e^{-0.5e}}+{e^{-0.5e^{e}}}+\frac{1}{e^{e^{e}}-1}$
$\displaystyle\leq 1,$

and $1/4$ for $\sum_{j=1}^{h-1}e^{-1.5{e^{*(j-1)}}}$, whose validity can be
seen as follows

$\displaystyle\sum_{j=1}^{\infty}e^{-1.5{e^{*(j-1)}}}$
$\displaystyle={e^{-1.5}}+{e^{-1.5e}}+{e^{-1.5e^{e}}}+\sum_{j=3}^{\infty}e^{-1.5{e^{*(j)}}}$
$\displaystyle\leq{e^{-1.5}}+{e^{-1.5e}}+{e^{-1.5e^{e}}}+\sum_{j=3}^{\infty}e^{-1.5{je^{e}}}$
$\displaystyle\leq{e^{-1.5}}+{e^{-1.5e}}+{e^{-1.5e^{e}}}+\frac{1}{e^{3e^{e}}-1/e^{1.5e^{e}}}$
$\displaystyle\leq 0.2401.$

Therefore, we obtain

$\frac{1}{d}\cdot\mathbb{E}\left[\sum_{i\in[d]}(Y(i)-Q(Y)(i))^{2}\mathbbm{1}_{|Y(i)|\leq
M_{h-1}}\right]\leq v\cdot\frac{9+3\ln s}{(k-1)^{2}}.$

∎

We remark that calculations present in this lemma are at the heart of the
analysis of RATQ. Also, this lemma will be useful for other applications
discussed in Chapters 4 and 5.

###### Step 4: Completing the proof.

Recall that the random matrix $R$ defined in (6) is used at the encoder of
RATQ to randomly rotate the input vector. We observe that the rotated vector
has subgaussian entries.

######  Lemma 6.8.

For an $\mathbb{R}^{d}$-valued random variable $Y$ such that
$\|Y\|_{2}^{2}\leq B^{2}\text{ a.s.}$, all coordinates of the rotated vector
$RY$ are centered subgaussian random variables with a variance factor of
${B^{2}}/{d}$, whereby

$P(|{RY}(j)|\geq M)\leq 2e^{-dM^{2}/2B^{2}},\quad\forall\,j\in[d],$

where $RY(j)$ is the $j^{th}$ coordinate of the rotated vector.

The proof uses similar calculations as [7] and [88]; it is deferred to Section
2.

Intuitively, the Lemma 6.8 highlights the fact that overall energy
$\|Y\|_{2}^{2}$ in the input vector $Y$ is divided equally among all the
coordinates after random rotation.

###### The worst-case second moment of RATQ.

Note that by the description of RATQ which will be denoted by $Q_{{\tt
at},R}(RY),$ we have that

$Q_{{\tt at},R}(Y)=R^{-1}Q_{{\tt at},I}(RY),$

where $Q_{{\tt at},I}$ is as defined in (25). Thus,

$\displaystyle Q_{{\tt at},I}(RY)=[Q_{{\tt at}}(RY_{1,s})^{T},\cdots,Q_{{\tt
at}}(RY_{\left\lceil d/s\right\rceil,s})^{T}]^{T},$ (26)

where the subvector $RY_{i,s}$ is given by

$\displaystyle RY_{i,s}=[RY((i-1)s+1),\cdots,RY(\min\\{is,d\\})]^{T}.$

To compute $\alpha(Q_{{\tt at},R}(Y))$, we will first compute the second
moment for the output of RATQ. Specifically, using the fact $R$ is a unitary
transform, we obtain

$\displaystyle\mathbb{E}\left[\|Q_{{\tt at},R}(Y)\|_{2}^{2}\right]$
$\displaystyle=\mathbb{E}\left[\|R^{-1}Q_{{\tt at},I}(RY)\|_{2}^{2}\right]$
$\displaystyle=\mathbb{E}\left[\|Q_{{\tt at},I}(RY)\|_{2}^{2}\right]$
$\displaystyle=\sum_{j\in[d]}\mathbb{E}\left[(Q_{{\tt
at},I}(RY)(j))^{2}\right]$
$\displaystyle=\sum_{i=1}^{\left\lceil\frac{d}{s}\right\rceil}\sum_{j=(i-1)s+1}^{\min\\{is,d\\}}\mathbb{E}\left[(Q_{{\tt
at},I}(RY)(j))^{2}\right].$

We now observe that for our choice of $m$ and $h$ for RATQ given by (8), we
have

$M_{h-1}^{2}\geq m(e^{*{\log_{e}^{*}(d/3)}})=(3B^{2}/d).(d/3)=B^{2}.$

Using this observation and noting that $R$ is a unitary matrix, we have that

$\mathbbm{1}_{\\{\|RY\|_{2}\leq M_{h-1}\\}}=1\text{ a.s.}.$

Also, noting that $|RY(j)|\leq\|RY\|_{2}=\|Y\|_{2}=B$ a.s., for all $j\in[d]$,
we get

$\mathbbm{1}_{\\{|RY(j)|\leq M_{h-1}\\}}=1\text{ a.s.},\forall j\in[d].$ (27)

Proceeding with these observations, we get

$\displaystyle\mathbb{E}\left[\|Q_{{\tt at},R}(Y)\|_{2}^{2}\right]$
$\displaystyle\leq\sum_{i=1}^{\left\lceil\frac{d}{s}\right\rceil}\sum_{j=(i-1)s+1}^{\min\\{is,d\\}}\mathbb{E}\left[(Q_{{\tt
at},I}(RY)(j))^{2}\mathbbm{1}_{\\{|RY(j)|\leq M_{h-1}\\}}\right]$
$\displaystyle=\sum_{i=1}^{\left\lceil\frac{d}{s}\right\rceil}\sum_{j=(i-1)s+1}^{\min\\{is,d\\}}\mathbb{E}\left[(Q_{{\tt
at},I}(RY)(j)-RY(j)+RY(j))^{2}\mathbbm{1}_{\\{|RY(j)|\leq M_{h-1}\\}}\right]$
$\displaystyle\leq\sum_{i=1}^{\left\lceil\frac{d}{s}\right\rceil}\sum_{j=(i-1)s+1}^{\min\\{is,d\\}}\mathbb{E}\left[\left((Q_{{\tt
at},I}(RY)(j)-RY(j))^{2}+RY(j)^{2}\right)\mathbbm{1}_{\\{|RY(j)|\leq
M_{h-1}\\}}\right],$

where the previous inequality uses the fact that, under the event
$\\{|RY(j)|\leq M_{h-1}\\}$, $Q_{{\tt at},I}(RY)(j)$ is an unbiased estimate
of $RY(j)$. Namely,

$\mathbb{E}\left[Q_{{\tt at},I}(RY)(j)\mathbbm{1}_{\\{|RY(j)|\leq
M_{h-1}\\}}\mid R,Y\right]=\mathbb{E}\left[RY(j)\mathbbm{1}_{\\{|RY(j)|\leq
M_{h-1}\\}}\mid R,Y\right].$

Therefore, noting that $R$ is a unitary matrix, we have

$\displaystyle\mathbb{E}\left[\|Q_{{\tt
at},R}(Y)\|_{2}^{2}\right]\leq\mathbb{E}\left[\sum_{j\in[d]}(RY(i)-Q_{{\tt
at},I}(RY)(j))^{2}\mathbbm{1}_{\\{|RY(j)|\leq
M_{h-1}\\}}\right]+\mathbb{E}\left[\|Y\|_{2}^{2}\right].$

To bound the first term on the right-side we have the following lemma.

######  Lemma 6.9.

For an $\mathbb{R}^{d}$-valued random variable $Y$ such that
$\|Y\|_{2}^{2}\leq B^{2}$ a.s.. Then, for $m$ and $m_{0}$ set to be $3B^{2}/d$
and $(2B^{2}/d)\ln s$, respectively, we have that

$\displaystyle\mathbb{E}\left[\sum_{j\in[d]}(RY(i)-Q_{{\tt
at},I}(RY)(j))^{2}\mathbbm{1}_{\\{|RY(j)|\leq M_{h-1}\\}}\right]\leq
B^{2}\cdot\frac{9+3\ln s}{(k-1)^{2}}.$

###### Proof.

By Lemma 6.8 we have that all coordinates $RY(j)$ are centered subgaussian
random variable with variance factor $B^{2}/d$. Thus, the parameters $m$ and
$m_{0}$ of RATQ set as in (8), and equal $3v$ and $2v\ln s$, respectively,
where $v$ is the variance factor of each subgaussian coordinate. The result
follows by invoking Lemma 6.7. ∎

Therefore, for any $Y$ such that $\|Y\|_{2}^{2}\leq B^{2}$, we have

$\displaystyle\mathbb{E}\left[\|Q_{{\tt at},R}(Y)\|_{2}^{2}\right]\leq
B^{2}\cdot\frac{9+3\ln s}{(k-1)^{2}}+B^{2},$

whereby

$\alpha_{2}(Q_{{\tt at},R})\leq B\sqrt{\frac{9+3\ln s}{(k-1)^{2}}+1}.$

###### The worst-case bias of RATQ.

By (27) we have that the input always remains in the dynamic-range of the
quantizer, resulting in unbiased quantized values. In other words,
$\beta_{2}(Q_{{\tt at,R}})=0$.

#####  4 Proof of Lemma 5.5

We first note AGUQ is used to quantize a scalar $Y$. It follows from the
description of the quantizer that

$\mathbbm{1}_{\\{|{Y}|\leq M_{g,h_{g}-1}\\}}\mathbb{E}\left[Q_{\tt
a}(Y)|Y\right]=\mathbbm{1}_{\\{|{Y}|\leq M_{g,h_{g}-1}\\}}Y,$ (28)

and that121212Once again, this follows from our convention that the outflow
symbol is evaluated to $0$.

$\mathbbm{1}_{\\{|{Y}|>M_{g,h_{g}-1}\\}}Q_{\tt a}(Y)=0.$ (29)

###### The worst-case second moment of AGUQ.

Towards evaluating $\alpha(Q_{{\tt a}})$ for AGUQ, for any $Y\in\mathbb{R}$ we
have

$\displaystyle\mathbb{E}\left[Q_{\tt a}(Y)^{2}\right]$
$\displaystyle=\mathbb{E}\left[Q_{\tt a}(Y)^{2}\mathbbm{1}_{\\{|Y|\leq
M_{g,h_{g}-1}\\}}\right]+\mathbb{E}\left[Q_{\tt
a}(Y)^{2}\mathbbm{1}_{\\{|Y|>M_{g,h-1}\\}}\right]$
$\displaystyle=\mathbb{E}\left[(Q_{\tt a}(Y)-Y+Y)^{2}\mathbbm{1}_{\\{|Y|\leq
M_{g,h_{g}-1}\\}}\right]+\mathbb{E}\left[Q_{\tt
a}(Y)^{2}\mathbbm{1}_{\\{|Y|>M_{g,h_{g}-1}\\}}\right]$
$\displaystyle=\mathbb{E}\left[(Q_{\tt a}(Y)-Y)^{2}\mathbbm{1}_{\\{|Y|\leq
M_{g,h_{g}-1}\\}}\right]+\mathbb{E}\left[Y^{2}\mathbbm{1}_{\\{|Y|\leq
M_{g,h_{g}-1}\\}}\right],$

where the last identity uses (29), and the fact that $\mathbb{E}\left[(Q_{\tt
a}(Y)-Y)Y\mathbbm{1}_{\\{|Y|\leq M_{g,h-1}\\}}|Y\right]=0,$ which follows from
(28). From Lemma 6.4 it follows that

$\displaystyle\mathbb{E}\left[(Q_{{\tt a}}(Y)-Y)^{2}\mathbbm{1}_{\\{|Y|\leq
M_{g,h-1}\\}}\right]\leq\frac{1}{4(k_{g}-1)^{2}}\left(B^{2}+\sum_{j=1}^{h-1}M_{j}^{2}P\left(|Y|>M_{g,j-1}\right)\right).$

By Markov’s inequality we get that for any random variable $Y$ with
$\mathbb{E}\left[Y^{2}\right]\leq B^{2}$, we have $P(|Y|>M_{g,j-1})\leq
B^{2}/M^{2}_{g,j-1},$ which further leads to

$\displaystyle\mathbb{E}\left[(Q_{{\tt
a}}(Y)-Y)_{2}^{2}\mathbbm{1}_{\\{|Y|\leq M_{g,h-1}\\}}\right]$
$\displaystyle\leq\frac{B^{2}}{4(k_{g}-1)^{2}}+\sum_{j=1}^{h_{g}-1}\frac{M_{g,j}^{2}}{4(k_{g}-1)^{2}}\frac{B^{2}}{M_{g,j-1}^{2}}$
$\displaystyle=\frac{B^{2}}{4(k_{g}-1)^{2}}+\frac{a_{g}(h_{g}-1)B^{2}}{4(k_{g}-1)^{2}}.$

Therefore, we have

$\displaystyle\mathbb{E}\left[Q_{\tt
a}(Y)^{2}\right]\leq\frac{B^{2}}{4(k_{g}-1)^{2}}+\frac{a_{g}(h_{g}-1)B^{2}}{4(k_{g}-1)^{2}}+\mathbb{E}\left[Y^{2}\mathbbm{1}_{\\{|Y|\leq
M_{g,h-1}\\}}\right].$

The result follows upon taking the supremum of the left-side over all random
variables $Y$ with $\mathbb{E}\left[Y^{2}\right]\leq B^{2}$.

###### The worst-case bias of AGUQ.

Towards evaluating $\beta(Q_{\tt a})$, we note first using Jensen’s inequality
that

$\displaystyle\big{|}\mathbb{E}\left[Q_{\tt a}(Y)-Y\right]\big{|}$
$\displaystyle\leq\mathbb{E}\left[\big{|}\mathbb{E}\left[Q_{\tt
a}(Y)-Y|Y\right]\big{|}\right].$

Then, for $Y$ with $\mathbb{E}\left[Y^{2}\right]\leq B^{2}$, using (28) and
Markov’s inequality, we get

$\displaystyle\mathbb{E}\left[|\mathbb{E}\left[Q_{\tt
a}(Y)-Y|Y\right]|\right]$
$\displaystyle=\mathbb{E}\left[|Y|\mathbbm{1}_{\\{|Y|\geq
M_{g,h-1}\\}}\right]$
$\displaystyle\leq\sqrt{\mathbb{E}\left[Y^{2}\right]P(|Y|\geq M_{g,h-1})}$
$\displaystyle\leq\frac{B^{2}}{M_{g,h-1}}.$ (30)

Therefore, for any $Y$ with $\mathbb{E}\left[Y^{2}\right]\leq B^{2}$, we have

$\displaystyle\big{|}\mathbb{E}\left[Q_{\tt
a}(Y)-Y\right]\big{|}\leq\sup_{Y\geq
0\text{a.s.}:\mathbb{E}\left[Y^{2}\right]\leq
B^{2}}\mathbb{E}\left[\big{|}\mathbb{E}\left[Q_{\tt
a}(Y)-Y|Y\right]\big{|}\right]\leq\frac{B^{2}}{M_{g,h-1}}.$

The result follows upon taking the supremum of left-side over all random
variables $Y$ with $\mathbb{E}\left[Y^{2}\right]\leq B^{2}$. ∎

#####  5 Proof of Lemma 5.10

######  $O(1)$ expected precision.

Recall that the variable-length bit string is a concatenation of two bit
strings: The first bit string represents the dynamic range $M_{g,j}$,
$j\in\\{0,\ldots h-1\\}$; the second-bit string represents the uniform level
within that dynamic range.

The first string uses the first $h$ symbols of the Huffman codes corresponding
to the geometric distribution with parameter $1/2.$ Its code length can be
bounded as follows. By Markov’s inequality, we have $P(|Y|>M_{g,j-1})\leq
B^{2}/M^{2}_{g,j-1}=a_{g}^{-j}=2^{-j+1}.$ For a symbol
$j\in\\{0,\cdots,h-1\\}$ representing the chosen dynamic range, let $\ell(j)$
denote the length of the codeword of that symbol. Therefore, the expected
codelength $\mathbb{E}\left[L\right]$ can be upper bounded as follows.

$\displaystyle\mathbb{E}\left[L\right]$
$\displaystyle\leq\sum_{j=0}^{h-1}P(|Y|>M_{g,j-1})\ell(j)$ $\displaystyle\leq
2\sum_{j=0}^{h-1}2^{-j}\ell(j).$

Since we will assign code-lengths $\ell(j)$ as that assigned to the first $h$
symbols of the Huffman code corresponding to the geometric distribtution with
parameter $1/2$, we have the following.

$\displaystyle\mathbb{E}\left[L\right]$ $\displaystyle\leq
2\sum_{j=0}^{h-1}2^{-j}\ell(j)$
$\displaystyle=4\sum_{j=0}^{h-1}2^{-j-1}\ell(j)$ $\displaystyle\leq
4(H(Z)+1),$

where $Z$ is the geometric distribution with parameter $1/2$. Above, the final
inequality can be seen by the fact that expected code-length for Huffman codes
for a particular pmf is upper bounded by one plus entropy of that pmf. This
bounds the code-length of the first bit string by a constant.

Coming to the bounding the code-length of the second bit string, the expected
code length of the second string is upper bounded by

$\displaystyle\sum_{j=0}^{h-1}P(|Y|>M_{g,j-1})\log(k_{g,j}+1)\leq
2\sum_{j=0}^{h-1}2^{-j}(j+1)\leq 12.$

###### Worst-case second moment of AGUQ+.

The only change from the worst-case second moment upper bound calculations in
the proof of Lemma 5.5 is that the number of uniform levels for different
dynamic ranges is different. The rest of proof remains precisely the same, and
is skipped.

###### Bias of AGUQ+.

The proof is identical to one in Lemma 5.5, and is skipped. ∎

#####  6 Proof of Theorems 5.3 and 5.4

Before we proceed with our lower bounds, we will set up some notation. We
consider quantizers of the form

$Q(Y)=Q_{g}(\|Y\|_{2})Q_{s}(Y/\|Y\|_{2}).$

Let $W(\cdot|y)$, $W_{g}(\cdot|y)$, and $W_{s}(\cdot|y)$, respectively, denote
the distribution of the output of quantizers $Q(y)$, $Q_{g}(y),$ and
$Q_{s}(y)$. We prove a general lower bound for a quantizer satisfying
Structural Assumptions 1-3 in Section 1 in terms of the precision $r$;
Theorems 5.3 and 5.4 are obtained as corollaries of this general lower bound.

######  Theorem 6.10.

Suppose that $\mathcal{X}$ contains the set
$\\{x\in\mathbb{R}^{d}:\|x\|_{2}\leq D/2\\}$. Consider a gain-shape quantizer
$Q$ of precision $r$ satisfying the Assumptions 1-3 in Section 1. Then, there
exists an oracle $(f,O)\in\mathcal{O}$ such that for any optimization protocol
$\pi$ using $T$ iterations, we have

$\mathcal{E}(f,O,\pi,Q)\geq\frac{DB}{2\sqrt{2}}\min\bigg{\\{}\frac{1}{2^{r}},\frac{1}{4\cdot
2^{r/3}T^{1/3}},\frac{1}{2(2T)^{1/3}}\bigg{\\}}.$

###### Proof.

Consider the function $f_{\alpha}:\mathbb{R}^{d}\to\mathbb{R}$,
$\alpha\in\\{-1,1\\}$ given by

$f_{\alpha}(x):=\delta\frac{B}{\sqrt{2}}|x(1)-\alpha
D/2|,\quad\alpha\in\\{-1,1\\}.$

Note that the functions $f_{1}$ and $f_{-1}$ are convex and depend only on the
first coordinate of $x$. Further, for $x\in\mathcal{X}$, the subgradient of
$f_{\alpha}$ is $-\delta\alpha Be_{1}/\sqrt{2}$, since $sign(x(1)-\alpha
D/2)=-sign(\alpha)$, where $e_{1}$ is the vector $[1,0,0,\dots,0]^{T}$. We
consider oracles $O_{\alpha}$, $\alpha\in\\{-1,1\\}$, that produce noisy
subgradient updates with distribution

$\displaystyle
P_{\alpha}\left(\frac{B}{\sqrt{2}}e_{1}\right)=\frac{1-\delta^{2}}{2},\quad
P_{\alpha}\left(\frac{-B}{\sqrt{2}}e_{1}\right)=\frac{1-\delta^{2}}{2},\quad
P_{\alpha}\big{(}-\frac{\alpha B}{\sqrt{2}\delta}e_{1}\big{)}=\delta^{2}.$

It is easy to check that the oracle outputs satisfy (5) and (3) described in
Section 1. That is, the output of $O_{\alpha}$ is an unbiased estimate of the
subgradient of $f_{\alpha}$, and the expected Euclidean norm square of the
oracle output is bounded by $B^{2}$.

We now take recourse to the standard reduction of optimization to hypothesis
testing: To estimate the optimal value of $f_{1}$ and $f_{-1}$ to an accuracy
$\delta$, the optimization protocol must determine if the oracle outputs are
generated by $P_{1}$ or $P_{-1}$. However in order to distinguish between
$P_{1}$ or $P_{-1}$, the optimization protocol only has access to the
quantized oracle outputs. Specifically, the protocol sees the samples from
$Q(Y)$ at every time step, where $Y$ has distribution either $P_{1}$ or
$P_{-1}$.

Denoting by $P_{\alpha}W$ the distribution of the output $Q(Y)$ when the input
$Y$ is generated from $P_{\alpha}$, we have from the standard reduction (see,
for instance, [23, Theorem 5.2.4]) that

$\max_{\alpha\in\\{-1,1\\}}\mathcal{E}(f,O,\pi,Q)\geq\frac{DB}{2\sqrt{2}}\delta\bigg{(}1-\sqrt{\frac{T}{2}\chi^{2}(P_{1}W,P_{-1}W}\bigg{)},$

where $\displaystyle{\chi^{2}(P,Q)=\sum_{x}(P(x)-Q(x))^{2}/Q(x)}$ denotes the
chi-squared divergence between $P$ and $Q$.

Note that Assumption 2 on the structure of the quantizer implies that when
$M<B/{\delta\sqrt{2}}$, the distributions $P_{1}W$ and $P_{-1}W$ are the same.
It follows that for every $\delta<\min\\{\sqrt{B^{2}/2M^{2}},1\\}$, the left-
side of the previous inequality exceeds $(DB/2\sqrt{2})\delta$, whereby

$\displaystyle\max_{\alpha\in\\{-1,1\\}}\mathcal{E}(f,O,\pi,Q)\geq\frac{DB}{2\sqrt{2}}\min\bigg{\\{}\frac{B}{\sqrt{2}M},1\bigg{\\}}.$
(31)

Next, we consider the following modification of the previous construction in
the case when ${B}/\sqrt{2}<m$:

$\displaystyle
P_{\alpha}\left(\frac{B}{\sqrt{2}}e_{1}\right)=\frac{1-\delta^{1+y}}{2},\quad
P_{\alpha}\left(\frac{-B}{\sqrt{2}}e_{1}\right)=\frac{1-\delta^{1+y}}{2},\quad
P_{\alpha}\big{(}-\frac{\alpha
B}{\sqrt{2}\delta^{y}}e_{1}\big{)}=\delta^{1+y}.$

for $y\in[0,1]$. Once again, the oracle outputs satisfy (5) and (3) described
in Section 1. In this case, the vector $Y\sim P_{\alpha}$ has entries with
$\ell_{2}$ norm at the most $B/(\sqrt{2}\delta^{y})$. We set $y$ such that
this value is less than $m$ and $\chi^{2}(P_{1}W,P_{-1}W)$ is minimized. Note
that if $B/(\delta^{y}\sqrt{2d})<m$, then ${\tt
supp}(Q_{g}(\|a\|))\subseteq\\{0,m\\}$ for all the $a$’s in the support of
$P_{1}$ or $P_{-1}$.

For all $z\neq 0$, $z\in{\tt supp}(Q(a))$, when $a$ is in the support of
$P_{1}$ or $P_{-1}$, we have

$\displaystyle W\big{(}z\mid
a\big{)}=W_{g}\big{(}m\mid\|a\|_{2}\big{)}W_{s}\big{(}\frac{z}{m}\mid\frac{a}{\|a\|_{2}}\big{)}.$

Therefore,

$\displaystyle P_{1}W(z)-P_{-1}W(z)$
$\displaystyle=\delta^{1+y}W_{g}\big{(}m\mid\frac{B}{\sqrt{2}\delta^{y}}\big{)}\left(W_{s}\big{(}\frac{z}{m}\mid-
e_{1}\big{)}-W_{s}\big{(}\frac{z}{m}\mid e_{1}\big{)}\right)$ $\displaystyle
P_{-1}W(z)$
$\displaystyle\geq\frac{1-\delta^{1+y}}{2}W_{g}\big{(}m\mid\frac{B}{\sqrt{2}}\big{)}W_{s}\big{(}\frac{z}{m}\mid
e_{1}\big{)}+\frac{1-\delta^{1+y}}{2}W_{g}\big{(}m\mid\frac{B}{\sqrt{2}}\big{)}W_{s}\big{(}\frac{z}{m}\mid-
e_{1}\big{)}.$

Using the preceding two inequalities

$\displaystyle\frac{(P_{1}W(z)-P_{-1}W(z))^{2}}{P_{-1}W(z)}$
$\displaystyle\leq\frac{\delta^{2+2y}W_{g}\big{(}m\mid\frac{B}{\sqrt{2}\delta^{y}}\big{)}^{2}\left(W_{s}\big{(}\frac{z}{m}\mid
e_{1}\big{)}-W_{s}\big{(}\frac{z}{m}\mid-
e_{1}\big{)}\right)^{2}}{\frac{1-\delta^{1+y}}{2}W_{g}\big{(}m\mid\frac{B}{\sqrt{2}}\big{)}W_{s}\big{(}\frac{z}{m}\mid
e_{1}\big{)}+\frac{1-\delta^{1+y}}{2}W_{g}\big{(}m\mid\frac{B}{\sqrt{2}}\big{)}W_{s}\big{(}\frac{z}{m}\mid-
e_{1}\big{)}}$
$\displaystyle\leq\frac{2\delta^{2+2y}}{1-\delta^{1+y}}\cdot\frac{W_{g}\big{(}m\mid\frac{B}{\sqrt{2}\delta^{y}}\big{)}^{2}\left(W_{s}\big{(}\frac{z}{m}\mid
e_{1}\big{)}+W_{s}\big{(}\frac{z}{m}\mid-
e_{1}\big{)}\right)}{W_{g}\big{(}m\mid\frac{B}{\sqrt{2}}\big{)}}$
$\displaystyle\leq\frac{2\delta^{2+y}}{1-\delta^{1+y}}\cdot
W_{g}\big{(}m\mid\frac{B}{\sqrt{2}\delta^{y}}\big{)}\left(W_{s}\big{(}\frac{z}{m}\mid
e_{1}\big{)}+W_{s}\big{(}\frac{z}{m}\mid-e_{1}\big{)}\right)$
$\displaystyle\leq\frac{2\delta^{2+y}}{1-\delta^{1+y}}\cdot\left(W_{s}\big{(}\frac{z}{m}\mid
e_{1}\big{)}+W_{s}\big{(}\frac{z}{m}\mid-e_{1}\big{)}\right),$

where the third inequality uses Assumption 3b for the quantizer in Section 1,
i.e., it uses

$\frac{W_{g}\big{(}m\mid\frac{B}{\sqrt{2}\delta^{y}}\big{)}}{W_{g}\big{(}m\mid\frac{B}{\sqrt{2}}\big{)}}\leq\delta^{-y}.$

For $z=0$, $z\in{\tt supp}(Q(a))$, when $a$ is in the support of $P_{1}$ or
$P_{-1}$, we have

$\displaystyle W\big{(}0\mid
a\big{)}=W_{g}\big{(}0\mid\|a\|_{2}\big{)}+W_{g}\big{(}m\mid\|a\|_{2}\big{)}W_{s}\big{(}0\mid
a/\|a\|_{2}\big{)}.$

Therefore, by similar calculations for $z\neq 0$, we have

$\displaystyle\frac{(P_{1}W(0)-P_{-1}W(0))^{2}}{P_{-1}W(0)}$
$\displaystyle\leq\frac{\delta^{2+2y}W_{g}\big{(}m\mid\frac{B}{\sqrt{2}\delta^{y}}\big{)}^{2}\left(W_{s}\big{(}0\mid
e_{1}\big{)}+W_{s}\big{(}0\mid-
e_{1}\big{)}\right)^{2}}{(\frac{1-\delta^{1+y}}{2})W_{g}\big{(}m\mid\frac{B}{\sqrt{2}}\big{)}W_{s}\big{(}0\mid
e_{1}\big{)}+(\frac{1-\delta^{1+y}}{2})W_{g}\big{(}m\mid\frac{B}{\sqrt{2}}\big{)}W_{s}\big{(}0\mid-
e_{1}\big{)}}$
$\displaystyle\leq\frac{2\delta^{2+y}}{1-\delta^{1+y}}\left(W_{s}\big{(}0\mid
e_{1}\big{)}+W_{s}\big{(}0\mid-e_{1}\big{)}\right).$

In conclusion,

$\displaystyle\chi^{2}(P_{1}W,P_{-1}W)\leq\frac{4\delta^{2+y}}{1-\delta^{1+y}}.$

Now, if $\delta<1/2,$ we have

$\displaystyle\chi^{2}(P_{1}W,P_{-1}W)\leq 8\delta^{2+y}.$

Upon setting $\delta=(16T)^{-1/(2+y)}$, which satisfies $\delta<1/2$ for all
$T$, we get

$\displaystyle\max_{\alpha\in\\{-1,1\\}}\mathcal{E}(f,O,\pi,Q)\geq\frac{DB}{2\sqrt{2}}\delta(1-\sqrt{4T\delta^{2+y}})=\frac{DB}{4\sqrt{2}}\left(\frac{1}{16T}\right)^{\frac{1}{2+y}}.$
(32)

But we can only set $\delta$ to this value if

$\displaystyle\frac{B}{\sqrt{2}}\cdot\left({16T}\right)^{\frac{y}{2+y}}<m.$
(33)

Thus, for each $y$ such that (33) holds, we get (32). Taking the the supremum
of RHS in (32) over all $y\in[0,1]$ such that (33) holds, we obtain whenever
$B/\sqrt{2}\leq m,$

$\displaystyle\max_{\alpha\in\\{-1,1\\}}\mathcal{E}(f,O,\pi,Q)\geq\frac{DB}{2\sqrt{2}}\cdot\min\left\\{\frac{1}{8}\sqrt{\frac{m\sqrt{2}}{BT}},\frac{1}{2(2T)^{1/3}}\right\\},$

where we use the following lemma proved in Section 3.

######  Lemma 6.11.

For $a,c>0,$ and $b>1$.

$\sup_{y\in[0,1]:a(b)^{y/(2+y)}<c.}a\left(\frac{1}{b}\right)^{\frac{1}{2+y}}=\min\left\\{\sqrt{\frac{ca}{b}},\frac{a}{b^{\frac{1}{3}}}\right\\}$

Upon combining this bound with (31), we obtain

$\sup_{(f,O)\in\mathcal{O}}\varepsilon(f_{\alpha},\pi^{QO})\geq\frac{DB}{2\sqrt{2}}\max\left\\{\min\left\\{\frac{cm}{M},1\right\\},\min\left\\{\frac{1}{8}\sqrt{\frac{1}{cT}},\frac{1}{2(2T)^{1/3}}\right\\}\mathbbm{1}_{\\{c<1\\}}\right\\},$

where $c=B/(m\sqrt{2})$. By making cases $1\leq c$, $\frac{1}{8(2T)^{1/3}}\leq
c<1$, and $c<\frac{1}{8(2T)^{1/3}}$, and using the fact that for $a,b\geq 0$,
$\max\\{a,b\\}\geq a^{1/3}b^{2/3}$ in the second case, we get

$\sup_{(f,O)\in\mathcal{O}}\varepsilon(f_{\alpha},\pi^{QO})\geq\frac{DB}{2\sqrt{2}}\min\bigg{\\{}1,\frac{1}{(M/m)},\frac{1}{4(M/m)^{1/3}T^{1/3}},\frac{1}{2(2T)^{1/3}}\bigg{\\}}.$

By Assumption 3 in Section 1, we know that $\frac{M}{m}\leq 2^{r}$. Therefore,

$\sup_{(f,O)\in\mathcal{O}}\varepsilon(f_{\alpha},\pi^{QO})\geq\frac{DB}{2\sqrt{2}}\min\bigg{\\{}\frac{1}{2^{r}},\frac{1}{4(2)^{r/3}T^{1/3}},\frac{1}{2(2T)^{1/3}}\bigg{\\}}.$

∎

Theorem 5.4 follows as an immediate corollary; Theorem 5.3, too, is obtained
by noting that

$\sup_{(f,O)\in\mathcal{O}}\varepsilon(f_{\alpha},\pi^{QO})<\frac{3DB}{\sqrt{T}}$

holds only if $\sqrt{T}<2^{r}$.

####  7 Remaining proofs for the main results

#####  1 Analysis of CUQ: Proof of Lemmas 6.1 and 6.2

###### Proof of Lemma 6.1:

Denoting by $\mathscr{B}_{j,\ell}$ the event
$\big{\\{}{Y}(j)\in[B_{M,k}(\ell),B_{M,k}(\ell+1))\big{\\}}$, we get

$\displaystyle\mathbb{E}\left[\sum_{j\in[d]}\big{(}Q_{{\tt
u}}(Y)(j)-{Y(j)}\big{)}^{2}\mathbbm{1}_{\\{{|Y(j)|}\leq M\\}}\mid Y\right]$
$\displaystyle=\sum_{j\in[d]}\sum_{\ell=0}^{k-1}\mathbb{E}\left[\big{(}Q_{{\tt
u}}(Y)(j)-{Y}(j)\big{)}^{2}\mathbbm{1}_{\mathscr{B}_{j,\ell}}\mid{Y}\right]\mathbbm{1}_{\\{{|Y(j)|}\leq
M\\}}.$

For the term inside the summation on the right-side, we obtain

$\displaystyle\mathbb{E}\left[\big{(}Q_{{\tt
u}}(Y)(j)-{Y}(j)\big{)}^{2}\mathbbm{1}_{\mathscr{B}_{j,\ell}}\mid{Y}\right]$
$\displaystyle=\left((B_{M,k}(\ell+1)-{Y}(j))^{2}\frac{{Y}(j)-B_{M,k}(\ell)}{B_{M,k}(\ell+1)-B_{M,k}(\ell)}\right)\mathbbm{1}_{\mathscr{B}_{j,\ell}}$
$\displaystyle\hskip
56.9055pt+\left((B_{M,k}(\ell)-{Y}(j))^{2}\frac{B_{M,k}(\ell+1)-{Y}(j)}{B_{M,k}(\ell+1)-B_{M,k}(\ell)}\right)\mathbbm{1}_{\mathscr{B}_{j,\ell}}$
$\displaystyle=\left(B_{M,k}(\ell+1)-{Y}(j))({Y}(j)-B_{M,k}(\ell)\right)\mathbbm{1}_{\mathscr{B}_{j,\ell}}$
$\displaystyle\leq\frac{1}{4}\left(B_{M,k}(\ell+1)-B_{M,k}(\ell)\right)^{2}$
$\displaystyle=\frac{M^{2}}{(k-1)^{2}},$ (34)

where the inequality uses the GM-AM inequality and the final identity is
simply by the definition of $B_{M,k}(\ell)$. Upon combining the bounds above,
we obtain

$\displaystyle\mathbb{E}\left[\sum_{j\in[d]}\big{(}Q_{{\tt
u}}(Y)(j)-{Y(j)}\big{)}^{2}\mathbbm{1}_{\\{{|Y(j)|}\leq M\\}}\mid
Y\right]\leq\frac{dM^{2}}{(k-1)^{2}}\cdot\frac{1}{d}\sum_{j\in[d]}\mathbbm{1}_{\\{{|Y(j)|}\leq
M\\}}.$

∎

###### Proof of Lemma 6.2

The proof is the same as the proof of Lemma 6.1, except that we need to set
$d=1$ and replace the identity used in(1) with

$B_{M,k}(\ell+1)-B_{M,k}(\ell)=\frac{M}{k-1}.$

#####  2 Proof of Lemma 6.8

For the rotation matrix $R=(1/\sqrt{d})HD$, each entry of $RY(j)$ of the
rotated matrix has the same distribution as $(1/\sqrt{d})V^{T}Y$, where
$V=[V(1),...,V(d)]^{T}$ has independent Rademacher entries. We will use this
observation to bound the moment generating function of $RY(i)$ conditioned on
$Y$. Towards that end, we have

$\displaystyle\mathbb{E}\left[e^{\lambda RY(i)}\mid Y\right]$
$\displaystyle=\prod_{i=1}^{d}\mathbb{E}\left[e^{\lambda
V(i)Y(i)/\sqrt{d}}\mid Y\right]$
$\displaystyle=\prod_{i=1}^{d}\frac{e^{\lambda Y(i)/\sqrt{d}}+e^{-\lambda
Y(i)/\sqrt{d}}}{2}$
$\displaystyle\leq\prod_{i=1}^{d}e^{\lambda^{2}Y(i)^{2}/2d}$
$\displaystyle=e^{\lambda^{2}\|Y\|_{2}^{2}/2d},$

where the first identity follows from independence of $V(i)$s and the first
inequality follows by the fact that $(e^{x}+e^{-x})/2$ is less than
$e^{x^{2}/2}$, which in turn can be seen from the Taylor series expansion of
these terms. Thus, we have proved the following:

$\displaystyle\mathbb{E}\left[e^{\lambda RY(i)}\mid Y\right]\leq
e^{\lambda^{2}\|Y\|_{2}^{2}/2d},\quad\forall\lambda\in\mathbb{R},\forall
i\in[d].$ (35)

Note that $\|Y\|_{2}^{2}$ can be further bounded by $B^{2}$, which along with
(35) leads to

$\mathbb{E}\left[e^{\lambda RY(i)}\right]\leq
e^{\lambda^{2}B^{2}/2d}\quad\forall\lambda\in\mathbb{R},\forall i\in[d].$

Using this inequality and the observation that
$\mathbb{E}\left[RY(i)\right]=0$, we note that $RY(i)$ is a centered
subgaussian with a variance parameter $B^{2}/d$. The second statement of the
lemma trivially follows from Lemma 6.6. ∎.

#####  3 Proof of Lemma 6.11

For any $y\in[0,1]$ such that $ab^{y/(2+y)}<c$, we have
$ab^{y/(2+y)}<\min\left\\{c,ab^{1/3}\right\\}$. By multiplying by $a/b$ on
both sides and taking square root, we get

$\frac{a}{b^{\frac{1}{2+y}}}<\min\left\\{\sqrt{\frac{ca}{b}},\frac{a}{b^{1/3}}\right\\},$

which gives

$\sup_{y\in[0,1]:a(b)^{y/(2+y)}<c.}\frac{a}{b^{\frac{1}{2+y}}}\leq\min\left\\{\sqrt{\frac{ca}{b}},\frac{a}{b^{1/3}}\right\\}.$

Making cases $ab^{1/3}\geq c$ and $ab^{1/3}<c$, we note that the supremum on
the left-side equals the right-side in both the cases. ∎

####  8 Concluding Remarks

In this chapter, we developed quantizers for communication-constrained
optimization over Euclidean spaces. The problem here essentially reduces to
minimizing the worst-case $\ell_{2}$ norm, $\alpha_{2}(Q)$ or $\alpha_{2}^{\tt
m}(Q)$, of the quantized gradient under the constraint that worst-case
$\ell_{2}$ bias between the quantized gradient and input gradient,
$\beta_{2}(Q)$ or $\beta_{2}^{\tt m}(Q)$, is small and the output of the
quantizer can be represented in $r$ bits. In fact, in the next chapter, we
will see that for designing gradient quantizers for communication-constrained
optimization over $\ell_{p}$ spaces, we need to solve a similar problem where
the $\ell_{q}$ norms are considered instead, where $q$ is the Hölder conjugate
of $p$. Since the only knowledge we have of the input gradient to be quantized
is either an almost sure or mean square-bound on the $\ell_{2}$ norm of the
gradient, we first preprocess the gradient to have some handle over the
distribution of the gradient coordinates. We do this by randomly rotating the
gradient input since it divides the overall gradient value equally across
coordinates. We believe that without any more information on gradient
distribution, this is a reasonable preprocessing. We will resort to this idea
of random rotation once again in Chapter 4. Another idea we will pick up from
the quantizer design in this chapter is that of adaptive quantization. As we
saw in our achievability proofs, adaptive gradient quantization became crucial
to come up with tight upper bounds. We will see in Chapter 5 that this idea
can also be used for classic information theory problems such as the Gaussian
rate-distortion problem.

###  Chapter 3 Communication-Constrained Optimization over $\ell_{p}$ Spaces

####  1 Synopsis

In this chapter, we study communication-constrained optimization for
$\ell_{p}$ lipschitz and convex function family. For this class of functions,
we characterize the minimum precision to which the oracle output must be
quantized to retain the unrestricted convergence rates? We characterize this
precision for every $p\geq 1$ by accessing the information theoretic lower
bounds derived in Chapter 1 and by providing quantizers that (almost) achieve
these lower bounds. Our quantizers are new and easy to implement. In
particular, our results are exact for $p=2$ and $p=\infty$, showing the
minimum precision needed in these settings are $\Theta(d)$ and $\Theta(\log
d)$, respectively. The latter result is surprising since recovering the
gradient vector will require $\Omega(d)$ bits.

The results presented in this Chapter are from [67].

####  2 Introduction

In this chapter, we develop new algorithms to match the lower-bounds for
communication-constrained optimization over $\ell_{p}$ spaces. Specifically,
we study communication-constrained optimization for convex and $\ell_{p}$
lipschitz function family. We study this problem in the _high-precision
regime_ introduced in Chapter 2. That is, we ask what is the minimum precision
to which the subgradient estimates’ supplied by the oracle must be quantized
so that we can attain the convergence of the classic, unrestricted setting. We
derive a lower bound on this precision using the lower bounds on optimization
error derived in Chapter 1. As our main contribution, we propose simple,
efficient subgradient quantization algorithms which along with appropriate
mirror decent algorithms match these lower bounds.

#####  1 Main Contributions

We show that for $p\in[1,2]$ and $p\geq 2$, respectively, roughly $d$ and
$d^{2/p}\log(d^{1-2/p}+1)$ bits are necessary and sufficient for retaining the
standard convergence rates. These bounds are tight upto an $O(\log d)$ factor,
in general, but are exact for $p=2$ and $p=\infty$. Prior work has only
considered the problem for the Euclidean case, and not for general $\ell_{p}$
geometry. Note that in the previous Chapter, we show that RATQ along with PSGD
requires a precision of $O(d\log\log\log\ln^{*}d)$ per iteration to attain the
classic convergence rate. In this chapter we get rid of the nagging
$\log\log\log\ln^{*}d$ factor and establish tight bounds.

We use different quantizers for $p\geq 2$ and $p\in[1,2]$. In the $p\geq 2$
range, we use a quantizer we call SimQ+. SimQ+, in turn, uses multiple
repetitions of another quantizer we call SimQ which expresses a vector as a
convex combination of corner points of an $\ell_{1}$ ball. It is SimQ that
yields an $O(\log d)$ bit quantizer for optimization over $\ell_{\infty}$.
Also, SimQ+ yields the exact upper bound in the $\ell_{2}$ case. In the
$[1,2]$ range, we divide the vector into two parts with small and large
coordinates. We use a uniform quantizer for the first part and RATQ of Chapter
2 for the second part.

The main observation in our analysis for upper bound is that the role of
quantizer in optimization is not to express the gradient with small error. It
suffices to have an unbiased estimate with appropriately bounded norms.

#####  2 Prior Work

A detailed literature review on the quantizer used in communication-
constrained optimization is presented in Chapter 2. Most of the literature in
this area looks at the Euclidean setting. In the general setting of
Information-constrained optimization, convex and $\ell_{p}$ Lipschitz family
was considered in [29], in a statistical query setup, and [24], in a local
differential privacy setup.

Finally, we remark that while our quantizers are related to the ones used in
prior works, our main contribution is to show that our specific design choices
yield optimal precision. For instance, the quantizers in [33] express the
input as a convex combination of a set of points, similar to SimQ. One of the
quantizers in [33] uses a similar set of points as that of SimQ with a
different scaling. However, the quantizers in [33] are designed keeping in
mind other objectives, and they fall short of attaining the optimal precision
guarantees of SimQ and SimQ+. SimQ is also closely related Maurey’s empirical
method (see [76], or [90] for a recent reference), however, the use in
gradient quantization is new.

##### Orgainization

In the next section, we describe the setup and the structure of the schemes we
will be employing. In Section 4, we describe the main result of the paper – a
characterization of the minimum precision required to attain classic
convergence rate for all $p$. In Section 5 and 1, we describe our quantizers
used to achieve our upper bounds. Finally, we close with comments on achieving
tight upper bounds for the lower bounds in Theorems 4.4 and 4.4 for all $p$
and for generalizing our results to mean square bounded oracles in Section 7.

####  3 Setup and preliminaries

#####  1 Setup

We consider optimization domains $\mathcal{X}_{p}$ such that $\ell_{p}$
diameter is less than $D$. That is,

$\displaystyle\mathcal{X}_{p}\in\mathbb{X}_{p}(D):=\\{\mathcal{X}^{\prime}:\sup_{x,y\in\mathcal{X}^{\prime}}\|x-y\|_{p}\leq
D.\\}$ (1)

For the domain of optimization $\mathcal{X}_{p}$, we develop subgradient
compression schemes for function and oracle families given by
$\mathcal{O}_{{\tt c},p}$, which are defined in Definition 3.3.

We want to study communication-constrained optimization for $\mathcal{O}_{{\tt
c},p}$ in the high precision regime. Thus, the fundamental quantity of
interest in this work is the minimum precision to achieve the optimization
accuracy of the classic case, denoted by $r^{*}(T,p)$. Symbolically,

$\displaystyle r^{*}(T,p)$
$\displaystyle:=\inf\\{r\in\mathbb{N}:\sup_{\mathcal{X}\in\mathbb{X}_{p}(D)}\mathcal{E}^{*}(\mathcal{X},\mathcal{O}_{{\tt
c},p},T,\mathcal{W}_{{\tt com},r})\leq\mathcal{U}(T,p)\\},$ (2)

where

$\displaystyle\mathcal{U}(T,p)$
$\displaystyle:=\frac{4c_{1}d^{1/2-1/p}DB}{\sqrt{T}},\quad\forall
p\in(2,\infty],$ (3) $\displaystyle\mathcal{U}(T,p)$
$\displaystyle:=\frac{4c_{1}\sqrt{\log d}DB}{\sqrt{T}},\quad\forall
p\in[1,2),$

and
$\sup_{\mathcal{X}\in\mathbb{X}_{p}(D)}\mathcal{E}^{*}(\mathcal{X},\mathcal{O}_{{\tt
c},p},T,\mathcal{W}_{{\tt com},r})$ is as defined in Chapter 1. Recall that
$\mathcal{U}(T,p)$ denotes the classic convergence rate for the family
$\mathcal{O}_{{\tt c},p}$ given in Theorem 3.5, where the oracle output is
available as it is to the optimization algorithm, without any quantization.

#####  2 Quantizer performance for finite precision optimization

As described in Section 2, we restrict to memoryless quantization schemes,
where the same quantizer will be used for each new subgradient vector, without
any information about the previous updates. Also recall from Section 2, our
nonadaptive channel selection strategy is simply denote by quantizer $Q$.
Further, the optimization error for a function $f$ and oracle $O$ when
employing a first order optimization $\pi$ and quantizer $Q$ is given by

$\mathcal{E}(f,O,\pi,Q)=\mathbb{E}\left[f(x_{T})\right]-\mathbb{E}\left[f(x^{\ast})\right].$

We now define $\alpha_{p}(Q)$, which generalizes the definition of
$\alpha_{2}(Q)$ in Chapter 2, to charactize the performance of a quantizer $Q$
for optimization of convex and $\ell_{p}$ lipschitz funciton class. Since we
restrict to unbiased quantizers, we don’t need to define $\beta$.

$\displaystyle{\alpha_{p}(Q):=\sup_{Y\in\mathbb{R}^{d}:\|Y\|_{q}^{2}\leq
B^{2}\text{ a.s.}}\sqrt{\mathbb{E}\left[\|Q(Y)\|_{2}^{2}\right]},\quad
p\in(2,\infty]},$

$\displaystyle{\alpha_{p}(Q):=\sup_{Y\in\mathbb{R}^{d}:\|Y\|_{q}^{2}\leq
B^{2}\text{ a.s.}}\sqrt{\mathbb{E}\left[\|Q(Y)\|_{q}^{2}\right]},\quad
p\in[1,2].}$

Note that for all $p\geq 1$, the composed oracle $QO$ satisfies assumption
(5). We employ the stochastic mirror descent (SMD) algorithm with mirror maps
given by Remarks 1 and 2 to use the output from the composed oracle. The
algorithm’s description is given in Algorithm 1. Recall that for a mirror map
$\Phi$, the Bregman divergence associated with $\Phi$ is defined as

$D_{\Phi}(x,y)\colon=\Phi(x)-\Phi(y)-\langle\nabla\Phi(y),x-y\rangle.$

1:Require: $x_{0}\in\mathcal{X},\eta\in\mathbb{R}^{+}$, $T$ and access to
composed oracle $QO$ 2:for $t=0$ to $T-1$ do
$x_{t+1}=\arg\min_{x\in\mathcal{X}}(\eta_{t}\langle
x,Q(\hat{g}(x_{t}))\rangle)+D_{\Phi_{a}}(x,x_{t}))$ 3:Output:
$\frac{1}{T}\cdot{\sum_{t=1}^{T}x_{t}}$ Algorithm 1: Quantized SMD with
quantizer $Q$

Moreover, in view of Remarks 1 and 2 , we have the following convergence
guarantees for first-order stochastic optimization using gradients quantized
by $Q$.

######  Theorem 3.1.

Consider a quantizer $Q$ for the gradients. Then the algorithm 1 with mirror
maps as in Remarks 1 and 2 and an unbiased quantizer $Q$ performs as follows.

  1. 1.

For $2\geq p\geq 1$,

$\displaystyle{\frac{c_{1}\sqrt{\log
d}D\alpha_{p}(Q)}{\sqrt{T}}\geq\sup_{(f,O)\in\mathcal{O}_{{\tt
c},p}}\mathcal{E}(f,O,\pi,Q);}$

  2. 2.

For $p>2$,

$\displaystyle{\frac{c_{1}d^{1/2-1/p}D\alpha_{p}(Q)}{\sqrt{T}}\geq\sup_{(f,O)\in\mathcal{O}_{{\tt
c},p}}\mathcal{E}(f,O,\pi,Q).}$

###### Proof.

The proof straightaway follows from Theorem 3.5 and Remarks 1 and 2. For
completeness, we provide the details below.

First statement simply follows by noting that the bounds in Theorem 3.2 hold
when instead of $\|\hat{g}(x)\|_{q}\leq B,$ we have
$\mathbb{E}\left[\|\hat{g}(x)\|_{q}^{2}\right]\leq B^{2}$ and then using
definition of $\alpha_{p}.$ The second statement simply follows by noting that
the bounds in Theorem 3.2 are obtained by employing PSGD. Thus it suffices to
only have a bound on $\mathbb{E}\left[\|\hat{g}(x)\|_{2}^{2}\right]$ and then
using the definition of $\alpha_{p}.$

∎

An interesting insight offered by the result above, which is perhaps simple in
hindsight, is that even when dealing with $\ell_{p}$ oracles for $p>2$, we
only need to be concerned about the expected $\ell_{2}$ norm of the quantizers
output. This follows from the fact that PSGD is the optimal optimization
algorithm for $p>2$ and it’s convergence rate is only concerned with the
$\ell_{2}$ norm of the quantizers output. It is this insight that leads to the
realization that SimQ+ is optimal for these settings.

In the rest of the Chapter, we design unbiased, fixed length quantizers which
have $\alpha_{p}(\cdot)$ of the same order as $B$. Then, using Theorem 3.1 the
quantized updates give the same convergence guarantees as that of the
classical case, which leads to upper bounds for $r^{*}(T,p)$. Further, we
using Theorems 4.4 and 4.5, we derive lower bounds for $r^{*}(T,p)$ to prove
optimality of our quantizers.

####  4 Main Result: Characterization of $r^{*}(T,p)$

The main result of this Chapter is the almost complete characterization of
$r^{*}(T,p)$. We divide the result into cases $p\in[1,2]$ and $p\geq 2$; as
mentioned earlier, we use different quantizers for these two cases.

######  Theorem 4.1.

For stochastic optimization using $T$ accesses to a first-order oracle, the
following bounds for $r^{*}(T,p)$ hold.

  1. 1.

For $p>2$, we have

$\displaystyle d^{2/p}\log$ $\displaystyle\,(2e\cdot d^{1-2/p}+2e)\geq
r^{*}(T,p)\geq\left(\frac{c_{0}}{4c_{1}}\cdot d^{1/p}\right)^{2}\vee
2\log\left(\frac{c_{0}}{4c_{1}}\cdot d^{1/2}\right).$

  2. 2.

For $2\geq p\geq 1,$ we have

$\displaystyle
d\left(\left\lceil\log(2\sqrt{2}{\Delta_{1}}^{1/q}+2)\right\rceil+3\right)+\Delta_{2}\geq~{}r^{*}(T,p)\geq\left(\frac{c_{0}}{4c_{1}\sqrt{\log
d}}\right)^{2}\cdot d,$

where $\Delta_{1}=\left\lceil\log\left(2+\sqrt{18+6\ln\Delta_{2}}\cdot
d^{1/2-1/q}\right)\right\rceil$ and
$\Delta_{2}=\left\lceil\log(1+\ln^{*}({d}/{3}))\right\rceil.$

Note that for $p>2$ the upper bounds and lower bounds for $r^{*}(T,p)$ are off
by nominal factor of $\log(d^{1-2/p}+1)$. Also, for $p\in[1,2]$ the bounds are
roughly off by $O(\log d\cdot\log(\log d^{1/2-1/q})^{1/q})$ (ignoring the
$\log^{*}d$ terms).

We present the quantizers achieving these upper bounds, and the proof of the
upper bounds, in the next two sections. For $p>2$, we use a quantizer SimQ and
its extension SimQ+, presented in Section 5. For $p\in[1,2]$, we use a
combination of uniform quantization and the quantizer RATQ from previous
chapter, presented in Section 6. The lower bounds on $r^{*}(T,p)$ follow
immediately by the lower bounds in Theorem 4.5 and 4.4.

We highlight the most interesting features of the result above in separate
remarks below.

######  Remark 24 ($r^{*}(T,p)$ is independent of $T$).

Theorem 4.1 shows that $r^{*}(T,p)$ is a function only of $p$ and $d$, and is
independent of $T$. The number of queries $T$ is a proxy for the desired
optimization accuracy. Therefore, the fact that $r^{*}(T,p)$ is independent of
such a parameter is interesting. We note, however, that for oracle models with
milder assumptions, such as mean square bounded oracles, this may not hold. In
fact, the results of previous chapter suggest that for mean square bounded
oracles $r^{*}(T,2)$ is dependent on $T$.

######  Remark 25 (Optimality for $p=\infty$).

Our bounds match for $p=\infty$, namely our quantizer SimQ offers optimal
convergence rate with gradient updates at the least precision. A surprising
observation is that this precision is merely $O(\log d)$, much smaller than
$O(d)$ bits needed to recover the gradient vector under any reasonable loss
function.

######  Remark 26 (Optimality for $p=2$).

The high-precision regime for $p=2$ was already considered in the previous
chapter. Both [9] and [88] give variable-length quantization schemes to
exactly achieve the lower bound on $r^{*}(T,p)$, but the worst-case precision
can be order-wise greater than $d$. The quanitzer RATQ from the previous
Chapter was within a small factor of $O(\log\log\log\ln^{*}d)$ of this lower
bound. In this chapter, we remove this nagging factor using a different fixed-
length quantizer SimQ+.

######  Remark 27 (Fixed precision).

The quantizer RATQ remains optimal upto a factor of $O(\sqrt{\log\ln^{*}d})$
for the more general problem of characterizing
$\displaystyle{\sup_{\mathcal{X}\in\mathbb{X}_{p}(D)}\mathcal{E}^{*}(\mathcal{X},\mathcal{O}_{{\tt
c},p},T,\mathcal{W}_{{\tt com},r})}$ for any precision $r$ less than $d$ bits.
In this setting of small precision, the performance of SimQ+ is much worse.

####  5 Our quantizers for $p>2$

We present our quantizer SimQ and its extension SimQ+. The former is seen to
be optimal for $p=\infty$ while the latter for $p=2$.

#####  1 An optimal quantizer for $p=\infty$

1:Input $Y\in\mathbb{R}^{d}$, Parameter $B$ 2:$i^{*}=\begin{cases}i\quad
w.p.\quad|Y(i)|/B\\\ 0\quad w.p.\quad 1-\|Y\|_{1}/B\end{cases}$ 3:if
$i^{*}\in[d]$ then 4: $j^{*}=sign(Y(i^{*}))$ 5:else 6: $j^{*}=1$ 7:Output:
$Q^{{\tt e}}_{{\tt SimQ}}(Y;B)=i^{*}\cdot j^{*}$ Figure 2: Encoder $Q^{{\tt
e}}_{{\tt SimQ}}(Y;B)$ for SimQ 1:Input $i^{\prime}\in\\{-d,-(d-1),\cdots
0,\cdots,d\\}$ 2:if $i^{\prime}\neq 0$ then 3:
$Z=Bsign(i^{\prime})e_{|i^{\prime}|}$ 4:else 5: $Z=0$ 6:Output: $Q^{{\tt
d}}_{{\tt SimQ}}(i^{\prime};B)=Z$ Algorithm 3: Decoder $Q^{{\tt d}}_{{\tt
SimQ}}(i^{\prime};B)$ for SimQ

######  Simplex Quantizer (SimQ)

Our first quantizer SimQ is described in Algorithms 2 and 3. For $p=\infty$,
our quantizer’s input vector $Y$ is an unbiased estimate of the subgradient of
the function at the point queried and satisfies $\|Y\|_{1}\leq B$. SimQ takes
such a $Y$ as an input and produces an output vector which, too, satisfies
both these properties. The main idea behind SimQ is the fact that any point
inside the unit $\ell_{1}$ ball can be represented as a convex combination of
at the most $2d$ points: $\\{e_{i},-e_{i}:i\in[d]\\}$. With this observation,
we can create an unbiased estimate of the input vector using only these $2d$
corner points along with the zero vector. Since all of these $2d+1$ points
have a $\ell_{2}$ norm of at the most $B$, the output vector, too, has a
$\ell_{2}$ norm of at the most $B$.

######  Theorem 5.1.

Let $Q$ be the quantizer SimQ described in Algorithms 2, 3. Then, for $Y$ such
that $\|Y\|_{1}\leq B~{}a.s.$, $Q(Y)$ can be represented in $\log(2d+1)$ bits,
$\mathbb{E}\left[Q(Y)|Y\right]=Y$, and $\alpha_{\infty}(Q)\leq B$.

###### Proof.

Since $i^{*}\in[d]$ and $j^{*}\in\\{-1,1\\}$, we can represent the output of
the encoder of SimQ using $\log(2d+1)$ bits. Next, denoting the quantizer SimQ
by $Q$, note that

$\mathbb{E}\left[Q(Y)|Y\right]=\sum_{i=1}^{d}B\cdot sign(Y(i))\cdot
e_{i}\cdot\frac{|Y(i)|}{B}=Y,$

namely SimQ is unbiased. To complete the proof, note that
$\|Q(Y)\|_{2}^{2}\leq B^{2}~{}a.s.$. ∎

Theorem 5.1 along with Theorem 3.1 establishes Theorem 4.1 for $p=\infty$.

#####  2 Our Quantizer for $p\in[2,\infty)$

For this case, we need to quantize inputs that are bounded in $\ell_{q}$ norm
with $q\in(1,2]$ so that the quantized output is unbiased and has small
expected $\ell_{2}$ norm square; we will use SimQ+ to do this.

###### $\textbf{SimQ}^{+}$

The quantizer SimQ+ outputs the average of $k$ independent repetitions of the
SimQ quantizer for a given input vector. The input vectors $Y$ satisfy
$\|Y\|_{1}\leq Bd^{1/p}$. Therefore, we use SimQ with parameter $Bd^{1/p}$
instead of $B$. The repetitions help reduce the error to compensate for the
extra loss factor. Specifically, the output of SimQ+ denoted by $Q(Y)$ is
given by

$\displaystyle Q(Y)=\frac{1}{k}\cdot\sum_{i=1}^{k}Q^{i}_{\tt
SimQ}(Y;Bd^{1/p}),$ (4)

where $Q^{i}_{\tt SimQ}$ are independent iterations of SimQ.

The next component of SimQ+ is how the encoder of SimQ+ expresses the output
of these $k$ copies of SimQ to attain compression. If represented naively,
this will require $O(d^{2/p}\log d)$. But we can do much better since we only
need the average value of these entries. For that, we can simply report the
type of this vector – the frequency of each index in the $k$ length sequence.
The signs of the input coordinates for the non-zero entries can be sent
separately.

Note that there are $d+1$ indices overall, as SimQ can pick any index from
$\\{0,\ldots d\\}$. Therefore, the total number of types is
${{d+k}\choose{k}}$, which can at the most be $(\frac{ed+ek}{k})^{k}$ bits.
Hence, the precision needed to represent the type is at the most $k\log
e+k\log(\frac{d}{k}+1)$.

The type of the input can be used to determine a set $\mathcal{I}_{0}$ of non-
zero indices that appear at least once. There are at most $k$ such entries.
Therefore, we can use a binary vector of length $k$ to store the signs for
these entries. We use this representation in SimQ+, with the indices in
$\mathcal{I}_{0}$ represented in the vector in increasing order.

######  Theorem 5.2.

For a $p\in[2,\infty)$, let $Q$ be the quantizer SimQ+ described in (4). Then,
for $Y$ such that $\|Y\|_{q}\leq B~{}a.s.,$ $Q(Y)$ can be represented in
$k\log e+k\log(\frac{d}{k}+1)+k$ bits, $\mathbb{E}\left[Q(Y)|Y\right]=Y$, and
$\displaystyle{\alpha_{p}(Q)\leq\sqrt{\frac{B^{2}d^{2/p}}{k}+B^{2}}}$.

###### Proof.

We already saw how to represent the output of the $k$ copies of SimQ using
$k\log e+k\log(\frac{d}{k}+1)+k$ bits. For bounding $\alpha_{p}(Q)$, note from
(4) that SimQ+ is an unbiased quantizer since SimQ is unbiased. Further,
denoting by $Q_{i}(Y)$ the output $Q^{i}_{\tt SimQ}(Y;Bd^{1/p})$, we get

$\displaystyle\mathbb{E}\left[\|Q(Y)\|_{2}^{2}\right]$
$\displaystyle=\mathbb{E}\left[\|Q(Y)-Y\|_{2}^{2}\right]+\mathbb{E}\left[\|Y\|_{2}^{2}\right]$
$\displaystyle=\frac{1}{k^{2}}\sum_{i=1}^{k}\mathbb{E}\left[\mathbb{E}\left[\|Q_{i}(Y)-Y\|_{2}^{2}|Y\right]\right]+\mathbb{E}\left[\|Y\|_{2}^{2}\right]$
$\displaystyle=\frac{\mathbb{E}\left[\|Q_{1}(Y)-Y\|_{2}^{2}\right]}{k}+\mathbb{E}\left[\|Y\|_{2}^{2}\right]$
$\displaystyle\leq\frac{d^{2/p}B^{2}}{k}+B^{2},$

where the first identity uses the fact that $Q(Y)$ is an unbiased estimate of
$Y$; the second uses the fact that $Q_{i}(Y)-Y$ are zero-mean, independent
random variables when conditioned on $Y$; the third uses the fact that
$Q_{i}(Y)-Y$ are identically distributed; and the final inequality is by the
performance of SimQ. ∎

The proof of upper bound for $p\in[2,\infty)$ in Theorem 4.1 is completed by
setting $k=d^{2/p}$ and using Theorems 5.2 and 3.1.

####  6 Our Quantizers for $p\in[1,2]$

For p in $[1,2]$, the oracle yields unbiased subgradient estimates $Y$ such
that $\|Y\|_{q}\leq B$ almost surely. Our goal is to quantize such $Y$s in an
unbiased manner and ensure that $\mathbb{E}\left[\|Q(Y)\|_{q}^{2}\right]$ is
$O(B^{2})$. It can be seen that a simple unbiased uniform quantizer will
achieve this using $d(\log d^{1/q}+1)$. However, our goal here is to get a
result that is stronger than this baseline performance. To that end, we split
the input vector $Y$ in two parts $Y_{1}$ and $Y_{2}$ with the first part
having $\ell_{\infty}$ norm less than $c$ and the second part having less than
$d/\Delta_{1}$ nonzero coordinates. We use an “$\ell_{\infty}$ ball quantizer”
(a uniform quantizer) for $Y_{1}$ and an “$\ell_{2}$ ball quantizer” for
$Y_{2}$.

Specifically, set $\displaystyle{c:=\frac{B\Delta_{1}^{1/q}}{d^{1/q}}},$ where
$\Delta_{1}$ is that in Theorem 4.1. Then, define

$\displaystyle Y_{1}:=\sum_{i=1}^{d}Y(i)\mathbbm{1}_{\\{|Y(i)|\leq
c\\}}e_{i},\text{~{}~{}}Y_{2}:=\sum_{i=1}^{d}Y(i)\mathbbm{1}_{\\{|Y(i)|>c\\}}e_{i}.$
(5)

Clearly, $\|Y_{1}\|_{\infty}\leq c$. Further, since $\|Y\|_{q}\leq B$, the
number of nonzero coordinates in $Y_{2}$ can be at the most
$B^{q}/c^{q}=d/\Delta_{1}$. For quantizing $Y_{1}$, we use the coordinate-wise
uniform quantizer (CUQ) described in Section 1. In order to quantize $Y_{1}$
in (5), we set the parameters of CUQ to

$\displaystyle
M=c,\quad\log(k+1)=\left\lceil\log(2\sqrt{2}\Delta_{1}^{1/q}+2)\right\rceil.$
(6)

######  Lemma 6.1.

Let $Q_{\tt u}$ be the quantizer CUQ with parameters $M$ and $k$ set as in
(6). Then, for $Y$ such that $\|Y\|_{q}\leq B~{}\text{a.s.}$ and $Y_{1}$ as
that in (5), $Q_{\tt u}(Y_{1})$ can be represented in
$d\left\lceil\log(2\sqrt{2}\Delta_{1}^{1/q}+2)\right\rceil$ bits,
$\mathbb{E}\left[Q_{\tt u}(Y_{1})\mid|Y\right]=Y_{1}$, and
$\mathbb{E}\left[\|Q_{\tt u}(Y_{1})\|_{q}^{2}\right]\leq 3B^{2}$.

###### Proof.

CUQ requires a precision of $d\log(k+1)$, which coincides with the statement
above for our choice of $k$. To see unbiasedness, note that CUQ is an unbiased
quantizer as long as all the coordinates of the input do not exceed $M$. Since
we have set $M=c$ and $\|Y_{1}\|_{\infty}=c$, this property holds. Finally, to
show that $\mathbb{E}\left[\|Q_{\tt u}(Y_{1})\|_{q}^{2}\right]\leq 3B^{2}$,
note that $\mathbb{E}\left[\|Q_{\tt u}(Y_{1})\|_{q}^{2}\right]\leq
2\mathbb{E}\left[\|Q_{\tt
u}(Y_{1})-Y_{1}\|_{q}^{2}\right]+2\mathbb{E}\left[\|Y_{1}\|_{q}^{2}\right].$
Also, $\mathbb{E}\left[\|Q_{\tt u}(Y_{1})-Y_{1}\|_{q}^{2}\right]\leq B^{2},$
where we use the fact that for $M$ set as in (6) we have that $|Q_{\tt
u}(Y_{1})(i)-Y_{1}(i)|\leq\frac{2M}{(k-1)}$ a.s., $\forall i\in[d]$, by the
description of CUQ. ∎

In order to quantize $Y_{2}$, we indicate the coordinates with non-zero
entries. This takes less than $d$ bits. Then, we quantize the restriction
$Y_{2}^{\prime}$ of $Y_{2}$ to these nonzero entries. Recall that the
dimension of $Y_{2}^{\prime}$ is less than $d^{\prime}:={d}/{\Delta_{1}}$.
Also, the $\ell_{2}$ norm of $Y_{2}^{\prime}$ is less than
$\|Y\|_{2}\leq\|Y\|_{q}d^{1/2-1/q}\leq Bd^{1/2-1/q}=:B^{\prime}$.

We need a quantizer $Q$ such that
$\mathbb{E}\left[\|Q(Y_{2}^{\prime})\|_{q}^{2}\right]$ is $O(B^{2})$. As seen
in the proof of Lemma 6.1, one way to do this is to ensure
$\mathbb{E}\left[\|Q(Y_{2}^{\prime})-Y^{\prime}\|_{q}^{2}\right]$ is
$O(B^{2}),$ which, in turn, can be ensured if
$\mathbb{E}\left[\|Q(Y_{2}^{\prime})-Y_{2}^{\prime}\|_{2}^{2}\right]$ is
$O(B^{2})$. To achieve this, we can use an unbiased quantizer for the unit
$\ell_{2}$ ball in $\mathbb{R}^{d}$, which can quantize it to an MSE of
$O(1/d^{1-2/q})$ using $O(d\log(d^{1/2-1/q})$ bits. We note that SimQ+, while
optimal for the stochastic optimization use-case, does not yield the required
scaling of bits in MSE. A natural candidate quantizer is RATQ, which is, in
fact, close to information theoretically optimal. We set the parameters of
RATQ in terms of $B^{\prime}$ and $d^{\prime}$. We set

$\displaystyle m=\frac{3{B^{\prime}}^{2}}{d^{\prime}},\quad
m_{0}=\frac{2{B^{\prime}}^{2}}{d^{\prime}}\cdot\ln s,\quad\log
h=\left\lceil\log(1+\ln^{\ast}(d^{\prime}/3))\right\rceil,$ $\displaystyle
s=\log h,\quad\log(k+1)=\Delta_{1}.$ (7)

######  Lemma 6.2.

Let $Q_{{\tt at},R}$ be the quantizer RATQ with parameters set as (6). Then,
for $Y$ such that $\|Y\|_{q}\leq B~{}{a.s.}$ and $Y_{2}^{\prime}$ the
restriction of $Y_{2}$ in (5), $Q_{{\tt at},R}(Y_{2}^{\prime})$ can be
represented in $2d+\Delta_{2}$ bits, $\mathbb{E}\left[Q_{{\tt
at},R}(Y_{2}^{\prime})\mid|Y\right]=Y_{2}^{\prime}$, and
$\mathbb{E}\left[\|Q_{{\tt at},R}(Y_{2}^{\prime})\|_{q}^{2}\right]\leq
3B^{2}.$

###### Proof.

First, we note that the output of RATQ can be represented in $\left\lceil
d^{\prime}/s\right\rceil(\log h)+d\log(k+1)$ bits, which, in this case, is
less than

$\displaystyle\frac{d}{\Delta_{1}\log h}\cdot\left(\log h\right)+\log
h+\left(\frac{d}{\Delta_{1}}\log(k+1)\right)\leq 2d+\Delta_{2}.$

For unbiasedness, note that for our choice of $m,m_{0},h$, RATQ is always an
unbiased quantizer of the input. Finally, for showing
$\mathbb{E}\left[\|Q_{{\tt at},R}(Y_{2}^{\prime})\|_{q}^{2}\right]\leq
3B^{2}$, we note that

$\displaystyle\mathbb{E}\left[\|Q_{{\tt
at},R}(Y_{2}^{\prime})\|_{q}^{2}\right]$ $\displaystyle\leq
2\mathbb{E}\left[\|Q_{{\tt
at},R}(Y_{2}^{\prime})-Y_{2}^{\prime}\|_{q}^{2}\right]+2\mathbb{E}\left[\|Y_{2}^{\prime}\|_{q}^{2}\right]$
$\displaystyle\leq 2\mathbb{E}\left[\|Q_{{\tt
at},R}(Y_{2}^{\prime})-Y_{2}^{\prime}\|_{q}^{2}\right]+2B^{2}$
$\displaystyle\leq 2\mathbb{E}\left[\|Q_{{\tt
at},R}(Y_{2}^{\prime})-Y_{2}^{\prime}\|_{2}^{2}\right]+2B^{2}.$

The proof will be complete upon showing that $\mathbb{E}\left[\|Q_{{\tt
at},R}(Y_{2}^{\prime})-Y_{2}^{\prime}\|_{2}^{2}\right]\leq B^{2}/2$, towards
which we apply Lemma 6.9 to get

$\mathbb{E}\left[\|Q_{{\tt
at},R}(Y_{2}^{\prime})-Y_{2}^{\prime}\|_{2}^{2}\right]\leq
B^{2}d^{1-2/q}\cdot\frac{9+3\ln s}{(k-1)^{2}},$

and substituting our choice of $k$. ∎

The overall quantizer $Q$ of input vector $Y$ is the sum of quantized outputs
of $Y_{1}$ and $Y_{2}$. By Lemmas 6.1 and 6.2, the quantized output of $Y$ can
be represented in
$d\left(\left\lceil\log(2\sqrt{2}{\Delta_{1}}^{1/q}+2)\right\rceil+3\right)+\Delta_{2}$
bits111This accounts for the communication needed to send the nonzero indices
of $Y_{2}$, too.. Furthermore, $\alpha_{p}(Q)\leq\sqrt{12}B$. These facts
along with Theorem 3.1 prove the upper bound in Theorem 4.1 for $p\in[1,2]$.

####  7 Characterization of general tradeoff and mean square bounded oracles

We close with the remark that an almost complete characterization of
optimization error $\mathcal{E}^{*}(\mathcal{X},\mathcal{O}_{{\tt
c},p},T,\mathcal{W}_{{\tt com},r})$ for any $r,p$ (namely, the low-precision
regime) can be obtained using our quantizers and the ideas developed in this
Chapter. We describe in detail algorithms to achieve these bounds below.

#####  1 Upper Bounds on $\mathcal{E}^{*}(\mathcal{X},\mathcal{O}_{{\tt
c},1},T,\mathcal{W}_{{\tt com},r})$ for $p\in(2,\infty]$

For upper bounds when $p\in[2,\infty)$, note that the parameter $k$ of SimQ+
gives us a nice lever to operate under any precision constraint $r\geq\log d$.
It turns out that such a quantizer along with PSGD leads to upper bounds which
are off by at the most $\sqrt{\log d}$ factor from the lower bounds in Theorem
4.5.

#####  2 Upper Bounds on $\mathcal{E}^{*}(\mathcal{X},\mathcal{O}_{{\tt
c},1},T,\mathcal{W}_{{\tt com},r})$

We now describe a new scheme to match the lower bound for $p=1$. Our scheme
divides the entire horizon of $T$ iterations into $Tr/d$ different phases. For
any phase $t\in[Tr/d]$, the same point $x_{t}$ in the domain is queried $d/r$
times. For each of the $d/r$ queries in a phase, we use $r$-bit quantizers to
quantize different coordinates of the subgradient output. At a high level, we
want to use these $r$ bits to send $1$ bit each for $r$ different coordinates,
sending $1$ bit for each coordinate across the phases. However, there is one
technical difficulty. We have not assumed that making queries for the same
point gives identically distributed random variables. We circumvent this
difficulty using random permutations to create unbiased estimates for the
subgradients.

Specifically, for a permutation $\sigma\colon[d]\to[d]$ chosen uniformly at
random using public randomness, we select the coordinates $\sigma(1+(i-1)\cdot
r)$ to $\sigma(i\cdot r)$ of the subgradient estimate $\hat{g}_{i}$ supplied
by the oracle for the $i$th query in the $t$th phase (i.e., $i$th time we
query the point $x_{t}$) and quantize all of these coordinates using an
$1$-bit unbiased quantizer for the interval $[-B,B]$. Note that such a
quantizer can be formed since $\|\hat{g}_{i}\|_{\infty}\leq B$.

Using this procedure, the quantized gradient for every query in each phase can
be stored in $r$ bits. Furthermore, using all the $d/r$ quantized estimates
received in a phase, we can create an estimate of the subgradient by simply
adding all the estimates. Denote by $\bar{Q}_{t}$ our subgradient estimate in
the $t$th phase. Then,

$\bar{Q}_{t}=\sum_{i=1}^{d}Q_{\pi(i)}(\hat{g}_{i})e_{\sigma(i)},$

where $\hat{g}_{i}$ is the subgradient estimate returned by the oracle when we
query $x_{t}$ for the $i$th time and $Q_{i}$ is a $1$-bit unbiased estimator
of the $i$th coordinate of gradient estimate given below: For all vectors $g$,
such that $\|g\|_{\infty}\leq B$, we have

$Q_{i}(g)=\begin{cases}B&\text{ w.p. }\quad\frac{g(i)+B}{2B}\\\ -B&\text{ w.p.
}\quad\frac{B-g(i)}{2B}\end{cases}.$

Then, we use $\bar{Q}_{t}$ to update $x_{t}$ to $x_{t+1}$ using stochastic
mirror descent with mirror map

$\phi_{a}(x)\colon=\frac{\|x\|_{a}^{2}}{a-1},$

where $a=\frac{2\log d}{2\log d-1}$.

1:for $t\in[Tr/d]$ do 2: for $i\in[d/r]$ do 3: At Center: Query the oracle for
$x_{t}$ 4: At Oracle: Output the $r$-bit vector of $1$-bit unbiased estimates
of the  5:$r$ coordinates $\\{1+(i-1)\cdot r,\ldots,i\cdot r\\}$ of
$\hat{g}_{i}(x_{t})$ given by  $\bar{Q}_{t}=\sum_{j=1+(i-1)\cdot r}^{i\cdot
r}Q_{\pi(j)}(\hat{g}_{i}(x_{t}))e_{\sigma(j)}$ 6: At Center:
$x_{t+1}=\arg\min_{x\in\mathcal{X}}(\eta_{t}\langle