論文の概要: Efficient Approximate Recovery from Pooled Data Using Doubly Regular Pooling Schemes

• arxiv url: http://arxiv.org/abs/2303.00043v1
• Date: Tue, 28 Feb 2023 19:31:40 GMT
• ステータス: 処理完了
• システム内更新日: 2023-03-02 17:07:00.056531
• Title: Efficient Approximate Recovery from Pooled Data Using Doubly Regular Pooling Schemes
• Title（参考訳）: 2重正則プーリングスキームを用いたプールデータからの効率的な近似復元
• Authors: Max Hahn-Klimroth, Dominik Kaaser, Malin Rau
• Abstract要約: 隠れたビットをグリーディーな方法で推定する近似再構成アルゴリズムを解析する。 我々の分析はノイズの度合いと$sigma$の空間性に一様である。
• 参考スコア（独自算出の注目度）: 1.7403133838762448
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In the pooled data problem we are given $n$ agents with hidden state bits, either $0$ or $1$. The hidden states are unknown and can be seen as the underlying ground truth $\sigma$. To uncover that ground truth, we are given a querying method that queries multiple agents at a time. Each query reports the sum of the states of the queried agents. Our goal is to learn the hidden state bits using as few queries as possible. So far, most literature deals with exact reconstruction of all hidden state bits. We study a more relaxed variant in which we allow a small fraction of agents to be classified incorrectly. This becomes particularly relevant in the noisy variant of the pooled data problem where the queries' results are subject to random noise. In this setting, we provide a doubly regular test design that assigns agents to queries. For this design we analyze an approximate reconstruction algorithm that estimates the hidden bits in a greedy fashion. We give a rigorous analysis of the algorithm's performance, its error probability, and its approximation quality. As a main technical novelty, our analysis is uniform in the degree of noise and the sparsity of $\sigma$. Finally, simulations back up our theoretical findings and provide strong empirical evidence that our algorithm works well for realistic sample sizes.
• Abstract（参考訳）: プールされたデータ問題では、隠された状態ビットを持つ$n$エージェント、0$または$1$が与えられます。 隠れた状態は未知であり、基礎となる真理は$\sigma$であると見なすことができる。 その事実を明らかにするために、複数のエージェントを同時にクエリするクエリ方法が与えられた。 各クエリは、クエリされたエージェントの状態の合計を報告します。 私たちのゴールは、できるだけ少ないクエリを使って隠れた状態ビットを学ぶことです。 これまでのところ、ほとんどの文献は隠れた状態ビットの正確な再構築を扱っている。 我々は、少数のエージェントを誤って分類できる、より緩和された変種について研究する。 これは、クエリの結果がランダムノイズを受けるプールデータ問題において、特にノイズに関係している。 この設定では、エージェントをクエリに割り当てる2つの定期的なテスト設計を提供します。 この設計のために,隠れたビットを欲深い方法で推定する近似再構成アルゴリズムを解析する。 本稿では,アルゴリズムの性能,誤差確率,近似品質を厳密に分析する。 主な技術的ノベルティとして、我々の分析はノイズの程度と$\sigma$のスパーシティで一様である。 最後に、シミュレーションは我々の理論的な結果を裏付け、我々のアルゴリズムが現実的なサンプルサイズでうまく機能することを示す強力な実証的な証拠を提供する。

関連論文リスト

• Benchmarking Private Population Data Release Mechanisms: Synthetic Data vs. TopDown [50.40020716418472]
  本研究では、TopDownアルゴリズムとプライベート合成データ生成を比較し、クエリの複雑さによる精度への影響を判定する。 この結果から,TopDownアルゴリズムは,分散クエリに対して,評価したどの合成データ手法よりもはるかに優れたプライバシー-忠実トレードオフを実現することがわかった。
  論文  参考訳（メタデータ） (2024-01-31T17:38:34Z)
• Recovering Top-Two Answers and Confusion Probability in Multi-Choice Crowdsourcing [10.508187462682308]
  我々は,クラウドソーシングの課題を,基礎的真理だけでなく,最も紛らわしい回答と混乱確率の回復を目標として検討している。 本稿では,各タスクの上位2つの答えが,他の選択肢と区別されるモデルを提案する。 このモデルでは、上位2つの答えと混乱確率の両方を推測する2段階の推論アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2022-12-29T09:46:39Z)
• Distributed Reconstruction of Noisy Pooled Data [2.0559497209595823]
  プールデータ問題に対する2つのノイズモデルについて考察する。 本稿では,2つの誤りモデルに対して,単純かつ効率的な分散アルゴリズムを提示し,解析する。 提案手法は,アルゴリズムが精度の高い正確な初期状態を再構成する誤差確率と分布の範囲を推定する。
  論文  参考訳（メタデータ） (2022-04-14T06:48:40Z)
• ReLU Regression with Massart Noise [52.10842036932169]
  本稿では、ReLU回帰の基本的問題として、Rectified Linear Units(ReLU)をデータに適合させることを目標としている。 我々は自然およびよく研究された半ランダムノイズモデルであるMassartノイズモデルにおけるReLU回帰に着目した。 このモデルにおいて,パラメータの正確な回復を実現する効率的なアルゴリズムを開発した。
  論文  参考訳（メタデータ） (2021-09-10T02:13:22Z)
• Generalization in the Face of Adaptivity: A Bayesian Perspective [3.0202264016476623]
  適応的に選択されたクエリによるデータサンプルの繰り返し使用は、急速に過度な適合につながる可能性がある。 単純なノイズアンバウンド付加アルゴリズムは、この問題を防ぐのに十分であることがわかった。 提案手法では, 過去のクエリに対する応答にデータサンプルに関する情報がどの程度エンコードされたか, ベイズ因子と新しいクエリの共分散から適応性の害が生じることを示す。
  論文  参考訳（メタデータ） (2021-06-20T22:06:44Z)
• Navigating to the Best Policy in Markov Decision Processes [68.8204255655161]
  マルコフ決定過程における純粋探索問題について検討する。 エージェントはアクションを逐次選択し、結果のシステム軌道から可能な限り早くベストを目標とする。
  論文  参考訳（メタデータ） (2021-06-05T09:16:28Z)
• Differentially Private Query Release Through Adaptive Projection [19.449593001368193]
  我々は,$k$-way マージンのような膨大な統計クエリに対する回答を解放するための新しいアルゴリズムを提案し,実装し,評価する。 我々のアルゴリズムは、単純な摂動を用いて、プライベートデータセット上のクエリに応答するプロジェクションメカニズムの連続緩和を適応的に利用する。 特に,プライバシ予算が小さい場合や,クエリクラスが大きい場合など,既存のアルゴリズムよりも優れていることが判明した。
  論文  参考訳（メタデータ） (2021-03-11T12:43:18Z)
• The Sparse Vector Technique, Revisited [67.57692396665915]
  我々は、微分プライバシーの文献において最も基礎的で広く適用可能なテクニックの1つを再考する。 この単純なアルゴリズムは、データベース上のあるクエリの値が、私たちが期待している値に近いかどうかをプライベートにテストします。 一つの個人が過剰なクエリの回答に寄与しない限り、クエリのテストを継続できる代替の、等しくシンプルなアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-10-02T10:50:52Z)
• GeoDA: a geometric framework for black-box adversarial attacks [79.52980486689287]
  我々は,最も困難なブラックボックス設定の1つにおいて,逆例を生成するためのフレームワークを提案する。 我々のフレームワークは、ディープネットワークの決定境界は通常、データサンプルの近傍で小さな平均曲率を持つという観察に基づいている。
  論文  参考訳（メタデータ） (2020-03-13T20:03:01Z)
• Contextual Search in the Presence of Adversarial Corruptions [33.28268414842846]
  より高次元における二項探索の一般化である文脈探索について検討する。 これらのアルゴリズムは, 敵対的腐敗がない場合に, ほぼ最適に後悔することを示す。 我々の手法は学習理論、ゲーム理論、高次元幾何学、凸解析からインスピレーションを得ている。
  論文  参考訳（メタデータ） (2020-02-26T17:25:53Z)
• The Simulator: Understanding Adaptive Sampling in the Moderate-Confidence Regime [52.38455827779212]
  エミュレータと呼ばれる適応サンプリングを解析するための新しい手法を提案する。 適切なログファクタを組み込んだトップk問題の最初のインスタンスベースの下位境界を証明します。 我々の新しい分析は、後者の問題に対するこの種の最初のエミュレータであるベストアームとトップkの識別に、シンプルでほぼ最適であることを示した。
  論文  参考訳（メタデータ） (2017-02-16T23:42:02Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。