論文の概要: On the Complexity of Differentially Private Best-Arm Identification with Fixed Confidence

• arxiv url: http://arxiv.org/abs/2309.02202v1
• Date: Tue, 5 Sep 2023 13:07:25 GMT
• ステータス: 処理完了
• システム内更新日: 2023-09-06 14:42:48.068122
• Title: On the Complexity of Differentially Private Best-Arm Identification with Fixed Confidence
• Title（参考訳）: 固定信頼度を持つ微分プライベートベストアーム識別の複雑さについて
• Authors: Achraf Azize, Marc Jourdan, Aymen Al Marjani, Debabrota Basu
• Abstract要約: 我々は、$epsilon$-global Differential Privacyの下で、信頼度を固定したベストアーム識別の問題について検討する。 われわれの限界は、プライバシー予算によって2つのプライバシー体制が存在することを示唆している。 我々はトップ2アルゴリズムの$epsilon$-global DP変種であるAdaP-TTを提案する。
• 参考スコア（独自算出の注目度）: 16.295693624977563
• 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 to name a few. Motivated by the data privacy concerns invoked by these applications, we study the problem of BAI with fixed confidence under $\epsilon$-global Differential Privacy (DP). First, to quantify the cost of privacy, we derive a lower bound on the sample complexity of any $\delta$-correct BAI algorithm satisfying $\epsilon$-global DP. Our lower bound suggests the existence of two privacy regimes depending on the privacy budget $\epsilon$. In the high-privacy regime (small $\epsilon$), the hardness depends on a coupled effect of privacy and a novel information-theoretic quantity, called the Total Variation Characteristic Time. In the low-privacy regime (large $\epsilon$), the sample complexity lower bound reduces to the classical non-private lower bound. Second, we propose AdaP-TT, an $\epsilon$-global DP variant of the Top Two algorithm. AdaP-TT runs in arm-dependent adaptive episodes and adds Laplace noise to ensure a good privacy-utility trade-off. We derive an asymptotic upper bound on the sample complexity of AdaP-TT that matches with the lower bound up to multiplicative constants in the high-privacy regime. Finally, we provide an experimental analysis of AdaP-TT that validates our theoretical results.
• Abstract（参考訳）: BAI問題(Best Arm Identification)は、適応型臨床試験の設計、ハイパーパラメータのチューニング、ユーザスタディの実施など、データセンシティブなアプリケーションに徐々に使用されている。 これらのアプリケーションによって引き起こされるデータプライバシの懸念に動機づけられて, bai の問題を $\epsilon$-global differential privacy (dp) の下で固定信頼で検討した。 まず、プライバシのコストを定量化するために、$\epsilon$-global DPを満たす任意の$\delta$-correct BAIアルゴリズムのサンプル複雑性を低くする。 われわれの限界は、プライバシー予算$\epsilon$に依存する2つのプライバシー体制の存在を示唆している。 高プライバシー体制(小さな$\epsilon$)では、ハードネスはプライバシーの結合効果と、総変動特性時間と呼ばれる新しい情報理論量に依存する。 低プライバシーのレジーム(大きな$\epsilon$)では、サンプル複雑性の下限は古典的な非プライベートな下限に還元される。 第2に、トップ2アルゴリズムの$\epsilon$-global DP変種であるAdaP-TTを提案する。 AdaP-TTはアーム依存の適応エピソードで動作し、優れたプライバシーユーティリティトレードオフを保証するためにLaplaceノイズを追加する。 我々は,AdaP-TTのサンプル複雑性に基づく漸近上界の導出を行う。 最後に,adap-ttの実験的解析を行い,理論結果の検証を行った。

関連論文リスト

• Differentially Private Best-Arm Identification [14.916947598339988]
  ベストアーム識別(BAI)問題は、データセンシティブなアプリケーションに徐々に使われている。 これらのアプリケーションによって引き起こされるデータプライバシの懸念に触発され、ローカルモデルと中央モデルの両方に一定の信頼を保ちながら、BAIの問題を研究する。
  論文  参考訳（メタデータ） (2024-06-10T16:02:48Z)
• FLIPHAT: Joint Differential Privacy for High Dimensional Sparse Linear Bandits [8.908421753758475]
  高次元スパース線形帯域は、シーケンシャルな意思決定問題の効率的なモデルとして機能する。 データプライバシの懸念により、我々は、共同でプライベートな高次元の疎線形帯域について検討する。 FLIPHATは,プライバシパラメータの点で最適に後悔することを示す。
  論文  参考訳（メタデータ） (2024-05-22T22:19:12Z)
• 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 Differential Privacy and Adaptive Data Analysis with Bounded Space [76.10334958368618]
  差分プライバシーと適応データ分析の2つの関連分野の空間複雑性について検討する。 差分プライバシーで効率的に解くために指数関数的に多くの空間を必要とする問題Pが存在することを示す。 アダプティブデータ分析の研究の行は、アダプティブクエリのシーケンスに応答するのに必要なサンプルの数を理解することに焦点を当てている。
  論文  参考訳（メタデータ） (2023-02-11T14:45:31Z)
• 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)
• Learning with User-Level Privacy [61.62978104304273]
  ユーザレベルの差分プライバシー制約下での学習課題を,アルゴリズムを用いて解析する。 個々のサンプルのプライバシーのみを保証するのではなく、ユーザレベルのdpはユーザの貢献全体を保護します。 プライバシコストが$tau$に比例した$K$適応的に選択されたクエリのシーケンスにプライベートに答えるアルゴリズムを導き出し、私たちが検討する学習タスクを解決するためにそれを適用します。
  論文  参考訳（メタデータ） (2021-02-23T18:25:13Z)
• Hiding Among the Clones: A Simple and Nearly Optimal Analysis of Privacy Amplification by Shuffling [49.43288037509783]
  ランダムシャッフルは、局所的ランダム化データの差分プライバシー保証を増幅する。 私たちの結果は、以前の作業よりも単純で、ほぼ同じ保証で差分プライバシーに拡張された新しいアプローチに基づいています。
  論文  参考訳（メタデータ） (2020-12-23T17:07:26Z)

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

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