論文の概要: One-Bit Clustering for Two Component Sub-Gaussian Mixture Models

• arxiv url: http://arxiv.org/abs/2606.21873v1
• Date: Sat, 20 Jun 2026 04:18:08 GMT
• ステータス: 情報取得中
• システム内更新日: 2026-06-23 15:11:08.98427
• Title: One-Bit Clustering for Two Component Sub-Gaussian Mixture Models
• Title（参考訳）: 2成分準ガウス混合モデルのための1ビットクラスタリング
• Authors: Junren Chen, Yun Yang,
• Abstract要約: 2成分のガウス混合モデルに対する最初の1ビットクラスタリング法を提案する。 この方法は、ディザード量子化器によって得られた各サンプルのエントリ毎に1ビットしか使用しない。
• 参考スコア（独自算出の注目度）: 17.177800879292963
• License:
• Abstract: Clustering is a fundamental problem in statistics and machine learning. We propose the first one-bit clustering method for two-component sub-Gaussian mixture models. The method uses only one bit per entry of each sample obtained via a dithered quantizer. Under a mild non-spikiness condition on the cluster centers, we show that a variant of Lloyd's algorithm achieves a misclassification rate that decays exponentially with a signal-to-noise ratio comparable to that in the unquantized setting. This result further implies exact recovery under an explicit separation condition, which exceeds the optimal threshold for unquantized data by only a logarithmic factor. When the dimension $p$ is sufficiently large, the non-spikiness condition can be enforced by applying a random rotation using a Haar distributed matrix prior to quantization. In particular, it holds with high probability when $p \gtrsim 1$ for partial recovery and $p \gtrsim \log n \log\log n$ for exact recovery, where $n$ is the sample size. We also establish a minimax lower bound, showing that the misclassification rate and separation condition exhibit sharp constants in general. Numerical results are provided to corroborate the theory and demonstrate the efficacy of the proposed method.
• Abstract（参考訳）: クラスタリングは統計学と機械学習の基本的な問題である。 2成分のガウス混合モデルに対する最初の1ビットクラスタリング法を提案する。 この方法は、ディザード量子化器によって得られた各サンプルのエントリ毎に1ビットしか使用しない。 クラスター中心における緩やかな非スパイク性条件の下では、ロイドのアルゴリズムの変種が不等化条件の信号-雑音比と比例して指数関数的に減衰する誤分類率を達成することを示す。 この結果は、対数係数のみによる不定値データの最適しきい値を超える明示的な分離条件下での正確な回復をさらに意味する。 次元$p$が十分大きいとき、量子化に先立ってハール分布行列を用いてランダムな回転を適用することで、非スパイキネス条件を適用できる。 特に、部分回復には$p \gtrsim 1$、正確な回復には$p \gtrsim \log n \log n$、サンプルサイズは$n$である。 また,誤分類率と分離条件が一般に鋭い定数を示すことを示し,ミニマックス下限を確立した。 提案手法の有効性を裏付ける数値的な結果を得た。

関連論文リスト

• Distributionally Robust K-Means Clustering [18.037323759791658]
  K平均のクラスタリングは、異常値、分布シフト、サンプルサイズに制限があることで知られている。 我々はそのような病態から保護する分布的に堅牢な変種を開発する。 トラクタブル双対は、ハード割り当てを滑らかに重み付けされたものに置き換えるソフトクラスタリングスキームを得る。
  論文  参考訳（メタデータ） (2026-04-13T07:32:36Z)
• Preparing Fermions via Classical Sampling and Linear Combinations of Unitaries [0.0]
  フェルミオン量子状態の効率的なフォールトトレラント化を可能にするQubits (E$OQ) フレームワーク上でのEvolving density matricesの拡張を提案する。 元の方法はサンプリングによって状態の準備を回避しているが、フェミオン系では多くの必要な回路に繋がるサイン問題に直面している。
  論文  参考訳（メタデータ） (2026-03-23T18:01:03Z)
• Almost Asymptotically Optimal Active Clustering Through Pairwise Observations [59.20614082241528]
  そこで本研究では, ノイズと能動的に収集された応答を用いて, M$アイテムを未知数の$K$個別グループにクラスタリングするための新しい分析フレームワークを提案する。 クラスタリングの精度に対する望ましい信頼性を達成するのに必要なクエリ数の基本的下位境界を確立する。 我々は、一般化された同値比統計の計算可能な変種を開発し、その下限に対する性能ギャップを正確に推定できることを実証的に示す。
  論文  参考訳（メタデータ） (2026-02-05T14:16:47Z)
• 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)
• 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)
• Stochastic regularized majorization-minimization with weakly convex and multi-convex surrogates [0.0]
  提案アルゴリズムの最初の最適性ギャップは,非テンソル依存データ設定下での様々な手法の期待損失率で減衰することを示す。 非テンション依存データ設定の下で, 各種手法の収束点を求める。
  論文  参考訳（メタデータ） (2022-01-05T15:17:35Z)
• Computationally efficient sparse clustering [67.95910835079825]
  我々はPCAに基づく新しいクラスタリングアルゴリズムの有限サンプル解析を行う。 ここでは,ミニマックス最適誤クラスタ化率を,体制$|theta infty$で達成することを示す。
  論文  参考訳（メタデータ） (2020-05-21T17:51:30Z)
• Outlier-Robust Clustering of Non-Spherical Mixtures [5.863264019032882]
  統計的に分離されたd-次元ガウスアン(k-GMM)の混合をクラスタリングするための最初のアウトリー・ローバストアルゴリズムを与える。 この結果は、$d$次元単位球面上の均一分布の任意のアフィン変換のクラスタリング混合に拡張される。
  論文  参考訳（メタデータ） (2020-05-06T17:24:27Z)
• Efficient Clustering for Stretched Mixtures: Landscape and Optimality [4.2111286819721485]
  本稿では,2つの楕円分布の平衡混合から抽出された未ラベルのサンプルを受信する正準クラスタリング問題について考察する。 非最適クラスタリング関数は、サンプルサイズが一定の統計的目標を超えると、望ましい幾何学的性質を示す。
  論文  参考訳（メタデータ） (2020-03-22T17:57:07Z)

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

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