論文の概要: Sample-Optimal Locally Private Hypothesis Selection and the Provable
Benefits of Interactivity
- arxiv url: http://arxiv.org/abs/2312.05645v1
- Date: Sat, 9 Dec 2023 19:22:10 GMT
- ステータス: 処理完了
- システム内更新日: 2023-12-12 19:37:30.064513
- Title: Sample-Optimal Locally Private Hypothesis Selection and the Provable
Benefits of Interactivity
- Title（参考訳）: サンプル最適局所的仮説選択と相互作用の証明可能な利点
- Authors: Alireza F. Pour, Hassan Ashtiani, Shahab Asoodeh
- Abstract要約: 本研究では,局所的な差分プライバシーの制約下での仮説選択の問題について検討する。
我々は$varepsilon$-locally-differentially-private ($varepsilon$-LDP)アルゴリズムを考案し、$Thetaleft(fracklog kalpha2min varepsilon2,1 right)$を使って$d_TV(h,hatf)leq alpha + 9 min_fin MathcalFを保証する。
- 参考スコア（独自算出の注目度）: 8.100854060749212
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We study the problem of hypothesis selection under the constraint of local
differential privacy. Given a class $\mathcal{F}$ of $k$ distributions and a
set of i.i.d. samples from an unknown distribution $h$, the goal of hypothesis
selection is to pick a distribution $\hat{f}$ whose total variation distance to
$h$ is comparable with the best distribution in $\mathcal{F}$ (with high
probability). We devise an $\varepsilon$-locally-differentially-private
($\varepsilon$-LDP) algorithm that uses $\Theta\left(\frac{k}{\alpha^2\min
\{\varepsilon^2,1\}}\right)$ samples to guarantee that $d_{TV}(h,\hat{f})\leq
\alpha + 9 \min_{f\in \mathcal{F}}d_{TV}(h,f)$ with high probability. This
sample complexity is optimal for $\varepsilon<1$, matching the lower bound of
Gopi et al. (2020). All previously known algorithms for this problem required
$\Omega\left(\frac{k\log k}{\alpha^2\min \{ \varepsilon^2 ,1\}} \right)$
samples to work.
Moreover, our result demonstrates the power of interaction for
$\varepsilon$-LDP hypothesis selection. Namely, it breaks the known lower bound
of $\Omega\left(\frac{k\log k}{\alpha^2\min \{ \varepsilon^2 ,1\}} \right)$ for
the sample complexity of non-interactive hypothesis selection. Our algorithm
breaks this barrier using only $\Theta(\log \log k)$ rounds of interaction.
To prove our results, we define the notion of \emph{critical queries} for a
Statistical Query Algorithm (SQA) which may be of independent interest.
Informally, an SQA is said to use a small number of critical queries if its
success relies on the accuracy of only a small number of queries it asks. We
then design an LDP algorithm that uses a smaller number of critical queries.
- Abstract（参考訳）: 局所的な差分プライバシーの制約の下で仮説選択の問題を考察する。
クラス$\mathcal{f}$ of $k$ディストリビューションと未知のディストリビューション$h$から一組のi.i.d.サンプルが与えられた場合、仮説選択の目標は、$h$までの合計変動距離が$\mathcal{f}$(高い確率で)のベストディストリビューションに匹敵する分布$\hat{f}$を選択することである。
我々は、$\theta\left(\frac{k}{\alpha^2\min \{\varepsilon^2,1\}}\right)$サンプルを使用して$d_{tv}(h,\hat{f})\leq \alpha + 9 \min_{f\in \mathcal{f}}d_{tv}(h,f)$を高い確率で保証する$\varepsilon$-locally-differentially-private (\varepsilon$-ldp)アルゴリズムを開発した。
このサンプルの複雑さは、Gopi et al. (2020) の下限と一致する$\varepsilon<1$に対して最適である。
この問題の既知アルゴリズムは全て$\Omega\left(\frac{k\log k}{\alpha^2\min \{ \varepsilon^2 ,1\}} \right)$サンプルを動作させる必要があった。
さらに,この結果は,$\varepsilon$-LDP仮説選択における相互作用のパワーを示す。
すなわち、非相互作用仮説選択のサンプル複雑性に対して、既知の$\Omega\left(\frac{k\log k}{\alpha^2\min \{ \varepsilon^2 ,1\}} \right)$を破る。
我々のアルゴリズムはこの障壁を$\Theta(\log \log k)$の相互作用で破る。
結果を証明するために,統計的問合せアルゴリズム (sqa) に対して,独立興味を持つかもしれない<emph{ critical query} の概念を定義する。
形式的には、SQAは、その成功が要求する少数のクエリの精度に依存する場合、少数のクリティカルクエリを使用すると言われている。
次に、より少数のクリティカルクエリを使用するLDPアルゴリズムを設計する。
関連論文リスト
- 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) - Near Sample-Optimal Reduction-based Policy Learning for Average Reward
MDP [58.13930707612128]
この研究は、平均報酬マルコフ決定過程(AMDP)における$varepsilon$-Optimal Policyを得る際のサンプルの複雑さを考察する。
我々は、状態-作用対当たりの$widetilde O(H varepsilon-3 ln frac1delta)$サンプルを証明し、$H := sp(h*)$は任意の最適ポリシーのバイアスのスパンであり、$varepsilon$は精度、$delta$は失敗確率である。
論文 参考訳（メタデータ） (2022-12-01T15:57:58Z) - Private High-Dimensional Hypothesis Testing [4.133655523622441]
我々は高次元分布の個人性テストのための改良された差分プライベートアルゴリズムを提供する。
具体的には、ある固定された$mu*$に対して$mathcalN(mu*, Sigma)$、または少なくとも$alpha$の総変動距離を持つ$mathcalN(mu*, Sigma)$に由来するかどうかをテストすることができる。
論文 参考訳（メタデータ） (2022-03-03T06:25:48Z) - Sampling from Log-Concave Distributions with Infinity-Distance
Guarantees and Applications to Differentially Private Optimization [33.38289436686841]
本稿では,dis distributionO(varepsilon)$close から$ infinity-distance に点を出力するアルゴリズムを提案する。
また、ディキンウォークの「ソフトパイ」バージョンも提示する。
論文 参考訳（メタデータ） (2021-11-07T13:44:50Z) - Statistically Near-Optimal Hypothesis Selection [33.83129262033921]
仮説選択問題に対する最適2ドルの近似学習戦略を導出する。
これは、最適な近似係数とサンプルの複雑さを同時に達成する最初のアルゴリズムである。
論文 参考訳（メタデータ） (2021-08-17T21:11:20Z) - Cascading Bandit under Differential Privacy [21.936577816668944]
本研究では,カスケードバンドにおける自己差分プライバシー(DP)と局所差分プライバシー(LDP)について検討する。
DPでは,$epsilon$-indistinguishability を保証し,$mathcalO(fraclog3 Tepsilon)$を任意の小さな$xi$に対して後悔するアルゴリズムを提案する。
Epsilon$,$delta$)-LDPの下では、プライバシの予算とエラー確率のトレードオフを通じて、K2$依存を緩和します。
論文 参考訳（メタデータ） (2021-05-24T07:19:01Z) - 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) - Agnostic Learning of a Single Neuron with Gradient Descent [92.7662890047311]
期待される正方形損失から、最も適合した単一ニューロンを学習することの問題点を考察する。
ReLUアクティベーションでは、我々の人口リスク保証は$O(mathsfOPT1/2)+epsilon$である。
ReLUアクティベーションでは、我々の人口リスク保証は$O(mathsfOPT1/2)+epsilon$である。
論文 参考訳（メタデータ） (2020-05-29T07:20:35Z) - Locally Private Hypothesis Selection [96.06118559817057]
我々は、$mathcalQ$から$p$までの総変動距離が最良の分布に匹敵する分布を出力する。
局所的な差分プライバシーの制約は、コストの急激な増加を引き起こすことを示す。
提案アルゴリズムは,従来手法のラウンド複雑性を指数関数的に改善する。
論文 参考訳（メタデータ） (2020-02-21T18:30:48Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。