論文の概要: Optimal Rates of (Locally) Differentially Private Heavy-tailed Multi-Armed Bandits

• arxiv url: http://arxiv.org/abs/2106.02575v2
• Date: Mon, 7 Jun 2021 01:56:07 GMT
• ステータス: 処理完了
• システム内更新日: 2021-06-08 11:36:22.883309
• Title: Optimal Rates of (Locally) Differentially Private Heavy-tailed Multi-Armed Bandits
• Title（参考訳）: 局所的にプライベートな重み付きマルチアームバンドの最適レート
• Authors: Youming Tao, Yulian Wu, Peng Zhao, Di Wang
• Abstract要約: 本稿では,DP/LDPモデルにおけるマルチアームバンディット(MAB)の問題について検討する。 本稿では,SEアルゴリズムの局所的プライベートかつロバストなバージョンとみなすアルゴリズムを提案する。
• 参考スコア（独自算出の注目度）: 11.419534203345187
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In this paper we study the problem of stochastic multi-armed bandits (MAB) in the (local) differential privacy (DP/LDP) model. Unlike the previous results which need to assume bounded reward distributions, here we mainly focus on the case the reward distribution of each arm only has $(1+v)$-th moment with some $v\in (0, 1]$. In the first part, we study the problem in the central $\epsilon$-DP model. We first provide a near-optimal result by developing a private and robust Upper Confidence Bound (UCB) algorithm. Then, we improve the result via a private and robust version of the Successive Elimination (SE) algorithm. Finally, we show that the instance-dependent regret bound of our improved algorithm is optimal by showing its lower bound. In the second part of the paper, we study the problem in the $\epsilon$-LDP model. We propose an algorithm which could be seen as locally private and robust version of the SE algorithm, and show it could achieve (near) optimal rates for both instance-dependent and instance-independent regrets. All of the above results can also reveal the differences between the problem of private MAB with bounded rewards and heavy-tailed rewards. To achieve these (near) optimal rates, we develop several new hard instances and private robust estimators as byproducts, which might could be used to other related problems. Finally, experimental results also support our theoretical analysis and show the effectiveness of our algorithms.
• Abstract（参考訳）: 本稿では,(局所)微分プライバシー(DP/LDP)モデルにおける確率的マルチアームバンディット(MAB)の問題について検討する。 有界な報酬分布を仮定する以前の結果とは異なり、ここでは主に各アームの報酬分布が、ある$v\in (0, 1]$で 1+v)$-番目のモーメントしか持たない場合に焦点を当てる。 最初の段階では、中央の$\epsilon$-dpモデルで問題を研究しています。 まず,プライベートでロバストなuper confidence bound (ucb)アルゴリズムを開発し,最適に近い結果を得る。 そこで我々は,逐次除去(SE)アルゴリズムのプライベートかつロバストなバージョンを用いて結果を改善する。 最後に,改良アルゴリズムのインスタンス依存的後悔境界は,その下限を示すことによって最適であることを示す。 論文の第2部では、$\epsilon$-ldpモデルでこの問題について研究している。 我々は,seアルゴリズムの局所的プライベートかつロバストなバージョンと見なすことができるアルゴリズムを提案し,インスタンス依存とインスタンス非依存の両方の後悔に対して(ほぼ)最適レートを達成できることを示す。 以上の結果はすべて、有界報酬とヘビーテール報酬の私的MAB問題の違いを明らかにすることができる。 これらの(ほぼ)最適率を達成するために、我々はいくつかの新しいハードインスタンスと、他の関連する問題に使用できる副産物としてのプライベートな頑健な推定器を開発した。 最後に,実験結果も理論的解析をサポートし,アルゴリズムの有効性を示す。

関連論文リスト

• Perturb-and-Project: Differentially Private Similarities and Marginals [73.98880839337873]
  差分プライバシーのための入力摂動フレームワークを再検討し、入力にノイズを付加する。 まず、ペアワイズ・コサイン類似性をプライベートにリリースするための新しい効率的なアルゴリズムを設計する。 我々は,$k$の辺縁クエリを$n$の機能に対して計算する新しいアルゴリズムを導出する。
  論文  参考訳（メタデータ） (2024-06-07T12:07:16Z)
• Best Arm Identification with Fixed Budget: A Large Deviation Perspective [54.305323903582845]
  我々は、様々な武器の報酬間の経験的ギャップに基づいて、あらゆるラウンドで腕を拒絶できる真に適応的なアルゴリズムであるsredを提示する。 特に、様々な武器の報酬の間の経験的ギャップに基づいて、あらゆるラウンドで腕を拒絶できる真に適応的なアルゴリズムであるsredを提示する。
  論文  参考訳（メタデータ） (2023-12-19T13:17:43Z)
• Combinatorial Stochastic-Greedy Bandit [79.1700188160944]
  我々は,選択した$n$のアームセットのジョイント報酬以外の余分な情報が観測されない場合に,マルチアームのバンディット問題に対する新規グリーディ・バンディット(SGB)アルゴリズムを提案する。 SGBは最適化された拡張型コミットアプローチを採用しており、ベースアームの大きなセットを持つシナリオ用に特別に設計されている。
  論文  参考訳（メタデータ） (2023-12-13T11:08:25Z)
• Differentially Private Domain Adaptation with Theoretical Guarantees [46.37771025567305]
  多くのアプリケーションでは、ラベル付きデータの処分におけるラベル付きデータはプライバシー上の制約を受けており、比較的制限されている。 これは、パブリックソースからプライベートターゲットドメインへのドメイン適応を監督する現代の問題である。 我々は、理論的な学習保証の恩恵を受けるために、一般の学習者を利用する。
  論文  参考訳（メタデータ） (2023-06-15T04:03:06Z)
• Differentially Private Episodic Reinforcement Learning with Heavy-tailed Rewards [12.809396600279479]
  差分プライバシ(DP)制約下での重み付き報酬を伴うマルコフ決定プロセス(MDP)の問題について検討する。 報酬に対するロバストな平均推定器を利用することで、まず重み付きMDPのための2つのフレームワークを提案する。 我々は,自家用RLとガウシアン以下のRLと,重み付き報酬とに根本的な相違があることを指摘した。
  論文  参考訳（メタデータ） (2023-06-01T20:18:39Z)
• Differentially-Private Hierarchical Clustering with Provable Approximation Guarantees [79.59010418610625]
  階層クラスタリングのための微分プライベート近似アルゴリズムについて検討する。 例えば、$epsilon$-DPアルゴリズムは入力データセットに対して$O(|V|2/epsilon)$-additiveエラーを示さなければならない。 本稿では,ブロックを正確に復元する1+o(1)$近似アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-01-31T19:14:30Z)
• Privately Estimating a Gaussian: Efficient, Robust and Optimal [6.901744415870126]
  純微分プライバシー(DP)モデルと近似微分プライバシー(DP)モデルの両方において、ガウス分布をプライベートに推定する効率的なアルゴリズムを提供する。 純粋なDP設定では、未知の$d$次元ガウス分布を任意の全変分誤差まで推定する効率的なアルゴリズムを与える。 平均推定の特別な場合、我々のアルゴリズムは$widetilde O(d1.5)$の最適なサンプル複雑性を達成し、以前の作業から$widetilde O(d1.5)$のバウンドを改善する。
  論文  参考訳（メタデータ） (2022-12-15T18:27:39Z)
• Scalable Differentially Private Clustering via Hierarchically Separated Trees [82.69664595378869]
  我々は,最大$O(d3/2log n)cdot OPT + O(k d2 log2 n / epsilon2)$,$epsilon$はプライバシ保証であることを示す。 最悪の場合の保証は、最先端のプライベートクラスタリング手法よりも悪いが、提案するアルゴリズムは実用的である。
  論文  参考訳（メタデータ） (2022-06-17T09:24:41Z)
• Output Perturbation for Differentially Private Convex Optimization with Improved Population Loss Bounds, Runtimes and Applications to Private Adversarial Training [12.386462516398469]
  強力な過剰なリスク境界を提供する効率的で実装が容易な差分プライベート(DP)アルゴリズムを見つけることは、現代の機械学習において重要な問題である。 我々は、滑らかさと強い凸性の存在下で、最もよく知られた$(epsilon, 0)$-DP人口損失境界と最速ランタイムを提供する。 我々はこの理論を2つの学習フレームワーク、傾きERMと逆学習フレームワークに適用する。
  論文  参考訳（メタデータ） (2021-02-09T08:47:06Z)
• Hiding Among the Clones: A Simple and Nearly Optimal Analysis of Privacy Amplification by Shuffling [49.43288037509783]
  ランダムシャッフルは、局所的ランダム化データの差分プライバシー保証を増幅する。 私たちの結果は、以前の作業よりも単純で、ほぼ同じ保証で差分プライバシーに拡張された新しいアプローチに基づいています。
  論文  参考訳（メタデータ） (2020-12-23T17:07:26Z)

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

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