RATQ: A Universal Fixed-Length Quantizer for Stochastic Optimization
  We present Rotated Adaptive Tetra-iterated Quantizer (RATQ), a fixed-length
quantizer for gradients in first order stochastic optimization. RATQ is easy to
implement and involves only a Hadamard transform computation and adaptive
uniform quantization with appropriately chosen dynamic ranges. For noisy
gradients with almost surely bounded Euclidean norms, we establish an
information theoretic lower bound for optimization accuracy using finite
precision gradients and show that RATQ almost attains this lower bound.
  For mean square bounded noisy gradients, we use a gain-shape quantizer which
separately quantizes the Euclidean norm and uses RATQ to quantize the
normalized unit norm vector. We establish lower bounds for performance of any
optimization procedure and shape quantizer, when used with a uniform gain
quantizer. Finally, we propose an adaptive quantizer for gain which when used
with RATQ for shape quantizer outperforms uniform gain quantization and is, in
fact, close to optimal.
  As a by-product, we show that our fixed-length quantizer RATQ has almost the
same performance as the optimal variable-length quantizers for distributed mean
estimation. Also, we obtain an efficient quantizer for Gaussian vectors which
attains a rate very close to the Gaussian rate-distortion function and is, in
fact, universal for subgaussian input vectors.
