論文の概要: 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}})$の後悔を被る。
我々の数値評価は理論的な結果を検証する。
関連論文リスト
- Private Zeroth-Order Nonsmooth Nonconvex Optimization [41.05664717242051]
非平滑な目的と非平滑な目的に対するプライベート最適化のための新しいゼロ階アルゴリズムを提案する。
データセットサイズが$M$であれば、アルゴリズムはプライバシの差分を見つける。
目的はスムーズではないが、プライバシーがある。
無料の$tdepsilon$
論文 参考訳（メタデータ） (2024-06-27T23:57:01Z) - Low-rank Matrix Bandits with Heavy-tailed Rewards [55.03293214439741]
アンダーライン重み付きアンダーラインリワード(LowHTR)を用いたアンダーラインローランク行列バンディットの問題点について検討する。
観測されたペイオフに対するトランケーションと動的探索を利用して,LOTUSと呼ばれる新しいアルゴリズムを提案する。
論文 参考訳（メタデータ） (2024-04-26T21:54:31Z) - DP-Dueling: Learning from Preference Feedback without Compromising User Privacy [32.58099924135157]
ユーザ好みでアクティブな学習を行うための,最初の微分プライベートなダリング帯域幅アルゴリズムを提案する。
我々のアルゴリズムは、ほぼ最適性能で計算効率が良い。
我々は結果を任意の一般的な決定空間に拡張し、潜在的に無限の腕を持つ$d$次元を持つ。
論文 参考訳（メタデータ） (2024-03-22T09:02:12Z) - 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) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。