論文の概要: Optimal Regret of Bernoulli Bandits under Global Differential Privacy
- arxiv url: http://arxiv.org/abs/2505.05613v1
- Date: Thu, 08 May 2025 19:48:58 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-05-12 20:40:10.066443
- Title: Optimal Regret of Bernoulli Bandits under Global Differential Privacy
- Title（参考訳）: ベルヌーイ・バンドのグローバルな差別的プライバシーの下での最適再編成
- Authors: Achraf Azize, Yulian Wu, Junya Honda, Francesco Orabona, Shinji Ito, Debabrota Basu,
- Abstract要約: エプシロン$-global Differential Privacy (DP) による包帯のレグレット最小化が広く研究されている。
我々はベルヌーイのバンディットに対する$epsilon-global DPアルゴリズムの残酷な下限と上限を再検討し、両者を改善した。
- 参考スコア（独自算出の注目度）: 44.25744563135375
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: As sequential learning algorithms are increasingly applied to real life, ensuring data privacy while maintaining their utilities emerges as a timely question. In this context, regret minimisation in stochastic bandits under $\epsilon$-global Differential Privacy (DP) has been widely studied. Unlike bandits without DP, there is a significant gap between the best-known regret lower and upper bound in this setting, though they "match" in order. Thus, we revisit the regret lower and upper bounds of $\epsilon$-global DP algorithms for Bernoulli bandits and improve both. First, we prove a tighter regret lower bound involving a novel information-theoretic quantity characterising the hardness of $\epsilon$-global DP in stochastic bandits. Our lower bound strictly improves on the existing ones across all $\epsilon$ values. Then, we choose two asymptotically optimal bandit algorithms, i.e. DP-KLUCB and DP-IMED, and propose their DP versions using a unified blueprint, i.e., (a) running in arm-dependent phases, and (b) adding Laplace noise to achieve privacy. For Bernoulli bandits, we analyse the regrets of these algorithms and show that their regrets asymptotically match our lower bound up to a constant arbitrary close to 1. This refutes the conjecture that forgetting past rewards is necessary to design optimal bandit algorithms under global DP. At the core of our algorithms lies a new concentration inequality for sums of Bernoulli variables under Laplace mechanism, which is a new DP version of the Chernoff bound. This result is universally useful as the DP literature commonly treats the concentrations of Laplace noise and random variables separately, while we couple them to yield a tighter bound.
- Abstract（参考訳）: シーケンシャルな学習アルゴリズムが現実の生活に適用されるにつれて、ユーティリティを維持しながらデータのプライバシを確保することが、タイムリーな疑問として現れます。
この文脈では、$\epsilon$-global Differential Privacy (DP) に基づく確率的包帯における後悔の最小化が広く研究されている。
DPのないバンディットとは異なり、この設定では最もよく知られた後悔と上界の間には大きなギャップがあるが、それらは順に「マッチ」する。
そこで我々はベルヌーイの盗賊に対する$\epsilon$-global DPアルゴリズムの左下と上の境界を再検討し、その両方を改善する。
まず,確率的包帯における$\epsilon$-global DPの硬さを特徴付ける新しい情報理論量を含む,より深い後悔の少ない境界を証明した。
私たちの低いバウンダリは、すべての$\epsilon$値で既存のバウンダリを厳密に改善します。
次に,DP-KLUCBとDP-IMEDという漸近的に最適な帯域幅アルゴリズムを2つ選択し,統一青写真を用いてDPバージョンを提案する。
(a)腕依存フェーズで動作し、
(b)プライバシーを達成するためにLaplaceノイズを追加する。
ベルヌーイの盗賊たちにとって、これらのアルゴリズムの後悔を分析し、それらの後悔が漸近的に我々の下界を 1 に一定に近くなることを示す。
このことは、グローバルDPの下で最適な帯域幅アルゴリズムを設計するには過去の報酬を忘れる必要があるという予想を否定する。
我々のアルゴリズムの中核には、Laplace機構の下でベルヌーイ変数の和に対する新しい集中不等式があり、これはチャーノフ境界の新しいDPバージョンである。
この結果は一般に有用であり、DP文献ではラプラスノイズとランダム変数の濃度を別々に扱うのが一般的である。
関連論文リスト
- Differentially Private Best-Arm Identification [14.916947598339988]
ベストアーム識別(BAI)問題は、データセンシティブなアプリケーションに徐々に使われている。
これらのアプリケーションによって引き起こされるデータプライバシの懸念に触発され、ローカルモデルと中央モデルの両方に一定の信頼を保ちながら、BAIの問題を研究する。
論文 参考訳（メタデータ） (2024-06-10T16:02:48Z) - Variance-Dependent Regret Bounds for Non-stationary Linear Bandits [52.872628573907434]
報酬分布の分散と$B_K$の分散を利用するアルゴリズムを提案する。
Restarted Weighted$textOFUL+$とRestarted$textSAVE+$の2つの新しいアルゴリズムを紹介します。
特に、V_K$が$K$よりはるかに小さい場合、我々のアルゴリズムは、異なる設定下での非定常線形バンドレットの最先端結果よりも優れている。
論文 参考訳（メタデータ） (2024-03-15T23:36:55Z) - Variance-Aware Regret Bounds for Stochastic Contextual Dueling Bandits [53.281230333364505]
本稿では, 一般化線形モデル(GLM)から, デュエルアームのバイナリ比較を生成するコンテキストデュエルバンド問題について検討する。
本稿では,SupLinUCB型アルゴリズムを提案する。このアルゴリズムは,計算効率と分散を意識したリセットバウンド$tilde Obig(dsqrtsum_t=1Tsigma_t2 + dbig)$を提案する。
我々の後悔は、比較が決定論的である場合の直感的な期待と自然に一致し、アルゴリズムは$tilde O(d)$ regretにのみ悩まされる。
論文 参考訳（メタデータ） (2023-10-02T08:15:52Z) - Concentrated Differential Privacy for Bandits [11.086440815804227]
本稿では,信頼性の高い集中型意思決定者による盗賊の識別プライバシー(DP)の理解に寄与する。
本稿では,AdaC-UCB,AdaC-GOPE,AdaC-OFULの3つのプライベートアルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-09-01T16:08:00Z) - Federated Linear Contextual Bandits with User-level Differential Privacy [8.396384861175799]
本稿では,ユーザレベル差分プライバシ(DP)の概念に基づく連立線形文脈帯域について検討する。
まず,DP の様々な定義を逐次決定設定で適用可能な統合された帯域幅フレームワークを提案する。
次に, ユーザレベルの集中型DP (CDP) とローカルDP (LDP) をフェデレート・バンディット・フレームワークに正式に導入し, 学習後悔と対応するDP保証との根本的なトレードオフについて検討する。
論文 参考訳（メタデータ） (2023-06-08T15:21:47Z) - 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) - Private Stochastic Non-Convex Optimization: Adaptive Algorithms and
Tighter Generalization Bounds [72.63031036770425]
有界非次元最適化のための差分プライベート(DP)アルゴリズムを提案する。
標準勾配法に対する経験的優位性について,2つの一般的なディープラーニング手法を実証する。
論文 参考訳（メタデータ） (2020-06-24T06:01:24Z) - Locally Differentially Private (Contextual) Bandits Learning [55.63825598391525]
本論文では,局所的差分性(LDP)バンディット学習について検討する。
我々は,DP保証を用いて,文脈自由な帯域幅学習問題を解くことのできる,シンプルなブラックボックス削減フレームワークを提案する。
論文 参考訳（メタデータ） (2020-06-01T04:02:00Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。