論文の概要: A Distribution Testing Approach to Clustering Distributions

• arxiv url: http://arxiv.org/abs/2512.08376v1
• Date: Tue, 09 Dec 2025 09:01:41 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-12-10 22:28:07.887299
• Title: A Distribution Testing Approach to Clustering Distributions
• Title（参考訳）: クラスタリング分布に対する分布試験手法
• Authors: Gunjan Kumar, Yash Pote, Jonathan Scarlett,
• Abstract要約: 2つのグループに$k$の分散を隠されたパーティションが与えられると、そのパーティションを回復することがゴールである。 2つの基本事例に対して,サンプルの複雑さの上限と下限を定めている。 特に、すべてのレジームに対して$(n,k,r,varepsilon)$(最大$O(log k)$ factor)に関して厳密性を達成する。
• 参考スコア（独自算出の注目度）: 35.016184519329194
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study the following distribution clustering problem: Given a hidden partition of $k$ distributions into two groups, such that the distributions within each group are the same, and the two distributions associated with the two clusters are $\varepsilon$-far in total variation, the goal is to recover the partition. We establish upper and lower bounds on the sample complexity for two fundamental cases: (1) when one of the cluster's distributions is known, and (2) when both are unknown. Our upper and lower bounds characterize the sample complexity's dependence on the domain size $n$, number of distributions $k$, size $r$ of one of the clusters, and distance $\varepsilon$. In particular, we achieve tightness with respect to $(n,k,r,\varepsilon)$ (up to an $O(\log k)$ factor) for all regimes.
• Abstract（参考訳）: 各グループ内の分布が同じであり、2つのクラスタに関連する2つの分布が合計変動で$\varepsilon$-farであるように、$k$の分布を2つのグループに隠された分割を与えられた場合、その分割を回復することが目的である。 我々は,(1)クラスタの分布の1つが分かっている場合,(2)両者が未知である場合,の2つの基本事例に対して,サンプル複雑性の上限と下限を定めている。 上と下の境界は、サンプルの複雑さがドメインサイズ$n$、分布数$k$、クラスタの1つのサイズ$r$、距離$\varepsilon$に依存することを特徴付けています。 特に、すべてのレジームに対して$(n,k,r,\varepsilon)$(最大$O(\log k)$ factor)に関して厳密性を達成する。

関連論文リスト

• Exponentially Consistent Nonparametric Linkage-Based Clustering of Data Sequences [4.2603120588176635]
  我々は、未知の分布から生成されたM$独立かつ同一の(d.d.)データ列の非パラメトリッククラスタリングを考える。 M$のデータシーケンスの分布は、基礎となる分散クラスタの$K$に属する。
  論文  参考訳（メタデータ） (2024-11-21T08:18:04Z)
• Clustering Mixtures of Bounded Covariance Distributions Under Optimal Separation [44.25945344950543]
  境界共分散分布の混合に対するクラスタリング問題について検討する。 このクラスタリングタスクに対して,最初のポリ時間アルゴリズムを提案する。 我々のアルゴリズムは、対数外乱の$Omega(alpha)$-fractionに対して堅牢である。
  論文  参考訳（メタデータ） (2023-12-19T01:01:53Z)
• Stochastic Approximation Approaches to Group Distributionally Robust Optimization and Beyond [89.72693227960274]
  本稿では,グループ分散ロバスト最適化 (GDRO) を,$m$以上の異なる分布をうまく処理するモデルを学習する目的で検討する。 各ラウンドのサンプル数を$m$から1に抑えるため、GDROを2人でプレイするゲームとして、一方のプレイヤーが実行し、他方のプレイヤーが非公開のマルチアームバンディットのオンラインアルゴリズムを実行する。 第2のシナリオでは、最大リスクではなく、平均的最上位k$リスクを最適化し、分散の影響を軽減することを提案する。
  論文  参考訳（メタデータ） (2023-02-18T09:24:15Z)
• Sum-of-norms clustering does not separate nearby balls [49.1574468325115]
  我々は,データセットを一般的な測度に置き換えた,和和クラスタリングの連続的なバージョンを示す。 我々は,離散データポイントの場合においても,新たなクラスタリングの局所的特徴を記述し,証明する。
  論文  参考訳（メタデータ） (2021-04-28T13:35:17Z)

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

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