論文の概要: Faster Rates for Private Adversarial Bandits
- arxiv url: http://arxiv.org/abs/2505.21790v1
- Date: Tue, 27 May 2025 21:42:10 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-05-29 17:35:50.308609
- Title: Faster Rates for Private Adversarial Bandits
- Title（参考訳）: 個人用逆帯域の高速化
- Authors: Hilal Asi, Vinod Raman, Kunal Talwar,
- Abstract要約: 我々は,敵の盗賊と盗賊の問題を専門的な助言で解き明かすために,新たな微分プライベートアルゴリズムを設計する。
逆バンディットに対しては、任意の非プライベートバンディットアルゴリズムをプライベートバンディットアルゴリズムにシンプルかつ効率的に変換する。
専門家のアドバイスを受けた盗賊に対しては、最初の微分プライベートなアルゴリズムを提示する。これは、期待された後悔の$Oleft(fracsqrtNTsqrtepsilonright), Oleft(fracsqrtKTlog(N)log(KT)epsilonright)$, $tildeOleft()である。
- 参考スコア（独自算出の注目度）: 31.74205580746007
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We design new differentially private algorithms for the problems of adversarial bandits and bandits with expert advice. For adversarial bandits, we give a simple and efficient conversion of any non-private bandit algorithm to a private bandit algorithm. Instantiating our conversion with existing non-private bandit algorithms gives a regret upper bound of $O\left(\frac{\sqrt{KT}}{\sqrt{\epsilon}}\right)$, improving upon the existing upper bound $O\left(\frac{\sqrt{KT \log(KT)}}{\epsilon}\right)$ for all $\epsilon \leq 1$. In particular, our algorithms allow for sublinear expected regret even when $\epsilon \leq \frac{1}{\sqrt{T}}$, establishing the first known separation between central and local differential privacy for this problem. For bandits with expert advice, we give the first differentially private algorithms, with expected regret $O\left(\frac{\sqrt{NT}}{\sqrt{\epsilon}}\right), O\left(\frac{\sqrt{KT\log(N)}\log(KT)}{\epsilon}\right)$, and $\tilde{O}\left(\frac{N^{1/6}K^{1/2}T^{2/3}\log(NT)}{\epsilon ^{1/3}} + \frac{N^{1/2}\log(NT)}{\epsilon}\right)$, where $K$ and $N$ are the number of actions and experts respectively. These rates allow us to get sublinear regret for different combinations of small and large $K, N$ and $\epsilon.$
- Abstract（参考訳）: 我々は,敵の盗賊と盗賊の問題を専門的な助言で解き明かすために,新たな微分プライベートアルゴリズムを設計する。
逆バンディットに対しては、任意の非プライベートバンディットアルゴリズムをプライベートバンディットアルゴリズムにシンプルかつ効率的に変換する。
既存の非プライベートなバンディットアルゴリズムによる変換は、後悔の上限である$O\left(\frac{\sqrt{KT}}{\sqrt{\epsilon}}\right)$を与え、既存の上限である$O\left(\frac{\sqrt{KT \log(KT)}}{\epsilon}\right)$をすべての$\epsilon \leq 1$に対して改善する。
特に、我々のアルゴリズムは、$\epsilon \leq \frac{1}{\sqrt{T}}$であっても、サブ線形の後悔を許す。
O\left(\frac{\sqrt{NT}}{\sqrt{\epsilon}}\right), O\left(\frac{\sqrt{KT\log(N)}\log(KT)}{\epsilon}\right)$, and $\tilde{O}\left(\frac{N^{1/6}K^{1/2}T^{2/3}\log(NT)}{\epsilon ^{1/3}} + \frac{N^{1/2}\log(NT)}{\epsilon}\right)$, ここでは$K$と$N$はそれぞれアクションの数と専門家である。
これらのレートは、小さくて大きい$K、N$、そして$\epsilonの組み合わせに対して、サブリニアな後悔を得ることができます。
$
関連論文リスト
- Differentially Private Stochastic Gradient Descent with Low-Noise [49.981789906200035]
現代の機械学習アルゴリズムは、データからきめ細かい情報を抽出して正確な予測を提供することを目的としており、プライバシー保護の目標と矛盾することが多い。
本稿では、プライバシを保ちながら優れたパフォーマンスを確保するために、プライバシを保存する機械学習アルゴリズムを開発することの実践的および理論的重要性について論じる。
論文 参考訳（メタデータ） (2022-09-09T08:54:13Z) - Differentially Private Stochastic Linear Bandits: (Almost) for Free [17.711701190680742]
中心的なモデルでは、最適な非プライベートなアルゴリズムとほとんど同じ後悔を実現しています。
シャッフルモデルでは、中央の場合のように$tildeO(sqrtT+frac1epsilon)$ % for small $epsilon$を後悔する一方、最もよく知られたアルゴリズムは$tildeO(frac1epsilonT3/5)$を後悔する。
論文 参考訳（メタデータ） (2022-07-07T17:20:57Z) - Corralling a Larger Band of Bandits: A Case Study on Switching Regret
for Linear Bandits [99.86860277006318]
本稿では,一組の逆アルゴリズムを組み合わせ,学習することの問題点について考察する。
Agarwal et al. の CORRAL はこの目標を、$widetildeO(sqrtd S T)$ の残酷なオーバーヘッドで達成している。
この問題に触発されて、後悔のオーバーヘッドが百万ドルにしか依存しない大規模バンディットアルゴリズムのバンドを囲む新しいレシピを提案する。
論文 参考訳（メタデータ） (2022-02-12T21:55:44Z) - Differentially Private Multi-Armed Bandits in the Shuffle Model [58.22098764071924]
シャッフルモデルにおけるマルチアームバンディット(MAB)問題に対して,$(varepsilon,delta)$-differentially privateアルゴリズムを提案する。
我々の上限は、集中モデルにおいて最もよく知られたアルゴリズムの後悔とほぼ一致し、局所モデルにおいて最もよく知られたアルゴリズムを著しく上回っている。
論文 参考訳（メタデータ） (2021-06-05T14:11:01Z) - Linear Bandits on Uniformly Convex Sets [88.3673525964507]
線形バンディットアルゴリズムはコンパクト凸作用集合上の $tildemathcalo(nsqrtt)$ pseudo-regret 境界を与える。
2種類の構造的仮定は、より良い擬似回帰境界をもたらす。
論文 参考訳（メタデータ） (2021-03-10T07:33:03Z) - Near-Optimal Algorithms for Differentially Private Online Learning in a Stochastic Environment [7.4288915613206505]
本研究では,バンディットとフルインフォメーションの両方のフィードバックの下で,オンライン学習環境における個人差分問題について検討する。
差分的な私的盗賊に対しては、UTBとトンプソンサンプリングに基づくアルゴリズムを同時に提案し、最適な$O左(sum_j: Delta_j>0 fracln(T)min leftDelta_j, epsilon right)$ minimax lower boundとする。
同じ差分プライベートなフル情報設定に対しては、$epsilon$-differentially も提示する。
論文 参考訳（メタデータ） (2021-02-16T02:48:16Z) - Optimal Regret Algorithm for Pseudo-1d Bandit Convex Optimization [51.23789922123412]
我々は,バンディットフィードバックを用いてオンライン学習を学習する。
learnerは、コスト/リワード関数が"pseudo-1d"構造を許可するゼロ次オラクルのみにアクセスできる。
我々は、$T$がラウンドの数である任意のアルゴリズムの後悔のために$min(sqrtdT、T3/4)$の下限を示しています。
ランダム化オンライングラデーション下降とカーネル化指数重み法を組み合わせた新しいアルゴリズムsbcalgを提案し,疑似-1d構造を効果的に活用する。
論文 参考訳（メタデータ） (2021-02-15T08:16:51Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。