論文の概要: Efficient Clustering in Stochastic Bandits

• arxiv url: http://arxiv.org/abs/2601.09162v1
• Date: Wed, 14 Jan 2026 05:05:58 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-01-15 18:59:20.273488
• Title: Efficient Clustering in Stochastic Bandits
• Title（参考訳）: 確率帯域における効率的なクラスタリング
• Authors: G Dhinesh Chandran, Kota Srinivas Reddy, Srikrishna Bhashyam,
• Abstract要約: 固定された信頼設定の下でBandit Clustering(BC)問題について検討する。 目的は、シーケンシャルサンプリングを通じてデータシーケンス(アーム)の集合をクラスタにまとめることである。 本稿では,各時間ステップで最適な値に向かって1ステップずつの効率的な帯域クラスタリングアルゴリズム(EBC)を提案する。
• 参考スコア（独自算出の注目度）: 4.211510706776733
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study the Bandit Clustering (BC) problem under the fixed confidence setting, where the objective is to group a collection of data sequences (arms) into clusters through sequential sampling from adaptively selected arms at each time step while ensuring a fixed error probability at the stopping time. We consider a setting where arms in a cluster may have different distributions. Unlike existing results in this setting, which assume Gaussian-distributed arms, we study a broader class of vector-parametric distributions that satisfy mild regularity conditions. Existing asymptotically optimal BC algorithms require solving an optimization problem as part of their sampling rule at each step, which is computationally costly. We propose an Efficient Bandit Clustering algorithm (EBC), which, instead of solving the full optimization problem, takes a single step toward the optimal value at each time step, making it computationally efficient while remaining asymptotically optimal. We also propose a heuristic variant of EBC, called EBC-H, which further simplifies the sampling rule, with arm selection based on quantities computed as part of the stopping rule. We highlight the computational efficiency of EBC and EBC-H by comparing their per-sample run time with that of existing algorithms. The asymptotic optimality of EBC is supported through simulations on the synthetic datasets. Through simulations on both synthetic and real-world datasets, we show the performance gain of EBC and EBC-H over existing approaches.
• Abstract（参考訳）: 固定された信頼設定の下でBandit Clustering(BC)問題について検討し、各ステップで適応的に選択されたアームからの逐次サンプリングによってデータシーケンス(アーム)の集合をクラスタにグループ化し、停止時の固定エラー確率を確保する。 クラスタ内のアームが異なる分布を持つような設定を考える。 ガウス分布アームを仮定するこの設定における既存の結果とは異なり、軽度の正則性条件を満たすベクトルパラメトリック分布のより広範なクラスについて研究する。 既存の漸近的に最適なBCアルゴリズムでは、各ステップでサンプリングルールの一部として最適化問題を解く必要があり、計算にコストがかかる。 本稿では,全最適化問題を解く代わりに,各時間ステップの最適値に向けて1ステップを要し,漸近的に最適でありながら計算的に効率的な帯域クラスタリングアルゴリズム(EBC)を提案する。 また、EBC のヒューリスティックな変種 EBC-H を提案し、サンプリングルールをさらに単純化し、停止規則の一部として計算された量に基づいてアームの選択を行う。 本稿では,既存のアルゴリズムと比較して,EBCとEBC-Hの計算効率を強調した。 EBCの漸近最適性は、合成データセットのシミュレーションによって支持される。 合成データセットと実世界のデータセットのシミュレーションにより、既存のアプローチよりもEBCとEBC-Hの性能向上を示す。

関連論文リスト

• Exact and Heuristic Algorithms for Constrained Biclustering [0.0]
  コクラスタリング(co-clustering)または双方向クラスタリング( two-way clustering)とも呼ばれるビクラスタリングは、データマトリックスの行と列を同時にパーティショニングすることで、コヒーレントパターンによるサブマトリクスを明らかにする。 我々は、オブジェクトが同一または異なるビクラスタに属するべきか否かを規定する制約付きビクラスタリング、すなわち、マスタリンクとナントリンクの制約について研究する。
  論文  参考訳（メタデータ） (2025-08-07T15:29:22Z)
• A Near-Optimal Single-Loop Stochastic Algorithm for Convex Finite-Sum Coupled Compositional Optimization [53.14532968909759]
  ALEXRと呼ばれる,効率的な単ループプリマル・デュアルブロック座標アルゴリズムを提案する。 本研究では, ALEXR の凸面および強凸面の収束速度を滑らか性および非滑らか性条件下で確立する。 CFCCO の ROC 曲線の下での GDRO および部分領域の実験結果から,提案アルゴリズムの有望な性能を示す。
  論文  参考訳（メタデータ） (2023-12-04T19:00:07Z)
• Selection of the Most Probable Best [2.1095005405219815]
  予測値ランキングと選択(R&S)問題では,すべてのk解のシミュレーション出力が,分布によって不確実性をモデル化可能な共通パラメータに依存する。 我々は、最も確率の高い最適解 (MPB) を、分布に関して最適である確率が最も大きい解と定義する。 最適化条件における未知の手段をその推定値に置き換えるアルゴリズムを考案し,シミュレーション予算が増加するにつれて,アルゴリズムのサンプリング比が条件を満たすことを証明した。
  論文  参考訳（メタデータ） (2022-07-15T15:27:27Z)
• Optimal Clustering with Bandit Feedback [57.672609011609886]
  本稿では,バンディットフィードバックを用いたオンラインクラスタリングの問題点について考察する。 これは、NPハード重み付きクラスタリング問題をサブルーチンとして解決する必要性を回避するための、シーケンシャルなテストのための新しい停止規則を含む。 合成および実世界のデータセットの広範なシミュレーションを通して、BOCの性能は下界と一致し、非適応的ベースラインアルゴリズムよりも大幅に優れることを示す。
  論文  参考訳（メタデータ） (2022-02-09T06:05:05Z)
• Adaptive Sequential SAA for Solving Two-stage Stochastic Linear Programs [1.6181085766811525]
  大規模2段階線形プログラムを解くための適応的逐次SAA(sample average approximation)アルゴリズムを提案する。 提案アルゴリズムは,品質の確率論的保証が与えられた解を返すために,有限時間で停止することができる。
  論文  参考訳（メタデータ） (2020-12-07T14:58:16Z)
• Multi-View Spectral Clustering with High-Order Optimal Neighborhood Laplacian Matrix [57.11971786407279]
  マルチビュースペクトルクラスタリングは、データ間の固有のクラスタ構造を効果的に明らかにすることができる。 本稿では,高次最適近傍ラプラシア行列を学習するマルチビュースペクトルクラスタリングアルゴリズムを提案する。 提案アルゴリズムは, 1次ベースと高次ベースの両方の線形結合の近傍を探索し, 最適ラプラシア行列を生成する。
  論文  参考訳（メタデータ） (2020-08-31T12:28:40Z)
• Non-Adaptive Adaptive Sampling on Turnstile Streams [57.619901304728366]
  カラムサブセット選択、部分空間近似、射影クラスタリング、および空間サブリニアを$n$で使用するターンタイルストリームのボリュームに対する最初の相対エラーアルゴリズムを提供する。 我々の適応的なサンプリング手法は、様々なデータ要約問題に多くの応用をもたらしており、これは最先端を改善するか、より緩和された行列列モデルで以前に研究されただけである。
  論文  参考訳（メタデータ） (2020-04-23T05:00:21Z)
• Clustering Binary Data by Application of Combinatorial Optimization Heuristics [52.77024349608834]
  本稿では,2値データのクラスタリング手法について検討し,まず,クラスタのコンパクトさを計測するアグリゲーション基準を定義した。 近隣地域と人口動態最適化メタヒューリスティックスを用いた5つの新しいオリジナル手法が導入された。 準モンテカルロ実験によって生成された16のデータテーブルから、L1の相似性と階層的クラスタリング、k-means(メドイドやPAM)の1つのアグリゲーションの比較を行う。
  論文  参考訳（メタデータ） (2020-01-06T23:33:31Z)

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

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