L G ] 2 6 A ug 2 01 9 Finite Precision Stochastic Optimization – Accounting for the Bias

Content Provider	Semantic Scholar
Author	Mayekar, Prathamesh Tyagi, Himanshu
Copyright Year	2019
Abstract	We consider first order stochastic optimization where the oracle must quantize each subgradient estimate to r bits. We treat two oracle models: the first where the Euclidean norm of the oracle output is almost surely bounded and the second where it is mean square bounded. Prior work in this setting assumes the availability of unbiased quantizers. While this assumption is valid in the case of almost surely bounded oracles, it does not hold true for the standard setting of mean square bounded oracles, and the bias can dramatically affect the convergence rate. We analyze the performance of standard quantizers from prior work in combination with projected stochastic gradient descent for both these oracle models and present two new adaptive quantizers that outperform the existing ones. Specifically, for almost surely bounded oracles, we establish first a lower bound for the precision needed to attain the standard convergence rate of T− 1 2 for optimizing convex functions over a d-dimentional domain. Our proposed Rotated Adaptive Tetra-iterated Quantizer (RATQ) is merely a factor O(log log log∗ d) far from this lower bound. For mean square bounded oracles, we show that a state-of-the-art Rotated Uniform Quantizer (RUQ) from prior work would need atleast Ω(d log T ) bits to achieve the convergence rate of T− 1 2 , using any optimization protocol. However, our proposed Rotated Adaptive Quantizer (RAQ) outperforms RUQ in this setting and attains a convergence rate of T− 1 2 using a precision of only O(d log log T ). For mean square bounded oracles, in the communication-starved regime where the precision r is fixed to a constant independent of T , we show that RUQ cannot attain a convergence rate better than T− 1 4 for any r, while RAQ can attain convergence at rates arbitrarily close to T− 1 2 as r increases. As a by-product of our study, we show that our fixed-length quantizer RATQ has the same performance as optimal variable-length quantizers for the related problem of distributed mean estimation. †Department of Electrical Communication Engineering, Indian Institute of Science, Bangalore 560012, India. Email: {prathamesh, htyagi}@iisc.ac.in
File Format	PDF HTM / HTML
Alternate Webpage(s)	http://export.arxiv.org/pdf/1908.08200
Language	English
Access Restriction	Open
Content Type	Text
Resource Type	Article