論文の概要: Concentrated Differential Privacy for Bandits

• arxiv url: http://arxiv.org/abs/2309.00557v2
• Date: Thu, 15 Feb 2024 17:44:24 GMT
• ステータス: 処理完了
• システム内更新日: 2024-02-16 21:17:07.779906
• Title: Concentrated Differential Privacy for Bandits
• Title（参考訳）: バンディットの集中的微分プライバシー
• Authors: Achraf Azize, Debabrota Basu
• Abstract要約: 本稿では,信頼性の高い集中型意思決定者による盗賊の識別プライバシー(DP)の理解に寄与する。 本稿では,AdaC-UCB,AdaC-GOPE,AdaC-OFULの3つのプライベートアルゴリズムを提案する。
• 参考スコア（独自算出の注目度）: 13.097161185372153
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Bandits serve as the theoretical foundation of sequential learning and an algorithmic foundation of modern recommender systems. However, recommender systems often rely on user-sensitive data, making privacy a critical concern. This paper contributes to the understanding of Differential Privacy (DP) in bandits with a trusted centralised decision-maker, and especially the implications of ensuring zero Concentrated Differential Privacy (zCDP). First, we formalise and compare different adaptations of DP to bandits, depending on the considered input and the interaction protocol. Then, we propose three private algorithms, namely AdaC-UCB, AdaC-GOPE and AdaC-OFUL, for three bandit settings, namely finite-armed bandits, linear bandits, and linear contextual bandits. The three algorithms share a generic algorithmic blueprint, i.e. the Gaussian mechanism and adaptive episodes, to ensure a good privacy-utility trade-off. We analyse and upper bound the regret of these three algorithms. Our analysis shows that in all of these settings, the prices of imposing zCDP are (asymptotically) negligible in comparison with the regrets incurred oblivious to privacy. Next, we complement our regret upper bounds with the first minimax lower bounds on the regret of bandits with zCDP. To prove the lower bounds, we elaborate a new proof technique based on couplings and optimal transport. We conclude by experimentally validating our theoretical results for the three different settings of bandits.
• Abstract（参考訳）: バンディットは逐次学習の理論的基礎であり、現代のレコメンデーションシステムのアルゴリズム的基礎である。 しかしながら、レコメンデータシステムは、しばしばユーザセンシティブなデータに依存し、プライバシーが重要な懸念事項となっている。 本稿では,集中型意思決定者によるバンディットにおけるディファレンシャルプライバシ(dp)の理解,特に集中型ディファレンシャルプライバシ(zcdp)の確保の意義について述べる。 まず, dpとバンドイットの異なる適応を, 入力と相互作用プロトコルに応じて形式化し比較する。 次に,有限腕バンディット,線形バンディット,線形コンテキストバンディットの3つのバンディット設定に対して,adac-ucb,adac-gope,adac-ofulの3つのプライベートアルゴリズムを提案する。 3つのアルゴリズムは、適切なプライバシー利用のトレードオフを確保するために、gaussian mechanismとadaptive episodesという、一般的なアルゴリズムの青写真を共有する。 これら3つのアルゴリズムの後悔を解析し、上位に並べる。 われわれの分析によると、これらの設定のすべてにおいて、zCDPを挿入する価格は(漸近的に)プライバシーを損なう後悔と比べて無視できる。 次に,ZCDP による盗賊の遺残に対する第1のミニマックス下限を補完する。 低境界を証明するために,結合と最適輸送に基づく新しい証明手法を提案する。 バンドの3つの異なる設定に対する理論的結果を実験的に検証して結論付ける。

関連論文リスト

• 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)

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

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