RATQ: A Universal Fixed-Length Quantizer for Stochastic Optimization

Prathamesh Mayekar, Himanshu Tyagi
Proceedings of the Twenty Third International Conference on Artificial Intelligence and Statistics, PMLR 108:1399-1409, 2020.

Abstract

We present Rotated Adaptive Tetra-iterated Quantizer (RATQ), afixed-length quantizer for gradients in first order stochasticoptimization. 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 informationtheoretic lower bound for optimization accuracy using finite precisiongradients 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.  

Cite this Paper

BibTeX
@InProceedings{pmlr-v108-mayekar20a, title = {RATQ: A Universal Fixed-Length Quantizer for Stochastic Optimization}, author = {Mayekar, Prathamesh and Tyagi, Himanshu}, booktitle = {Proceedings of the Twenty Third International Conference on Artificial Intelligence and Statistics}, pages = {1399--1409}, year = {2020}, editor = {Chiappa, Silvia and Calandra, Roberto}, volume = {108}, series = {Proceedings of Machine Learning Research}, month = {26--28 Aug}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v108/mayekar20a/mayekar20a.pdf}, url = {https://proceedings.mlr.press/v108/mayekar20a.html}, abstract = {We present Rotated Adaptive Tetra-iterated Quantizer (RATQ), afixed-length quantizer for gradients in first order stochasticoptimization. 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 informationtheoretic lower bound for optimization accuracy using finite precisiongradients 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.  } }
Endnote
%0 Conference Paper %T RATQ: A Universal Fixed-Length Quantizer for Stochastic Optimization %A Prathamesh Mayekar %A Himanshu Tyagi %B Proceedings of the Twenty Third International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2020 %E Silvia Chiappa %E Roberto Calandra %F pmlr-v108-mayekar20a %I PMLR %P 1399--1409 %U https://proceedings.mlr.press/v108/mayekar20a.html %V 108 %X We present Rotated Adaptive Tetra-iterated Quantizer (RATQ), afixed-length quantizer for gradients in first order stochasticoptimization. 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 informationtheoretic lower bound for optimization accuracy using finite precisiongradients 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.  
APA
Mayekar, P. & Tyagi, H.. (2020). RATQ: A Universal Fixed-Length Quantizer for Stochastic Optimization. Proceedings of the Twenty Third International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 108:1399-1409 Available from https://proceedings.mlr.press/v108/mayekar20a.html.

Related Material