# Democratic Source Coding: An Optimal Fixed-Length Quantization Scheme for
Distributed Optimization Under Communication Constraints

Rajarshi Saha
Electrical Engineering
Stanford University
Stanford, CA 94305
<EMAIL_ADDRESS>
&Mert Pilanci
Electrical Engineering
Stanford University
Stanford, CA 94305
<EMAIL_ADDRESS>
&Andrea J. Goldsmith
Electrical and Computer Engineering
Princeton University
Princeton, NJ 08540
<EMAIL_ADDRESS>

###### Abstract

The communication cost of distributed optimization algorithms is a major
bottleneck in their scalability. This work considers a parameter-server
setting in which the worker is constrained to communicate information to the
server using only $R$ bits per dimension. We show that democratic embeddings
from random matrix theory are significantly useful for designing efficient and
optimal vector quantizers that respect this bit budget. The resulting
polynomial complexity source coding schemes are used to design distributed
optimization algorithms with convergence rates matching the minimax optimal
lower bounds for: (i) Smooth and Strongly-Convex objectives with access to an
Exact Gradient oracle, as well as (ii) General Convex and Non-Smooth
objectives with access to a Noisy Subgradient oracle. We further propose a
relaxation of this coding scheme which is nearly minimax optimal. Numerical
simulations validate our theoretical claims.

##  1 Introduction

Distributed optimization algorithms that leverage the computational
capabilities of multiple devices have proved promising for training large-
scale machine learning models [7, 18]. To solve an optimization problem
$\mathop{\rm min_{\cdot}}_{\mathbf{x}\in{\cal
X}\subseteq\mathbb{R}^{n}}f(\mathbf{x})$ in the parameter-server framework
[23], the server maintains an estimate $\mathbf{x}_{t}$ of the minimizer
$\mathbf{x}_{f}^{*}$ of $f(\mathbf{x})$ at iteration $t$. For first-order
algorithms, the (sub) gradient computation is delegated to (possibly multiple)
computation nodes (or, workers). At every iteration, the worker(s) receives
the current iterate $\mathbf{x}_{t}$ from the server, computes $\nabla
f(\mathbf{x}_{t})$, and communicates information about the computed
gradient(s) back to the server, which allows it to take a descent step in that
direction. This process is repeated till convergence.

Communication overhead is invariably the primary bottleneck in the scalability
of such distributed systems. When distributed optimization algorithms are
implemented over severely bit budget constrained environments, for instance in
wireless networks [4], the communication bandwidth of the channel (over which
the workers send information to the server) is an expensive resource, and is
often a pre-specified constraint beyond the algorithm designers’ control. In
this work, we resolve the question: How to design optimal quantization schemes
when the worker(s) is constrained to communicate its (sub) gradient
information to the server with a strict budget of $R$ bits per dimension?

When $f(\cdot)$ is $L$-smooth and $\mu$-strongly convex, it is possible to
achieve a linear convergence of the iterates $\mathbf{x}_{t}$ to
$\mathbf{x}_{f}^{*}$, and we consider the asymptotic minimax rate $C(R)$ given
as in [24] by

$C(R)\triangleq\inf_{\pi\in\Pi_{R}}\limsup_{T\to\infty}\sup_{f\in{\cal
F}_{\mu,L,D}}\left(\frac{\lVert\mathbf{x}_{T}(\pi)-\mathbf{x}_{f}^{*}\rVert_{2}}{D}\right)^{\frac{1}{T}}.$
(1)

Here, $\Pi_{R}$ denotes the set of all algorithms or optimization protocols
with access to an exact first order oracle for which information exchange
between the worker and server at every iteration is limited to $R$-bits per
dimension, ${\cal F}_{\mu,L,D}$ is the class of $L$-smooth and $\mu$-strongly
convex functions which satisfy $\lVert\mathbf{x}_{f}^{*}\rVert_{2}\leq D$
($D\geq 0$), and $\mathbf{x}_{T}(\pi)$ denotes the output of the protocol
$\pi\in\Pi_{R}$ after $T$ iterations. The minimax rate in (1) can be lower
bounded by $C(R)\geq\max\\{\sigma,2^{-R}\\}$, where
$\sigma=\frac{L-\mu}{L+\mu}$. On the other hand, when $f(\cdot)$ is a general
convex function not necessarily smooth, and we have access to a noisy
subgradient oracle [26], it is not possible to achieve a linear convergence.
In this case, we consider the minimax expected suboptimality gap given by

${\cal E}(T,R)\triangleq\inf_{\pi\in\Pi_{T,R}}\sup_{(f,{\cal O})}\hskip
2.84526pt\mathbb{E}f(\mathbf{x}(\pi))-f(\mathbf{x}^{*}),$ (2)

and study how it scales with the number of iterations $T$. Here, $\Pi_{T,R}$
denotes the set of all protocols with at most $T$ iterations, and a bit budget
of $R$-bits per dimension per iteration, $\mathbf{x}(\pi)$ is the output of
protocol $\pi$, and we consider the worst-case scenario over all objectives
$f:{\cal X}\to\mathbb{R}$ with compact, convex domain ${\cal
X}\subseteq\mathbb{R}^{n}$ satisfying $\sup_{\mathbf{x},\mathbf{y}\in{\cal
X}}\lVert\mathbf{x}-\mathbf{y}\rVert_{2}\leq D$, and stochastic subgradient
oracles ${\cal O}$ whose outputs are uniformly bounded by some parameter $B$.
When $R>1$, a lower bound on (2) is given in [26] by ${\cal
E}(T,R)\geq\frac{cDB}{\sqrt{T}}$ for some absolute constant $c$ independent of
$n,T$ and $R$.

A minimax optimal protocol (or algorithm) $\pi$ in either setting requires
designing an optimal vector quantizer. A source coding scheme is a pair of
mappings $({\mathsf{E}},{\mathsf{D}})$, where the encoding
${\mathsf{E}}:\mathbb{R}^{n}\to\\{0,1\\}^{nR}$ is done by the worker to
quantize the information it wants to send to the server. The decoding map
${\mathsf{D}}:\\{0,1\\}^{nR}\to\mathbb{R}^{n}$ recovers an estimate of the
input to the encoder and is implemented at the server. In this work, we
present Democratic Source Coding (DSC), an efficient polynomial-time fixed-
length vector quantization scheme, which when used with suitably designed
first-order optimization algorithms, can achieve the respective lower bounds
on the minimax rates (1) and (2) to within constant factors, establishing the
minimax optimality of the algorithms obtained.

###  1.1 Our Contributions

Our focus in this work is to consider algorithms that attain the information
theoretic lower bounds to the minimax performance metrics of bit budget
constrained optimization. Existing works [24, 26], have characterized the
precise lower bounds to (1), (2), and we provide optimal algorithms which
achieve these minimax lower bounds to within constant factors. Our
contributions are as follows:

  1. 1.

We first propose Democratic Source Coding (DSC) which makes use of Kashin
embeddings [25] to compress a vector in $\mathbb{R}^{n}$ subject to a
constraint of $R$ bits per dimension. DSC is a polynomial-time source coding
scheme and the error introduced by it is independent of the dimension $n$,
which is a crucial property for efficiently compressing high-dimensional
vectors.

  2. 2.

For smooth and strongly convex objectives, we propose DGD-DEF: Distributed
Gradient Descent with Democratically Encoded Feedback, a distributed
optimization algorithm that uses DSC to quantize the feedback-corrected
gradients and show that it attains the lower bound on (1).

  3. 3.

For general convex, non-smooth objectives, we propose DQ-PSGD: Democratically
Quantized Projected Stochastic subGradient Descent and show that it attains
the lower bound on (2).

  4. 4.

We further propose a relaxation of DSC, referred to as NDSC: Near Democratic
Source Coding, which is computationally simpler and achieves optimality to
within a mild logarithmic factor.

  5. 5.

Finally, we illustrate that DSC or NDSC consistently improve the performance
when used in conjunction with existing compression strategies like random
sparsification (§5 & Appendix I).

To the best of our knowledge, our proposed DGD-DEF and DQ-PSGD are the first
algorithms for their respective optimization settings to achieve the minimax
optimal rates under bit budget constraints (1), (2), while having a
computational complexity with polynomial dependence on dimension $n$.

###  1.2 Significance and Related work

Communication-Constrained Distributed Consensus and Optimization. A lot of
work has been done in recent years to address the communication bottleneck in
distributed optimization. Gradient quantization strategies like sign
quantization [8, 30], ternary quantization [35], standard dithering [5], vqSGD
[13] have proven to be very effective in designing consensus and optimization
algorithms which exchange finite precision information between worker(s) and
server or amongst workers. Variable-length coding schemes were proposed in [2,
33]. The bit-requirement of these quantization schemes are optimal in
expectation, but their worst-case performance is not. For our setting, when
precision constraints are imposed as a pre-specified bit budget which needs to
be strictly respected even for worst case inputs, it is preferred to design
fixed-length quantizers.

The problem of distributed optimization under bit budget constraints is
considered in [24, 26]. [24] considers smooth and strongly convex objectives,
and derive a lower bound on the minimax convergence rate defined in (1), along
with a matching upper bound. However, their upper bounding algorithm has
exponential complexity and hence, practically infeasible; whereas, our
proposed algorithm DGD-DEF, which uses DSC for quantization has polynomial
complexity and achieves the minimax lower bound to within constant factors.
For the setting of general convex and non-smooth objectives, [26] provides a
lower bound to the minimax suboptimality gap defined in (2). Using their
proposed quantizer RATQ, they also give an upper bound which characterizes the
minimum bit budget required to attain this minimax optimal lower bound to
within an iterated logarithmic factor in $d$. Compared to this, DQ-PSGD uses
$R+o_{n}(1)$ bits per dimension, and attains a suboptimality gap within
constant factors of the minimax lower bound. Here, $R$ is specified as a
constraint and is beyond the algorithm designer’s control and $o_{n}(1)$ is a
term that goes to zero as $n\to\infty$. A fixed length nearly optimal coding
scheme that employs random rotations was used in [1, 21, 33]. In our work, we
also propose a computationally simpler relaxation of DSC, namely NDSC that
achieves the minimax lower bounds to within a logarithmic factor $O(\sqrt{\log
n})$. We note that our proposed near-democratic embeddings boil down to random
rotations when square orthonormal transforms are used. When Hadamard
transforms are considered, these works assume that the dimension $n$ is such,
that a Hadamard matrix can be constructed. However, it might not necessarily
be true, and naive heuristics like partitioning the vector or zero-padding in
order to make the dimension equal to the nearest power of $2$ can be
suboptimal. NDSC performs better than random rotations in such cases. Another
popular strategy to reduce the communication requirement is gradient
sparsification [3, 6, 19, 31], which reduces the dimension of the vector being
exchanged. We note that our coding strategies, DSC and NDSC can be used in
conjunction with these sparsification methods.

Kashin Embeddings and Random Matrix Theory. Kashin embeddings were studied in
the random matrix theory literature [20, 25] for their relation to convex
geometry and vector quantization. From a high level perspective, Kashin
embedding of a vector $\mathbf{y}\in\mathbb{R}^{n}$, is a vector
$\mathbf{x}\in\mathbb{R}^{N}$ $(N>n)$, which has the property that the
components of $\mathbf{x}$ are similar to each other in magnitude, i.e. for
all $i\in[N]$, $|x_{i}|=\Theta(1/\sqrt{N})$. Even if components of
$\mathbf{y}$ may be arbitrarily varying in magnitude, democratic embeddings
have an effect of evenly distributing this variation across different
components of $\mathbf{x}$. Subsequently, applying lossy compression schemes
(eg. quantization) to the democratic embedding $\mathbf{x}$ instead of the
original vector $\mathbf{y}$ incurs less error. The embedding map
$\mathbb{R}^{n}\to\mathbb{R}^{N}$ is taken to be linear, i.e.
$\mathbf{y}=\mathbf{S}\mathbf{x}$ for some $\mathbf{S}\in\mathbb{R}^{n\times
N}$. Usually, $\mathbf{S}$ is randomly generated and the properties of the
democratic embeddings are very closely related to Restricted Isometry Property
(RIP) parameters of $\mathbf{S}$ [10]. We study different classes of random
matrices (subgaussian, orthonormal, and Hadamard) and their pros and cons of
using them for constructing respective DSC schemes. The efficacy of Kashin
embeddings for distributed mean estimation under joint privacy-communication
constraints was studied in [11]. [9, 29] use them for general stochastic
compressors. In our work, we go even further in using them for designing
general source coding schemes (both stochastic and deterministic) and show
that they yield minimax optimal optimization algorithms. Kashin embedding of a
vector is not unique, and [25] proposed an iterative-projection type algorithm
to compute a Kashin embedding. However, their algorithm requires explicit
knowledge of RIP parameters of $\mathbf{S}$, which is not readily available.
To this end, [32] introduced the notion of democratic embeddings (DE). DE of a
vector $\mathbf{y}\in\mathbb{R}^{n}$ is a Kashin embedding too, and is
obtained by solving a linear program. We propose a simple relaxation of this
linear program, and show that its solution yields a near-democratic embedding.

##  2 Democratic Embeddings

Consider a wide matrix $\mathbf{S}\in\mathbb{R}^{n\times N}$, where $n\leq N$.
For any given vector $\mathbf{y}\in\mathbb{R}^{n}$, the system of equations
$\mathbf{y}=\mathbf{S}\mathbf{x}$ is under-determined in
$\mathbf{x}\in\mathbb{R}^{N}$, with the set ${\cal
S}=\\{\mathbf{x}\in\mathbb{R}^{N}\hskip 2.84526pt|\hskip
2.84526pt\mathbf{y}=\mathbf{S}\mathbf{x}\\}$ as the solution space. The vector
$\mathbf{x}^{*}\in{\cal S}$ which has the minimum $\ell_{\infty}$-norm in this
solution space is referred to as the Democratic Embedding of $\mathbf{y}$ with
respect to $\mathbf{S}$. In other words, $\mathbf{x}^{*}$ is obtained by
solving,

$\mathop{\rm
min_{\cdot}}_{\mathbf{x}\in\mathbb{R}^{N}}\lVert\mathbf{x}\rVert_{\infty}\hskip
5.69054pt\text{subject to}\hskip 5.69054pt\mathbf{y}=\mathbf{S}\mathbf{x}.$
(3)

The constraint set ${\cal S}$ can be relaxed to a larger set ${\cal
S}^{\prime}=\\{\mathbf{x}\in\mathbb{R}^{n}\hskip 2.84526pt|\hskip
2.84526pt\lVert\mathbf{y}-\mathbf{S}\mathbf{x}\rVert_{2}\leq\epsilon\\}$ as in
[32]. In the rest of our work, we consider $\epsilon=0$, i.e. exact
representations. In order to characterize the solution of (3) (cf. Lemma 1),
we review certain definitions from [25, 32].

######  Definition 1.

(Frame) A matrix $\mathbf{S}\in\mathbb{R}^{n\times N}$ with $n\leq N$ is
called a frame if
$A\lVert\mathbf{y}\rVert_{2}^{2}\leq\lVert\mathbf{S}^{\top}\mathbf{y}\rVert_{2}^{2}\leq
B\lVert\mathbf{y}\rVert_{2}^{2}$ holds for any vector
$\mathbf{y}\in\mathbb{R}^{n}$ with $0<A\leq B<\infty$, where $A$ and $B$ are
called lower and upper frame bounds respectively.

######  Definition 2.

(Uncertainty principle (UP)) A frame $\mathbf{S}\in\mathbb{R}^{n\times N}$
satisfies the Uncertainty Principle with parameters $\eta,\delta$, with
$\eta>0,\delta\in(0,1)$ if
$\lVert\mathbf{S}\mathbf{x}\rVert_{2}\leq\eta\lVert\mathbf{x}\rVert_{2}$ holds
for all (sparse) vectors $\mathbf{x}\in\mathbb{R}^{N}$ satisfying
$\lVert\mathbf{x}\rVert_{0}\leq\delta N$, where $\lVert\mathbf{x}\rVert_{0}$
denotes the number of non-zero elements in $\mathbf{x}$.

######  Lemma 1.

[Democratic embeddings] [32] Let $\mathbf{S}\in\mathbb{R}^{n\times N}$ be a
frame with bounds $A,B$ (cf. Def. 1) that satisfies the uncertainty principle
(UP) (cf. Def. 2) with parameters $\eta,\delta$ such that $A>\eta\sqrt{B}$.
Then for any vector $\mathbf{y}\in\mathbb{R}^{n}$, the solution
$\mathbf{x}^{*}$ of (3) satisfies

$\frac{K_{l}}{\sqrt{N}}\lVert\mathbf{y}\rVert_{2}\leq\lVert\mathbf{x}^{*}\rVert_{\infty}\leq\frac{K_{u}}{\sqrt{N}}\lVert\mathbf{y}\rVert_{2}.$
(4)

where, $K_{l}=\frac{1}{\sqrt{B}}$ and
$K_{u}=\frac{\eta}{\left(A-\eta\sqrt{B}\right)\sqrt{\delta}}$ are called lower
and upper Kashin constants respectively.

We are primarily interested in Parseval frames ($A=B=1$), i.e. they satisfy
$\mathbf{S}\mathbf{S}^{\top}=\mathbf{I}_{n}$, where
$\mathbf{I}_{n}\in\mathbb{R}^{n\times n}$ is the identity matrix. This means
$K_{l}=1$ and $K_{u}=\eta(1-\eta)^{-1}\delta^{-1/2}$. Note that $K_{u}$
depends only on the choice of $\mathbf{S}$ and nothing else. Lemma 1 shows
that none of the coordinate values of the democratic embedding is too large,
and the information content of $\mathbf{y}$ is distributed evenly.

The value of upper Kashin constant $K_{u}$ depends on the choice of frame
construction $\mathbf{S}$, as well as its aspect ratio $\lambda=N/n$. [25, 32]
show that if $\mathbf{S}$ is a random orthonormal matrix, then
$K=K\left(\lambda\right)$, where $\lambda>1$ can be arbitrarily close to $1$.
Such frames can be obtained by generating a random $N\times N$ orthonormal
matrix, and randomly selecting $n$ of its rows. Since choosing $\lambda$ is
upto us, Lemma 1 implies that for random orthonormal frames, democratic
embeddings satisfy $\lVert\mathbf{x}\rVert_{\infty}=\Theta(1/\sqrt{N})$. As we
will see in §3, for large $n$ (or equivalently large $N$ since $N\geq n$),
this remarkably improves the robustness of our proposed compression schemes. A
comprehensive comparison of the properties of different choices for
$\mathbf{S}$ is given in Appendix A.

###  2.1 Near-Democratic Embeddings

Although the linear program (3) can be solved in polynomial time using
algorithms like simplex or Newton’s method, it can still be computationally
intensive. A simplified projected gradient descent type algorithm with
$O(n^{2})$ complexity was presented in [25]. However, implementing it requires
explicit knowledge of $\eta,\delta$ which is not readily available. We propose
a yet simpler relaxation of (3):

$\mathop{\rm
min_{\cdot}}_{\mathbf{x}\in\mathbb{R}^{N}}\lVert\mathbf{x}\rVert_{2}^{2}\hskip
5.69054pt\text{subject to}\hskip 5.69054pt\mathbf{y}=\mathbf{S}\mathbf{x}.$
(5)

The solution of the $\ell_{2}$-minimization (5) is easily available in closed
form (cf. Appendix B) as:

$\overline{\mathbf{x}}=\mathbf{S}^{\dagger}\mathbf{y}=\mathbf{S}^{\top}\left(\mathbf{S}\mathbf{S}^{\top}\right)^{-1}\mathbf{y}\in\mathbb{R}^{n}.$
(6)

where $(\cdot)^{\dagger}$ (defined as above) is the pseudo-inverse. For
Parseval frames $\mathbf{S}$, this boils down to
$\overline{\mathbf{x}}=\mathbf{S}^{\top}\mathbf{y}$. We refer to
$\overline{\mathbf{x}}=\mathbf{S}^{\dagger}\mathbf{y}$ as the Near-Democratic
embedding of $\mathbf{y}\in\mathbb{R}^{n}$ with respect to
$\mathbf{S}\in\mathbb{R}^{n\times N}$, and show that the solution
$\overline{\mathbf{x}}$ of (5) satisfies
$\lVert\overline{\mathbf{x}}\rVert_{\infty}=O((\sqrt{\log
N}/\sqrt{N})\lVert\mathbf{y}\rVert_{2})$. The additional $\sqrt{\log N}$
factor instead of the constant $K_{u}$ is a very modest price to pay compared
to the computational savings, even for dimensions as large as $N\sim 10^{6}$.
Note that as $\lambda$ approaches $1$, the solution space ${\cal S}$ of
$\eqref{eq:l_inf_minimization_problem}$ becomes smaller, and for $\lambda=1$,
the solutions of (3) and (5) coincide. Lemma 2 characterizes our result
explicitly. A random orthonormal matrix is obtained by generating random
Gaussian matrix $\mathbf{G}\in\mathbb{R}^{N\times N}$,
$\mathbf{G}_{ij}\sim{\cal N}(0,1)$, computing its singular-value decomposition
$\mathbf{Q}=\mathbf{U}\mathbf{\Sigma}\mathbf{V}^{\top}$, letting
$\widetilde{\mathbf{S}}=\mathbf{U}\mathbf{V}^{\top}$ and generating
$\mathbf{S}\in\mathbb{R}^{n\times N}$ by randomly selecting $n$ rows of
$\widetilde{\mathbf{S}}$, i.e. $\mathbf{S}=\mathbf{P}\widetilde{\mathbf{S}}$
where $\mathbf{P}\in\mathbb{R}^{n\times N}$ is a sampling matrix obtained by
randomly selecting $n$ rows of $\mathbf{I}_{N}$.

######  Lemma 2.

(Near-Democratic Embeddings with Random Orthonormal Frames) For a random
orthonormal frame $\mathbf{S}\in\mathbb{R}^{n\times N}$ generated as described
above, with probability at least $1-\frac{1}{2N}$, the solution of (5)
satisfies:

$\lVert\mathbf{x}\rVert_{\infty}\leq
2\sqrt{\frac{\lambda\log(2N)}{N}}\lVert\mathbf{y}\rVert_{2}.$ (7)

###### Proof.

Details in Appendix C. It utilizes the fact that each coordinate of
$\mathbf{S}^{\top}\mathbf{y}\in\mathbb{R}^{N}$ is isotropically distributed. A
subsequent concentration of measure argument, and a union bound gives the
result. ∎

Random orthonormal matrices prove quite beneficial in this regard.
Nevertheless, computing the near-democratic embeddings
$\overline{\mathbf{x}}=\mathbf{S}^{\top}\mathbf{y}$, for random orthonormal
frames requires $O\left(n^{2}\right)$ time, and moreover, even storing
$\mathbf{S}$, comprising of $32$-bit floating-point entries can be memory
intensive. To address this, we further propose a randomized Hadamard
construction for $\mathbf{S}$. Storing a randomized Hadamard matrix amounts to
only storing the signs, and near-democratic embeddings using such matrices can
be computed in near-linear time. Consider the $N\times N$ Hadamard matrix
$\mathbf{H}$ whose entries are normalized, i.e. $\mathbf{H}_{ij}=\pm
1/\sqrt{N}$, $\mathbf{H}=\mathbf{H}^{\top}$, and
$\mathbf{H}\mathbf{H}^{\top}=\mathbf{I}_{N}$. Let
$\mathbf{D}\in\mathbb{R}^{N\times N}$ be a diagonal matrix whose entries are
randomly chosen to be $\pm 1$ with equal probability. Let
$\mathbf{P}\in\mathbb{R}^{n\times N}$ be the sampling matrix as before. We
define our frame to be
$\mathbf{S}=\mathbf{P}\mathbf{D}\mathbf{H}\in\mathbb{R}^{n\times N}$. Note
that
$\mathbf{S}\mathbf{S}^{\top}=\mathbf{P}\mathbf{D}\mathbf{H}\mathbf{H}^{\top}\mathbf{D}\mathbf{P}^{\top}=\mathbf{P}\mathbf{D}^{2}\mathbf{P}^{\top}=\mathbf{P}\mathbf{P}^{\top}=\mathbf{I}_{n}$.
i.e., our randomized Hadamard construction is a Parseval frame. Storing the
$1$-bit signs is enough to store the matrix
$\mathbf{S}=\mathbf{P}\mathbf{D}\mathbf{H}$ in the memory. Furthermore, the
near-democratic embedding
$\overline{\mathbf{x}}=\mathbf{S}^{\top}\mathbf{y}=\mathbf{H}\mathbf{D}\mathbf{P}^{\top}\mathbf{y}$
can be computed with $O(n\log n)$ additions, since it does not require any
explicit floating-point multiplications as $\mathbf{S}_{ij}=\pm 1/\sqrt{N}$.
Lemma 3 characterizes the $\lVert\cdot\rVert_{\infty}$ of the solution of (5)
with $\mathbf{S}=\mathbf{P}\mathbf{D}\mathbf{H}$.

######  Lemma 3.

(Near-Democratic Embeddings with Randomized Hadamard Frames) For
$\mathbf{S}=\mathbf{P}\mathbf{D}\mathbf{H}\in\mathbb{R}^{n\times N}$, with
$\mathbf{P},\mathbf{D},\mathbf{H}$ defined as above, with probability at least
$1-\frac{1}{2N}$, the solution of (5) satisfies:

$\lVert\mathbf{x}\rVert_{\infty}\leq
2\sqrt{\frac{\log\left(2N\right)}{N}}\lVert\mathbf{y}\rVert_{2}.$ (8)

###### Proof.

Similar to the proof of Lemma 2, we upper bound the tail probability of each
coordinate of $\mathbf{S}^{\top}\mathbf{y}$ using a Chernoff-type argument,
followed by a union bound. Details in Appendix D. ∎

In §3, we employ our democratic and near-democratic embeddings for source
coding and show that they yield efficient (near) optimal quantizers.

##  3 Democratic Source Coding

Suppose the $\ell_{\infty}$-ball of radius $r$ centered at the origin of
$\mathbb{R}^{N}$ is denoted as ${\cal B}_{\infty}^{N}(r)$. Finite length
source coding schemes map its inputs to a discrete set of finite cardinality.
Consider the Rate-$R$ uniform scalar quantizer to be the mapping
${\mathsf{Q}}(\cdot):{\cal B}_{\infty}^{N}(1)\to S$ with
$S\subset\mathbb{R}^{N}$ and $|S|\leq 2^{\lfloor nR\rfloor}$. With a bit
budget of $R$-bits per dimension, the $M=2^{R}$ quantization points
$\\{v_{i}\\}_{i=1}^{M}$ along any dimension are given by
$v_{i}=-1+(2i-1)\Delta/2$, for $i=1,\ldots M$, where $\Delta=2/M$ is the
resolution. ${\mathsf{Q}}(\mathbf{x})$ for $\mathbf{x}\in{\cal
B}_{\infty}^{N}(1)$ is defined as:

${\mathsf{Q}}(\mathbf{x})=\left[x_{1}^{\prime},\ldots,x_{N}^{\prime}\right]^{\top};\hskip
5.69054ptx_{j}^{\prime}\triangleq\mathop{\rm arg\hskip
2.84526ptmin_{\cdot}}_{y\in\\{v_{1},\ldots,v_{M}\\}}|y-x_{j}|$ (9)

The maximum possible quantization error is then,

$d=\sup_{\mathbf{x}\in{\cal
B}_{\infty}^{N}(1)}\lVert\mathbf{x}-{\mathsf{Q}}(\mathbf{x})\rVert_{2}\leq\frac{\Delta}{2}\sqrt{N}$
(10)

###  3.1 Proposed Quantization Strategy

Given a frame $\mathbf{S}\in\mathbb{R}^{n\times N}$, for any
$\mathbf{y}\in\mathbb{R}^{n}$, denote its democratic and near-democratic
embeddings (i.e. the solutions of (3) and (5) respectively) by
$\mathbf{x}_{d}$ and $\mathbf{x}_{nd}$, both $\in\mathbb{R}^{N}$. The
democratic and near-democratic encoders are mappings
${\mathsf{E}}_{d}(\cdot),{\mathsf{E}}_{nd}(\cdot):\mathbb{R}^{n}\to
S\subset\mathbb{R}^{N}$, $|S|\leq 2^{\lfloor nR\rfloor}$ defined as:

${\mathsf{E}}_{d}(\mathbf{y})={\mathsf{Q}}\left(\frac{\mathbf{x}_{d}}{\lVert\mathbf{x}_{d}\rVert_{\infty}}\right),\hskip
2.84526pt{\mathsf{E}}_{nd}(\mathbf{y})={\mathsf{Q}}\left(\frac{\mathbf{x}_{nd}}{\lVert\mathbf{x}_{nd}\rVert_{\infty}}\right)$
(11)

${\mathsf{E}}_{d}(\cdot)$ and ${\mathsf{E}}_{nd}(\cdot)$ are quantized outputs
and sent over the channel from source (worker) to the destination (parameter
server). The corresponding decoder is the same for both, and is defined as the
mapping ${\mathsf{D}}(\cdot):S\to\mathbb{R}^{n}$,
${\mathsf{D}}(\mathbf{x}^{\prime})=\lVert\mathbf{x}\rVert_{\infty}\mathbf{S}\mathbf{x}^{\prime}$,
where $\mathbf{x}$ is either $\mathbf{x}_{d}$ or $\mathbf{x}_{nd}$, and
$\mathbf{x}^{\prime}={\mathsf{E}}_{d}(\mathbf{y})$ or
${\mathsf{E}}_{nd}(\mathbf{y})$. Normalization by
$\lVert\mathbf{x}\rVert_{\infty}$ is needed to ensure that the input to
${\mathsf{Q}}(\cdot)$ lies in ${\cal B}_{\infty}^{N}(1)$. In the following
Prop. 1 we show the independence/weak-logarithmic dependence of DSC and NDSC.
In Appendix J, we consider the situation when the scalar
$\lVert\cdot\rVert_{\infty}$ needs to be quantized and sent too.

######  Proposition 1.

(Quantization error of DSC and NDSC) Given $\mathbf{S}\in\mathbb{R}^{n\times
N}$ and a rate-$R$ uniform scalar quantizer ${\mathsf{Q}}(\cdot)$, for any
$\mathbf{y}\in\mathbb{R}^{n}$, let
${\mathsf{Q}}_{d}(\mathbf{y})={\mathsf{D}}\left({\mathsf{E}}_{d}(\mathbf{y})\right)$
and
${\mathsf{Q}}_{nd}(\mathbf{y})={\mathsf{D}}\left({\mathsf{E}}_{nd}(\mathbf{y})\right)$.
Then,

$\displaystyle\lVert\mathbf{y}-{\mathsf{Q}}_{d}\left(\mathbf{y}\right)\rVert_{2}\leq
2^{\left(1-\frac{R}{\lambda}\right)}K_{u}\lVert\mathbf{y}\rVert_{2}$ (12)
$\displaystyle\text{and},\hskip 5.69054pt$
$\displaystyle\lVert\mathbf{y}-{\mathsf{Q}}_{nd}\left(\mathbf{y}\right)\rVert_{2}\leq
2^{\left(2-\frac{R}{\lambda}\right)}\sqrt{\log(2N)}\lVert\mathbf{y}\rVert_{2}.$
(13)

The proof of Prop. 1 is a direct consequence of Lemmas 1, 2 and 3 and is
provided in Appendix E. In the above Prop. 1 we consider a randomized Hadamard
frame for near-democratic representation (i.e. Lemma 3). For random
orthonormal frames, a $\sqrt{\lambda\log(2N)}$ factor appears instead of
$\sqrt{\log(2N)}$. For $\lambda=1$, Prop. 1 holds for both classes of frames.
Choosing $\lambda=1$ is possible for random orthonormal frames, but not in the
case of Hadamard frames for which the dimension $N$ must be such that Hadamard
matrix can be constructed. [16] considers orthogonal transformations followed
by dithered quantization. Democratic and near-democratic embeddings provide a
unified way of looking at basis transforms for quantization, and can be
applied with any general compression scheme.

###  3.2 Optimal Covering Efficiency of Democratic Source Coding

The notion of covering efficiency is a measure of how close a fixed-length
quantizer is to being optimal. Quantizer efficiency is related to how
effectively a Euclidean ball of unit radius can be covered with a finite
number of smaller balls [12, 14, 36]. We review certain definitions to
precisely characterize this notion. Let ${\cal B}_{2}^{n}(a)$ denote the
Euclidean ball of radius $a$ centered at the origin. The dynamic range (r) of
a rate-$R$ quantizer ${\mathsf{Q}}:{\cal R}\to{\cal
R}^{\prime}\subset\mathbb{R}^{n}$, $|{\cal R}^{\prime}|\leq 2^{\lfloor
nR\rfloor}$ is defined to be the radius of the largest Euclidean ball which
fits inside the domain of ${\mathsf{Q}}$, i.e. $r\triangleq\sup\\{a\hskip
2.84526pt|\hskip 2.84526pt{\cal B}_{2}^{n}(a)\subseteq{\cal R}\\}$. The
covering radius of ${\mathsf{Q}}$ is defined as the maximum possible
quantization error when any $\mathbf{x}\in{\cal B}_{2}^{n}(r)$ is quantized to
its nearest neighbor, i.e. $d({\mathsf{Q}})\triangleq\inf\\{d>0\hskip
2.84526pt|\hskip 2.84526pt\forall\mathbf{x}\hskip 2.84526pt\in{\cal
B}_{2}^{n}(r),\lVert\mathbf{x}-{\mathsf{Q}}(\mathbf{x})\rVert_{2}\leq d\\}$.
The covering efficiency $\rho_{n}({\mathsf{Q}})$ of ${\mathsf{Q}}:{\cal
R}\to{\cal R}^{\prime}\subset\mathbb{R}^{n}$ is defined as:

$\rho_{n}({\mathsf{Q}})=\left(|{\cal R}^{\prime}|\frac{\text{vol}\left({\cal
B}_{2}^{n}(r)\right)}{\text{vol}\left({\cal
B}_{2}^{n}(d({\mathsf{Q}})\right)}\right)^{\frac{1}{n}}=|{\cal
R}^{\prime}|^{\frac{1}{n}}\frac{d({\mathsf{Q}})}{r}.$ (14)

If we consider Euclidean balls of radius $d({\mathsf{Q}})$ around each
quantization point, the total volume of these balls must cover ${\cal
B}_{2}^{n}(r)$. Covering efficiency formalizes how well this covering is, and
$\rho_{n}({\mathsf{Q}})\geq 1$ is a natural lower bound. [24] note that for
Roger’s quantizer [28], $\rho_{n}$ approaches $1$ as $n\to\infty$, and is
hence asymptotically optimal. However, it is practically infeasible for large
$n$ as it cannot be implemented in polynomial time. Popular quantization
schemes [2] use uniform scalar quantizers that have $\rho_{n}=\sqrt{n}$, which
grows significantly far away from the lower bound of $1$ for large $n$ and are
quite suboptimal. The following Lemma 4 quantifies the efficiency of our
proposed quantization scheme. Proof is a direct consequence of Prop. 1 and is
given in Appendix F.

######  Lemma 4.

(Covering Efficiency of (Near) Democratic Source Coding) For the (near)
democratic source coding schemes described in §3.1, with probability at least
$1-\frac{1}{2N}$, the covering efficiencies are given by

$\displaystyle\rho_{d}=2^{1+R\left(1-\frac{1}{\lambda}\right)}K_{u},\hskip
2.84526pt\text{and}\hskip
2.84526pt\rho_{nd}=2^{2+R\left(1-\frac{1}{\lambda}\right)}\sqrt{\log(2N)}$

where, $\lambda=N/n$ is the aspect ratio of the frame
$\mathbf{S}\in\mathbb{R}^{n\times N}$, and $K_{u}$ is its upper Kashin
constant.

Lemma 4 shows that when compared to vanilla scalar quantizers, DSC and NDSC
have remarkably better covering efficiency for large $n$, since it is either
dimension independent or has a weak logarithmic dependence. In the next
section, we will show that this gives us independence/weak-logarithmic
dependence on dimension for distributed optimization under bit-budget
constraints.

##  4 Proposed Optimization Algorithms

###  4.1 Smooth and Strongly Convex Objectives with Exact Gradient Oracle

Consider the class of $L$-smooth and $\mu$-strongly convex objective functions
which satisfy $\lVert\mathbf{x}_{f}^{*}\rVert\leq D$ for some known $D\geq 0$,
where $\mathbf{x}_{f}^{*}=\mathop{\rm arg\hskip
2.84526ptmin_{\cdot}}_{\mathbf{x}\in\mathbb{R}^{n}}f(\mathbf{x})$. For a
starting point $\widehat{\mathbf{x}}_{0}\in\mathbb{R}^{n}$ and step-size
$\alpha>0$, we consider $\Pi_{R}$ to be the class of Rate-$R$ Quantized
Gradient Descent (QGD) algorithms that iterate the descent rule
$\widehat{\mathbf{x}}_{t+1}\leftarrow\widehat{\mathbf{x}}_{t}-\alpha\mathbf{q}_{t}$,
where the descent direction $\mathbf{q}_{t}$ is a function of the computed
gradient [24]. Due to a bit budget constraint, $\mathbf{q}_{i}$ can only take
values from a finite set of cardinality $2^{\lfloor nR\rfloor}$. In order to
incorporate the effect of error-feedback to avoid noise accumulation, at each
iteration $t$, the functions
${\mathsf{z}}_{t}:\mathbb{R}^{n\otimes(t+1)}\to\mathbb{R}^{n}$, defined by
$\mathbf{z}_{t}={\mathsf{z}}_{t}\left(\widehat{\mathbf{x}}_{t},\mathbf{e}_{t-1}\,\ldots,\mathbf{e}_{0}\right)$,
and ${\mathsf{u}}_{t}:\mathbb{R}^{n\otimes(t+1)}\to\mathbb{R}^{n}$, defined by
$\mathbf{u}_{t}={\mathsf{u}}_{t}\left(\nabla
f(\mathbf{z}_{t}),\mathbf{e}_{t-1},\ldots,\mathbf{e}_{0}\right)$ determine the
gradient access point $\mathbf{z}_{t}$ and the quantizer input
$\mathbf{u}_{t}$ respectively. Here, $\\{\mathbf{e}_{j}\\}_{j=0}^{t-1}$ are
the past quantization errors. For all $\mathbf{x}\in\mathbb{R}^{n}$, the
functions ${\mathsf{z}}_{t},{\mathsf{u}}_{t}$ satisfy,
${\mathsf{z}}_{t}(\mathbf{x},\underbrace{\mathbf{0},\ldots,\mathbf{0}}_{t\hskip
2.84526pt\text{times}})=\mathbf{x}$, and
${\mathsf{u}}_{i}(\mathbf{x},\underbrace{\mathbf{0},\ldots,\mathbf{0}}_{t\hskip
2.84526pt\text{times}})=\mathbf{x}$.

######  Theorem 1.

(Lower bound, Thm. 4, [24]) For the class $\Pi_{R}$ of rate-$R$ QGD algorithms
as described above, the minimax rate over the function class ${\cal
F}_{\mu,L,D}$ defined in (1) is lower bounded by
$C(R)\geq\max\left\\{\sigma,2^{-R}\right\\}$, where
$\sigma\triangleq\frac{L-\mu}{L+\mu}$.

Here, $\sigma$ is the worst-case linear convergence rate of unquantized
gradient descent over the same function class [27]. $C(R)$ has a sharp
transition at a threshold rate $R_{*}=\log(1/\sigma)$. [24] shows that for
their proposed algorithm, using scalar quantizers yields a convergence rate of
$\leq\max\left\\{\sigma,\sqrt{n}2^{-R}\right\\}$. This upper bound means that
we require $R>\log(\sqrt{n}/\sigma)$ to achieve the convergence rate of
unquantized GD, which is far from the lower bound for large $n$. We propose
DGD-DEF: Distributed Gradient Descent with Democratically Encoded Feedback
(Algorithm 1) which resolves this issue. Here, ${\mathsf{E}}(\cdot)$ can be
either ${\mathsf{E}}_{d}$ or ${\mathsf{E}}_{nd}$. DGD-DEF is essentially a
modification of the algorithm in [24], with the quantization scheme replaced
by our coding scheme(s). Prop. 2 characterizes the convergence rate of DGD-
DEF. Its proof is similar to [24, Thm. 7] and is deferred to Appendix G.

######  Proposition 2.

(DGD-DEF convergence guarantee) For an objective $f\in{\cal F}_{\mu,L,D}$, a
bit budget of $R$-bits per dimension, with high probability, DGD-DEF (Alg. 1)
with step-size $\alpha\leq\alpha^{*}\triangleq\frac{2}{L+\mu}$, employing a
frame $\mathbf{S}\in\mathbb{R}^{n\times N}$ (with Kashin constant $K_{u}$) for
DSC or NDSC achieves

$\lVert\widehat{\mathbf{x}}_{T}-\mathbf{x}^{*}\rVert_{2}\leq\begin{cases}\max\left\\{\nu,\beta\right\\}^{T}\left(1+\beta\frac{\alpha
L}{|\beta-\nu|}\right)D,\hskip 2.84526pt\text{if}\hskip
2.84526pt\nu\neq\beta\\\ \nu^{T}\left(1+\alpha LT\right)D,\hskip
5.69054pt\text{otherwise},\end{cases}$

where, $\beta$ is the normalized error as in Prop. 1, i.e. $\beta\triangleq
2^{\left(1-R/\lambda\right)}K_{u}$ if ${\mathsf{E}}={\mathsf{E}}_{d}$, and
$\beta\triangleq 2^{\left(2-R/\lambda\right)}\sqrt{\log(2N)}$ if
${\mathsf{E}}={\mathsf{E}}_{nd}$, and
$\nu\triangleq\left(1-(\alpha^{*}L\mu)\alpha\right)^{1/2}$ is the convergence
rate of unquantized gradient descent with stepsize $\alpha$.

It is worthwhile to note that with $\alpha=\alpha^{*}$,
$\limsup_{T\to\infty}\sup_{f\in{\cal
F}_{\mu,L,D}}\left(\lVert\mathbf{x}_{T}-\mathbf{x}_{f}^{*}\rVert/D\right)^{1/T}=\max\left\\{\sigma,2^{-R}\beta\right\\}$.
For DSC, $\beta=O(1)$, which implies that DGD-DEF achieves the minimax optimal
lower bound of Thm. 1 to within constant factors, and since
$\beta=O(\sqrt{\log n})$ for NDSC, it is just a weak logarithmic factor away,
which is better than $\sqrt{n}$ scaling of vanilla scalar quantizers. In other
words, the threshold rate $R_{*}=\log\left(\beta/\sigma\right)$ is much less
than $\log\left(\sqrt{n}/\sigma\right)$ for large $n$. Furthermore, compared
to [24], which used Roger’s quantizer [28] that has exponential complexity,
the worst-case complexity of DGD-DEF is polynomial time with respect to
dimension, i.e. $O(n^{3})$ (for computing the democratic embeddings).

Algorithm 1 DGD-DEF

1:Initialize: $\widehat{\mathbf{x}}_{0}\leftarrow\mathbf{0}$ and
$\mathbf{e}_{-1}\leftarrow\mathbf{0}$

2:for $t=0$ to $T-1$ do

3: Worker:

4: $\mathbf{z}_{t}\leftarrow\widehat{\mathbf{x}}_{t}+\alpha\mathbf{e}_{t-1}$
(gradient access point)

5: $\mathbf{u}_{t}\leftarrow\nabla f(\mathbf{z}_{t})-\mathbf{e}_{t-1}$ (error
feedback)

6: $\mathbf{v}_{t}={\mathsf{E}}\left(\mathbf{u}_{t}\right)$ (source encoding)

7: $\mathbf{e}_{t}\leftarrow{\mathsf{D}}(\mathbf{v}_{t})-\mathbf{u}_{t}$
(error for next step)

8: Server:

9: $\mathbf{q}_{t}={\mathsf{D}}(\mathbf{v}_{t})$ (source decoding)

10:
$\widehat{\mathbf{x}}_{t+1}\leftarrow\widehat{\mathbf{x}}_{t}-\alpha\mathbf{q}_{t}$
(gradient descent step)

11:end for

Algorithm 2 DQ-PSGD

1:Initialize: $\widehat{\mathbf{x}}_{0}\in{\cal X}$, $\eta\in\mathbb{R}_{+}$
and $T$

2:for $t=0$ to $T-1$ do

3: Worker:

4: $\widehat{\mathbf{g}}_{t}=\widehat{\mathbf{g}}(\widehat{\mathbf{x}}_{t})$
(noisy subgradient)

5: $\mathbf{v}_{t}={\mathsf{E}}_{Dith}(\widehat{\mathbf{g}}_{t})$ (source
encoding)

6: Server:

7: $\mathbf{q}_{t}={\mathsf{D}}_{Dith}(\mathbf{v}_{t})$ (source decoding)

8:
$\underline{\widehat{\mathbf{x}}}_{t+1}\leftarrow\widehat{\mathbf{x}}_{t}-\eta\mathbf{q}_{t}$
(subgradient step)

9: $\widehat{\mathbf{x}}_{t+1}=\Gamma_{{\cal
X}}\left(\underline{\widehat{\mathbf{x}}}_{t+1}\right)$ (projection step)

10:end for

11:Output: $\mathbf{x}_{T}=\frac{1}{T}\sum_{t=1}^{T}\widehat{\mathbf{x}}_{t}$

###  4.2 General Convex and Non-Smooth Objectives with Stochastic Subgradient
Oracle

Consider $f$ to be convex, but not necessarily smooth. The stochastic
subgradient oracle output $\widehat{\mathbf{g}}(\mathbf{x})$ for any input
query $\mathbf{x}\in{\cal X}$ is assumed to be unbiased, i.e.
$\mathop{\mathbbm{E}{}}[\widehat{\mathbf{g}}(\mathbf{x})|\mathbf{x}]\in\partial
f(\mathbf{x})$, and uniformly bounded, i.e.
$\lVert\widehat{\mathbf{g}}(\mathbf{x})\rVert_{2}\leq B$. In this case, an
$\mathbf{R}$-bit quantizer is defined to be a set of (possibly randomized)
mappings $({\mathsf{Q}}^{e},{\mathsf{Q}}^{d})$ with the encoder
${\mathsf{Q}}^{e}:\mathbb{R}^{n}\to\\{0,1\\}^{nR}$ and the decoder
${\mathsf{Q}}^{d}:\\{0,1\\}^{nR}\to\mathbb{R}^{n}$. To design the source
coding scheme for a stochastic subgradient oracle, we consider the class of
gain-shape quantizers. For any vector input $\mathbf{y}\in\mathbb{R}^{n}$,
gain-shape quantizers are of the form
${\mathsf{Q}}(\mathbf{y})\triangleq{\mathsf{Q}}_{G}(\lVert\mathbf{y}\rVert_{2})\cdot{\mathsf{Q}}_{S}(\mathbf{y}/\lVert\mathbf{y}\rVert_{2})$,
where ${\mathsf{Q}}_{G}:\mathbb{R}\to\mathbb{R}$ and
${\mathsf{Q}}_{S}:\mathbb{R}^{n}\to\mathbb{R}^{n}$ quantize the magnitude and
shape separately, and multiply the estimates to obtain the quantized output.
We consider a uniformly dithered variant DSC which we denote as
$({\mathsf{E}}_{Dith},{\mathsf{D}}_{Dith})$ in Alg. 2 (cf. Appendix H for
detailed description of this quantizer design) for ${\mathsf{Q}}_{S}$, and
propose DQ-PSGD: Democratically Quantized Projected Stochastic subGradient
Descent (Algorithm 2). We use a dithered version of DSC instead of the nearest
neighbor scheme of §3 because for stochastic oracles, the performance metric
is the expected suboptimality gap. An unbiased quantizer enables us to attain
the optimal minimax rate even without error-feedback. Prop. 3 characterizes
the expected suboptimality gap of DQ-PSGD. Its proof is similar to [26,
Corollary 3.4] and is deferred to Appendix H.

######  Proposition 3.

(DQ-PSGD convergence guarantee) For any general objective $f$ with access to
the oracle ${\mathsf{Q}}\circ{\cal O}$ which outputs quantized noisy
subgradients ${\mathsf{Q}}(\widehat{\mathbf{g}}(\mathbf{x}))$, where
${\mathsf{Q}}$ employs DSC for the shape quantizer using a frame
$\mathbf{S}\in\mathbb{R}^{n\times N}$ with Kashin constant $K_{u}$, with high
probability, the worst case expected suboptimality gap of the output
$\mathbf{x}_{T}$ of DQ-PSGD after $T$ iterations is

$\sup_{(f,{\cal O})}\hskip
2.84526pt\mathbb{E}f(\mathbf{x}_{T})-f(\mathbf{x}^{*})\leq\frac{K_{u}DB}{\sqrt{T}}$
(15)

Prop. 3 shows that DQ-PSGD achieves the minimax lower bound [26, Theorem 2.3,
3.1], using only $R+o_{n}(1)$ bits per dimension. The additional $o_{n}(1)$
bits is for transmitting the scalar magnitude. A similar result with a weak
logarithmic dependence of the dimension $n$ can be derived for NDSC as well.
Compared to [26], DQ-PSGD attains the minimax optimal $O(1/\sqrt{T})$ rate
without additional logarithmic multiplicative factors in the bit budget
requirement.

In Appendix I (Prop. 4), we show that DSC and NDSC improve performance when
used in conjunction with existing general compression schemes, such as random
sparsification.

##  5 Numerical Simulations

We validate our theoretical claims with numerical simulations. Fig. 1(a) plots
the normalized compression errors i.e.
$\mathop{\mathbbm{E}{}}\left[\lVert{\mathsf{Q}}(\mathbf{y})-\mathbf{y}\rVert\right]_{2}/\lVert\mathbf{y}\rVert_{2}$
for different compression schemes with and without the presence of near-
democratic source coding. The vectors $\mathbf{y}\in\mathbb{R}^{1000}$ chosen
for compression are generated from a standard Gaussian distribution, and then
raised to the power of $3$ element-wise. $\text{Gaussian}^{3}$ distribution
has a heavier tail, and hence the entries of $\mathbf{y}$ have very different
magnitudes. Each point is obtained by averaging over $50$ realizations. In the
legend, SD denotes Standard Dithering [2], Top-K denotes Top-K sparsification
[3], and NDH, NDO are abbreviations for Near-Democratic Hadamard/Orthogonal,
specifying the type of randomized frame chosen for our coding scheme. Note
that for $n=1000$ dimensions, solving (3) to compute the democratic
representation using standard optimization packages like CVX [15] is
computationally demanding. Hence, we used [25]’s algorithm to compute Kashin
representations, which require explicit knowledge of UP parameters
$\eta,\delta$. For the two black plots labelled Kashin (with random
orthonormal frame), we choose $\lambda=1.5\text{ and }1.8$, which implies
availability of $R/\lambda$ bits per dimension to quantize. Due to the fixed
bit budget, the desired effect of even distribution of information in Kashin
representation, is offset by the poorer quantization resolution per
coordinate, which results in no net benefit (if not worse). For this reason,
in our near democratic representation with orthonormal frame, we choose
$\lambda=1$. We observe that in the presence of a fixed bit budget, $\lambda$
is desired to be as close to $1$ as possible, and for Hadamard frame, we let
$N=2^{\lceil\log_{2}n\rceil}=1024$.

(a) Comparison of different compression methods with and without near-
democratic encoding

(b) Variation of empirical convergence rate of DGD-DEF with bit budget per
dimension (R)

(c) Wall clock times for computing near-democratic vs. democratic
representations

(d) $\ell_{2}$-regularized least squares regression on MNIST dataset using
sparsified GD

Figure 1: Simulation results.

Fig. 1(b) compares the empirical convergence rate, defined as
$\left.\lVert\widehat{\mathbf{x}}_{T}-\mathbf{x}_{f}^{*}\rVert_{2}\middle/\lVert\widehat{\mathbf{x}}_{0}-\mathbf{x}_{f}^{*}\rVert_{2}\right.$
versus the bit budget constraint, i.e. $R$ bits per dimension, for solving the
least squares problem $\mathop{\rm
min_{\cdot}}_{\mathbf{x}\in\mathbb{R}^{n}}\frac{1}{2}\lVert\mathbf{y}-\mathbf{A}\mathbf{x}\rVert_{2}^{2}$,
where $n=116$, and the entries of $\mathbf{A}$ are drawn from
$\text{Gaussian}^{3}$ as before. If the algorithm does not converge, the
empirical rate is clipped at $1$. Unquantized GD has a constant rate equal to
$\frac{L-\mu}{L+\mu}$ [27]. DQGD proposed in [24] used a predefined sequence
of dynamic ranges, and nearest-neighbor scalar quantization. In comparison, we
normalize the input to the quantizer by $\lVert\cdot\rVert_{\infty}$ norm, and
since its a scalar quantity and assume that the scalar is transmitted with
infinite precision. A more comprehensive justification for sending scalars can
be found in Appendix J. We observe that with near-democratic quantization
performs at par with democratic quantization, and both ensure convergence at
very low bit budgets. Sometimes, it may even perform better because near-
democratic representations allow us to choose $N=n$, and hence as seen before,
no resolution is lost due to fixed bit budget. Even though near-democratic
coding performs at par with democratic coding the computational advantage of
the former is evident from Fig. 1(c) where we plot the wall-clock time (in
seconds) (averaged over 10 realizations) vs. dimension to find these
representations. The democratic embeddings are obtained by solving (3) using
CVX and, the near-democratic embeddings are obtained from the closed form
expression $\mathbf{x}=\mathbf{S}^{\top}\mathbf{y}$. Here, for each $n$, the
value of $N$ is chosen to be $N=2^{\lceil\log_{2}n\rceil}$. This plot was
obtained on a Dell Vostro with an Intel i5 1.60GHz processor running MATLAB
R2014b. Finally, in Fig. 1(d), we solve the $\ell_{2}$-regularized least
squares problem for the MNIST dataset [22]. We use gradient descent where the
gradients are compressed, first by random sparsification followed by an
aggressive $1$-bit quantization for the retained coordinates, so that
effectively $R=0.5$ bits are used per dimension. We note that near-democratic
embeddings using random orthonormal frames converge for $R=0.5$, whereas the
vanilla compression scheme fails.

##  6 Conclusions

In this work, we showed that democratic embeddings can yield minimax optimal
distributed optimization algorithms when employed in source coding schemes.
For smooth and strongly convex objectives, we proposed DGD-DEF, which employs
error feedback to achieve linear convergence. For the case of general convex
and non-smooth objectives, where the output of the stochastic subgradient
oracle is quantized using a democratic source coding scheme, projected
subgradient descent attains minimax optimal convergence rate. We note that
although DSC theoretically attains minimax optimal performance to within
constant factors, computing democratic embeddings can be computation and
memory intensive, for which we proposed a randomized Hadamard construction for
fast near-democratic embeddings. Finally, we demonstrate that for any
compression scheme, instead of directly compressing the input, computing the
(near) democratic representation and compressing that instead, invariably
improves performance. A potential limitation of the proposed optimization
approach is that the curvature information is not utilized, which we leave as
future work.

## References

  * Abdi and Fekri [2020] A. Abdi and F. Fekri.  Quantized compressive sampling of stochastic gradients for efficient communication in distributed deep learning.  In _Proceedings of the AAAI Conference on Artificial Intelligence_ , volume 34(04), pages 3105–3112, 2020.
  * Alistarh et al. [2017] D. Alistarh, D. Grubic, J. Li, R. Tomioka, and M. Vojnovic.  QSGD: Communication-efficient sgd via gradient quantization and encoding.  In _Advances in Neural Information Processing Systems_ , volume 30, pages 1709–1720. Curran Associates, Inc., 2017.
  * Alistarh et al. [2018] D. Alistarh, T. Hoefler, M. Johansson, N. Konstantinov, S. Khirirat, and C. Renggli.  The convergence of sparsified gradient methods.  In _Advances in Neural Information Processing Systems_ , volume 31. Curran Associates, Inc., 2018.
  * Amiri and Gündüz [2020] M. M. Amiri and D. Gündüz.  Machine learning at the wireless edge: Distributed stochastic gradient descent over-the-air.  _IEEE Transactions on Signal Processing_ , 68:2155–2169, 2020.
  * Aysal et al. [2008] T. C. Aysal, M. J. Coates, and M. G. Rabbat.  Distributed average consensus with dithered quantization.  _IEEE Transactions on Signal Processing_ , 56(10):4905–4918, 2008.
  * Barnes et al. [2020] L. P. Barnes, H. A. Inan, B. Isik, and A. Özgür.  rtop-k: A statistical estimation approach to distributed sgd.  _IEEE Journal on Selected Areas in Information Theory_ , 1(3):897–907, 2020.
  * Bekkerman et al. [2011] R. Bekkerman, M. Bilenko, and J. Langford.  _Scaling up Machine Learning: Parallel and Distributed Approaches_.  Cambridge University Press, USA, 2011.
  * Bernstein et al. [2018] J. Bernstein, Y.-X. Wang, K. Azizzadenesheli, and A. Anandkumar.  signSGD: Compressed optimisation for non-convex problems.  In _ICML_ , pages 559–568, 2018.
  * Caldas et al. [2019] S. Caldas, J. Konečny, H. B. McMahan, and A. Talwalkar.  Expanding the reach of federated learning by reducing client resource requirements, 2019.
  * Candes and Tao [2005] E. J. Candes and T. Tao.  Decoding by linear programming.  _IEEE Transactions on Information Theory_ , 51(12):4203–4215, 2005.
  * Chen et al. [2020] W.-N. Chen, P. Kairouz, and A. Ozgur.  Breaking the communication-privacy-accuracy trilemma.  In _Neural Information Processing Systems (NeurIPS) 2020_ , 2020.
  * Dumer [2016] I. Dumer.  Covering spheres with spheres.  _Discrete & Computational Geometry_, 38:665–679, 2016\.
  * Gandikota et al. [2021] V. Gandikota, D. Kane, R. Kumar Maity, and A. Mazumdar.  vqSGD: Vector quantized stochastic gradient descent.  In _Proceedings of The 24th International Conference on Artificial Intelligence and Statistics_ , volume 130 of _Proceedings of Machine Learning Research_ , pages 2197–2205. PMLR, 13–15 Apr 2021.
  * [14] A. Gersho and R. M. Gray.  _Vector Quantization and Signal Compression_.  Springer International.
  * Grant and Boyd [2014] M. Grant and S. Boyd.  CVX: Matlab software for disciplined convex programming, version 2.1.  http://cvxr.com/cvx, Mar. 2014.
  * Hadad and Erez [2016] R. Hadad and U. Erez.  Dithered quantization via orthogonal transformations.  _IEEE Transactions on Signal Processing_ , 64(22):5887–5900, 2016.  doi: 10.1109/TSP.2016.2599482.
  * [17] I. Haviv and O. Regev.  _The Restricted Isometry Property of Subsampled Fourier Matrices_ , pages 288–297.  doi: 10.1137/1.9781611974331.ch22.  URL https://epubs.siam.org/doi/abs/10.1137/1.9781611974331.ch22.
  * Kairouz and et al. [2019] P. Kairouz and et al.  Advances and open problems in federated learning, 2019.
  * Karimireddy et al. [2019] S. P. Karimireddy, Q. Rebjock, S. Stich, and M. Jaggi.  Error feedback fixes SignSGD and other gradient compression schemes.  In _Proceedings of the 36th International Conference on Machine Learning_ , volume 97 of _Proceedings of Machine Learning Research_ , pages 3252–3261. PMLR, 09–15 Jun 2019.
  * Kashin [1977] B. S. Kashin.  Diameters of some finite -dimensional sets and classes of smooth functions.  _Mathematics of the USSR-Izvestiya_ , 11(2):317–333, apr 1977.
  * Konečný et al. [2017] J. Konečný, H. B. McMahan, F. X. Yu, P. Richtárik, A. T. Suresh, and D. Bacon.  Federated learning: Strategies for improving communication efficiency, 2017.
  * LeCun et al. [1998] Y. LeCun, L. Bottou, Y. Bengio, and P. Haffner.  Gradient-based learning applied to document recognition.  http://yann.lecun.com/exdb/mnist/, 1998.
  * Li et al. [2014] M. Li, D. G. Andersen, J. W. Park, A. J. Smola, A. Ahmed, V. Josifovski, J. Long, E. J. Shekita, and B.-Y. Su.  Scaling distributed machine learning with the parameter server.  In _Proceedings of the 11th USENIX Conference on Operating Systems Design and Implementation_ , page 583–598, 2014.
  * Lin et al. [2020] C.-Y. Lin, V. Kostina, and B. Hassibi.  Achieving the fundamental convergence-communication tradeoff with differentially quantized gradient descent, 2020.
  * Lyubarskii and Vershynin [2010] Y. Lyubarskii and R. Vershynin.  Uncertainty principles and vector quantization.  _IEEE Trans. Inf. Theor._ , 56(7):3491–3501, 2010.
  * Mayekar and Tyagi [2020] P. Mayekar and H. Tyagi.  RATQ: A universal fixed-length quantizer for stochastic optimization.  In _Proceedings of the Twenty Third International Conference on Artificial Intelligence and Statistics_ , pages 1399–1409, 2020.
  * Nesterov [2014] Y. Nesterov.  _Introductory Lectures on Convex Optimization: A Basic Course_.  Springer Publishing Company, Incorporated, 1 edition, 2014.  ISBN 1461346916.
  * Rogers [1963] C. A. Rogers.  Covering a sphere with spheres.  _Mathematika_ , 10(2):157–164, 1963.
  * Safaryan et al. [2021] M. Safaryan, E. Shulgin, and P. Richtárik.  Uncertainty principle for communication compression in distributed and federated learning and the search for an optimal compressor, 2021.
  * Seide et al. [2014] F. Seide, H. Fu, J. Droppo, G. Li, and D. Yu.  1-bit stochastic gradient descent and application to data-parallel distributed training of speech dnns.  In _Interspeech 2014_ , September 2014.
  * Stich et al. [2018] S. U. Stich, J.-B. Cordonnier, and M. Jaggi.  Sparsified sgd with memory.  In _Proceedings of the 32nd International Conference on Neural Information Processing Systems_ , NIPS’18, page 4452–4463, Red Hook, NY, USA, 2018. Curran Associates Inc.
  * Studer et al. [2015] C. Studer, T. Goldstein, W. Yin, and R. G. Baraniuk.  Democratic representations, 2015.
  * Suresh et al. [2017] A. T. Suresh, F. X. Yu, S. Kumar, and H. B. McMahan.  Distributed mean estimation with limited communication.  In _Proceedings of the 34th International Conference on Machine Learning_ , volume 70 of _Proceedings of Machine Learning Research_ , pages 3329–3337. PMLR, 06–11 Aug 2017.
  * Wangni et al. [2018] J. Wangni, J. Wang, J. Liu, and T. Zhang.  Gradient sparsification for communication-efficient distributed optimization.  In _Advances in Neural Information Processing Systems_. Curran Associates, Inc., 2018.
  * Wen et al. [2017] W. Wen, C. Xu, F. Yan, C. Wu, Y. Wang, Y. Chen, and H. Li.  Terngrad: Ternary gradients to reduce communication in distributed deep learning.  In _Advances in Neural Information Processing Systems_ , volume 30, pages 1509–1519. Curran Associates, Inc., 2017.
  * Wyner [1967] A. D. Wyner.  Random packings and coverings of the unit n-sphere.  _The Bell System Technical Journal_ , 46(9):2111–2118, 1967.

##  Appendix A Comparison of Different Classes of Randomized Frames for
Computing Democratic Embeddings

The Uncertainty Principle (UP) for random matrices (Definition 2), is closely
related to the Restricted Isometry Property (RIP) for random matrices
introduced in [10].

######  Definition 3.

(Restricted Isometry Property (RIP)) A matrix
$\mathbf{S}\in\mathbb{R}^{n\times N}$ is said to satisfy the Restricted
Isometry Property of order $k$ with constant $\epsilon>0$, if for every
$k$-sparse vector $\mathbf{x}\in\mathbb{R}^{N}$ (i.e. a vector with at most
$k$ non-zeros entries), the following holds true:

$(1-\epsilon)\lVert\mathbf{x}\rVert_{2}^{2}\leq\lVert\mathbf{S}\mathbf{x}\rVert_{2}^{2}\leq(1+\epsilon)\lVert\mathbf{x}\rVert_{2}^{2}$
(16)

Comparing Definition 3 above with the definition of UP (Definition 2), it can
be seen that any matrix that satisfies RIP with parameters $(k,\epsilon)$,
satisfies UP with parameters $\left(\sqrt{1+\epsilon},\frac{k}{N}\right)$. In
other words, randomly constructed frames which satisfy the UP with high
probability, are strongly related to sensing matrices with small restricted
isometry constants.

Since the upper Kashin constant $K_{u}$ is given by
$K_{u}=\frac{\eta}{\left(A-\eta\sqrt{B}\right)\sqrt{\delta}}$, in order to
achieve embeddings having small $\ell_{\infty}$ norm, one is therefore
interested in finding frames satisfying the UP with small $\eta$ and large
$\delta$.

###  A.1 Sub-Gaussian Random Matrices

######  Definition 4.

(Sub-Gaussian random variable) A random variable $X$ is called sub-Gaussian
with parameter $\beta$ if

$\Pr\left[|X|>u\right]\leq\exp\left(1-\frac{u^{2}}{\beta^{2}}\right)\hskip
5.69054pt\text{for all}\hskip 5.69054ptu>0.$ (17)

From [25], we have the following result regarding the uncertainty principle
parameters of random sub-Gaussian matrices:

######  Theorem 2.

[25, Theorem 5]: (Uncertainty principle for sub-Gaussian matrices) Let the
entries of $\widetilde{\mathbf{S}}\in\mathbb{R}^{n\times N}$ be i.i.d. zero-
mean sub-Gaussian random variables with parameter $\beta$. Let $\lambda=N/n$
for some $\lambda\geq 2$. Then with probability at least $1-\lambda^{-n}$, the
random matrix $\mathbf{S}=\frac{1}{\sqrt{N}}\widetilde{\mathbf{S}}$ satisfies
the UP with parameters:

$\eta=C_{0}\beta\sqrt{\frac{\log\left(\lambda\right)}{\lambda}},\hskip
5.69054pt\text{and}\hskip 5.69054pt\delta=\frac{C_{1}}{\lambda},$ (18)

where, $C_{0},C_{1}>0$ are absolute constants.

Note: Random sub-Gaussian matrices are NOT tight frames. However, [25, Lemma
4.8] and [25, Corollary 4.9] show that $\mathbf{S}$ (as constructed above) is
an approximate Parseval frame with high probability, i.e. $\mathbf{S}$ has
frame bounds $A=1-\xi$ and $B=1+\xi$ for some small $\xi\in(0,1)$.
Substituting in the values to obtain the upper Kashin constant, we have,

$\displaystyle K_{u}=\frac{\eta}{\left(A-\eta\sqrt{B}\right)\sqrt{\delta}}$
$\displaystyle=C_{0}\beta\sqrt{\frac{\log(\lambda)}{\lambda}}\cdot\sqrt{\frac{\lambda}{C_{1}}}\cdot\frac{1}{1-\xi-\left(C_{0}\beta\sqrt{\frac{\log(\lambda)}{\lambda}}\right)\sqrt{1+\xi}}$
$\displaystyle=\frac{C_{0}\beta}{\sqrt{C_{1}}}\cdot\frac{\log(\lambda)}{1-\xi-\left(C_{0}\beta\sqrt{\frac{\log(\lambda)}{\lambda}}\right)\sqrt{1+\xi}}$
(19)

Note that the upper Kashin constant $K_{u}$ has a logarithmic dependence on
the aspect ratio of the frame, $\lambda$. Since $\lambda$ is essentially
treated as a constant, $K_{u}$ is a constant. However, the $32$-bit floating
point entries of a sub-Gaussian matrix need to be stored in the memory and
furthermore, multiplying the dense matrix $\mathbf{S}\in\mathbb{R}^{n\times
N}$ by a vector $\mathbf{x}\in\mathbb{R}^{N}$ can take up to a worst case of
$O\left(nN\right)$ time. Hence, choosing sub-Gaussian frames can be
intensively computation as well as memory demanding.

###  A.2 Random Orthonormal Matrices

Random orthonormal matrices refer to $n\times N$ matrices whose rows are
orthonormal. Such matrices can be obtained by randomly selecting the first $n$
rows of a randomly generated $N\times N$ orthonormal matrix. We state a result
from [25]. If ${\cal S}(N)$ denotes the space of all orthogonal $N\times N$
matrices with the normalized Haar measure, then ${\cal S}(n\times
N)=\left\\{\mathbf{P}_{n}\mathbf{V};\mathbf{V}\in{\cal S}(N)\right\\}$, where
$\mathbf{P}_{n}:\mathbb{R}^{N}\to\mathbb{R}^{n}$ is the orthogonal projection
on the first $n$ coordinates, denotes the space of all $n\times N$ orthonormal
matrices. The probability measure on ${\cal S}(n\times N)$ is induced by the
Haar measure on ${\cal S}(N)$.

######  Theorem 3.

[25, Theorem 4.1]: (UP for Random Orthonormal Matrices) Let $\mu>0$ and
$N=(1+\mu)n$. Then with probability at least $1-2\exp\left(-c\mu^{2}n\right)$,
a random orthonormal $n\times N$ matrix $\mathbf{S}$ satisfies the uncertainty
principle with parameters

$\eta=1-\frac{\mu}{4}\hskip 5.69054pt\text{and},\hskip
5.69054pt\delta=\frac{c\mu^{2}}{\log(1/\mu)}$ (20)

where $c>0$ is an absolute constant.

Note that random orthonormal matrices are Parseval frames, i.e. $A=B=1$. So,
the upper Kashin bound is given by:

$\displaystyle
K_{u}=\frac{1-\frac{\mu}{4}}{\mu/4}\cdot\frac{\sqrt{\log(1/\mu)}}{\mu\sqrt{c}}=\frac{4}{\mu^{2}\sqrt{c}}\left(1-\frac{\mu}{4}\right)\sqrt{\log\left(\frac{1}{\mu}\right)}$
(21)

This once again shows that $K_{u}$ is a constant.

###  A.3 Random Matrices with Fast Transforms

Matrices with fast transforms refer to structured matrices like Fourier
transform matrix, etc. for which fast algorithms exist to compute the forward
transform efficiently. To analyze the RIP properties of our proposed
randomized Hadamard matrix construction,
$\mathbf{S}=\mathbf{P}\mathbf{D}\mathbf{H}\in\mathbb{R}^{n\times N}$, we
recall the following theorem from [17].

######  Theorem 4.

[17, Theorem 4.5] For sufficiently large $N$ and $k$, a unitary matrix
$\mathbf{M}\in\mathbb{R}^{N\times N}$ with entries of absolute value
$O(1/\sqrt{N})$, and for sufficiently small $\epsilon>0$, the following holds:
For some $n=)\left(\log^{2}(1/\epsilon)\epsilon^{-2}\cdot
k\cdot\log^{2}\left(k/\epsilon\right)\cdot\log N\right)$, let
$\widetilde{\mathbf{S}}\in\mathbb{R}^{n\times N}$ be a matrix whose $n$ rows
are chosen uniformly at random and independently from the rows of
$\mathbf{M}$, multiplied by $\sqrt{N/n}$. Then, with probability
$1-2^{\Omega\left(\log N\cdot\log\left(k/\epsilon\right)\right)}$, the matrix
$\widetilde{\mathbf{S}}$ satisfies the restricted isometry property of order
$k$ with constant $\epsilon$.

The upper Kashin constant for such a matrix can be computed approximately as
follows:

$n=O\left(\log^{2}\left(\frac{1}{\epsilon}\right)\epsilon^{-2}k\log^{2}\left(\frac{k}{\epsilon}\right)\log
N\right)\implies
k\log^{2}\left(\frac{k}{\epsilon}\right)=\Omega\left(\frac{n}{\log^{2}(1/\epsilon)\epsilon^{-2}\log
N}\right).$ (22)

Furthermore, since the definition of UP requires
$\lVert\mathbf{S}\mathbf{x}\rVert_{2}\leq\eta\lVert\mathbf{x}\rVert_{2}$, it
is apparent that if we scale the entries of the matrix $\mathbf{S}$ by a
constant factor, the parameter $\eta$ of UP also scales by the same factor.
So, in Thm. 4, if we multiply the matrix $\widetilde{\mathbf{S}}$ by
$\sqrt{\frac{n}{N}}$ to negate the effect of multiplying by
$\sqrt{\frac{N}{n}}$ as in the statement of the theorem in order to get
$\mathbf{S}=\sqrt{\frac{n}{N}}\cdot\widetilde{\mathbf{S}}$, then the
corresponding UP parameters of $\mathbf{S}$ are:

$\eta=\sqrt{\frac{n}{N}\left(1+\epsilon\right)}\hskip
5.69054pt\text{and},\hskip 5.69054pt\delta=\frac{k}{N},$ (23)

where $k$ is dictated by (22).

$\displaystyle K_{u}$
$\displaystyle=\frac{\sqrt{\frac{n}{N}(1+\epsilon)}}{1-\sqrt{\frac{n}{N}(1+\epsilon)}}\cdot\sqrt{\frac{N}{k}}$
$\displaystyle=\frac{\sqrt{\frac{n}{N}(1+\epsilon)}}{1-\sqrt{\frac{n}{N}(1+\epsilon)}}\cdot\frac{\sqrt{N}\log\left(k/\epsilon\right)}{\sqrt{k\log^{2}\left(k/\epsilon\right)}}$
$\displaystyle=O\left(\frac{\sqrt{\frac{n}{N}(1+\epsilon)}}{1-\sqrt{\frac{n}{N}(1+\epsilon)}}\cdot\log\left(\frac{k}{\epsilon}\right)\cdot\sqrt{\frac{N}{n}}\cdot\log\left(\frac{1}{\epsilon}\right)\cdot\frac{1}{\epsilon}\cdot\sqrt{\log
N}\right)$
$\displaystyle=O\left(\frac{\sqrt{1+\epsilon}}{1-\sqrt{\frac{n}{N}(1+\epsilon)}}\cdot\log\left(\frac{k}{\epsilon}\right)\cdot\log\left(\frac{1}{\epsilon}\right)\cdot\sqrt{\log
N}\right)=O\left(\sqrt{\log N}\right).$ (24)

We see that our proposed randomized Hadamard construction
$\mathbf{S}=\mathbf{P}\mathbf{D}\mathbf{H}$, which provides computational and
memory savings, as seen in the main paper falls in this class of random
matrices with fast transforms. However, for such matrices, since $K_{u}$ is
not a constant and scales as $O\left(\sqrt{\log N}\right)$, when $n$ is large,
computing democratic embedding does not yield much benefit as compared to the
near-democratic embedding. From Lemma 3 of the main paper, the
$\ell_{\infty}$-norm of the near-democratic embedding
$\overline{\mathbf{x}}\in\mathbb{R}^{N}$ of $\mathbf{y}\in\mathbb{R}^{n}$ also
scales as
$\lVert\overline{\mathbf{x}}\rVert_{\infty}\leq\frac{O\left(\sqrt{\log
N}\right)}{\sqrt{N}}\lVert\mathbf{y}\rVert_{2}$.

In other words, for random matrices with fast transforms, asympotically (i.e.
for large $n$), near-democratic embeddings have $\ell_{\infty}$-norm as good
as democratic embeddings. However, unlike sub-Gaussian and random orthonormal
frames, since the entries of $\mathbf{S}=\mathbf{P}\mathbf{D}\mathbf{H}$ are
$\pm\frac{1}{\sqrt{N}}$, only the signs need to be stored (which amounts to
$1$-bit per entry, hence saving memory requirements), and
$\overline{\mathbf{x}}=\mathbf{S}^{\top}\mathbf{y}$ can effectively be
obtained in $O(n\log n)$ additions, which is much less computationally
demanding.

##  Appendix B Closed Form Expression for Near-Democratic Embeddings

For any $\mathbf{y}\in\mathbb{R}^{n}$, its near-democratic embedding
$\overline{\mathbf{x}}\in\mathbb{R}^{N}$ for $N\geq n$ with respect to a frame
$\mathbf{S}\in\mathbb{R}^{n\times N}$ is defined to be the solution of the
following $\ell_{2}$-norm minimization problem:

$\mathop{\rm
min_{\cdot}}_{\mathbf{x}\in\mathbb{R}^{N}}\lVert\mathbf{x}\rVert_{2}^{2}\hskip
5.69054pt\text{subject to}\hskip 5.69054pt\mathbf{y}=\mathbf{S}\mathbf{x}.$
(25)

The Lagrangian of the above problem is given by
$L(\mathbf{x},\mbox{\boldmath$\nu$})=\mathbf{x}^{\top}\mathbf{x}+\mbox{\boldmath$\nu$}^{\top}\left(\mathbf{S}\mathbf{x}-\mathbf{y}\right)$,
for $\mbox{\boldmath$\nu$}\in\mathbb{R}^{n}$ The Lagrange dual function is
then $g(\mbox{\boldmath$\nu$})=\mathop{\rm
min_{\cdot}}_{\mathbf{x}\in\mathbb{R}^{N}}L\left(\mathbf{x},\mbox{\boldmath$\nu$}\right)$,
i.e.

$\displaystyle\nabla_{\mathbf{x}}L(\mathbf{x},\mbox{\boldmath$\nu$})=2\mathbf{x}+\mathbf{S}^{\top}\mbox{\boldmath$\nu$}=0\implies\overline{\mathbf{x}}=-\frac{1}{2}\mathbf{S}^{\top}\mbox{\boldmath$\nu$}$
(26)

Substituting it in $\mathbf{y}=\mathbf{S}\mathbf{x}$ gives
$\mbox{\boldmath$\nu$}=-2\left(\mathbf{S}\mathbf{S}^{\top}\right)^{-1}\mathbf{y}$.
So,

$\overline{\mathbf{x}}=-\frac{1}{2}\mathbf{S}^{\top}\left(-2\left(\mathbf{S}\mathbf{S}^{\top}\right)^{-1}\mathbf{y}\right)=\mathbf{S}^{\top}\left(\mathbf{S}\mathbf{S}^{\top}\right)^{-1}\mathbf{y}=\mathbf{S}^{\top}\mathbf{y}.$
(27)

The last equality follows from the fact that we choose our frames
$\mathbf{S}\in\mathbb{R}^{n\times N}$ to be Parseval, i.e. they satisfy
$\mathbf{S}\mathbf{S}^{\top}=\mathbf{I}^{n\times n}$ . Random orthonormal
matrices, or our proposed construction
$\mathbf{S}=\mathbf{P}\mathbf{D}\mathbf{H}$ are Parseval frames, and hence
near-democratic representations can be computed in closed form very
efficiently.

##  Appendix C Proof of Lemma 2: Near-Democratic Embeddings with Random
Orthonormal Frames

Let $\\{\mathbf{s}_{i}\\}_{i=1}^{N}\in\mathbb{R}^{n}$ and
$\\{\widetilde{\mathbf{s}}_{i}\\}_{i=1}^{N}\in\mathbb{R}^{N}$ denote the
columns of $\mathbf{S}$ and $\widetilde{\mathbf{S}}$ respectively. Then for
any $1\leq i\leq N$,
$\lVert\mathbf{s}_{i}\rVert_{2}\leq\lVert\mathbf{P}\widetilde{\mathbf{s}}_{i}\rVert_{2}\leq\lVert\widetilde{\mathbf{s}}_{i}\rVert_{2}=1$.
The last inequality follows since
$\widetilde{\mathbf{S}}^{\top}\widetilde{\mathbf{S}}=\mathbf{I}_{N}$. For any
$\mathbf{y}\in\mathbb{R}^{n}$, let
$\widehat{\mathbf{y}}=\mathbf{y}/\lVert\mathbf{y}\rVert_{2}$. Then,

$\displaystyle\lVert\mathbf{S}^{\top}\mathbf{y}\rVert_{\infty}=\max_{1\leq
i\leq N}|\mathbf{s}_{i}^{\top}\mathbf{y}|$
$\displaystyle=\lVert\mathbf{y}\rVert_{2}\max_{1\leq i\leq
N}\lVert\mathbf{s}_{i}\rVert_{2}|\widehat{\mathbf{s}}_{i}^{\top}\widehat{\mathbf{y}}|$
$\displaystyle\leq\lVert\mathbf{y}\rVert_{2}\max_{1\leq i\leq
N}|\widehat{\mathbf{s}}_{i}^{\top}\widehat{\mathbf{y}}|$

where
$\widehat{\mathbf{s}}_{i}=\mathbf{s}_{i}/\lVert\mathbf{s}_{i}\rVert_{2}$. Note
that $\widehat{\mathbf{s}}_{i}\in\mathbb{R}^{n}$ is uniformly random on the
unit sphere in $\mathbb{R}^{n}$, i.e. $\widehat{\mathbf{s}}_{i}$ has identical
distribution as $\mathbf{g}/\lVert\mathbf{g}\rVert_{2}$ where
$\mathbf{g}\sim{\cal N}(\mathbf{0},\mathbf{I}_{n})$. Due to rotational
invariance of Gaussian distribution, for any fixed
$\widehat{\mathbf{y}}\in\mathbb{R}^{n}$ such that
$\lVert\widehat{\mathbf{y}}\rVert_{2}=1$,
$\widehat{\mathbf{s}}_{i}^{\top}\widehat{\mathbf{y}}_{i}$ has identical
distribution as $\widehat{\mathbf{s}}_{i}^{\top}\mathbf{e}_{1}$, where
$\mathbf{e}_{1}$ is the first ordinary basis vector. Let
$\widehat{\mathbf{s}}_{i}^{\top}\mathbf{e}_{1}=\mathbf{g}_{1}/\lVert\mathbf{g}\rVert_{2}=s_{1}$.
From concentration of measure for uniform distribution on the unit sphere (cf.
Supplementary),

$\mathop{\mathbbm{P}}\left[|\widehat{\mathbf{s}}_{i}^{\top}\widehat{\mathbf{y}}|\geq
t\right]=\mathop{\mathbbm{P}}\left[|s_{1}|\geq t\right]\leq 2e^{-nt^{2}/2}.$
(28)

With a subsequent application of union bound, we get
$\mathop{\mathbbm{P}}\left[\max_{1\leq i\leq
N}|\widehat{\mathbf{s}}_{i}^{\top}\widehat{\mathbf{y}}|\geq t\right]\leq
2Ne^{-nt^{2}/2}$. Choosing $t=2\sqrt{\frac{\log(2N)}{n}}$ yields

$\mathop{\mathbbm{P}}\left[\lVert\mathbf{S}^{\top}\mathbf{y}\rVert_{\infty}\geq
2\sqrt{\frac{\lambda\log(2N)}{N}}\lVert\mathbf{y}\rVert_{2}\right]\leq\frac{1}{2N},$

which completes the proof.

##  Appendix D Proof of Lemma 3: Near-Democratic Embeddings with Randomized
Hadamard Frames

Denote
$\mathbf{z}=\mathbf{P}^{\top}\mathbf{y}=[z_{1},\ldots,z_{N}]^{\top}\in\mathbb{R}^{N}$.
In order to study the effect of the transform $\mathbf{H}\mathbf{D}$, let
$\mathbf{u}=\mathbf{H}\mathbf{D}\mathbf{z}=[u_{1},\ldots,u_{N}]^{\top}$. Here,
$u_{j}$ is of the form $\sum_{i=1}^{N}a_{i}z_{i}$, with each
$a_{i}=\pm\frac{1}{\sqrt{N}}$ chosen uniformly and independently. So for any
$t\in\mathbb{R}$ and $\lambda>0$, a Chernoff-type argument gives:

$\displaystyle\mathop{\mathbbm{P}}[u_{j}>t]=\mathop{\mathbbm{P}}\left[e^{\lambda
u_{j}}>e^{\lambda t}\right]\leq e^{-\lambda
t}\prod_{i=1}^{N}\mathop{\mathbbm{E}{}}\left[e^{\lambda a_{i}z_{i}}\right].$
(29)

Now $\mathop{\mathbbm{E}{}}\left[e^{\lambda
a_{i}z_{i}}\right]=\frac{1}{2}e^{\frac{\lambda}{\sqrt{N}}z_{i}}+\frac{1}{2}e^{-\frac{\lambda}{\sqrt{N}}z_{i}}=\cosh\left(\frac{\lambda}{\sqrt{N}z_{i}}\right)\leq
e^{\lambda^{2}z_{i}^{2}/(2N)}$; the last inequality follows from a bound on
hyperbolic cosine. So, (29) becomes
$\mathop{\mathbbm{P}}\left[u_{j}>t\right]\leq
e^{\frac{\lambda^{2}}{2N}\lVert\mathbf{z}\rVert_{2}^{2}-\lambda t}$. Choosing
$\lambda=tN/\lVert\mathbf{z}\rVert_{2}^{2}$ gives the tightest bound
$\mathop{\mathbbm{P}}\left[u_{j}>t\right]\leq
e^{-t^{2}N/(2\lVert\mathbf{z}\rVert_{2}^{2})}$. Similarly, one can show that
$\mathop{\mathbbm{P}}\left[u_{j}<-t\right]\leq
e^{-t^{2}N/(2\lVert\mathbf{z}\rVert_{2}^{2})}$. Since
$\lVert\mathbf{u}\rVert_{\infty}=\max_{1\leq j\leq N,s\in\\{\pm 1\\}}su_{j}$,
an application of union bound gives

$\displaystyle\mathop{\mathbbm{P}}\left[\lVert\mathbf{H}\mathbf{D}\mathbf{z}\rVert_{\infty}>t\right]\leq
e^{-\frac{t^{2}N}{2\lVert\mathbf{z}\rVert_{2}^{2}}+\log(2N)}$ (30)

Setting $t=2\lVert\mathbf{z}\rVert_{2}\sqrt{\frac{\log(2N)}{N}}$ yields:

$\mathop{\mathbbm{P}}\left[\lVert\mathbf{H}\mathbf{D}\mathbf{z}\rVert_{\infty}\leq
2\lVert\mathbf{z}\rVert_{2}\sqrt{\frac{\log(2N)}{N}}\right]\geq
1-\frac{1}{2N}.$ (31)

$\mathbf{z}=\mathbf{P}^{\top}\mathbf{y}\implies\lVert\mathbf{z}\rVert_{2}=\lVert\mathbf{y}\rVert_{2}$,
completes the proof.

##  Appendix E Proof of Proposition 1: Quantization Error of DSC and NDSC

Let ${\mathsf{E}}$ denote either ${\mathsf{E}}_{d}$ or ${\mathsf{E}}_{nd}$.
Then, given an input $\mathbf{y}\in\mathbb{R}^{n}$ to ${\mathsf{E}}(\cdot)$,
$\mathbf{x}\in\mathbb{R}^{N}$ is the (near) democratic representation,
$\widetilde{\mathbf{x}}=\mathbf{x}/\lVert\mathbf{x}\rVert_{\infty}$ is the
normalized input to ${\mathsf{Q}}(\cdot)$,
$\mathbf{x}^{\prime}\in\mathbb{R}^{N}$ is the encoder output, and
$\mathbf{y}^{\prime}={\mathsf{D}}(\mathbf{x}^{\prime})\in\mathbb{R}^{n}$ is
the decoder output. So the error incurred after encoding and subsequent
decoding is:

$\displaystyle\lVert\mathbf{y}^{\prime}-\mathbf{y}\rVert_{2}\leq\lVert\mathbf{x}\rVert_{\infty}\lVert\mathbf{S}\left(\mathbf{x}^{\prime}-\widetilde{\mathbf{x}}\right)\rVert_{2}\leq\lVert\mathbf{x}\rVert_{\infty}\lVert\mathbf{x}^{\prime}-\widetilde{\mathbf{x}}\rVert_{2}$

The last inequality follows since
$\lVert\mathbf{S}\left(\mathbf{x}^{\prime}-\widetilde{\mathbf{x}}\right)\rVert_{2}\leq\lVert\mathbf{S}\rVert_{2}\lVert\mathbf{x}-\widetilde{\mathbf{x}}\rVert_{2}$.
Recalling that $\mathbf{S}$ is a Parseval frame, and that non-zero eigenvalues
of $\mathbf{S}^{\top}\mathbf{S}$ are the same as those of
$\mathbf{S}\mathbf{S}^{\top}=\mathbf{I}_{n}$, we have
$\lVert\mathbf{S}\rVert_{2}=1$. To upper bound the quantization error
$\lVert\mathbf{x}^{\prime}-\widetilde{\mathbf{x}}\rVert_{2}$, note that if we
originally had a total bit budget of $nR$-bits, the number of bits per
dimension to uniformly quantize $\widetilde{\mathbf{x}}\in\mathbb{R}^{N}$ is
now $nR/N$, i.e. $2^{nR/N}$ quantization points per dimension. From (10), we
have $\lVert\mathbf{x}^{\prime}-\widetilde{\mathbf{x}}\rVert_{2}\leq
2^{1-nR/N}\sqrt{N}$. So, if we use ${\mathsf{Q}}_{d}$ from Lemma 1, we have,

$\lVert\mathbf{y}^{\prime}-\mathbf{y}\rVert_{2}\leq\frac{K_{u}}{\sqrt{N}}\lVert\mathbf{y}\rVert_{2}2^{1-\frac{nR}{N}}\sqrt{N}=2^{\left(1-\frac{R}{\lambda}\right)}K_{u}\lVert\mathbf{y}\rVert_{2}.$

Similarly, for ${\mathsf{Q}}_{nd}$, using Prop. 3, we once again get,

$\lVert\mathbf{y}^{\prime}-\mathbf{y}\rVert_{2}\leq
2\sqrt{\frac{\log(2N)}{N}}\lVert\mathbf{y}\rVert_{2}2^{\left(1-\frac{nR}{N}\right)}\sqrt{N}.$

This completes the proof.

##  Appendix F Proof of Lemma 4: Covering efficiency of DSC and NDSC

Suppose the input to the encoders satisfy $\lVert\mathbf{y}\rVert_{2}\leq r$.
From Prop. 1, $\lVert\mathbf{y}-{\mathsf{Q}}_{d}(\mathbf{y})\rVert_{2}\leq
2^{\left(1-R/\lambda\right)}r$. Since a rate-$R$ quantizer has cardinality
$|{\cal R}^{\prime}|\leq 2^{nR}$, using (14),

$\rho_{d}=\left(2^{nR}\right)^{\frac{1}{n}}\frac{2^{(1-R/\lambda)}K_{u}r}{r}=2^{1+R\left(1-\frac{1}{\lambda}\right)}K_{u}.$
(32)

Similarly, the expression for $\rho_{nd}$ follows.

##  Appendix G Proof of Proposition 2: Convergence Rate of DGD-DEF

###  G.1 Preliminaries

For a rate-$R$ Quantized Gradient Descent (QGD) algorithm (as defined in [24]
as well as the main paper) that satisfies
${\mathsf{z}}_{i}(\mathbf{x},\underbrace{\mathbf{0},\ldots,\mathbf{0}}_{i\hskip
2.84526pt\text{times}})=\mathbf{x}$, and
${\mathsf{u}}_{i}(\mathbf{x},\underbrace{\mathbf{0},\ldots,\mathbf{0}}_{i\hskip
2.84526pt\text{times}})=\mathbf{x}$, where ${\mathsf{z}}_{i}$ and
${\mathsf{u}}_{i}$ are mappings to get the gradient access point
$\mathbf{z}_{i}$ and the quantizer input $\mathbf{u}_{i}$ respectively, the
minimax convergence rate (1) over the function class ${\cal F}_{\mu,L,D}$ is
lower bounded as $C(R)\geq\max\\{\sigma,2^{-R}\\}$, where
$\sigma\triangleq\frac{L-\mu}{L+\mu}$.

The convergence analysis of DGD-DEF essentially follows on the lines of [24,
Thm. 7], and consists of the following steps A critical observation is the
fact that the path of DGD-DEF satisfies a recursive invariant. Consider the
two descent trajectories: DGD-DEF and unquantized GD, with the same step size
$\alpha$, starting at the same location
$\widehat{\mathbf{x}}_{0}=\mathbf{x}_{0}$. Then, using triangle inequality, at
each iteration $i\in\mathbb{N}$ we have,

$\widehat{\mathbf{x}}_{t}=\mathbf{x}_{t}-\alpha\widehat{\mathbf{e}}_{t-1}\implies\lVert\widehat{\mathbf{x}}_{t}-\mathbf{x}^{*}\rVert_{2}\leq\lVert\mathbf{x}_{t}-\mathbf{x}^{*}\rVert_{2}+\alpha\lVert\widehat{\mathbf{e}}_{t-1}\rVert_{2}$
(33)

where, $\widehat{\mathbf{e}}_{-1}=\mathbf{0}$. From the algorithm pseudocode,
note that

$\mathbf{z}_{t}=\mathbf{x}_{t}$ (34)

i.e., DGD-DEF computes the gradient at the unquantized trajectory
$\\{\mathbf{x}_{t}\\}_{t=0}^{\infty}$. The convergence guarantee of
unquantized GD [27] states that:

$\lVert\mathbf{x}_{T}-\mathbf{x}^{*}\rVert_{2}\leq\nu^{T}\lVert\mathbf{x}_{0}-\mathbf{x}^{*}\rVert_{2}$
(35)

where, $\nu\triangleq(1-(\alpha^{*}L\mu)\alpha)^{1/2}$ is the convergence rate
for unquantized GD with step size $\alpha$. (35) controls the first term in
the recursion (33). An upper bound to the second term is obtained from our
quantization scheme. The following auxillary lemma will prove helpful for
upper bounding $\lVert\widehat{\mathbf{e}}_{t-1}\rVert_{2}$.

######  Lemma 5.

For any iteration $t=1,2,\ldots$ of DGD-DEF, we have
$\lVert\mathbf{u}_{t}\rVert_{2}\leq r_{t}$, where the sequence $\\{r_{t}\\}$
is given by

$r_{t}=LD\sum_{j=0}^{t}\nu^{j}\beta^{t-j}$

where, $L$ is the smoothness constant of the objective function $f$, $D$ is an
upper bound to the initial distance to optimal solution, i.e.
$\lVert\widehat{\mathbf{x}}_{0}-\mathbf{x}^{*}\rVert_{2}\leq D$, and
$\beta\triangleq 2^{(1-R/\lambda)}K_{u}$ is democratic embeddings are used,
and $\beta\triangleq 2^{(2-R/\lambda)}\sqrt{\log(2N)}$ if near-democratic
embeddings are used.

###### Proof.

This is proved using induction. For $t=0$, we have $\mathbf{u}_{0}=\nabla
f(\mathbf{x}_{0})-\mathbf{e}_{-1}$. Since $\mathbf{e}_{-1}=\mathbf{0}$,
recalling the facts that $\nabla f(\mathbf{x}^{*})=\mathbf{0}$ and $f$ is
$L$-smooth, we have,

$\displaystyle\lVert\mathbf{u}_{0}\rVert_{2}=\lVert\nabla
f(\mathbf{x}_{0})\rVert_{2}=\lVert\nabla f(\mathbf{x}_{0})-\nabla
f(\mathbf{x}^{*})\rVert_{2}\leq
L\lVert\mathbf{x}_{0}-\mathbf{x}^{*}\rVert_{2}\leq LD,$ (36)

and so the lemma holds true for $t=0$. To prove it for any general $t$, note
that from triangle inequality,

$\displaystyle\mathbf{u}_{t}=\nabla
f(\mathbf{x}_{t})-\mathbf{e}_{t-1}\implies\lVert\mathbf{u}_{t}\rVert_{2}\leq\lVert\nabla
f(\mathbf{x}_{t})\rVert_{2}+\lVert\mathbf{e}_{t-1}\rVert_{2}$ (37)

The first term can be upper bounded as

$\displaystyle\lVert\nabla f(\mathbf{x}_{t})\rVert_{2}=\lVert\nabla
f(\mathbf{x}_{t})-\nabla f(\mathbf{x}^{*})\rVert_{2}\leq
L\lVert\mathbf{x}_{t}-\mathbf{x}^{*}\rVert_{2}\leq
L\nu^{t}\lVert\mathbf{x}_{0}-\mathbf{x}^{*}\rVert_{2}\leq L\nu^{t}D$ (38)

The first inequality follows from $L$-smoothness of $f$ as before, while the
second inequality follows from the convergence guarantee of unquantized GD, as
given in (35). Furthermore,

$\displaystyle\lVert\mathbf{e}_{t-1}\rVert_{2}=\lVert\mathbf{u}_{t-1}-{\mathsf{D}}\left({\mathsf{E}}(\mathbf{u}_{t-1})\right)\rVert_{2}\leq\beta\lVert\mathbf{u}_{t-1}\rVert_{2}\leq\beta
LD\sum_{j=0}^{t-1}\nu^{j}\beta^{t-1-j}=LD\sum_{j=0}^{t-1}\nu^{j}\beta^{t-j},$
(39)

where $\beta$ depends on whether we choose democratic or near-democratic
embeddings for our source coding scheme, and the second inequality is the
induction hypothesis. So, using (38) and (39), we can further upper bound (37)
as,

$\displaystyle\lVert\mathbf{u}_{t}\rVert_{2}\leq
LD\left(\nu^{t}+\sum_{j=0}^{t-1}\nu^{j}\beta^{t-j}\right)=LD\sum_{j=0}^{t}\nu^{j}\beta^{t-j}.$
(40)

This completes the proof. ∎

###  G.2 Proof of Proposition 2

The proof of Prop. 2 is similar to the [24, Thm. 7] except for appropriate
modifications due to our proposed source coding schemes: DSC and NDSC. The
first term in the iteration invariant (33) can be upper bounded from the
descent guarantee of unquantized GD trajectory as,

$\lVert\mathbf{x}_{T}-\mathbf{x}^{*}\rVert_{2}\leq\nu^{T}\lVert\mathbf{x}_{0}-\mathbf{x}^{*}\rVert_{2}\leq\nu^{T}D.$
(41)

The second term in (33) can be upper bounded as,

$\lVert\mathbf{e}_{T-1}\rVert_{2}\leq\beta\lVert\mathbf{u}_{T-1}\rVert_{2}\leq\beta
r_{T-1}=\beta LD\sum_{j=0}^{T-1}\nu^{j}\beta^{T-1-j},$ (42)

where the inequalities follow from the definition of $\beta$, and Lemma 5. So
we have,

$\lVert\widehat{\mathbf{x}}_{T}-\mathbf{x}^{*}\rVert_{2}\leq bD,\hskip
5.69054pt\text{where}\hskip 5.69054ptb=\nu^{T}+\beta\alpha
L\sum_{j=0}^{T-1}\nu^{j}\beta^{T-1-j}.$ (43)

There are now three possibilities:

  1. 1.

$\nu>\beta$: The geometric sum is computed as,

$b=\nu^{T}+\beta\alpha
L\nu^{T-1}\frac{1-(\beta/\nu)^{T}}{1-\beta/\nu}\leq\nu^{T}\left(1+\beta\frac{\alpha
L}{\nu-\beta}\right).$ (44)

  2. 2.

$\nu=\beta$: In this case,

$b=\nu^{T}+\alpha L\nu\cdot\nu^{T-1}T=\nu^{T}\left(1+\alpha LT\right).$ (45)

  3. 3.

$\nu<\beta$: The case parallels the first case by interchanging the role of
$\nu$ and $\beta$, and we get,

$b=\nu^{T}+\beta\alpha
L\beta^{T-1}\sum_{j=0}^{T-1}\left(\frac{\nu}{\beta}\right)^{j}=\nu^{T}+\alpha
L\beta^{T}\frac{1-(\nu/\beta)^{T}}{1-\nu/\beta}\leq\beta^{T}\left(1+\beta\frac{\alpha
L}{\beta-\nu}\right).$ (46)

All the above three cases can be concisely expressed as,

$\lVert\widehat{\mathbf{x}}_{T}-\mathbf{x}^{*}\rVert_{2}\leq\begin{cases}\max\\{\nu,\beta\\}^{T}\left(1+\beta\frac{\alpha
L}{|\beta-\mbox{\boldmath$\nu$}|}\right)D,\hskip 5.69054pt\text{if}\hskip
2.84526pt\nu\neq\beta\\\ \nu^{T}\left(1+\alpha LT\right)D,\hskip
5.69054pt\text{otherwise}\end{cases}$ (47)

This completes the proof.

##  Appendix H Proof of Proposition 3: Convergence Rate of DQ-PSGD

Consider the optimization problem:

$\mathop{\rm min_{\cdot}}_{\mathbf{x}\in{\cal X}}f(\mathbf{x})$ (48)

where, ${\cal X}\subseteq\mathbb{R}^{n}$ is a convex set, and $f$ is convex,
but not necessarily smooth. The constraint set ${\cal X}$ is such that
$\sup_{\mathbf{x},\mathbf{y}\in{\cal
X}}\lVert\mathbf{x}-\mathbf{y}\rVert_{2}\leq D$ for some known $D\geq 0$.
Furthermore, we assume that we have oracle access to noisy subgradients of
$f$. We consider the oracle output $\widehat{\mathbf{g}}(\mathbf{x})$, for any
input query point $\mathbf{x}\in{\cal X}$, to be unbiased, i.e.
$\mathop{\mathbbm{E}{}}[\widehat{\mathbf{g}}(\mathbf{x})|\mathbf{x}]\in\partial
f(\mathbf{x})$, where, $\partial f(\mathbf{x})$ denotes the subdifferential of
$f$ at the point $\mathbf{x}$, and uniformly bounded, i.e.
$\lVert\widehat{\mathbf{g}}(\mathbf{x})\rVert_{2}\leq B$ for all $\mathbf{x}$,
for some $B>0$.

An $\mathbf{R}$-bit quantizer is defined to be a (possibly randomized) set of
mappings $({\mathsf{Q}}^{e},{\mathsf{Q}}^{d})$, with the encoder mapping
${\mathsf{Q}}^{e}:\mathbb{R}^{n}\to\\{0,1\\}^{nR}$ and the decoder mapping
${\mathsf{Q}}^{d}:\\{0,1\\}^{nR}\to\mathbb{R}^{n}$. Let ${\cal Q}_{R}$ denote
the set of all such $R$-bit quantizers. For any pair $(f,{\cal O})$ of
objective function $f$ and oracle ${\cal O}$, and an $R$-bit quantizer
${\mathsf{Q}}$, let ${\mathsf{Q}}\circ{\cal O}$ denote the composition oracle
that outputs ${\mathsf{Q}}(\widehat{\mathbf{g}}(\mathbf{x}))$ for each query
$\mathbf{x}\in{\cal X}$.

Let $\pi$ be an optimization protocol with at most $T$ iterations with oracle
access to ${\mathsf{Q}}\circ{\cal O}$, and let the set of all such
optimization protocols is denoted by $\Pi_{T}$. Then the minimax expected
suboptimality gap (2) can also be expressed as:

${\cal E}(T,R)\triangleq\inf_{\pi\in\Pi_{T}}\inf_{{\mathsf{Q}}\in{\cal
Q}_{R}}\sup_{(f,{\cal
O})}\mathop{\mathbbm{E}{}}f(\mathbf{x}(\pi))-\mathbf{x}_{f}^{*}$ (49)

Note that since we consider a constraint of $R$-bits per dimension, the total
number of bits used to quantize the subgradient oracle output is $nR$. In
other words, the total bit budget is $\Omega(n)$, and hence we are operating
in the high-precision regime as defined in [26].

The convergence rate of DQ-PSGD depends on the quantizer design of
${\mathsf{Q}}$, keeping in mind the but-budget constraint, i.e.
${\mathsf{Q}}\in{\cal Q}_{R}$. The performance of any quantizer is determined
by the following two quantities:

  1. 1.

Worst-case second moment defined as

$\alpha({\mathsf{Q}})\triangleq\sup_{\mathbf{y}\in\mathbb{R}^{n}:\lVert\mathbf{y}\rVert_{2}\leq
B}\sqrt{\mathop{\mathbbm{E}{}}[\lVert{\mathsf{Q}}(\mathbf{y})\rVert_{2}^{2}]}$
(50)

  2. 2.

Worst-case bias defined as

$\beta({\mathsf{Q}})\triangleq\sup_{\mathbf{y}\in\mathbb{R}^{n}:\lVert\mathbf{y}\rVert_{2}\leq
B}\lVert\mathop{\mathbbm{E}{}}[\mathbf{y}-{\mathsf{Q}}(\mathbf{y})]\rVert_{2}$
(51)

For any such quantizer ${\mathsf{Q}}$, from [26, Theorem 2.4], the worst-case
expected suboptimality gap of quantized projected subgradient descent
algorithm after $T$ iterations is given by:

$\sup_{(f,{\cal O})}\mathop{\mathbbm{E}{}}f(\mathbf{x})-f(\mathbf{x}^{*})\leq
D\left(\frac{\alpha({\mathsf{Q}})}{\sqrt{T}}+\beta({\mathsf{Q}})\right)$ (52)

where, the step-size $\eta$ is set to
$\frac{D}{\alpha({\mathsf{Q}})\sqrt{T}}$. In order to design ${\mathsf{Q}}$
appropriately, we consider the class of gain-shape quantizers. For any input
$\mathbf{y}\in\mathbb{R}^{n}$, gain-shape quantizers encode the magnitude (or
gain) of the input $\lVert\mathbf{y}\rVert_{2}$ and the direction (or shape)
$\mathbf{y}_{S}=\frac{\mathbf{y}}{\lVert\mathbf{y}\rVert_{2}}$ of $\mathbf{y}$
separately, and form the estimate of $\mathbf{y}$ by simply multiplying the
estimate for the magnitude and direction. In other words,

${\mathsf{Q}}(\mathbf{y})\triangleq{\mathsf{Q}}_{G}(\lVert\mathbf{y}\rVert_{2})\cdot{\mathsf{Q}}_{S}\left(\frac{\mathbf{y}}{\lVert\mathbf{y}\rVert_{2}}\right)$
(53)

where, ${\mathsf{Q}}_{G}:\mathbb{R}\to\mathbb{R}$, and
${\mathsf{Q}}_{S}:\mathbb{R}^{n}\to\mathbb{R}^{n}$. It is assumed that
${\mathsf{Q}}_{G}$ and ${\mathsf{Q}}_{S}$ are independent of each other, given
$\mathbf{y}$. From [26, Theorem 4.2], we know that if the shape quantizer
${\mathsf{Q}}_{S}$ is unbiased, i.e.
$\mathop{\mathbbm{E}{}}[{\mathsf{Q}}_{S}(\mathbf{y}_{S})]=\mathbf{y}_{S}$ for
all $\mathbf{y}_{S}$ such that $\lVert\mathbf{y}_{S}\rVert_{2}\leq 1$, then,

$\beta({\mathsf{Q}};B,n)\leq\sup_{\mathbf{y}\in\mathbb{R}^{n}:\lVert\mathbf{y}\rVert_{2}\leq
B}\mathbb{E}_{\mathbf{y}}\left[\left|\mathop{\mathbbm{E}{}}[{\mathsf{Q}}_{G}\left(\lVert\mathbf{y}\rVert_{2}\right)-\lVert\mathbf{y}\rVert_{2}|\mathbf{y}]\right|\right]$
(54)

The uniformly dithered gain quantizer for ${\mathsf{Q}}_{G}$ is defined as
follows. Let the dynamic range of ${\mathsf{Q}}_{G}$ be taken to be the known
uniform upper bound on the input to the magnitude of the inputs to
${\mathsf{Q}}$, i.e. the input to ${\mathsf{Q}}_{G}$ lies in $[0,B]$. Consider
$m$ quantization points $\\{u_{1},\ldots,u_{m}\\}$ uniformly spaced along the
interval $[0,B]$, and let $u_{0}=0$ and $u_{m+1}=B$. For any input
$v\in[u_{j},u_{j+1})\subseteq[0,B]$, the output of the gain quantizer
${\mathsf{Q}}(v)$ is defined to be:

${\mathsf{Q}}(v)=\begin{cases}u_{j}\hskip 17.07164pt\text{with
probability}\hskip 5.69054pt$r$\\\ u_{j+1}\hskip 5.69054pt\text{with
probability}\hskip 5.69054pt$1-r$\end{cases}$ (55)

where, $r\triangleq\frac{u_{j+1}-v}{(B/(m+1))}$. If fixed number of $b$ bits
(typically, $32$ bits) are allotted to the gain quantizer, $m=2^{b}$. Then, it
can be shown easily that ${\mathsf{Q}}_{G}$ is unbiased.

For designing the shape quantizer ${\mathsf{Q}}_{S}$, we employ the idea of
democratic embeddings. Let the input to ${\mathsf{Q}}_{S}$ be $\mathbf{y}$
such that $\lVert\mathbf{y}\rVert_{2}\leq 1$. For any given frame
$\mathbf{S}\in\mathbb{R}^{n\times N}$, suppose $\mathbf{x}_{d}$ denotes the
democratic embedding of $\mathbf{y}$ with respect to
$\mathbf{S}\in\mathbb{R}^{n\times N}$, i.e.

$\mathbf{x}_{d}\triangleq\mathop{\rm arg\hskip
2.84526ptmin_{\cdot}}_{\mathbf{x}\in\mathbb{R}^{N},\hskip
2.84526pt\mathbf{x}=\mathbf{S}\mathbf{y}}\lVert\mathbf{x}\rVert_{\infty}$ (56)

Then,
$\lVert\mathbf{x}_{d}\rVert_{\infty}\leq\frac{K_{u}}{\sqrt{N}}\lVert\mathbf{y}\rVert_{2}=\frac{K_{u}}{\sqrt{N}}$.
Let the coordinate-wise uniformly dithered quantizer (${\mathsf{Q}}_{CUQ}$) be
defined as in [26]. Essentially, we do dithered quantization (as described
above) of each coordinate of $\mathbf{x}_{d}$ independently, using $R$ bits
per dimension and a dynamic range of
$\left[-\frac{K_{u}}{\sqrt{N}},+\frac{K_{u}}{\sqrt{N}}\right]$. Then, the
final quantizer output is given by
${\mathsf{Q}}_{S}(\mathbf{y})=\mathbf{S}{\mathsf{Q}}_{CUQ}(\mathbf{x}_{d})$.
Since, we know that this co-ordinate wise uniformly dithered quantizer is
unbiased, it follows that the output of the shape quantizer is unbiased, i.e.

$\mathop{\mathbbm{E}{}}[{\mathsf{Q}}_{S}(\mathbf{y})]=\mathop{\mathbbm{E}{}}[\mathbf{S}{\mathsf{Q}}_{CUQ}(\mathbf{x}_{d})]=\mathbf{S}\mathop{\mathbbm{E}{}}[{\mathsf{Q}}_{CUQ}(\mathbf{x}_{d})]=\mathbf{S}\mathbf{x}_{d}=\mathbf{y}.$
(57)

Furthermore, since both the gain and shape quantizers are are conditionally
independent of each other, the bias of
${\mathsf{Q}}(\cdot)={\mathsf{Q}}_{G}(\cdot)\cdot{\mathsf{Q}}_{S}(\cdot)=0$.
That is, the worst-case bias is $\beta({\mathsf{Q}})=0$.

To evaluate the worst-case second moment of ${\mathsf{Q}}$, we once again
resort to [26, Theorem 4.2], which states that for a gain-shape quantizer,

$\alpha({\mathsf{Q}};B,n)\leq\alpha({\mathsf{Q}}_{G};B,1)\cdot\alpha({\mathsf{Q}}_{S};1,n).$
(58)

For the gain quantizer, if we choose the dynamic range to be $[0,B]$, the
worst-case bias is $\alpha({\mathsf{Q}}_{G};B,1)\leq B$. For the shape
quantizer, for any $\mathbf{y}$ such that $\lVert\mathbf{y}\rVert_{2}\leq 1$,
we have

$\displaystyle\lVert{\mathsf{Q}}_{S}(\mathbf{y})\rVert_{2}^{2}=\lVert\mathbf{S}{\mathsf{Q}}_{CUQ}(\mathbf{x}_{d})\rVert_{2}^{2}\leq\sigma_{max}^{2}(\mathbf{S})\cdot\lVert{\mathsf{Q}}_{CUQ}(\mathbf{x}_{d})\rVert_{2}^{2}\leq\lVert{\mathsf{Q}}_{CUQ}(\mathbf{x}_{d})\rVert_{2}^{2}$
(59)

The final inequality follows from the fact that for Parseval frames
$\mathbf{S}$ such that $\mathbf{S}\mathbf{S}^{\top}=\mathbf{I}_{n}$, the
maximum singular value $\sigma_{max}(\mathbf{S})=1$. Moreover, since
$\lVert\mathbf{x}_{d}\rVert_{\infty}\leq\frac{K_{u}}{\sqrt{N}}$, this implies,
$\lVert{\mathsf{Q}}_{CUQ}(\mathbf{x}_{d})\rVert_{2}^{2}\leq K_{u}^{2}$ for all
$\mathbf{y}$
$\implies\mathop{\mathbbm{E}{}}\lVert{\mathsf{Q}}_{CUQ}(\mathbf{x}_{d})\rVert_{2}\leq
K_{u}^{2}$. So, the worst-case second moment is
$\alpha({\mathsf{Q}})=\sqrt{\mathop{\mathbbm{E}{}}\lVert{\mathsf{Q}}_{S}(\mathbf{y})\rVert_{2}^{2}}\leq
BK_{u}$. Substituting these values for $\alpha({\mathsf{Q}})$ and
$\beta({\mathsf{Q}})$ in (52), we get the result. A similar result with a
$O(\sqrt{\log n})$ dependence of the dimension can be proved for NDSC.

##  Appendix I Extension to General Compression Schemes

We remark that given any general (possibly stochastic) lossy compression
scheme like sparsification, standard dithering, etc, instead of compressing
the input $\mathbf{y}\in\mathbb{R}^{n}$ directly, compressing its (near)
democratic embedding $\mathbf{x}\in\mathbb{R}^{N}$, will consistently improve
robustness by ensuring that the error due to compression has independent/weak-
logarithmic dependence on dimension $n$. Prop. 4 formally states our result.

######  Proposition 4.

For any unbiased compression operator ${\cal
C}:\mathbb{R}^{N}\to\mathbb{R}^{N}$, i.e. $\mathop{\mathbbm{E}{}}\left[{\cal
C}(\mathbf{x})\right]=\mathbf{x}$, that preserves sign and maximum magnitude,
i.e. $0\leq{\cal
C}(\mathbf{x})\text{sign}(\mathbf{x})\leq\lVert\mathbf{x}\rVert_{\infty}$ for
all $\mathbf{x}\in\mathbb{R}^{N}$, the (near) democratic source coding scheme
utilizing frame $\mathbf{S}\in\mathbb{R}^{n\times N}$ with corresponding
encoding and decoding functions defined for any $\mathbf{y}\in\mathbb{R}^{n}$
as ${\mathsf{E}}\left(\mathbf{y}\right)={\cal C}\left(\mathbf{x}\right)$ and
${\mathsf{D}}\left(\mathbf{x}\right)=\mathbf{S}\mathbf{x}$, satisfies:

$\mathop{\mathbbm{E}{}}[\lVert{\mathsf{D}}({\mathsf{E}}(\mathbf{y}))-\mathbf{y}\rVert_{2}^{2}]\leq\gamma^{2}\lVert\mathbf{y}\rVert_{2}^{2}$
(60)

where, $\gamma=K_{u}$ (upper Kashin constant of $\mathbf{S}$) if
$\mathbf{x}=\mathbf{x}_{d}$, and $\gamma=2\sqrt{\log(2N)}$ if
$\mathbf{x}=\mathbf{x}_{nd}$.

###### Proof.

For a given frame $\mathbf{S}\in\mathbb{R}^{n\times N}$, for any (possibly)
stochastic unbiased compression operator ${\cal
C}:\mathbb{R}^{N}\to\mathbb{R}^{N}$ that preserves sign and maximum magnitude,
from the unbiasedness of ${\cal C}$ and linearity of expectations, we have

$\displaystyle\mathop{\mathbbm{E}{}}\left[{\mathsf{D}}\left({\mathsf{E}}(\mathbf{y})\right)\right]=\mathop{\mathbbm{E}{}}\left[{\mathsf{D}}\left({\cal
C}(\mathbf{x})\right)\right]=\mathop{\mathbbm{E}{}}\left[\mathbf{S}{\cal
C}(\mathbf{x})\right]=\mathbf{S}\mathop{\mathbbm{E}{}}\left[{\cal
C}(\mathbf{x})\right]=\mathbf{S}\mathbf{x}=\mathbf{y}$ (61)

So, unbiasedness in preserved. Here, $\mathbf{x}$ can represent either the
democratic representation $\mathbf{x}_{d}$ or the near-democratic
representation $\mathbf{x}_{nd}$. Similar to Prop. 1, the approximation error
can be bounded uniformly (without the expectation) as follows,

$\displaystyle\lVert{\mathsf{D}}\left({\mathsf{E}}(\mathbf{y})\right)-\mathbf{y}\rVert_{2}^{2}=\lVert\mathbf{S}{\cal
C}(\mathbf{x})-\mathbf{S}\mathbf{x}\rVert_{2}^{2}$
$\displaystyle\leq\lVert{\cal C}(\mathbf{x})-\mathbf{x}\rVert_{2}^{2}$
$\displaystyle\leq N\cdot\max_{1\leq i\leq N}\left({\cal
C}(\mathbf{x})_{i}-\mathbf{x}_{i}\right)^{2}\leq
N\cdot\lVert\mathbf{x}\rVert_{\infty}^{2}$ (62)

Here once again, the first inequality follows from the fact that
$\lVert\mathbf{S}\rVert_{2}=1$. If $\mathbf{x}=\mathbf{x}_{d}$, then from
Lemma 1,
$\lVert\mathbf{x}\rVert_{\infty}\leq\frac{K_{u}}{\sqrt{N}}\lVert\mathbf{y}\rVert_{2}$.
Substituting this in (I), we get the result for democratic representations
with $\gamma=K_{u}$. Similarly, if $\mathbf{x}=\mathbf{x}_{nd}$, using Lemmas
3, $\lVert\mathbf{x}\rVert_{\infty}\leq
2\sqrt{\frac{\log(2N)}{N}}\lVert\mathbf{y}\rVert_{2}$. Substituting this once
again in (I), we get the result for near-democratic representations with
$\gamma=2\sqrt{\log(2N)}$. This completes the proof. ∎

##  Appendix J Quantizing the $\ell_{\infty}$ norm

For simplicity of exposition, the statement of Prop. 2 assumes that the
$\ell_{\infty}$ norm of the input to the quantizer can be transmitted
perfectly without lossy quantization. The situation does not change much if we
allot a finite number of bits to quantize $\lVert\mathbf{x}\rVert_{\infty}$ as
well.

If we use a constant number $O(1)$ of bits (typically, $32$ bits depending on
the machine precision), then the total number of bits required to quantize the
vector is $nR+O(1)$. This means that the number of bits per dimension is
$R+\frac{O(1)}{n}\to R$ as $n\to\infty$. Hence, the bit budget is respected
asymptotically and the additional constant number of bits is negligible when
high dimensional problems are considered.

To take account the quantization error due to
$\lVert\mathbf{x}\rVert_{\infty}$ quantization, we use the notion of gain-
shape quantizers for DGD-DEF too. Note that if
$\mathbf{y}_{S}=\frac{\mathbf{y}}{\lVert\mathbf{y}\rVert_{\infty}}$,

$\displaystyle\lVert{\mathsf{Q}}(\mathbf{y})-\mathbf{y}\rVert_{2}$
$\displaystyle=\lVert{\mathsf{Q}}_{G}(\lVert\mathbf{y}\rVert_{\infty}){\mathsf{Q}}_{S}\left(\mathbf{y}_{S}\right)-\lVert\mathbf{y}\rVert_{\infty}\mathbf{y}_{S}\rVert_{2}$
$\displaystyle=\left\lVert\left(\lVert\mathbf{y}\rVert_{\infty}+\epsilon\right){\mathsf{Q}}_{S}(\mathbf{y}_{S})-\lVert\mathbf{y}\rVert_{\infty}\mathbf{y}_{S}\right\rVert_{2}$
$\displaystyle\leq\lVert\mathbf{y}\rVert_{\infty}\lVert{\mathsf{Q}}_{S}(\mathbf{y}_{S})-\mathbf{y}_{S}\rVert_{2}+\epsilon\lVert{\mathsf{Q}}_{S}(\mathbf{y}_{S})\rVert_{2}$
(63)

The last inequality follows from triangle inequality. Since we employ DSC for
the shape quantizer, the first term can be upper bounded using Prop. 1. The
second term can be upper bounded as:

$\displaystyle\epsilon\lVert{\mathsf{Q}}_{S}(\mathbf{y}_{S})\rVert_{2}\leq\epsilon\sqrt{N}\lVert{\mathsf{Q}}(\mathbf{y}_{S})\rVert_{\infty}\leq\epsilon\sqrt{N}\frac{K_{u}}{\sqrt{N}}\leq\epsilon
K_{u}$ (64)

which is an additional constant error. The whole convergence analysis follows
through with this constant additive error too.

##  Appendix K Simulations: General Convex and Non-Smooth Objectives

We consider training a support vector machine where the subgradients are
quantized using $R$-bits per dimension. Suppose the worker has $m$ datapoints
$(\mathbf{a}_{i},b_{i})\in\mathbb{R}^{n}\times\\{-1,+1\\}$ for $i=1,\ldots,m$.
We want to solve the following optimization problem in which our aim is to
minimize the hinge loss,

$\mathop{\rm
min_{\cdot}}_{\mathbf{x}\in\mathbb{R}^{n}}\frac{1}{m}\sum_{i=1}^{m}\max\left(0,1-b_{i}\cdot\mathbf{x}^{\top}\mathbf{a}_{i}\right)$
(65)

The worker evaluates the subgradient at every iteration and sends it to the
server using only $R$-bits per dimension. We compare the performance of our
proposed DQ-PSGD algorithm with naive scalar quantization as well as
unquantized projected stochastic subgradient descent. The stochasticity in the
subgradient oracle evaluation arises from randomly subsampling the dataset to
compute the subgradient at every iteration. We consider the number of
datapoints $m=100$, and dimension of the problem $n=30$. For Figs. 2(a) and
2(b), the data corresponding to each class is generated independently from
Gaussian distributions with different means. We consider random orthonormal
frames for computing the near-democratic embeddings.

(a) Suboptimality gap

(b) Classification error

Figure 2: Support Vector Machine for Gaussian data

(a) Objective function value

(b) Test classification error

Figure 3: Support Vector Machine for MNIST data

Fig 2(a) plots the suboptimality gap (averaged over $10$ different
realizations) versus the number of iterations. The optimal value $f_{*}$ for
computing the suboptimality gap in Fig. 2(a) is obtained by solving (65) using
interior point solver provided by CVX [15]. We consider the number of bits per
dimension to be $R=0.5$, i.e. less than one bit per dimension. This
essentially means that some coordinates of the subgradient get zero bits,
while some of them get one bit for scalar quantization. In other words, since
we only have a total of $nR=15$ bits available, the subgradient is randomly
sparsified by making certain coordinates zero, and the remaining vector is
quantized using $1$-bit per dimension. The red plot corresponds to doing this
naively, i.e. randomly sparsifying $50\%$ of the coordinates and quantizing
the rest of the coordinates uniformly using 1 bit each, which gives a very
poor performance. Compared to that, the yellow curve, which computes the near-
democratic embedding (using a random orthonormal frame) followed by randomly
sparsifying $50\%$ of the coordinates and doing scalar quantization of the
retained coordinates, has a relatively better performance, and is closer to
the blue curve, which corresponds to unquantized subgradient descent (i.e.
without any bit budget).

We also consider top-K sparsification [31] with and without near-democratic
embeddings (green and purple curves). For top-K sparsification, we choose
$K=3$, i.e. we decide to retain only the top $10\%$ of the coordinates. Both
the curves have similar performance which we attribute to the fact that the
top $10\%$ coordinates are of similar magnitude, which is why quantizing the
near-democratic embedding does not yield any improvement in performance.
However, it is worthwhile to note that top-K does not perform better than
Near-democratic embedding + Random sparsification. This is because we ensure
that for all the curves (except blue), the total bit-budget is constant, i.e.
we have a total of $nR=15$ bits to quantize the gradient which
$\in\mathbb{R}^{30}$. When we employ both sparsification and quantization
techniques simultaneously to compress the gradient, but only have a fixed
total number of bits available, there arises a tradeoff between how many
coordinates we want to retain and the number of bits allotted for quantizing
each retained coordinates. Smaller $K$ means more bits per coordinate i.e.
better resolution for scalar quantization of the retained coordinates, and
vice versa. For instance, in random sparsification, we retain $15$
coordinates, with $1$-bit allotted for each. For top-K, we retain $3$
coordinates and allot $5$ bits for quantizing each of them. Although top-K
sparsification is expected to perform better than random sparsification, the
parameter $K$ is often chosen heuristically and a wrong choice of $K$ may
yield poorer performance (despite the additional computation required for
determining the top K coordinates) as in this case. We also plot the
classification error, that is the percentage of misclassified samples in the
training set at every iteration in Fig. 2(b) and observe a similar trend for
the different sparsification and quantization schemes.

Figs. 3(a) and 3(b) consider the MNIST dataset [22], and the problem of
training a support vector machine to distinguish the digit $0$ from digit $1$.
Fig. 3(a) shows how the objective function value decreases with the number of
iterations. Fig. 3(b) plots the classification error on the hold-out test set
for each iteration. We consider only $1$ realization for this setting and we
let the bit-budget constraint to be $R=0.1$ bits per dimension. For top-K
sparsification, we once again retain the top $10\%$ coordinates, while
ensuring that the total bit budget remains same for all the schemes, that is a
total of $\lfloor nR\rfloor=\lfloor 784\times 0.1\rfloor=78$ bits. For yellow
and red curves which consider random sparsification with and without near-
democratic embeddings respectively, $78$ coordinates are chosen randomly from
the gradient which $\in\mathbb{R}^{784}$ and $1$ bit is allotted to each of
them. For top-$10\%$ sparsification, we now choose to retain the top $78$
coordinates of maximum magnitude, allot $1$ bit to quantize each of them, and
make the rest zero. Since the number of retained coordinates is the same for
both random and top-K sparsification in this setting i.e. $78$, top-K performs
better as expected.

##  Appendix L Comparison with other Quantization/Sparsification schemes

In this section, we compare our work with some more existing quantization and
sparsification schemes from the literature. They are succinctly summarized in
Table 1. We characterize each compression scheme by its bit requirement and
the normalized error. For any input vector $\mathbf{x}\in\mathbb{R}^{n}$, if
the output of a compression scheme is denoted as ${\cal C}(\mathbf{x})$, then
the normalized error is defined to be $\lVert{\cal
C}(\mathbf{x})-\mathbf{x}\rVert_{2}$. For simplicity, we assume inputs satisfy
$\lVert\mathbf{x}\rVert_{2}=1$.

Compression Scheme | No. of Bits | Error
---|---|---
Sign quantization [8, 19] | $O(n)$ | $O(\sqrt{n})$
QSGD (Standard Dithering) [2] | $O(s(s+\sqrt{n}))$ | $\min\left\\{\frac{\sqrt{n}}{s},\frac{n}{s^{2}}\right\\}$
Ternary quantization [35] | $O(n)$ | $O(\sqrt{n})$
vqSGD-Gaussian [13] | $O\left(c\right),c>\log n$ | $O\left(\frac{n}{c}\right)$
vqSGD-Cross Polytope [13] | $O\left(\log n\right)$ | $O\left(n\right)$
Top-$k$ sparsification [31] | $O\left(k+\log_{2}\binom{n}{k}\right)$ | $\frac{n-k}{n}$
Random sparsification [34] | $O\left(k+\log_{2}\binom{n}{k}\right)$ | $O\left(\frac{n}{k}\right)$
Democratic source coding (Ours) | $nR+O(1)$ | $O\left(2^{-R/\lambda}\right)$
Table 1: Comparison of various compression schemes

Sign quantization [8, 19] quantizes each coordinate of $\mathbf{x}$ to either
$+1$ or $-1$ depending on its sign. If we additionally assume that each
coordinate of $\mathbf{x}$ is bounded, i.e.
$\lVert\mathbf{x}\rVert_{\infty}\leq B$, then the error incurred can be upper
bounded as $\sqrt{(B-1)^{2}n}\sim O(\sqrt{n})$. QSGD proposed by [2] uses $s$
quantization levels for each coordinate. In other words, if we were to use $R$
bits per dimension, then we have $s=2^{R}$. The bit requirement and error are
available in [2, Thm 3.2]. All these methods require $O(n)$ computation to
perform the source coding.

TernGrad [35], similar to sign quantization, uses three numerical levels
$\\{-1,0,+1\\}$ to quantize gradients for distributed training of neural
networks. [13] propose Vector Quantized (vq) SGD, in which they construct a
convex hull using a finite number of points and quantize their vector to one
of the points randomly. They also consider both communication and privacy
parameters of their coding scheme simultaneously. The exact expressions can be
found in [13, Table 2].

Top-$k$ sparsification [31] is a common gradient sparsification technique.
Here, $k$ denotes the number of retained coordinates. The bit-requirement
arises from the need to communicate the values of the $k$ chosen coordinates,
and the $\log_{2}\binom{n}{k}$ comes from the number of the ways $k$ out of
$n$ indices can be chosen, which also needs to be conveyed. This source coding
scheme requires a computation of $O(k+(n-k)\log_{2}k)$ due to the fact that
the coordinates must be sorted in order to be able to choose the top $k$ out
of them. Random sparsification [34] is another simple strategy which randomly
chooses the $k$ out of $n$ indices.

For our proposed strategy Democratic Source Coding, $\lambda=N/n$ denotes the
aspect ratio of the frame (random orthonormal or randomized Hadamard) chosen
for computing the embeddings. The additional constant number of $O(1)$ bits is
required to quantize and transmit the $\lVert\cdot\rVert_{\infty}$ norm of the
vector being quantized. It is important to note that the error is dimension
independent. If we resort to using near-democratic embeddings for our coding
scheme, the error would be $O(2^{-R/\lambda}\sqrt{\log n})$. As already seen
in the main paper, computing the democratic embedding entails solving an
$\ell_{\infty}$ minimization problem, which is a linear program that can be
solved in $O(n^{3})$ time. If we somehow knew the uncertainty principle
parameters of the frames we are using for computing the embeddings, for
example through Monte Carlo simulations etc., we can resort to using the
algorithm proposed in [25] to compute the Kashin embedding in $O(n^{2})$ time.
If we use near-democratic embeddings, which requires us to solve the
$\ell_{2}$ minimization problem, we can do that in $O(n\log n)$ time if we use
randomized Hadamard frames using fast transform algorithms, and in $O(n^{2})$
time using random orthonormal frames.