論文の概要: Fixed-Budget Differentially Private Best Arm Identification
- arxiv url: http://arxiv.org/abs/2401.09073v1
- Date: Wed, 17 Jan 2024 09:23:25 GMT
- ステータス: 処理完了
- システム内更新日: 2024-01-18 16:27:25.440162
- Title: Fixed-Budget Differentially Private Best Arm Identification
- Title（参考訳）: 固定予算別個人別ベストアーム識別
- Authors: Zhirui Chen, P. N. Karthik, Yeow Meng Chee, and Vincent Y. F. Tan
- Abstract要約: 差分プライバシー制約下における固定予算制度における線形包帯のベストアーム識別(BAI)について検討した。
誤差確率に基づいてミニマックス下限を導出し、下限と上限が指数関数的に$T$で崩壊することを示した。
- 参考スコア（独自算出の注目度）: 62.36929749450298
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We study best arm identification (BAI) in linear bandits in the fixed-budget
regime under differential privacy constraints, when the arm rewards are
supported on the unit interval. Given a finite budget $T$ and a privacy
parameter $\varepsilon>0$, the goal is to minimise the error probability in
finding the arm with the largest mean after $T$ sampling rounds, subject to the
constraint that the policy of the decision maker satisfies a certain {\em
$\varepsilon$-differential privacy} ($\varepsilon$-DP) constraint. We construct
a policy satisfying the $\varepsilon$-DP constraint (called {\sc DP-BAI}) by
proposing the principle of {\em maximum absolute determinants}, and derive an
upper bound on its error probability. Furthermore, we derive a minimax lower
bound on the error probability, and demonstrate that the lower and the upper
bounds decay exponentially in $T$, with exponents in the two bounds matching
order-wise in (a) the sub-optimality gaps of the arms, (b) $\varepsilon$, and
(c) the problem complexity that is expressible as the sum of two terms, one
characterising the complexity of standard fixed-budget BAI (without privacy
constraints), and the other accounting for the $\varepsilon$-DP constraint.
Additionally, we present some auxiliary results that contribute to the
derivation of the lower bound on the error probability. These results, we
posit, may be of independent interest and could prove instrumental in proving
lower bounds on error probabilities in several other bandit problems. Whereas
prior works provide results for BAI in the fixed-budget regime without privacy
constraints or in the fixed-confidence regime with privacy constraints, our
work fills the gap in the literature by providing the results for BAI in the
fixed-budget regime under the $\varepsilon$-DP constraint.
- Abstract（参考訳）: 本研究は,固定予算体制における線形バンディットにおける最良アーム識別(bai)について,単位間隔でアーム報酬が支持される場合のプライバシー制約下で検討する。
有限予算の$t$とプライバシパラメータ$\varepsilon>0$が与えられると、決定メーカーのポリシーが特定の$\varepsilon$-differential privacy} (\varepsilon$-dp) 制約を満たすという制約の下で、$t$サンプリングラウンドの後に最大の平均でアームを見つける際のエラー確率を最小化することが目標となる。
我々は, "em maximum absolute determinants} の原理を提唱することで,$\varepsilon$-dp 制約("sc dp-bai}")を満たす方針を構築し,その誤差確率の上限を導出する。
さらに、誤差確率の最小値下限を導出し、下限と上限が指数関数的に$t$で崩壊し、2つの値下限の指数が順番に一致することを証明する。
(a)腕の準最適ギャップ。
(b)$\varepsilon$、および
(c) 標準的な固定予算BAIの複雑さ(プライバシー制約なしで)を特徴付ける2項の和として表現可能な問題複雑性と、$\varepsilon$-DP制約を考慮に入れること。
さらに,誤差確率に対する下界の導出に寄与する補助的な結果を示す。
これらの結果は独立な関心を持ち、他のいくつかのバンドイット問題における誤差確率の低限界を証明するのに有用であると考えられる。
プライバシー制約のない固定予算体制におけるBAIの成果や、プライバシー制約のない固定予算体制におけるBAIの成果とは対照的に、我々は、$\varepsilon$-DP制約の下での固定予算体制におけるBAIの成果を提供することで、文献のギャップを埋める。
関連論文リスト
- Differentially Private Best-Arm Identification [14.916947598339988]
ベストアーム識別(BAI)問題は、データセンシティブなアプリケーションに徐々に使われている。
これらのアプリケーションによって引き起こされるデータプライバシの懸念に触発され、ローカルモデルと中央モデルの両方に一定の信頼を保ちながら、BAIの問題を研究する。
論文 参考訳（メタデータ） (2024-06-10T16:02:48Z) - 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) - Contextual Combinatorial Bandits with Probabilistically Triggered Arms [55.9237004478033]
確率的に誘発される腕(C$2$MAB-T)を様々な滑らかさ条件下で検討した。
トリガー変調 (TPM) 条件の下では、C$2$-UC-Tアルゴリズムを考案し、後悔すべき$tildeO(dsqrtT)$を導出する。
論文 参考訳（メタデータ） (2023-03-30T02:51:00Z) - 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) - Batch-Size Independent Regret Bounds for Combinatorial Semi-Bandits with Probabilistically Triggered Arms or Independent Arms [59.8188496313214]
半帯域 (CMAB) について検討し, 半帯域 (CMAB) におけるバッチサイズ (K$) の依存性の低減に着目した。
まず,確率的に引き起こされるアーム(CMAB-T)を用いたCMABの設定に対して,分散を考慮した信頼区間を持つBCUCB-Tアルゴリズムを提案する。
次に,独立アームを用いた非トリガ型CMABの設定に対して,TPVM条件の非トリガ型を利用したSESCBアルゴリズムを提案する。
論文 参考訳（メタデータ） (2022-08-31T13:09:39Z) - Connect the Dots: Tighter Discrete Approximations of Privacy Loss
Distributions [49.726408540784334]
PLDベースの会計の鍵となる問題は、特定の個別サポートに対してPLDと(潜在的に連続的な)PLDをどのように近似するかである。
悲観的推定はすべての悲観的推定の中で最良であることを示す。
論文 参考訳（メタデータ） (2022-07-10T04:25:02Z) - New Lower Bounds for Private Estimation and a Generalized Fingerprinting
Lemma [10.176795938619417]
統計的推定タスクの新たな下限を$(varepsilon, delta)$-differential privacyの制約の下で証明する。
フロベニウスノルムの推定には$Omega(d2)$サンプルが必要であり、スペクトルノルムでは$Omega(d3/2)$サンプルが必要である。
論文 参考訳（メタデータ） (2022-05-17T17:55:10Z) - Problem Dependent View on Structured Thresholding Bandit Problems [73.70176003598449]
我々は、Thresholding Bandit problem (TBP)における問題依存体制について検討する。
学習者の目的は、シーケンシャルゲームの終わりに、所定のしきい値を超える手段を持つアームセットを出力することである。
コンケーブ設定と単調設定の両方で誤差の確率を上下に設定する。
論文 参考訳（メタデータ） (2021-06-18T15:01:01Z) - On Lower Bounds for Standard and Robust Gaussian Process Bandit
Optimization [55.937424268654645]
有界ノルムを持つ関数のブラックボックス最適化問題に対するアルゴリズム非依存な下界を考える。
本稿では, 単純さ, 汎用性, エラー確率への依存性の向上など, 後悔の下位境界を導出するための新しい証明手法を提案する。
論文 参考訳（メタデータ） (2020-08-20T03:48:14Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。