  In this work, we present a family of vector quantization schemes \emph{vqSGD}
(Vector-Quantized Stochastic Gradient Descent) that provide an asymptotic
reduction in the communication cost with convergence guarantees in first-order
distributed optimization. In the process we derive the following fundamental
information theoretic fact: $\Theta(\frac{d}{R^2})$ bits are necessary and
sufficient to describe an unbiased estimator ${\hat{g}}({g})$ for any ${g}$ in
the $d$-dimensional unit sphere, under the constraint that
$\|{\hat{g}}({g})\|_2\le R$ almost surely. In particular, we consider a
randomized scheme based on the convex hull of a point set, that returns an
unbiased estimator of a $d$-dimensional gradient vector with almost surely
bounded norm. We provide multiple efficient instances of our scheme, that are
near optimal, and require only $o(d)$ bits of communication at the expense of
tolerable increase in error. The instances of our quantization scheme are
obtained using the properties of binary error-correcting codes and provide a
smooth tradeoff between the communication and the estimation error of
quantization. Furthermore, we show that \emph{vqSGD} also offers strong privacy
guarantees.
