論文の概要: Collaborative Learning and Personalization in Multi-Agent Stochastic
Linear Bandits
- arxiv url: http://arxiv.org/abs/2106.08902v1
- Date: Tue, 15 Jun 2021 00:45:55 GMT
- ステータス: 処理完了
- システム内更新日: 2021-06-17 17:37:47.735331
- Title: Collaborative Learning and Personalization in Multi-Agent Stochastic
Linear Bandits
- Title（参考訳）: マルチエージェント確率的リニアバンディットにおける協調学習とパーソナライズ
- Authors: Avishek Ghosh, Abishek Sankararaman and Kannan Ramchandran
- Abstract要約: エージェント(ユーザ)が似ているが、すべて同一ではないような、N$エージェントの不均一な線形帯域幅フレームワークにおける後悔を最小限に抑える問題を考える。
任意のエージェントに対して、後悔のスケールが$mathcalO(sqrtT/N)$、エージェントが十分に分離されたクラスタにある場合、あるいはクラスタが$mathcalO(Tfrac12 + varepsilon/(N)frac12 -varepsilon)$であることを示す。
- 参考スコア（独自算出の注目度）: 24.293155063082438
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We consider the problem of minimizing regret in an $N$ agent heterogeneous
stochastic linear bandits framework, where the agents (users) are similar but
not all identical. We model user heterogeneity using two popularly used ideas
in practice; (i) A clustering framework where users are partitioned into groups
with users in the same group being identical to each other, but different
across groups, and (ii) a personalization framework where no two users are
necessarily identical, but a user's parameters are close to that of the
population average. In the clustered users' setup, we propose a novel
algorithm, based on successive refinement of cluster identities and regret
minimization. We show that, for any agent, the regret scales as
$\mathcal{O}(\sqrt{T/N})$, if the agent is in a `well separated' cluster, or
scales as $\mathcal{O}(T^{\frac{1}{2} + \varepsilon}/(N)^{\frac{1}{2}
-\varepsilon})$ if its cluster is not well separated, where $\varepsilon$ is
positive and arbitrarily close to $0$. Our algorithm is adaptive to the cluster
separation, and is parameter free -- it does not need to know the number of
clusters, separation and cluster size, yet the regret guarantee adapts to the
inherent complexity. In the personalization framework, we introduce a natural
algorithm where, the personal bandit instances are initialized with the
estimates of the global average model. We show that, an agent $i$ whose
parameter deviates from the population average by $\epsilon_i$, attains a
regret scaling of $\widetilde{O}(\epsilon_i\sqrt{T})$. This demonstrates that
if the user representations are close (small $\epsilon_i)$, the resulting
regret is low, and vice-versa. The results are empirically validated and we
observe superior performance of our adaptive algorithms over non-adaptive
baselines.
- Abstract（参考訳）: エージェント(ユーザ)が似ているが、すべて同一ではないような、N$エージェントの不均一な確率的線形包帯フレームワークにおける後悔を最小限に抑える問題を考える。
我々は,2つの一般的なアイデアを用いて,ユーザ不均一性をモデル化する。 (i) 同一グループ内のユーザ同士が同一であるが,グループ間で異なるグループに分割されたクラスタリングフレームワーク, (ii) 2人のユーザが必ずしも同一ではないが,ユーザのパラメータが人口平均に近いパーソナライズフレームワーク。
クラスタ化ユーザの設定において,クラスタのアイデンティティの連続的改善と後悔の最小化に基づく新しいアルゴリズムを提案する。
任意のエージェントに対して、後悔のスケールが $\mathcal{O}(\sqrt{T/N})$、エージェントが 'well separated' クラスタにある場合、または $\mathcal{O}(T^{\frac{1}{2} + \varepsilon}/(N)^{\frac{1}{2} -\varepsilon})$、クラスタが十分に分離されていない場合、$\varepsilon$は正で、任意に$0$である。
私たちのアルゴリズムはクラスタ分離に適応しており、パラメータフリーです -- クラスタの数や分離、クラスタサイズを知る必要はありませんが、後悔の保証は固有の複雑さに適応します。
パーソナライズフレームワークでは,グローバル平均モデルの推定値に基づいて,個人的帯域幅のインスタンスを初期化する自然なアルゴリズムを導入する。
パラメータが$\epsilon_i$から$\epsilon_i$にずれたエージェント$i$は、$\widetilde{O}(\epsilon_i\sqrt{T})$の後悔のスケーリングを実現する。
これは、ユーザ表現が近い場合(小さな$\epsilon_i)$、結果として生じる後悔は低く、逆であることを示している。
その結果は実証的に検証され,非適応ベースラインに対する適応アルゴリズムの優れた性能が観察される。
関連論文リスト
- Instance-Optimal Cluster Recovery in the Labeled Stochastic Block Model [79.46465138631592]
観測されたラベルを用いてクラスタを復元する効率的なアルゴリズムを考案する。
本稿では,期待値と高い確率でこれらの下位境界との性能を一致させる最初のアルゴリズムであるIACを提案する。
論文 参考訳（メタデータ） (2023-06-18T08:46:06Z) - Optimal Algorithms for Latent Bandits with Cluster Structure [50.44722775727619]
本稿では,複数のユーザが存在するクラスタ構造を持つ潜伏包帯問題と関連するマルチアーム包帯問題とを考察する。
本稿では,潜伏クラスタ構造を利用して$widetildeO(sqrt(mathsfM+mathsfN)mathsfTの最小限の後悔を提供するLATTICEを提案する。
論文 参考訳（メタデータ） (2023-01-17T17:49:04Z) - An Improved Algorithm for Clustered Federated Learning [29.166363192740768]
本稿では、フェデレートラーニング(FL)における異種モデル間の二分法と同時学習について述べる。
ユーザの(最適)局所モデルに基づいてFLの新しいクラスタリングモデルを定義する。
textttSR-FCAは、クラスタ内の堅牢な学習アルゴリズムを使用して、同時トレーニングとクラスタエラーの修正を行う。
論文 参考訳（メタデータ） (2022-10-20T19:14:36Z) - Optimal Clustering with Bandit Feedback [57.672609011609886]
本稿では,バンディットフィードバックを用いたオンラインクラスタリングの問題点について考察する。
これは、NPハード重み付きクラスタリング問題をサブルーチンとして解決する必要性を回避するための、シーケンシャルなテストのための新しい停止規則を含む。
合成および実世界のデータセットの広範なシミュレーションを通して、BOCの性能は下界と一致し、非適応的ベースラインアルゴリズムよりも大幅に優れることを示す。
論文 参考訳（メタデータ） (2022-02-09T06:05:05Z) - Personalized Federated Learning via Convex Clustering [72.15857783681658]
本稿では,局所凸型ユーザコストを用いた個人化フェデレーション学習のためのアルゴリズム群を提案する。
提案するフレームワークは,異なるユーザのモデルの違いをペナル化する凸クラスタリングの一般化に基づいている。
論文 参考訳（メタデータ） (2022-02-01T19:25:31Z) - Fuzzy Clustering with Similarity Queries [56.96625809888241]
ファジィ(fuzzy, soft objective)は、よく知られた$k$-means問題の一般化である。
クエリを少なくすることで、問題の解決が容易になる。
論文 参考訳（メタデータ） (2021-06-04T02:32:26Z) - K-expectiles clustering [0.0]
本稿では,期待値に基づく分割クラスタリングアルゴリズムを提案する。
固定$tau$クラスタリングと適応$tau$クラスタリングの2つのスキームを提案します。
論文 参考訳（メタデータ） (2021-03-16T21:14:56Z) - Computationally efficient sparse clustering [67.95910835079825]
我々はPCAに基づく新しいクラスタリングアルゴリズムの有限サンプル解析を行う。
ここでは,ミニマックス最適誤クラスタ化率を,体制$|theta infty$で達成することを示す。
論文 参考訳（メタデータ） (2020-05-21T17:51:30Z) - Explainable $k$-Means and $k$-Medians Clustering [25.513261099927163]
我々は、小さな決定木を使ってデータセットをクラスタに分割し、クラスタを直接的な方法で特徴付けることを検討する。
一般的なトップダウン決定木アルゴリズムが任意のコストでクラスタリングに繋がる可能性があることを示す。
我々は、$k$の葉を持つ木を用いて説明可能なクラスタを生成する効率的なアルゴリズムを設計する。
論文 参考訳（メタデータ） (2020-02-28T04:21:53Z) - Query-Efficient Correlation Clustering [13.085439249887713]
相関クラスタリングはクラスタリングの最も自然な定式化であることは間違いない。
相関クラスタリングの主な欠点は、入力として$Theta(n2)$ペアの類似性を必要とすることである。
我々は,最大3cdot OPT + O(fracn3Q)$の相違点が期待される解が得られる相関クラスタリングアルゴリズムを考案した。
論文 参考訳（メタデータ） (2020-02-26T15:18:20Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。