Distributed Reconstruction of Noisy Pooled Data
- URL: http://arxiv.org/abs/2204.07491v1
- Date: Thu, 14 Apr 2022 06:48:40 GMT
- Title: Distributed Reconstruction of Noisy Pooled Data
- Authors: Max Hahn-Klimroth and Dominik Kaaser
- Abstract summary: We consider two noise models for the pooled data problem.
We present and analyze for both error models a simple and efficient distributed algorithm.
Our novel analysis pins down the range of error probabilities and distributions for which our algorithm reconstructs the exact initial states with high probability.
- Score: 2.0559497209595823
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: In the pooled data problem we are given a set of $n$ agents, each of which
holds a hidden state bit, either $0$ or $1$. A querying procedure returns for a
query set the sum of the states of the queried agents. The goal is to
reconstruct the states using as few queries as possible. In this paper we
consider two noise models for the pooled data problem. In the noisy channel
model, the result for each agent flips with a certain probability. In the noisy
query model, each query result is subject to random Gaussian noise. Our results
are twofold. First, we present and analyze for both error models a simple and
efficient distributed algorithm that reconstructs the initial states in a
greedy fashion. Our novel analysis pins down the range of error probabilities
and distributions for which our algorithm reconstructs the exact initial states
with high probability. Secondly, we present simulation results of our algorithm
and compare its performance with approximate message passing (AMP) algorithms
that are conjectured to be optimal in a number of related problems.
Related papers
- Perturb-and-Project: Differentially Private Similarities and Marginals [73.98880839337873]
We revisit the input perturbations framework for differential privacy where noise is added to the input $Ain mathcalS$.
We first design novel efficient algorithms to privately release pair-wise cosine similarities.
We derive a novel algorithm to compute $k$-way marginal queries over $n$ features.
arXiv Detail & Related papers (2024-06-07T12:07:16Z) - Information-Computation Tradeoffs for Learning Margin Halfspaces with
Random Classification Noise [50.64137465792738]
We study the problem of PAC $gamma$-margin halfspaces with Random Classification Noise.
We establish an information-computation tradeoff suggesting an inherent gap between the sample complexity of the problem and the sample complexity of computationally efficient algorithms.
arXiv Detail & Related papers (2023-06-28T16:33:39Z) - Efficient Approximate Recovery from Pooled Data Using Doubly Regular
Pooling Schemes [1.7403133838762448]
We analyze an approximate reconstruction algorithm that estimates the hidden bits in a greedy fashion.
Our analysis is uniform in the degree of noise and the sparsity of $sigma$.
arXiv Detail & Related papers (2023-02-28T19:31:40Z) - Learning to Bound Counterfactual Inference in Structural Causal Models
from Observational and Randomised Data [64.96984404868411]
We derive a likelihood characterisation for the overall data that leads us to extend a previous EM-based algorithm.
The new algorithm learns to approximate the (unidentifiability) region of model parameters from such mixed data sources.
It delivers interval approximations to counterfactual results, which collapse to points in the identifiable case.
arXiv Detail & Related papers (2022-12-06T12:42:11Z) - Higher degree sum-of-squares relaxations robust against oblivious
outliers [14.58610686291355]
We consider estimation models of the form $Y=X*+N$, where $X*$ is some $m$-dimensional signal we wish to recover.
We introduce a family of algorithms that under mild assumptions recover the signal $X*$ in all estimation problems for which there exists a sum-of-squares algorithm.
arXiv Detail & Related papers (2022-11-14T13:09:12Z) - Learning from aggregated data with a maximum entropy model [73.63512438583375]
We show how a new model, similar to a logistic regression, may be learned from aggregated data only by approximating the unobserved feature distribution with a maximum entropy hypothesis.
We present empirical evidence on several public datasets that the model learned this way can achieve performances comparable to those of a logistic model trained with the full unaggregated data.
arXiv Detail & Related papers (2022-10-05T09:17:27Z) - Clustering with Queries under Semi-Random Noise [13.817228853960655]
We develop robust learning methods that tolerate general semi-random noise.
We show that information theoretically $Oleft(fracnk log n (1-2p)2right)$ queries suffice to learn any cluster of sufficiently large size.
arXiv Detail & Related papers (2022-06-09T16:02:00Z) - ReLU Regression with Massart Noise [52.10842036932169]
We study the fundamental problem of ReLU regression, where the goal is to fit Rectified Linear Units (ReLUs) to data.
We focus on ReLU regression in the Massart noise model, a natural and well-studied semi-random noise model.
We develop an efficient algorithm that achieves exact parameter recovery in this model.
arXiv Detail & Related papers (2021-09-10T02:13:22Z) - Local policy search with Bayesian optimization [73.0364959221845]
Reinforcement learning aims to find an optimal policy by interaction with an environment.
Policy gradients for local search are often obtained from random perturbations.
We develop an algorithm utilizing a probabilistic model of the objective function and its gradient.
arXiv Detail & Related papers (2021-06-22T16:07:02Z) - Efficient Algorithms for Multidimensional Segmented Regression [42.046881924063044]
We study the fundamental problem of fixed design em multidimensional regression.
We provide the first sample and computationally efficient algorithm for this problem in any fixed dimension.
Our algorithm relies on a simple merging iterative approach, which is novel in the multidimensional setting.
arXiv Detail & Related papers (2020-03-24T19:39:34Z)
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.