論文の概要: (Locally) Differentially Private Combinatorial Semi-Bandits
- arxiv url: http://arxiv.org/abs/2006.00706v2
- Date: Fri, 3 Jul 2020 10:52:42 GMT
- ステータス: 処理完了
- システム内更新日: 2022-11-26 06:04:48.568377
- Title: (Locally) Differentially Private Combinatorial Semi-Bandits
- Title（参考訳）: (地方)差動的にプライベートな組合せ半バンド
- Authors: Xiaoyu Chen, Kai Zheng, Zixin Zhou, Yunchang Yang, Wei Chen, Liwei
Wang
- Abstract要約: 我々は,従来のマルチアーマッド・バンド(MAB)の拡張であるコンビニアル・セミバンド(CSB)と,より強力なローカル・ディファレンシャル・プライバシ(LDP)設定について検討した。
- 参考スコア（独自算出の注目度）: 26.462686161971803
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: In this paper, we study Combinatorial Semi-Bandits (CSB) that is an extension
of classic Multi-Armed Bandits (MAB) under Differential Privacy (DP) and
stronger Local Differential Privacy (LDP) setting. Since the server receives
more information from users in CSB, it usually causes additional dependence on
the dimension of data, which is a notorious side-effect for privacy preserving
learning. However for CSB under two common smoothness assumptions
\cite{kveton2015tight,chen2016combinatorial}, we show it is possible to remove
this side-effect. In detail, for $B_{\infty}$-bounded smooth CSB under either
$\varepsilon$-LDP or $\varepsilon$-DP, we prove the optimal regret bound is
$\Theta(\frac{mB^2_{\infty}\ln T } {\Delta\epsilon^2})$ or
$\tilde{\Theta}(\frac{mB^2_{\infty}\ln T} { \Delta\epsilon})$ respectively,
where $T$ is time period, $\Delta$ is the gap of rewards and $m$ is the number
of base arms, by proposing novel algorithms and matching lower bounds. For
$B_1$-bounded smooth CSB under $\varepsilon$-DP, we also prove the optimal
regret bound is $\tilde{\Theta}(\frac{mKB^2_1\ln T} {\Delta\epsilon})$ with
both upper bound and lower bound, where $K$ is the maximum number of feedback
in each round. All above results nearly match corresponding non-private optimal
rates, which imply there is no additional price for (locally) differentially
private CSB in above common settings.
- Abstract（参考訳）: 本稿では,差動プライバシー (dp) と強固な局所差動プライバシー (ldp) 設定下での古典的マルチアーム付きバンディット (mab) の拡張である組合せ半バンド (csb) について検討する。
サーバはcsbのユーザからより多くの情報を受信するので、通常はデータ次元に依存し、プライバシー保護学習の副作用として悪名高い。
しかし、2つの共通の平滑性仮定のcsbに対して、この副作用を取り除くことが可能であることを示す。
詳しくは、$b_{\infty}$-bounded smooth csb に対して、$\varepsilon$-ldp または $\varepsilon$-dp の下で、最適な後悔の限界は$\theta(\frac{mb^2_{\infty}\ln t } {\delta\epsilon^2})$ または $\tilde{\theta}(\frac{mb^2_{\infty}\ln t} { \delta\epsilon})$ である。
b_1$-bounded smooth csb に対して、$\varepsilon$-dp の下では、最適後悔境界は $\tilde{\theta}(\frac{mkb^2_1\ln t} {\delta\epsilon})$ であり、上界と下界の両方において、$k$ は各ラウンドにおけるフィードバックの最大数である。
上記の結果はすべて、対応する非プライベートな最適レートとほぼ一致しており、これは、(局所的に)微分プライベートなCSBを上記の一般的な設定で追加価格にしないことを意味する。
関連論文リスト
- DP-Dueling: Learning from Preference Feedback without Compromising User Privacy [32.58099924135157]
ユーザ好みでアクティブな学習を行うための,最初の微分プライベートなダリング帯域幅アルゴリズムを提案する。
我々のアルゴリズムは、ほぼ最適性能で計算効率が良い。
我々は結果を任意の一般的な決定空間に拡張し、潜在的に無限の腕を持つ$d$次元を持つ。
論文 参考訳（メタデータ） (2024-03-22T09:02:12Z) - Near Sample-Optimal Reduction-based Policy Learning for Average Reward
MDP [58.13930707612128]
この研究は、平均報酬マルコフ決定過程(AMDP)における$varepsilon$-Optimal Policyを得る際のサンプルの複雑さを考察する。
我々は、状態-作用対当たりの$widetilde O(H varepsilon-3 ln frac1delta)$サンプルを証明し、$H := sp(h*)$は任意の最適ポリシーのバイアスのスパンであり、$varepsilon$は精度、$delta$は失敗確率である。
論文 参考訳（メタデータ） (2022-12-01T15:57:58Z) - 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) - Cascading Bandit under Differential Privacy [21.936577816668944]
本研究では,カスケードバンドにおける自己差分プライバシー(DP)と局所差分プライバシー(LDP)について検討する。
DPでは,$epsilon$-indistinguishability を保証し,$mathcalO(fraclog3 Tepsilon)$を任意の小さな$xi$に対して後悔するアルゴリズムを提案する。
Epsilon$,$delta$)-LDPの下では、プライバシの予算とエラー確率のトレードオフを通じて、K2$依存を緩和します。
論文 参考訳（メタデータ） (2021-05-24T07:19:01Z) - Nearly Horizon-Free Offline Reinforcement Learning [97.36751930393245]
S$状態、$A$アクション、計画的地平$H$で、エピソードな時間同質なMarkov決定プロセスに関するオフライン強化学習を再考する。
経験的MDPを用いた評価と計画のための,約$H$自由なサンプル複雑性境界の最初の集合を得る。
論文 参考訳（メタデータ） (2021-03-25T18:52:17Z) - Bandits with many optimal arms [68.17472536610859]
最適アームの割合は$p*$、最適アームとサブ最適化アームの間の最小平均ギャップは$Delta$と書きます。
我々は,累積的後悔設定と最良腕識別設定の両方において最適な学習率を特徴付ける。
論文 参考訳（メタデータ） (2021-03-23T11:02:31Z) - Private Stochastic Convex Optimization: Optimal Rates in $\ell_1$
Geometry [69.24618367447101]
対数要因まで $(varepsilon,delta)$-differently private の最適過剰人口損失は $sqrtlog(d)/n + sqrtd/varepsilon n.$ です。
損失関数がさらなる滑らかさの仮定を満たすとき、余剰損失は$sqrtlog(d)/n + (log(d)/varepsilon n)2/3で上界(対数因子まで)であることが示される。
論文 参考訳（メタデータ） (2021-03-02T06:53:44Z) - 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) - Near-Optimal Regret Bounds for Contextual Combinatorial Semi-Bandits
with Linear Payoff Functions [53.77572276969548]
我々は、C$2$UCBアルゴリズムが分割マトロイド制約に対して最適な後悔結合$tildeO(dsqrtkT + dk)$を有することを示した。
一般的な制約に対して,C$2$UCBアルゴリズムで腕の報酬推定値を変更するアルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-01-20T04:29:18Z) - Nearly Minimax Optimal Reinforcement Learning for Discounted MDPs [99.59319332864129]
UCBVI-$gamma$が$tildeObig(sqrtSAT/ (1-gamma)1.5big)$ regret, where $S$ is the number of state, $A$ is the number of action, $gamma$ is the discount factor, $T$ is the number of steps。
さらに、ハードMDPのクラスを構築し、任意のアルゴリズムに対して、期待される後悔は少なくとも$tildeOmegabig(sqrtSAT/)であることを示す。
論文 参考訳（メタデータ） (2020-10-01T17:57:47Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。