論文の概要: Cascading Bandit under Differential Privacy

• arxiv url: http://arxiv.org/abs/2105.11126v1
• Date: Mon, 24 May 2021 07:19:01 GMT
• ステータス: 処理完了
• システム内更新日: 2021-05-26 01:20:15.840192
• Title: Cascading Bandit under Differential Privacy
• Title（参考訳）: 差分プライバシー下における帯域のカスケード
• Authors: Kun Wang, Jing Dong, Baoxiang Wang, Shuai Li, Shuo Shao
• Abstract要約: 本研究では,カスケードバンドにおける自己差分プライバシー(DP)と局所差分プライバシー(LDP)について検討する。 DPでは,$epsilon$-indistinguishability を保証し,$mathcalO(fraclog3 Tepsilon)$を任意の小さな$xi$に対して後悔するアルゴリズムを提案する。 Epsilon$,$delta$)-LDPの下では、プライバシの予算とエラー確率のトレードオフを通じて、K2$依存を緩和します。
• 参考スコア（独自算出の注目度）: 21.936577816668944
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: This paper studies \emph{differential privacy (DP)} and \emph{local differential privacy (LDP)} in cascading bandits. Under DP, we propose an algorithm which guarantees $\epsilon$-indistinguishability and a regret of $\mathcal{O}((\frac{\log T}{\epsilon})^{1+\xi})$ for an arbitrarily small $\xi$. This is a significant improvement from the previous work of $\mathcal{O}(\frac{\log^3 T}{\epsilon})$ regret. Under ($\epsilon$,$\delta$)-LDP, we relax the $K^2$ dependence through the tradeoff between privacy budget $\epsilon$ and error probability $\delta$, and obtain a regret of $\mathcal{O}(\frac{K\log (1/\delta) \log T}{\epsilon^2})$, where $K$ is the size of the arm subset. This result holds for both Gaussian mechanism and Laplace mechanism by analyses on the composition. Our results extend to combinatorial semi-bandit. We show respective lower bounds for DP and LDP cascading bandits. Extensive experiments corroborate our theoretic findings.
• Abstract（参考訳）: 本稿では,カスケード包帯における \emph{differential privacy (DP) と \emph{local differential privacy (LDP) について検討する。 dp の下では、任意に小さい $\xi$ に対して $\epsilon$-indistinguishability と $\mathcal{o}((\frac{\log t}{\epsilon})^{1+\xi}) の後悔を保証するアルゴリズムを提案する。 これは以前の $\mathcal{O}(\frac{\log^3 T}{\epsilon})$ regret よりも大幅に改善されている。 $\epsilon$,$\delta$)-LDPの下で、プライバシー予算$\epsilon$とエラー確率$\delta$の間のトレードオフを通じて$K^2$依存を緩和し、$\mathcal{O}(\frac{K\log (1/\delta) \log T}{\epsilon^2})$の後悔を得る。 この結果は、組成の分析によりガウス機構とラプラス機構の両方が成り立つ。 結果は組合せ半帯域まで及んでいる。 DP および LDP カスケードバンドのそれぞれ下限を示す。 広範な実験は私たちの理論的な発見と一致している。

関連論文リスト

• Fast Rates for Bandit PAC Multiclass Classification [73.17969992976501]
  我々は,帯域幅フィードバックを用いたマルチクラスPAC学習について検討し,入力を$K$ラベルの1つに分類し,予測されたラベルが正しいか否かに制限する。 我々の主な貢献は、問題の無知な$(varepsilon,delta)$PACバージョンのための新しい学習アルゴリズムを設計することである。
  論文  参考訳（メタデータ） (2024-06-18T08:54:04Z)
• Sample-Optimal Locally Private Hypothesis Selection and the Provable Benefits of Interactivity [8.100854060749212]
  本研究では,局所的な差分プライバシーの制約下での仮説選択の問題について検討する。 我々は$varepsilon$-locally-differentially-private ($varepsilon$-LDP)アルゴリズムを考案し、$Thetaleft(fracklog kalpha2min varepsilon2,1 right)$を使って$d_TV(h,hatf)leq alpha + 9 min_fin MathcalFを保証する。
  論文  参考訳（メタデータ） (2023-12-09T19:22:10Z)
• 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)
• Private Convex Optimization via Exponential Mechanism [16.867534746193833]
  我々は、$ellcave2$ regularizerを$F(x)$に追加することで指数的なメカニズムを変更することで、既知の最適経験的リスクと人口損失の両方を$(epsilon,delta)$-DPで回復することを示した。 また、DP-SCOに対して$widetildeO(n min(d, n))クエリを使って$f_i(x)にこのメカニズムを実装する方法を示す。
  論文  参考訳（メタデータ） (2022-03-01T06:51:03Z)
• Faster Rates of Differentially Private Stochastic Convex Optimization [7.93728520583825]
  人口リスク関数がTysbakovノイズ条件(TNC)をパラメータ$theta>1$で満たす場合について検討した。 第2部では,人口リスク関数が強く凸する特殊な事例に着目した。
  論文  参考訳（メタデータ） (2021-07-31T22:23:39Z)
• 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)
• Fast Dimension Independent Private AdaGrad on Publicly Estimated Subspaces [24.52697154861819]
  AdaGradは、従来のAdaGradに匹敵する後悔と、ノイズによるよく制御された用語を達成していることを示す。 我々は制約付きおよび制約なしの最小化において一般凸関数で操作する。
  論文  参考訳（メタデータ） (2020-08-14T20:46:38Z)
• Model-Free Reinforcement Learning: from Clipped Pseudo-Regret to Sample Complexity [59.34067736545355]
  S$状態、$A$アクション、割引係数$gamma in (0,1)$、近似しきい値$epsilon > 0$の MDP が与えられた場合、$epsilon$-Optimal Policy を学ぶためのモデルなしアルゴリズムを提供する。 十分小さな$epsilon$の場合、サンプルの複雑さで改良されたアルゴリズムを示す。
  論文  参考訳（メタデータ） (2020-06-06T13:34:41Z)
• (Locally) Differentially Private Combinatorial Semi-Bandits [26.462686161971803]
  我々は,従来のマルチアーマッド・バンド(MAB)の拡張であるコンビニアル・セミバンド(CSB)と,より強力なローカル・ディファレンシャル・プライバシ(LDP)設定について検討した。
  論文  参考訳（メタデータ） (2020-06-01T04:23:27Z)
• Locally Private Hypothesis Selection [96.06118559817057]
  我々は、$mathcalQ$から$p$までの総変動距離が最良の分布に匹敵する分布を出力する。 局所的な差分プライバシーの制約は、コストの急激な増加を引き起こすことを示す。 提案アルゴリズムは,従来手法のラウンド複雑性を指数関数的に改善する。
  論文  参考訳（メタデータ） (2020-02-21T18:30:48Z)
• Curse of Dimensionality on Randomized Smoothing for Certifiable Robustness [151.67113334248464]
  我々は、他の攻撃モデルに対してスムースな手法を拡張することは困難であることを示す。 我々はCIFARに関する実験結果を示し,その理論を検証した。
  論文  参考訳（メタデータ） (2020-02-08T22:02:14Z)

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

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