<figure><img src="image_1.png" /></figure>

HAL
open science

# Computational lower bounds in latent models: clustering, sparse-clustering, biclustering

Bertrand Even, Christophe Giraud, Nicolas Verzelen

<figure><img src="image_2.png" /></figure>

## To cite this version:

Bertrand Even, Christophe Giraud, Nicolas Verzelen. Computational lower bounds in latent models: clustering, sparse-clustering, biclustering. 2025. hal-05116284

HAL Id: hal-05116284

https://hal.science/hal-05116284v1

Preprint submitted on 17 Jun 2025

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_3.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
COMPUTATIONAL LOWER BOUNDS IN LATENT MODELS: CLUSTERING,
SPARSE-CLUSTERING, BICLUSTERING

BY BERTRAND EVEN<fnref n="1" />,ᵃ, CHRISTOPHE GIRAUD<fnref n="1" />,ᵇ AND NICOLAS VERZELEN<fnref n="2" />,ᶜ

In many high-dimensional problems, like sparse-PCA, planted clique, or clustering, the best known algorithms with polynomial time complexity fail to reach the statistical performance provably achievable by algorithms free of computational constraints. This observation has given rise to the conjecture of the existence, for some problems, of gaps – so called statistical-computational gaps – between the best possible statistical performance achievable without computational constraints, and the best performance achievable with poly-time algorithms. A powerful approach to assess the best performance achievable in poly-time is to investigate the best performance achievable by polynomials with low-degree. We build on the seminal paper of [66] and propose a new scheme to derive lower bounds on the performance of low-degree polynomials in some latent space models. By better leveraging the latent structures, we obtain new and sharper results, with simplified proofs. We then instantiate our scheme to provide computational lower bounds for the problems of clustering, sparse clustering, and biclustering. We also prove matching upper-bounds and some additional statistical results, in order to provide a comprehensive description of the statistical-computational gaps occurring in these three problems.

# 1. Introduction.
In high-dimensional statistics, the primary goal is to derive computation-
ally efficient estimation procedures, achieving the best possible statistical performance. Yet,
in many problems, such as sparse PCA, planted clique or clustering, the best known al-
gorithms with polynomial-time complexity are unable to match the performances provably
achievable by the best estimators (without computational constraints). This observation has
lead to several conjectures on the existence of gaps (called statistical-computational gaps) be-
tween the optimal statistical performance, i.e. the best performance achievable without com-
putational constraints, and the best performance achievable by polynomial time algorithms.
In particular, to assess the quality of a computationally efficient algorithm for a given task, the
theoretical performance should not be compared to the optimal statistical performance (with-
out computational constraints), but to the performance of the best poly-time algorithm. This
raises the problem of establishing lower-bounds on the performance of the best poly-time
algorithms for a wide range of problems.

Since high-dimensional statistics deal with random instances, the classical notions of worst-case hardness, such as P, NP, etc are not suitable for the high-dimensional framework. Instead, lower bounds are obtained for some specific models of computations, such as SoS [38, 10],

<footnote n="1">¹Laboratoire de Mathématiques d'Orsay, Université Paris-Saclay, a@bertrand.even@universite-paris-saclay.fr;</footnote>

<footnote>ᵇchristophe.giraud@universite-paris-saclay.fr</footnote>

<footnote n="2">²MISTEA, INRAE, Institut Agro, Univ. Montpellier, cNicolas.Verzelen@inrae.fr</footnote>

<footnote>MSC2020 subject classifications: Primary 62H30, 68Q17.</footnote>

<footnote>Keywords and phrases: Computational lower bound, Statistical–computational tradeoffs, Low-degree polynomials, Clustering, Gaussian mixtures, Sparse clustering, Biclustering.</footnote>
overlap gap property [32], statistical query [41, 13], and low-degree polynomials [37, 44, 66],
possibly combined with reductions between different statistical problems [12, 11, 14].

Low-degree polynomial lower bounds (LD bounds) have recently attracted a lot of attention
due to their ability to provide state-of-the-art lower bounds for a wide class of detection prob-
lems, including community detection [39], spikes tensor models [39, 44], sparse PCA [25]
among others. We refer to [71] for a recent survey. The low-degree polynomial framework is
a computational model, where we only consider estimators, or test statistics, within the class
of multivariate polynomials of degree at most *D* of the observations. The premise of the LD
literature is that for a large class of problems, the polynomials of degree *D* = *O*(log *n*) are as
powerful as any polynomial-time algorithm. Hence, proving failure of degree *O*(log *n*) poly-
nomials for a given task is an indication [44] that no poly-time algorithm can solve this task.
Interestingly, it has been demonstrated that this framework is closely related to other compu-
tational frameworks including statistical queries [13], free-energy landscapes from statistical
physics [7] or approximate message passing [57]. In addition to predicting computational
barriers for algorithms computable in polynomial time, LD polynomials may be used to pre-
dict the amount of time needed to resolve a problem in the hard regime. In sparse PCA, [25]
exhibits a phenomenon where, when the signal-to-noise ratio decreases, the complexity in-
terpolates between being of polynomial time in the easy regime and being exponential at the
informational threshold. In general, [37] states in its low-degree conjecture that polynomials
of degree *D* are a proxy for algorithm of time complexity roughly *n*^*D*.

The LD framework has been initially developed for hypothesis testing (detection problems), where the goal is to detect the existence of a possible planted signal in the data. The framework has then been extended to the estimation problem in the seminal paper of Schramm and Wein [66]. In the estimation framework, the goal is to lower-bound the risk of the best polynomial of degree at most *D*. A key contribution of [66] is to relate the derivation of LD bounds to the upper-bounding of some multivariate cumulants. The theory developed in [66] provides a versatile framework to derive LD bounds in estimation and has been applied among others to submatrix estimation [66], stochastic block models and graphons [52], dense cycles recovery [54], coloring problems [43]. However, it suffers from two limitations:

1. It can lead to quite complex analyses for some involved problems, and this complexity can limit the range of the results that can be obtained, as e.g. in [28] for Gaussian mixture models or in [52] for biclustering. Those examples are discussed precisely later on.

2. It provides non-sharp thresholds, with spurious poly-log factors.

The second limitation has been recently tackled by Sohn and Wein [68], which provides more
powerful technics to derive sharp thresholds, but at the price of an even higher technicality
and complexity, limiting the applicability to more involved problems.

1.1. *Our contributions.* Our main technical contribution is to propose some new schemes for upper-bounding the cumulants in some latent variable models. The heart of the improvement is to better handle conditional independences in latent variable models by conditioning, leading to stronger and new results, with simpler proofs. This scheme is then instantiated in the three following emblematic problems: clustering Gaussian mixtures, sparse clustering and biclustering. Whereas the computational-statistical gaps were previously known in some restrictive, we provide an almost full picture in this work. To complement the LD bounds, we also provide upper-bounds on the statistical and computational rates for these problems. Let us describe our main contributions into more details.
**Bounding multivariate cumulants in a model with latent variables.** We consider the following model of data generation. We observe a $n \times p$ matrix $Y \in \mathbb{R}^{n \times p}$, which can be decomposed as $Y = X + E$, where $E$ is a noise matrix with i.i.d. Gaussian entries, and $X$ is a signal matrix, independent of $E$, structured by a latent variable $Z \in \mathcal{Z}$

$$ (1) \qquad X_{ij} = \delta_{ij}(Z)\nu_{\theta_{ij}(Z)}, \quad \text{for } (i,j) \in [n] \times [p], $$

with

* $\nu_{k\ell} \in \mathbb{R}$, for $(k, \ell) \in [K] \times [L]$, possibly randomly generated;

* $\delta_{ij}: \mathcal{Z} \to \{0, 1, -1\}$ and $\theta_{ij}: \mathcal{Z} \to [K] \times [L]$, for any $(i, j) \in [n] \times [p]$.

In the analysis of [66], the key step for proving LD bounds is to upper-bound multivariate cumulants of the form $\kappa_{h(Z),\alpha} = \text{Cum}(h(Z), \{X_{ij}: (i,j) \in \alpha\})$, where $h: \mathcal{Z} \to \mathbb{R}$ is a measurable function, and $\{X_{ij}: (i,j) \in \alpha\}$ is a multiset, where the variable $X_{ij}$ is repeated $\alpha_{ij}$-times. Our first contribution is to provide some simple bounds, and simple recursions for bounding such cumulants $\kappa_{h(Z),\alpha}$. These bounds and recursions are obtained by merely applying a conditioning on the latent variable $Z$, and observing that many simplifications occur. While technically very simple, this first step is the basis for deriving new lower-bounds in different instances of the latent model (1).

**Clustering Gaussian mixtures.** The classical Gaussian mixture model is an instantiation of the latent model (1). For some unknown vectors $\mu_1, \dots, \mu_K \in \mathbb{R}^p$, some unknown $\sigma > 0$, and an unknown partition $G^* = \{G_1^*, \dots, G_K^*\}$ of $[n]$, the observations $Y_{ij}$ are sampled independently with distribution

$$ (2) \qquad Y_{ij} \sim \mathcal{N}(\mu_{kj}, \sigma^2), \quad \text{for } i \in G_k^* \text{ and } j \in [p]. $$

For simplicity, we focus on the case where the partition is balanced, i.e. where all clusters $G_k^*$ have similar cardinality. Denoting by

$$ (3) \qquad \Delta^2 = \min_{k \neq l} \frac{\|\mu_k - \mu_l\|^2}{2\sigma^2}, $$

the minimal (scaled) separation between clusters, we prove in Theorem 3.1 that, for $p \ge \log^5(n)$, clustering better than a random guessing with $\log(n)$-degree polynomials can be impossible when

$$ (4) \qquad \Delta^2 < (c \log K) \vee \left( \frac{\sqrt{p}}{(\log n)^9} \wedge \sqrt{\frac{K^2 p}{n}} \right), $$

where $c$ is a positive numerical constant. This result extends the LD bound of [28], only valid for the high-dimensional regime $p \ge n$, to the much more challenging moderately high-dimensional regime $\log^5(n) \le p \le n$. The LD bound is also improved, removing spurious poly-log($n$) factors present in the lower-bound of [28]. In particular, the bound recovers the exact BBP threshold $\sqrt{K^2 p/n}$, that was conjectured in [48] with tools from statistical physics. Comparing (4) to the statistical threshold

$$ (5) \qquad \Delta^2 \gtrsim \log(K) + \sqrt{\frac{pK}{n} \log(K)}, $$

derived in [28], above which partial clustering is achievable by minimizing exactly the Kmeans criterion, we observe the existence of a statistical-computational gap when

$$ p > \frac{n \log(K)}{K^2} \quad \text{and} \quad K \lesssim n^{1-\alpha(1)}. $$
We also provide some new upper-bounds proving that clustering in polynomial time is possible when $\Delta^2$ is larger (up to log factors) than (4), in a wide range of regimes of $K, n, p$.

**Sparse Clustering.** Sparse clustering is an instance of the clustering model above, where the means $\mu_k$ are sparse. Let $s \in [p]$ and an unknown subset $J^* \subseteq [p]$ with $|J^*| \le s$. For some unknown vectors $\mu_1, \dots, \mu_K$ which are all supported on $J^*$, some unknown $\sigma > 0$, and some unknown partition $G^* = \{G_1^*, \dots, G_K^*\}$ of $[n]$, the observations $Y_{ij}$ are sampled independently with distribution

$$Y_{ij} \sim \mathcal{N}(\mu_{kj}, \sigma^2), \quad \text{for } i \in G_k^* \text{ and } j \in [p].$$

In Section 4, we prove that clustering better than a random guessing with $\log(n)$-degree polynomials can be impossible when

$$(6) \quad \Delta^2 \lesssim_{\log 1 + \min\left(\sqrt{s}, \sqrt{\frac{sK^2}{n}}\right) + \sqrt{\frac{s^2}{n}}} \text{ and } \Delta^2 \lesssim_{\log 1 + \min\left(\sqrt{p}, \sqrt{\frac{pK^2}{n}}\right)}.$$

This result generalizes the computational lower bound proved in Löffler et al. [50] for the specific case of $K = 2$ groups. Our lower bound (6) is valid for any $K$ and $s$ and, thereby, shed lights on the joint dependence of computationally efficient rates on $K$ and $s$. The second condition in (6) corresponds to the Condition (4) for clustering in poly-time in dimension $p$. The third term in the right-hand side of the first condition can be understood as the signal needed to ensure recovery of the $s$ columns supporting the $\mu_k$, while the two first terms corresponds to the rate for poly-time clustering in dimension $s$. Under the simplifying assumption that the signal is well spread over the $s$ columns, we prove that clustering above the level (6) can indeed be performed in poly-time by (i) selecting the $s$ columns with the largest $\ell^2$-norm, (ii) removing all the other columns, (iii) applying an optimal poly-time clustering algorithm on the remaining matrix. To delineate the statistical-computational gap, we prove in Proposition 4.6, that, by applying an exhaustive search over all the partitions and all the columns, perfect clustering can be achieved in this context as soon as

$$(7) \quad \Delta^2 \gtrsim_{\log 1 + \sqrt{\frac{sK}{n}} + \sqrt{\frac{sK}{n}}} \text{ or } \Delta^2 \gtrsim_{\log 1 + \sqrt{\frac{pK}{n}}}.$$

The first minimal separation in (7) gathers the statistical threshold (25) in dimension $p = s$, with a separation $\Delta^2 \ge \sqrt{sK}/n$ corresponding to the separation required for recovering the active columns set $J^*$ once the clustering is known. We highlight the following interesting statistical-computational phenomenon in sparse-clustering, with a well spread signal. The additional separation $\Delta^2 \gtrsim \sqrt{s^2}/n$ required in poly-time corresponds to the separation needed for recovering the active columns before clustering, while the statistical additional separation $\Delta^2 \lesssim \sqrt{sK}/n$ corresponds to the separation needed for recovering the active columns after clustering. This feature unveils a better ability of non poly-time algorithm to fully exploit the joint sparse-and-clustered structure. Comparing (6) and (7), we observe the existence of a statistical-computational gap, which, depending on the regimes, can be as large as factor $\sqrt{n/K}$ or a factor $\sqrt{K}$.

**Biclustering.** As a last example, we investigate the biclustering problem where both rows and columns can be clustered. For some unknown matrix $\mu \in \mathbb{R}^{K \times L}$, some unknown $\sigma > 0$, and unknown partitions $G^* = \{G_1^*, \dots, G_K^*\}$ of $[n]$ and $H^* = \{H_1^*, \dots, H_L^*\}$ of $[p]$, the $Y_{ij}$'s are sampled independently with distribution

$$Y_{ij} \sim \mathcal{N}(\mu_{kl}, \sigma^2), \quad \text{for } (i, j) \in G_k^* \times H_l^*.$$
We observe that when all the clusters in $G^*$ (respectively $H^*$) have the same size $n/K$ (resp. $p/L$), we have for $i \in G_k^*$ and $i' \in G_{k'}^*$

$$ \|X_i - X_{i'}\|^2 = \sum_{l=1}^{L} |H_l^*|(\mu_{kl} - \mu_{k'l})^2 \asymp \frac{p}{L} \|\mu_k - \mu_{k'}\|^2 . $$

Hence, we introduce

$$ \Delta_r^2 = \frac{p}{L} \min_{k \neq k' \in [K]} \frac{\|\mu_k - \mu_{k'}\|^2}{2\sigma^2} \quad \text{and} \quad \Delta_c^2 = \frac{n}{K} \min_{l \neq l' \in [L]} \frac{\|\mu_l - \mu_{l'}\|^2}{2\sigma^2}, $$

which represent the minimum row and column separations. Given the symmetry of the problem, we can focus on the problem of finding the minimum separations for row clustering, i.e. for recovering partially $G^*$. We investigate if and how the column structure can help for recovering the row clusters. Our results in Section 5 show the following dichotomy.

1. Either $\Delta_c^2 \le \log 1 + \min(\sqrt{n}, \sqrt{nK^2/p})$, in which case row-clustering can be impossible in poly-time below the threshold $\Delta_r^2 \le \log 1 + \min(\sqrt{p}, \sqrt{pK^2/n})$ corresponding to simple clustering;

2. Or $\Delta_c^2 \ge \log 1 + \min(\sqrt{n}, \sqrt{nK^2/p})$, in which case row-clustering is possible only above the threshold $\Delta_r^2 \stackrel{\log}{=} 1 + \min(\sqrt{L}, \sqrt{LK^2/n})$ corresponding to clustering in dimension $L$.

This result exhibits the following interesting phenomenon. We observe that the threshold $\Delta_c \ge \log 1 + \min(\sqrt{n}, \sqrt{nK^2/p})$ corresponds to the minimal level for clustering the $n$-dimensional columns in poly-time. When it is possible to cluster these columns in poly-time (case 2), then an optimal poly-time algorithm amounts to (i) cluster the columns, (ii) average the columns within a same group, reducing the number of columns to $L$, and (iii) apply a poly-time row clustering on the new $n \times L$ matrix. Conversely, when it is not possible to cluster the columns in poly-time (case 1), then the column structure is useless, and the minimal level for clustering the rows in poly-time corresponds to the level for simple clustering. Hence, for poly-time algorithms, the column structure is helpful for row clustering, only when the columns can be clustered in poly-time.

This is in contrast with computationally unconstrained algorithms, which can better leverage the column structure: we prove that a variant of exact Kmeans for biclustering only requires

$$ \{ \Delta_r^2 \ge \log 1 + \sqrt{\frac{KL}{n}} \quad \text{and} \quad \Delta_c^2 \ge \log 1 + \sqrt{\frac{KL}{p}} \}, \quad \underline{\text{or}} \quad \{ \Delta_r^2 \ge \log 1 + \sqrt{\frac{Kp}{n}} \}, $$

for recovering $G^*$. We observe that (i) the column separation $\Delta_c^2 \ge \log 1 + \sqrt{KL/p}$ corresponds to the minimal separation required to recover $H^*$ when $G^*$ is known, and (ii) when this condition is met we can recover $G^*$ with the separation $\Delta_r^2 \ge \log 1 + \sqrt{KL/n}$ which corresponds to the minimal separation required to recover $G^*$ when $H^*$ is known. Hence, only a $K$-dimensional column separation condition is needed to benefit from the $L$-dimensional row separation condition $\Delta_r^2 \ge \log 1 + \sqrt{KL/n}$ for successful clustering. This feature is in contrast with poly-time algorithms, where the $n$-dimensional column separation $\Delta_c^2 \ge \log 1 + \min(\sqrt{n}, \sqrt{L^2n/p})$ is required for benefiting from the $L$-dimensional row separation condition $\Delta_r^2 \ge \log 1 + \min(\sqrt{L}, \sqrt{K^2L/n})$. Our results then unveil a much better
ability of non poly-time algorithms to leverage the biclustering structure, compared to poly-time algorithms.

## 1.2. Related Literature on clustering problems.

**Gaussian mixture clustering.** Gaussian mixtures are arguably the most iconic distribution model for clustering. The corresponding problem has lead to many developments both in statistics and machine learning [20, 69, 48, 51, 24, 64, 35, 30, 17, 45, 67, 65, 49, 21, 28]. In the isotropic Gaussian mixture model, the minimax condition for partial recovery in any dimension was characterized in [28], although it was already known in the low-dimensional case, see e.g. [64, 67].

In an asymptotic regime where $K$ is fixed, $n, p \to \infty$ with $p/n \to \alpha \ge \frac{1}{K^2}$, it was conjectured by [48] that the problem is indeed hard under the BBP transition $\Delta^2 \asymp \sqrt{pK^2/n}$. To do so, they study the fixed points of the sate evolution equation of Approximate Message Passing. In the same asymptotic regime, [9] proves that spectral detection is possible if and only if the separation is above the BBP transition $\sqrt{pK^2/n}$.

In the high-dimensional regime where $p \ge n$, [28] partially confirmed this conjecture by establishing a LD lower bound that agrees (up to polylog) with the prediction of [48] in the regime where $n \le K^2$, and by unveiling another rate in the many group regime ($n \ge K^2$). These LD lower bounds are matched by a combination of a SDP [35] and hierarchical-clustering techniques. In contrast, in the low-dimensional regime $n \ge \text{poly}(p, K)$, there is no significant statistical-computational gap. Indeed, using iterative projections of high-order tensors, Liu and Li [49] have proved that it is possible to partially recover the clusters when $\Delta^2 \gtrsim \log(K)^{1+\varepsilon}$, with $\varepsilon$ an arbitrary small positive constant, thereby almost matching the informational bound. The moderately high-dimensional regime $p < n < \text{poly}(p, K)$, for some (non-explicit) polynomial $\text{poly}(p, K)$ from [49], is still to be understood. Although there are numerous works on spectral procedures as well as Lloyd's algorithm [59, 51], SDP [30, 35], or hierarchical-clustering procedures [69] in this moderately high-dimensional regime, it remains largely unknown whether those are optimal among polynomial-time algorithms.

We underline that we focus in this work on the isotropic case. In the non-isotropic case, there is an additional statistical-computational gap which does not come from the high-dimensionality but from the unknown covariance structure. In particular, [23] and [22] establish some lower-bounds on the running time of any Statistical-Query algorithms, proving a statistical-computational gap between optimal procedures and SQ algorithms.

**Sparse clustering.** Motivated by practical considerations, Raftery and Dean [63] have introduced the sparse clustering model, where the clusters only differ on a small number of features. This lead to the development of numerous procedures that aim to build upon this sparsity to improve the clustering –see e.g. [56, 55, 72, 58] and references therein. Notably, [72] uses a penalization by the $l_1$-norm in order to use weighted versions of the Kmeans objective. Another class of procedures amounts to alternate between feature selection and clustering (e.g. [58]). In the specific case where $K = 2$, [4] have characterized the minimax optimal rate for clustering. They also provided a two-step computationally-efficient procedure, but with significantly worse clustering rate. Under some technical assumptions, [40] introduced a more general two-step procedure that (i) selects active columns, (ii) uses a vanilla clustering procedure for $K \ge 2$, and they conjectured the existence of a statistical-computational gap. The corresponding sparse clustering detection problem was studied in [70] from a minimax
perspective. In the regime where the sparsity $s$ is small, they drawn some informal connection with the sparse PCA problem, for which a statistical-computational gap has been exhibited [11]. Let us remark that some procedures such as CHIME [16] do not seem to exhibit this statistical-computational gap, but they rely on a good initialization which is only known to be achieved by non-efficient procedures. This connection to sparse PCA as well as the interest in sparse clustering has spurred the need for computational lower bounds [29, 12, 50]. All of these works are restricted to the case $K = 2$, and focus on the sparsity effect. Brennan and Bresler [12] have reduced sparse-clustering to a variant of planted clique, whereas Fan et al. [29] have established a matching statistical query (SQ) lower-bound. Closer to our perspective, [50] have provided a LD lower bound for the corresponding detection problem. All these lower bounds suggest that it is impossible to recover the $K = 2$ groups in polynomial-time when $\Delta^2 \le \log s/\sqrt{n}$ in a high-dimensional regime where $s \le \sqrt{pn}$. In some way, we extend this theory to the case of a general number $K \ge 2$ of groups, unraveling the impact of $K$ in the statistical-computational gap.

**Biclustering.** The biclustering problem arises when both the rows and the columns of a matrix $Y$ can be clustered [36]. A simpler version of this problem is to detect or estimate a single submatrix hidden in some noise. The latter is one of the earliest problem whose statistical-computational gap has been established [6, 42, 53, 15, 66, 68]. Closer to biclustering, [19] considers the case where there are multiple planted submatrices by providing in particular LD lower bounds for the detection problem. For the general biclustering problem with $(K, L)$ groups, the minimax estimation rate for estimating the signal matrix $X = \mathbb{E}[Y]$ in Frobenius norm has been characterized in [33]. On the computational side, Luo and Gao [52] have built on the general methodology of [66] to provide a LD lower bound for this problem; they also studied spectral algorithms to match this bound. However, their LD lower bound turns out to be sharp only in the almost square regime $n \asymp p$ and when $\min(K, L) \le \sqrt{\max(n, p)}$. In particular, handling rectangular settings where $n$ and $p$ differ significantly, requires a more careful control of the cumulants, as done in this manuscript. Another important difference between our work and that of [52] is that we focus on the problem of recovering the clustering of rows instead of reconstructing the mean matrix. In asymmetric regimes, where either $n$ is different from $p$, or $K$ different from $L$, the clustering problem turns out to behave quite differently.

Extensions of stochastic block models (SBM) to biclustering problems have been considered e.g. in [31, 60], but their instance of the model is quite different from ours, as it is assumed that the number of groups $K$ is equal to $L$, that each group of rows is associated to a group of columns, and that the connection probability is higher between the corresponding nodes. In this sense, the model is closer to the literature on SBM.

### 1.3. Organisation and notation.
In Section 2, we introduce the low-degree estimation framework as well as the general latent model. Then, we describe the conditioning techniques and showcase a simple application to Gaussian mixture models. The reader less interested in the techniques for proving LD lower bounds may skip this section. Then, we use these techniques to establish tight LD lower bounds for our three main problems: Gaussian mixture clustering (Section 3), sparse clustering (Section 4), and biclustering (Section 5). A long the way, we provide polynomial-time upper bounds and informational upper bounds, when unknown, in order to precisely quantify the statistical-computational gaps. Section 6 provides a discussion of possible extensions and open problems. More technical discussions as well as the proofs are postponed to the appendix.
**Notation.** Given a vector $v$, we write $\|v\|$ for its Euclidean norm. For a matrix $A$, we denote $\|A\|_F$ for its Frobenius norm, and $\|A\|_{op}$ for its operator norm. For two function $u$ and $v$, we write $u \lesssim v$ if there exists a numerical constant such that $u \leq cv$. We write $u \asymp v$ if $u \lesssim v$ and $v \lesssim u$. For two functions that may depend on $n$ and $p$, we write $u \leq_{\log} v$, if there exist numerical constants $c$ and $c'$ such that $u \leq c \log^c(np)v$. If $u, v$ also depend on some other parameter $\gamma$, we write $u \leq_{\log, \gamma} v$, if there exist a constant $c_\gamma$ depending only on $\gamma$ and a numerical constant $c'$ such that $u \leq c_\gamma \log^c(np)v$. For a subset $S$, we write $|S|$ for its cardinality. Given a random variable $x$ and an event $B$, we write $1\{B\}$ for the indicator function of $B$ and $E[x; B]$ for $E[x1_B]$.

We identify a matrix $\alpha \in \mathbb{N}^{n \times p}$ with the multiset of $[n] \times [p]$ containing $\alpha_{ij}$ copies of $(i, j)$. For $i \in [n]$, we write $\alpha_i$: the $i$-th row of $\alpha$. Similarly, for $j \in [p]$, we write $\alpha_{:j}$ the $j$-th column of $\alpha$. We denote $\text{supp}(\alpha) = \{i \in [n], \alpha_i \neq 0\}$ and $\text{col}(\alpha) = \{j \in [p], \alpha_{:j} \neq 0\}$. Then, we denote $\#\alpha = |\text{supp}(\alpha)|$ and $r_\alpha = |\text{col}(\alpha)|$. Finally, we shall write $|\alpha|$ the $l_1$-norm of $\alpha$, which is the cardinality of $\alpha$ viewed as a multiset. Finally, $\alpha!$ stands for $\prod_{ij} \alpha_{ij}$! and, for any real valued matrix $Q$, we define $Q^\alpha = \prod_{ij} Q_{ij}^{\alpha_{ij}}$.

For $W_1, \dots, W_l$ random variables on the same space, we write $\text{Cum}(W_1, \dots, W_l)$ for their joint cumulant. For $Z$, another random variable on the same space, we write $\text{Cum}(W_1, \dots, W_l|Z)$ the joint cumulant of the random variables taken conditionally on $Z$.

## 2. Proof technique for LD bounds in the latent model.

### 2.1. Low-degree framework.
Let us consider the latent model introduced earlier, where we observe a matrix $Y \in \mathbb{R}^{n \times p}$, which can be decomposed as the sum $Y = X + E$ of a noise matrix $E$ with i.i.d. Gaussian errors, and a signal matrix $X$ structured according to a latent variable $Z \in \mathcal{Z}$ as in (1)

$$X_{ij} = \delta_{ij}(Z)\nu_{\theta_{ij}(Z)}, \quad \text{for } (i,j) \in [n] \times [p],$$

with $\delta_{ij}: Z \to \{0, 1, -1\}$ and $\theta_{ij}: Z \to [K] \times [L]$, for any $(i, j) \in [n] \times [p]$. For example, in the case of clustering, $Z$ is the vector of independent labels $Z = [k_1^*, \dots, k_n^*] \in [K]^n$, $\delta_{ij}(Z) = 1$ and $\theta_{ij}(Z) = (k_i^*, j)$. For proving LD bounds, we make the following additional assumptions.

**ASSUMPTION 1.** [Gaussian means] The $\nu_{kl}$'s are independent of $Z$, and i.i.d. with $N(0, \lambda^2)$ distribution for some $\lambda > 0$.

This assumption is very convenient for our analysis, as it leads to many simplifications. We mention yet, that a similar analysis can be done for other data distributions, like the Bernoulli distribution for binary $Y_{ij}$; see Appendix A.4 for a discussion.

We consider the problem where we want to estimate some scalar function of $Z$, that we write $x(Z)$, or simply $x$, with polynomials of the $Y_{ij}$ of degree at most $D$. For example, in the case of clustering, where $Z = [k_1^*, \dots, k_n^*] \in [K]^n$, we may want to estimate $x(Z) = 1_{k_1^* = k_2^*}$. Our goal is to lower bound the best mean-square error achieved by a polynomial of degree at most $D$

$$ (8) \qquad MMSE_{\leq D} := \inf_{f \in \mathbb{R}_D[Y]} \mathbb{E} \left[ (f(Y) - x(Z))^2 \right] . $$

As noticed by [66], the $MMSE_{\leq D}$ can be decomposed as

$$ (9) \qquad MMSE_{\leq D} = \mathbb{E}[x(Z)^2] - \text{corr}_{\leq D}^2, $$
where $corr_{\leq D}$ is the $L^2$-norm of the $L^2$-projection of $x(Z)$ on the linear span of polynomials $f(Y)$ with degree at most $D$

$$ (10) \qquad corr_{\leq D} := \sup_{\substack{f \in \mathbb{R}_D[Y] \\ \mathbb{E}[f^2(Y)]=1}} \mathbb{E}(f(Y)x(Z)) = \sup_{\substack{f \in \mathbb{R}_D[Y] \\ \mathbb{E}[f^2(Y)] \neq 0}} \frac{\mathbb{E}[f(Y)x(Z)]}{\sqrt{\mathbb{E}[f^2(Y)]}} $$

Hence, in order to lower-bound $MMSE_{\leq D}$, it is sufficient to prove an upper-bound on $corr_{\leq D}$. Our latent model is a particular instance of the Additive Gaussian Noise Model considered in [66]. Therefore, we can apply Theorem 2.2 from [66] that upper-bounds the low-degree correlation $corr_{\leq D}$ by a sum of squared cumulants – see Appendix B for definitions and properties of cumulants. Let us recall their result.

**PROPOSITION 2.1.** [Theorem 2.2. in [66]] The degree-$D$ maximum correlation satisfies the upper-bound

$$ (11) \qquad corr_{\leq D}^2 \leq \sum_{\alpha \in \mathbb{N}^{n \times p}, |\alpha| \leq D} \frac{\kappa_{x,\alpha}^2}{\alpha!}, $$

with $\alpha! = \prod_{ij \in [n] \times [p]} \alpha_{ij}$, and where, for $\alpha \in \mathbb{N}^{n \times p}$, $\kappa_{x,\alpha}$ is defined as the cumulant

$$ (12) \qquad \kappa_{x,\alpha} := \text{Cum}(x, X_{\alpha}) = \text{Cum}\left(x(Z), \{X_{ij}\}_{(i,j) \in \alpha}\right), $$

where $X_{\alpha} = \{X_{ij}\}_{(i,j) \in \alpha}$ is the multiset containing $\alpha_{ij}$ copies of $X_{ij}$ for $(i,j) \in [n] \times [p]$.

A key feature noticed by [66], is that the sum in (11) is sparse, due to the nullity of the cumulants of independent variables [61].

**LEMMA 2.2.** Let $W_1, \dots, W_K$ be random variables on the same space $W$. Suppose that there exist disjoint sets $K_1$ and $K_2$, non-empty and covering $[1, K]$, such that $(W_i)_{i \in K_1}$ and $(W_i)_{i \in K_2}$ are independent. Then, we have the nullity of the joint cumulant $\text{Cum}(W_1, \dots, W_K) = 0$.

In light of these two results, the strategy of [66] to upper bound the correlation $corr_{\leq D}$ is

1. To find a large set of $\alpha$'s such that $\kappa_{x,\alpha} = 0$ by using Lemma 2.2;

2. To upper-bound the cumulants $\kappa_{x,\alpha}$ for the remaining $\alpha$'s.

The second step is performed by expressing the cumulants $\kappa_{x,\alpha}$ as a linear combination of the mixed moments of the signal matrix $X$ – see Lemma B.1 in Appendix B –, and by applying the triangular inequality. However, this method fails for the problem of clustering when $p \leq n$, see [28]. We manage to improve this proof strategy, by taking better advantage of the conditional independencies of the entries of the signal matrix $X$ conditionally on the latent variable $Z$.

**2.2. Conditioning on the latent variables.** Our first main contribution is to propose a method for efficiently bounding cumulants $\kappa_{x,\alpha}$ in the latent variable model (1). This method then enables us to derive LD bounds for the problems of Clustering, Sparse Clustering and Biclustering. Our recipe to enhance the proof technique of [66] is to better exploit the conditional independences in the model. A key ingredient for handling conditional independences is the Law of Total Cumulance, that we recall here.
### LEMMA 2.3. [Law of Total Cumulance]
Let $W_1, \dots, W_K$ and $Z$ be random variables on the same space $\mathcal{W}$. Then,

$$ \text{Cum}(W_1, \dots, W_l) = \sum_{\pi \in \mathcal{P}([K])} \text{Cum} \left( \text{Cum} \left( (W_i)_{i \in R} \mid Z \right)_{R \in \pi} \right), $$

where $\mathcal{P}([K])$ denotes the set of all partitions of $[K]$.

We identify $\alpha \in \mathbb{N}^{n \times p}$ to a multiset of $[n] \times [p]$, where each $(i, j)$ is repeated $\alpha_{ij}$ times. For $\pi \in \mathcal{P}(\alpha \cup x)$ a partition of $\alpha \cup \{x\}$, we denote by $\pi_0$ the group containing $x$. Applying Lemma 2.3 and conditioning on the latent variables $Z$, leads to

$$ \kappa_{x,\alpha} = \text{Cum}(x, X_{\alpha}) = \sum_{\pi \in \mathcal{P}(\alpha \cup \{x\})} \text{Cum} \left( \text{Cum}(x, X_{\pi_0 \setminus \{x\}} | Z), \text{Cum}(X_R | Z)_{R \in \pi \setminus \{\pi_0\}} \right). $$

In our setting, the benefit of conditioning by $Z$ is that many of the conditional cumulants are zero, and those that are non-zero have very simple expressions.

### LEMMA 2.4. In the latent model (1) and under Assumption 1, for $\beta \in \mathbb{N}^{[n] \times [p]}$, we have

$$ \text{Cum}(x, X_{\beta} | Z) = x \mathbf{1}_{\beta=0} \quad \text{and} \quad \text{Cum}(X_{\beta} | Z) = \lambda^{\beta} \delta(Z)^{\beta} \mathbf{1}_{|\beta|=2} \mathbf{1}_{\Omega_{\beta}(Z)}, $$

where $\delta(Z)^{\beta} := \prod_{(i,j) \in \beta} \delta_{ij}(Z)$, and

$$ (14) \qquad \Omega_{\beta}(Z) := \{ \delta_{ij}(Z) \neq 0, \forall (i,j) \in \beta \} \cap \{|\theta_{ij}(Z) : (i,j) \in \beta| = 1\}. $$

### PROOF OF LEMMA 2.4.
For the first formula, when $\beta \neq 0$, since the variable $x$ is $\sigma(Z)$-measurable, it is independent from $X$ conditionally on $Z$. Lemma 2.2 implies that $\text{Cum}(x, (X_{ij})_{ij \in \beta} | Z) = 0$.

When $\beta = 0$, we have $\text{Cum}(x|Z) = \mathbb{E}[x|Z] = x$. So, we conclude

$$ \text{Cum}(x, X_{\beta} | Z) = x \mathbf{1}_{\beta=0}. $$

For the second formula, if there exists $(i_0, j_0) \in \beta$ such that $\delta_{i_0 j_0}(Z) = 0$, then $X_{i_0 j_0} = 0$ and so $\text{Cum}(X_{\beta} | Z) = 0$.

Let us then prove that if $|\{\theta_{ij}(Z), (i,j) \in \beta\}| \geq 2$, then $\text{Cum}(X_{\beta} | Z) = 0$. For that purpose, let us write, for some fixed $(k, l) \in \{\theta_{ij}(Z), (i,j) \in \beta\}$, $(\beta^{(1)})_{ij} = \beta_{ij} \mathbf{1}_{\theta_{ij}(Z)=(k,l)}$ and $(\beta^{(2)})_{ij} = \beta_{ij} \mathbf{1}_{\theta_{ij}(Z) \neq (k,l)}$. Both $\beta^{(1)}$ and $\beta^{(2)}$ are non-zero, and sum to $\beta$. Since $X_{ij} = \delta_{ij}(Z) \nu_{\theta_{ij}(Z)}$, and since the $\nu_{k,l}$'s are independent, the two families of random variables $(X_{ij})_{ij \in \beta^{(1)}}$ and $(X_{ij})_{ij \in \beta^{(2)}}$ are independent conditionally on $Z$. Thus, Lemma 2.2 implies the nullity of $\text{Cum}(X_{\beta} | Z)$. Finally, since $\nu_{kl} \sim \mathcal{N}(0, \lambda^2)$, when $|\{\theta_{ij}(Z) : (i,j) \in \beta\}| = 1$, we have

$$ \text{Cum}(X_{\beta} | Z) = \delta(Z)^{\beta} \text{Cum} \left( (\nu_{\theta_{ij}(Z)})_{(i,j) \in \beta} | Z \right) = \delta(Z)^{\beta} \lambda^{\beta} \mathbf{1}_{|\beta|=2}. $$

□

As a consequence of Lemma 2.4, only partitions $\pi \in \mathcal{P}(\alpha \cup \{x\})$ fulfilling $\pi_0 = \{x\}$ and $|\pi_j| = 2$ for $j \geq 1$ can provide non-zero terms in the decomposition (13). This set of partition is in bijection with the set of partitions $\pi = \{\pi_1, \dots, \pi_l\} \in \mathcal{P}(\alpha)$ fulfilling
$|\pi_j| = 2$ for $j = 1, \dots, l$. For such a partition $\pi$, there exists at least one decomposition $\alpha = \beta_1 + \dots + \beta_l$, with $l = |\pi| = |\alpha|/2$, fulfilling $|\beta_1| = \dots = |\beta_l| = 2$, and $\beta_1, \dots, \beta_l$ representing the groups $\pi_1, \dots, \pi_l$, i.e $[\beta_s]_{ij}$ counts the number of copies of $(i, j)$ in $\pi_s$. Let us define $\mathcal{B}_\alpha = \{\beta \in \mathbb{N}^{n \times p} : |\beta_1| = \dots = |\beta_l| = 2, \beta_1 + \dots + \beta_l = \alpha\}$ and denote by $S_l$ the set of permutations on $[l]$. The permutations in $S_l$ act on $\mathcal{B}_\alpha$, according to the action $\sigma \cdot \beta = (\beta_{\sigma(1)}, \dots, \beta_{\sigma(l)})$. Since group labels are meaningless for partitions, each partition $\pi \in \mathcal{P}(\alpha)$ with $|\pi_j| = 2$ for $j \ge 1$, can be represented by a unique element $\beta(\pi) \in \mathcal{B}_\alpha/S[l]$. To sum-up, each partition $\pi' \in \mathcal{P}(\alpha \cup \{x\})$ with $\pi'_0 = \{x\}$ and $|\pi'_j| = 2$ for $j \ge 1$, can be uniquely represented by a partition $\pi \in \mathcal{P}_2(\alpha) := \{\pi \in \mathcal{P}(\alpha) : |\pi_j| = 2 \text{ for } j \ge 1\}$, which, in turns, can be represented by an element $\beta(\pi) \in \mathcal{B}_\alpha/S[l]$. Hence, we have

$$ (15) \quad \sum_{\pi' \in \mathcal{P}(\alpha \cup \{x\})} \mathrm{Cum} \left( \mathrm{Cum} (x, X_{\pi'_0 \setminus \{x\}} | Z), \mathrm{Cum} (X_R | Z)_{R \in \pi' \setminus \{\pi'_0\}} \right) = \\ \qquad \sum_{\pi \in \mathcal{P}_2(\alpha)} \mathrm{Cum} \left( x, (\mathrm{Cum}(X_{\beta_s(\pi)} | Z))_{s \in [l]} \right). $$

We can now state our first main result, which provides a simple formula for the cumulant $\kappa_{x,\alpha}$.

**THEOREM 2.5.** For $\alpha \in \mathbb{N}^{n \times p}$, with $|\alpha| = 2l$, we define $\mathcal{P}_2(\alpha) := \{\pi \in \mathcal{P}(\alpha) : |\pi_j| = 2 \text{ for } j \in [l]\}$. In the latent model (1) and under Assumption 1, for $\alpha \in \mathbb{N}^{n \times p}$, with $|\alpha| = 2l$, the cumulant $\kappa_{x,\alpha}$ can be decomposed as a sum of cumulants

$$ (16) \qquad \kappa_{x,\alpha} = \lambda^{|\alpha|} \sum_{\pi \in \mathcal{P}_2(\alpha)} C_{x,\beta_1(\pi), \dots, \beta_l(\pi)}, $$

where $\beta(\pi) \in \{\beta \in (\mathbb{N}^{n \times p})^l : |\beta_1| = \dots = |\beta_l| = 2, \beta_1 + \dots + \beta_l = \alpha\}$, with $[\beta_s(\pi)]_{ij}$ counting the number of copies of $(i, j)$ in $\pi_s$, and where

$$ (17) \qquad C_{x, \beta_1, \dots, \beta_l} = \mathrm{Cum} \left( x, \delta(Z)^{\beta_1} \mathbf{1}_{\Omega_{\beta_1}(Z)}, \dots, \delta(Z)^{\beta_l} \mathbf{1}_{\Omega_{\beta_l}(Z)} \right), $$
with $\Omega_\beta(Z)$ defined in (14), and $\delta(Z)^\beta := \prod_{(i,j) \in \beta} \delta_{ij}(Z)$.

In particular, denoting $\beta[S] = \{\beta_s : s \in S\}$, the cumulants $C_{x, \beta_1, \dots, \beta_l}$ fulfill the recursive bound

$$ (18) \qquad |C_{x, \beta_1, \dots, \beta_l}| \le \mathbb{E} \left[ |x| \mid \bigcap_{s \in [l]} \Omega_{\beta_s} \right] + \sum_{S \subsetneq [l]} |C_{x, \beta[S]}| \mathbb{P} \left[ \bigcap_{s \in [l] \setminus S} \Omega_{\beta_s} \right]. $$

**PROOF OF THEOREM 2.5.** Formula (16) follows from (15), Lemma 2.4, and the homogeneity of cumulants. Formula (18) readily follows from the recursion formula for cumulants – see (59), page 38 –

$$ C_{x, \beta_1, \dots, \beta_l} = \mathbb{E} \left[ x \prod_{j \in [l]} \delta(Z)^{\beta_j} \mid \bigcap_{s \in [l]} \Omega_{\beta_s}(W) \right] - \sum_{S \subsetneq [l]} C_{x, \beta[S]} \mathbb{E} \left[ \prod_{j \in [l] \setminus S} \delta(Z)^{\beta_j} \mid \bigcap_{s \in [l] \setminus S} \Omega_{\beta_s}(Z) \right], $$
and $|\delta_{ij}(Z)| \le 1$. $\square$

For the sake of completeness, we derive below a simple upper-bound on the cumulant (17), which is good enough to get results up to poly-log factors.
**COROLLARY 2.6.** Under the hypotheses of Theorem 2.5, the cumulant (17) can be upper-bounded by

$$ (19) \quad |C_{x,\beta_1,\dots,\beta_l}| \le 2f_l \max_{\pi \in \mathcal{P}([l]\cup\{x\})} \left\{ \mathbb{E} \left[ |x|; \bigcap_{s \in \pi_1 \setminus \{x\}} \Omega_{\beta_s} \right] \prod_{k=2}^{[\pi]} \mathbb{P} \left[ \bigcap_{s \in \pi_k} \Omega_{\beta_s} \right] \right\}, $$

with $f_l$ the Fubini number, which fulfills $f_l \le 3l!2^l$.

We refer to Appendix F for a proof of this Corollary. The Bound (19) enables to prove meaningful computational barriers in the models considered, up to poly-log degree $D$. Yet, to prove computational barriers with sharp constants and/or higher degree $D$, we need a refined analysis, inspired by [68], based on the recursive bound (18) of Theorem 2.5.

**2.3. Deriving bounds on cumulants.** Let us now sketch how we can easily derive from Theorem 2.5 some useful bounds on the cumulants $\kappa_{x,\alpha}$ of Proposition 2.1. While the overall strategy is similar for the different models, the precise derivation is model specific. As an example, we outline the derivation of a bound on $\kappa_{x,\alpha}$ for the emblematic problem of Clustering a Gaussian mixture (2), which is an instantiation of the latent model (1), with $\nu = \mu$,

$$ Z = k^* = [k_1^*, \dots, k_n^*] \sim \mathcal{U}([K]^n), \quad \delta_{ij}(k^*) = 1, \quad \text{and} \quad \theta_{ij}(k^*) = (k_i^*, j). $$

Our goal is to estimate $x = \mathbf{1}_{k_1^*=k_2^*}$. We only describe here a simple proof strategy to get a bound on $\kappa_{x,\alpha}$, with a tight dependence in $K$, but a suboptimal dependence in $|\alpha|$. We refer to Appendix C for the detailed and tighter analysis, and we refer to Section 3 for detailed results on the clustering problem.

In the Gaussian clustering model, for $\alpha \in \mathbb{N}^{n \times p}$, we seek to control the cumulant

$$ \kappa_{x,\alpha} := \mathrm{Cum} \left( x, (\nu_{k_i^*; j})_{(i,j) \in \alpha} \right). $$

In the light of Theorem 2.5, it is sufficient to bound, for $\beta_1 + \dots + \beta_l = \alpha$ with $\beta_s = \{(i_s, j_s); (i'_s, j'_s)\}$, the cumulant

$$ \begin{aligned} C_{x,\beta_1,\dots,\beta_l} &= \mathrm{Cum} \left( x, \left( \mathbf{1}_{\{k_{i_s}^* = k_{i'_s}^*\}} \mathbf{1}_{\{j_s = j'_s\}} \right)_{s \in [l]} \right) \\ &= \mathrm{Cum} \left( \left( \mathbf{1}_{\{k_{i_s}^* = k_{i'_s}^*\}} \mathbf{1}_{\{j_s = j'_s\}} \right)_{s \in [0,l]} \right), \end{aligned} $$

where we take the convention $i_0 = 1, i'_0 = 2$ and $j_0 = j'_0 = 0$. Since the cumulant $C_{x,\beta_1,\dots,\beta_l}$ is zero when $j_s \neq j'_s$ for some $s \in [l]$, we focus on the case where $j_s = j'_s$ for all $s \in [l]$, and we seek to upper-bound

$$ C_{x,\beta_1,\dots,\beta_l} = \mathrm{Cum} \left( \left( \mathbf{1}_{\{k_{i_s}^* = k_{i'_s}^*\}} \right)_{s \in [0,l]} \right). $$

For any subset $S \subseteq [l]$, we write $\beta[S] = \{\beta_s, s \in S\}$. It is convenient to introduce a graph $\mathcal{V}$ on $[0, l]$ with an edge between $s, s'$ if and only if $\{i_s, i_{s'}\}$ intersects $\{i_{s'}, i'_{s'}\}$. A first step is to remark that, according to Lemma 2.2, when $S \neq \emptyset$, for having $C_{x,\beta[S]} \neq 0$, one needs to have (see Lemma C.5 for details)

1. $1, 2 \in \cup_{s \in S} \{i_s, i'_s\}$;

2. The restriction of $\mathcal{V}$ to $\{0\} \cup S$, denoted $\mathcal{V}[\{0\} \cup S]$, is connected.
Let us call active subsets $S \subseteq [l]$, subsets either satisfying these two conditions, or being empty. Building on the recursive bound (18), we have that, for any active $S$,
(20)

$$|C_{x,\beta[S]}| \le \mathbb{P}[\forall s \in S \cup \{0\}, k_{i_s}^* = k_{i'_s}^*] + \sum_{\substack{S' \subseteq S \\ S' \text{active}}} |C_{x,\beta[S']}| \mathbb{P}[\forall s \in S \setminus S', k_{i_s}^* = k_{i'_s}^*].$$

Let us denote by $\#\alpha$ the number of non-zero rows of $\alpha$. Since the graph $V[S \cup \{0\}]$ is connected, and since $1, 2 \in \cup_{s \in S} \{i_s, i'_s\}$, we have

$$\mathbb{P}[\forall s \in S \cup \{0\}, k_{i_s}^* = k_{i'_s}^*] = \left(\frac{1}{K}\right)^{\#\alpha_S - 1},$$

and, for all $S' \subseteq S$, we have

$$(21) \qquad \mathbb{P}[\forall s \in S \setminus S', k_{i_s}^* = k_{i'_s}^*] = \left(\frac{1}{K}\right)^{\#\alpha_{S\setminus S'} - cc(V[S\setminus S'])},$$

where $cc(V[S \setminus S'])$ stands for the number of connected components of $V[S \setminus S']$. Plugging these two formulas in (20), we get

$$(22) \qquad |C_{x,\beta[S]}| \le \left(\frac{1}{K}\right)^{\#\alpha_S - 1} + \sum_{\substack{S' \subseteq S \\ S' \text{active}}} |C_{x,\beta[S']}| \left(\frac{1}{K}\right)^{\#\alpha_{S\setminus S'} - cc(V[S\setminus S'])}.$$

From this recursive bound, we derive the following upper-bound on $|C_{x,\beta[S]}|$.

**LEMMA 2.7.** *There exists a constant $c_{|S|}$ such that $|C_{x,\beta[S]}| \le c_{|S|} \left(\frac{1}{K}\right)^{\#\alpha_S - 1}$.*

**PROOF OF LEMMA 2.7.** We prove Lemma 2.7 by induction over $S$. The initialization is immediate since $C_{x,\emptyset} = \mathbb{E}[x] = K^{-1}$. By induction, we get from (21) and (22)

$$|C_{x,\beta[S]}| \le \left(\frac{1}{K}\right)^{\#\alpha_S - 1} + \left(\frac{1}{K}\right)^{1+\#\alpha_S - cc(V[S])} + \sum_{\emptyset \ne S' \subseteq S} c_{|S'|} \left(\frac{1}{K}\right)^{\#\alpha_{S'} - 1 + \#\alpha_{S\setminus S'} - cc(V[S\setminus S'])}.$$

Since $V[S \cup \{0\}]$ is connected, it is clear that $cc(V[S]) \le 2$. Thus $1 + \#\alpha_S - cc(V[S]) \ge \#\alpha_S - 1$, and the second term in the right-hand side in not larger than the first one.

It remains to prove that for any active non empty subset $S' \subseteq S$, we have

$$\#\alpha_{S'} + \#\alpha_{S\setminus S'} - 1 - cc(V[S \setminus S']) \ge \#\alpha_S - 1.$$

To do so, we shall use the fact that $V[S \cup \{0\}]$ is connected. All connected component $cc$ of $V[S \setminus S']$ must be connected to $\{0\} \cup S'$. In other words, for such a connected component $cc$, there exists $i \in supp(\alpha_{cc}) \cap supp(\alpha_{S'})$, where $supp(\alpha)$ is the set of non-zero rows of $\alpha$. From this, we deduce that

$$\#\alpha_{S\setminus S'} \ge |supp(\alpha_{S\setminus S'}) \setminus supp(\alpha_{S'})| + cc(V[S \setminus S]),$$

and we conclude $\#\alpha_{S'} + \#\alpha_{S\setminus S'} - 1 - cc(V[S \setminus S']) \ge \#\alpha_S - 1$. This concludes the proof of the induction. $\square$
Lemma 2.7 ensures that $C_{x,\beta_1(\pi),...,\beta_l(\pi)} \le c_l \left(\frac{1}{K}\right)^{\#\alpha-1}$, for all $\pi \in \mathcal{P}_2(\alpha)$. Summing this bound over all the partitions in $\mathcal{P}_2(\alpha)$, ensures the existence of a constant $C_{|\alpha|}$, only depending on the norm $|\alpha|$, such that

$$ (23) \qquad \kappa_{x,\alpha} \le C_{|\alpha|} \left(\frac{1}{K}\right)^{\#\alpha-1}. $$

**REMARK 1.** In Appendix C, we improve this (sketch of) proof by controlling more carefully the terms in the induction of Lemma 2.7 and the number of partitions in $\mathcal{P}_2(\alpha)$ such that $C_{x,\beta_1(\pi),...,\beta_l(\pi)} \ne 0$. This allows us to avoid powers of D in the computational barrier of clustering, and to catch the BBP threshold at the exact constant, when $n \ge \text{poly}(D, K)$.

**REMARK 2.** In addition to upper-bounding the cumulants $\kappa_{x,\alpha}$ for any multiset $\alpha$, one also needs to prune a large number of multisets $\alpha$ such that $\kappa_{x,\alpha} = 0$. This is done in the proof of Theorem 3.1 in Appendix C. Let us underline another advantage of the conditioning: it reveals that for having $\kappa_{x,\alpha} \ne 0$, it is necessary that, for all $i \in \text{supp}(\alpha)$, $|\alpha_i| \ge 2$. Such a condition is necessary to catch the exact BBP constant.

**REMARK 3.** In [28], the control of $\kappa_{x,\alpha}$ is performed without conditioning. The power of $\frac{1}{K}$ in the upper-bound of [28] is not $\#\alpha - 1$ as in (23), but instead $\max(1, \#\alpha + r_\alpha - |\alpha|/2 - 1)$, where $r_\alpha$ is the number of non-zero rows and $|\alpha|$ is the $l^1$-norm of $\alpha$. This last power is much worse than $\#\alpha - 1$. For example, if one considers the matrix $\alpha$ defined by $\alpha_{ij} = \mathbf{1}\{i \le m\}\mathbf{1}\{j \le 2\}$, with $m$ even, we obtain,

a bound $O\left(\frac{1}{K^{m-1}}\right)$ with conditioning, and a bound $O\left(\frac{1}{K}\right)$ without conditioning.

This is the reason why our result for clustering in Theorem 3.1 holds in any dimension $p$, and not only when $p \ge n$, as in [28].

### 3. Clustering Gaussian mixtures.

*Set-up.* For the reader convenience, let us recall the Gaussian Mixture set-up (2). We observe a set of $n$ points $Y_1, \dots, Y_n \in \mathbb{R}^p$, which have been generated as follows. For some unknown vectors $\mu_1, \dots, \mu_K \in \mathbb{R}^p$, some unknown $\sigma > 0$, and an unknown partition $G^* = \{G_1^*, \dots, G_K^*\}$ of $\{1, \dots, n\}$, the points $Y_1, \dots, Y_n$ are sampled independently with distribution

$$ Y_i \sim \mathcal{N}(\mu_k, \sigma^2 I_p), \quad \text{for } i \in G_k^*. $$

For simplicity, we focus henceforth on the case where the clusters are balanced:

$$ (24) \qquad \frac{\max_k |G_k^*|}{\min_k |G_k^*|} \le \gamma, \quad \text{for some } \gamma \ge 1. $$

The clustering objective is to recover, partially or perfectly, the partition $G^*$. Our aim is to determine what is the minimal (scaled) separation $\Delta^2$, defined by (3), required for performing better than random clustering in polynomial time.
The minimal informational separation $\Delta^2$ for clustering better than at random has been established in [28]. When $p \gtrsim \log(K)$, the minimal separation for partial recovery (having less than some fixed proportion of misclassified points) is – see Theorems 2 and 3 in [28]

$$ (25) \qquad \Delta^2 \gtrsim \log(K) + \sqrt{\frac{pK}{n}\log(K)} . $$

However, partial recovery at the minimal separation level (25) is achieved by exactly minimizing the Kmeans criterion over all partitions of $[n]$. The problem of minimizing the Kmeans criterion is known to be NP-hard, and even hard to approximate [2]. In fact, in high dimension $p \ge n$, [28] provides a low-degree polynomial lower-bound suggesting that the problem is computationally hard when, up to logarithmic factors,

$$ (26) \qquad \Delta^2 \le \log 1 + \min \left( \sqrt{\frac{pK^2}{n}}, \sqrt{p} \right) . $$

It is also conjectured in [48] that there exists a statistical-computational gap in high dimension $p \ge \frac{n}{K^2}$. They consider the asymptotic regime, with $K$ fixed and $n/p \to \alpha > 0$, where they study the stable fixed points of the state evolution equation of Approximate Message Passing. In that setup, based on replica theory in statistical physics, they conjecture the hardness of clustering when $p \ge \log n/K^2$ and $\Delta^2 \le \sqrt{pK^2/n}$. Our goal in this section is to give evidence of this phenomenon, in a non-asymptotic regime, using the low-degree framework. More precisely,

1. for $K \le \text{poly-log } \sqrt{n}$, we prove low-degree hardness at the BBP threshold $\Delta^2 \le \sqrt{pK^2/n}$ with exact constant;

2. for $K \ge \text{poly-log } \sqrt{n}$, we prove low-degree hardness at the lower separation $\Delta^2 \le \log \sqrt{p}$, with a matching upper-bound, dismissing the conjecture of [48] when the number of clusters is high.

Compared to [28], our results are valid in any dimension $p$, including the challenging intermediate dimensions $n/K^2 \le p \le n$, and they are more precise as we prove a computational barrier at the exact level of the BBP transition. We also provide in Section 3.2 a poly-time algorithm matching the LD bound in most regimes, up to poly-log factors.

3.1. *LD lower-bound for clustering.* Our main contribution for the clustering problem is to prove low-degree hardness for

$$ \Delta^2 \le \min \left( \sqrt{\frac{pK^2}{n}}, \sqrt{\frac{p}{\log^{18} n}} \right) . $$

As explained in Section 2, our proof starts from Proposition 2.1 lifted from [66], and then build on Theorem 2.5 together with some arguments adapted from [68] to derive bounds on cumulants.

Low-degree polynomials are not well-suited for directly outputting a partition $\hat{G}$, which is combinatorial by nature. Instead, we focus on the problem of estimating the partnership matrix $M^*$ defined by $M_{ij}^* = \mathbb{1}\{i \stackrel{G^*}{\sim} j\}$. Indeed, proving computational hardness for estimating $M^*$, implies computational hardness for estimating $G^*$. Given a partition $G$, define the partnership matrix $M^G$ by $M_{ij}^G = \mathbb{1}\{i \stackrel{G}{\sim} j\}$. By [28] p.5, we know that,

$$ (27) \qquad \frac{1}{n(n-1)} \|M^G - M^*\|_F^2 \le \min_{\pi \in S_K} \frac{1}{n} \sum_{k=1}^{K} |G_k^* \Delta \hat{G}_{\pi(k)}| =: 2 \operatorname{err}(\hat{G}, G^*), $$
where $\triangle$ represents the symmetric difference, $S_K$ the permutation group on $[K]$, and where $err(\hat{G}, G^*)$ is the average proportion of misclassified points in $\hat{G}$. Hence, estimating $M^*$ in polynomial-time with small square-Frobenius distance is no harder than building a polynomial-time estimator $\hat{G}$ with a small error $err(\hat{G}, G^*)$. By linearity, we focus on estimating the functional $x = M_{12}^* = \mathbb{1}\{1 \stackrel{G^*}{\sim} 2\}$. In Appendix A.2, we also show that the hardness for reconstructing $x$ within a square error $K^{-1}(1 + o(1))$ implies that all polynomial-time balanced estimator $\hat{G}$ achieve an error $err(\hat{G}, G^*) \ge 1 + o(1)$. In other words, it is impossible to perform better than random guess.

For proving the LD bound, we consider the following prior on the means $\mu_k$ and the partition $G^*$.

**DEFINITION 1.** Let $k^*$ be a random variable uniformly distributed on $[K]^n$, and for $k \in [K]$ set $G_k^* = \{i \in [n] : k_i^* = k\}$. Furthermore, let the $\mu_k$ be random variables independent of $k^*$, with distribution

$$ \mu_{kj} \stackrel{i.i.d.}{\sim} \mathcal{N}(0, \lambda^2), \quad \text{with } \lambda^2 = \frac{1}{p} \bar{\Delta}^2 \sigma^2. $$

The prior in Definition 1 is an instantiation of the model (1), with

$$ Z = k^*, \quad \delta_{ij}(k^*) = 1, \quad \text{and} \quad \theta_{ij}(k^*) = (k_i^*, j). $$

We emphasize that, with high probability, we have a separation $\Delta^2 = \bar{\Delta}^2(1 + o_p(1))$ under this prior. The risk of the trivial estimator $\hat{x} = \mathbb{E}[x]$ of $x$ is

$$ MMSE_{\le 0} = \mathrm{var}(x) = \frac{1}{K} - \frac{1}{K^2}. $$

The next theorem provides conditions ensuring that $MMSE_{\le D} = MMSE_{\le 0}(1 + o_K(1))$.

**THEOREM 3.1.** Let $D \in \mathbb{N}$ with $D^5 \le p$ and assume that $\zeta := \frac{\bar{\Delta}^4}{p\sigma^4} \max(D^{18}, \frac{n}{K^2}) < 1$. Then, under the prior of Definition 1,

$$ MMSE_{\le D} \ge \frac{1}{K} - \frac{1}{K^2} \left[ 1 + \frac{\zeta}{(1 - \sqrt{\zeta})^3} \right]. $$

Theorem 3.1, proved in Appendix C, improves on Theorem 1 of [28] in two directions: First, it is valid for any dimension $p \ge D^5$, while Theorem 1 of [28] only covered the simplest case $p \ge n$; Second, the exact BBP threshold $\sqrt{pK^2}/n$ appears in $\zeta$, whereas there is a spurious factor $D^{12}$ in Theorem 1 of [28]. Theorem 3.1 implies that, for any numerical constant $\varepsilon > 0$, if $\sqrt{\zeta} \le 1 - \varepsilon$ and $p \ge D^5$, then there exists $C(\varepsilon) > 0$ such that

$$ MMSE_{\le D} \ge \frac{1}{K} - \frac{C(\varepsilon)}{K^2} = MMSE_{\le 0}(1 + o_K(1)). $$

Hence, no degree $D$ polynomials can perform significantly better than the trivial estimator in this regime. In particular, taking $D = (\log n)^{1+\eta}$, if $p \ge (\log n)^{5(1+\eta)}$, we prove $(\log n)^{1+\eta}$-degree hardness when

$$ (28) \qquad \bar{\Delta}^2 \le (1 - \varepsilon) \min \left( \sqrt{\frac{pK^2}{n}}, \sqrt{\frac{p}{(\log n)^{18(1+\eta)}}} \right). $$

Since polynomials of degree at most $(\log n)^{1+\eta}$ are considered as a proxy for algorithms that are computable in polynomial time [44, 66], Theorem 3.1 together with (27) suggest
the computational hardness of clustering in the regime (28) We remark that, when $K^2 \le n/(\log n)^{18(1+\eta)}$, the computational barrier (28) reduces to

$$ (29) \qquad \bar{\Delta}^2 \le (1 - \varepsilon) \sqrt{\frac{pK^2}{n}}, $$

as conjectured in [48] with replica heuristics. This barrier matches exactly the BBP transition threshold [9], where, in the asymptotic regime $n/p \to \alpha$ and $K \ll n, p$, the leading eigenvalues of the matrix $Y^TY$ become significantly larger from those of the Wigner matrix $E^T E$. We build on this property in Proposition 3.2, in order to design a poly-time algorithm, which recovers the partition $G^*$ after projecting the data onto the low dimensional space spanned by the leading eigenvectors of the matrix $Y^TY$.

Finally, we remark that, in low-dimension $p \le n(\log(K)/K)^2$, the computational barrier (28) is smaller than the informational barrier (25). Combining these two barriers, we provide evidence, when $p \ge (\log n)^{5(1+\eta)}$, that partial recovery of $G^*$ is computationally hard below the threshold

$$ (30) \qquad \bar{\Delta}^2 \le (c \log K) \vee \left( (1 - \varepsilon) \min \left( \sqrt{\frac{pK^2}{n}}, \sqrt{\frac{p}{\log(n)^{18(1+\eta)}}} \right) \right). $$

In the next section, we show that clustering in poly-time is possible, in almost all regimes, above the level (30). This provides an almost complete picture of the computational barrier for clustering Gaussian mixtures.

### 3.2. Matching the LD bound with a Spectral Method.
Let us first recall some known poly-time algorithms that, for some regimes of $n, p, K$, succeed to recover $G^*$ above the separation level (30), up to log factors.

* Many groups $K \gtrsim \sqrt{n}$. Hierarchical Clustering with single linkage, recovers exactly, with high probability, the partition $G^*$ when $\Delta^2 \gtrsim \log(n) + \sqrt{p \log(n)}$, see e.g. Proposition 4 in [28]. Thus, if $n \le cK^2$ for some constant $c$, it is easy to recover exactly $G^*$ when the separation is larger, up to some logarithmic factor, than the barrier (30), i.e. $\Delta^2 \gtrsim_{\text{poly-log}} \sqrt{p}$ in this regime;

* High dimension $p \ge n$. When $p \ge n$, some SDP relaxation of Kmeans, recover partially $G^*$, with high probability, when the separation is, up to some numerical constant, above the BBP threshold $\sqrt{pK^2/n}$, see Theorem 1 and Formula (12) in [35];

* Low dimension $\text{poly}(p, K) \le n$. Liu and Li [49] provides a poly-time algorithm which, with high probability, recover partially $G^*$ in poly-time, when $\Delta^2 \ge (\log K)^{1+c}$, and exactly when $\Delta^2 \ge (\log n)^{1+c}$, where $c$ is a constant depending on the polynomial of the condition $n \ge \text{poly}(p, K)$, see Theorem 2.5 and Corollary 2.6 in [49]. Their result ensures in particular the absence of statistical-computational gap (up to log factors) in low dimension.

These three results show that some poly-time algorithms succeed to recover $G^*$ above the separation level (30) – up to log factors –, either when the number of groups is high ($K \gtrsim \sqrt{n}$), or when the dimension is high ($p \ge n$) or small ($\text{poly}(p, K) \le n$). It remains to figure out if there exist some algorithms succeeding above the separation level (30) in moderate dimension $\text{poly-log}(n) \le p \le n$ with a small number of groups $K \lesssim \sqrt{n}$. Below, we show that we can find such algorithms in almost all, but not all, this regime.

For simplicity, we focus on the objective of perfect recovery of $G^*$ with high probability. The next proposition shows that clustering is possible in poly-time above the threshold (30) –up
to logarithmic factors–, except in the regime where both $p \le n/K$ and $K^2 \lesssim n \le \text{poly}(K)$, where the problem of optimal poly-time clustering remains open. We postpone to Appendix G.1 the proof of this proposition.

**PROPOSITION 3.2.** Assume that the unknown partition $G^*$ is $\gamma$-balanced (24).

1. There exist positive constants $c_\gamma$, $c'_\gamma$ depending only on $\gamma$, such that the following holds. If $n \ge c_\gamma K^2$, $n \ge p \ge \frac{n}{K}$ and $\Delta^2 \ge c'_\gamma \log(n) + \sqrt{pK^2 \log(n)/n}$, it is possible to recover exactly $G^*$ in poly-time with probability $1 - O(n^{-2})$;

2. There exists a constant $c''_\gamma > 0$ depending only on $\gamma$, such that, for all $\varepsilon > 0$, there exists $c_3(\varepsilon, \gamma) > 0$ satisfying the following. If $n \ge K^{c_3(\varepsilon, \gamma)}$ and $\Delta^2 \ge c''_\gamma \log(n)^{1+\varepsilon} + \sqrt{pK^2/n}$, it is possible to recover exactly $G^*$ in poly-time with probability $1 - O(n^{-c})$.

According to Proposition 3.2, perfect recovery can be achieved in poly-time above the threshold

$$ \Delta^2 \ge \log 1 + \min \left( \sqrt{p}, \sqrt{\frac{pK^2}{n}} \right), $$

except when both poly-log($n$) $\le p \le \frac{n}{K}$ and $K^2 \le n \le \text{poly}(K)$. The poly-time algorithm achieving this result, essentially proceeds as follows.

1. First, it projects the data points onto the $K$-dimensional space spanned by the $K$ leading eigenvectors of $Y^TY$;

2. Second, it applies on the projected data points, either hierarchical clustering with single linkage (first claim of Proposition 3.2), or the tensor-based algorithm of [49] (second claim).

The actual algorithm turns out to be a bit more involved, with some sample splitting to handle dependencies between the first and second step, we refer to Appendix G.1 for the detailed description. The key result on which Proposition 3.2 relies is Lemma G.1. This lemma ensures that, above the BBP threshold, at least a positive fraction of the signal is remaining after projection along the $K$ leading eigenvectors of $Y^TY$. Hence, the ambient dimension is reduced from $p$ to $K$, while preserving a fraction of the signal, reducing the initial problem to the problem of clustering in dimension $K$, for which we can apply existing optimal algorithms.

**REMARK 4.** In Section G.1, Proposition G.7 provides a result valid in any dimension, completing Proposition 3.2. This result states that when $n \gtrsim K^2$ and

$$ (31) \qquad \Delta^2 \ge c_\gamma \left( \log(n) + \sqrt{K \log(n)} + \sqrt{\frac{pK^2 \log(n)}{n}} \right), $$

hierarchical clustering with single linkage applied on the projected dataset exactly recovers $G^*$ with high probability. Despite not matching the lower bound of Theorem 3.1, Proposition G.7 improves on the result from [35] where a separation $\Delta^2 \gtrsim \log(n) + K + \sqrt{pK(K + \log(n))/n}$ is required.

**4. Sparse clustering.** In this section, we investigate the same problem of clustering an isotropic Gaussian mixture, but with the additional assumption that the means of the mixture are sparse.
**Set-up.** Let us recall the sparse clustering model. We observe a set of $n$ points $Y_1, \dots, Y_n \in \mathbb{R}^p$ which have been generated as follows. For some known $s \in [p]$, there exists an unknown subset $J^* \subseteq [p]$, with cardinality $|J^*| \le s$, such that, the unknown means $\mu_1, \dots, \mu_K$ are all supported on $J^*$, which means that $\mu_{kj} = 0$ for all $j \notin J^*$. Then, for some $\sigma > 0$, and some unknown partition $G^* = \{G_1^*, \dots, G_K^*\}$ of $[n]$, the points $Y_1, \dots, Y_n \in \mathbb{R}^p$ are sampled independently with distribution

$$Y_i \sim \mathcal{N}(\mu_k, \sigma^2 I_p), \quad \text{for } i \in G_k^*.$$

Again, we assume that the hidden partition $G^*$ is balanced, i.e that it satisfies (24), and as in Section 3, we analyse the minimal separation (3) required for successful clustering in poly-time and without time constraints.

The sparse clustering model is a particular instance of the Gaussian mixture model. Hence, the upper-bounds for clustering an isotropic Gaussian Mixture still hold in the case of sparse clustering. The computational lower-bound of Theorem 3.1 does not yet hold here, since the prior of Definition 1 is not sparse. We investigate in this section, whether the sparsity of the centers can help to recover in poly-time the partition $G^*$ below the computational barrier (30). Our contributions are:

1. Implementing the technique of Theorem 2.5, we provide a LD lower bound for the problem of sparse clustering. When $s \le \log \sqrt{p(K^2 \wedge n)}$, this lower-bound corresponds to the computational barrier (30) in reduced dimension $p = s$, plus an additional term $\sqrt{s^2/n}$, which can be interpreted as the minimal signal required to recover the active columns set $J^*$ in poly-time before clustering. When $s \le \log \sqrt{p(K^2 \wedge n)}$, this additional term $\sqrt{s^2/n}$ becomes larger than the computational barrier (30) in dimension $p$, and only this computational barrier applies.

2. Inspired by this lower-bound, we analyze a method that seeks to estimate the active columns set $J^*$ in polynomial time, and then clusters the points after removing the non-selected columns. Under an additional assumption of homogeneity of the signal along $J^*$, this method succeeds to cluster above the low-degree barrier obtained in the first step, up to log factors. This result supports our interpretation that the minimal separation for poly-time clustering is the sum of the separation $\sqrt{s^2/n}$ required for first recovering the active columns set $J^*$, plus the minimal separation for poly-time clustering in dimension $s$.

3. Under the same additional homogeneity assumption, we analyse an algorithm, not computable in polynomial time, which succeeds to cluster above the statistical rate (25) in reduced dimension $p = s$, when, in addition, $\Delta^2 \ge s\sqrt{K}/n$, up to log terms. This last constraint corresponds to the separation required for recovering the active columns set $J^*$ once the clustering is known. Since $K \le n$, we observe that this separation level $\Delta^2 \ge s\sqrt{K}/n$ is always smaller than the separation level $\sqrt{s^2/n}$ required for poly-time algorithms. We underline then a contrastive phenomenon for sparse-clustering under the homogeneity assumption. The additional separation $\Delta^2 \gtrsim \sqrt{s^2/n}$ required in poly-time corresponds to the separation needed for recovering the active columns before clustering, while the statistical additional separation $\Delta^2 \gtrsim s\sqrt{K}/n$ corresponds to the separation needed for recovering the active columns after clustering, exhibiting a better ability to fully exploit the joint sparse-and-clustered structure by non poly-time algorithms.

When $s \le n$, we observe that the separation level $\Delta^2 \gtrsim s\sqrt{K}/n$ is even smaller than the minimal statistical separation for clustering in dimension $s$, hence, in this specific case, sparse clustering without computational constraints is not harder than clustering in dimension $s$ without computational constraints.
Comparing the statistical and the computational rates, we observe the existence of a statistical-computational gap when either (i) $s \ge n$, or (ii) $s \in [K, n]$ and $n \le \log[pK^2 \wedge s^2]$, or (iii) $s \le K$ and $n \le \log K^2 s$. In particular, while the sparsity of the means makes the problem easier, both statistical and computationally, it widens the computational gap.

### 4.1. LD lower-bound for sparse clustering.
Let us introduce the prior under which we derive our LD bound. A simple choice could be to consider the same prior as in Definition 1, introducing sparsity by keeping the signal only on $s$ columns randomly chosen. Yet, such a prior introduces some weak-dependencies between the entries of a column, and the LD bounds that we would obtain under this prior would be suboptimal –see the discussion and derivations in Appendix A.3. To overcome this issue, we introduce some symmetrization in the generation of the means. For simplicity, we consider a partition into $2K$ groups, generate $K$ means as suggested before and then symmetrize them to get the remaining $K$ means. This process could have been applied with $K$ groups, instead of $2K$, by symmetrizing the centers of the first $2\lfloor K/2 \rfloor$ groups. However, this adds an unnecessary layer of complexity in the proof. In the following prior, the groups correspond to the different values of $(k_i^*, \epsilon_i) \in [K] \times \{-1, 1\}$.

**DEFINITION 2.** The signal matrix $X \in \mathbb{R}^{n \times p}$ is generated by sampling independently:

- $k_1^*, \dots, k_n^*$ independent with uniform distribution on $[K]$,

- $z_1, \dots, z_p$ independent, with Bernoulli distribution $\mathcal{B}(\rho)$, where $\rho = \bar{s}/p$,

- $\epsilon_1, \dots, \epsilon_n$ independent with uniform distribution on $\{-1, 1\}$,

- $\nu_{k,j}$, for $k, j \in [K] \times [p]$, independent, with $\nu_{k,j} \sim \mathcal{N}(0, \lambda^2)$, where $\lambda^2 = \bar{\Delta}^2 \sigma^2 / \rho p$; and then, setting

$$ (32) \qquad \mathbf{X}_{ij} = z_j \epsilon_i \nu_{k_i^*, j}. $$

Under the prior (32), the set of active columns is $J^* = \{j: z_j = 1\}$, and the partition $G^*$ is defined by $G_k^* = \{i: k_i^* = k\}$, and $\epsilon_i = 1$ for $k = 1, \dots, K$ and $G_k^* = \{i: k_i^* = k - K\}$, and $\epsilon_i = -1$ for $k = K+1, \dots, 2K$.

**REMARK 5.** With high probability, under the sparse prior (32), we have a separation $\Delta^2 = \bar{\Delta}^2(1 + o_{pp}(1))$.

**REMARK 6.** Let $s(z) := |\{j \in [p]: z_j = 1\}|$. It readily follows from large deviation inequality for Bernoulli variable, see e.g. Section 12.9.7 in [34], that $\mathbb{P}[s(z) > 5\rho p] \le \exp(-\rho p/2)$. Hence, when $\rho p \ge \log(n)$, with high probability, the model fulfills a sparsity assumption with $s = 5\rho p$.

As in Section 3, we consider the estimation of the variable $x = \mathbf{1}_{k_1^*=k_2^*}$. The next theorem, proved in Section D, provides a lower-bound on the $MMSE_{\le D}$ for estimating $x$.

**THEOREM 4.1.** Let $D \in \mathbb{N}$ and assume $\zeta := \frac{\bar{\Delta}^4}{\rho^2 p^2} \max(D^{14}, D^7 n, D^7 \rho^2 p, \rho^2 p \frac{n}{K^2}) < 1$. Then, under the prior distribution of Definition 2,

$$ MMSE_{\le D} \ge \frac{1}{K} - \frac{1}{K^2} \left[ 1 + \frac{\zeta}{(1 - \sqrt{\zeta})^3} \right]. $$
In particular, for any $\varepsilon > 0$, if $\sqrt{\zeta} \le 1 - \varepsilon$, then

$$MMSE_{\le D} = MMSE_{\le 0}(1 + o_K(1)).$$

If $D \le (\log n)^{1+\eta}$ and $\bar{\Delta}^2 \le (1 - \varepsilon) \min \left( \sqrt{\frac{\rho^2 p^2}{n(\log n)^{9(1+\eta)}}}, \sqrt{\frac{p}{(\log n)^{9(1+\eta)}}}, \sqrt{\frac{pK^2}{n}} \right)$, then $MMSE_{\le D} = \frac{1}{K} - \frac{1}{K^2}(1 + o_K(1))$. Since the class of polynomials of degree at most $(\log n)^{1+\eta}$ is considered as a proxy for algorithms computable in polynomial time, Theorem 4.1 provides evidence that sparse clustering is hard when

$$ (33) \quad \bar{\Delta}^2 \le (1 - \varepsilon) \min \left( \sqrt{\frac{\bar{s}^2}{n(\log n)^{9(1+\eta)}}}, \sqrt{\frac{p}{(\log n)^{9(1+\eta)}}}, \sqrt{\frac{pK^2}{n}} \right). $$

We recognize in (33) the barrier $\min(\sqrt{\frac{p}{(\log n)^{9(1+\eta)}}}, \sqrt{\frac{pK^2}{n}})$ from clustering in dimension $p$ – see (28). We notice yet that we have here the BBP threshold $\sqrt{pK^2/n}$ for $K$ groups, instead of $2K$ groups, due to the symmetrization in the prior of Definition 2, thereby using a factor 2. The barrier (33) can yet be smaller than the barrier for clustering in dimension $p$, due to the additional term $\sqrt{\bar{s}^2/(n(\log n)^{9(1+\eta)})}$. As we will see in the next section, this term can be interpreted as the barrier for estimating the non-zero columns of the signal.

We observe that when $\bar{s} \le \log n \wedge K^2$, the barrier (33) becomes smaller than the computational barrier $c \log(K) \vee \min \left( \sqrt{\frac{\bar{s}}{(\log n)^{18(1+\eta)}}}, \sqrt{\frac{\bar{s}K^2}{n}} \right)$ for clustering in dimension $\bar{s}$. Furthermore, the partial matrix $Y_{:,J_*}$ is independent of $X$ conditionally on $J^*$. So sparse-clustering is at least as hard as clustering the $n \times |J^*|$ matrix $Y_{:,J^*}$. In other words, sparse-clustering cannot be easier than clustering in dimension $|J^*|$. Hence, lifting the bound proved in Theorem 3.1 with $p = s$, we get that sparse clustering is low-degree hard when

$$ (34) \quad \bar{\Delta}^2 \le (c \log K) \vee \left( (1 - \varepsilon) \min \left( \sqrt{\frac{\bar{s}K^2}{n}}, \sqrt{\frac{\bar{s}}{(\log n)^{18(1+\eta)}}} \right) \right) \vee \left( (1 - \varepsilon) \min \left( \sqrt{\frac{\bar{s}^2}{n(\log n)^{9(1+\eta)}}}, \sqrt{\frac{p}{(\log n)^{9(1+\eta)}}}, \sqrt{\frac{pK^2}{n}} \right) \right), $$

which reduces, up to poly-logarithmic factors, to

$$ (35) \quad \bar{\Delta}^2 \le \log 1 + \min \left( \sqrt{\frac{\bar{s}K^2}{n}}, \sqrt{\bar{s}} \right) + \sqrt{\frac{\bar{s}^2}{n}} \quad \text{and} \quad \bar{\Delta}^2 \le \log 1 + \min \left( \sqrt{p}, \sqrt{\frac{pK^2}{n}} \right). $$

The first term in (35) is the sum of the computational barrier for clustering in dimension $\bar{s}$, plus a computational barrier $\sqrt{\bar{s}^2/n}$ for recovering the $\bar{s}$ active columns. The second condition is simply the computational barrier for clustering in dimension $p$. In some way, our bound (35) extends the LD lower bound of [50] for $K = 2$ to all $(K, s)$ regimes.

4.2. *Poly-time sparse clustering.* The setup of sparse clustering is a particular instance of clustering. Hence all the upper-bounds for clustering a Gaussian Mixture hold for sparse clustering, and we can cluster in poly-time above the second term in (35) in almost all regimes of $n, p, K$, see Section 3.2.
It remains to check that sparse clustering is possible in polynomial time when, up to some logarithmic factors,

$$ (36) \qquad \Delta^2 \ge_{\log} 1 + \sqrt{\frac{s^2}{n}} + \min \left( \sqrt{s}, \sqrt{\frac{sK^2}{n}} \right). $$

Since the term $1 + \min(\sqrt{s}, \sqrt{sK^2/n})$ corresponds, up to some logarithmic factors, to the computational barrier (30) for clustering in dimension $s$, it is natural [50, 58] to proceed by first detecting the active columns $J^*$ of $Y$ on which the signal is supported, then remove all the other columns of $Y$, and finally applying a clustering procedure on the reduced $Y_{:,J^*}$.

In a general, it is not easy, for $K \ge 2$, to recover exactly all the columns on which the signal is supported. We can still find columns on which most of the centers $\mu_k$ have a large part of their weight, and then recover the corresponding groups. However, this strategy is hard to analyse –see Appendix A.1, and, for simplicity of the proof, we consider a much simpler algorithm, merely selecting the $s$ columns $\hat{J}$ of $Y$ with largest Euclidean norm. This simple method will be successful under a minimum column-signal assumption. We denote by

$$ (37) \qquad \omega_{J^*}^2 := \frac{1}{\sigma^2} \min_{j \in J^*} \sum_{i \in n} X_{ij}^2 = \frac{1}{\sigma^2} \sum_{k \in [K]} |G_k^*| \mu_{k,j}^2, $$

the minimum $\ell^2$-norm of the active columns of $X$, and we assume that $\omega_{J^*}^2 \ge_{\log} \sqrt{n}$. Next lemma states that, under the previous minimum column-signal assumption, the estimator $\hat{J}$ contains $J^*$ with high probability.

**LEMMA 4.2.** There exists a numerical constant $c_1 > 0$ such that the following holds. If $\omega_{J^*}^2 \ge c_1 (\sqrt{n \log(pn)} + \log(p))$, then, with probability higher than $1 - \frac{1}{n^2}$, $\hat{J}$ contains $J^*$.

Let us briefly explain why the condition $\omega_{J^*}^2 \ge_{\log} \sqrt{n}$ condition ensures that $\hat{J} = J^*$ with high probability, we refer to Appendix G.2 for the detailed proof of Lemma 4.2. The square norm $\|Y_{:,j}\|^2$ has mean $\mathbb{E}[\|Y_{:,j}\|^2] = \|X_{:,j}\|^2 + n\sigma^2$, and standard deviation sdev $[\|Y_{:,j}\|^2] = \sigma^2\sqrt{n}$. Hence, as soon as $\omega_{J^*}^2 \ge_{\log} \sqrt{n}$, the set $J^*$ belongs to the $s$ columns of $Y$ with maximum Euclidean norm.

It turns out –see Lemma 4.4 and Corollary 4.5 below– that, under some homogeneity conditions on the signal, the condition $\omega_{J^*}^2 \ge_{\log} \sqrt{n}$ corresponds to our regimes of interest in (36). Once the columns $J^*$ have been retrieved, we can remove all the other columns, and apply a clustering procedure in dimension $s$, leading to the next result proved in Appendix G.2.

**PROPOSITION 4.3.** There exist constants $c$, $c_1$, and $c_2 > 0$ such that the following holds for any $\gamma$-balanced partition $G^*$ –see (24). Suppose that either $s \notin [\text{poly-log}(n), n/K]$ or $n \notin [K^2, K^c]$. Then, if

$$ \omega_{J^*}^2 \ge c_1 (\sqrt{n(\log(pn))} + \log(p)) \quad \text{and} \quad \Delta^2 \ge_{\log, \gamma} 1 + \min \left( \sqrt{s}, \sqrt{\frac{sK^2}{n}} \right), $$

there exists an algorithm computable in polynomial time which recovers exactly $G^*$ with probability higher than $1 - n^{-c_2}$.

When the signal is well spread along the active columns of $J^*$, a large separation $\Delta^2$ implies a large minimum $\ell^2$-norm of the active columns of $X$. In the following, we consider the case where the matrix $X$ satisfies the following homogeneity assumption.
ASSUMPTION 2. [η-homogeneity] For some η ≥ 1, the matrix X satisfies

$$
(38) \qquad \max_{j \in J^*} \frac{\|X:j\|^2}{\min_{j \in J^*} \|X:j\|^2} \le \eta .
$$

REMARK 7. With probability larger than 1 − ( n ∨ p ) − $^{2}$, the prior of Definition 2 is η -
homogeneous with η ≤ c √ log(np) /n .

We remark that when X satisfies the η-homogeneity assumption, we can lower-bound the minimum l²-norm of the active columns of X. We postpone to Section H the proof of the next lemma.

LEMMA 4.4. Assume that X satisfies the η-homogeneity Assumption (38). Then,

$$
w_{J^*}^2 \geq \frac{n(K-1)}{2sK\gamma\eta} \Delta^2 .
$$

Combining Lemma 4.4 with Proposition 4.3 directly implies the following corollary.

COROLLARY 4.5. Assume that X satisfies both the η-homogeneity assumption (38) and the balancedness condition (24) with η, γ ≤ poly-log(np) . Then, except in the regime where s ∈ [poly-log(n) , n/K ] and n ∈ [ K $^{2}$, poly( K )] , if

$$
\Delta^2 \geq_{\log} 1 + \min \left( \sqrt{s}, \sqrt{\frac{sK^2}{n}} \right) + \frac{s}{\sqrt{n}},
$$

we can recover perfectly G* in polynomial time, with probability higher than 1 − n − $^{c}$, for
some constant c.

We also prove in Appendix A.1, that, when $K \le 4$, the condition of $\eta$-homogeneity can be
dropped in Corollary 4.5.

In summary, we have introduced polynomial-time estimators that match our low-degree poly-
nomial lower bound (35) in almost all regimes. Our results show-case that, for the sparse clus-
tering problem, in polynomial-time, one cannot do significantly better, than applying an ag-
nostic clustering procedure (oblivious of the sparse structure) or applying a simple dimension
reduction scheme together with clustering procedure in the reduced space. The only regimes
where there is mismatch, namely when $n \in [K^2; \text{poly}(K)]$ and either $s \in [\text{poly-log}(n), n/K]$ or $p \in [\text{poly-log}(n), n/K]$, are the counterparts of those that have arisen in Proposition 3.2
for clustering.

4.3. Upper-bound on the minimal statistical separation for sparse clustering. Our previous results characterize the optimal separation conditions in polynomial-time (35). We now highlight the statistical-computational gaps for this problem by providing sufficient conditions for, possibly non-polynomial time procedures, to recover the partition $G^*$. We already deduce from [28] –see also the previous subsection– that $\Delta^2 \gtrsim \log(K) + \sqrt{pK \log(K)/n}$ is sufficient for the exact $K$-means estimator to achieve partial recovery, thereby lowering the second part of low-degree Condition (35) by a factor $\sqrt{K/\log(K)}$. Here, we focus on the second statistical-computational gap arising in sparse clustering, which is pertaining to the detection of the active columns. Recall the definition (37) of $\omega_{J^*}^2$ as the minimum squared $l^2$-norm of the active columns of $X$.
**PROPOSITION 4.6.** There exist two numerical constants $c_1, c_2$ and an estimator $\hat{G}$ such that the following holds. If $w_{J^*}^2 \ge c_1\gamma^2(\sqrt{K\log(np)} + \log(np))$ and $\Delta^2 \ge c\gamma^{5/2}[\sqrt{\frac{sK}{n}[\log(n)]} + \log(n)]$, then, with probability at least $1 - 4/n^2$, we have $\hat{G} = G^*$.

The rationale underlying the algorithm of Proposition 4.6 is to jointly select the column set $\hat{J}$ and the partition $\hat{G}$ by exactly minimizing some variant of the Kmeans criterion. Such a minimization requires to jointly scan over all the columns and partitions. In particular, the algorithm cannot be computed in poly-time.

Let us interpret the condition $w_{J^*}^2 \ge \log \sqrt{K}$ appearing in Proposition 4.6. We write $\bar{Y}^{G^*} \in \mathbb{R}^{K \times p}$ for the matrix obtained by averaging the rows within a same cluster: $\bar{Y}_{kj}^{G^*} = \text{average}\{Y_{ij} : i \in G_k^*\}$. We observe that, in the balanced case where $|G_k^*| = n/K$ for all $k$, we have $\mathbb{E}[\|\bar{Y}_{:j}^{G^*}\|^2] = \|\mu_{:j}\|^2 + K^2\sigma^2/n$ with standard deviation sdev $[\|\bar{Y}_{:j}^{G^*}\|^2] = K^{3/2}\sigma^2/n$. Hence, when knowing $G^*$, it is possible to recover the active columns $J^*$ as soon as

$$ (39) \qquad \min_{j \in J^*} \|\mu_{:j}\|^2 \ge \log \frac{K^{3/2}\sigma^2}{n}, $$

by selecting the $s$ columns of $\bar{Y}^{G^*}$ with largest $\ell^2$-norm. Since $\omega_{J^*}^2 \asymp \frac{n}{K\sigma^2} \min_{j \in J^*} \|\mu_{:j}\|^2$, Condition (39) is equivalent to $w_{J^*}^2 \ge \log \sqrt{K}$. Hence, the first condition of Proposition 4.6 corresponds to the condition for recovering $J^*$ when the partition $G^*$ is known beforehand. As for the second condition $\Delta^2 \ge \log 1 + \sqrt{sK/n}$, it corresponds to the optimal condition for recovering $G^*$ when $J^*$ is known, by applying exact Kmeans on the matrix $Y_{:,J^*}$, where we have only kept the active columns. Hence, non poly-time algorithms can fully leverage the sparse-clustering set-up by only requiring the minimal column signal for selecting the active columns when the clustering $G^*$ is known beforehand, in addition to the minimal separation for clustering when the active columns $J^*$ are known beforehand. This situation is in contrast with the poly-time algorithms, which require the minimal column signal for selecting the active columns with no clustering information.

Under the homogeneity assumption (38), Lemma 4.4 ensures that $\|\mu_{:j}\|^2 \gtrsim n\Delta^2\sigma^2/s$ for all $j \in J^*$, so the condition $\Delta^2 \ge \log s\sqrt{K}/n$ ensures (39). Combining this with Proposition 4.6 leads to next corollary.

**COROLLARY 4.7.** Assume that $X$ satisfies both the $\eta$-homogeneity assumption (38) and the balancedness condition (24) with $\eta, \gamma \le \text{poly-log}(np)$. Then, if

$$ \Delta^2 \ge \log 1 + \sqrt{\frac{sK}{n}} + \frac{s\sqrt{K}}{n}, $$
we have $\hat{G} = G^*$ with probability $1 - 4/n^2$.

Combining this corollary with the bounds of exact Kmeans in dimension $p$, we deduce that it is possible to recover $G^*$ as soon as

$$ \Delta^2 \ge \log 1 + \min \left[ \sqrt{\frac{sK}{n}} + \frac{s\sqrt{K}}{n}, \sqrt{\frac{pK}{n}} \right]. $$

In comparison to the LD lower bound (35), we see that, depending on the regimes, the statistical-computational gap is possibly as large as factor $\sqrt{n/K}$ or a factor $\sqrt{K}$.
**5. Biclustering.** We now turn our attention to the problem of biclustering, where both rows and columns are structured. Our goal is to understand if and how the clustering structure on the columns can help for recovering the clustering structure on rows, both statistically and in poly-time.

*Set-up.* In the biclustering model, we observe a matrix $Y \in \mathbb{R}^{p \times n}$ generated as follows. There exists two unknown partitions: $G^* = \{G_1^*, \dots, G_K^*\}$, partition of $[n]$, and $H^* = \{H_1^*, \dots, H_L^*\}$, partition of $[p]$. Then, for some unknown matrix $\mu \in \mathbb{R}^{K \times L}$, and unknown $\sigma > 0$, the entries $Y_{ij}$ are independent with distribution

$$Y_{ij} \sim \mathcal{N}(\mu_{kl}, \sigma^2), \quad \text{for } (i, j) \in G_k^* \times H_l^*.$$

We assume in the following that both $G^*$ and $H^*$ fulfill the balancedness condition (24). We observe that under the balancedness condition (24), for $i \in G_k^*$ and $i' \in G_{k'}^*$ we have

$$\|X_{i:} - X_{i' :}\|^2 = \sum_{l=1}^{L} |H_l^*| (\mu_{kl} - \mu_{k'l})^2 \asymp \frac{p}{L} \|\mu_{k:} - \mu_{k' :}\|^2.$$

Hence, we introduce

$$\Delta_r^2 = \frac{p}{L} \min_{k \neq k' \in [K]} \frac{\|\mu_{k:} - \mu_{k' :}\|^2}{2\sigma^2} \quad \text{and} \quad \Delta_c^2 = \frac{n}{K} \min_{l \neq l' \in [L]} \frac{\|\mu_{l:} - \mu_{l' :}\|^2}{2\sigma^2},$$

which represents, up to a constant factor, the minimum separation relative to the rows of $X$, and the minimum separation relative to the columns of $X$, respectively. The biclustering model being symmetric, we focus on the problem of recovering $G^*$. We investigate the minimal separation $\Delta_r^2$ required for recovering $G^*$, and how it depends on $\Delta_c^2$. Our contributions are

1. Implementing the technique of Theorem 2.5, we provide a LD lower bound for the biclustering problem, unveiling the following phenomenon. When $\Delta_c^2$ is below the minimal threshold $\Delta_c^2 \le \log 1 + \min(\sqrt{n}, \sqrt{nK^2/p})$ for poly-time clustering of the columns, then the clustering of the rows is as hard as when there is no column structure, and the separation (30) is required on $\Delta_r^2$ for recovering $G^*$. On the contrary, when $\Delta_c^2$ is above the minimal threshold for poly-time clustering, then the column structure can be leveraged to reduce the dimension from $p$ to $L$, and only the separation $\Delta_r^2 \ge \log 1 + \min(\sqrt{L}, \sqrt{LK^2/n})$ is required for recovering $G^*$. In this last case, recovery of $G^*$ is possible when $\Delta_r^2 \ge \log 1 + \min(\sqrt{L}, \sqrt{LK^2/n})$ by (i) clustering the columns, (ii) averaging all the columns within a same group, reducing the number of columns to $L$, and (iii) applying a poly-time row clustering on the new $n \times L$ matrix.

2. We prove that non poly-time algorithms can much better leverage the biclustering structure by merely requiring the separations

$$\Delta_r^2 \ge \log 1 + \sqrt{\frac{KL}{n}} \quad \text{and} \quad \Delta_c^2 \ge \log 1 + \sqrt{\frac{KL}{p}},$$

or $\Delta_r^2 \ge \log 1 + \sqrt{Kp/n}$. The separation $\Delta_r \ge \log \sqrt{KL/n}$ corresponds to the statistical separation for clustering the $n$ rows in dimension $L$, while the separation $\Delta_c^2 \ge \log \sqrt{KL/p}$ corresponds to the statistical separation for clustering the $p$ columns in dimension $K$. The separation $\Delta_c^2 \ge \log 1 + \sqrt{KL/p}$, required on the columns to benefit from the dimension reduction phenomenon, i.e. to benefit from the reduced requirement
$\Delta_r^2 \geq \log 1 + \sqrt{KL/n}$ on the rows, is much smaller than the separation $\Delta_c^2 \geq \log 1 + \min(\sqrt{n}, \sqrt{nK^2/p})$ required by poly-time algorithms. This separation $\Delta_c^2 \geq \log \sqrt{KL/p}$ corresponds to the separation needed to cluster the columns (recover $H^*$) when $G^*$ is known. Indeed, clustering the columns at this level of separation can be obtained when $G^*$ is known by (i) averaging the rows along the partition $G^*$, reducing the row dimension from $n$ to $K$, and (ii) clustering the columns of the transformed $K \times p$ matrix. Interestingly, this separation needed to recover $H^*$ when $G^*$ is known then allows to recover $G^*$ with the same separation $\Delta_r^2 \geq \log \sqrt{KL/n}$ as if the partition $H^*$ was known. Hence, non poly-time algorithms can fully leverage the biclustering structure.

5.1. *LD lower-bound for biclustering.* Let us introduce the prior distribution under which we derive our LD bound. As for sparse clustering, we use a symmetrization of the means in order to derive tight lower-bound, and for convenience we consider a setting with $2K$ row-clusters and $2L$ column-clusters.

**DEFINITION 3.** The signal matrix $X \in \mathbb{R}^{n \times p}$ is generated by sampling independently
- $k_1^*, \dots, k_n^*$ i.i.d. with uniform distribution on $[K]$,

- $l_1^*, \dots, l_p^*$ i.i.d. with uniform distribution on $[L]$,

- $\varepsilon_1^r, \dots, \varepsilon_n^r$ i.i.d. with uniform distribution on $\{-1, 1\}$,

- $\varepsilon_1^c, \dots, \varepsilon_p^c$ i.i.d. with uniform distribution on $\{-1, 1\}$,

- $(\nu_{k,l})_{k \in [K], l \in [L]}$ i.i.d. with $\mathcal{N}(0, \lambda^2)$ distribution, with $\lambda > 0$;

and then setting

$$ (40) \qquad X_{ij} = \varepsilon_i^r \varepsilon_j^c \nu_{k_i^*, l_j^*} . $$

Under the prior (40), the partition $G^*$ is defined by $G_k^* = \{i: k_i^* = k, \text{ and } \varepsilon_i^r = 1\}$ for $k=1, \dots, K$, and $G_k^* = \{i: k_i^* = k - K, \text{ and } \varepsilon_i^r = -1\}$ for $k = K + 1, \dots, 2K$; while the partition $H^*$ is defined by $H_l^* = \{j: l_j^* = l, \text{ and } \varepsilon_j^c = 1\}$ for $l=1, \dots, L$, and $H_l^* = \{j: l_j^* = l - L, \text{ and } \varepsilon_j^c = -1\}$ for $l=L+1, \dots, 2L$. Furthermore, under the assumption that $L \geq \log(K)$ and $K \geq \log(L)$, we have

$$ \Delta_r^2 = \frac{\lambda^2 p}{\sigma^2} \left( 1 + O \left( \sqrt{\frac{\log(K)}{L}} \right) \right) \quad \text{and} \quad \Delta_c^2 = \frac{\lambda^2 n}{\sigma^2} \left( 1 + O \left( \sqrt{\frac{\log(L)}{K}} \right) \right). $$

The next result provides two LD lower-bounds for the problem of clustering under the prior distribution (40).

**THEOREM 5.1.** Let $D \in \mathbb{N}$ and suppose that $\zeta := \frac{\lambda^4}{\sigma^4} D^8 \max(p, n, \frac{pn}{K^2}, \frac{pn}{L^2}) < 1$. Then, under the prior distribution of Definition 3, we have

$$ (41) \qquad MMSE_{\leq D} \geq \frac{1}{K} - \frac{1}{K^2} \left( 1 + \frac{\zeta}{(1 - \sqrt{\zeta})^3} \right). $$

Moreover, if $\zeta' := \frac{\lambda^4}{\sigma^4} D^{10} \frac{5p^2}{L} \max(1, \frac{n}{K^2}) < 1$, then, under the prior distribution of Definition 3, we have

$$ (42) \qquad MMSE_{\leq D} \geq \left(1 - L \exp\left(-\frac{5p}{2L} \log(5)\right)\right) \left(\frac{1}{K} - \frac{1}{K^2} \frac{\sqrt{\zeta'}}{(1 - \sqrt{\zeta'})^2}\right). $$
We refer to Appendix E for a proof of this result. Instantiating Theorem 5.1 for the degree $D = \log(n)^{1+\eta}$, we get that $MMSE_{\le D} = (\frac{1}{K} - \frac{1}{K^2})(1 + o(1))$

$$ (43) \quad \text{if } n\lambda^2 \le \log \sigma^2 \min \left( \sqrt{n}, \sqrt{\frac{L^2 n}{p}} \right) \quad \text{and} \quad p\lambda^2 \le \log \sigma^2 \min \left( \sqrt{p}, \sqrt{\frac{K^2 p}{n}} \right), $$

$$ (44) \quad \text{or, if } p \gg L \log L \quad \text{and} \quad p\lambda^2 \le \log \sigma^2 \min \left( \sqrt{L}, \sqrt{\frac{LK^2}{n}} \right). $$

Let us interpret these two conditions.

The first Condition (43) can be reformulated as

$$ \Delta_c^2 \le \log \min \left( \sqrt{n}, \sqrt{\frac{L^2 n}{p}} \right) \quad \text{and} \quad \Delta_r^2 \le \log \min \left( \sqrt{p}, \sqrt{\frac{K^2 p}{n}} \right). $$

We recognize in this condition the Threshold (28) for clustering in poly-time the $p$ columns in dimension $n$, and for clustering in poly-time the $n$ rows in dimension $p$. In particular, this result unravels that, below the threshold for poly-time clustering of the columns $\Delta_c^2 \le \log \min(\sqrt{n}, \sqrt{L^2n/p})$, the poly-time clustering of the rows is as hard as if there was no column structure. In other words, poly-time algorithms can leverage the biclustering structure only when either the columns or the rows have a separation larger than the separation (28) for simple clustering.

The second Condition (44) shows that, when $\Delta_c^2 \ge \log \min(\sqrt{n}, \sqrt{L^2n/p})$, poly-time clustering of the rows can be impossible when $p \gg L \log L$ and

$$ \Delta_r^2 \le \log \min \left( \sqrt{L}, \sqrt{\frac{LK^2}{n}} \right). $$

We recognize here the Threshold (28) for clustering in poly-time $n$ points in dimension $L$, into $K$ groups. This means that when columns can be clustered into $L$ groups, row clustering is as hard as clustering in dimension $L$. This threshold can be simply understood as follows. Let us define for $(i, l) \in [n] \times [L]$,

$$ (45) \qquad \bar{Y}_{il}^{H^*} = \frac{1}{|H_l^*|} \sum_{j \in H_l^*} Y_{ij} = \mu_{k_i l} + \bar{E}_{il}^{H^*}. $$

We observe that for $j \in H_l^*$, we have $Y_{ij} = \bar{Y}_{il}^{H^*} + \tilde{E}_{ij}$, where $\tilde{E}_{ij} = E_{ij} - \bar{E}_{il}^{H^*}$ is independent of $\bar{Y}_{il}^{H^*}$, with a distribution independent of $G^*$ and $\mu$. Hence, clustering the rows of $Y$ is at least as hard as clustering the rows of $\bar{Y}^{H^*}$. Conversely, when $\Delta_c^2 \ge \log \min(\sqrt{n}, \sqrt{L^2n/p})$, the column structure $H^*$ can be recovered in poly-time, with high-probability, in almost all regimes of $L, n, p$, so we can compute $\bar{Y}^{H^*}$ –see Section 3. Hence, when $\Delta_c^2 \ge \log \min(\sqrt{n}, \sqrt{L^2n/p})$, clustering the rows of $Y$ is not harder than clustering the rows of $\bar{Y}^{H^*}$. Since $\mathrm{var}(\bar{E}_{il}^{H^*}) \asymp L\sigma^2/p$, the row separation for $\bar{Y}^{H^*}$ is

$$ \Delta^2 \asymp \min_{k \ne k'} \frac{\|\mu_k - \mu_{k'}\|^2}{2L\sigma^2/p} = \Delta_r^2 $$

and the Condition (44) corresponds to the Threshold (28) for clustering the rows of $\bar{Y}^{H^*}$ in poly-time.
5.2. Upper bound on the statistical rate for biclustering. To get a complete picture of the biclustering problem, let us now investigate the minimal separations $\Delta_r$ and $\Delta_c$ above which row clustering is possible. First of all, according to (25), row clustering with exact Kmeans is always possible when $\Delta_r^2 \ge \log 1 + \sqrt{Kp/n}$, regardless of $\Delta_c^2$. Let us now examine how non poly-time algorithms can leverage the biclustering structure.

Let us consider the bi-Kmeans estimator (which is the MLE in the Gaussian setting)

$$ (46) \qquad (\hat{G}, \hat{H}) \in \underset{G,H}{\operatorname{argmin}} \sum_{\substack{k \in [K] \\ l \in [L]}} \sum_{\substack{i \in G_k \\ j \in H_l}} (Y_{ij} - \bar{Y}_{kl}^{G \times H})^2, $$

where $\bar{Y}_{kl}^{G \times H}$ is the average value of $Y_{ij}$ over $G_k \times H_l$. In some way, this least-square estimator shares some similarities with that in [33], although Gao et al. [33] focus their attention on the reconstruction of $X$ in Frobenius norm. The next proposition, proved in Section G.4, provides a condition under which bi-Kmeans is able to recover the partitions $G^*$ and $H^*$.

**PROPOSITION 5.2.** There exists numerical constants $c, c', c''$ such that the following holds for all $(n \lor p) \ge c'$ and for all $\gamma > 1$. Assume that the hidden partitions $G^*$ and $H^*$ fulfill the balancedness condition (24). Then, as long as we have

$$ (47) \qquad \Delta_r^2 \ge c\gamma^{5/2} \left[ \sqrt{\frac{KL \log(n \lor p)}{n}} + \log(n \lor p) \right], $$

$$ (48) \qquad \text{and} \quad \Delta_c^2 \ge c\gamma^{5/2} \left[ \sqrt{\frac{KL \log(n \lor p)}{p}} + \log(n \lor p) \right], $$

we have $\hat{G} = G^*$ and $\hat{H} = H^*$, with probability higher than $1 - c''/(n \lor p)^2$.

Proposition 5.2 ensures that non poly-time algorithms can recover the row (or column) partition $G^*$ as soon as

$$ \Delta_r^2 \ge \log 1 + \sqrt{\frac{KL}{n}} \quad \text{and} \quad \Delta_c^2 \ge \log 1 + \sqrt{\frac{KL}{p}}. $$

The separation $\Delta_r \ge \log \sqrt{KL/n}$ corresponds to the statistical separation for clustering $n$ rows in dimension $L$, while the separation $\Delta_c^2 \ge \log \sqrt{KL/p}$ corresponds to the statistical separation for clustering $p$ columns in dimension $K$. The separation $\Delta_c^2 \ge \log \sqrt{KL/p}$ can be interpreted as the separation needed to cluster the columns (recover $H^*$) when $G^*$ is known, by computing

$$ \bar{Y}_{kj}^{G^*} = \frac{1}{|G_k^*|} \sum_{i \in G_k^*} Y_{ij}, \quad \text{for } (k, j) \in [K] \times [p], $$

and then clustering the columns of $\bar{Y}^{G^*}$. Indeed, the variance of the entries of $\bar{Y}^{G^*}$ is around $K\sigma^2/n$, and the column separation for $\bar{Y}^{G^*}$ is then

$$ \Delta^2 \asymp \min_{l \neq l'} \frac{\|\mu_{:l} - \mu_{:l'}\|^2}{2K\sigma^2/n} = \Delta_c^2. $$

Strikingly, above the column separation $\Delta_c^2 \ge \log \sqrt{KL/p}$ needed to recover $H^*$ when $G^*$ is known, we are able to recover $G^*$ with the separation $\Delta_r^2 \ge \log \sqrt{KL/n}$ required when the partition $H^*$ is known. Hence, only a $K$-dimensional column separation condition is
needed to benefit from the L-dimensional row separation condition $\Delta_r^2 \ge \log 1 + \sqrt{KL/n}$ for successful clustering. This feature is in contrast with poly-time algorithms, where the n-dimensional column separation $\Delta_c^2 \ge \log 1 + \min(\sqrt{n}, \sqrt{L^2n/p})$ is required for benefitting from the L-dimensional row separation condition $\Delta_r^2 \ge \log 1 + \min(\sqrt{L}, \sqrt{K^2L/n})$. Hence, our analysis unravels a much better ability of non poly-time algorithms to leverage the biclustering structure, compared to poly-time algorithms.

To complete the picture, we underline that the condition $\Delta_r^2 \ge \log 1 + \sqrt{KL/n}$ is minimal for recovering $G^*$. Indeed, we can argue as in Section 5.1, and consider, for $j \in H_l^*$ the decomposition $Y_{ij} = \bar{Y}_{il}^{H*} + \tilde{E}_{ij}$, where $\bar{Y}_{il}^{H*}$ is defined in (45) and $\tilde{E}_{ij} = E_{ij} - \bar{E}_{il}^{H*}$ is independent of $\bar{Y}_{il}^{H*}$, with a distribution independent of $G^*$ and $\mu$. The problem of clustering the rows of Y is at least as hard as the problem of clustering the rows of $\bar{Y}_{il}^{H*}$, and the condition $\Delta_r^2 \ge \log 1 + \sqrt{KL/n}$ corresponds to the threshold above which row clustering of $\bar{Y}_{il}^{H*}$ is statistically possible. Hence, row-clustering of Y is, in general, impossible when $\Delta_r^2 \le \log 1 + \sqrt{KL/n}$. To sum-up, the minimal condition for recovering $G^*$ without computational constraints is

$$ \Delta_r^2 \ge \log 1 + \sqrt{\frac{Kp}{n}}, \quad \text{or} \quad \Delta_r^2 \ge \log 1 + \sqrt{\frac{KL}{n}} \quad \text{and} \quad \Delta_c^2 \ge \log 1 + \sqrt{\frac{KL}{p}}. $$

**6. Discussion and Open Problems.** The technique developed in Section 2 enables to derive computational lower bounds for three important clustering problems, matching the upper-bounds for poly-time algorithms in most of the regimes of parameters $n, p, K$. It is likely that this technique can also be successfully applied to other problems like tensor PCA [27], semi-supervised sparse clustering [3], etc. It can also be applied to binary observations, see Appendix A.4.

One major limitation of our technique is that it relies on the lower-bound on the $MMSE_{\le D}$ of [66] in terms of a sum of cumulants. This lower bound may not be tight in some regimes, due to a Jensen inequality at the heart of the analysis of [66], see e.g. the discussion in Appendix A.3. In particular, for clustering Gaussian mixture, in the regime where both $p \le n/K$ and $K^2 \lesssim n \le \text{poly}(K)$, our LD bound (30) and our poly-time upper bound (31) do not match. We suspect that, in this regime, both the LD and the poly-time upper-bounds are suboptimal. Some other proof techniques are probably needed to handle this very challenging regime, and the minimal separation for poly-time algorithms in this regime remains an open problem.

**Funding.** This work has been partially supported by ANR-21-CE23-0035 (ASCAI, ANR).

## REFERENCES

[1] ACHLIOPTAS, D. and MCSHERRY, F. (2005). On Spectral Learning of Mixtures of Distributions. In *Learning Theory* (P. AUER and R. MEIR, eds.) 458–469. Springer Berlin Heidelberg, Berlin, Heidelberg.

[2] AWASTHI, P., CHARIKAR, M., KRISHNASWAMY, R. and SINOP, A. K. (2015). The Hardness of Approximation of Euclidean k-Means. In *31st International Symposium on Computational Geometry (SoCG 2015)* 34 754–767. Schloss Dagstuhl – Leibniz-Zentrum für Informatik.

[3] AZAR, E. and NADLER, B. (2024). Semi-supervised sparse gaussian classification: Provable benefits of unlabeled data. *Advances in Neural Information Processing Systems* 37 20132–20169.

[4] AZIZYAN, M., SINGH, A. and WASSERMAN, L. (2013). Minimax theory for high-dimensional gaussian mixtures with sparse mean separation. In *Advances in Neural Information Processing Systems* 2139–2147.
[5] BAIK, J., AROUS, G. B. and PÉCHÉ, S. (2005). Phase transition of the largest eigenvalue for nonnull complex sample covariance matrices. *The Annals of Probability* **33** 1643–1697.

[6] BALAKRISHNAN, S., KOLAR, M., RINALDO, A., SINGH, A. and WASSERMAN, L. (2011). Statistical and computational tradeoffs in biclustering. *NIPS 2011 workshop on computational trade-offs in statistical learning* **4**.

[7] BANDEIRA, A. S., EL ALAOUI, A., HOPKINS, S., SCHRAMM, T., WEIN, A. S. and ZADIK, I. (2022). The Franz-Paris criterion and computational trade-offs in high dimensional statistics. *Advances in Neural Information Processing Systems* **35** 33831–33844.

[8] BANDEIRA, A. S., KUNISKY, D. and WEIN, A. S. (2019). Computational Hardness of Certifying Bounds on Constrained PCA Problems. *arXiv* 1902.07324.

[9] BANKS, J., MOORE, C., VERSHYNIN, R., VERZELEN, N. and XU, J. (2018). Information-theoretic bounds and phase transitions in clustering, sparse PCA, and submatrix localization. *IEEE Transactions on Information Theory* **64** 4872–4894.

[10] BARAK, B., HOPKINS, S., KELNER, J., KOTHARI, P. K., MOITRA, A. and POTECHIN, A. (2019). A Nearly Tight Sum-of-Squares Lower Bound for the Planted Clique Problem. *SIAM Journal on Computing* **48** 687–735.

[11] BERTHET, Q. and RIGOLLET, P. (2013). Complexity Theoretic Lower Bounds for Sparse Principal Component Detection. In *Proceedings of the 26th Annual Conference on Learning Theory* (S. SHALEV-SHWARTZ and I. STEINWART, eds.). *Proceedings of Machine Learning Research* **30** 1046–1066. PMLR, Princeton, NJ, USA.

[12] BRENNAN, M. and BRESLER, G. (2020). Reducibility and statistical-computational gaps from secret leakage. In *Conference on Learning Theory* 648–847. PMLR.

[13] BRENNAN, M., BRESLER, G., HOPKINS, S. B., LI, J. and SCHRAMM, T. (2020). Statistical query algorithms and low-degree tests are almost equivalent. *arXiv preprint arXiv:2009.06107*.

[14] BRENNAN, M., BRESLER, G. and HULEIHEL, W. (2018). Reducibility and computational lower bounds for problems with planted sparse structure. In *Conference On Learning Theory* 48–166. PMLR.

[15] CAI, T., LIANG, T. and RAKHLIN, A. (2017). Computational and Statistical Boundaries for Submatrix Localization in a Large Noisy Matrix. *The Annals of Statistics* **45** 1403–1430.

[16] CAI, T. T., MA, J. and ZHANG, L. (2019). Chime: Clustering of high-dimensional Gaussian mixtures with EM algorithm and its optimality. *Annals of Statistics* **47** 1234–1267.

[17] CHEN, X. and YANG, Y. (2021). Hanson–Wright inequality in Hilbert spaces with application to $K$-means clustering for non-Euclidean data. *Bernoulli* **27** 586–614.

[18] CHEN, Z., SHEEHAN, C. and ZADIK, I. (2024). On the Low-Temperature MCMC threshold: the cases of sparse tensor PCA, sparse regression, and a geometric rule. *arXiv preprint arXiv:2408.00746*.

[19] DADON, M., HULEIHEL, W. and BENDORY, T. (2024). Detection and recovery of hidden submatrices. *IEEE Transactions on Signal and Information Processing over Networks* **10** 69–82.

[20] DASGUPTA, S. (1999). Learning mixtures of Gaussians. In *40th Annual Symposium on Foundations of Computer Science (Cat. No.99CB37039)* 634–644.

[21] DIAKONIKOLAS, I., KANE, D. M., PITTAS, T. and ZARIFIS, N. (2023). SQ Lower Bounds for Learning Mixtures of Separated and Bounded Covariance Gaussians. In *Proceedings of Thirty Sixth Conference on Learning Theory* (G. NEU and L. ROSASCO, eds.). *Proceedings of Machine Learning Research* **195** 2319–2349. PMLR.

[22] DIAKONIKOLAS, I., KANE, D. M., PITTAS, T. and ZARIFIS, N. (2023). SQ Lower Bounds for Learning Mixtures of Separated and Bounded Covariance Gaussians. *Proceedings of Thirty Sixth Conference on Learning Theory* **195**.

[23] DIAKONIKOLAS, I., KANE, D. M. and STEWART, A. (2017). Statistical Query Lower Bounds for Robust Estimation of High-Dimensional Gaussians and Gaussian Mixtures. *2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS)*.

[24] DIAKONIKOLAS, I., KANE, D. M. and STEWART, A. (2018). List-decodable robust mean estimation and learning mixtures of spherical gaussians. In *Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing. STOC 2018* 1047–1060. Association for Computing Machinery.

[25] DING, Y., KUNISKY, D., WEIN, A. S. and BANDEIRA, A. S. (2024). Subexponential-time algorithms for sparse PCA. *Foundations of Computational Mathematics* **24** 865–914.

[26] DONOHO, D. L., MALEKI, A. and MONTANARI, A. (2009). Message-passing algorithms for compressed sensing. *Proceedings of the National Academy of Sciences* **106** 18919.

[27] DUDEJA, R. and HSU, D. (2024). Statistical-computational trade-offs in tensor PCA and related problems via communication complexity. *The Annals of Statistics* **52** 131–156. https://doi.org/10.1214/23-AOS2331
[28] EVEN, B., GIRAUD, C. and VERZELEN, N. (2024). Computation-information gap in high-dimensional clustering. In *Proceedings of Thirty Seventh Conference on Learning Theory* (S. AGRAWAL and A. ROTH, eds.). *Proceedings of Machine Learning Research* **247** 1646–1712. PMLR.

[29] FAN, J., LIU, H., WANG, Z. and YANG, Z. (2018). Curse of heterogeneity: Computational barriers in sparse mixture models and phase retrieval. *arXiv preprint arXiv:1808.06996*.

[30] FEI, Y. and CHEN, Y. (2018). Hidden Integrality of SDP Relaxations for Sub-Gaussian Mixture Models. In *Proceedings of the 31st Conference On Learning Theory. Proceedings of Machine Learning Research* **75** 1931–1965. PMLR.

[31] FLORESCU, L. and PERKINS, W. (2016). Spectral thresholds in the bipartite stochastic block model. In *Conference on Learning Theory* 943–959. PMLR.

[32] GAMARNIK, D. (2021). The overlap gap property: A topological barrier to optimizing over random structures. *Proceedings of the National Academy of Sciences* **118** e2108492118.

[33] GAO, C., LU, Y., MA, Z. and ZHOU, H. H. (2016). Optimal estimation and completion of matrices with biclustering structures. *Journal of Machine Learning Research* **17** 1–29.

[34] GIRAUD, C. (2021). *Introduction to high-dimensional statistics*. *Monographs on Statistics and Applied Probability* **168**. CRC Press, Boca Raton, FL.

[35] GIRAUD, C. and VERZELEN, N. (2019). Partial recovery bounds for clustering with the relaxed K-means. *Mathematical Statistics and Learning* **1** 317–374.

[36] HARTIGAN, J. A. (1972). Direct clustering of a data matrix. *Journal of the american statistical association* **67** 123–129.

[37] HOPKINS, S. (2018). Statistical inference and the sum of squares method, PhD thesis, Cornell University.

[38] HOPKINS, S. B., K. KOTHARI, P., A. POTECHIN, A., RAGHAVENDRA, P., CHRAMM, T. and STEURER, D. (2017). The Power of Sum-of-Squares for Detecting Hidden Structures. In *2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS)* 720-731. IEEE Computer Society, Los Alamitos, CA, USA.

[39] HOPKINS, S. B. and STEURER, D. (2017). Efficient Bayesian Estimation from Few Samples: Community Detection and Related Problems. In *2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS)* 379-390.

[40] JIN, J., KE, Z. T. and WANG, W. (2017). Phase transitions for high dimensional clustering and related problems. *The Annals of Statistics* **45**.

[41] KEARNS, M. (1998). Efficient noise-tolerant learning from statistical queries. *Journal of the ACM (JACM)* **45** 983–1006.

[42] KOLAR, M., BALAKRISHNAN, S., RINALDO, A. and SINGH, A. (2011). Minimax localization of structural information in large noisy matrices. *Advances in Neural Information Processing Systems* **24**.

[43] KOTHARI, P., VEMPALA, S. S., WEIN, A. S. and XU, J. (2023). Is planted coloring easier than planted clique? In *The Thirty Sixth Annual Conference on Learning Theory* 5343–5372. PMLR.

[44] KUNISKY, D., WEIN, A. S. and BANDEIRA, A. S. (2019). Notes on computational hardness of hypothesis testing: Predictions using the low-degree likelihood ratio. In *ISAAC Congress (International Society for Analysis, its Applications and Computation)* 1–50. Springer.

[45] KWON, J. and CARAMANIS, C. (2020). The EM Algorithm gives Sample-Optimality for Learning Mixtures of Well-Separated Gaussians. In *Proceedings of Thirty Third Conference on Learning Theory* (J. ABERNETHY and S. AGARWAL, eds.). *Proceedings of Machine Learning Research* **125** 2425–2487. PMLR.

[46] LAURENT, B. and MASSART, P. (2000). Adaptive estimation of a quadratic functional by model selection. *Annals of Statistics* **28** 1302–1338. MR1805785 (2002c:62052)

[47] LEI, J. and RINALDO, A. (2015). Consistency of spectral clustering in stochastic block models. *Ann. Statist.* **43** 215–237. MR3285605

[48] LESIEUR, T., DE BACCO, C., BANKS, J., KRZAKALA, F., MOORE, C. and ZDEBOROVÁ, L. (2016). Phase transitions and optimal algorithms in high-dimensional Gaussian mixture clustering. In *2016 54th Annual Allerton Conference on Communication, Control, and Computing (Allerton)* 601–608. IEEE.

[49] LIU, A. and LI, J. (2022). Clustering mixtures with almost optimal separation in polynomial time. In *Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing*. STOC 2022 1248–1261. Association for Computing Machinery, New York, NY, USA.

[50] LÖFFLER, M., WEIN, A. S. and BANDEIRA, A. S. (2022). Computationally efficient sparse clustering. *Information and Inference: A Journal of the IMA* **11**.

[51] LU, Y. and ZHOU, H. H. (2016). Statistical and computational guarantees of lloyd's algorithm and its variants. *arXiv preprint arXiv:1612.02099*.

[52] LUO, Y. and GAO, C. (2024). Computational lower bounds for graphon estimation via low-degree polynomials. *The Annals of Statistics* **52** 2318–2348.
[53] MA, Z. and WU, Y. (2015). Computational Barriers in Minimax Submatrix Detection. *The Annals of Statistics* **43** 1089–1116.

[54] MAO, C., WEIN, A. S. and ZHANG, S. (2023). Detection-recovery gap for planted dense cycles. In *The Thirty Sixth Annual Conference on Learning Theory* 2440–2481. PMLR.

[55] MARBAC, M. and SEDKI, M. (2017). Variable selection for model-based clustering using the integrated complete-data likelihood. *Statistics and Computing* **27** 1049–1063.

[56] MAUGIS, C. and MICHEL, B. (2011). A non asymptotic penalized criterion for Gaussian mixture model selection. *ESAIM: Probability and Statistics* **15** 41–68.

[57] MONTANARI, A. and WEIN, A. S. (2024). Equivalence of approximate message passing and low-degree polynomials in rank-one matrix estimation. *Probability Theory and Related Fields*.

[58] MUN, J., DUBEY, P. and FAN, Y. (2025). High-Dimensional Sparse Clustering via Iterative Semidefinite Programming Relaxed K-Means. *arXiv preprint arXiv:2505.20478*.

[59] NDAOUD, M. (2022). Sharp optimal recovery in the two component Gaussian mixture model. *The Annals of Statistics* **50** 2096 – 2126.

[60] NDAOUD, M., SIGALLA, S. and TSYBAKOV, A. B. (2021). Improved clustering algorithms for the bipartite stochastic block model. *IEEE Transactions on Information Theory* **68** 1960–1975.

[61] NOVAK, J. (2014). Three lectures on free probability. *Random matrix theory, interacting particle systems, and integrable systems* **65** 13.

[62] PENG, J. and WEI, Y. (2007). Approximating k-means-type clustering via semidefinite programming. *SIAM journal on optimization* **18** 186–205.

[63] RAFTERY, A. E. and DEAN, N. (2006). Variable selection for model-based clustering. *Journal of the American Statistical Association* **101** 168–178.

[64] REGEV, O. and VIJAYARAGHAVAN, A. (2017). On Learning Mixtures of Well-Separated Gaussians. In *2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS)* 85–96.

[65] ROMANOV, E., BENDORY, T. and ORDENTLICH, O. (2022). On the Role of Channel Capacity in Learning Gaussian Mixture Models. *Proceedings of Machine Learning Research vol 178:1–50*.

[66] SCHRAMM, T. and WEIN, A. S. (2022). Computational barriers to estimation from low-degree polynomials. *The Annals of Statistics* **50** 1833–1858.

[67] SEGOL, N. and NADLER, B. (2021). Improved convergence guarantees for learning Gaussian mixture models by EM and gradient EM. *Electronic Journal of Statistics* **15** 4510 – 4544.

[68] SOHN, Y. and WEIN, A. S. (2025). Sharp Phase Transitions in Estimation with Low-Degree Polynomials.

[69] VEMPALA, S. and WANG, G. (2004). A spectral algorithm for learning mixture models. *Journal of Computer and System Sciences* **68** 841–860. Special Issue on FOCS 2002.

[70] VERZELEN, N. and ARIAS-CASTRO, E. (2017). Detection and feature selection in sparse mixture models. *Annals of Statistics* **45** 1920–1950.

[71] WEIN, A. S. (2025). Computational Complexity of Statistics: New Insights from Low-Degree Polynomials.

[72] WITTEN, D. M. and TIBSHIRANI, R. (2010). A Framework for Feature Selection in Clustering. *Journal of the American Statistical Association* **105** 713–726.

[73] YUN, S. and PROUTIÈRE, A. (2014). Accurate Community Detection in the Stochastic Block Model via Spectral Algorithms. *CoRR abs/1412.7335*.
APPENDIX A: TECHNICAL DISCUSSIONS

All the results stated in this section are proved in Appendix H

**A.1. Sparse clustering: discussion of $w_J^2$, and of $\eta$-homogeneity condition.** In Sections 4.2 and 4.2, we introduced a condition on $w_J^2$ the minimum $l_2$-norm of the active columns of signal matrix $X$, in order to analyze our sparse clustering procedures. As explained in that section, our condition in $\omega_J^*$ matches the LD lower bound when an $\eta$-homogeneity condition is satisfied (Assumption 2).

We now shortly discuss how one could extend our sparse clustering procedures to bypass the condition on $\omega_J^*$ or equivalently Assumption 2. First, observe that, in general, it is impossible to recover all the active columns $J^*$ with high probability without any assumption on $w_J^*$. Nevertheless, as long as $\Delta^2$ is large enough, our feature selection procedure selects, with high probability, a subset $\bar{J}$ of $J^*$ which separates well a large fraction of the $\mu_k$'s.

**LEMMA A.1.** *There exist a subset $\bar{J} \subseteq J^*$ and a subset $K \subset [K]$ with $|K| \ge \frac{8K}{10}$ satisfying:*

1. For all $j \in \bar{J}$, $\sum_{k \in [K]} |G_k^*| (\mu_k)_j^2 \ge \frac{n\Delta^2}{80s\gamma}\sigma^2$;

2. For all $k \in K$ and $l \in [K]$, $\|(\mu_k)_{\bar{J}} - (\mu_l)_{\bar{J}}\|^2 \ge \frac{1}{8}\Delta^2\sigma^2$.

The first part of the above lemma ensures that the square norm of $X_{:j}$ is large, so that $j \in \bar{J}$ can be detected by looking at the norm $Y_{:j}$. The second part of Lemma A.1, ensures that reducing our attention to $\bar{J}$ allows to separate well most of the groups –but not all of them.

Assume that $\Delta^2 \ge_{\log,\gamma} 1 + s/\sqrt{n} + \min(\sqrt{s}, \sqrt{sK^2/n})$, which corresponds to the LD lower bound. In principle, we could then use a hierarchical scheme. We would first build independent copies of $Y$ –to the price of slightly lowering the separation $\Delta$. Then, we could first select a subset $\hat{J}$ of size $s$ of the columns with largest empirical norm. With large probability, it turns out that $\hat{J}$ will contain the subset $\bar{J}$ of Lemma A.1. Considering the second independent sample and focusing on the columns $\hat{J}$, we are back to a Gaussian mixture model with $K$ groups, $|K|$ of which, are separated by, up to constants, at least $\Delta^2$ from all the other groups. Hence, if we could adapt Proposition 3.2 to the case of a Gaussian mixture model, where a small proportion of the groups are not well separated, then we could distinguish the well-separated groups. Applying recursively the scheme to the subgroups and applying Lemma A.1 to these subgroups we would be able to recover features that allow to distinguish new groups.

However, the technical hurdle behind this approach is that Proposition 3.2 is only valid for Gaussian mixture models such that all groups are well-separated. In fact, Proposition 3.2 is based on a combination of clustering techniques: spectral projections, hierarchical clustering, the high-order tensor projection method of Li and Liu [49], and a SDP version of Kmeans. It is not difficult to show that both the spectral projection and hierarchical steps can be easily adapted to this setting. As for the high-order tensor projection method, we really suspect that it will be able to distinguish the groups $G_k^*$ with $k \in K$, but we did not check all the details. However, we do not know how to adapt the SDP analysis of [35] to this setting. As we mainly focus this manuscript on LD lower bounds, we do not pursue in this direction.
Case with $K \le 4$ clusters. When $K \le 4$, Lemma A.1 straightforwardly entails that $\bar{J}$ contain enough variables so that the restriction of $X$ to $\bar{J}$ still ensures a minimum separation at least $\Delta^2/8$ between all the clusters. Since, with high probability, $\hat{J}$ contains $J^*$, this implies that, in the second step of our polynomial-time sparse clustering procedure, we will apply a clustering procedure to a dimension $s$ Gaussian model with $K$ groups with separation $\Delta^2/8$. As a consequence, Corollary 4.5 is valid for $K \le 4$ without requiring the $\eta$-homogeneity condition.

**A.2. Impossibility of partition reconstruction.** Given a partition $G$, define the (unnormalized) partnership matrix $M^G \in \{0,1\}^{n \times n}$ by $M_{ij}^G = \mathbf{1}_{k_i^* = k_j^*}$. We write $M^*$ for $M^{G*}$. To simplify the discussion, we consider an asymptotic setting where $(K, n)$ (and possibly $p$) go to infinity, with $K = o(n)$.

**LEMMA A.2.** If $\mathbb{E}[\|M^*\|_F^2] = n^2 K^{-1}(1+o(1))$ and

$$MMSE_{poly} := \inf_{\hat{M}_{poly-time}} \frac{1}{n(n-1)} \mathbb{E} \left[ \|\hat{M} - M^*\|_F^2 \right] = \frac{1}{K}(1+o(1)),$$

then

$$\inf_{\hat{G}_{poly-time}} \frac{1}{n(n-1)} \mathbb{E} \left[ \|M^* - M^{\hat{G}}\|_F^2 \right] \geq \frac{2}{K}(1+o(1)).$$

Since the error $2K^{-1}(1+o(1))$ corresponds to the error rate of a uniform random partition, it means that, if we cannot estimate $M^*$ better than by its mean value, then we cannot estimate $\hat{G}$ better than at random in terms of the metric $\mathbb{E}[\|M^* - M^{\hat{G}}\|_F^2]$.

Let us consider the prior distribution of Definition 1 with $K \ll n/\log(n)$ so that $\mathbb{E}[\|M^*\|_F^2] = n^2 K^{-1}(1+o(1))$ and $G^*$ is $\gamma$-balanced with $\gamma = 1+o(1)$.

**PROPOSITION A.3.** Assume that $MMSE_{poly} = K^{-1}(1+o(1))$. Then, all polynomial-time estimators of the partition that are $\gamma$-balanced satisfy $\mathbb{E}[\mathrm{err}(\hat{G}, G^*)] = 1+o(1)$.

In other words, it is impossible to reconstruct in polynomial-time a (balanced) partition $\hat{G}$ better than random guessing in the regime where $MMSE_{poly} = K^{-1}(1+o(1))$.

**A.3. On the prior distribution for sparse clustering.** For the LD bound for sparse clustering, we introduce some symmetry in the prior of Definition 2. Let us explain why we did not consider a closer variant of the prior of Definition 1, by simply keeping the signal on $s$ columns randomly chosen. We underline in this appendix that, under this prior, we cannot derive the desired lower bound on the low-degree MMSE. Although this could come from the fact that this (non-symmmetric) prior is not suited for establishing the hardness of spase clustering, we suspect that this behaviour is rather due to the Jensen bound at the heart of the general method of [66].

Let us first define a (non-symmetric) prior for sparse clustering, which is more in line to Definition 1. We assume in this subsection that $\sigma = 1$.

**DEFINITION 4.** The signal matrix $X \in \mathbb{R}^{n \times p}$ is generated as follows. We sample independently:
- $k_1^*, \dots, k_n^*$ independent with uniform distribution on $[K]$,

- $z_1, \dots, z_p$ independent, with Bernoulli distribution $\mathcal{B}(\rho)$, where $\rho = \bar{s}/p$,

- $\nu_{k,j}$, for $k, j \in [K] \times [p]$, independent, with $\nu_{k,j} \sim \mathcal{N}(0, \lambda^2)$, where $\lambda^2 = \bar{\Delta}^2 \sigma^2 / \rho p$.

Then, we set

$$ (49) \qquad \mathbf{X}_{ij} = z_j \nu_{k_i^*, j}. $$

In our signal plus noise Gaussian model $Y = X + E$, it is straightforward to retrace the (strict) inequalities in the general bound of [66]. Indeed, given a polynomial $f(Y)$, the crux of [66] is to apply Jensen inequality to lower bound the second moments of $f(Y)$, that is

$$ \mathbb{E}[f(Y)^2] \ge \mathbb{E}_Z \left[ \left( \mathbb{E}_X [f(X + Z)] \right)^2 \right], $$

where $\mathbb{E}_X[\cdot] (\mathbb{E}_Z[\cdot])$ stands for the expectation with respect to $X$ (resp. $Z$). With this bound in mind, we define

$$ (50) \qquad \overline{corr}_{\le D}^{(SW)} := \sup_{\substack{f \in \mathbb{R}_D[Y] \\ \mathbb{E}(f^2(Y)) \ne 0}} \frac{\mathbb{E}[f(Y)x(Z)]}{\sqrt{\mathbb{E}_Z \left[ \left( \mathbb{E}_X [f(X + Z)] \right)^2 \right]}} $$

which is an upper bound of $corr_{\le D}$. We readily deduce from the proof of Theorem 2.2 in [66] that this modified degree-$D$ maximum correlation satisfies the equality

$$ (51) \qquad \left( \overline{corr}_{\le D}^{(SW)} \right)^2 = \sum_{\substack{\alpha \in \mathbb{N}^{n \times p} \\ |\alpha| \le D}} \frac{\kappa_{x, \alpha}^2}{\alpha!} . $$

The following proposition, provides a lower bound on $\left( \overline{corr}_{\le D}^{(SW)} \right)^2$.

**PROPOSITION A.4.** The exist two numerical constants $c$ and $c'$ such that the following holds. Consider any even $D$ degree such that $n \ge 4D$ and $\rho \le [12(D/2)!2^{D/2}]^{-1}$. Then, we have

$$ \left( \overline{corr}_{\le D}^{(SW)} \right)^2 \ge c' e^{-cD \log(D)} p \frac{n^{D-2}}{K^D} \lambda^{2D} \rho^2, $$

In light of the definition of $\lambda$, we conclude that $\left( \overline{corr}_{\le D}^{(SW)} \right)^2 \ge 1$ as soon as

$$ (52) \qquad \bar{\Delta}^2 \ge c' e^{c \log(D)} \frac{\bar{s} K}{n} \cdot \left( \frac{n^2 p}{\bar{s}^2} \right)^{1/D} . $$

In particular, it is therefore not possible to provide a non-trivial lower bound on $MMSE_{\le D}$ using the approach of [66] as long as the above condition is satisfied.

Consider for a instance a regime where $K$ is a constant and $\sqrt{n} \ll s \ll p$. Then, our main result in Section 4-see 35- entails that clustering is impossible as soon as

$$ \bar{\Delta}^2 \le \log \frac{\bar{s}}{\sqrt{n}}, $$

whereas, equipped with the prior of Definition 4, we would at best be able to prove the condition $\bar{\Delta}^2 \le \log \bar{s}/n$, which is looser by a factor $\sqrt{n}$.
**A.4. Extension to binary observations.** When the data $Y \in \{0,1\}^{n \times p}$ are binary, with $\mathbb{P}[Y_{ij} = 1|X] = X_{ij}$ and $1 < \tau_0 \le X_{ij} \le \tau_1 < 1$, [66] provides a lower bound on the MMSE$_{\le D}$ in terms of the cumulants $\text{Cum}(x, X_\alpha)$

$$ (53) \qquad MMSE_{\le D} \ge \mathbb{E}[x^2] - \sum_{\alpha \in \{0,1\}^{n \times p}, \ |\alpha| \le D} \frac{\text{Cum}(x, X_\alpha)^2}{(\tau_0(1-\tau_1))^{|\alpha|}}. $$

In this case, we cannot choose in the latent model the $\nu_{kj}$ with Gaussian distribution, since it should be bounded a.s. Instead, we can consider $\nu$ uniformly distributed on a shifted hyper-cube. We explain below how to handle this setting.

Let us suppose that the signal matrix is the form

$$ X_{ij} = m_{ij} + \delta_{ij}(Z)\nu_{\theta_{ij}}(Z), $$

with $m_{ij} \in (0,1)$ and the $\nu_{kl}$ taken i.i.d uniformly on $\{-\lambda, \lambda\}$, instead of being Gaussian. We then have $X_{ij} \in [\tau_0, \tau_1]$ a.s., with $\tau_0 = \min_{ij} m_{ij} - \lambda$ and $\tau_1 = \max_{ij} m_{ij} + \lambda$. Since the $m_{ij}$'s are constant, by multilinearity of the cumulants combined with Lemma 2.2, we have that, for any multiset $\alpha \in \mathbb{N}^{n \times p}$,

$$ \text{Cum}(x, X^\alpha) = \text{Cum}(x, (\delta_{ij}(Z)\nu_{\theta_{ij}}(Z))_{(i,j)\in\alpha}). $$

Therefore, without loss of generality, we can assume that $m_{ij} = 0$ for all $(i, j)$.

As for the Gaussian prior, we can still apply the Law of Total Cumulance and get,

$$ \kappa_{x,\alpha} = \text{Cum}(x, X_\alpha) = \sum_{\pi \in \mathcal{P}(\alpha \cup \{x\})} \text{Cum} \left( \text{Cum} \left( x, X_{\pi_0 \setminus \{x\}} | Z \right), \text{Cum} \left( X_R | Z \right)_{R \in \pi \setminus \{\pi_0\}} \right). $$

For $\beta \ne 0$, it is still true that $\text{Cum}(x, (X_{ij})_{ij \in \beta} | Z) = 0$. The difference lies in the expression of $\text{Cum}(X_\beta | Z)$ which is

$$ \text{Cum}(X_\beta | Z) = c_{|\beta|} \lambda^{|\beta|} \delta(Z)^\beta \mathbf{1}_{|\beta|=0|2|} \mathbf{1}_{\Omega_\beta(Z)}, $$

where $\delta(Z)^\beta := \prod_{(i,j) \in \beta} \delta_{ij}(Z)$,

$$ (54) \qquad \Omega_\beta(Z) := \{\delta_{ij}(Z) \ne 0, \forall (i,j) \in \beta\} \cap \{|\theta_{ij}(Z) : (i,j) \in \beta| = 1\}, $$

and

$$ c_{|\beta|} = \sum_{\pi \in \mathcal{P}(|\beta|)} m(\pi) \mathbf{1}\{\forall R \in \pi, |R| = 0 \text{ [2]}\}. $$

We recall that with a Gaussian prior, this conditional cumulant was null whenever $|\beta| \ne 2$. For $\alpha \in \mathbb{N}^{n \times p}$ a multiset, we write $\mathcal{P}^{even}(\alpha)$ the set of all partitions $\pi$ of $\alpha$ such that, for all $R \in \pi$, $|R| = 0$ [2]. We end up with the following proposition.

**PROPOSITION A.5.** For all $\alpha \in \mathbb{N}^{n \times p}$

$$ (55) \qquad \kappa_{x,\alpha} = \lambda^{|\alpha|} \sum_{\pi \in \mathcal{P}^{even}(\alpha)} \left( \prod_{s \in |\pi|} c_{|\beta_s(\pi)|} \right) C_{x,\beta_1(\pi), \dots, \beta_{|\pi|}(\pi)}, $$

with $[\beta_s(\pi)]_{ij}$ counting the number of copies of $(i, j)$ in $\pi_s$, and where

$$ (56) \qquad C_{x,\beta_1, \dots, \beta_{|\pi|}} = \text{Cum} \left( x, \delta(Z)^{\beta_1} \mathbf{1}_{\Omega_{\beta_1}(Z)}, \dots, \delta(Z)^{\beta_l} \mathbf{1}_{\Omega_{\beta_{|\pi|}}(Z)} \right), $$

with $\Omega_\beta(Z)$ defined in (54), and $\delta(Z)^\beta := \prod_{(i,j) \in \beta} \delta_{ij}(Z)$.
Applying Proposition A.5 to the three problems considered, we would obtain the same upper-
bounds on $\kappa_{x,\alpha}$ than with a Gaussian Prior, up to some multiplicative constant of the form
$|\alpha|^{|c|\alpha}$. The obtained computational barrier would be similar up to some power of $D$. The
downside of this being that we would not be able to catch the exact BBP constant when
$n \ge \text{poly}(K, D)$ for the problems of Clustering and Sparse Clustering. For Biclustering, we
would obtain the same result, with a modification of the power of $D$ in the expression of $\zeta$
(see Theorem 5.1).

**A.5. Discussion of other frameworks of computational lower-bounds.** LD Polynomi-
als is a popular restricted class of estimators used for understanding computational limits.
However, it is not the only class that is used to predict computational barriers; here is an non-
exhaustive list of other classes of estimators that are widely used when trying to understand
computational limits.

*Sum-of-Square Hierarchy.* The Sum of Square hierarchy is a family of Semi-Definite pro-
grams that is used for the task of *certification* [37, 38, 10]. The question to answer is wether
SoS can certify the absence of a structure. However, *certification* problems can be sometimes
harder than the associated recovery problem [8].

*Approximate Message Passing (AMP).* AMP is an iterative procedure that is believed to be optimal amongst polynomial time algorithms. Failure of AMP is often taken as an evidence for the Hardness of a problem [48, 26]. AMP can be approximated by low-degree polynomials; hence LD hardness is stronger than AMP hardness. [57] proved the equivalence of AMP and LD polynomials in Rank-One Matrix Estimation.

*SQ Lower bound* [41]. The Statistical Query model corresponds to a framework where we can access to queries, which are noised version of the expectation of a chosen function. Lower-bounding the number of queries needed is taken as a proxy for the time complexity of this problem [23] [22]. In a lot of detection models, the SQ framework is equivalent to the LD framework [13].

*Spectral Methods.* Spectral Algorithms rely on computing leading eigenvectors or singular vectors of a well chosen matrix constructed from the data. [5] proves an asymptotic phase transition for spectral detection in sparse PCA that we refer as the BBP transition. Numerous spectral methods have studied for different models, such as clustering [69, 9], learning of distributions [1], the Stochastic Block model [73, 47], or as said before sparse PCA. Since eigenvectors of matrices can be approximated via power-iteration, spectral methods with respect to matrices which are polynomials of the data can be approximated by LD polynomials.

*Landscape Analysis.* In optimization problems, it is possible to provide a barrier for stable Algorithms with the Overlap Gap Property [32]. This property can be extended to problems of estimation with planted structure and provide barriers for algorithms such as MCMC [18].

APPENDIX B: BACKGROUND ON CUMULANTS

From [66], we know that in a Gaussian Additive model, proving LD lower bounds can be
reduced to computing some joint cumulants $\kappa_{x,\alpha}$. We provide in this section a brief overview
on cumulants, and we refer e.g. to [61] for more details.
**DEFINITION 5.** Let $W_1, \dots, W_l$ be random variables on the same space $\mathcal{W}$. Their cumulant generating function is the function

$$K(t_1, \dots, t_l) := \log \mathbb{E} \left[ \exp \left( \sum_{l'=1}^{l} t_{l'} W_{l'} \right) \right],$$

and their joint cumulant is the quantity

$$\mathrm{Cum}(W_1, \dots, W_l) := \left( \left( \prod_{l'=1}^{l} \frac{\partial}{\partial t_{l'}} \right) K(t_1, \dots, t_l) \right)_{t_1, \dots, t_l=0}.$$

The joint cumulant of random variables can be expressed as a linear combination of their mixed moments and vice-versa.

**LEMMA B.1.** Let $W_1, \dots, W_l$ be random variables on the same space $\mathcal{W}$. Let $\mathcal{P}([l])$ stands for the collections of permutations of $[l]$. Then

$$(57) \qquad \mathbb{E}[W_1 \cdots W_l] = \sum_{\pi \in \mathcal{P}([l])} \prod_{R \in \pi} \mathrm{Cum}(W_j : j \in R),$$

$$(58) \qquad \text{and} \quad \mathrm{Cum}(W_1, \dots, W_l) = \sum_{\pi \in \mathcal{P}([l])} m(\pi) \prod_{R \in \pi} \mathbb{E} \left[ \prod_{l' \in R} W_{l'} \right],$$

where $m(\pi)$ is the Möbius function $m(\pi) = (-1)^{|\pi|-1} (|\pi| - 1)!$.

By considering aside the trivial partition $\pi$ with one group, and by enumerating the partitions $\pi$ on $[l]$ by considering $\{l\} \subset R_0 \subset \{1, \dots, l\}$ and partitions $\pi'$ of $[l] \setminus R_0$, we get from (57), with the short notation $\mathrm{Cum}[R] := \mathrm{Cum}(W_j : j \in R)$

$$\mathbb{E}[W_1 \cdots W_l] = \mathrm{Cum}[[l]] + \sum_{\{l\} \subset R_0 \subset \{1, \dots, l\}} \mathrm{Cum}[R_0] \sum_{\pi' \in \mathcal{P}([l] \setminus R_0)} \prod_{R \in \pi'} \mathrm{Cum}[R]$$

$$(59) \qquad = \mathrm{Cum}[[l]] + \sum_{\{l\} \subset R_0 \subset \{1, \dots, l\}} \mathrm{Cum}[R_0] \mathbb{E} \left[ \prod_{j \in [l] \setminus R_0} W_j \right].$$

As noticed by [66], a key feature for proving LD lower-bounds is next lemma, which gives a sufficient condition for the nullity of cumulants.

**LEMMA B.2.** Let $W_1, \dots, W_l$ be random variables on the same space $\mathcal{W}$. Suppose that there exist disjoint sets $L_1$ and $L_2$, non-empty and covering $[l]$, such that $(W_i)_{i \in L_1}$ and $(W_i)_{i \in L_2}$ are independent. Then, we have the nullity of the joint cumulant $\mathrm{Cum}(W_1, \dots, W_l) = 0$.

**B.1. Further Notation for the control of the cumulants.** Here, we gather some notation that we use repeatedly in the proof. For $\alpha \in \mathbb{N}^{n \times p}$ a multiset and $i \in [n]$, we write $\alpha_i$: the $i$-th row of $\alpha$. Similarly, for $j \in [p]$, we write $\alpha_{:j}$ the $j$-th column of $\alpha$. We denote $\mathrm{supp}(\alpha) = \{i \in [n] : \alpha_i \neq 0\}$ and $\mathrm{col}(\alpha) = \{j \in [p] : \alpha_{:j} \neq 0\}$. Then, we denote $\#\alpha = |\mathrm{supp}(\alpha)|$ and $r_\alpha = |\mathrm{col}(\alpha)|$. Finally, we shall write $|\alpha|$ the $l_1$-norm of $\alpha$. Finally, $\alpha!$ stands for $\prod_{ij} \alpha_{ij}$! and, for any real valued matrix $Q$, $Q^\alpha = \prod_{ij} Q_{ij}^{\alpha_{ij}}$. For any finite set $S$, we write $|S|$ its cardinality.
Given a graph $G = (V, E)$, with $V$ the set of nodes and $E$ the set of edges, and $V' \subset V$, we write $G[V']$ the restriction of $G$ to the nodes in $V'$, i.e $G' = (V', E')$ with $E' = V'^2 \cap E$. We write $cc(G)$ the number of connected components of $G$.

## APPENDIX C: PROOF OF THEOREM 3.1

With no loss of generality, we assume in all the proof that $\sigma^2 = 1$. Let $D \in \mathbb{N}$. In the remaining of the proof, we write $x = M_{12}^* = \mathbf{1}_{k_1^*=k_2^*}$. Then, our goal is to lower-bound

$$MMSE_{\leq D} = \inf_{f \in \mathbb{R}_D(Y)} \mathbb{E} \left[ (f(Y) - x)^2 \right],$$

or equivalently, according to (9), to upper-bound $corr_{\leq D}^2$ defined in (10). More precisely, proving Theorem 3.1 is equivalent to proving

$$corr_D^2 \leq \frac{1}{K^2} \left[ 1 + \frac{\zeta}{(1 - \sqrt{\zeta})^3} \right], \quad \text{for} \quad \zeta := \frac{\bar{\Delta}^4}{p} \max \left( D^{18}, \frac{n}{K^2} \right) < 1.$$

The clustering model is a special case of the latent model (1), with

$$Z = k^*, \quad \delta_{ij}(k^*) = 1, \quad \text{and} \quad \theta_{i,j}(k^*) = (k_i^*, j).$$

Combining Proposition 2.1 and Theorem 2.5, we need to upper bound the cumulant, for any decomposition $\alpha = \beta_1 + \dots + \beta_l$, with $|\beta_s| = 2$ for $s = 1, \dots, l$,

$$C_{x, \beta_1, \dots, \beta_l} = \text{Cum} \left( x, \mathbf{1}_{\Omega_{\beta_1}(k^*)}, \dots, \mathbf{1}_{\Omega_{\beta_l}(k^*)} \right),$$

with $\Omega_\beta(k^*) := \{|\{(k_i^*, j) : (i, j) \in \beta\}| = 1\}$. Building on the recursive Bound (18), we derive in Section C.1 the following upper-bound.

**LEMMA C.1.** We recall that $\#\alpha$ stands for the cardinality of the points $i \in [1, n]$ such that $\alpha_i \neq 0$, and that $|\alpha| := \sum_{ij} \alpha_{ij}$. We have

$$(60) \qquad |C_{x, \beta_1, \dots, \beta_l}| \leq |\alpha|^{|\alpha|-2\#\alpha+4} \left(\frac{1}{K}\right)^{\#\alpha-1}.$$

Combining this bound with (55) and counting the number of partitions $\pi \in \mathcal{P}_2(\alpha)$ such that $C_{x, \beta_1(\pi), \dots, \beta_l(\pi)} \neq 0$, we prove in Section C.5 the next upper-bound on $|\kappa_{x,\alpha}|$.

**LEMMA C.2.** Let $\alpha \in \mathbb{N}^{n \times p}$ non-zero. We have the upper bound

$$|\kappa_{x,\alpha}| \leq \left(\frac{1}{K}\right)^{\#\alpha-1} \lambda^{|\alpha|} |\alpha|^{|\alpha|-2\#\alpha+4} |\alpha|^{|\alpha|-\#\alpha-r_{\alpha}+1}.$$

The last stage, is to prune the multiset $\alpha$ for which $\kappa_{x,\alpha} = 0$. Next lemma gives necessary conditions for having $\kappa_{x,\alpha} \neq 0$. For this purpose, it is convenient to introduce a bipartite multigraph $G_\alpha$ on two disjoint sets $U = \{u_1, \dots, u_n\}$ and $V = \{v_1, \dots, v_p\}$ with, for $i, j \in [n] \times [p]$, $\alpha_{ij}$ edges between $u_i$ and $v_j$. We write $G_\alpha^-$ the restriction of $G_\alpha$ to non-isolated points. We denote $U(\alpha)$ the elements of $U$ spanned by $G_\alpha^-$ and $V(\alpha)$ the elements of $V$ spanned by $G_\alpha^-$. We refer to Section C.6 for a proof of this lemma.
LEMMA C.3. Let $\alpha \in \mathbb{N}^{n \times p}$ be non-zero. If $\kappa_{x,\alpha} \neq 0$, then

• $u_1, u_2 \in U(\alpha)$;

• $G_{\alpha}^{-} \cup \{(u_1, u_2)\}$ is connected;

• All the elements of $U(\alpha) \setminus \{u_1, u_2\}$ and $V(\alpha)$ are of degree at least 2.

In particular, we have $\#\alpha \ge 2$, $|\alpha| \ge 2r_{\alpha}$ and $|\alpha| \ge 2\#\alpha - 2$.

REMARK 8. In fact, we can prove that $G_{\alpha}^{-}$ is connected (see [28]), but it is sufficient and more straightforward to prove that $G_{\alpha}^{-} \cup \{(u_1, u_2)\}$ is connected.

We derive from Lemma C.3 the next lemma, which upper-bounds the cardinality of the $\alpha$'s providing non-zero $\kappa_{x,\alpha}$, in terms of $|\alpha|$, $\#\alpha$ and $r_{\alpha} := |\{j \in [1, p] \mid \alpha_j \neq 0\}|$. We refer to Section C.7 for a proof of this lemma.

LEMMA C.4. Given $m \ge 2$, $r \ge 1$, $d \ge \max(2m-2, 2r)$, there exists at most $d^{3(d-r-m+2)}n^{m-2}p^r$ matrices $\alpha \in \mathbb{N}^{n \times p}$ satisfying the conditions of Lemma C.3 with $\#\alpha = m$, $r_{\alpha} = r$ and $|\alpha| = d$.

We now have all the pieces to upper-bound the degree-D correlation $corr_{\le D}^2$. Given $d \ge 1$, we set $\mathcal{D}_d := \{m, r \in [2, d] \times [1, d], d \ge 2m-2, d \ge 2r\}$. We have

$$ 
\begin{aligned}
corr_{\le D}^2 &\le \sum_{\substack{\alpha \in \mathbb{N}^{n \times p} \\ |\alpha| \le D}} \kappa_{x, \alpha}^2 \\
&\le \frac{1}{K^2} + \sum_{d=2}^D \sum_{m, r \in \mathcal{D}_d} p^r n^{m-2} d^{5(d-r-(m-2))} d^{2d-4(m-2)} \lambda^{2d} \left(\frac{1}{K^2}\right)^{m-1} \\
&\le \frac{1}{K^2} + \frac{1}{K^2} \sum_{d=1}^D \sum_{m, r \in \mathcal{D}_d} (D^7 \lambda^2)^d \left(\frac{p}{D^5}\right)^r \left(\frac{n}{K^2 D^9}\right)^{m-2}.
\end{aligned}
$$

Given $d \in [1, D]$ and $m, r \in \mathcal{D}_d$, let us upper-bound $(D^7 \lambda^2)^d \left(\frac{p}{D^5}\right)^r \left(\frac{n}{K^2 D^9}\right)^{m-2}$. First, let us assume that $r \ge m-1$. By definition of $\mathcal{D}_d$, we can assume that $d \ge 2r$. Recall the definition of $\zeta$ in the statement of the theorem. We get

$$ 
\begin{aligned}
(D^7 \lambda^2)^d \left(\frac{p}{D^5}\right)^r \left(\frac{n}{K^2 D^9}\right)^{m-2} &= \left(D^7 \frac{1}{p} \bar{\Delta}^2\right)^{d-2r} \left(\frac{D^9 \bar{\Delta}^4}{p}\right)^{r-(m-2)} \left(\frac{\bar{\Delta}^4 n}{p K^2}\right)^{m-2} \\
&\le \zeta^{\frac{d-2r}{2}} \zeta^{r-(m-2)} \zeta^{m-2} \le \zeta^{\frac{d}{2}}.
\end{aligned}
$$

Now, let us suppose that $r \le m-2$, and let us consider the case $d \ge 2m-2$.

$$ 
\begin{aligned}
(D^7 \lambda^2)^d \left(\frac{p}{D^5}\right)^r \left(\frac{n}{K^2 D^9}\right)^{m-2} &= \left(D^7 \frac{1}{p} \bar{\Delta}^2\right)^{d-2(m-2)} \left(\frac{n D^5}{K^2 p^2} \bar{\Delta}^4\right)^{m-2-r} \\
&\quad \times \left(\bar{\Delta}^4 \frac{n}{K^2 p}\right)^r.
\end{aligned}
$$
It is clear using directly the definition $\zeta = \frac{\bar{\Delta}^4}{p} \max(D^{18}, \frac{n}{K^2})$ that $D^7 \frac{1}{p} \bar{\Delta}^2 \le \sqrt{\zeta}$ and $\bar{\Delta}^4 \frac{n}{K^2 p} \le \zeta$. For the remaining factor $\frac{n D^5}{K^2 p^2} \bar{\Delta}^4$, we use the hypothesis $p \ge D^5$. Thus, $\frac{n D^5}{K^2 p^2} \bar{\Delta}^4 \le \frac{n}{K^2 p} \bar{\Delta}^4 \le \zeta$. Hence,

$$ (D^9 \lambda^2)^d \left(\frac{p}{D^7}\right)^r \left(\frac{n}{K^2 D^{11}}\right)^{m-2} \le \zeta^{\frac{d-2(m-2)}{2}} \zeta^{m-2-r} \zeta^r \le \zeta^{\frac{d}{2}}. $$

Hence, for all $d \in [1, D]$ and $m, r \in \mathcal{D}_d$, we have $(D^9 \lambda^2)^d \left(\frac{p}{D^7}\right)^r \left(\frac{n}{K^2 16 D^{11}}\right)^{m-2} \le \zeta^{\frac{d}{2}}$. Combining this with $|\mathcal{D}_d| \le \frac{d(d-1)}{2}$ leads to

$$ \begin{aligned} \mathrm{corr}^2_{\le D} &\le \frac{1}{K^2} + \frac{1}{K^2} \sum_{d=2}^{D} \frac{d(d-1)}{2} \zeta^{d/2} \\ &\le \frac{1}{K^2} \left[ 1 + \frac{\zeta}{(1 - \sqrt{\zeta})^3} \right]. \end{aligned} $$

This concludes the proof of the theorem.

**C.1. Proof of Lemma C.1.** Let $\beta_1, \dots, \beta_l$ such that $|\beta_s| = 2$ for $s \in [l]$ and such that $\beta_1 + \dots + \beta_l = \alpha$. We seek to upper-bound

$$ C_{x, \beta_1, \dots, \beta_l} = \mathrm{Cum} \left( x, \mathbf{1}_{\Omega_{\beta_1}(k^*)}, \dots, \mathbf{1}_{\Omega_{\beta_l}(k^*)} \right), $$

with $\Omega_{\beta}(k^*) := \{|\{(k_i^*, j) : (i, j) \in \beta\}| = 1\}$. For $C_{x, \beta_1, \dots, \beta_l}$ to be non-zero, it is necessary that, for $s \in [l]$, $\Omega_{\beta_s}(k^*)$ is an event of positive probability. This condition implies that $\beta_s$ must be contained in a single column of $\alpha$, which we denote $j_s$. We write $\beta_s = \{(i_s, j_s); (i'_s, j'_s)\}$, for $s \in [l]$. We also take the convention $i_0 = 1, i'_0 = 2$, and $j_0 = 0$. We then have

$$ C_{x, \beta_1, \dots, \beta_l} = \mathrm{Cum} \left( \mathbf{1} \left\{ k_{i_s}^* = k_{i'_s}^* \right\} \right)_{s \in [0, l]}. $$

For $S \subseteq [l]$, we denote $\beta[S] = \{\beta_s, s \in S\}$ and $\alpha_S = \sum_{s \in S} \beta_s$. Applying the recursion formula 18, we deduce that, for all $S \subseteq [l]$,

$$ \begin{aligned} |C_{x, \beta[S]}| &\le \left| \mathbb{E} \left[ \prod_{s \in \{0\} \cup S} \mathbf{1} \left\{ k_{i_s}^* = k_{i'_s}^* \right\} \right] \right| + \sum_{S' \subsetneq S} |C_{x, \beta[S']}| \left| \mathbb{E} \left[ \prod_{s \in S \setminus S'} \mathbf{1} \left\{ k_{i_s}^* = k_{i'_s}^* \right\} \right] \right| \\ (61) \qquad \le \mathbb{P} \left[ \forall s \in \{0\} \cup S, \ k_{i_s}^* = k_{i'_s}^* \right] + \sum_{S' \subsetneq S} |C_{x, \beta[S']}| \mathbb{P} \left[ \forall s \in S \setminus S', \ k_{i_s}^* = k_{i'_s}^* \right]. \end{aligned} $$

Let us compute, for any subset $R \subseteq [0, l]$, the quantity $\mathbb{P}[\forall s \in R, k_{i_s}^* = k_{i'_s}^*]$. To do so, let us define $\mathcal{V}$ the graph on $[0, l]$ defined by; for $s, s' \ge 0$, there is an edge between $s$ and $s'$ if and only if $\{i_s, i'_s\} \cap \{i_{s'}, i'_{s'}\} \ne \emptyset$. Let $\mathcal{V}[R]$ denote the restriction of $\mathcal{V}$ to $R$ and $cc(\mathcal{V}[R])$ the number of connected components of this graph. Let $cc_1, \dots, cc_{q^*}$ be the connected components of $\mathcal{V}[R]$, with $q^* = cc(\mathcal{V}[R])$. For $q \in [q^*]$, let $i_q$ be any element of $\cup_{s \in cc_q} \{i_s, i'_s\}$. Having for all $s \in R$, $k_{i_s}^* = k_{i'_s}^*$ is equivalent to having, for all $q \in [q^*]$ and for all $i \in \cup_{s \in cc_{q'}} \{i_s, i'_s\}$, $k_i^* = k_{i'_q}^*$. Such an event occurs with probability
$$
\begin{align*}
\mathbb{P}[\forall q \in [q^*], \forall i \in \cup_{s \in cc_q} \{i_s, i'_s\}, k_i^* = k_{i_q}^*] &= \prod_{q \in [q^*]} \mathbb{P}[\forall i \in \cup_{s \in cc_q} \{i_s, i'_s\}, k_i^* = k_{i_q}^*] \\
&= \prod_{q \in [q^*]} \left(\frac{1}{K}\right)^{|\cup_{s \in cc_q} \{i_s, i'_s\}|-1}.
\end{align*}
$$

By definition of the graph $\mathcal{V}$, we have $\sum_{q \le q^*} |\cup_{s \in cc_q} \{i_s, i'_s\}| = |\cup_{s \in R} \{i_s, i'_s\}|$. If $R$ does not contain $0$, then $|\cup_{s \in R} \{i_s, i'_s\}| = \#\alpha_R$, with $\alpha_R = \sum_{s \in R} \beta_s$. If $R$ contains $0$, $|\cup_{s \in R} \{i_s, i'_s\}| = |\text{supp}(\alpha_R \setminus \{0\}) \cup \{1, 2\}|$. Plugging this in (61) leads to

$$
(62) \quad |C_{x,\beta[S]}| \le \left(\frac{1}{K}\right)^{|\text{supp}(\alpha_S) \cup \{1,2\}| - \text{cc}(\mathcal{V}[S])} + \sum_{S' \subsetneq S} |C_{x,\beta[S']}| \left(\frac{1}{K}\right)^{\#\alpha_{S\setminus S'} - \text{cc}(\mathcal{V}[S\setminus S'])} .
$$

The next lemma prunes the subsets $S \subseteq [l]$ such that $C_{x,\beta[S]} \neq 0$. In the following, we denote $S([l])$ the set of all subsets $S \subseteq [l]$ satisfying;

1. $\mathcal{V}[\{0\} \cup S]$ is connected;

2. If $S \neq \emptyset$, then, for all $i \in \cup_{\{0\} \cup S} \{i_s, i'_s\}$, there exists $s \neq s' \in \{0\} \cup S$ such that $i \in \{i_s, i'_s\}$ and $i \in \{i_{s'}, i'_{s'}\}$. In particular, $1, 2 \in \text{supp}(\alpha_S)$.

LEMMA C.5. Let $S \subseteq [l]$ such that $C_{x,\beta[S]} \neq 0$. Then $S \in S([l])$

PROOF OF LEMMA C.5. Let us first suppose that $\mathcal{V}[\{0\} \cup S]$ is not connected and let us prove that $C_{x,\beta[S]} = 0$. Let $S_1$ and $S_2$ be a partition of $\{0\} \cup S$ with no edges connecting them. Then, $(k_i^*)_{i \in \cup_{s \in S_1} \{i_s, i'_s\}}$ is independent from $(k_i^*)_{i \in \cup_{s \in S_2} \{i_s, i'_s\}}$ and so $(\mathbf{1}\{k_{i_s}^* = k_{i'_s}^*\})_{s \in S_1}$ is independent from $(\mathbf{1}\{k_{i_s}^* = k_{i'_s}^*\})_{s \in S_2}$. Lemma B.2 then implies that $C_{x,\beta[S]} = 0$.

Now, suppose $S \neq \emptyset$ and suppose that there exists $\underline{i} \in \cup_{s \in \{0\} \cup S} \{i_s, i'_s\}$ such that there exists only one $s_0 \in \{0\} \cup S$ such that $\underline{i} \in \{i_{s_0}, i'_{s_0}\}$. We suppose by symmetry that $\underline{i} = i_{s_0}$. Conditionally on $(\mathbf{1}\{k_{i_s}^* = k_{i'_s}^*\})_{s \in (\{0\} \cup S) \setminus \{s_0\}} \cup \{k_{i'_{s_0}}^*\}$, the variable $\mathbf{1}\{k_{i_{s_0}}^* = k_{i'_{s_0}}^*\}$ is either a Bernoulli of parameter $\frac{1}{K}$ if $i_{s_0} \neq i'_{s_0}$, either deterministic and equal to 1 if $i_{s_0} = i'_{s_0}$. A fortiori, $\mathbf{1}\{k_{i_{s_0}}^* = k_{i'_{s_0}}^*\}$ is independent from $(\mathbf{1}\{k_{i_s}^* = k_{i'_s}^*\})_{s \in (\{0\} \cup S) \setminus \{s_0\}}$. Lemma B.2 again implies $C_{x,\beta[S]} = 0$.

□

Pruning the other terms in (62) leads us to, for all $S \in S([l])$,

$$
(63) \quad |C_{x,\beta[S]}| \le \left(\frac{1}{K}\right)^{\#\alpha_S - 1} + \sum_{\substack{S' \subsetneq S \\ S' \in S([l])}} |C_{x,\beta[S']}| \left(\frac{1}{K}\right)^{\#\alpha_{S\setminus S'} - \text{cc}(\mathcal{V}[S\setminus S'])} .
$$
In the following, let us define recursively a function $f$ on $S([l])$ satisfying, for all $S \in S([l])$,

$$ (64) \qquad f(S) = 1 + \sum_{\substack{S' \subsetneq S \\ S' \in S([l])}} f(S'), $$

with $f(\emptyset) = 1$. The next lemma upper-bounds, for $S \in S([l])$, $|C_{x,\beta[S]}|$ with respect to $f(S)$. We refer to Section C.2 for a proof of this lemma.

**LEMMA C.6.** For all $S \in S([l])$, we have $|C_{x,\beta[S]}| \le (\frac{1}{K})^{\#\alpha_S - 1} f(S)$.

It remains to upper-bound $f(S)$ for all $S \in S([l])$. We postpone to Section C.4 the computation leading to next lemma.

**LEMMA C.7.** For all $S \in S([l])$ with $S \ne \emptyset$, we have $f(S) \le |\alpha|^{\alpha_S - 2\#\alpha_S + 4}$.

Plugging Lemma C.7 in Lemma C.6 leads us to

$$ |C_{x,\beta_1, \dots, \beta_t}| \le |\alpha|^{\alpha|\alpha| - 2\#\alpha + 4} \left(\frac{1}{K}\right)^{\#\alpha - 1}, $$

which concludes the proof of the lemma.

**C.2.** *Proof of Lemma C.6.* Let us prove by induction that, for all $S \in S([l])$, $|C_{x,\beta[S]}| \le (\frac{1}{K})^{\#\alpha_S - 1} f(S)$. The initialization is straightforward since $C_x = \kappa(\mathbf{1}\{k_1^* = k_2^*\}) = \frac{1}{K}$ and $\alpha_\emptyset = 0$.

For the induction, let $S \in S([l])$ and let us suppose that the result holds for all $S' \in S([l])$ with $S' \subsetneq S$. Applying Inequality (63) to $S$ together with the induction hypothesis leads to

$$ \begin{aligned} |C_{x,\beta[S]}| &\le \left(\frac{1}{K}\right)^{\#\alpha_S - 1} + \sum_{\substack{S' \subsetneq S \\ S' \in S([l])}} |C_{x,\beta[S']}| \left(\frac{1}{K}\right)^{\#\alpha_{S\setminus S'} - cc(V[S\setminus S'])} \\ &\le \left(\frac{1}{K}\right)^{\#\alpha_S - 1} + \frac{1}{K} \left(\frac{1}{K}\right)^{\#\alpha_S - cc(V[S])} + \\ &\qquad + \sum_{\substack{S' \subsetneq S \\ \emptyset \ne S' \in S([l])}} f(S') \left(\frac{1}{K}\right)^{\#\alpha_{S'} - 1} \left(\frac{1}{K}\right)^{\#\alpha_{S\setminus S'} - cc(V[S\setminus S'])} \\ &\le \left(\frac{1}{K}\right)^{\#\alpha_S - 1} + \sum_{\substack{S' \subsetneq S \\ S' \in S([l])}} f(S') \left(\frac{1}{K}\right)^{\#\alpha_{S'} - 1 + \#\alpha_{S\setminus S'} - cc(V[S\setminus S'])} . \end{aligned} $$

In the last line, for the term corresponding to $S' = \emptyset$, we used the fact that $cc(V[S]) \le cc(V[S \cup \{0\}]) + 1 \le 2$, since $V[S \cup \{0\}]$ is assumed to be connected. We deduced from that $\frac{1}{K} (\frac{1}{K})^{\#\alpha_S - cc(V[S])} \le (\frac{1}{K})^{\#\alpha_S - 1}$.
The next lemma uses the connectivity of the graph $\mathcal{V}[\{0\} \cup S]$ in order to lower-bound the other exponents in the above inequality.

**LEMMA C.8.** For all $\emptyset \neq S' \subsetneq S$ with $S, S' \in \mathcal{S}([l])$,

$$ \#\alpha_{S'} - 1 + \#\alpha_{S \setminus S'} - cc(\mathcal{V}[S \setminus S']) \geq \#\alpha_S - 1 . $$

Applying Lemma C.8 leads to

$$ |C_{x,\beta[S]}| \leq \left(\frac{1}{K}\right)^{\#\alpha_S - 1} \left(1 + \sum_{\substack{S' \subsetneq S \\ S' \in \mathcal{S}([l])}} f(S')\right) = \left(\frac{1}{K}\right)^{\#\alpha_S - 1} f(S), $$

which concludes the induction.

**C.3. Proof of Lemma C.8.** For any subset $R \subseteq [l]$, we write $\alpha_R = \sum_{s \in R} \beta_s$.

Let $\emptyset \neq S' \subsetneq S$ with $S, S' \in \mathcal{S}([l])$. Let $q^* = cc(\mathcal{V}[S \setminus S'])$ and let us write $cc_1, \dots, cc_{q^*}$ those connected components. Since $\mathcal{V}[S \cup \{0\}]$ is connected, we deduce that, for all $q \leq q^*$, $cc_q$ is connected to $S' \cup \{0\}$ in $\mathcal{V}[S \cup \{0\}]$. This implies that, for all $q \in [q^*]$, $\#\alpha_{cc_q} \geq 1 + |\text{supp}(\alpha_{cc_q}) \setminus \text{supp}(\alpha_{S'})|$. Hence, we have

$$ \begin{aligned} \#\alpha_{S'} - 1 + \#\alpha_{S \setminus S'} - cc(\mathcal{V}[S \setminus S']) &= \#\alpha_{S'} - 1 + \sum_{q \in [q^*]} (\#\alpha_{cc_q} - 1) \\ &\geq \#\alpha_{S'} - 1 + \sum_{q \in [q^*]} |\text{supp}(\alpha_{cc_q}) \setminus \text{supp}(\alpha_{S'})| \\ &\geq \#\alpha_S - 1, \end{aligned} $$

which concludes the proof of the lemma.

**C.4. Proof of Lemma C.7.** We shall prove, by induction, that for all $S \in \mathcal{S}([l])$,

$$ (65) \qquad f(S) \leq |\alpha|^{|\alpha_S| - 2|\text{supp}(\alpha_S) \cup \{1,2\}| + 4} . $$

In fact, the bound (65) implies the desired result. Indeed, for $S \neq \emptyset$, we deduce from the definition of $\mathcal{S}([l])$ that $1, 2 \in \text{supp}(\alpha_S)$. This implies that $|\text{supp}(\alpha_S \cup \{1,2\})| = \#\alpha_S$. The case $S = \emptyset$ is straightforward as $f(\emptyset) = 1$.

Hence, we only need to prove (65). The initialization is trivial since $f(\emptyset) = 1 = 0^0$ and $\alpha_\emptyset = 0$. Let us take $S \in \mathcal{S}([l])$ and let us suppose that the result holds for all $S' \in \mathcal{S}([l])$ with $S' \subsetneq S$. For all $s \in S$, let $S^*(s)$ be the maximal (with respect to the inclusion) element of $\mathcal{S}([l])$ which is included in $S \setminus \{s\}$. The existence of such an element is ensured by the fact that the set of elements $S' \in \mathcal{S}([l])$ with $S' \subseteq S \setminus \{s\}$ is not empty (it contains $\emptyset$) and is stable by union. We have
$$
\begin{align*}
f(S) &= 1 + \sum_{\substack{S' \subsetneq S \\ S' \in \mathcal{S}([l])}} f(S') \\
&\le 1 + \sum_{s \in S} \sum_{\substack{S' \subsetneq S^*(s) \\ S' \in \mathcal{S}([l])}} f(S') \\
&\le 1 + \sum_{s \in S} [2f(S^*(s)) - 1] \\
&\le 2 \sum_{s \in S} f(S^*(s)),
\end{align*}
$$

where we used the recursive definition of f in the third line. Applying the induction hypoth-
esis leads us to

$$
(66) \qquad f(S) \le 2 \sum_{s \in S} |\alpha|^{\alpha_{S^*(s)}} - 2|\text{supp}(\alpha_{S^*(s)} \cup \{1,2\})| + 4 .
$$

Let $s \in S$ and let $i \in (\cup_{s' \in S} \{i_{s'}, i'_{s'}\}) \setminus (\cup_{s' \in S^*(s) \cup \{0\}} \{i_{s'}, i'_{s'}\})$. Since $S$ belong to $\mathcal{S}([l])$ and by definition of that collection, we know that there must exist at least two different $s_1, s_2 \in S \setminus (S^*(s) \cup \{0\})$ such that $i \in \text{supp}(\beta_{s_1})$ and $i \in \text{supp}(\beta_{s_2})$. And, from the connectivity of the graph $\mathcal{V}$, we know that there exists $i \in (\text{supp}(\alpha_{S \setminus S^*(s)}) \cup \{1,2\}) \cap (\text{supp}(\alpha_{S^*(s)}) \cup \{1,2\})$. We deduce that

$$
|\alpha_S| \geq |\alpha_{S^*(s)}| + 2 \left| \left( \cup_{s' \in S} \{i_{s'}, i'_{s'}\} \right) \setminus \left( \cup_{s' \in S^*(s) \cup \{0\}} \{i_{s'}, i'_{s'}\} \right) \right| + 1 .
$$

We deduce that

$$
|\alpha_{S^*(s)}| - 2|\text{supp}(\alpha_{S^*(s)}) \cup \{1,2\}| + 4 \le |\alpha_S| - 2|\text{supp}(\alpha_S \cup \{1,2\})| - 1 + 4 .
$$

Coming back to (66), we get

$$
f(S) \le \frac{2|S|}{|\alpha|} |\alpha|^{|\alpha_S|-2|\text{supp}(\alpha_S \cup \{1,2\})|+4} \le |\alpha|^{|\alpha_S|-2|\text{supp}(\alpha_S \cup \{1,2\})|+4} ,
$$

since, for $S \in \mathcal{S}([l])$, $|\alpha| \le 2|S|$. We have proved (65).

**C.5. Proof of Lemma C.2.** To prove Lemma C.2 we merely need to upper-bound the num-
ber of partitions $\pi = \pi_1, \dots, \pi_l \in \mathcal{P}_2(\alpha)$, satisfying $C_{x,\beta_1(\pi)}, \dots, \beta_l(\pi) \neq 0$, where $\beta_s(\pi)$ counts
the number of copies of $(i,j)$ in $\pi_s$. For such a partition, we have $l = \lfloor \frac{|\alpha|}{2} \rfloor$, and we need that all
groups $\pi_s$ must be contained in a single column of $\alpha$. Hence, we only need to upper-bound
the number of partition of each multiset $\alpha_{:j}$, for $j \in \text{col}(\alpha)$, into groups of size 2.

For $j \in \text{col}(\alpha)$, the number of partitions of the multiset $\alpha_{:j}$ into pairings is at most $|\alpha_{:j}|^{|\alpha_{:j}|/2-1}$. We deduce that the number of satisfying partitions of $\alpha$ in pairings is at most $|\alpha|^{|\alpha|/2-r_{\alpha}}$.

Lemma C.5 also implies that for all $i \in \text{supp}(\alpha) \setminus \{1,2\}$, $|\alpha_i| \ge 2$. We deduce that $|\alpha| \ge 2^{\#\alpha} - 2$ and so $|\alpha|^{\alpha|/2-r_\alpha} \le |\alpha|^{\alpha|}-^{\#\alpha-r_\alpha+1}$. Combining Lemma C.1 and (55) leads us to

$$
|\kappa_{x,\alpha}| \le \lambda^{|\alpha|} \left(\frac{1}{K}\right)^{\#\alpha - 1} |\alpha|^{\alpha|} - 2^{\#\alpha + 4} |\alpha|^{\alpha|} - \#\alpha - r_{\alpha} + 1,
$$

which concludes the proof of Lemma C.1.
**C.6.** *Proof of Lemma C.3.* Let $\alpha \neq 0$. Let us prove that if $\mathcal{G}_\alpha^-$ does not satisfy any of the three conditions of Lemma C.3, then $\kappa_{x,\alpha} = 0$.

Let us first suppose that either $u_1 \notin U(\alpha)$ or $u_2 \notin U(\alpha)$. Then, conditionally on $(X_{ij})_{ij \in \alpha}$, $x$ is a Bernoulli of parameter $\frac{1}{K}$. Thus, $x$ is independent from $(X_{ij})_{ij \in \alpha}$. We conclude with Lemma B.2 that $\kappa_{x,\alpha} = 0$.

Let us suppose that $\mathcal{G}_\alpha^- \cup \{(u_1, u_2)\}$ is not connected. Recall Theorem 2.5. For proving that $\kappa_{x,\alpha} = 0$, it is sufficient to prove that, for all decomposition $\beta_1 + \dots + \beta_l = \alpha$, with $\beta_s = \{(i_s, j_s); (i'_s, j'_s)\}$, we have $C_{x,\beta_1, \dots, \beta_l} = 0$. For such a decomposition to be non-zero, we need that the graph $\mathcal{V}[\{0\} \cup [l]]$ defined in Section C.1 is connected –see Lemma C.5. This directly implies that $\mathcal{G}_\alpha^- \cup \{(u_1, u_2)\}$ is connected. So, if $\mathcal{G}_\alpha^- \cup \{(u_1, u_2)\}$ is not connected, all those decompositions satisfy $C_{x,\beta_1, \dots, \beta_l} = 0$ and we deduce $\kappa_{x,\alpha} = 0$.

It remains to prove that if a node in $U(\alpha) \setminus \{u_1, u_2\}$ or $V(\alpha)$ is of degree 1, then $\kappa_{x,\alpha} = 0$. Let us first suppose that there exists $v_{j_0} \in V(\alpha)$ of degree 1. $(x, (X_{ij})_{ij \in \alpha})$ has the same law as $(x, (X_{ij}(-1)^{j=j_0}))$ and so $\kappa_{x,\alpha} = \kappa(x, (X_{ij}(-1)^{j=j_0})) = -\kappa(x, (X_{ij})) = -\kappa_{x,\alpha}$. Hence, $\kappa_{x,\alpha} = 0$.

Let us now suppose that there exists a vertex $u_{i_0} \in U(\alpha) \setminus \{1, 2\}$ which is of degree 1. As previously, we know from Theorem 2.5 that for proving that $\kappa_{x,\alpha} = 0$, it is sufficient to prove that, for all decomposition $\alpha = \beta_1 + \dots + \beta_l$ with $\beta_s = \{(i_s, j_s); (i'_s, j'_s)\}$, we have $C_{x,\beta_1, \dots, \beta_l} = 0$. Let $\beta_1, \dots, \beta_l$ be such a decomposition and let $s_0 \in [l]$ such that $i_0 \in \{i_{s_0}, i'_{s_0}\}$. Since $u_{i_0}$ is of degree at most 1, it is clear that $i_0 \notin \cup_{s \neq s_0} \{i_s, i'_{s}\}$. Thus, $1\{k_{i_{s_0}}^* = k_{i'_{s_0}}^*\}$ is independent from $\{x\} \cup (1\{k_{i_{s_0}}^* = k_{i'_{s_0}}^*\})_{s \neq s_0}$. We deduce from lemma B.2 that $C_{x,\beta_1, \dots, \beta_l} = 0$. This being true for all decomposition, we conclude $\kappa_{x,\alpha} = 0$.

**C.7.** *Proof of Lemma C.4.* We adapt the proof of Lemma 5.5 of [68] to the case of bipartite multigraphs. We remark first that counting the matrices $\alpha$ is equivalent to counting the bipartite multigraphs $\mathcal{G}_\alpha$. Let us first construct the graphs $\mathcal{G}_\alpha$ with some basic operations. We will then upper-bound the number of graphs by counting the operations that are needed to construct all the graphs. In the following, for $G$ a bipartite multigraph of $U \times V$, we denote $G^-$ the graph obtained after removing all the isolated nodes.

In order to construct a bipartite multigraph $G$ of $U \times V$ such that $G^-$ satisfies the conditions of Lemma C.3, we start with two isolated vertices $u_1$ and $u_2$. Then, recursively, we are allowed to add either a "path" or a "lollipop". Let us precise what these two operations on graphs correspond to:

* For adding a "path", we choose $l > 0$ and two existing nodes $w^{(0)}, w^{(l+1)}$ (not necessarily distinct) of $G^-$. Then, we choose distinct $w^{(1)}, \dots, w^{(t)} \in U \cup V$ (with the constraint that, for $l' \in [0, l]$, if $w_{(l')'} \in U$ then $w_{(l'+1)'} \in V$ and conversely) which are not nodes of $G^-$ and we add the edges $((w^{(l')}, w^{(l'+1)})_{l' \in [0,l]})$ to $G$. We remark that all the new nodes added to $G^-$ are of degree 2,

* For constructing a "lollipop", we choose $w^{(0)}$ an existing node of $G^-$. We choose distinct $w^{(1)}, \dots, w^{(l)} \in U \cup V$ (still with the constraint that, for $l' \in [0, l-1]$, if $w_{(l')'} \in U$ then $w_{(l'+1)'} \in V$ and conversely) which are not nodes of $G^-$. We then add to $G$ the edges $((w^{(l')}, w^{(l'+1)})_{l' \in [0,l-1]})$. Then, we choose $l' \in [l-1]$ and we add the edge $(w^{(l)}, w^{(l')})$,
with the constraint that $(w^{(l)}, w^{(l')}) \in (U \times V) \cup (V \times U)$. We have added nodes of degree 2 except one node of degree 3 (which is $w^{(l')}$).

We postpone to Section C.8 the proof of the next lemma, which states that this construction of graphs is surjective.

**LEMMA C.9.** *All graph G, with $G^-$ satisfying the conditions of Lemma C.3, can be obtained by a finite number of operations "path" or "lollipop".*

Now, suppose that a graph $G_\alpha^-$ has been produced by $T$ operations "path" or "lollipop". Let $l_t$ denote the number of vertices added at step $t$. The total number $|\alpha|$ of multi-edges satisfies $|\alpha| = \sum_t (l_t + 1)$ and the total number of vertices $r_\alpha + |\alpha|$ satisfies $r_\alpha + |\alpha| - 2 = \sum_t l_t$. This implies that $T = |\alpha| - |\alpha| - r_\alpha + 2 = d - m - r + 2$. Then, since for all $t \in [T]$, we have necessarily $l_t \in [1, d]$, for obtaining all the possible graphs, the number of possibilities for choosing the $l_t$'s is at most $d^{d-m-r+2}$. At each step, there are at most $d^2$ possibilities for choosing the existing vertices (counting the future existing vertex when we add a "lollipop"). Finally, the new vertices must be chosen either in $U \setminus \{1, 2\}$ or $V$ depending on where the existing edges are. It is clear that, in total, the number of nodes that we need to choose in $U$ is $m-2$ and the number of nodes that we need to choose in $V$ is $r$. When we choose a new node, the fact that it belongs to $U$ or $V$ is entirely determined by the previous choices of nodes. The final count is at most

$$d^3(d-r-m+2)n^{m-2}p^r,$$

which concludes the proof of the lemma.

**C.8. Proof of Lemma C.9.** Let $G$ a bipartite multigraph of $U \times V$ such that $G^-$ satisfies the conditions of Lemma C.3, which are:

1. $u_1, u_2$ are nodes of $G^-$,

2. $G^- \cup \{(u_1, u_2)\}$ is connected;

3. All the nodes of $G^-$, except $u_1$ and $u_2$, are of degree at least 2. Together with the first point, this implies that all the nodes of $G^- \cup \{(u_1, u_2)\}$ are of degree at least 2.

Let us prove that $G^-$ can be obtained with a finite number of operations "path" or "lollipop". To do so, we deconstruct the graph $G$ by removing paths and lollipops. We write $G_0 = G$ and we construct recursively a sequence of subgraphs of $G$ as follows.

Suppose that we are given a graph $G_t$, for $t \ge 0$. If it exists, choose an edge $e$ of $G_t^-$ whose absence does not disconnect the graph $G_t^- \cup \{(u_1, u_2)\}$. Then, let $P$ be the maximal path included in $G_t^-$ containing $e$ and such that all the nodes inside this path are of degree 2 and are not $u_1$ or $u_2$. We distinguish two cases:

* If the extremities of this path are distinct, or if they are not distinct but are a node of degree at least 4 (or equal either to $u_1$ or $u_2$), we remove all the edges of the path to obtain the graph $G_{t+1}^-$. This corresponds to removing a "path".

* If both extremities of this path are a same node of degree 3 which is not in $\{u_1, u_2\}$, then remove also all the edges of this path. There remains an edge $e'$ connecting the extremity to the rest of the graph. We consider the maximum path containing $e'$ such that all the nodes are of degree 2 and are not $u_1$ or $u_2$. We also remove all the edges of this path. This corresponds to removing a "lollipop".
We stop at the step $T$ which corresponds to the moment where there is no edge deconnecting $G_T^- \cup \{(u_1, u_2)\}$. To conclude the proof of the lemma, it remains to prove that $G_T$ has no edge -which is the starting point of the construction of the graphs above-. First, we define the set $\mathcal{H}$ of bipartite multigraphs satisfying, for $G \in \mathcal{H}$;

1. $G^- \cup \{(u_1, u_2)\}$ is connected;

2. All the nodes of $G^-$, except $u_1$ and $u_2$, are of degree at least 2.

It is clear that $G_0 \in \mathcal{H}$, since $G_0$ satisfies the conditions of Lemma C.3. Lemma C.10 below implies that, if $G_t \in \mathcal{H}$, then $G_{t-1}$ belongs to $\mathcal{H}$.

**LEMMA C.10.** Let $G \in \mathcal{H}$ be a non empty graph. Let us remove either a "lollipop" or a "path" from $G$ with the scheme described above. Then, the obtained graph $G'$ also belongs to $\mathcal{H}$.

In particular, $G_T \in \mathcal{H}$. Let us suppose that $G_T$ has an edge and let us find a contradiction. If $G_T$ only has edges between $u_1$ and $u_2$, then removing one of these edges does not disconnect $G_T^- \cup \{(u_1, u_2)\}$ and this leads to a contradiction.

Otherwise, one can extract from $G_T^- \cup \{(u_1, u_2)\}$ a spanning tree with $u_1$ as the root. We can suppose that there exists at least one leaf of this tree which is not $u_2$. This leaf is of degree at least 2 for $G_T^- \cup \{(u_1, u_2)\}$ but of degree 1 for the spanning tree. Removing an edge which is not in the tree does not disconnect $G_T^- \cup \{(u_1, u_2)\}$. This contradicts the fact that $T$ is the final step. All in all, we have shown that $G_T$ does not have any edge, which concludes the proof of the lemma.

**C.9. Proof of Lemma C.10.** Let $G \in \mathcal{H}$. Let $e$ an edge that does not disconnect $G^- \cup \{(u_1, u_2)\}$. Let $P$ be the maximal path included in $G^-$ containing $e$ and such that all the nodes inside $P$ are of degree 2 and are not $u_1$ or $u_2$.

We first suppose that the extremities of this path are distinct, or that they are not distinct but are a node of degree at least 4 or that they are equal to $u_1$ or $u_2$. Then, the obtained graph $G'$ is $G \setminus P$. Let us prove that $G' \in \mathcal{H}$. There are two things to check:

1. Let us prove that $G'^- \cup \{(u_1, u_2)\}$ is connected. Since the absence of $e$ does not disconnect $G^- \cup \{(u_1, u_2)\}$, so does the absence of $P$ and we get that $G'^- \cup \{(u_1, u_2)\}$ is connected,

2. Let us prove that all the nodes of $G'^- \cup \{(u_1, u_2)\}$ except $u_1$ and $u_2$ are of degree at least 2. The nodes along the path $P$ are not nodes of $G'^- \cup \{(u_1, u_2)\}$. The nodes that are not extremities of $P$ have the same degree for $G'^- \cup \{(u_1, u_2)\}$ than for $G^- \cup \{(u_1, u_2)\}$. It remains to check that the extremities of $P$ which are not $u_1$ or $u_2$ are of degree at least 2 for $G'^- \cup \{(u_1, u_2)\}$. Let $w, w'$ be those extremities, and let us suppose that $w \notin \{u_1, u_2\}$. If $w \neq w'$, then the degree of $w$ decreases by 1 and since, by maximality of $P$, it was different from 2 for $G^- \cup \{(u_1, u_2)\}$, it is at least 2 for $G'^- \cup \{(u_1, u_2)\}$. If $w = w'$ then the degree of $w$ decreases by 2 and since it was larger than 4 for $G^- \cup \{(u_1, u_2)\}$, it is at least 2 for $G'^- \cup \{(u_1, u_2)\}$.

Thus, we have proved that $G' \in \mathcal{H}$.

We now suppose that the two extremities of the path are the same node $w$, different from $u_1$ or $u_2$, and is of degree 3. Let $e'$ the unique edge of $G \setminus P$ such $w$ as an extremity of $e'$ and
let $P'$ denote the maximal path containing $e'$ and that only travels through nodes of degree 2 which are not in $\{u_1, u_2\}$. Then, using the exact same arguments as above, it is clear that $G \setminus (P \cup P') \in \mathcal{H}$. This concludes the proof of the lemma.

## APPENDIX D: PROOF OF THEOREM 4.1

Without loss of generality, we assume through the proof that $\sigma^2 = 1$. Let $D \in \mathbb{N}$. We recall the assumption

$$ (67) \qquad \zeta := \frac{\bar{\Delta}^4}{\rho^2 p^2} \max(D^{14}, D^7 n, D^7 \rho^2 p, \rho^2 p \frac{n}{K^2}) < 1 . $$

Again, as in the proof of Theorem 3.1 in Section C, the expression of the $MMSE_{\le D}$ can be reduced to

$$ MMSE_{\le D} = \inf_{f \in R_D[Y]} \mathbb{E} \left[ (f(Y) - x)^2 \right] = \frac{1}{K} - \text{corr}_{\le D}^2 , $$

with $x = \mathbf{1}_{k_1^*=k_2^*}$ and $\text{corr}_{\le D}^2$ being defined by Equation (10). We shall again upper-bound $\text{corr}_{\le D}^2$ using Proposition 2.1, which states that

$$ \text{corr}_{\le D}^2 \le \sum_{\substack{\alpha \in \mathbb{N}^{n \times p} \\ |\alpha| \le D}} \frac{\kappa_{x,\alpha}^2}{\alpha!} , $$

with $\kappa_{x,\alpha} = \text{Cum}(x, (X_{ij})_{ij \in \alpha})$. Here, $\alpha$ is seen as a multiset of $[n] \times [p]$, i.e $(X_{ij})_{ij \in \alpha}$ contains $\alpha_{ij}$ copies of $X_{ij}$. The sparse clustering model is a special case of the latent model (1), with

$$ Z = (k^*, z, \varepsilon), \quad \delta_{ij}(Z) = z_j \varepsilon_i, \quad \text{and} \quad \theta_{i,j}(Z) = (k_i^*, j) . $$

Combining Proposition 2.1 and Theorem 2.5, we need to upper bound, for any decomposition $\beta_1 + \dots + \beta_l = \alpha$, with $|\beta_s| = 2$, the cumulant

$$ C_{x, \beta_1, \dots, \beta_l} = \text{Cum} \left( x, \prod_{(ij) \in \beta_1} \varepsilon_i \mathbf{1}_{\Omega_{\beta_1}(k^*)}, \dots, \prod_{(ij) \in \beta_1} \varepsilon_i \mathbf{1}_{\Omega_{\beta_l}(k^*)} \right), $$

$$ \text{with } \Omega_{\beta}(k^*) := \left\{ \left| \left\{ (k_i^*, j) : (i, j) \in \beta \right\} \right| = 1 \right\} \cap \left\{ \forall j \in \text{col}(\beta), z_j = 1 \right\}. $$

Building on the recursive Bound (18), we derive in Section C.1 the following upper-bound.

**LEMMA D.1.** We recall that $\#\alpha$ stands for the number of indices $i \in [1, n]$ such that $\alpha_i \neq 0$, that $r_\alpha$ stands for the number of indices $j \in [1, p]$ such that $\alpha_{i,j} \neq 0$ and that $|\alpha| := \sum_{ij} \alpha_{ij}$. We have

$$ C_{x, \beta_1, \dots, \beta_l} \le \rho^{r_\alpha} |\alpha|^{|\alpha|-r_\alpha-\#\alpha+2} \min \left( \left( \frac{1}{K} \right)^{\#\alpha+r_\alpha-\frac{|\alpha|}{2}-1}, \frac{1}{K} \right) . $$

Combining this bound with (55) and counting the number of partitions $\pi \in \mathcal{P}_2(\alpha)$ for which $C_{x, \beta_1(\pi), \dots, \beta_l(\pi)} \neq 0$, we prove in Section D.7 the following upper-bound on $|\kappa_{x,\alpha}|$.
**LEMMA D.2.** Let $\alpha \in \mathbb{N}^{n \times p}$ non-zero. We have

$$|\kappa_{x,\alpha}| \le \lambda^{|\alpha|} \rho^{r_{\alpha}} |\alpha|^{2(|\alpha|-r_{\alpha}-\#\alpha+2)} \min\left(\left(\frac{1}{K}\right)^{\#\alpha+r_{\alpha}-\frac{|\alpha|}{2}-1}, \frac{1}{K}\right).$$

The last stage is to prune the multisets $\alpha$ for which $\kappa_{x,\alpha} = 0$. The next lemma gives necessary conditions for having $\kappa_{x,\alpha} \neq 0$. For this purpose, it is convenient, as in the proof of Theorem 3.1, to introduce a bipartite multigraph $\mathcal{G}_{\alpha}$ on two disjoint sets $U = \{u_1, \dots, u_n\}$ and $V = \{v_1, \dots, v_p\}$ with $\alpha_{ij}$ edges between $u_i$ and $v_j$, for any $i, j \in [n] \times [p]$. We write $\mathcal{G}_{\alpha}^{-}$ the restriction of $\mathcal{G}_{\alpha}$ to non-isolated nodes. We denote $U(\alpha)$ the elements of $U$ which are nodes of $\mathcal{G}_{\alpha}^{-}$ and $V(\alpha)$ the elements of $V$ which are nodes of $\mathcal{G}_{\alpha}^{-}$. We refer to Section D.8 for a proof of this lemma.

**LEMMA D.3.** Let $\alpha \in \mathbb{N}^{n \times p}$ be non-zero. If $\kappa_{x,\alpha} \neq 0$, then

* $u_1, u_2 \in U(\alpha)$;

* $\mathcal{G}_{\alpha}^{-} \cup \{(u_1, u_2)\}$ is connected;

* All the elements of $U(\alpha)$ and $V(\alpha)$ are of degree at least 2.

In particular, we have $\#\alpha \ge 2$, $|\alpha| \ge 2r_{\alpha}$ and $|\alpha| \ge 2\#\alpha$.

**REMARK 9.** In fact, we can prove that $\mathcal{G}_{\alpha}^{-}$ is connected (see [28]), but it is sufficient and more straightforward using Theorem 2.5 to prove that $\mathcal{G}_{\alpha}^{-} \cup \{(u_1, u_2)\}$ is connected.

Let $d \in [2, D]$, $m, r$ such that $d \ge 2 \max(r, m)$. Since the conditions of Lemma D.3 are more restrictive than the ones of Lemma C.3, we can apply Lemma C.4. Thus, there exists at most $n^{m-2}p^r d^{3(d-r-m+2)}$ matrices $\alpha$ satisfying the conditions of Lemma D.3 with $|\alpha| = d$, $\#\alpha = m$ and $r_{\alpha} = r$.

Then, using Proposition 2.1 together with Lemma D.2, and pruning the terms that do not satisfy the conditions of Lemma D.3, we get

$$\begin{aligned} \mathrm{corr}_{\le D}^2 - \frac{1}{K^2} &\le \sum_{\alpha \ne 0, \ |\alpha| \le D} \kappa_{\alpha}^2 \\ &\le \frac{1}{K^2} \sum_{d \in [D]} \sum_{\substack{r \le d/2 \\ 2 \le m \le d/2}} (d^7 \lambda^2)^d \left(\frac{n}{d^7}\right)^{m-2} \left(\frac{\rho^2 p}{d^7}\right)^r \min\left(1, \left(\frac{1}{K^2}\right)^{m+r-\frac{d}{2}-2}\right). \end{aligned}$$

Let us fix $r \ge 1$, $m \ge 2$ and $d \ge \max(2r, 2m)$ and let us upper-bound the quantity

$$A_{d,r,m} := (d^7 \lambda^2)^d \left(\frac{n}{d^7}\right)^{m-2} \left(\frac{\rho^2 p}{d^7}\right)^r \min\left(1, \left(\frac{1}{K^2}\right)^{m+r-\frac{d}{2}-2}\right).$$
First, let us suppose that $d < 2(m - 2) + 2r$. Decomposing into sums of positive terms $m - 2 = m - 2 - (d/2 - r) + (d/2 - r)$ and $d = 2r + 2(d/2 - r)$, we get

$$
\begin{align*}
A_{d,r,m} &= (d^7 \lambda^2)^d \left(\frac{n}{d^7}\right)^{m-2} \left(\frac{\rho^2 p}{d^7}\right)^r \left(\frac{1}{K^2}\right)^{m+r-\frac{d}{2}-2} \\
&\le D^{7(d-m-r+2)} \lambda^{2d} n^{m-2} (\rho^2 p)^r \left(\frac{1}{K^2}\right)^{m+r-\frac{d}{2}-2} \\
&\le D^{7(d-m-r+2)} (\lambda^4 \rho^2 p)^r (\lambda^4 n)^{d/2-r} \left(\frac{n}{K^2}\right)^{m-2-(d/2-r)} \\
&\le D^{7(d-m-r+2)} (\lambda^4 \rho^2 p)^{r-(m-2-(d/2-r))} \left(\frac{\lambda^4 \rho^2 pn}{K^2}\right)^{m-2-(d/2-r)} (\lambda^4 n)^{d/2-r} \\
&\le \left(\frac{D^7 \bar{\Delta}^4}{p}\right)^{r-(m-2-(d/2-r))} \left(\frac{\bar{\Delta}^4 n}{pK^2}\right)^{m-2-(d/2-r)} \left(\frac{D^7 \bar{\Delta}^4 n}{p^2 \rho^2}\right)^{d/2-r} \\
&\le \zeta^{r-(m-2-(d/2-r))} \zeta^{m-2-(d/2-r)} \zeta^{d/2-r} = \zeta^{\frac{d}{2}},
\end{align*}
$$

where we used in the fifth line that $\lambda^2 = \bar{\Delta}^2/(p\rho)$ and the definition (67) of $\zeta$.

On the other hand, if $d \ge 2r + 2(m-2)$, we decompose $d = d - (2(m-2) + 2r) + 2(m-2) + 2r$ to get

$$
\begin{align*}
A_{d,r,m} &= (d^7 \lambda^2)^d \left(\frac{n}{d^7}\right)^{m-2} \left(\frac{\rho^2 p}{d^7}\right)^r \min \left(1, \left(\frac{1}{K^2}\right)^{m+r-\frac{d}{2}-2}\right) \\
&\le (D^7 \lambda^2)^d \left(\frac{n}{D^7}\right)^{m-2} \left(\frac{\rho^2 p}{D^7}\right)^r \\
&\le (D^7 \lambda^2)^{d-2r-2(m-2)} (D^7 \lambda^4 n)^{m-2} (D^7 \lambda^4 \rho^2 p)^r \\
&\le \left(D^7 \frac{\bar{\Delta}^2}{p\rho}\right)^{d-2r-2(m-2)} \left(D^7 \frac{\bar{\Delta}^4}{p^2 \rho^2} n\right)^{m-2} \left(D^7 \frac{\bar{\Delta}^4}{p}\right)^r \\
&\le \sqrt{\zeta}^{d-2r-2(m-2)} \zeta^{m-2} \zeta^r = \zeta^{\frac{d}{2}}.
\end{align*}
$$

We can conclude the proof of the theorem with

$$
corr_{\le D}^2 \le \frac{1}{K^2} \left( 1 + \sum_{d \in [2, D]} \sum_{\substack{r \le d/2 \\ 2 \le m \le d/2}} \zeta^{\frac{d}{2}} \right) \le \frac{1}{K^2} \left( 1 + \sum_{d \in [2, D]} \frac{d(d-1)}{2} \zeta^{\frac{d}{2}} \right) \le \frac{1}{K^2} \left( 1 + \frac{\zeta}{(1 - \sqrt{\zeta})^3} \right) .
$$

**D.1. Proof of Lemma D.1.** Let us fix a decomposition $\beta_1 + \dots + \beta_l = \alpha$, with $|\beta_s| = 2$ and let us upper-bound $|C_{x,\beta_1,\dots,\beta_l}|$. For having $C_{x,\beta_1,\dots,\beta_l}$, it is necessary that each $\beta_s$ is supported on only one column. Thus, we can write $\beta_s = \{(i_s, j_s); (i'_s, j'_s)\}$. Henceforth, we use the convention $i_0 = 1$, $i'_0 = 2$, and $j_0 = 0$. For $S \subseteq [l]$, we write $\beta[S] = \{\beta_s, s \in S\}$. Building on (18), we get, for all $S \subseteq [l]$, the recursion formula

$$
|C_{x,\beta[S]}| \le \mathbb{P}[\forall s \in \{0\} \cup S, k_{i_s}^* = k_{i'_s}^*] \mathbb{P}[\forall s \in S, z_{j_s} = 1] +
$$
$$
+ \sum_{S' \subseteq S} |C_{x,\beta[S']}| \mathbb{P}[\forall s \in \{0\} \cup S', k_{i_s}^* = k_{i_s'}^*] \mathbb{P}[\forall s \in S, z_{j_s} = 1] \\
\leq \rho^{r_{\alpha_S}} \mathbb{P}[\forall s \in \{0\} \cup S, k_{i_s}^* = k_{i_s'}^*] + \sum_{S' \subseteq S} |C_{x,\beta[S']}| \rho^{r_{\alpha_{S\setminus S'}}} \mathbb{P}[\forall s \in S \setminus S', k_{i_s}^* = k_{i_s'}^*],
$$

where, for $R \subseteq [l]$, $\alpha_R = \sum_{s \in R} \beta_R$.

Let us compute, for any subset $R \subseteq [0, l]$, the quantity $\mathbb{P}[\forall s \in R, k_{i_s}^* = k_{i_s'}^*]$. To do so, let us define, as in Section C.1, $\mathcal{V}$ the graph on $[0, l]$ defined by: for $s, s' \ge 0$, there is an edge between $s$ and $s'$ if and only if $\{i_s, i_s'\} \cap \{i_{s'}, i_{s'}'\} \ne \emptyset$. For $R \subseteq [0, l]$, we write $\mathcal{V}[R]$ the restriction of $\mathcal{V}$ to $R$ and $cc(\mathcal{V}[R])$ the number of connected components of this graph. As in Section C.1, we obtain, when $0 \in R$, $\mathbb{P}[\forall s \in R, k_{i_s}^* = k_{i_s'}^*] = (\frac{1}{K})^{\text{supp}(\alpha_R \setminus \{0\}) \cup \{1,2\} - \text{cc}(\mathcal{V}[R])}$, and, when $0 \notin R$, $\mathbb{P}[\forall s \in R, k_{i_s}^* = k_{i_s'}^*] = (\frac{1}{K})^{\#\alpha_R - \text{cc}(\mathcal{V}[R])}$. In turn, for all $S \subseteq [l]$, we have

$$
(68) \quad |C_{x,\beta[S]}| \le \rho^{r_{\alpha_S}} \left(\frac{1}{K}\right)^{|\text{supp}(\alpha_S) \cup \{1,2\}| - \text{cc}(\mathcal{V}[S \cup \{0\}])} + \sum_{S' \subseteq S} |C_{x,\beta[S']}| \rho^{r_{\alpha_{S\setminus S'}}} \left(\frac{1}{K}\right)^{\#\alpha_{S\setminus S'} - \text{cc}(\mathcal{V}[S \setminus S'])}.
$$

The next lemma whose proof is postponed to Section D.2, prunes subsets $S \subseteq [l]$ such that $C_{x,\beta[S]} = 0$. To do so, we introduce the graph $W$ on $[0, l]$ with an edge between $s, s' \in [0, l]$ if and only if $j_s = j_{s'}$ or $\{i_s, i_s'\} \cap \{i_{s'}, i_{s'}'\} \ne \emptyset$ (we recall that for $s=0$, we write $j_0=0$). For $S \subseteq [l]$ and $j \in \cup_{s \in S \cup \{0\}} \{j_s\} = \text{col}(\alpha_S) \cup \{0\}$, we write $S_j = \{s \in S, j_s = j\}$ (in particular $S_0 = \{0\}$). In the following, we denote $S([l])$ the collection of subset $S$ of $[l]$ satisfying;

1. $W[S \cup \{0\}]$ is connected;

2. If $S \neq \emptyset$, then for all $j \in \text{col}(\alpha_S) \cup \{0\}$, there exist $\underline{i} \neq \underline{i}' \in \cup_{s \in S_j} \{i_s, i_s'\}$ such that both $\underline{i}$ and $\underline{i}'$ are in $\cup_{s \in S \setminus S_j} \{i_s, i_s'\}$;

3. For all $i \in \text{supp}(\alpha_S) \setminus \{1,2\}$, $|\langle \alpha_S \rangle_i| \ge 2$.

In particular, the second property implies that, as long as $S \neq \emptyset$, we have $\{1,2\} \subset \text{supp}(\alpha_S)$.

LEMMA D.4. For $S \subseteq [l]$, if $C_{x,\beta[S]} \neq 0$, then $S \in S([l])$.

Pruning the other terms in (68) leads to, for all $S \in S([l])$,

$$
(69) \quad |C_{x,\beta[S]}| \le \rho^{r_{\alpha_S}} \left(\frac{1}{K}\right)^{|\text{supp}(\alpha_S) \cup \{1,2\}| - \text{cc}(\mathcal{V}[S \cup \{0\}])} + \sum_{\substack{S' \subseteq S \\ S' \in \mathcal{S}([l])}} |C_{x,\beta[S']}| \rho^{r_{\alpha_{S \setminus S'}}} \left(\frac{1}{K}\right)^{\#\alpha_{S \setminus S'} - \text{cc}(\mathcal{V}[S \setminus S'])}.
$$

In the following, let us define recursively a function $f$ on $S([l])$ satisfying, for all $S \in S([l])$,

$$
(70) \qquad f(S) = 1 + \sum_{\substack{S' \subseteq S \\ S' \in S([l])}} f(S').
$$
In particular, $f(\emptyset) = 1$. The next lemma, proved in Section D.3, relies on the connectivity of $W[S \cup \{0\}]$ for $S \in S([l])$, to bound $|C_{x,\beta[S]}|$ with respect to this function $f$.

**LEMMA D.5.** For all $S \in S([l])$, we have $|C_{x,\beta[S]}| \le \rho^{r_{\alpha_S}} \min \left( \left(\frac{1}{K}\right)^{\#\alpha_S + r_{\alpha_S} - \frac{|\alpha_S|}{2} - 1}, \frac{1}{K} \right) f(S)$.

It remains to upper-bound $f(S)$ for all $S \in S([l])$.

**LEMMA D.6.** For all non empty $S \in S([l])$, we have $f(S) \le |\alpha|^{|\alpha_S|-\#\alpha_S-r_{\alpha_S}+2}$.

Applying Lemma D.6 and Lemma D.5 to $S = [l]$ leads to

$$C_{x,\beta_1,\dots,\beta_t} \le \rho^{r_{\alpha}} |\alpha|^{|\alpha|-r_{\alpha}-\#\alpha+2} \min \left( \left(\frac{1}{K}\right)^{\#\alpha+r_{\alpha}-\frac{|\alpha|}{2}-1}, \frac{1}{K} \right),$$

which concludes the proof of the lemma.

**D.2. Proof of Lemma D.4.** Let $S \subseteq [l]$. Let us suppose that $S \notin S([l])$ and let us prove that $C_{x,\beta[S]} = 0$. The set $S([l])$ is an intersection of three constraints. We shall suppose that one of these constraints is not satisfied;

1. Let us first suppose that $W[S \cup \{0\}]$ is not connected. Let $C_1$ and $C_2$ a partition of $S \cup \{0\}$ with no edges of $W$ connecting them. We suppose by symmetry that $0 \in C_1$. Then, the family of random variables $((\epsilon_i, k_i^*)_{i \in \cup_{s \in C_1} \{i_s, i'_s\}}, (z_j)_{j \in \cup_{s \in C_1 \setminus \{0\}} \{j_s\}})$ is independent of the family $((\epsilon_i, k_i^*)_{i \in \cup_{s \in C_2} \{i_s, i'_s\}}, (z_j)_{j \in \cup_{s \in C_2} \{j_s\}})$. Then, Lemma B.2 implies that $C_{x,\beta[S]} = 0$.

2. Let us now suppose that there exists $j_0 \in \text{col}(\alpha_S) \cup \{0\}$ with at most one element in $\cup_{s \in S_{j_0}} \{i_s, i'_s\}$ which is also in $\cup_{s \in S \setminus S_{j_0}} \{i_s, i'_s\}$. Let us denote $\underline{i}$ this element. Then, $(\epsilon_{\underline{i}})$ is independent of $(\epsilon_{i_s} \epsilon_{i'_s})_{s \in S \setminus S_{j_0}}$. Indeed, since the $\epsilon_i$'s are distributed as independent rademacher, the conditional distribution of $(\epsilon_{i_s} \epsilon_{i'_s})_{s \in S \setminus S_{j_0}}$ does not depend on the value $(\epsilon_{\underline{i}})$. Since, apart from $\epsilon_{\underline{i}}$, all the other $\epsilon_i$ with $i \in \cup_{s \in S_{j_0}} \{i_s, i'_s\}$ do not occur in $(\epsilon_{i_s} \epsilon_{i'_s})_{s \in S \setminus S_{j_0}}$, we deduce that $(\epsilon_i)_{i \in \cup_{s \in S_{j_0}} \{i_s, i'_s\}}$ is independent of $(\epsilon_{i_s} \epsilon_{i'_s})_{s \in S \setminus S_{j_0}}$. We have proved that $(\epsilon_{i_s} \epsilon_{i'_s})_{s \in S_{j_0}}$ is independent of $(\epsilon_{i_s} \epsilon_{i'_s})_{s \in S \setminus S_{j_0}}$. Arguing similarly, we get that $(z_{j_0}, (\epsilon_{i_s} \epsilon_{i'_s} \mathbf{1}_{\{k_{i_s}^* = k_{i'_s}^*\}})_{s \in S_{j_0}})$ is independent of $((z_j)_{j \ne j_0}, (\epsilon_{i_s} \epsilon_{i'_s} \mathbf{1}_{\{k_{i_s}^* = k_{i'_s}^*\}})_{s \in S \setminus S_{j_0}})$. From Lemma B.2, we conclude that $C_{x,\beta[S]} = 0$.

3. Let us finally suppose that there exists $\underline{i} \in \text{supp}(\alpha_S) \setminus \{1,2\}$ with $|\langle \alpha_S \rangle_{\underline{i}}| = 1$. Let $s_0$ the unique element of $S$ such that $\underline{i} \in \text{supp}(\beta_{s_0})$; we suppose $\underline{i} = i_{s_0}$ for exemple. The random variable $\epsilon_{\underline{i}}$ is symmetric and independent from all the other random variables. Hence, changing $\epsilon_{\underline{i}}$ to $-\epsilon_{\underline{i}}$ does not change the joint law of all the random variables and thus, by multilinearity of the cumulant, we have

$$\begin{align*}
C_{x,\beta[S]} &= \text{Cum} \left( x, \left( \epsilon_{i_s} \epsilon_{i'_s} \mathbf{1}_{z_{j_s} \ne 0} \mathbf{1}_{k_{i_s}^* = k_{i'_s}^*} \right)_{s \in S} \right) \\
&= \text{Cum} \left( x, \left( \epsilon_{i_s} \epsilon_{i'_s} \mathbf{1}_{z_{j_s} \ne 0} \mathbf{1}_{k_{i_s}^* = k_{i'_s}^*} \right)_{s \in S \setminus \{s_0\}}, -\epsilon_{i_{s_0}} \epsilon_{i'_{s_0}} \mathbf{1}_{z_{j_{s_0}} \ne 0} \mathbf{1}_{k_{i_{s_0}}^* = k_{i'_{s_0}}^*} \right)
\end{align*}$$
$$
\begin{align*}
&= - \mathrm{Cum} \left( x, \left( \varepsilon_{i_s} \varepsilon_{i'_s} \mathbf{1}_{z_{j_s} \neq 0} \mathbf{1}_{k_{i_s}^* = k_{i'_s}^*} \right)_{s \in S} \right) \\
&= - C_{x, \beta[S]},
\end{align*}
$$

which, in turn, implies that $C_{x,\beta[S]} = 0$.

**D.3. Proof of Lemma D.5.** Let us prove by induction that, for all $S \in \mathcal{S}([l])$,

$$
|C_{x,\beta[S]}| \le \rho^{r_{\alpha_S}} \min\left(\frac{1}{K}, \left(\frac{1}{K}\right)^{\frac{\alpha_S + r_{\alpha_S} - \frac{|\alpha_S|}{2} - 1}{2}} f(S)\right).
$$

The initialization is trivial since $C_{x,\beta[\emptyset]} = \mathrm{Cum}(x) = \frac{1}{K}$ and $|\alpha_{\emptyset}| = 0$.

Induction. Let $S \neq \emptyset \in \mathcal{S}([l])$ and let us suppose that the result holds for all $S' \subsetneq S$ with $S' \in \mathcal{S}([l])$. Since $S \neq \emptyset$, we know from the remark below the definition of $\mathcal{S}([l])$ that $\{1,2\} \subset \mathrm{supp}(\alpha_S)$.

Applying Inequality (69) to $S$ together with the induction hypothesis leads to

$$
\begin{align*}
|C_{x,\beta[S]}| &\le \rho^{r_{\alpha_S}} \left(\frac{1}{K}\right)^{\#\alpha_S - cc(V[S \cup \{0\})} \\
&\quad + \sum_{\substack{S' \subsetneq S \\ S' \in \mathcal{S}([l])}} |C_{x,\beta[S']}| \rho^{r_{\alpha_{S \setminus S'}}} \left(\frac{1}{K}\right)^{\#\alpha_{S \setminus S'} - cc(V[S \setminus S'])} \\
&\le \rho^{r_{\alpha_S}} \left(\frac{1}{K}\right)^{\#\alpha_S - cc(V[S \cup \{0\})} \\
&\quad + \sum_{\substack{S' \subsetneq S \\ S' \in \mathcal{S}([l])}} f(S') \min \left(\frac{1}{K}, \left(\frac{1}{K}\right)^{\#\alpha_{S'} + r_{\alpha_{S'}} - \frac{|\alpha_{S'}|}{2} - 1}\right) \left(\frac{1}{K}\right)^{\#\alpha_{S \setminus S'} - cc(V[S \setminus S'])} \rho^{r_{\alpha_{S'}} + r_{\alpha_{S \setminus S'}}}.
\end{align*}
$$

Let us remark that $r_{\alpha_{S'}} + r_{\alpha_{S \setminus S'}} \ge r_{\alpha_S}$. Since $\#\alpha_S - cc(V[S \cup \{0\}]) \ge 1$ and since $\#\alpha_{S \setminus S'} - cc(V[S \setminus S']) \ge 0$, we directly deduce that $|C_{x,\beta[S]}| \le \frac{1}{K}f(S)\rho^{r_{\alpha_S}}$.

It remains to prove that $|C_{x,\beta[S]}| \le \rho^{r_{\alpha_S}} f(S) \left(\frac{1}{K}\right)^{\#\alpha_S + r_{\alpha_S} - \frac{|\alpha_S|}{2} - 1}$. Let us isolate the term $S' = \emptyset$ in the sum.

$$
\begin{align*}
\rho^{-r_{\alpha_S}} |C_{x,\beta[S]}| &\le \left(\frac{1}{K}\right)^{\#\alpha_S - cc(V[S \cup \{0\})} \\
&\quad + \sum_{\substack{\emptyset \ne S' \subsetneq S \\ S' \in \mathcal{S}([l])}} f(S') \left(\frac{1}{K}\right)^{\#\alpha_{S'} + r_{\alpha_{S'}} - \frac{|\alpha_{S'}|}{2} - 1 + \#\alpha_{S \setminus S'} - cc(V[S \setminus S'])} \\
&\quad + \frac{1}{K} \left(\frac{1}{K}\right)^{\#\alpha_S - cc(V[S])}.
\end{align*}
$$

The next lemma uses the connectivity of the graph $\mathcal{W}[S \cup \{0\}]$ in order to lower bound the exposants of the above inequality. We refer to Section D.4 for its proof.

LEMMA D.7. For any subset $R \subseteq [0, l]$, $cc(W[R]) - cc(V[R]) \ge r_{\alpha_R} - \frac{|\alpha_R|}{2}$.

Applying Lemma D.7 together with the fact that $\mathcal{W}[S \cup \{0\}]$ is connected leads us to

$$
\frac{|C_{x,\beta[S]}|}{\rho^{\alpha_R}} \le \left(\frac{1}{K}\right)^{\#\alpha_S + r_{\alpha_S} - \frac{|\alpha_S|}{2} - 1}
$$
$$ + \sum_{\substack{S' \subseteq S \\ \emptyset \neq S' \in \mathcal{S}([l])}} f(S') \left(\frac{1}{K}\right)^{\#\alpha_{S'} + r_{\alpha_{S'}} - \frac{|\alpha_{S'}|}{2} - 1 + \#\alpha_{S \setminus S'} + r_{\alpha_{S \setminus S'}} - \frac{|\alpha_{S \setminus S'}|}{2} - cc(W[S \setminus S'])} \\ + \left(\frac{1}{K}\right)^{1 + \#\alpha_S + r_{\alpha_S} - \frac{|\alpha_S|}{2} - cc(W[S])} $$

The next lemma uses again the connectivity of $W[S \cup \{0\}]$ in order to lower-bound the exposants in the sum above. We refer to Section D.5 for its proof.

**LEMMA D.8.** For any subset $S' \subseteq S$ that both belong to $\mathcal{S}([l])$ and such that $S' \neq \emptyset$, we have

$$ \#\alpha_{S'} + r_{\alpha_{S'}} + \#\alpha_{S \setminus S'} + r_{\alpha_{S \setminus S'}} - cc(W[S \setminus S']) \geq \#\alpha_S + r_{\alpha_S} . $$

For the term $S' = \emptyset$, we use the fact that $cc(W[S]) \leq 2$ to get the desired inequality

$$ \left(\frac{1}{K}\right)^{1 + \#\alpha_S + r_{\alpha_S} - \frac{|\alpha_S|}{2} - cc(W[S])} \leq \left(\frac{1}{K}\right)^{\#\alpha_S + r_{\alpha_S} - \frac{|\alpha_S|}{2} - 1} . $$

We deduce from this and Lemma D.8 that

$$ \frac{|C_{x,\beta[S]}|}{\rho^{\alpha_R}} \leq \left(\frac{1}{K}\right)^{\#\alpha_S + r_{\alpha_S} - \frac{|\alpha_S|}{2} - 1} \left( 1 + \sum_{\substack{S' \subseteq S \\ S' \in \mathcal{S}([l])}} f(S') \right) \\ \leq f(S) \left(\frac{1}{K}\right)^{\#\alpha_S + r_{\alpha_S} - \frac{|\alpha_S|}{2} - 1} , $$

which concludes the induction and the proof of the lemma.

**D.4. Proof of Lemma D.7.** Let us fix $R \subseteq [0, l]$. We need to prove that

$$ |\alpha_R| \geq 2(r_{\alpha_R} - cc(W[R]) + cc(V[R])) . $$

By definition, $V(R)$ is a subgraph of $W_r$. Hence, to show this inequality, it is sufficient to prove it for all connected components of $W[R]$. We can therefore suppose without loss of generality that $W[R]$ is connected.

Denote $q = cc(V[R])$ and let us write $cc_1, \dots, cc_q$ the collection of the connected components of $V[R]$. Since the graph $W[R]$ is connected, we can, up to a reordering of the $cc_l$'s, suppose that, for all $q' \in [2, q]$, $W[R]$ has an edge connecting $cc_{q'}$ to $(\cup_{q''<q'} cc_{q''})$. In the following, for all $q' \in [q]$, we write $\alpha_{cc_{q'}} = \sum_{s \in cc_{q'}} \beta_s$ and $\alpha^{(q')} = \sum_{q'' \leq q'} \alpha_{cc_{q''}}$. Let us prove by induction over $q' \in [q]$ that

$$ |\alpha^{(q')}| \geq 2r_{\alpha^{(q')}} + 2(q' - 1) . $$
**Initialization.** For all $j \in \text{col}(\alpha^{(1)})$, there exists $s \in cc_1 \setminus \{0\}$ such that $j_s = j$ (we recall that $\beta_s = \{(i_s, j_s); (i'_s, j'_s)\}$). Thus, $|\alpha^{(1)}|_j \ge |\beta_s| = 2$. We deduce that $|\alpha^{(1)}| \ge 2r_{\alpha^{(1)}}$.

**Induction.** Let us suppose that the result holds for some $q' \in [q-1]$ and let us prove that it still holds for $q' + 1$. As for the initialisation, we have $|\alpha_{cc_{q'+1}}| \ge 2r_{\alpha_{cc_{q'+1}}}$. Since $\mathcal{W}$ has an edge connecting $cc_{q'+1}$ to $(\cup_{q'' \le q'} cc_{q''})$ whereas $\mathcal{V}$ does not have any, we know that $\text{col}(\alpha_{cc_{q'+1}})$ intersects $\text{col}(\alpha^{(q')})$. Together with the induction hypothesis, this implies that

$$|\alpha^{(q'+1)}| \ge 2r_{\alpha^{(q')}} + 2(q' - 1) + 2r_{\alpha_{cc_{q'+1}}} \ge 2r_{\alpha^{(q'+1)}} + 2q',$$

and concludes the induction.

**D.5. Proof of Lemma D.8.** Let $S' \subseteq S$ be a non-empty set. Since $S' \in \mathcal{S}([l])$ is non-empty, we know that $\{1, 2\} \subset \text{supp}(\alpha_{S'})$. Let us prove the inequality

$$\#\alpha_{S'} + r_{\alpha_{S'}} + \#\alpha_{S \setminus S'} + r_{\alpha_{S \setminus S'}} \ge \#\alpha_S + r_{\alpha_S} + cc(\mathcal{W}[S \setminus S']) .$$

Let $q = \text{cc}(\mathcal{W}[S \setminus S'])$ and let us write $cc_1, \dots, cc_q$ the collection of the connected components of $\mathcal{W}[S \setminus S']$. Since the graph $\mathcal{W}[S \setminus S']$ does not have any edge between the $cc_{q'}$'s, we have $\#\alpha_{S \setminus S'} = \sum_{q' \in [q]} \#\alpha_{cc_{q'}}$ and $r_{\alpha_{S \setminus S'}} = \sum_{q' \in [q]} r_{\alpha_{cc_{q'}}}$.

Since the graph $\mathcal{W}[S \cup \{0\}]$ is connected, for all $q' \in [q]$, $\mathcal{W}[S \cup \{0\}]$ has an edge connecting $cc_{q'}$ to $S' \cup \{0\}$. Thus, for all $q' \in [q]$, either $\text{supp}(\alpha_{cc_{q'}})$ intersects $\text{supp}(\alpha_{S'}) \cup \{1, 2\} = \text{supp}(\alpha_{S'})$, or that $\text{col}(\alpha_{cc_{q'}})$ intersects $\text{col}(\alpha_{S'})$. We deduce that

$$\#\alpha_{cc_{q'}} + r_{\alpha_{cc_{q'}}} \ge 1 + |\text{supp}(\alpha_{cc_{q'}}) \setminus \text{supp}(\alpha_{S'})| + |\text{col}(\alpha_{cc_{q'}}) \setminus \text{col}(\alpha_{S'})| .$$

Gathering everything, we get

$$\begin{align*}
\#\alpha_{S'} + r_{\alpha_{S'}} + \#\alpha_{S \setminus S'} + r_{\alpha_{S \setminus S'}}
&= \#\alpha_{S'} + r_{\alpha_{S'}} + \sum_{q' \in [q]} \#\alpha_{cc_{q'}} + \sum_{q' \in [q]} r_{\alpha_{cc_{q'}}} \\
&\ge \#\alpha_{S'} + r_{\alpha_{S'}} + \sum_{q' \in [q]} 1 + |\text{supp}(\alpha_{cc_{q'}}) \setminus \text{supp}(\alpha_{S'})| + |\text{col}(\alpha_{cc_{q'}}) \setminus \text{col}(\alpha_{S'})| \\
&\ge \#\alpha_S + r_{\alpha_S} + cc(\mathcal{W}[S \setminus S']) ,
\end{align*}$$

which concludes the proof of the lemma.

**D.6. Proof of Lemma D.6.** We proceed by induction on $S \in \mathcal{S}([l])$ to prove that

$$(71) \qquad f(S) \le |\alpha|^{|\alpha_S| - |\text{supp}(\alpha_S) \cup \{1, 2\}| - r_{\alpha_S} + 2}.$$

Since when $S \ne \emptyset$, we have $|\text{supp}(\alpha_S) \cup \{1, 2\}| = |\text{supp}(\alpha_S)| = \#\alpha_S$ –see the remark below the definition of $\mathcal{S}([l])$, this is sufficient for our purpose.

The initialization is trivial since $f(\emptyset) = 1$ and $\alpha_{\emptyset} = 0$. Let us take $S \in \mathcal{S}([l])$ and let us suppose that the result holds for all $S' \subseteq S$. For all $s \in S$, denote $S^*(s)$ the maximal element of $\mathcal{S}([l])$ which is included in $S \setminus \{s\}$. The existence of such an element is justified by the
fact that the set of elements $S' \in S([l])$ with $S' \subseteq S \setminus \{s\}$ is not empty (it contains $\emptyset$) and is stable by union. Then, we have

$$
\begin{align*}
f(S) &= 1 + \sum_{\substack{S' \subseteq S \\ S' \in S([l])}} f(S') \le 1 + \sum_{\substack{s \in S \\ S' \subseteq S^*(s) \\ S' \in S([l])}} \sum_{\substack{s' \in S \\ S' \subseteq S^*(s')}} f(S') \\
&\le 1 + \sum_{s \in S} [2f(S^*(s)) - 1] \\
&\le 2 \sum_{s \in S} f(S^*(s)),
\end{align*}
$$

where we used the recursive definition of $f$ in the second row. Applying the induction hy-
pothesis leads us to

$$
(72) \qquad f(S) \le 2 \sum_{s \in S} |\alpha|^{|\alpha_{S^*(s)}| - |\text{supp}(\alpha_{S^*(s)}) \cup \{1,2\}| - r_{\alpha_{S^*(s)}} + 2} .
$$

Let us fix $s_0 \in S \setminus S^*(s_0)$. We denote in the following $S^- = S \setminus S^*(s_0)$. Besides, let $S_0^-$ denote the set of all $s \in S \setminus S^*(s_0)$ such that $j_s \in \text{col}(\alpha_{S^*(s_0)})$. Then, we write $j^1, \dots, j^r \in [p]$ the other columns of $S \setminus S^*(s_0)$ that do not appear in $\text{col}(\alpha_{S^*(s_0)})$. Besides, for $r' = 1, \dots, r$, we write $S_r^-$ the set of $s \in S^-$ such that $j_s = j^{r'}$. Since the graph $W[S \cup \{0\}]$ is connected, we can suppose, up to some reordering, that for all $r' \le r$, there exists $i \in \text{supp}(\alpha_{S_r^-}) \cap (\text{supp}(\alpha_{S^*(s_0)} + \sum_{0 \le r'' \le r'-1} \alpha_{S_{r''}^-}) \cup \{1,2\})$. Moreover, at the final step $r' = r$, from Lemma D.4, we know that there exist two distinct $i, i' \in \text{supp}(\alpha_{S_r^-}) \cap (\text{supp}(\alpha_{S^*(s_0)} + \sum_{0 \le r'' \le r-1} \alpha_{S_{r''}^-}) \cup \{1,2\})$. If $r \ne 0$, those two claims imply that $|\alpha_{S^-}| \ge r+1 + |\text{supp}(\alpha_{S^-}) \setminus (\text{supp}(\alpha_{S^*(s_0)}) \cup \{1,2\})|$. Since $\{1,2\} \subseteq \text{supp}(\alpha_S)$, we derive from the latter that

$$
|\alpha_S| - |\text{supp}(\alpha_S) \cup \{1,2\}| - r_{\alpha_S} - 1 \ge |\alpha_{S^*(s_0)}| - |\text{supp}(\alpha_{S^*(s_0)}) \cup \{1,2\}| - r_{\alpha_{S^*(s_0)}} .
$$

If $r=0$, we use the fact that all $i \in \text{supp}(\alpha_S)$ must satisfy $|(\alpha_S)_{i}| \ge 2$ –see Lemma D.4.
This implies that

$$
\begin{align*}
|\alpha_{S^-}| &\ge \min(2, 2|\text{supp}(\alpha_{S^-}) \setminus (\text{supp}(\alpha_{S^*(s_0)} \cup \{1,2\}))|) \\
&\ge |\text{supp}(\alpha_{S^-}) \setminus (\text{supp}(\alpha_{S^*(s_0)} \cup \{1,2\}))| + 1 .
\end{align*}
$$

Hence, as in the case $r \neq 0$, we also get in the case $r = 0$ that

$$
|\alpha_S| - |\text{supp}(\alpha_S) \cup \{1,2\}| - r_{\alpha_S} - 1 \ge |\alpha_{S^*(s_0)}| - |\text{supp}(\alpha_{S^*(s_0)} \cup \{1,2\})| - r_{\alpha_{S^*(s_0)}} .
$$

Hence, we deduce from (72) that

$$
f(S) \le \frac{2|S|}{|\alpha|} |\alpha|^{|\alpha_S|-|\text{supp}(\alpha_S) \cup \{1,2\}|-r_{\alpha_S}+2} \le |\alpha|^{|\alpha_S|-|\text{supp}(\alpha_S) \cup \{1,2\}|-r_{\alpha_S}+2} .
$$

We have shown (71), which concludes the proof.

**D.7. Proof of Lemma D.2.** In order to get a suitable upper bound of $|\kappa_{x,\alpha}|$ from Theorem 2.5 and Lemma D.1, it is sufficient to upper-bound the number of partitions $\pi = \pi_1, \dots, \pi_l$ of the multisets $\alpha$ into groups of size 2 such that $C_{x,\beta_1(\pi),\dots,\beta_l(\pi)} \ne 0$, where $(\beta_s(\pi))_{ij}$ counts the number of copies of $(i,j)$ in $\pi_s$. Remember that for such a partition, it is necessary that, for