A low-degree polynomial lower bound is established showing that clustering is hard as long as the separation $\Delta$ satisfies $\Delta^2\ll(K^2d^{3/2}/n)^{1/(2m+2)}\wedge\sqrt d$, up to polylogarithmic factors.
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 $\Delta$ satisfies $\Delta^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.
For many probability measures on $\mathbb{R}^n$, and for $k$ sufficiently smaller than $n$, most $k$-dimensional coordinate marginals are close to product measures. We prove this in two regimes, which notably involve no exchangeability assumptions as in prior theorems of de Finetti type. First, for log-concave measures...
We study the maximization of a nonnegative $k$-submodular function, not assumed monotone, in which each of $n$ elements receives one of $k\ge2$ labels or stays unselected and the selected elements must satisfy a constraint. For a compact convex down-closed region $P\subseteq[0,1]^n$ of fractional selection vectors, the...
For sequences of $n$ nonnegative integer vectors in $\mathbb Z^k$ with distinct subset sums, we prove, for fixed $k$, the uniform lower bound $M\ge (C_k-o(1))2^{n/k}/\sqrt n$ for the largest coordinate, where \[ C_k=\sqrt{\frac{2k}{\pi}}\, \frac{(k+1)^{(k-1)/(2k)}}{\sqrt{\lfloor (k+1)^2/4\rfloor}}. \] The proof compare...
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 rela...
We study the random geometric graph formed by connecting $n$ independent uniform points on $\mathbb S^{d-1}$ whenever their inner product exceeds a threshold chosen to give edge density $p$. We establish the conjectured dimensionality threshold for indistinguishability from the Erd\"{o}s-R\'enyi graph $G(n,p)$ througho...
We prove sharp spectral-norm bounds and construct a mean-fitting regularization procedure for sparse random tensors of fixed order $k$. For an $n\times\cdots\times n$ tensor with independentBernoulli$(p)$ entries, the centered norm is $O(\sqrt{np})$ with polynomially high probability whenever $np\ge c\log n$. This remo...
Zhi-Xin Zhou, Yizhe Zhu· 2 citations· ⚡1
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.