論文の概要: Differentially Private Best-Arm Identification
- arxiv url: http://arxiv.org/abs/2406.06408v1
- Date: Mon, 10 Jun 2024 16:02:48 GMT
- ステータス: 処理完了
- システム内更新日: 2024-06-11 13:09:08.297416
- Title: Differentially Private Best-Arm Identification
- Title（参考訳）: 個人別Best-Arm識別
- Authors: Achraf Azize, Marc Jourdan, Aymen Al Marjani, Debabrota Basu,
- Abstract要約: ベストアーム識別(BAI)問題は、データセンシティブなアプリケーションに徐々に使われている。
これらのアプリケーションによって引き起こされるデータプライバシの懸念に触発され、ローカルモデルと中央モデルの両方に一定の信頼を保ちながら、BAIの問題を研究する。
- 参考スコア（独自算出の注目度）: 14.916947598339988
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Best Arm Identification (BAI) problems are progressively used for data-sensitive applications, such as designing adaptive clinical trials, tuning hyper-parameters, and conducting user studies. Motivated by the data privacy concerns invoked by these applications, we study the problem of BAI with fixed confidence in both the local and central models, i.e. $\epsilon$-local and $\epsilon$-global Differential Privacy (DP). First, to quantify the cost of privacy, we derive lower bounds on the sample complexity of any $\delta$-correct BAI algorithm satisfying $\epsilon$-global DP or $\epsilon$-local DP. Our lower bounds suggest the existence of two privacy regimes. In the high-privacy regime, the hardness depends on a coupled effect of privacy and novel information-theoretic quantities involving the Total Variation. In the low-privacy regime, the lower bounds reduce to the non-private lower bounds. We propose $\epsilon$-local DP and $\epsilon$-global DP variants of a Top Two algorithm, namely CTB-TT and AdaP-TT*, respectively. For $\epsilon$-local DP, CTB-TT is asymptotically optimal by plugging in a private estimator of the means based on Randomised Response. For $\epsilon$-global DP, our private estimator of the mean runs in arm-dependent adaptive episodes and adds Laplace noise to ensure a good privacy-utility trade-off. By adapting the transportation costs, the expected sample complexity of AdaP-TT* reaches the asymptotic lower bound up to multiplicative constants.
- Abstract（参考訳）: BAI問題(Best Arm Identification)は、適応型臨床試験の設計、ハイパーパラメータのチューニング、ユーザスタディの実行など、データに敏感なアプリケーションに徐々に使用されている。
これらのアプリケーションによって引き起こされるデータプライバシの懸念に触発されて、ローカルモデルと中央モデルの両方において、BAIの問題、すなわち、$\epsilon$-local と $\epsilon$-global Differential Privacy (DP) について検討する。
まず、プライバシのコストを定量化するために、$\epsilon$-global DPまたは$\epsilon$-local DPを満たす$\delta$-correct BAIアルゴリズムのサンプル複雑さの低い境界を導出する。
下限は2つのプライバシー体制の存在を示唆している。
高民権体制では、その硬さは、プライバシーと、トータル変量を含む新しい情報理論量の複合効果に依存する。
低プライバシー体制では、下限は非私的下限に減少する。
我々は,トップ2アルゴリズム,すなわち CTB-TT と AdaP-TT* のそれぞれに対して,$\epsilon$-local DP と $\epsilon$-global DP の変種を提案する。
$\epsilon$-local DP の場合、CTB-TT はランダム化された応答に基づく手段のプライベートな推定器を差し込むことで漸近的に最適である。
$$\epsilon$-global DPの場合、当社のプライベートな推定器は、アーム依存のアダプティブなエピソードを実行し、Laplaceノイズを追加して、優れたプライバシーとユーティリティのトレードオフを保証する。
輸送コストに適応することにより、AdaP-TT*の期待されるサンプルの複雑さは、乗法定数までの漸近的下界に達する。
関連論文リスト
- Fixed-Budget Differentially Private Best Arm Identification [62.36929749450298]
差分プライバシー制約下における固定予算制度における線形包帯のベストアーム識別(BAI)について検討した。
誤差確率に基づいてミニマックス下限を導出し、下限と上限が指数関数的に$T$で崩壊することを示した。
論文 参考訳（メタデータ） (2024-01-17T09:23:25Z) - A Generalized Shuffle Framework for Privacy Amplification: Strengthening Privacy Guarantees and Enhancing Utility [4.7712438974100255]
パーソナライズされたプライバシパラメータで$(epsilon_i,delta_i)$-PLDP設定をシャッフルする方法を示す。
shuffled $(epsilon_i,delta_i)$-PLDP process approximately saves $mu$-Gaussian Differential Privacy with mu = sqrtfrac2sum_i=1n frac1-delta_i1+eepsilon_i-max_ifrac1-delta_i1+e
論文 参考訳（メタデータ） (2023-12-22T02:31:46Z) - On the Complexity of Differentially Private Best-Arm Identification with
Fixed Confidence [16.295693624977563]
我々は、$epsilon$-global Differential Privacyの下で、信頼度を固定したベストアーム識別の問題について検討する。
われわれの限界は、プライバシー予算によって2つのプライバシー体制が存在することを示唆している。
我々はトップ2アルゴリズムの$epsilon$-global DP変種であるAdaP-TTを提案する。
論文 参考訳（メタデータ） (2023-09-05T13:07:25Z) - When Privacy Meets Partial Information: A Refined Analysis of
Differentially Private Bandits [4.964737844687583]
我々は、$epsilon$-global Differential Privacy (DP) を用いたマルチアームバンディットの問題点について検討する。
我々は、UCBおよびKL-UCBアルゴリズム、すなわちAdaP-UCBとAdaP-KLUCBの$epsilon$-global DP拡張をインスタンス化する。
AdaP-KLUCBは、どちらも$epsilon$-global DPを満たす最初のアルゴリズムであり、問題依存の下位境界を乗法定数に一致する後悔の上限を与える。
論文 参考訳（メタデータ） (2022-09-06T15:26:24Z) - Normalized/Clipped SGD with Perturbation for Differentially Private
Non-Convex Optimization [94.06564567766475]
DP-SGDとDP-NSGDは、センシティブなトレーニングデータを記憶する大規模モデルのリスクを軽減する。
DP-NSGD は DP-SGD よりも比較的チューニングが比較的容易であるのに対して,これらの2つのアルゴリズムは同様の精度を実現する。
論文 参考訳（メタデータ） (2022-06-27T03:45:02Z) - Individual Privacy Accounting for Differentially Private Stochastic Gradient Descent [69.14164921515949]
DP-SGDで訓練されたモデルをリリースする際の個々の事例に対するプライバシー保証を特徴付ける。
ほとんどの例では、最悪のケースよりも強力なプライバシー保証を享受しています。
これは、モデルユーティリティの観点からは守られないグループが同時に、より弱いプライバシー保証を経験することを意味する。
論文 参考訳（メタデータ） (2022-06-06T13:49:37Z) - Smoothed Differential Privacy [55.415581832037084]
微分プライバシー(DP)は、最悪のケース分析に基づいて広く受け入れられ、広く適用されているプライバシーの概念である。
本稿では, 祝賀されたスムーズな解析の背景にある最悪の平均ケースのアイデアに倣って, DPの自然な拡張を提案する。
サンプリング手順による離散的なメカニズムはDPが予測するよりもプライベートであるのに対して,サンプリング手順による連続的なメカニズムはスムーズなDP下では依然としてプライベートではないことが証明された。
論文 参考訳（メタデータ） (2021-07-04T06:55:45Z) - Learning with User-Level Privacy [61.62978104304273]
ユーザレベルの差分プライバシー制約下での学習課題を,アルゴリズムを用いて解析する。
個々のサンプルのプライバシーのみを保証するのではなく、ユーザレベルのdpはユーザの貢献全体を保護します。
プライバシコストが$tau$に比例した$K$適応的に選択されたクエリのシーケンスにプライベートに答えるアルゴリズムを導き出し、私たちが検討する学習タスクを解決するためにそれを適用します。
論文 参考訳（メタデータ） (2021-02-23T18:25:13Z) - Private Stochastic Non-Convex Optimization: Adaptive Algorithms and
Tighter Generalization Bounds [72.63031036770425]
有界非次元最適化のための差分プライベート(DP)アルゴリズムを提案する。
標準勾配法に対する経験的優位性について,2つの一般的なディープラーニング手法を実証する。
論文 参考訳（メタデータ） (2020-06-24T06:01:24Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。