論文の概要: Interactive and Concentrated Differential Privacy for Bandits
- arxiv url: http://arxiv.org/abs/2309.00557v1
- Date: Fri, 1 Sep 2023 16:08:00 GMT
- ステータス: 処理完了
- システム内更新日: 2023-09-04 13:01:36.340278
- Title: Interactive and Concentrated Differential Privacy for Bandits
- Title（参考訳）: バンドの対話型および集中型微分プライバシー
- Authors: Achraf Azize, Debabrota Basu
- Abstract要約: 本稿では,対話型微分プライバシ(DP)のレンズを用いた信頼性の高い集中型意思決定者との盗聴者のプライバシーについて検討する。
有限武装および線形バンディットに対する後悔の最小限と問題依存の下位境界を提供する。
AdaC-UCBとAdaC-GOPEの2つのZCDP帯域幅アルゴリズムを,それぞれ有限武装および線形帯域幅に対して提案する。
- 参考スコア（独自算出の注目度）: 13.097161185372153
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Bandits play a crucial role in interactive learning schemes and modern
recommender systems. However, these systems often rely on sensitive user data,
making privacy a critical concern. This paper investigates privacy in bandits
with a trusted centralized decision-maker through the lens of interactive
Differential Privacy (DP). While bandits under pure $\epsilon$-global DP have
been well-studied, we contribute to the understanding of bandits under zero
Concentrated DP (zCDP). We provide minimax and problem-dependent lower bounds
on regret for finite-armed and linear bandits, which quantify the cost of
$\rho$-global zCDP in these settings. These lower bounds reveal two hardness
regimes based on the privacy budget $\rho$ and suggest that $\rho$-global zCDP
incurs less regret than pure $\epsilon$-global DP. We propose two $\rho$-global
zCDP bandit algorithms, AdaC-UCB and AdaC-GOPE, for finite-armed and linear
bandits respectively. Both algorithms use a common recipe of Gaussian mechanism
and adaptive episodes. We analyze the regret of these algorithms to show that
AdaC-UCB achieves the problem-dependent regret lower bound up to multiplicative
constants, while AdaC-GOPE achieves the minimax regret lower bound up to
poly-logarithmic factors. Finally, we provide experimental validation of our
theoretical results under different settings.
- Abstract（参考訳）: バンドはインタラクティブな学習スキームやモダンな推薦システムにおいて重要な役割を果たす。
しかし、これらのシステムはセンシティブなユーザーデータに依存することが多く、プライバシーが重要な問題となっている。
本稿では,対話型微分プライバシー(DP)のレンズを用いて,信頼度の高い意思決定者との盗聴者のプライバシーについて検討する。
純粋な$\epsilon$-global DPの下でのバンディットはよく研究されているが、ゼロ集中DP(zCDP)下でのバンディットの理解に寄与している。
有限武装および線形バンディットに対する後悔の最小値と問題依存の下限を提供し、これらの設定において$\rho$-global zCDP のコストを定量化する。
これらの下限は、プライバシー予算$\rho$に基づく2つの厳しい体制を明らかにし、$\rho$-global zCDPが純粋な$\epsilon$-global DPよりも後悔の少ないことを示唆している。
AdaC-UCBとAdaC-GOPEの2つのZCDP帯域幅アルゴリズムを,それぞれ有限武装および線形帯域幅に対して提案する。
どちらのアルゴリズムもガウス機構と適応エピソードの共通のレシピを使用している。
AdaC-UCBは問題依存的後悔を乗法定数まで下げる一方、AdaC-GOPEは最小最大後悔を多対数因子まで下げることを示すために、これらのアルゴリズムの後悔を分析する。
最後に, 異なる条件下での理論的結果の実験的検証を行う。
関連論文リスト
- Feel-Good Thompson Sampling for Contextual Dueling Bandits [49.450050682705026]
FGTS.CDBという名前のトンプソンサンプリングアルゴリズムを提案する。
われわれのアルゴリズムの核心は、デュエルバンディットに適した新しいFeel-Good探索用語である。
我々のアルゴリズムは最小限の誤差、すなわち $tildemathcalO(dsqrt T)$, $d$ はモデル次元、$T$ は時間水平線である。
論文 参考訳（メタデータ） (2024-04-09T04:45:18Z) - On Differentially Private Federated Linear Contextual Bandits [9.51828574518325]
我々は、差分プライバシーの下で、クロスサイロフェデレーション線形文脈帯域問題(LCB)を考える。
現状の3つの課題は, (i) 主張されたプライバシ保護の失敗, (ii) ノイズの計算ミスによる不正確な後悔,である。
我々は,信頼されたサーバを使わずに,アルゴリズムがほぼ最適であることを示す。
論文 参考訳（メタデータ） (2023-02-27T16:47:49Z) - Contextual bandits with concave rewards, and an application to fair
ranking [108.48223948875685]
CBCR (Contextual Bandits with Concave Rewards) に対する反省点のある最初のアルゴリズムを提案する。
我々は,スカラー・リワード問題に対するCBCRの後悔から,新たな縮小を導出した。
推薦の公正さによって動機づけられたCBCRの特別事例として,ランク付けと公正を意識した目的について述べる。
論文 参考訳（メタデータ） (2022-10-18T16:11:55Z) - 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) - Versatile Dueling Bandits: Best-of-both-World Analyses for Online
Learning from Preferences [28.79598714109439]
両環境および敵環境における$K$武器のデュエルバンディットの問題について検討する。
まず,マルチアームのバンディットに対して,任意の(一般的な)デュエル・バンドレットから新たなリダクションを提案する。
提案アルゴリズムは,コンドルチェット・ウィンナーベンチマークに対して最適な$O(sum_i = 1K fraclog TDelta_i)$ regret boundを達成した最初のアルゴリズムでもある。
論文 参考訳（メタデータ） (2022-02-14T13:37:23Z) - Bayesian decision-making under misspecified priors with applications to
meta-learning [64.38020203019013]
トンプソンサンプリングやその他のシーケンシャルな意思決定アルゴリズムは、文脈的包帯における探索と探索のトレードオフに取り組むための一般的なアプローチである。
性能は不特定な事前条件で優雅に低下することを示す。
論文 参考訳（メタデータ） (2021-07-03T23:17:26Z) - Bias-Robust Bayesian Optimization via Dueling Bandit [57.82422045437126]
ベイジアン最適化は、観測が逆偏りとなるような環境において考慮する。
情報指向サンプリング(IDS)に基づくダリングバンディットの新しい手法を提案する。
これにより、累積的後悔保証を伴う帯域幅の並列化のための、最初の効率的なカーネル化アルゴリズムが得られる。
論文 参考訳（メタデータ） (2021-05-25T10:08:41Z) - Upper Confidence Bounds for Combining Stochastic Bandits [52.10197476419621]
バンディットアルゴリズムを結合する簡単な手法を提案する。
私たちのアプローチは、個々のbanditアルゴリズムのそれぞれを、より高いレベルのn$-armed bandit問題のアームとして扱う"meta-ucb"手順に基づいています。
論文 参考訳（メタデータ） (2020-12-24T05:36:29Z) - Locally Differentially Private (Contextual) Bandits Learning [55.63825598391525]
本論文では,局所的差分性(LDP)バンディット学習について検討する。
我々は,DP保証を用いて,文脈自由な帯域幅学習問題を解くことのできる,シンプルなブラックボックス削減フレームワークを提案する。
論文 参考訳（メタデータ） (2020-06-01T04:02:00Z) - Bandit algorithms to emulate human decision making using probabilistic
distortions [20.422725678982726]
報奨分布に歪んだ確率を持つ2つの多重武装バンディット問題を定式化する。
以上のような後悔の最小化の問題と、マルチアームバンディットのための最高の腕識別フレームワークについて考察する。
論文 参考訳（メタデータ） (2016-11-30T17:37:51Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。