論文の概要: 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)に関して厳密性を達成する。
関連論文リスト
- Near-Optimal Clustering in Mixture of Markov Chains [74.3828414695655]
我々は、長さ$H$の軌跡を、大きさ$S$の有限状態空間上の未知のエルゴードマルコフ鎖の1つによって生成される、$T$ trajectories of length $H$の問題を研究する。
我々は、連鎖の遷移核間の重み付きKL分散によって支配されるクラスタリングエラー率に基づいて、インスタンス依存で高い確率の低い境界を導出する。
次に,新しい2段階クラスタリングアルゴリズムを提案する。
論文 参考訳（メタデータ） (2025-06-02T05:10:40Z) - 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) - Testing with Non-identically Distributed Samples [19.421846478881363]
本研究では,サンプルが独立に分布するが同一に分布しない設定に対して,サブ線形サンプル特性試験と推定が適用範囲について検討する。
それぞれの分布から$c=1$のサンプルが与えられた場合、$k$の線形なサンプル数が必要であることを示す。
2つの分布の「クローズネス」をテストする問題に我々の手法を拡張します。
論文 参考訳（メタデータ） (2023-11-19T01:25:50Z) - Replicable Clustering [57.19013971737493]
我々は,統計学的な$k$-medians,統計学的な$k$-means,統計学的な$k$-centers問題のアルゴリズムをブラックボックス方式で近似ルーチンを用いて提案する。
理論的結果を検証するブラックボックスとしてsklearnの$k$-means++実装を用いた2次元合成分布の実験も行っている。
論文 参考訳（メタデータ） (2023-02-20T23:29:43Z) - 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) - $k$-Variance: A Clustered Notion of Variance [23.57925128327]
我々は,ランダム二成分マッチングの機構に基づく分散の一般化である $k$-variance を導入する。
1次元測度、クラスター測度、低次元部分集合に集中した測度など、いくつかの重要な場合において、この量の詳細分析を行う。
論文 参考訳（メタデータ） (2020-12-13T04:25:32Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。