論文の概要: Distributed Reconstruction of Noisy Pooled Data
- arxiv url: http://arxiv.org/abs/2204.07491v1
- Date: Thu, 14 Apr 2022 06:48:40 GMT
- ステータス: 処理完了
- システム内更新日: 2022-04-18 12:52:46.925728
- Title: Distributed Reconstruction of Noisy Pooled Data
- Title（参考訳）: ノイズプールデータの分散再構成
- Authors: Max Hahn-Klimroth and Dominik Kaaser
- Abstract要約: プールデータ問題に対する2つのノイズモデルについて考察する。
本稿では,2つの誤りモデルに対して,単純かつ効率的な分散アルゴリズムを提示し,解析する。
提案手法は,アルゴリズムが精度の高い正確な初期状態を再構成する誤差確率と分布の範囲を推定する。
- 参考スコア（独自算出の注目度）: 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.
- Abstract（参考訳）: プールされたデータ問題では、$n$エージェントのセットが与えられ、それぞれが$0$または$$$の隠れた状態ビットを保持します。
クエリ手順はクエリセットに対して、クエリされたエージェントの状態の合計を返す。
目標は、できるだけ少ないクエリを使って状態を再構築することだ。
本稿では,プールデータ問題に対する2つのノイズモデルについて考察する。
ノイズチャネルモデルでは、各エージェントに対する結果が、ある確率で反転する。
ノイズの多いクエリモデルでは、各クエリ結果はランダムなガウスノイズを受ける。
私たちの結果は2倍です。
まず, 2つの誤差モデルについて,初期状態を欲張りな方法で再構成する単純かつ効率的な分散アルゴリズムを提示し,解析する。
提案手法は,アルゴリズムが精度の高い正確な初期状態を再構成する誤差確率と分布の範囲を推定する。
次に,本アルゴリズムのシミュレーション結果と,その性能を,多くの関連する問題において最適と推定される近似メッセージパッシング(AMP)アルゴリズムと比較する。
関連論文リスト
- Accelerated zero-order SGD under high-order smoothness and overparameterized regime [79.85163929026146]
凸最適化問題を解くための新しい勾配のないアルゴリズムを提案する。
このような問題は医学、物理学、機械学習で発生する。
両種類の雑音下で提案アルゴリズムの収束保証を行う。
論文 参考訳（メタデータ） (2024-11-21T10:26:17Z) - Evolutionary Algorithms Are Significantly More Robust to Noise When They Ignore It [10.165640083594573]
再評価の必要性は過大評価される可能性があり、実際は有害である。
この進化的アルゴリズムの最初の分析は、再評価なしに単一目的雑音の問題を解くことで、そのようなアルゴリズムが以前考えられていたよりもずっと良いノイズに対処できることを示している。
論文 参考訳（メタデータ） (2024-08-31T00:10:10Z) - Perturb-and-Project: Differentially Private Similarities and Marginals [73.98880839337873]
差分プライバシーのための入力摂動フレームワークを再検討し、入力にノイズを付加する。
まず、ペアワイズ・コサイン類似性をプライベートにリリースするための新しい効率的なアルゴリズムを設計する。
我々は,$k$の辺縁クエリを$n$の機能に対して計算する新しいアルゴリズムを導出する。
論文 参考訳（メタデータ） (2024-06-07T12:07:16Z) - Efficient Approximate Recovery from Pooled Data Using Doubly Regular
Pooling Schemes [1.7403133838762448]
隠れたビットをグリーディーな方法で推定する近似再構成アルゴリズムを解析する。
我々の分析はノイズの度合いと$sigma$の空間性に一様である。
論文 参考訳（メタデータ） (2023-02-28T19:31:40Z) - Learning to Bound Counterfactual Inference in Structural Causal Models
from Observational and Randomised Data [64.96984404868411]
我々は、従来のEMベースのアルゴリズムを拡張するための全体的なデータの特徴付けを導出する。
新しいアルゴリズムは、そのような混合データソースからモデルパラメータの(不特定性)領域を近似することを学ぶ。
反実的な結果に間隔近似を与え、それが特定可能な場合の点に崩壊する。
論文 参考訳（メタデータ） (2022-12-06T12:42:11Z) - Higher degree sum-of-squares relaxations robust against oblivious
outliers [14.58610686291355]
我々は、$Y=X*+N$という形の推定モデルを考える。
本稿では,2乗推定アルゴリズムが存在するすべての推定問題において,軽度仮定の下で信号が$X*$に回復するアルゴリズム群を紹介する。
論文 参考訳（メタデータ） (2022-11-14T13:09:12Z) - Learning from aggregated data with a maximum entropy model [73.63512438583375]
我々は,観測されていない特徴分布を最大エントロピー仮説で近似することにより,ロジスティック回帰と類似した新しいモデルが,集約データからのみ学習されることを示す。
我々は、この方法で学習したモデルが、完全な非凝集データでトレーニングされたロジスティックモデルに匹敵するパフォーマンスを達成することができるという、いくつかの公開データセットに関する実証的な証拠を提示する。
論文 参考訳（メタデータ） (2022-10-05T09:17:27Z) - Clustering with Queries under Semi-Random Noise [13.817228853960655]
一般半ランダム雑音を許容する頑健な学習法を開発した。
理論的には$Oleft(fracnk log n (1-2p)2right)$ query suffice to learn any cluster of enough large size。
論文 参考訳（メタデータ） (2022-06-09T16:02:00Z) - ReLU Regression with Massart Noise [52.10842036932169]
本稿では、ReLU回帰の基本的問題として、Rectified Linear Units(ReLU)をデータに適合させることを目標としている。
我々は自然およびよく研究された半ランダムノイズモデルであるMassartノイズモデルにおけるReLU回帰に着目した。
このモデルにおいて,パラメータの正確な回復を実現する効率的なアルゴリズムを開発した。
論文 参考訳（メタデータ） (2021-09-10T02:13:22Z) - Local policy search with Bayesian optimization [73.0364959221845]
強化学習は、環境との相互作用によって最適な政策を見つけることを目的としている。
局所探索のための政策勾配は、しばしばランダムな摂動から得られる。
目的関数の確率モデルとその勾配を用いたアルゴリズムを開発する。
論文 参考訳（メタデータ） (2021-06-22T16:07:02Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。