論文の概要: Almost Asymptotically Optimal Active Clustering Through Pairwise Observations

• arxiv url: http://arxiv.org/abs/2602.05690v1
• Date: Thu, 05 Feb 2026 14:16:47 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-02-06 18:49:08.966295
• Title: Almost Asymptotically Optimal Active Clustering Through Pairwise Observations
• Title（参考訳）: ペアワイズ観測によるほぼ漸近的最適アクティブクラスタリング
• Authors: Rachel S. Y. Teo, P. N. Karthik, Ramya Korlakai Vinayak, Vincent Y. F. Tan,
• Abstract要約: そこで本研究では, ノイズと能動的に収集された応答を用いて, M$アイテムを未知数の$K$個別グループにクラスタリングするための新しい分析フレームワークを提案する。 クラスタリングの精度に対する望ましい信頼性を達成するのに必要なクエリ数の基本的下位境界を確立する。 我々は、一般化された同値比統計の計算可能な変種を開発し、その下限に対する性能ギャップを正確に推定できることを実証的に示す。
• 参考スコア（独自算出の注目度）: 59.20614082241528
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We propose a new analysis framework for clustering $M$ items into an unknown number of $K$ distinct groups using noisy and actively collected responses. At each time step, an agent is allowed to query pairs of items and observe bandit binary feedback. If the pair of items belongs to the same (resp.\ different) cluster, the observed feedback is $1$ with probability $p>1/2$ (resp.\ $q<1/2$). Leveraging the ubiquitous change-of-measure technique, we establish a fundamental lower bound on the expected number of queries needed to achieve a desired confidence in the clustering accuracy, formulated as a sup-inf optimization problem. Building on this theoretical foundation, we design an asymptotically optimal algorithm in which the stopping criterion involves an empirical version of the inner infimum -- the Generalized Likelihood Ratio (GLR) statistic -- being compared to a threshold. We develop a computationally feasible variant of the GLR statistic and show that its performance gap to the lower bound can be accurately empirically estimated and remains within a constant multiple of the lower bound.
• Abstract（参考訳）: そこで本研究では, ノイズと能動的に収集された応答を用いて, M$アイテムを未知数の$K$個別グループにクラスタリングするための新しい分析フレームワークを提案する。 各ステップでは、エージェントがアイテムのペアをクエリして、ランディットバイナリフィードバックを観察することが可能になる。 アイテムのペアが同じものに属している場合(resp)。 異なる)クラスタでは、観測されたフィードバックは1ドル、確率$p>1/2$(resp)である。 は$q<1/2$。 ユビキタスな測定手法を用いることで、クラスタリングの精度に望ましい信頼性を実現するために必要となるクエリ数の期待値の基本的な下限を確立し、sup-inf最適化問題として定式化する。 この理論の基礎の上に構築された漸近的に最適なアルゴリズムを設計し、停止基準は、内部のインフィムの実証的なバージョン、すなわち一般化された好奇率(GLR)統計値がしきい値と比較される。 我々は,GLR統計量の計算可能な変種を開発し,その性能ギャップを実験的に推定し,下界の定数倍の範囲内に留まることを示す。

関連論文リスト

• EVaR-Optimal Arm Identification in Bandits [7.340828059560291]
  The fixed-confidence best arm identification problem in the multiarmed bandit (MAB) framework under the Entropic Value-at-Risk criterion。
  論文  参考訳（メタデータ） (2025-10-06T11:49:56Z)
• Asymptotically Optimal Linear Best Feasible Arm Identification with Fixed Budget [55.938644481736446]
  本稿では,誤差確率の指数的減衰を保証し,最適な腕識別のための新しいアルゴリズムを提案する。 我々は,複雑性のレベルが異なる様々な問題インスタンスに対する包括的経験的評価を通じて,アルゴリズムの有効性を検証する。
  論文  参考訳（メタデータ） (2025-06-03T02:56:26Z)
• One-shot Robust Federated Learning of Independent Component Analysis [16.462282750354408]
  そこで我々は,$k$-meansクラスタリングを利用して局所的クライアント推定における置換あいまいさを解消する幾何的中央値に基づく集約アルゴリズムを提案する。 提案手法は,まず,クライアントが提供する推定器をクラスタに分割し,次に幾何学的中央値を用いて各クラスタ内の推定器を集約するk-meansを実行する。
  論文  参考訳（メタデータ） (2025-05-26T21:37:19Z)
• Efficient Algorithms for Empirical Group Distributional Robust Optimization and Beyond [15.664414751701718]
  経験的GDROを$textittwo-level$ finite-sum convex-concave minimax Optimization問題として定式化する。 我々は、スナップショットとミラースナップショットポイントを1インデックスシフトした重み付き平均で計算し、単純エルゴディック平均と区別する。 注目すべきは、我々の手法が最先端の手法よりも$sqrtm$で優れていることだ。
  論文  参考訳（メタデータ） (2024-03-06T09:14:24Z)
• Revisiting Instance-Optimal Cluster Recovery in the Labeled Stochastic Block Model [85.51611950757643]
  IAC (Instance-Adaptive Clustering, インスタンス適応クラスタリング) を提案する。 IACは$ MathcalO(n, textpolylog(n) $の計算複雑性を維持しており、大規模問題に対してスケーラブルで実用的なものである。
  論文  参考訳（メタデータ） (2023-06-18T08:46:06Z)
• Optimal Clustering with Bandit Feedback [57.672609011609886]
  本稿では,バンディットフィードバックを用いたオンラインクラスタリングの問題点について考察する。 これは、NPハード重み付きクラスタリング問題をサブルーチンとして解決する必要性を回避するための、シーケンシャルなテストのための新しい停止規則を含む。 合成および実世界のデータセットの広範なシミュレーションを通して、BOCの性能は下界と一致し、非適応的ベースラインアルゴリズムよりも大幅に優れることを示す。
  論文  参考訳（メタデータ） (2022-02-09T06:05:05Z)

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

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