論文の概要: (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}モデル(中央モデル,局所モデル,シャッフルモデルを含む)を組み込むことで,分散学習プロセスに参加するユーザに対して,プライバシ保証を提供する。
最後に,理論結果を検証し,実験結果を評価するために,広範なシミュレーションを行う。
関連論文リスト
- Error Feedback under $(L_0,L_1)$-Smoothness: Normalization and Momentum [56.37522020675243]
機械学習の幅広い問題にまたがる正規化誤差フィードバックアルゴリズムに対する収束の最初の証明を提供する。
提案手法では,許容可能なステップサイズが大きくなったため,新しい正規化エラーフィードバックアルゴリズムは,各種タスクにおける非正規化エラーよりも優れていた。
論文 参考訳（メタデータ） (2024-10-22T10:19:27Z) - Noisy Correspondence Learning with Self-Reinforcing Errors Mitigation [63.180725016463974]
クロスモーダル検索は、実際は精力的な、十分に整合した大規模データセットに依存している。
我々は、新しい雑音対応学習フレームワーク、textbfSelf-textbfReinforcing textbfErrors textbfMitigation(SREM)を導入する。
論文 参考訳（メタデータ） (2023-12-27T09:03:43Z) - Distributed Extra-gradient with Optimal Complexity and Communication
Guarantees [60.571030754252824]
複数のプロセッサ/ワーカー/クライアントがローカルなデュアルベクトルにアクセス可能なマルチGPU設定において、モノトン変分不等式(VI)問題を考察する。
モノトーンVI問題に対するデファクトアルゴリズムであるExtra-gradientは、通信効率が良くないように設計されている。
そこで本稿では,VI の解法に適した非バイアスで適応的な圧縮手法である量子化一般化外部勾配 (Q-GenX) を提案する。
論文 参考訳（メタデータ） (2023-08-17T21:15:04Z) - 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) - Learning Explicit User Interest Boundary for Recommendation [5.715918678913698]
ユーザ関心境界を表すために、各ユーザに対して補助的なスコア$b_u$を導入します。
提案手法は個人化された意思決定境界を提供し,特別なサンプリング戦略を使わずにトレーニング効率を大幅に向上させることができることを示す。
論文 参考訳（メタデータ） (2021-11-22T07:26:51Z) - 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) - Batched Neural Bandits [107.5072688105936]
BatchNeuralUCBはニューラルネットワークと楽観性を組み合わせ、探索と探索のトレードオフに対処する。
BatchNeuralUCBは、完全なシーケンシャルバージョンと同じ後悔を達成しつつ、ポリシー更新の数を大幅に減らしています。
論文 参考訳（メタデータ） (2021-02-25T17:36:44Z) - Learning with User-Level Privacy [61.62978104304273]
ユーザレベルの差分プライバシー制約下での学習課題を,アルゴリズムを用いて解析する。
個々のサンプルのプライバシーのみを保証するのではなく、ユーザレベルのdpはユーザの貢献全体を保護します。
プライバシコストが$tau$に比例した$K$適応的に選択されたクエリのシーケンスにプライベートに答えるアルゴリズムを導き出し、私たちが検討する学習タスクを解決するためにそれを適用します。
論文 参考訳（メタデータ） (2021-02-23T18:25:13Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。