Pith. sign in

REVIEW 2 major objections 4 minor 1 cited by

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

T0 review · 2 major / 4 minor · reviewed 2026-08-15 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read This paper proves sharp computational lower bounds for clustering, sparse clustering, and biclustering by conditioning on latent structure, recovering the exact BBP threshold for Gaussian mixtures in moderate dimension.

desk verdict Strong new conditioning technique and a clean BBP-threshold result for Gaussian mixture clustering, but the sparse-clustering and biclustering lower bounds prove hardness for a symmetrized 2K model, not the original K-cluster problem. read the letter →

arxiv 2506.13647 v1 pith:4G77OFB6 submitted 2025-06-16 math.ST stat.MLstat.TH

Bertrand Even , Christophe Giraud , Nicolas Verzelen This is my paper · ORCID
classification math.STstat.MLstat.TH MSC 62H3068Q17
keywords computationallowerboundsstatistical-computationalgapslow-degreepolynomialsclusteringGaussianmixturessparsebiclusteringcumulants
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper develops a new proof scheme for lower-bounding the performance of low-degree polynomials in latent-space models, and uses it to map the computational-statistical gaps of three clustering problems. The central claim is that in the moderately high-dimensional regime $p\ge \log^5 n$, no degree-$O(\log n)$ polynomial can cluster isotropic Gaussian mixtures better than random guessing once the mean separation falls below the BBP threshold $\sqrt{pK^2/n}$ (or the dimension-limited threshold $\sqrt{p/\log^{18}n}$). The same conditioning technique yields barriers for sparse clustering and biclustering, each with an interpretation in terms of what must be recovered before clustering is possible. The paper also provides almost matching polynomial-time algorithms, so the gaps are located precisely rather than merely conjectured.

What carries the argument

The central object is the multivariate cumulant $\kappa_{x,\alpha}=\mathrm{Cum}(x,\{X_{ij}\}_{(i,j)\in\alpha})$ and a new recursion for bounding it. Conditioning on the latent variable $Z$ and applying the law of total cumulance, the only surviving conditional cumulants are second-order ones sitting inside a single latent class, so the low-degree correlation bound $\mathrm{corr}^2_{\le D}\le\sum_{|\alpha|\le D}\kappa_{x,\alpha}^2/\alpha!$ reduces to counting sparse multisets $\alpha$ with explicit graph-theoretic connectedness conditions. This improved control removes the poly-log factors of earlier arguments and yields the exact constant at the BBP threshold.

What would settle it

Run a polynomial-time clustering algorithm on isotropic Gaussian mixtures with $K$ fixed, $n=10^6$, $p=(\log n)^6$, and mean separation $\Delta^2=0.9\sqrt{pK^2/n}$. If it recovers the true partition with misclassification error $o(1)$ with probability $1-o(1)$, then degree-$O(\log n)$ polynomials are not a faithful proxy for poly-time algorithms in this regime, and the claimed computational gap collapses.

Watch

Extended reading notes

Core claim

The paper's main discovery is a general cumulant identity for the latent model $Y_{ij}=\delta_{ij}(Z)\nu_{\theta_{ij}(Z)}+E_{ij}$ with Gaussian $\nu$'s: conditioning on the latent variable $Z$ and applying the law of total cumulance collapses the low-degree correlation to sums over pair partitions, giving recursive bounds with the correct dependence on $K$, $n$, and $p$. Instantiating this for Gaussian mixtures yields Theorem 3.1: under a random balanced prior with separation parameter $\bar\Delta$, whenever $D^5\le p$ and $\zeta=\frac{\bar\Delta^4}{p}\max(D^{18},n/K^2)<1$, the degree-$D$ minimal mean-square error for estimating the partnership indicator satisfies $\mathrm{MMSE}_{\le D}\ge \bigl(\frac1K-\frac1{K^2}\bigr)\bigl(1+\frac{\zeta}{(1-\sqrt{\zeta})^3}\bigr)$. Consequently, degree $(\log n)^{1+\eta}$ polynomials are no better than random guessing whenever $\bar\Delta^2\le(1-\varepsilon)\min\bigl(\sqrt{pK^2/n},\sqrt{p/\log^{18}n}\bigr)$; for $K^2\le n/\log^{18}n$ this is exactly the BBP threshold. The same proof engine, with symmetry-modified priors and refined counting of nonzero cumulants, gives the sparse-clustering barrier and the biclustering thresholds, and the matching upper bounds show these barriers are tight up to log factors in almost all regimes.

Load-bearing premise

The whole computational-hardness interpretation rests on the low-degree conjecture: that polynomials of degree $O(\log n)$ are as powerful as every polynomial-time algorithm for these clustering problems.

Editorial extensions

If this is right

  • For Gaussian mixtures with $p\ge \log^5 n$ and few clusters, clustering is low-degree-hard at the exact BBP level $\Delta^2=\sqrt{pK^2/n}$, matching the spectral transition where the leading eigenvalue separates from the noise bulk.
  • The sparse-clustering barrier combines the reduced-dimension clustering threshold with an extra $\sqrt{s^2/n}$ term, interpreted as the signal needed to find the active columns before clustering; the matching algorithm selects columns by norm and clusters the reduced matrix.
  • For biclustering, the column structure can lower the row-clustering threshold only when the columns themselves can already be clustered in polynomial time; otherwise row clustering is as hard as if the column structure were absent.
  • Almost matching polynomial-time upper bounds, by spectral projection and low-dimensional clustering, show that the barrier is tight up to log factors in nearly all regimes, with the remaining gap in the regime $p\le n/K$ and $K^2\le n\le \mathrm{poly}(K)$.
  • The paper provides evidence that sparse clustering and biclustering widen or reshape the statistical-computational gap in specific parameter regimes, depending on the relative sizes of $s$, $K$, $n$, and $p$.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • If the low-degree conjecture is accepted, the BBP threshold becomes the true poly-time boundary for isotropic Gaussian mixture clustering when $\log^5 n\le p\le n$, resolving a statistical-physics prediction non-asymptotically.
  • The conditioning recursion is a general technique; applying it to tensor PCA, community detection, or submatrix localization should give analogous sharp barriers wherever the signal is organized by a latent class variable, though the paper does not pursue those cases.
  • In the open regime $p\le n/K$ and $K^2\le n\le \mathrm{poly}(K)$, the authors suspect both the lower and upper bounds are loose; a sharper low-degree analysis or an improved algorithm there would settle the last unresolved gap.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

2 major / 4 minor

Summary. The paper develops a new conditioning-based scheme for bounding the multivariate cumulants that appear in the low-degree (LD) lower-bound framework of Schramm and Wein. The scheme is applied to three problems: Gaussian mixture clustering, sparse clustering, and biclustering. For Gaussian mixture clustering, Theorem 3.1 proves an LD lower bound that holds for p ≥ D^5 and recovers the conjectured BBP threshold sqrt(p K^2 / n) with an exact constant, improving on the earlier bound of Even, Giraud and Verzelen. The paper also provides polynomial-time upper bounds, mostly matching the LD barriers up to logarithmic factors, as well as statistical (information-theoretic) upper bounds. The authors are transparent about the open regime p ≤ n/K with K^2 ≤ n ≤ poly(K) and about the fact that the hardness conclusions depend on the low-degree conjecture.

Significance. If the main theorem for clustering is correct, this is a significant contribution to the computational-statistics literature: it substantially broadens the regime in which LD lower bounds are available for Gaussian mixtures, removes spurious poly-log factors, and gives the first non-asymptotic confirmation of the BBP-threshold conjecture for clustering in moderate dimension. The proof technique, based on conditioning on latent variables and the law of total cumulance, is elegant and likely to be useful in other latent-variable models. The upper bounds and the explicit discussion of the open regime are also valuable. However, the claimed lower bounds for sparse clustering and biclustering are undermined by a mismatch between the target functional used in the lower-bound theorems and the actual clustering target defined by the priors; this is a load-bearing problem for those two sections.

major comments (2)
  1. [Section 4.1, Definition 2, Theorem 4.1] The lower bound in Theorem 4.1 is stated for estimating x = 1{k*_1 = k*_2}, but the partition G* defined in Definition 2 is generated by the pairs (k*_i, epsilon_i), so the partnership indicator of G* is 1{k*_1 = k*_2, epsilon_1 = epsilon_2}. The reduction from partition recovery to x-estimation used in the clustering section, namely Eq. (27) and Proposition A.3, applies only to the partnership matrix of the partition being recovered; Proposition A.3 is explicitly stated for the prior of Definition 1, which has no epsilon variables. Consequently Theorem 4.1 lower-bounds the estimation of coarse labels in a 2K-component symmetrized mixture, not the recovery of the K or 2K clusters of the sparse-clustering model. The claimed sparse-clustering barriers (6), (33), and (35), including the additional sqrt(s^2/n) term, are therefore not established.
  2. [Section 5.1, Definition 3, Theorem 5.1] The same target mismatch occurs in the biclustering lower bound. The row partition G* in Definition 3 is defined by the pairs (k*_i, epsilon^r_i), but both parts of Theorem 5.1 bound the MMSE for x = 1{k*_1 = k*_2}, which ignores epsilon^r. The reduction in Eq. (27) and Appendix A.2 does not transfer an LD lower bound for this x to a lower bound on recovering G*. Thus the thresholds stated in (43) and (44), and the claimed dichotomy that poly-time row clustering can leverage column structure only above the column-clustering threshold, are derived for a different estimation problem. The computational-hardness conclusions for biclustering are not established even if the low-degree conjecture is granted.
minor comments (4)
  1. [Abstract and Section 1.1] The phrase 'we provide an almost full picture' is somewhat stronger than what is proved, given the open regime acknowledged in Section 6; the abstract could state the scope of the claims more cautiously.
  2. [Section 1.1, sparse clustering paragraph] The sentence 'which, depending on the regimes, can be as large as factor p n/K or a factor sqrt(K)' appears to contain a typo; the intended expression is likely sqrt(n/K) rather than p n/K.
  3. [Section 2.2, Theorem 2.5] The notation B_alpha and the quotient by S_l is introduced quickly; a short example or a reference to the appendix would improve readability.
  4. [Appendix A.2] The statement of Lemma A.2 and Proposition A.3 should clarify that they are tied to the specific partnership matrix 1{k*_i = k*_j} and do not automatically apply to symmetrized priors with additional sign variables.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: thresholds are derived from explicit priors and cumulant bounds; the low-degree conjecture is an external premise and the [28] self-citation is not load-bearing.

full rationale

The central derivation is self-contained. Proposition 2.1 is imported from Schramm and Wein [66], and Theorems 3.1, 4.1, and 5.1 bound the low-degree correlation via sums of squared cumulants, with pruning and graph-counting lemmas; the BBP-like thresholds appear from optimizing those bounds rather than from fitting the target threshold. The only unproven load-bearing input is the low-degree conjecture, explicitly labeled as a premise in Section 1: "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." That is an external assumption about a computational model, not a circular derivation. The self-citation to [28] for inequality (27) is minor: the same reduction is re-proved independently in Appendix A.2, and [28] is prior work not fitted to this paper. Section 6 honestly records a limitation of the [66] bound. The symmetrized priors in Definitions 2 and 3 target x = 1{k*_1 = k*_2} while the row partitions include ε signs; this is a potential target-mismatch or correctness concern, but a mismatch is not an input-output equivalence, so it is not scored as circularity here.

Assumptions & free parameters 2 free parameters · 6 assumptions · 0 invented entities

The central claim rests on the low-degree conjecture and on Bayesian priors with Gaussian means. The technique requires conditioning on latent variables and uses the Law of Total Cumulance. No new physical entities are introduced. The free parameters listed are prior scalings, not fits to data.

free parameters (2)
  • prior signal scale λ² = ¯Δ² σ² / p
    Chosen to parameterize the Bayesian prior so that the effective separation equals ¯Δ²; not fitted to data, but a modeling choice.
  • sparsity rate ρ = ¯s / p
    Sets the expected number of active columns in the sparse clustering prior; a parameter of the prior, not fitted to data.
assumptions (6)
  • domain assumption Low-degree conjecture: degree-D polynomials with D = O(log n) are a proxy for polynomial-time algorithms
    Sections 1 and 2.1; the interpretation of LD hardness as computational hardness relies on this unproven premise.
  • domain assumption Assumption 1 (Gaussian means prior): the ν_kl are i.i.d. N(0, λ²) independent of Z
    Section 2.1; used in Lemma 2.4 to derive simple conditional cumulants; central to the proof technique.
  • domain assumption Balancedness of partitions (Condition 24)
    Assumed for all three problems; needed for the upper-bound algorithms and threshold interpretations.
  • standard math Law of Total Cumulance (Lemma 2.3)
    Used to decompose cumulants conditionally on the latent variable Z in Theorem 2.5.
  • domain assumption Assumption 2 (η-homogeneity) for sparse clustering upper bounds
    Required for Corollary 4.5 and Corollary 4.7; not needed for the LD lower bound.
  • domain assumption Technical condition p ≥ D^5 in Theorem 3.1
    Ensures the counting bounds close; restricts the regime to p ≥ log^5 n for D = log n.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Computational lower bounds in latent models: clustering, sparse-clustering, biclustering." pith.science (2026). https://pith.science/paper/4G77OFB6

@misc{pith2026250613647,
  author       = {Pith},
  title        = {Pith review of: Computational lower bounds in latent models: clustering, sparse-clustering, biclustering},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/4G77OFB6}},
  note         = {Machine review of arXiv:2506.13647}
}
read the original abstract

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 Schramm and Wein (2022) 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.

Review history (2 revisions) →

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

  1. Phase Transition for Stochastic Block Model with more than $\sqrt{n}$ Communities

    stat.ML 2025-09 accept novelty 7.0 of 10

    For K >= sqrt(n), low-degree polynomials fail to recover stochastic block model communities below the Chin et al. threshold for all densities, while clique and self-avoiding path counting succeed above it for specific...

Reference graph

Works this paper leans on

98 extracted references · 74 canonical work pages · cited by 1 Pith paper

  1. [1]

    and MCSHERRY, F

    ACHLIOPTAS, D. and MCSHERRY, F. (2005). On Spectral Learning of Mixtures of Distributions. InLearning Theory (P. AUERand R. MEIR, eds.) 458–469. Springer Berlin Heidelberg, Berlin, Heidelberg

    2005

  2. [2]

    and SINOP, A

    AWASTHI, P., CHARIKAR, M., KRISHNASWAMY, R. and SINOP, A. K. (2015). The Hardness of Approximation of Eu- clidean k-Means. In31st International Symposium on Computational Geometry (SoCG 2015)34754–767. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. 28

    2015

  3. [3]

    and NADLER, B

    AZAR, E. and NADLER, B. (2024). Semi-supervised sparse gaussian classification: Provable benefits of unlabeled data. Advances in Neural Information Processing Systems3720132–20169

    2024

  4. [4]

    and WASSERMAN, L

    AZIZYAN, M., SINGH, A. and WASSERMAN, L. (2013). Minimax theory for high-dimensional gaussian mixtures with sparse mean separation. InAdvances in Neural Information Processing Systems2139–2147

    2013

  5. [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 Probability331643 – 1697

    2005

  6. [6]

    and WASSERMAN, L

    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 learning4

    2011

  7. [7]

    S., ELALAOUI, A., HOPKINS, S., SCHRAMM, T., WEIN, A

    BANDEIRA, A. S., ELALAOUI, A., HOPKINS, S., SCHRAMM, T., WEIN, A. S. and ZADIK, I. (2022). The Franz-Parisi criterion and computational trade-offs in high dimensional statistics.Advances in Neural Information Processing Systems3533831–33844

    2022

  8. [8]

    S., KUNISKY, D

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

    arXiv 2019

Show all 98 references
  1. [9]

    and XU, J

    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 Theory64 4872–4894

    2018

  2. [10]

    K., MOITRA, A

    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 Computing48687-735

    2019

  3. [11]

    and RIGOLLET, P

    BERTHET, Q. and RIGOLLET, P. (2013). Complexity Theoretic Lower Bounds for Sparse Principal Component Detection. InProceedings of the 26th Annual Conference on Learning Theory(S. SHALEV-SHWARTZand I. STEINWART, eds.).Proceedings of Machine Learning Research301046–1066. PMLR, P...

    2013

  4. [12]

    and BRESLER, G

    BRENNAN, M. and BRESLER, G. (2020). Reducibility and statistical-computational gaps from secret leakage. InConfer- ence on Learning Theory648–847. PMLR

    2020

  5. [13]

    B., LI, J

    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

    2020 arXiv

  6. [14]

    and HULEIHEL, W

    BRENNAN, M., BRESLER, G. and HULEIHEL, W. (2018). Reducibility and computational lower bounds for problems with planted sparse structure. InConference On Learning Theory48–166. PMLR

    2018

  7. [15]

    and RAKHLIN, A

    CAI, T., LIANG, T. and RAKHLIN, A. (2017). Computational and Statistical Boundaries for Submatrix Localization in a Large Noisy Matrix.The Annals of Statistics451403–1430

    2017

  8. [16]

    T., MA, J

    CAI, T. T., MA, J. and ZHANG, L. (2019). Chime: Clustering of high-dimensional Gaussian mixtures with EM algorithm and its optimality 1.Annals of Statistics471234–1267

    2019

  9. [17]

    and YANG, Y

    CHEN, X. and YANG, Y. (2021). Hanson–Wright inequality in Hilbert spaces with application toK-means clustering for non-Euclidean data.Bernoulli27586 – 614

    2021

  10. [18]

    and ZADIK, I

    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

    2024 arXiv

  11. [19]

    and BENDORY, T

    DADON, M., HULEIHEL, W. and BENDORY, T. (2024). Detection and recovery of hidden submatrices.IEEE Transactions on Signal and Information Processing over Networks1069–82

    2024

  12. [20]

    DASGUPTA, S. (1999). Learning mixtures of Gaussians. In40th Annual Symposium on Foundations of Computer Science (Cat. No.99CB37039)634-644

    1999

  13. [21]

    M., PITTAS, T

    DIAKONIKOLAS, I., KANE, D. M., PITTAS, T. and ZARIFIS, N. (2023). SQ Lower Bounds for Learning Mixtures of Separated and Bounded Covariance Gaussians. InProceedings of Thirty Sixth Conference on Learning Theory (G. NEUand L. ROSASCO, eds.).Proceedings of Machine Learning Resea...

    2023

  14. [22]

    M., PITTAS, T

    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 Theory195

    2023

  15. [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)

    2017

  16. [24]

    DIAKONIKOLAS, I., KANE, D. M. and STEWART, A. (2018). List-decodable robust mean estimation and learning mix- tures of spherical gaussians. InProceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing. STOC 20181047–1060. Association for Computing Machinery

    2018

  17. [25]

    DING, Y., KUNISKY, D., WEIN, A. S. and BANDEIRA, A. S. (2024). Subexponential-time algorithms for sparse PCA. Foundations of Computational Mathematics24865–914

    2024

  18. [26]

    L., MALEKI, A

    DONOHO, D. L., MALEKI, A. and MONTANARI, A. (2009). Message-passing algorithms for compressed sensing.Pro- ceedings of the National Academy of Sciences10618919

    2009

  19. [27]

    and HSU, D

    DUDEJA, R. and HSU, D. (2024). Statistical-computational trade-offs in tensor PCA and related problems via communi- cation complexity.The Annals of Statistics52131 – 156. https://doi.org/10.1214/23-AOS2331

    2024 doi

  20. [28]

    and VERZELEN, N

    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. AGRAWALand A. ROTH, eds.).Proceedings of Machine Learning Research2471646–1712. PMLR. COMPUTATIONAL LOWER...

    2024

  21. [29]

    and YANG, Z

    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

    2018 arXiv

  22. [30]

    and CHEN, Y

    FEI, Y. and CHEN, Y. (2018). Hidden Integrality of SDP Relaxations for Sub-Gaussian Mixture Models. InProceedings of the 31st Conference On Learning Theory.Proceedings of Machine Learning Research751931–1965. PMLR

    2018

  23. [31]

    and PERKINS, W

    FLORESCU, L. and PERKINS, W. (2016). Spectral thresholds in the bipartite stochastic block model. InConference on Learning Theory943–959. PMLR

    2016

  24. [32]

    GAMARNIK, D. (2021). The overlap gap property: A topological barrier to optimizing over random structures.Proceed- ings of the National Academy of Sciences118e2108492118

    2021

  25. [33]

    and ZHOU, H

    GAO, C., LU, Y., MA, Z. and ZHOU, H. H. (2016). Optimal estimation and completion of matrices with biclustering structures.Journal of Machine Learning Research171–29

    2016

  26. [34]

    (2021).Introduction to high-dimensional statistics.Monographs on Statistics and Applied Probability168

    GIRAUD, C. (2021).Introduction to high-dimensional statistics.Monographs on Statistics and Applied Probability168. CRC Press, Boca Raton, FL

    2021

  27. [35]

    and VERZELEN, N

    GIRAUD, C. and VERZELEN, N. (2019). Partial recovery bounds for clustering with the relaxedK-means.Mathematical Statistics and Learning1317–374

    2019

  28. [36]

    HARTIGAN, J. A. (1972). Direct clustering of a data matrix.Journal of the american statistical association67123–129

    1972

  29. [37]

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

    2018

  30. [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. In2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS)720-731. IEEE Computer Society, Los Alami...

    2017

  31. [39]

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

    2017

  32. [40]

    JIN, J., KE, Z. T. and WANG, W. (2017). Phase transitions for high dimensional clustering and related problems.The Annals of Statistics45

    2017

  33. [41]

    KEARNS, M. (1998). Efficient noise-tolerant learning from statistical queries.Journal of the ACM (JACM)45983–1006

    1998

  34. [42]

    and SINGH, A

    KOLAR, M., BALAKRISHNAN, S., RINALDO, A. and SINGH, A. (2011). Minimax localization of structural information in large noisy matrices.Advances in Neural Information Processing Systems24

    2011

  35. [43]

    S., WEIN, A

    KOTHARI, P., VEMPALA, S. S., WEIN, A. S. and XU, J. (2023). Is planted coloring easier than planted clique? InThe Thirty Sixth Annual Conference on Learning Theory5343–5372. PMLR

    2023

  36. [44]

    KUNISKY, D., WEIN, A. S. and BANDEIRA, A. S. (2019). Notes on computational hardness of hypothesis testing: Predic- tions using the low-degree likelihood ratio. InISAAC Congress (International Society for Analysis, its Applications and Computation)1–50. Springer

    2019

  37. [45]

    and CARAMANIS, C

    KWON, J. and CARAMANIS, C. (2020). The EM Algorithm gives Sample-Optimality for Learning Mixtures of Well- Separated Gaussians. InProceedings of Thirty Third Conference on Learning Theory(J. ABERNETHYand S. AGAR- WAL, eds.).Proceedings of Machine Learning Research1252425–2487. PMLR

    2020

  38. [46]

    and MASSART, P

    LAURENT, B. and MASSART, P. (2000). Adaptive estimation of a quadratic functional by model selection.Annals of Statistics281302–1338. MR1805785 (2002c:62052)

    2000

  39. [47]

    and RINALDO, A

    LEI, J. and RINALDO, A. (2015). Consistency of spectral clustering in stochastic block models.Ann. Statist.43215–237. MR3285605

    2015

  40. [48]

    and ZDEBOROVÁ, L

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

    2016

  41. [49]

    and LI, J

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

    2022

  42. [50]

    LÖFFLER, M., WEIN, A. S. and BANDEIRA, A. S. (2022). Computationally efficient sparse clustering.Information and Inference: A Journal of the IMA11

    2022

  43. [51]

    and ZHOU, H

    LU, Y. and ZHOU, H. H. (2016). Statistical and computational guarantees of lloyd’s algorithm and its variants.arXiv preprint arXiv:1612.02099

    2016 arXiv

  44. [52]

    and GAO, C

    LUO, Y. and GAO, C. (2024). Computational lower bounds for graphon estimation via low-degree polynomials.The Annals of Statistics522318–2348

    2024

  45. [53]

    and WU, Y

    MA, Z. and WU, Y. (2015). Computational Barriers in Minimax Submatrix Detection.The Annals of Statistics431089– 1116

    2015

  46. [54]

    MAO, C., WEIN, A. S. and ZHANG, S. (2023). Detection-recovery gap for planted dense cycles. InThe Thirty Sixth Annual Conference on Learning Theory2440–2481. PMLR

    2023

  47. [55]

    and SEDKI, M

    MARBAC, M. and SEDKI, M. (2017). Variable selection for model-based clustering using the integrated complete-data likelihood.Statistics and Computing271049–1063

    2017

  48. [56]

    and MICHEL, B

    MAUGIS, C. and MICHEL, B. (2011). A non asymptotic penalized criterion for Gaussian mixture model selection. ESAIM: Probability and Statistics1541–68

    2011

  49. [57]

    and WEIN, A

    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. 30

    2024

  50. [58]

    and FAN, Y

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

    2025 arXiv

  51. [59]

    NDAOUD, M. (2022). Sharp optimal recovery in the two component Gaussian mixture model.The Annals of Statistics50 2096 – 2126

    2022

  52. [60]

    and TSYBAKOV, A

    NDAOUD, M., SIGALLA, S. and TSYBAKOV, A. B. (2021). Improved clustering algorithms for the bipartite stochastic block model.IEEE Transactions on Information Theory681960–1975

    2021

  53. [61]

    NOVAK, J. (2014). Three lectures on free probability.Random matrix theory, interacting particle systems, and integrable systems6513

    2014

  54. [62]

    and WEI, Y

    PENG, J. and WEI, Y. (2007). Approximating k-means-type clustering via semidefinite programming.SIAM journal on optimization18186–205

    2007

  55. [63]

    RAFTERY, A. E. and DEAN, N. (2006). Variable selection for model-based clustering.Journal of the American Statistical Association101168–178

    2006

  56. [64]

    and VIJAYARAGHAVAN, A

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

    2017

  57. [65]

    and ORDENTLICH, O

    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

    2022

  58. [66]

    and WEIN, A

    SCHRAMM, T. and WEIN, A. S. (2022). Computational barriers to estimation from low-degree polynomials.The Annals of Statistics501833–1858

    2022

  59. [67]

    and NADLER, B

    SEGOL, N. and NADLER, B. (2021). Improved convergence guarantees for learning Gaussian mixture models by EM and gradient EM.Electronic Journal of Statistics154510 – 4544

    2021

  60. [68]

    and WEIN, A

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

    2025

  61. [69]

    and WANG, G

    VEMPALA, S. and WANG, G. (2004). A spectral algorithm for learning mixture models.Journal of Computer and System Sciences68841–860. Special Issue on FOCS 2002

    2004

  62. [70]

    and ARIAS-CASTRO, E

    VERZELEN, N. and ARIAS-CASTRO, E. (2017). Detection and feature selection in sparse mixture models.Annals of Statistics451920–1950

    2017

  63. [71]

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

    2025

  64. [72]

    WITTEN, D. M. and TIBSHIRANI, R. (2010). A Framework for Feature Selection in Clustering.Journal of the American Statistical Association105713–726

    2010

  65. [73]

    and PROUTIÈRE, A

    YUN, S. and PROUTIÈRE, A. (2014). Accurate Community Detection in the Stochastic Block Model via Spectral Algo- rithms.CoRRabs/1412.7335. COMPUTATIONAL LOWER BOUNDS31 APPENDIX A: TECHNICAL DISCUSSIONS All the results stated in this section are proved in Appendix H A.1. Sparse ...

    2014 arXiv

  66. [74]

    path" or a

    IfS̸=∅, then, for alli∈∪ {0}∪S{is,i′ s}, there existss̸=s ′∈{0}∪Ssuch thati∈{i s,i′ s}and i∈{i s′,i′ s′}. In particular,1,2∈supp(α S). LEMMAC.5.LetS⊆[l]such thatC x,β[S]̸= 0. ThenS∈S([l]) PROOF OFLEMMAC.5. Let us first suppose thatV[{0}∪S]is not connected and let us prove that...

  67. [75]

    path" or

    All the nodes ofG −, exceptu 1 andu 2, are of degree at least2. Together with the first point, this implies that all the nodes ofG−∪{(u 1,u 2)}are of degree at least2. Let us prove thatG − can be obtained with a finite number of operations "path" or "lollipop". To do so, we de...

  68. [76]

    lollipop

    All the nodes ofG −, exceptu 1 andu 2, are of degree at least2. It is clear thatG 0∈H, sinceG 0 satisfies the conditions of Lemma C.3. Lemma C.10 below implies that, ifG t∈H, thenG t−1 belongs toH. LEMMAC.10.LetG∈Hbe a non empty graph. Let us remove either a "lollipop" or a "p...

  69. [77]

    Since the absence ofedoes not disconnectG −∪ {(u1,u 2)}, so does the absence ofPand we get thatG ′−∪{(u 1,u 2)}is connected,

    Let us prove thatG ′−∪{(u 1,u 2)}is connected. Since the absence ofedoes not disconnectG −∪ {(u1,u 2)}, so does the absence ofPand we get thatG ′−∪{(u 1,u 2)}is connected,

  70. [78]

    The nodes along the pathPare not nodes ofG ′−∪{(u 1,u 2)}

    Let us prove that all the nodes ofG ′−∪{(u 1,u 2)}exceptu 1 andu 2 are of degree at least2. The nodes along the pathPare not nodes ofG ′−∪{(u 1,u 2)}. The nodes that are not extremities ofP have the same degree forG ′−∪{(u 1,u 2)}than forG −∪{(u 1,u 2)}. It remains to check th...

  71. [79]

    IfS̸=∅, then for allj∈col(α S)∪{0}, there existi ̸=i′∈∪s∈Sj{is,i′ s}such that bothi andi′ are in∪ s∈S\Sj{is,i′ s}

  72. [80]

    In particular, the second property implies that, as long asS̸=∅, we have{1,2}⊂supp(α S)

    For alli∈supp(α S)\{1,2},|(α S)i:|≥2. In particular, the second property implies that, as long asS̸=∅, we have{1,2}⊂supp(α S). LEMMAD.4.ForS⊆[l], ifC x,β[S]̸= 0, thenS∈S([l]). Pruning the other terms in (68) leads to, for allS∈S([l]), (69) |Cx,β[S]|≤ρ rαS 1 K |supp(αS)∪{1,2}|−...

  73. [81]

    LetC 1 andC 2 a partition ofS∪{0} with no edges ofWconnecting them

    Let us first suppose thatW[S∪{0}]is not connected. LetC 1 andC 2 a partition ofS∪{0} with no edges ofWconnecting them. We suppose by symmetry that0∈C 1. Then, the fam- ily of random variables((ε i,k∗ i )i∈∪s∈C1{is,i′ s},(zj)j∈∪s∈C1\{0}{js})is independent of the family ((εi,k∗ ...

  74. [82]

    Let us denotei this element

    Let us now suppose that there existsj 0∈col(αS)∪{0}with at most one element in∪ s∈Sj0 {is,i′ s} which is also in∪ s∈S\Sj0 {is,i′ s}. Let us denotei this element. Then,(ϵ i)is independent of (ϵisϵi′ s)s∈S\Sj0 . Indeed, since theϵ i’s are distributed as independent rademacher, t...

  75. [83]

    Lets 0 the unique element ofSsuch thati ∈supp(β s0); we supposei =i s0 for exemple

    Let us finally suppose that there existsi ∈supp(αS)\{1,2}with|(α S)i:|= 1. Lets 0 the unique element ofSsuch thati ∈supp(β s0); we supposei =i s0 for exemple. The random variableε i is symmetric and independent from all the other random variables. Hence, changingε i to−ε i doe...

  76. [84]

    By symmetry, we suppose thatα 2: = 0

    We suppose that eitherα 1: = 0orα 2: = 0. By symmetry, we suppose thatα 2: = 0. Then, the label k∗ 2 is independent of the random variables(X ij)ij∈α∪{k∗ 1}. And sincek∗ 2 follows a uniform law on [K], we directly deduce thatx=1 k∗ 1=k∗ 2 is also independent from(X ij)ij∈α∪{k∗...

  77. [85]

    εi0 is symmetric and independent from the other random variables

    We suppose that there existsi 0∈supp(α)such that P j∈[p]αi0j = 1and we shall prove thatκx,α = 0. εi0 is symmetric and independent from the other random variables. In particular,x,(Xij)ij∈α has the same distribution asx, (−1)1i=i0Xij ij∈α and soκ x,α =−κx,α. We deduceκx,α = 0

  78. [86]

    It is clear in that case that there does not exist any decompositionα=β 1 +...+β l withβ s ={(i s,js); (i′ s,js)}

    We suppose that there existsj 0∈[p]such that P i∈[n]αij0 = 1. It is clear in that case that there does not exist any decompositionα=β 1 +...+β l withβ s ={(i s,js); (i′ s,js)}. Hence, Theorem 2.5 ensures thatκ x,α = 0

  79. [87]

    Letβ 1 +...+β l =αwithβ s = {(is,js); (i′ s,js)}

    Let us suppose that the graphG − α∪{(u 1,u 2)}is not connected. Letβ 1 +...+β l =αwithβ s = {(is,js); (i′ s,js)}. Let us prove thatC x,β1,...,βl is null. The fact thatG − α∪{(u 1,u 2)}is disconnected implies that the graphWof[0,l]defined is Section D.1 is also disconnected. We...

  80. [88]

    Consiser any decomposition α=β 1 +...+β l withβ s ={(is,js); (i′ s,j′ s)}

    Let us suppose that there existsi ∈supp(α)\{1,2}with|α i:|= 1. Consiser any decomposition α=β 1 +...+β l withβ s ={(is,js); (i′ s,j′ s)}. Lets 0 be the only element such thati∈supp(βs0). It follows that1{k ∗ is0 =k∗ i′ s0 }is independent of(x,(1{k ∗ is =k∗ i′ s })s∈[l]\{s0})an...

  81. [89]

    PROOF OFLEMMAE.3

    The last point of the lemma is a direct consequence of Theorem 2.5. PROOF OFLEMMAE.3. Since we necessarily have1,2∈supp(α), there are at mostn m−2 possi- bilities for choosingsupp(α). Using the third point of Lemma E.2 together with the hypothesis n j∈[p],l ∗ j =l o ≤5 p L, fo...

  82. [90]

    We split the dataset randomly into two datasetsY (1) andY (2)

  83. [91]

    We computeˆv1,...,ˆvK the leading eigenvectors of Y (1) T Y (1) and we project orthogonallyY (2) ontoˆv1,...,ˆvK

  84. [92]

    We apply a low-dimensional clustering procedure on the projected datasetˆp Y (2)

  85. [93]

    Letδ 1,...,δ n i.i.d uniformly taken on{1,2}

    We perform Linear Discriminant Analysis in order to assign each point ofY (1) to one of the clusters ofˆp Y (2) . Letδ 1,...,δ n i.i.d uniformly taken on{1,2}. LetI 1 ={i∈[n],δ i = 1}andI 2 ={i∈[n],δ i = 2}. Let Y (1)∈R|I1|×p be the data matrix restricted toI 1 andY (2)∈R|I2|×...

  86. [94]

    Using Hoeffding Inequality, we deduce that, fort>0, P ||G∗ k∩I 1|− |G∗ k| 2 |≥t ≤2 exp −2t2 |G∗ k| . Takingt= |G∗ k| 4 , applying an union bound on allk∈[K], yields that the desired result holds with prob- abilily higher than1−2Kexp[−(min k=1,...,K|G∗ k|)/4]which is larger tha...

  87. [95]

    This concludes the proof of the lemma

    Hence,∥ˆp(µk)−ˆp(µl)∥2 =∥µk−µl∥2∥ˆp(y)∥2 =∥µk−µl∥2⟨y,ˆp(y)⟩2≥∥µk−µl∥2 4 . This concludes the proof of the lemma. PROOF OFLEMMAG.8. In the proof of this lemma, we writeA∈{0,1} n′×K for the assignment matrix defined byA ik =1i∈G∗ k,µ∈R K×p for the matrix of the means whosek-th r...

  88. [96]

    Using the hypothesis|⟨x,y⟩|≥ 1 2, we deduce that|⟨x,µ k−µl⟩|≥ ∆ 2 and therefore|⟨x,µ k⟩|≥ ∆ 4 or |⟨x,µl⟩|≥ ∆ 4

    We writey= µk−µl ∥µk−µl∥ and we compute xT (Aµ)T (Aµ)x= X k′∈[1,K] X a∈G∗ k′ ⟨µk′,x⟩ 2≥ n 4Kγ ⟨x,µk⟩2 +⟨x,µ l⟩2 . Using the hypothesis|⟨x,y⟩|≥ 1 2, we deduce that|⟨x,µ k−µl⟩|≥ ∆ 2 and therefore|⟨x,µ k⟩|≥ ∆ 4 or |⟨x,µl⟩|≥ ∆ 4 . Hence,x T (Aµ)T (Aµ)x≥ n 64γK ∆2. This concludes t...

  89. [97]

    Use the first datasetY (1) in order to estimate the setJ∗ of active columns

  90. [98]

    r γsK n [log(n) +γ 2] + log(n) +γ # ≥δB ∆2 8 −(c 1 + 2c2)[δB∨1]

    Use a clustering procedure to the second dataset, keeping only columns estimated in the first step. For the first step, we consider ˆJcollecting thescolumns ofY (1) with the largest euclidean norm. We recall the definition wJ∗ := min j∈J∗ X i∈[n] X2 ij . Next lemma states that...

Pith tools

Reviewed August 15, 2026 · model on record in the stance chip above.