論文の概要: (Private) Kernelized Bandits with Distributed Biased Feedback
- arxiv url: http://arxiv.org/abs/2301.12061v1
- Date: Sat, 28 Jan 2023 02:30:15 GMT
- ステータス: 処理完了
- システム内更新日: 2023-01-31 19:25:30.850781
- Title: (Private) Kernelized Bandits with Distributed Biased Feedback
- Title（参考訳）: (原始)分散バイアスフィードバックによるカーネル化バンド
- Authors: Fengjiao Li, Xingyu Zhou, and Bo Ji
- Abstract要約: 分散バイアスフィードバックを用いたカーネル化された帯域幅について検討する。
Emphdistributed phase-then-batch-based elimination (textttDPBE)アルゴリズムを提案する。
textttDPBE は $tildeO(T1-alpha/2+sqrtgamma_TT)$ のサブ線形後悔を実現する。
- 参考スコア（独自算出の注目度）: 13.312928989951505
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: In this paper, we study kernelized bandits with distributed biased feedback.
This problem is motivated by several real-world applications (such as dynamic
pricing, cellular network configuration, and policy making), where users from a
large population contribute to the reward of the action chosen by a central
entity, but it is difficult to collect feedback from all users. Instead, only
biased feedback (due to user heterogeneity) from a subset of users may be
available. In addition to such partial biased feedback, we are also faced with
two practical challenges due to communication cost and computation complexity.
To tackle these challenges, we carefully design a new \emph{distributed
phase-then-batch-based elimination (\texttt{DPBE})} algorithm, which samples
users in phases for collecting feedback to reduce the bias and employs
\emph{maximum variance reduction} to select actions in batches within each
phase. By properly choosing the phase length, the batch size, and the
confidence width used for eliminating suboptimal actions, we show that
\texttt{DPBE} achieves a sublinear regret of
$\tilde{O}(T^{1-\alpha/2}+\sqrt{\gamma_T T})$, where $\alpha\in (0,1)$ is the
user-sampling parameter one can tune. Moreover, \texttt{DPBE} can significantly
reduce both communication cost and computation complexity in distributed
kernelized bandits, compared to some variants of the state-of-the-art
algorithms (originally developed for standard kernelized bandits). Furthermore,
by incorporating various \emph{differential privacy} models (including the
central, local, and shuffle models), we generalize \texttt{DPBE} to provide
privacy guarantees for users participating in the distributed learning process.
Finally, we conduct extensive simulations to validate our theoretical results
and evaluate the empirical performance.
- Abstract（参考訳）: 本稿では,分散バイアスフィードバックを用いた分散バンディットについて検討する。
この問題は、複数の実世界のアプリケーション(動的価格設定、セルラーネットワーク構成、ポリシー作成など)によって動機付けられており、大人口のユーザが中央組織が選択した行動の報奨に貢献するが、すべてのユーザーからのフィードバックを集めることは困難である。
代わりに、ユーザのサブセットからの(ユーザの不均一性による)偏りのあるフィードバックしか利用できない。
このような偏りのあるフィードバックに加えて、通信コストと計算複雑性の2つの現実的な課題に直面している。
これらの課題に対処するために,我々は,フィードバックを収集するフェーズでユーザをサンプリングしてバイアスを低減し,各フェーズ内のバッチ内のアクションを選択するための,新しい \emph{distributed phase-then-batch-based elimination (\texttt{dpbe})}アルゴリズムを慎重に設計する。
位相長、バッチサイズ、サブオプティカルアクションの除去に用いられる信頼度幅を適切に選択することにより、\textt{dpbe} は$\tilde{o}(t^{1-\alpha/2}+\sqrt{\gamma_t t})$(ここで $\alpha\in (0,1)$ は、チューニング可能なユーザサンプリングパラメータである。
さらに、'texttt{DPBE} は分散カーネル化帯域における通信コストと計算の複雑さを、最先端のアルゴリズム(元は標準カーネル化帯域のために開発された)の変種と比較して著しく低減することができる。
さらに,各種のemph{differential privacy}モデル(中央モデル,局所モデル,シャッフルモデルを含む)を組み込むことで,分散学習プロセスに参加するユーザに対して,プライバシ保証を提供する。
最後に,理論結果を検証し,実験結果を評価するために,広範なシミュレーションを行う。
関連論文リスト
- Smoothed Normalization for Efficient Distributed Private Optimization [54.197255548244705]
フェデレートされた学習は、参加者のプライバシを備えた機械学習モデルを可能にする。
トレーニングやフィードバックのない問題に対して、差分にプライベートな分散手法は存在しない。
証明可能な収束保証付き分散アルゴリズム$alpha$-$sf NormEC$を導入する。
論文 参考訳（メタデータ） (2025-02-19T07:10:32Z) - Continuous K-Max Bandits [54.21533414838677]
我々は、連続的な結果分布と弱い値-インデックスフィードバックを持つ、$K$-Maxのマルチアームバンディット問題について検討する。
この設定は、レコメンデーションシステム、分散コンピューティング、サーバスケジューリングなどにおいて重要なアプリケーションをキャプチャします。
我々の重要な貢献は、適応的な離散化とバイアス補正された信頼境界を組み合わせた計算効率の良いアルゴリズムDCK-UCBである。
論文 参考訳（メタデータ） (2025-02-19T06:37:37Z) - The Cost of Shuffling in Private Gradient Based Optimization [40.31928071333575]
その結果, DP-ShuffleGはDP-SGDと比較して, データのシャッフル処理により過大なリスクが生じることがわかった。
我々は、プライベートな最適化に公開データサンプルを統合するハイブリッドアプローチである textitInterleaved-ShuffleG を提案する。
論文 参考訳（メタデータ） (2025-02-05T22:30:00Z) - Personalized Denoising Implicit Feedback for Robust Recommender System [60.719158008403376]
ユーザの個人的損失分布には,正常なインタラクションとノイズの多いインタラクションが明確に区別されていることを示す。
本稿では,ユーザのパーソナライズロス分布であるPLDを用いてDenoiseに対する再サンプリング戦略を提案する。
論文 参考訳（メタデータ） (2025-02-01T07:13:06Z) - Error Feedback under $(L_0,L_1)$-Smoothness: Normalization and Momentum [56.37522020675243]
機械学習の幅広い問題にまたがる正規化誤差フィードバックアルゴリズムに対する収束の最初の証明を提供する。
提案手法では,許容可能なステップサイズが大きくなったため,新しい正規化エラーフィードバックアルゴリズムは,各種タスクにおける非正規化エラーよりも優れていた。
論文 参考訳（メタデータ） (2024-10-22T10:19:27Z) - Disincentivizing Polarization in Social Networks [10.758115514959593]
本稿では,フィルタバブルを回避するコンテンツキュレーションとパーソナライゼーションのモデルを提案する。
推奨を最適化するためのアルゴリズム保証を提供する。
実世界の嗜好データを用いて、我々のモデルでは、利用者は小さなユーティリティ損失のみで多様化の重荷を共有していることを確認した。
論文 参考訳（メタデータ） (2023-05-23T21:47:31Z) - Discrete Distribution Estimation under User-level Local Differential
Privacy [37.65849910114053]
ユーザレベルの局所差分プライバシー(LDP)に基づく離散分布推定について検討する。
ユーザレベルの$varepsilon$-LDPでは、各ユーザは$mge1$サンプルを持ち、すべての$m$サンプルのプライバシを同時に保存する必要がある。
論文 参考訳（メタデータ） (2022-11-07T18:29:32Z) - Distributed Sparse Regression via Penalization [5.990069843501885]
エージェントのネットワーク上の線形回帰を、(集中ノードを持たない)無向グラフとしてモデル化する。
推定問題は、局所的なLASSO損失関数の和とコンセンサス制約の2次ペナルティの最小化として定式化される。
本稿では, ペナル化問題に適用した近似勾配アルゴリズムが, 集中的な統計的誤差の順序の許容値まで線形に収束することを示す。
論文 参考訳（メタデータ） (2021-11-12T01:51:50Z) - Linear Speedup in Personalized Collaborative Learning [69.45124829480106]
フェデレート学習におけるパーソナライゼーションは、モデルのバイアスをトレーディングすることで、モデルの精度を向上させることができる。
ユーザの目的の最適化として、パーソナライズされた協調学習問題を定式化する。
分散の低減のためにバイアスを最適にトレードオフできる条件について検討する。
論文 参考訳（メタデータ） (2021-11-10T22:12:52Z) - Learning with User-Level Privacy [61.62978104304273]
ユーザレベルの差分プライバシー制約下での学習課題を,アルゴリズムを用いて解析する。
個々のサンプルのプライバシーのみを保証するのではなく、ユーザレベルのdpはユーザの貢献全体を保護します。
プライバシコストが$tau$に比例した$K$適応的に選択されたクエリのシーケンスにプライベートに答えるアルゴリズムを導き出し、私たちが検討する学習タスクを解決するためにそれを適用します。
論文 参考訳（メタデータ） (2021-02-23T18:25:13Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。