論文の概要: DP-Dueling: Learning from Preference Feedback without Compromising User Privacy

• arxiv url: http://arxiv.org/abs/2403.15045v1
• Date: Fri, 22 Mar 2024 09:02:12 GMT
• ステータス: 処理完了
• システム内更新日: 2024-03-25 18:08:17.687567
• Title: DP-Dueling: Learning from Preference Feedback without Compromising User Privacy
• Title（参考訳）: DP-Dueling: ユーザのプライバシを損なうことなく、優先フィードバックから学ぶ
• Authors: Aadirupa Saha, Hilal Asi,
• Abstract要約: ユーザ好みでアクティブな学習を行うための,最初の微分プライベートなダリング帯域幅アルゴリズムを提案する。 我々のアルゴリズムは、ほぼ最適性能で計算効率が良い。 我々は結果を任意の一般的な決定空間に拡張し、潜在的に無限の腕を持つ$d$次元を持つ。
• 参考スコア（独自算出の注目度）: 32.58099924135157
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We consider the well-studied dueling bandit problem, where a learner aims to identify near-optimal actions using pairwise comparisons, under the constraint of differential privacy. We consider a general class of utility-based preference matrices for large (potentially unbounded) decision spaces and give the first differentially private dueling bandit algorithm for active learning with user preferences. Our proposed algorithms are computationally efficient with near-optimal performance, both in terms of the private and non-private regret bound. More precisely, we show that when the decision space is of finite size $K$, our proposed algorithm yields order optimal $O\Big(\sum_{i = 2}^K\log\frac{KT}{\Delta_i} + \frac{K}{\epsilon}\Big)$ regret bound for pure $\epsilon$-DP, where $\Delta_i$ denotes the suboptimality gap of the $i$-th arm. We also present a matching lower bound analysis which proves the optimality of our algorithms. Finally, we extend our results to any general decision space in $d$-dimensions with potentially infinite arms and design an $\epsilon$-DP algorithm with regret $\tilde{O} \left( \frac{d^6}{\kappa \epsilon } + \frac{ d\sqrt{T }}{\kappa} \right)$, providing privacy for free when $T \gg d$.
• Abstract（参考訳）: 差分プライバシーの制約の下で、学習者がペアワイズ比較を用いて準最適行動を特定することを目的とした、よく研究されたデュエルバンディット問題について考察する。 本研究では,大規模(潜在的に非有界な)決定空間に対するユーティリティベースの選好行列の一般クラスを考察し,ユーザ選好を用いたアクティブラーニングのための最初の微分プライベート・デュエル・バンディットアルゴリズムを提案する。 提案アルゴリズムは, プライベートおよび非プライベートな後悔境界の両面において, ほぼ最適性能で計算効率がよい。 より正確には、決定空間が有限サイズ$K$であるとき、提案アルゴリズムは、$O\Big(\sum_{i = 2}^K\log\frac{KT}{\Delta_i} + \frac{K}{\epsilon}\Big)$ regret bound for pure $\epsilon$-DP, ここで、$\Delta_i$は$i$-th腕の最適値差を表す。 また,アルゴリズムの最適性を証明した下界解析も提案する。 最後に、我々の結果は、潜在的に無限の腕を持つ$d$-dimensionsに拡張し、後悔する$\tilde{O} \left( \frac{d^6}{\kappa \epsilon } + \frac{d\sqrt{T }}{\kappa} \right)$で$\epsilon$-DPアルゴリズムを設計します。

関連論文リスト

• Perturb-and-Project: Differentially Private Similarities and Marginals [73.98880839337873]
  差分プライバシーのための入力摂動フレームワークを再検討し、入力にノイズを付加する。 まず、ペアワイズ・コサイン類似性をプライベートにリリースするための新しい効率的なアルゴリズムを設計する。 我々は,$k$の辺縁クエリを$n$の機能に対して計算する新しいアルゴリズムを導出する。
  論文  参考訳（メタデータ） (2024-06-07T12:07:16Z)
• Towards Optimal Regret in Adversarial Linear MDPs with Bandit Feedback [30.337826346496385]
  線形マルコフ決定過程におけるオンライン強化学習について,敵対的損失と帯域幅フィードバックを用いて検討した。 既存の手法と比較して、後悔性能を向上させるアルゴリズムを2つ導入する。
  論文  参考訳（メタデータ） (2023-10-17T19:43:37Z)
• 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)
• 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)
• Learning with User-Level Privacy [61.62978104304273]
  ユーザレベルの差分プライバシー制約下での学習課題を,アルゴリズムを用いて解析する。 個々のサンプルのプライバシーのみを保証するのではなく、ユーザレベルのdpはユーザの貢献全体を保護します。 プライバシコストが$tau$に比例した$K$適応的に選択されたクエリのシーケンスにプライベートに答えるアルゴリズムを導き出し、私たちが検討する学習タスクを解決するためにそれを適用します。
  論文  参考訳（メタデータ） (2021-02-23T18:25:13Z)
• 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)

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

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