CS Paper Radar

The low-degree sample complexity of clustering Gaussian mixtures with more groups than dimensions

Alexandra Carpentier, Nicolas Verzelen

cs.CC math.STstat.ML ·submitted 2026-11-18 20:38 UTC · v1
theory

Abstract

We study the computational limits of clustering $n$ observations drawn from a mixture of $K$ isotropic Gaussian distributions in $\mathbb R^d$, when the number $K$ of groups is much larger than the dimension $d$. In this regime, distance-based and spectral procedures require a squared separation $Δ^2$ of order $\sqrt d$. In contrast, tensor-based procedures cluster at a polylogarithmic separation but need a sample size that is a large polynomial of $dK$, and the low-degree lower bounds known for random centers only show that $n$ must exceed $dK^2$. Focusing on normally distributed centers, we characterize the minimal separation for clustering with low-degree polynomials in the regime $K>d$, through a low-degree lower bound and a matching upper bound, up to subpolynomial factors. In particular, for $K=d^{p/2}$ with $p> 2$ a real number, we show that a sample size of the order of $K^3 d^{(\lceil p\rceil-p)/2}$ is required to recover the clustering with subpolynomial separation, and that it suffices when $p$ is not an integer.

Closest papers

Nearest neighbours by meaning across the whole index.

Low-degree polynomials lower bounds for clustering in small dimension

cs.LG stat.ML ·2026-10-27 ·Alexandra Carpentier, Nicolas Verzelen
theory similarity 0.85
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.

0.19

When is Uniform Sampling Optimal? Coresets for Distributional Clustering

cs.DS cs.CG ·2026-11-16 ·Junqiu Hu, Lingxiao Huang, Baoduo Xu
theory similarity 0.70
Abstract

Recent work [1] settled the optimal worst-case strong $\varepsilon$-coreset size for Euclidean $k$-means in unrestricted dimension at $\tildeΘ(\min\{k^{3/2}\varepsilon^{-2}, k\varepsilon^{-4}\})$, showing that the natural target $\tilde{O}(k\varepsilon^{-2})$ is unattainable in general. For mixtures of $k$ isotropic Gaussian components with balanced weights and bounded scale imbalance in dimension $d\ge\log k$, we show that uniform sampling yields strong $\varepsilon$-coresets of size $\tilde{O}(k\varepsilon^{-2})$, without cluster separation. This saves a factor of $\min\{\sqrt{k},\varepsilon^{-2}\}$ over the worst-case bound, up to logarithms. For population approximation by independent, equally weighted samples, the near-linear rate is optimal up to logarithmic factors over this class. More generally, for datasets generated from an isotropic Gaussian mixture $μ$ satisfying a mild cost-comparison assumption, uniform sampling yields strong $\varepsilon$-coresets of size $\tilde{O}((kζ_μ+π_{\min}^{-1})\varepsilon^{-2})$, where $π_{\min}$ is the minimum component weight and $ζ_μ$ measures scale imbalance. Our proof uses a base-shift cost decomposition: one query center per component describes the base costs, and graph spanners control the sparse corrections from points switching centers. For general mixtures under cost and tail assumptions, we obtain $\tilde{O}((kζ_μ+π_{\min}^{-1})\varepsilon^{-2}\min\{\sqrt{k},\varepsilon^{-2}\})$ samples. We also prove a matching $\tildeΩ(\min\{k^{3/2}\varepsilon^{-2},k\varepsilon^{-4}\})$ lower bound for population approximation by uniform sampling from anisotropic Gaussian mixtures, even with equal weights and a shared covariance matrix. [1] Junqiu Hu, Lingxiao Huang, Jian Li, and Baoduo Xu. Tight coreset bounds for $(k, z)$-clustering in Euclidean and doubling metrics, 2026. arXiv:2610.34373.

0.17

Dimension Reduction and Coresets for Min-Sum $k$-Clustering

cs.DS cs.CG ·2026-10-28 ·Asaf Dallal, Robert Krauthgamer
similarity 0.65
Abstract

The min-sum $k$-clustering problem asks to partition an input of $n$ points into $k$ clusters so as to minimize the total pairwise distance within clusters. It is a natural alternative to center-based objectives when the data is not well captured by a small set of representative points. We study for this problem two standard sketching methods, dimension reduction and coresets, which represent the input more compactly while preserving the min-sum cost of every $k$-partition up to $1\pm\varepsilon$ factor. Our first contribution addresses dimension reduction in Euclidean space. The Johnson-Lindenstrauss (JL) Lemma readily implies that a random linear map to target dimension $t=O(\varepsilon^{-2}\log n)$ preserves, with high probability, the min-sum cost of all $k$-partitions. We show that target dimension $t=O(\varepsilon^{-2}(ddim\cdot\log(1/\varepsilon)+\log k+\log\log n))$ suffices for Euclidean inputs of doubling dimension at most $ddim$, and moreover this bound is nearly optimal. We also show that target dimension $t=O(\varepsilon^{-2}(\log(1/\varepsilon)+\log k+\logΔ))$ suffices for Euclidean inputs of aspect ratio at most $Δ$. Our second contribution is to design the first $\varepsilon$-coreset for metric min-sum $k$-clustering. It is actually a movement-based coreset, has size $(1/\varepsilon)^{O(ddim)} k\log n$ for inputs of doubling dimension at most $ddim$, and can be constructed in randomized near-linear-time. We further use these coresets to design streaming algorithms for the problem.

0.18

Polylogarithmic Sparsity of Randomly Reweighted NPMLEs for Gaussian Mixtures

cs.LG stat.MEmath.ST ·2026-10-01 ·Hansheng Jiang
similarity 0.65
Abstract

The nonparametric maximum likelihood estimator (NPMLE) of a Gaussian location mixture maximizes the likelihood over the infinite-dimensional space of mixing distributions. The maximizing mixing distribution can be nonunique, and the classical bound on its number of atoms grows linearly with the sample size $n$. We show that a vanishingly small random perturbation of the likelihood yields exact polylogarithmic sparsity. The resulting randomly reweighted NPMLE maximizes a weighted likelihood whose independent weights, taken to be Gamma in our analysis, concentrate around one as $n$ grows. With high probability, it is unique, has $O\{(\log n/\log\log n)^d+\log n\}$ atoms in dimension $d$, nearly maximizes the ordinary likelihood, and estimates the mixture density at a Hellinger rate that is parametric up to logarithmic factors. This sparsity holds for the estimator itself, not for an approximation of it, and requires no support penalty. The proof rests on an effective-dimension principle for positive kernel mixtures: low-dimensional variation of the fitted values controls the support of every extreme point of the set of maximizers. Numerical illustrations verify that the reweighted NPMLE has Hellinger risk and support size comparable to those of the ordinary NPMLE.

0.47

Exponential Sampling Lower Bounds for Polynomial Sources

cs.CC math.CO ·2026-09-06 ·Yan Zhong
similarity 0.64
Abstract · 17 pages

A degree-$d$ polynomial source is the output of a polynomial map of degree at most $d$ over $\mathbb{F}_2$ on arbitrarily many uniform random bits. Khodabandeh and Shinkar (FOCS '26) proved that $\mathrm{Ber}(1/3)^{\otimes N}$ has statistical distance $1-o(1)$ from every constant-degree polynomial source and conjectured exponentially small overlap. Independently of Khodabandeh and Shinkar, Byramji, Kane, Morris, and Ostuni (RANDOM '26) asked for an explicit target distribution at distance $1-\exp(-N^{Ω_d(1)})$. We resolve both questions. For every fixed $d\geq1$, every degree-$d$ polynomial source has overlap at most $\exp(-c_dN)$ with $\mathrm{Ber}(1/3)^{\otimes N}$, where $c_d>0$ is independent of the seed length. For quadratics, $c_2=2^{-26}$ suffices. We amplify Khodabandeh and Shinkar's uniform separation of acceptance probabilities from non-dyadic parameters (numbers not of the form $a/2^b$ for integers $a$ and $b\geq0$). The result extends to other non-dyadic Bernoulli parameters and to coordinates that are Boolean functions of boundedly many bounded-degree polynomials. We also give a uniform deterministic hierarchy between adjacent degrees. Appending the outputs of disjoint AND gates on $d+1$ inputs to uniform seed bits yields flat degree-$(d+1)$ target distributions of entropy $k$ with overlap $\exp(-Ω_d(\min\{k,N-k\}))$ against every degree-$d$ source, for $\min\{k,N-k\}\geq2(d+1)$. This entropy dependence is optimal up to constants in the exponent among flat target distributions for fixed $d$. The construction has locality $d+1$ and uses $O(N)$ field operations to sample. At $k=\lfloor N/2\rfloor$, it handles $d\leq(1-\varepsilon)\log_2N/3$ with overlap $\exp(-N^{\varepsilon-o(1)})$ for fixed $0<\varepsilon<1$. The proof combines monotonicity of Gowers uniformity norms, pairwise independence of points in a random affine cube, and relative entropy.

0.53

$L_1$ versus $L_2$ Clustering: When Does the Choice of Norm Matter?

cs.DS ·2026-11-04 ·Nick Gravin, Jianhao Jia
similarity 0.64
Abstract

We study how well approximation guarantees for clustering under one norm translate into guarantees under another. Specifically, we compare $k$-clustering in $\mathbb{R}^d$ under the $L_1$ and $L_2$ objectives, defined as the sums of Manhattan and Euclidean distances, respectively. In the worst case, the elementary relationship between these norms yields a $\sqrt{d}$ approximation bound, which is already tight for $k=2$. We therefore investigate whether stronger guarantees are possible in a natural average-case model, where the dataset is arbitrary but the coordinate system is chosen uniformly at random among all orthonormal bases. Our main result shows that, when $d=Ω(\log k)$, with high probability over the random rotation, any $β$-approximate $L_1$ clustering, with optimally chosen centers for its clusters, is also an $O(β)$-approximation under the $L_2$ objective. We also establish an expected approximation ratio of $O(β\min\{\sqrt{d},k^{2/d}\})$, yielding a dimension-independent bound of $O(β\sqrt{\log k/\log\log k})$. We obtain analogous guarantees in the reverse direction, from $L_2$ to $L_1$. We complement these results with lower bounds of $Ω(\min\{\sqrt{d},k^{1/d}\})$ in both directions, showing that our dimension-independent guarantees have asymptotically optimal dependence on $k$ for constant $β$. Our proofs overcome the dependence of the algorithm's output on the random rotation using geometric projection arguments and small Euclidean coresets. In particular, our results provide guarantees for existing clustering algorithms without requiring their redesign.

0.13

Hermite Brings a Laptop: Analyzing Frieze-Jerrum Rounding Yields Improved Approximations for Clustering Problems

cs.DS ·2026-09-28 ·David García-Soriano, Atsushi Miyauchi
similarity 0.61
Abstract

The Frieze-Jerrum rounding is a standard tool for rounding SDP relaxations of graph partitioning and clustering problems, assigning nodes to at most $k$ clusters using $k$ independent Gaussian vectors. Its analysis hinges on the collision probability $P_k(ρ)$ that two nodes whose SDP vectors have inner product $ρ$ are assigned to the same cluster. No tractable closed form for $P_k$ is known for $k\geq 4$, making it difficult to certify approximation guarantees and hindering the systematic search for better algorithms. We develop a Hermite-coefficient certification framework to derive accurate and tractable bounds on $P_k$. Using the Hermite expansion of Gaussian noise stability, we express $P_k$ as a power series with nonnegative coefficients, reduce these coefficients to one-dimensional Gaussian integrals, and certify finitely many of them, yielding rigorous bounds on $P_k$ over the entire correlation range. Our framework yields strengthened polynomial-time approximations for several clustering problems. For MaxAgree Correlation Clustering, we derive a $0.7818$-approximation, the first improvement in two decades over the $0.7666$ ratio of Swamy (2004). We also improve the best known ratios for the variant with at most $K$ clusters, MaxAgree$[K]$ (e.g., from $0.77$ to $0.8151$ for $K=3$). For Max $K$-Cut we resolve, via a structural property of the Hermite expansion, a conjecture of de Klerk et al. (2004) characterizing the Frieze--Jerrum approximation ratio for every $K\ge3$; we show that this ratio is tight, and determine it to within $10^{-6}$ accuracy for $K\le16$. Finally, we reduce the additive approximation error for modularity maximization from $0.42084$ (Kawase et al., 2021) to $0.3790$. On the hardness side, we show that approximating Maxagree within $0.802+ε$ is Unique Games-hard via a construction in Gaussian space analyzed by Borell's inequality.

0.39

Low-Dimensional Embeddings for Gaussian Kernels on Manifolds

cs.CG cs.LG ·2026-09-14 ·Soumik Dutta, Kunal Dutta
theory similarity 0.61
Abstract · 57 pages, 3 figures

The Gaussian kernel is a widely used similarity measure underlying kernel methods such as kernel PCA and spectral clustering, but computing Gaussian kernel distances for many pairs of points can be expensive. Using Random Fourier Features (RFF), Chen and Phillips [ALT 2017] showed that for points in a $d$-dimensional Euclidean ball in ${\mathbb R}^N$, $t=Ω((d/\varepsilon^2)\log(dR/\varepsilon))$ features suffice to preserve all pairwise Gaussian kernel distances within a $(1\pm\varepsilon)$ factor with high probability. We establish a uniform relative-error embedding theorem for the more general setting of an arbitrary positive-reach submanifold $\mathcal M\subset{\mathbb R}^N$ of intrinsic dimension $d$. We show that $t=O((d/\varepsilon^2)\log(\operatorname{vol}(\mathcal M)^2N^{2d}/(\operatorname{vol}(B_1^d(0))^2\operatorname{rch}(\mathcal M)^{2d}\varepsilon^{2d+1}δ)))$, or approximately $O((d^2/\varepsilon^2)(\log N+\log(1/(\varepsilonδ))))$, RFFs suffice, with probability $1-δ$, to preserve the Gaussian kernel distance between every pair of manifold points up to relative error $\varepsilon$. Thus the bound depends only logarithmically on the ambient dimension and on manifold parameters such as volume and reach, while retaining the $1/\varepsilon^2$ Euclidean rate. We also prove a topological consequence: under the same RFF embedding, persistent homology is preserved in the sense that weighted Cech and Rips filtrations built from Gaussian kernel power distance are $(1\pm\varepsilon_\star)$-interleaved, where $\varepsilon_\star$ accounts for both distance distortion and kernel-weight approximation.

0.22