論文の概要: Differentially Private Stochastic Linear Bandits: (Almost) for Free
- arxiv url: http://arxiv.org/abs/2207.03445v1
- Date: Thu, 7 Jul 2022 17:20:57 GMT
- ステータス: 処理完了
- システム内更新日: 2022-07-08 16:14:52.835238
- Title: Differentially Private Stochastic Linear Bandits: (Almost) for Free
- Title(参考訳): 異なる個人的確率線形帯域:(ほとんど)無料
- Authors: Osama A. Hanna, Antonious M. Girgis, Christina Fragouli, Suhas Diggavi
- Abstract要約: 中心的なモデルでは、最適な非プライベートなアルゴリズムとほとんど同じ後悔を実現しています。
シャッフルモデルでは、中央の場合のように$tildeO(sqrtT+frac1epsilon)$ % for small $epsilon$を後悔する一方、最もよく知られたアルゴリズムは$tildeO(frac1epsilonT3/5)$を後悔する。
- 参考スコア(独自算出の注目度): 17.711701190680742
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: In this paper, we propose differentially private algorithms for the problem
of stochastic linear bandits in the central, local and shuffled models. In the
central model, we achieve almost the same regret as the optimal non-private
algorithms, which means we get privacy for free. In particular, we achieve a
regret of $\tilde{O}(\sqrt{T}+\frac{1}{\epsilon})$ matching the known lower
bound for private linear bandits, while the best previously known algorithm
achieves $\tilde{O}(\frac{1}{\epsilon}\sqrt{T})$. In the local case, we achieve
a regret of $\tilde{O}(\frac{1}{\epsilon}{\sqrt{T}})$ which matches the
non-private regret for constant $\epsilon$, but suffers a regret penalty when
$\epsilon$ is small. In the shuffled model, we also achieve regret of
$\tilde{O}(\sqrt{T}+\frac{1}{\epsilon})$ %for small $\epsilon$ as in the
central case, while the best previously known algorithm suffers a regret of
$\tilde{O}(\frac{1}{\epsilon}{T^{3/5}})$. Our numerical evaluation validates
our theoretical results.
- Abstract(参考訳): 本稿では,中央モデル,局所モデル,シャッフルモデルにおける確率線形帯域問題に対する微分プライベートアルゴリズムを提案する。
中心的なモデルでは、最適な非プライベートなアルゴリズムとほとんど同じ後悔を実現しています。
特に、既知のプライベート線形包帯の下位境界と一致する$\tilde{O}(\sqrt{T}+\frac{1}{\epsilon})$の後悔を達成する一方、最もよく知られたアルゴリズムは$\tilde{O}(\frac{1}{\epsilon}\sqrt{T})$である。
局所の場合、定数 $\epsilon$ に対して非プライベートな後悔と一致する$\tilde{o}(\frac{1}{\epsilon}{\sqrt{t}}) の後悔が得られるが、$\epsilon$ が小さいと後悔の罰を受ける。
シャッフルモデルでは、中央の場合のように小さな$\epsilon$に対して$\tilde{o}(\sqrt{t}+\frac{1}{\epsilon})$ % の後悔が得られ、最もよく知られたアルゴリズムは$\tilde{o}(\frac{1}{\epsilon}{t^{3/5}})$の後悔を被る。
我々の数値評価は理論的な結果を検証する。
関連論文リスト
- Tackling Heavy-Tailed Rewards in Reinforcement Learning with Function
Approximation: Minimax Optimal and Instance-Dependent Regret Bounds [26.277745106128197]
本研究では,線形関数近似を用いた強化学習におけるそのような報奨の課題に対処する。
我々はまず,重み付き線形包帯に対するtextscHeavy-OFUL というアルゴリズムを設計し,インセンス依存の$T$-round regret of $tildeObig を実現した。
我々の結果は、オンライン回帰問題全般において、重くノイズを扱うことに独立した関心を持つような、新しい自己正規化集中不等式によって達成される。
論文 参考訳(メタデータ) (2023-06-12T02:56:09Z) - Near-Optimal Algorithms for Private Online Optimization in the
Realizable Regime [74.52487417350221]
オンライン学習の問題は,ゼロロスソリューションが存在する,実現可能な環境において考慮する。
そこで我々は,ほぼ最適の後悔境界を求める新たなDPアルゴリズムを提案する。
論文 参考訳(メタデータ) (2023-02-27T21:19:24Z) - Private Online Prediction from Experts: Separations and Faster Rates [74.52487417350221]
専門家によるオンライン予測は機械学習の基本的な問題であり、いくつかの研究がプライバシーの制約の下でこの問題を研究している。
本研究では,非適応的敵に対する最良な既存アルゴリズムの残差を克服する新たなアルゴリズムを提案し,解析する。
論文 参考訳(メタデータ) (2022-10-24T18:40:19Z) - 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 Private Online Learning in a Stochastic
Environment [10.731932533903509]
最適な後悔境界を達成できる任意の UCB ベースのアルゴリズムを提案する。
また、$Omega left (maxleft fraclog KDelta_min, fraclog Kepsilon right right)$ problem-dependent lower bound を示す。
論文 参考訳(メタデータ) (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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。