--- res: bibo_abstract: - We consider the problem ofdistributed mean estimation (DME), in which n machines are each given a local d-dimensional vector xv∈Rd, and must cooperate to estimate the mean of their inputs μ=1n∑nv=1xv, while minimizing total communication cost. DME is a fundamental construct in distributed machine learning, and there has been considerable work on variants of this problem, especially in the context of distributed variance reduction for stochastic gradients in parallel SGD. Previous work typically assumes an upper bound on the norm of the input vectors, and achieves an error bound in terms of this norm. However, in many real applications, the input vectors are concentrated around the correct output μ, but μ itself has large norm. In such cases, previous output error bounds perform poorly. In this paper, we show that output error bounds need not depend on input norm. We provide a method of quantization which allows distributed mean estimation to be performed with solution quality dependent only on the distance between inputs, not on input norm, and show an analogous result for distributed variance reduction. The technique is based on a new connection with lattice theory. We also provide lower bounds showing that the communication to error trade-off of our algorithms is asymptotically optimal. As the lattices achieving optimal bounds under l2-norm can be computationally impractical, we also present an extension which leverages easy-to-use cubic lattices, and is loose only up to a logarithmic factor ind. We show experimentally that our method yields practical improvements for common applications, relative to prior approaches.@eng bibo_authorlist: - foaf_Person: foaf_givenName: Peter foaf_name: Davies, Peter foaf_surname: Davies foaf_workInfoHomepage: http://www.librecat.org/personId=11396234-BB50-11E9-B24C-90FCE5697425 orcid: 0000-0002-5646-9524 - foaf_Person: foaf_givenName: Vijaykrishna foaf_name: Gurunanthan, Vijaykrishna foaf_surname: Gurunanthan - foaf_Person: foaf_givenName: 'Niusha ' foaf_name: 'Moshrefi, Niusha ' foaf_surname: Moshrefi foaf_workInfoHomepage: http://www.librecat.org/personId=4db776ff-ce15-11eb-96e3-bc2b90b01c16 - foaf_Person: foaf_givenName: Saleh foaf_name: Ashkboos, Saleh foaf_surname: Ashkboos foaf_workInfoHomepage: http://www.librecat.org/personId=0D0A9058-257B-11EA-A937-9341C3D8BC8A - foaf_Person: foaf_givenName: Dan-Adrian foaf_name: Alistarh, Dan-Adrian foaf_surname: Alistarh foaf_workInfoHomepage: http://www.librecat.org/personId=4A899BFC-F248-11E8-B48F-1D18A9856A87 orcid: 0000-0003-3650-940X dct_date: 2021^xs_gYear dct_language: eng dct_title: New bounds for distributed mean estimation and variance reduction@ ...