論文の概要: Low-degree polynomials lower bounds for clustering in small dimension

• arxiv url: http://arxiv.org/abs/2610.37272v1
• Date: Tue, 27 Oct 2026 14:02:43 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-10-28 21:04:31.65055
• Title: Low-degree polynomials lower bounds for clustering in small dimension
• Title（参考訳）: 小次元クラスタリングのための低次多項式下界
• Abstract要約: 我々は、K$等方分布の混合から引き出された$n$観測の計算限界について検討する。 特に、多対数分離では、低次は多対数因子まで、$ngtrsim K2d3/2$の観測を必要とする。
• 参考スコア（独自算出の注目度）: 53.03724383992195
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study the computational limits of clustering $n$ observations drawn from a mixture of $K$ isotropic distributions in $\mathbb R^d$, in the regime where the number $K$ of groups is much larger than the dimension $d$. In this regime, tensor-based procedures recover the partition with a polylogarithmic separation between the centers, but they require a sample size that is a large and non-explicit polynomial of $dK$, whereas the existing low-degree lower bounds only show that $n$ must be larger than $dK^2$. We introduce a mixture of $2K$ product Bernoulli distributions on $\{0,1\}^d$, with $K=(d+1)^m$, whose centers are built from a dual BCH code. This construction ensures that the moment tensors of the observations coincide with those of the uniform distribution on $\{-1,1\}^d$ up to the order $2m+1$. For any fixed $m$, we establish a low-degree polynomial lower bound showing that clustering is hard as long as the separation $Δ$ satisfies $Δ^2\ll(K^2d^{3/2}/n)^{1/(2m+2)}\wedge\sqrt d$, up to polylogarithmic factors. In particular, with a polylogarithmic separation, low-degree polynomials require $n\gtrsim K^2d^{3/2}$ observations, up to polylogarithmic factors. Through a Gaussianization argument, this hardness carries over, in the sense of reductions, to isotropic Gaussian mixtures. Our proof relies on a family of polynomials of the observations, indexed by bipartite graphs, which is almost orthonormal. The moments of these polynomials are governed by the number of solutions of polynomial systems over the finite field $\mathbb F\_{d+1}$ that are induced by the BCH code, and the crux of our analysis is to connect the combinatorial structure of the bipartite graphs with the structure of the solution sets of these systems.
• Abstract（参考訳）: 我々は、$K$の等方分布の混合から引き出された$n$のクラスタリングの計算限界を$\mathbb R^d$で調べる。 この状態において、テンソルベースの手順は、中心間の多対数分離で分割を回復するが、それらは、dK$の大きく非明示的な多項式であるサンプルサイズを必要とするが、既存の低次下界は、$n$が$dK^2$より大きいことを示さなければならない。 我々は、${0,1\}^d$ と$K=(d+1)^m$ に 2K の積ベルヌーイ分布を導入する。 この構成により、観測のモーメントテンソルは、$\{-1,1\}^d$ 上の均一分布のテンソルと 2m+1$ まで一致することが保証される。 任意の固定$m$に対して、分離 $Δ$ が $Δ^2\ll(K^2d^{3/2}/n)^{1/(2m+2)}\wedge\sqrt d$ を満たす限り、クラスタリングが困難であることを示す低次多項式の下界を確立する。 特に、多対数分離では、低次多項式は多対数因子まで、$n\gtrsim K^2d^{3/2}$観測を必要とする。 ガウス化の議論を通じて、この硬さは還元の意味において等方的なガウス混合へと引き継がれる。 我々の証明は、ほぼ正則な二部グラフでインデックスされた観測の多項式の族に依存している。 これらの多項式のモーメントは、BCH符号によって誘導される有限体 $\mathbb F\_{d+1}$ 上の多項式系の解の数によって支配され、我々の分析の要点は、二部グラフの組合せ構造とこれらの系の解集合の構造を結びつけることである。

関連論文リスト

• A solution to the Erdős Problem #1040 [0.0]
  任意の閉無限集合に対して$vartheta(K)$が$FsubsetmathbbC$transfinite diameter at least oneであることを証明する。
  論文  参考訳（メタデータ） (2026-09-05T12:11:52Z)
• Where Multipartite Entanglement Localizes: The Junction Law for Genuine Multi-Entropy [2.477977081568645]
  ギャップ付き局所系における真の多部絡み合いに対する「ジャンクション法則」を見いだす。 このギャップ付き自由フェルミオン設定では、真の多重粒子の絡み合いは、ジャンクションの相関長近傍に局在する。
  論文  参考訳（メタデータ） (2026-02-18T10:12:06Z)
• A Unified Framework for Uniform Signal Recovery in Nonlinear Generative Compressed Sensing [68.80803866919123]
  非線形測定では、ほとんどの先行結果は一様ではない、すなわち、すべての$mathbfx*$に対してではなく、固定された$mathbfx*$に対して高い確率で保持される。 本フレームワークはGCSに1ビット/一様量子化観測と単一インデックスモデルを標準例として適用する。 また、指標集合が計量エントロピーが低い製品プロセスに対して、より厳密な境界を生み出す濃度不等式も開発する。
  論文  参考訳（メタデータ） (2023-09-25T17:54:19Z)
• Quantum and classical low-degree learning via a dimension-free Remez inequality [52.12931955662553]
  ハイパーグリッド上の関数をポリトーラス上の高調波拡張に関連付ける新しい方法を示す。 巡回群 $exp(2pi i k/K)_k=1K$ の積に対して函数の上限が$f$であることを示す。 我々は最近、超キューブやキュービット上の観測可能な観測値の低次学習を、同様に効率的に行う方法として、EI22, CHP, VZ22を引用して、新しい空間に拡張した。
  論文  参考訳（メタデータ） (2023-01-04T04:15:40Z)
• Low-degree learning and the metric entropy of polynomials [44.99833362998488]
  少なくとも$Omega(sqrtvarepsilon)2dlog n leq log mathsfM(mathscrF_n,d,|cdot|_L,varepsilon)は2辺の推定値$c(1-varepsilon)2dlogを満たす。
  論文  参考訳（メタデータ） (2022-03-17T23:52:08Z)
• Stochastic behavior of outcome of Schur-Weyl duality measurement [45.41082277680607]
  我々は、$n$ qubits上のシュル=ワイル双対性に基づく分解によって定義される測定に焦点をあてる。 我々は、$n$が無限大に進むとき、中心極限の一種を含む様々な種類の分布を導出する。
  論文  参考訳（メタデータ） (2021-04-26T15:03:08Z)
• Robustly Learning any Clusterable Mixture of Gaussians [55.41573600814391]
  本研究では,高次元ガウス混合系の対向ロバスト条件下での効率的な学習性について検討する。 理論的に最適に近い誤り証明である$tildeO(epsilon)$の情報を、$epsilon$-corrupted $k$-mixtureで学習するアルゴリズムを提供する。 我々の主な技術的貢献は、ガウス混合系からの新しい頑健な識別可能性証明クラスターであり、これは正方形の定度証明システムによって捉えることができる。
  論文  参考訳（メタデータ） (2020-05-13T16:44:12Z)
• A computable multipartite multimode Gaussian correlation measure and the monogamy relation for continuous-variable systems [4.205209248693658]
  計算可能マルチパーティタイト多モードガウス量子相関測度を提案する。 $mathcal M(k)$は、多部量子相関測度が従うべき階層条件を満たす。
  論文  参考訳（メタデータ） (2020-01-05T14:25:09Z)

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

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