論文の概要: When Privacy Meets Partial Information: A Refined Analysis of
Differentially Private Bandits
- arxiv url: http://arxiv.org/abs/2209.02570v1
- Date: Tue, 6 Sep 2022 15:26:24 GMT
- ステータス: 処理完了
- システム内更新日: 2022-09-07 13:26:24.365303
- Title: When Privacy Meets Partial Information: A Refined Analysis of
Differentially Private Bandits
- Title（参考訳）: プライバシーが部分的情報と出会うとき: 異なる個人的帯域の精査分析
- Authors: Achraf Azize and Debabrota Basu
- Abstract要約: 我々は、$epsilon$-global Differential Privacy (DP) を用いたマルチアームバンディットの問題点について検討する。
我々は、UCBおよびKL-UCBアルゴリズム、すなわちAdaP-UCBとAdaP-KLUCBの$epsilon$-global DP拡張をインスタンス化する。
AdaP-KLUCBは、どちらも$epsilon$-global DPを満たす最初のアルゴリズムであり、問題依存の下位境界を乗法定数に一致する後悔の上限を与える。
- 参考スコア（独自算出の注目度）: 4.964737844687583
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We study the problem of multi-armed bandits with $\epsilon$-global
Differential Privacy (DP). First, we prove the minimax and problem-dependent
regret lower bounds for stochastic and linear bandits that quantify the
hardness of bandits with $\epsilon$-global DP. These bounds suggest the
existence of two hardness regimes depending on the privacy budget $\epsilon$.
In the high-privacy regime (small $\epsilon$), the hardness depends on a
coupled effect of privacy and partial information about the reward
distributions. In the low-privacy regime (large $\epsilon$), bandits with
$\epsilon$-global DP are not harder than the bandits without privacy. For
stochastic bandits, we further propose a generic framework to design a
near-optimal $\epsilon$ global DP extension of an index-based optimistic bandit
algorithm. The framework consists of three ingredients: the Laplace mechanism,
arm-dependent adaptive episodes, and usage of only the rewards collected in the
last episode for computing private statistics. Specifically, we instantiate
$\epsilon$-global DP extensions of UCB and KL-UCB algorithms, namely AdaP-UCB
and AdaP-KLUCB. AdaP-KLUCB is the first algorithm that both satisfies
$\epsilon$-global DP and yields a regret upper bound that matches the
problem-dependent lower bound up to multiplicative constants.
- Abstract（参考訳）: 我々は,多腕バンディットの問題を$\epsilon$-global Differential Privacy (DP)を用いて検討した。
まず, バンディットの硬度を$\epsilon$-global dpで定量化する確率的および線形なバンディットに対して, 最小値と問題依存の後悔値下限を証明した。
これらの境界は、プライバシー予算$\epsilon$に依存する2つの硬度制度の存在を示唆している。
高プライバシー体制(小さな$\epsilon$)では、ハードネスは、プライバシと報酬分配に関する部分的情報の組み合わせによる影響に依存する。
低プライバシー体制(大きな$\epsilon$)では、$\epsilon$-global dpのバンディットはプライバシーのないバンディットよりも難しくない。
確率的バンディットに対しては、インデックスベースの楽観的バンディットアルゴリズムの最適に近い$\epsilon$ global dp拡張を設計するための汎用フレームワークも提案する。
フレームワークは、Laplaceメカニズム、アーム依存適応エピソード、および前回で収集された報酬のみを使用したプライベート統計計算の3つの要素で構成されている。
具体的には、UCBおよびKL-UCBアルゴリズム、すなわちAdaP-UCBとAdaP-KLUCBの$\epsilon$-global DP拡張をインスタンス化する。
AdaP-KLUCBは、ともに$\epsilon$-global DPを満たす最初のアルゴリズムであり、問題依存の下位境界を乗法定数に一致する後悔の上限を与える。
関連論文リスト
- Differentially Private Best-Arm Identification [14.916947598339988]
ベストアーム識別(BAI)問題は、データセンシティブなアプリケーションに徐々に使われている。
これらのアプリケーションによって引き起こされるデータプライバシの懸念に触発され、ローカルモデルと中央モデルの両方に一定の信頼を保ちながら、BAIの問題を研究する。
論文 参考訳（メタデータ） (2024-06-10T16:02:48Z) - Fixed-Budget Differentially Private Best Arm Identification [62.36929749450298]
差分プライバシー制約下における固定予算制度における線形包帯のベストアーム識別(BAI)について検討した。
誤差確率に基づいてミニマックス下限を導出し、下限と上限が指数関数的に$T$で崩壊することを示した。
論文 参考訳（メタデータ） (2024-01-17T09:23:25Z) - Combinatorial Stochastic-Greedy Bandit [79.1700188160944]
我々は,選択した$n$のアームセットのジョイント報酬以外の余分な情報が観測されない場合に,マルチアームのバンディット問題に対する新規グリーディ・バンディット(SGB)アルゴリズムを提案する。
SGBは最適化された拡張型コミットアプローチを採用しており、ベースアームの大きなセットを持つシナリオ用に特別に設計されている。
論文 参考訳（メタデータ） (2023-12-13T11:08:25Z) - 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) - Federated Linear Contextual Bandits with User-level Differential Privacy [8.396384861175799]
本稿では,ユーザレベル差分プライバシ(DP)の概念に基づく連立線形文脈帯域について検討する。
まず,DP の様々な定義を逐次決定設定で適用可能な統合された帯域幅フレームワークを提案する。
次に, ユーザレベルの集中型DP (CDP) とローカルDP (LDP) をフェデレート・バンディット・フレームワークに正式に導入し, 学習後悔と対応するDP保証との根本的なトレードオフについて検討する。
論文 参考訳（メタデータ） (2023-06-08T15:21:47Z) - 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) - Learning with User-Level Privacy [61.62978104304273]
ユーザレベルの差分プライバシー制約下での学習課題を,アルゴリズムを用いて解析する。
個々のサンプルのプライバシーのみを保証するのではなく、ユーザレベルのdpはユーザの貢献全体を保護します。
プライバシコストが$tau$に比例した$K$適応的に選択されたクエリのシーケンスにプライベートに答えるアルゴリズムを導き出し、私たちが検討する学習タスクを解決するためにそれを適用します。
論文 参考訳（メタデータ） (2021-02-23T18:25:13Z) - Stochastic Linear Bandits Robust to Adversarial Attacks [117.665995707568]
我々はロバスト位相除去アルゴリズムの2つの変種を提供し、その1つは$C$を知っており、もう1つはそうでない。
いずれの変種も、倒壊しない場合には、それぞれ$C = 0$ となり、それぞれ追加の加法項が生じる。
文脈的設定では、単純な欲求的アルゴリズムは、明示的な探索を行わず、C$を知らないにもかかわらず、ほぼ最適加法的後悔項で証明可能な堅牢性を示す。
論文 参考訳（メタデータ） (2020-07-07T09:00:57Z) - Locally Differentially Private (Contextual) Bandits Learning [55.63825598391525]
本論文では,局所的差分性(LDP)バンディット学習について検討する。
我々は,DP保証を用いて,文脈自由な帯域幅学習問題を解くことのできる,シンプルなブラックボックス削減フレームワークを提案する。
論文 参考訳（メタデータ） (2020-06-01T04:02:00Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。