---
_id: '9543'
abstract:
- lang: eng
  text: 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.
article_processing_charge: No
arxiv: 1
author:
- first_name: Peter
  full_name: Davies, Peter
  id: 11396234-BB50-11E9-B24C-90FCE5697425
  last_name: Davies
  orcid: 0000-0002-5646-9524
- first_name: Vijaykrishna
  full_name: Gurunanthan, Vijaykrishna
  last_name: Gurunanthan
- first_name: 'Niusha '
  full_name: 'Moshrefi, Niusha '
  id: 4db776ff-ce15-11eb-96e3-bc2b90b01c16
  last_name: Moshrefi
- first_name: Saleh
  full_name: Ashkboos, Saleh
  id: 0D0A9058-257B-11EA-A937-9341C3D8BC8A
  last_name: Ashkboos
- first_name: Dan-Adrian
  full_name: Alistarh, Dan-Adrian
  id: 4A899BFC-F248-11E8-B48F-1D18A9856A87
  last_name: Alistarh
  orcid: 0000-0003-3650-940X
citation:
  ama: 'Davies P, Gurunanthan V, Moshrefi N, Ashkboos S, Alistarh D-A. New bounds
    for distributed mean estimation and variance reduction. In: <i>9th International
    Conference on Learning Representations</i>. ; 2021.'
  apa: Davies, P., Gurunanthan, V., Moshrefi, N., Ashkboos, S., &#38; Alistarh, D.-A.
    (2021). New bounds for distributed mean estimation and variance reduction. In
    <i>9th International Conference on Learning Representations</i>. Virtual.
  chicago: Davies, Peter, Vijaykrishna Gurunanthan, Niusha  Moshrefi, Saleh Ashkboos,
    and Dan-Adrian Alistarh. “New Bounds for Distributed Mean Estimation and Variance
    Reduction.” In <i>9th International Conference on Learning Representations</i>,
    2021.
  ieee: P. Davies, V. Gurunanthan, N. Moshrefi, S. Ashkboos, and D.-A. Alistarh, “New
    bounds for distributed mean estimation and variance reduction,” in <i>9th International
    Conference on Learning Representations</i>, Virtual, 2021.
  ista: 'Davies P, Gurunanthan V, Moshrefi N, Ashkboos S, Alistarh D-A. 2021. New
    bounds for distributed mean estimation and variance reduction. 9th International
    Conference on Learning Representations. ICLR: International Conference on Learning
    Representations.'
  mla: Davies, Peter, et al. “New Bounds for Distributed Mean Estimation and Variance
    Reduction.” <i>9th International Conference on Learning Representations</i>, 2021.
  short: P. Davies, V. Gurunanthan, N. Moshrefi, S. Ashkboos, D.-A. Alistarh, in:,
    9th International Conference on Learning Representations, 2021.
conference:
  end_date: 2021-05-07
  location: Virtual
  name: 'ICLR: International Conference on Learning Representations'
  start_date: 2021-05-03
corr_author: '1'
date_created: 2021-06-10T19:46:08Z
date_published: 2021-05-01T00:00:00Z
date_updated: 2025-07-10T12:01:50Z
day: '01'
department:
- _id: DaAl
ec_funded: 1
external_id:
  arxiv:
  - '2002.09268'
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: https://openreview.net/pdf?id=t86MwoUCCNe
month: '05'
oa: 1
oa_version: Published Version
project:
- _id: 260C2330-B435-11E9-9278-68D0E5697425
  call_identifier: H2020
  grant_number: '754411'
  name: ISTplus - Postdoctoral Fellowships
publication: 9th International Conference on Learning Representations
publication_status: published
quality_controlled: '1'
status: public
title: New bounds for distributed mean estimation and variance reduction
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2021'
...