Wyner-Ziv Estimators: Efficient Distributed Mean Estimation with Side Information

• URL: http://arxiv.org/abs/2011.12160v1
• Date: Tue, 24 Nov 2020 15:19:55 GMT
• Title: Wyner-Ziv Estimators: Efficient Distributed Mean Estimation with Side Information
• Authors: Prathamesh Mayekar, Ananda Theertha Suresh, and Himanshu Tyagi
• Abstract summary: We study the problem of distributed mean estimation where the server has access to side information. We propose emphWyner-Ziv estimators, which are communication and computationally efficient. In a different direction, we present an alternative Wyner-Ziv estimator that uses correlated sampling.
• Score: 36.49502352300087
• License: http://creativecommons.org/publicdomain/zero/1.0/
• Abstract: Communication efficient distributed mean estimation is an important primitive that arises in many distributed learning and optimization scenarios such as federated learning. Without any probabilistic assumptions on the underlying data, we study the problem of distributed mean estimation where the server has access to side information. We propose \emph{Wyner-Ziv estimators}, which are communication and computationally efficient and near-optimal when an upper bound for the distance between the side information and the data is known. As a corollary, we also show that our algorithms provide efficient schemes for the classic Wyner-Ziv problem in information theory. In a different direction, when there is no knowledge assumed about the distance between side information and the data, we present an alternative Wyner-Ziv estimator that uses correlated sampling. This latter setting offers {\em universal recovery guarantees}, and perhaps will be of interest in practice when the number of users is large and keeping track of the distances between the data and the side information may not be possible.

Related papers

• Mutual Information Multinomial Estimation [53.58005108981247]
  Estimating mutual information (MI) is a fundamental yet challenging task in data science and machine learning. Our main discovery is that a preliminary estimate of the data distribution can dramatically help estimate. Experiments on diverse tasks including non-Gaussian synthetic problems with known ground-truth and real-world applications demonstrate the advantages of our method.
  arXiv  Detail & Related papers  (2024-08-18T06:27:30Z)
• Multi-Source Conformal Inference Under Distribution Shift [41.701790856201036]
  We consider the problem of obtaining distribution-free prediction intervals for a target population, leveraging multiple potentially biased data sources. We derive the efficient influence functions for the quantiles of unobserved outcomes in the target and source populations. We propose a data-adaptive strategy to upweight informative data sources for efficiency gain and downweight non-informative data sources for bias reduction.
  arXiv  Detail & Related papers  (2024-05-15T13:33:09Z)
• Mean Estimation with User-Level Privacy for Spatio-Temporal IoT Datasets [5.34194012533815]
  We develop user-level differentially private algorithms to ensure low estimation errors on real-world datasets. We test our algorithms on ITMS (Intelligent Traffic Management System) data from an Indian city. We characterize the best performance of pseudo-user creation-based algorithms on worst-case datasets via a minimax approach.
  arXiv  Detail & Related papers  (2024-01-29T06:21:29Z)
• Optimal Data Splitting in Distributed Optimization for Machine Learning [85.99744701008802]
  This study focuses on an optimal ratio of distributed data between the server and local machines for any costs of communications and local computations. The running times of the network are compared between uniform and optimal distributions. The superior theoretical performance of our solutions is experimentally validated.
  arXiv  Detail & Related papers  (2024-01-15T16:30:12Z)
• Leveraging Spatial and Temporal Correlations in Sparsified Mean Estimation [11.602121447683597]
  We study the problem of estimating at a central server the mean of a set of vectors distributed across several nodes. We leverage these correlations by simply modifying the decoding method used by the server to estimate the mean. We provide an analysis of the resulting estimation error as well as experiments for PCA, K-Means and Logistic Regression.
  arXiv  Detail & Related papers  (2021-10-14T22:24:26Z)
• Learning Bias-Invariant Representation by Cross-Sample Mutual Information Minimization [77.8735802150511]
  We propose a cross-sample adversarial debiasing (CSAD) method to remove the bias information misused by the target task. The correlation measurement plays a critical role in adversarial debiasing and is conducted by a cross-sample neural mutual information estimator. We conduct thorough experiments on publicly available datasets to validate the advantages of the proposed method over state-of-the-art approaches.
  arXiv  Detail & Related papers  (2021-08-11T21:17:02Z)
• Time-Series Imputation with Wasserstein Interpolation for Optimal Look-Ahead-Bias and Variance Tradeoff [66.59869239999459]
  In finance, imputation of missing returns may be applied prior to training a portfolio optimization model. There is an inherent trade-off between the look-ahead-bias of using the full data set for imputation and the larger variance in the imputation from using only the training data. We propose a Bayesian posterior consensus distribution which optimally controls the variance and look-ahead-bias trade-off in the imputation.
  arXiv  Detail & Related papers  (2021-02-25T09:05:35Z)
• High-Dimensional Multi-Task Averaging and Application to Kernel Mean Embedding [0.0]
  We propose an improved estimator for the multi-task averaging problem. We prove theoretically that this approach provides a reduction in mean squared error. An application of this approach is the estimation of multiple kernel mean embeddings.
  arXiv  Detail & Related papers  (2020-11-13T07:31:30Z)
• DEMI: Discriminative Estimator of Mutual Information [5.248805627195347]
  Estimating mutual information between continuous random variables is often intractable and challenging for high-dimensional data. Recent progress has leveraged neural networks to optimize variational lower bounds on mutual information. Our approach is based on training a classifier that provides the probability that a data sample pair is drawn from the joint distribution.
  arXiv  Detail & Related papers  (2020-10-05T04:19:27Z)
• Evaluating representations by the complexity of learning low-loss predictors [55.94170724668857]
  We consider the problem of evaluating representations of data for use in solving a downstream task. We propose to measure the quality of a representation by the complexity of learning a predictor on top of the representation that achieves low loss on a task of interest.
  arXiv  Detail & Related papers  (2020-09-15T22:06:58Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.