論文の概要: Query-Efficient Locally Private Hypothesis Selection via the Scheffe Graph
- arxiv url: http://arxiv.org/abs/2509.16180v1
- Date: Fri, 19 Sep 2025 17:41:15 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-09-22 18:18:11.259813
- Title: Query-Efficient Locally Private Hypothesis Selection via the Scheffe Graph
- Title（参考訳）: Scheffe グラフによる局所的私的仮説の選択
- Authors: Gautam Kamath, Alireza F. Pour, Matthew Regehr, David P. Woodruff,
- Abstract要約: 局所的な差分プライバシーを満足するアルゴリズムを記述し、個人に対して$tildeO(k3/2)$非適応クエリを実行する。
また、Scheff'eグラフをダブする新しいオブジェクトを導入し、$Q$の分散間の差の構造をキャプチャする。
- 参考スコア（独自算出の注目度）: 45.975805184376036
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We propose an algorithm with improved query-complexity for the problem of hypothesis selection under local differential privacy constraints. Given a set of $k$ probability distributions $Q$, we describe an algorithm that satisfies local differential privacy, performs $\tilde{O}(k^{3/2})$ non-adaptive queries to individuals who each have samples from a probability distribution $p$, and outputs a probability distribution from the set $Q$ which is nearly the closest to $p$. Previous algorithms required either $\Omega(k^2)$ queries or many rounds of interactive queries. Technically, we introduce a new object we dub the Scheff\'e graph, which captures structure of the differences between distributions in $Q$, and may be of more broad interest for hypothesis selection tasks.
- Abstract（参考訳）: 本稿では,局所的な差分プライバシー制約の下での仮説選択問題に対して,クエリの複雑さを改良したアルゴリズムを提案する。
Q$の確率分布のセットを与えられた場合、局所的な差分プライバシーを満たすアルゴリズムを記述し、確率分布のサンプルを持つ個人に対して$\tilde{O}(k^{3/2})$非適応クエリを実行し、$Q$から確率分布を出力する。
以前のアルゴリズムでは$\Omega(k^2)$クエリか、対話型クエリのラウンドが必要だった。
技術的に、我々はSchuff\'eグラフをダブした新しいオブジェクトを導入し、これは分布間の差を$Q$でキャプチャし、仮説選択タスクに対してより幅広い関心を持つかもしれない。
関連論文リスト
- Nearly-Linear Time Private Hypothesis Selection with the Optimal Approximation Factor [7.069470347531414]
分布の密度をサンプルから推定することは統計学の基本的な問題である。
仮説選択は、サンプルセットに加えて、$n$の候補分布が与えられる設定に対処する。
本稿では,仮説の数に関して,ほぼ直線時間で実行される中央モデルに差分プライベートなアルゴリズムを提案する。
論文 参考訳（メタデータ） (2025-06-01T20:46:46Z) - On the query complexity of sampling from non-log-concave distributions [2.4253233571593547]
密度$p(x)propto e-f(x)$を持つ$d$次元分布からサンプリングする問題を、必ずしも良好な等尺条件を満たすとは限らない。
広い範囲のパラメータに対して、サンプリングは$d$の超指数係数による最適化よりも厳密に容易であることを示す。
論文 参考訳（メタデータ） (2025-02-10T06:54:16Z) - Sample-Optimal Locally Private Hypothesis Selection and the Provable
Benefits of Interactivity [8.100854060749212]
本研究では,局所的な差分プライバシーの制約下での仮説選択の問題について検討する。
我々は$varepsilon$-locally-differentially-private ($varepsilon$-LDP)アルゴリズムを考案し、$Thetaleft(fracklog kalpha2min varepsilon2,1 right)$を使って$d_TV(h,hatf)leq alpha + 9 min_fin MathcalFを保証する。
論文 参考訳（メタデータ） (2023-12-09T19:22:10Z) - Stochastic Approximation Approaches to Group Distributionally Robust Optimization and Beyond [89.72693227960274]
本稿では,グループ分散ロバスト最適化 (GDRO) を,$m$以上の異なる分布をうまく処理するモデルを学習する目的で検討する。
各ラウンドのサンプル数を$m$から1に抑えるため、GDROを2人でプレイするゲームとして、一方のプレイヤーが実行し、他方のプレイヤーが非公開のマルチアームバンディットのオンラインアルゴリズムを実行する。
第2のシナリオでは、最大リスクではなく、平均的最上位k$リスクを最適化し、分散の影響を軽減することを提案する。
論文 参考訳（メタデータ） (2023-02-18T09:24:15Z) - Simple Binary Hypothesis Testing under Local Differential Privacy and
Communication Constraints [8.261182037130407]
局所差分プライバシー (LDP) と通信制約の両面から, 単純な二分仮説テストについて検討する。
我々はその結果をミニマックス最適かインスタンス最適かのどちらかとみなす。
論文 参考訳（メタデータ） (2023-01-09T18:36:49Z) - Locally Private Hypothesis Selection [96.06118559817057]
我々は、$mathcalQ$から$p$までの総変動距離が最良の分布に匹敵する分布を出力する。
局所的な差分プライバシーの制約は、コストの急激な増加を引き起こすことを示す。
提案アルゴリズムは,従来手法のラウンド複雑性を指数関数的に改善する。
論文 参考訳（メタデータ） (2020-02-21T18:30:48Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。