論文の概要: Locally Private Hypothesis Selection

• arxiv url: http://arxiv.org/abs/2002.09465v2
• Date: Sat, 20 Jun 2020 02:58:48 GMT
• ステータス: 処理完了
• システム内更新日: 2022-12-30 01:18:47.113983
• Title: Locally Private Hypothesis Selection
• Title（参考訳）: ローカル・プライベート仮説の選択
• Authors: Sivakanth Gopi, Gautam Kamath, Janardhan Kulkarni, Aleksandar Nikolov, Zhiwei Steven Wu, Huanyu Zhang
• Abstract要約: 我々は、$mathcalQ$から$p$までの総変動距離が最良の分布に匹敵する分布を出力する。 局所的な差分プライバシーの制約は、コストの急激な増加を引き起こすことを示す。 提案アルゴリズムは,従来手法のラウンド複雑性を指数関数的に改善する。
• 参考スコア（独自算出の注目度）: 96.06118559817057
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We initiate the study of hypothesis selection under local differential privacy. Given samples from an unknown probability distribution $p$ and a set of $k$ probability distributions $\mathcal{Q}$, we aim to output, under the constraints of $\varepsilon$-local differential privacy, a distribution from $\mathcal{Q}$ whose total variation distance to $p$ is comparable to the best such distribution. This is a generalization of the classic problem of $k$-wise simple hypothesis testing, which corresponds to when $p \in \mathcal{Q}$, and we wish to identify $p$. Absent privacy constraints, this problem requires $O(\log k)$ samples from $p$, and it was recently shown that the same complexity is achievable under (central) differential privacy. However, the naive approach to this problem under local differential privacy would require $\tilde O(k^2)$ samples. We first show that the constraint of local differential privacy incurs an exponential increase in cost: any algorithm for this problem requires at least $\Omega(k)$ samples. Second, for the special case of $k$-wise simple hypothesis testing, we provide a non-interactive algorithm which nearly matches this bound, requiring $\tilde O(k)$ samples. Finally, we provide sequentially interactive algorithms for the general case, requiring $\tilde O(k)$ samples and only $O(\log \log k)$ rounds of interactivity. Our algorithms are achieved through a reduction to maximum selection with adversarial comparators, a problem of independent interest for which we initiate study in the parallel setting. For this problem, we provide a family of algorithms for each number of allowed rounds of interaction $t$, as well as lower bounds showing that they are near-optimal for every $t$. Notably, our algorithms result in exponential improvements on the round complexity of previous methods.
• Abstract（参考訳）: 局所的な差分プライバシーの下で仮説選択の研究を開始する。 未知の確率分布$p$のサンプルと、$k$の確率分布$\mathcal{Q}$のセットが与えられた場合、我々は、$\varepsilon$-local differential privacyという制約の下で、$\mathcal{Q}$の分布を出力することを目指している。 これは、$k$-wise な単純な仮説テストの古典的な問題の一般化であり、$p \in \mathcal{Q}$ のときに対応するもので、$p$ を識別したい。 プライバシの制約がなければ、この問題には$p$から$o(\log k)$のサンプルが必要となる。 しかし、局所的な差分プライバシーの下でこの問題に対処するには$\tilde O(k^2)$サンプルが必要である。 まず、局所微分プライバシーの制約によってコストが指数関数的に増加することを示し、この問題に対するアルゴリズムは少なくとも$\Omega(k)$サンプルを必要とする。 第二に、$k$の単純な仮説テストの特別な場合、この境界にほぼ一致する非相互作用アルゴリズムを提供し、$\tilde O(k)$サンプルを必要とする。 最後に、一般の場合に対して逐次インタラクティブなアルゴリズムを提供し、$\tilde O(k)$サンプルと$O(\log \log k)$ラウンドの対話性を必要とする。 提案手法は,並列環境での学習を開始する独立関心の問題である逆比較器による最大選択の削減によって実現される。 この問題に対して、我々は、許容される相互作用のラウンド数$t$に対するアルゴリズム群と、それらが$t$毎にほぼ最適であることを示す下界を提供する。 特に,本アルゴリズムは従来手法のラウンド複雑性を指数関数的に改善する。

関連論文リスト

• 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)
• Near-Optimal Bounds for Learning Gaussian Halfspaces with Random Classification Noise [50.64137465792738]
  この問題に対する効率的なSQアルゴリズムは、少なくとも$Omega(d1/2/(maxp, epsilon)2)$. のサンプル複雑性を必要とする。 我々の下限は、この1/epsilon$に対する二次的依存は、効率的なアルゴリズムに固有のものであることを示唆している。
  論文  参考訳（メタデータ） (2023-07-13T18:59:28Z)
• Succinct quantum testers for closeness and $k$-wise uniformity of probability distributions [2.3466828785520373]
  確率分布の近さ特性と$k$-wise均一性をテストする基本的な問題に対する潜在的な量子スピードアップについて検討する。 我々は、$ell1$-および$ell2$-closenessテストの量子クエリ複雑性が$O(sqrtn/varepsilon)$と$O(sqrtnk/varepsilon)$であることを示す。 クエリ複雑性を$O(sqrtnk/varepsilon)で表した最初の量子アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-04-25T15:32:37Z)
• Best Policy Identification in Linear MDPs [70.57916977441262]
  縮退した線形マルコフ+デルタ決定における最適同定問題について, 生成モデルに基づく固定信頼度設定における検討を行った。 複雑な非最適化プログラムの解としての下位境界は、そのようなアルゴリズムを考案する出発点として用いられる。
  論文  参考訳（メタデータ） (2022-08-11T04:12:50Z)
• Private High-Dimensional Hypothesis Testing [4.133655523622441]
  我々は高次元分布の個人性テストのための改良された差分プライベートアルゴリズムを提供する。 具体的には、ある固定された$mu*$に対して$mathcalN(mu*, Sigma)$、または少なくとも$alpha$の総変動距離を持つ$mathcalN(mu*, Sigma)$に由来するかどうかをテストすることができる。
  論文  参考訳（メタデータ） (2022-03-03T06:25:48Z)
• Statistically Near-Optimal Hypothesis Selection [33.83129262033921]
  仮説選択問題に対する最適2ドルの近似学習戦略を導出する。 これは、最適な近似係数とサンプルの複雑さを同時に達成する最初のアルゴリズムである。
  論文  参考訳（メタデータ） (2021-08-17T21:11:20Z)
• Optimal Testing of Discrete Distributions with High Probability [49.19942805582874]
  高確率状態に着目して離散分布を試験する問題について検討する。 一定の要素でサンプル最適である近接性および独立性テストのための最初のアルゴリズムを提供する。
  論文  参考訳（メタデータ） (2020-09-14T16:09:17Z)
• The Sparse Hausdorff Moment Problem, with Application to Topic Models [5.151973524974052]
  我々は$m=2k$iid二進確率変数のサンプルを用いて$k$-mixtureを同定するアルゴリズムを提案する。 加法精度$w_mincdotzetaO(k)$のモーメントを知るだけで十分である。
  論文  参考訳（メタデータ） (2020-07-16T04:23:57Z)
• Streaming Complexity of SVMs [110.63976030971106]
  本稿では,ストリーミングモデルにおけるバイアス正規化SVM問題を解く際の空間複雑性について検討する。 両方の問題に対して、$frac1lambdaepsilon$の次元に対して、$frac1lambdaepsilon$よりも空間的に小さいストリーミングアルゴリズムを得ることができることを示す。
  論文  参考訳（メタデータ） (2020-07-07T17:10:00Z)
• Model-Free Reinforcement Learning: from Clipped Pseudo-Regret to Sample Complexity [59.34067736545355]
  S$状態、$A$アクション、割引係数$gamma in (0,1)$、近似しきい値$epsilon > 0$の MDP が与えられた場合、$epsilon$-Optimal Policy を学ぶためのモデルなしアルゴリズムを提供する。 十分小さな$epsilon$の場合、サンプルの複雑さで改良されたアルゴリズムを示す。
  論文  参考訳（メタデータ） (2020-06-06T13:34:41Z)

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

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