Optimal Sparsity-Sensitive Bounds for Distributed Mean Estimation

2019-12-01 · NeurIPS 2019 12 · Zengfeng Huang, Ziyue Huang, Yilei Wang, Ke Yi

We consider the problem of estimating the mean of a set of vectors, which are stored in a distributed system. This is a fundamental task with applications in distributed SGD and many other distributed problems, where communication is a main bottleneck for scaling up computations. We propose a new sparsity-aware algorithm, which improves previous results both theoretically and empirically. The communication cost of our algorithm is characterized by Hoyer's measure of sparseness. Moreover, we prove that the communication cost of our algorithm is information-theoretic optimal up to a constant factor in all sparseness regime. We have also conducted experimental studies, which demonstrate the advantages of our method and confirm our theoretical findings.

📄 PDF Abstract BibTeX

Code (1)

ZiyueHuang/DME 공식 구현

Methods 이 논문이 사용한 방법론

SGD Stochastic Gradient Descent is an iterative optimization technique that uses minibatches of data to form an expectation of the gradient, rather than the full gradient using…

Minimax Optimal Sparse Signal Recovery with Poisson Statistics

2015-01-21 · Mohammad H. Rohban, Delaram Motamedvaziri, Venkatesh Saligrama

We are motivated by problems that arise in a number of applications such as Online Marketing and Explosives detection, where the observations are usually modeled using Poisson statistics. We model each observation as a P…

Decoder Marketing

Sparsity of SVMs that use the epsilon-insensitive loss

2008-12-01 · NeurIPS 2008 12 · Ingo Steinwart, Andreas Christmann

In this paper lower and upper bounds for the number of support vectors are derived for support vector machines (SVMs) based on the epsilon-insensitive loss function. It turns out that these bounds are asymptotically tigh…

New Bounds For Distributed Mean Estimation and Variance Reduction

2020-02-21 · ICLR 2021 1 · Peter Davies, Vijaykrishna Gurunathan, Niusha Moshrefi, Saleh Ashkboos 외

We consider the problem of distributed mean estimation (DME), in which $n$ machines are each given a local $d$-dimensional vector $x_v \in \mathbb{R}^d$, and must cooperate to estimate the mean of their inputs $\mu = \fr…

Distributed Optimization Quantization

Information-Theoretic Bounds for Sparse Covariance Estimation in the Vertical-Split Distributed Model

2026-06-05 · Jing Yee Tan, Guangyue Han arxiv

We study the minimax estimation error for distributed covariance matrix estimation in the vertical-split (feature-split) setting, where two agents each observe different coordinates of $m$ i.i.d. sub-Gaussian samples and…

Information-theoretic lower bounds for distributed statistical estimation with communication constraints

2013-12-01 · NeurIPS 2013 12 · Yuchen Zhang, John Duchi, Michael. I. Jordan, Martin J. Wainwright

We establish minimax risk lower bounds for distributed statistical estimation given a budget $B$ of the total number of bits that may be communicated. Such lower bounds in turn reveal the minimum amount of communication …

Binary Classification General Classification regression