PaperlayerView exact revision on arXiv

Source-linked AI summary

Statistical-Computational Tradeoffs in Planted Problems and Submatrix Localization with a Growing Number of Clusters and Submatrices

Yudong Chen, Jiaming Xu

arXiv:1402.1267v3stat.MLmath.ST

TL;DR

The paper asks how statistical and computational limits govern recovery of growing numbers of clusters and submatrices. It analyzes MLE, convexified MLE, and simple counting or thresholding procedures, establishing four recovery regimes and sharp minimax boundaries. The results show progressively weaker statistical performance for faster algorithms and suggest that the information limit may not be achievable in polynomial time.

  • Problem

    The paper studies recovery of hidden clusters and elevated submatrices under noisy observations, especially when their number grows with problem size.

  • Method

    The paper characterizes success and failure conditions for the MLE, its convex relaxation, and simple counting or thresholding algorithms across planted clustering and submatrix localization.

  • Results

    The parameter space divides into impossible, hard, easy, and simple regimes with successively faster algorithms and weaker statistical performance; the MLE attains the minimax recovery boundary.

  • Takeaways & Limitations

    The results expose statistical-computational tradeoffs in high-rank planted problems and suggest that polynomial-time algorithms may not attain the information limit.

  • Takeaways & Limitations

    The paper does not prove its conjecture that no polynomial-time algorithm can succeed in the hard regime, and a rigorous proof is difficult with current techniques.

Abstract

from arXiv · show

We consider two closely related problems: planted clustering and submatrix localization. The planted clustering problem assumes that a random graph is generated based on some underlying clusters of the nodes; the task is to recover these clusters given the graph. The submatrix localization problem concerns locating hidden submatrices with elevated means inside a large real-valued random matrix. Of particular interest is the setting where the number of clusters/submatrices is allowed to grow unbounded with the problem size. These formulations cover several classical models such as planted clique, planted densest subgraph, planted partition, planted coloring, and stochastic block model, which are widely used for studying community detection and clustering/bi-clustering. For both problems, we show that the space of the model parameters (cluster/submatrix size, cluster density, and submatrix mean) can be partitioned into four disjoint regions corresponding to decreasing statistical and computational complexities: (1) the \emph{impossible} regime, where all algorithms fail; (2) the \emph{hard} regime, where the computationally expensive Maximum Likelihood Estimator (MLE) succeeds; (3) the \emph{easy} regime, where the polynomial-time convexified MLE succeeds; (4) the \emph{simple} regime, where a simple counting/thresholding procedure succeeds. Moreover, we show that each of these algorithms provably fails in the previous harder regimes. Our theorems establish the minimax recovery limit, which are tight up to constants and hold with a growing number of clusters/submatrices, and provide a stronger performance guarantee than previously known for polynomial-time algorithms. Our study demonstrates the tradeoffs between statistical and computational considerations, and suggests that the minimax recovery limit may not be achievable by polynomial-time algorithms.

1 Introduction

The paper studies how statistical difficulty and computational cost interact in recovering growing numbers of clusters or submatrices. It identifies four regimes with progressively faster algorithms, while showing gaps between information-theoretic and polynomial-time recovery.

  • Motivation: Recovery becomes harder with noisier observations, smaller structures, and more clusters, creating distinct statistical and computational limits.The model parameters include cluster size, edge-density contrast, submatrix mean, and the number of hidden structures.
  • The Four Regimes: The impossible regime permits no successful algorithm, whereas the hard regime is recoverable by the computationally expensive MLE.The hard regime has no known polynomial-time algorithm that succeeds.
  • The Four Regimes: The easy regime is recovered by a polynomial-time convexified MLE, which provably fails in the hard regime.The convexified MLE replaces the discrete clustering constraint with trace-norm and linear constraints.
  • The Four Regimes: The simple regime is recovered by counting or thresholding, but this procedure fails in harder regimes because it cannot separate clusters as effectively.For α = 1/4, the simple, polynomial-time, and intractable algorithms succeed when β exceeds 0.75, 0.625, and 0.25, respectively.
  • Implications: The MLE establishes the minimax recovery boundary, while polynomial-time guarantees improve previous results but may remain separated from the information limit.The results apply to growing numbers of clusters or submatrices and to several classical planted models.
  • Discussions: Convex relaxations are much more powerful than simple counting for multiple clusters or submatrices because they separate structures rather than merely identify one.This contrasts with rank-one settings, where prior work found similar order-wise performance for simple and convex methods.

2 Main Results for Planted Clustering

For planted clustering, the paper characterizes recovery through information and computational thresholds, from impossibility to MLE, convexified MLE, and counting-based procedures. The results establish tight minimax boundaries up to constants while identifying regimes where polynomial-time methods lose statistical performance.

  • Model reduction: Flipping the adjacency matrix reduces the p < q case to the analyzed p > q case, transferring both achievability and converse results.The transformed graph uses complementary in-cluster and cross-cluster edge probabilities.
  • Impossible and hard regimes: The impossible regime is information-theoretically unrecoverable, while the MLE succeeds at the minimax recovery boundary up to constant factors.The boundary follows from matching theorem conditions based on the information in the graph and MLE achievability.
  • Easy regime: The convexified MLE replaces the discrete clustering constraint with a trace-norm constraint and linear constraints, yielding a polynomial-time method for the easy regime.The true cluster matrix remains feasible because its trace norm equals rK.
  • Easy regime: The convexified MLE can be statistically sub-optimal because an additional term creates a stricter cluster-size requirement than the MLE condition.Its converse shows failure even when the exact number and sizes of clusters are supplied.
  • Computational limits: The convex relaxation matches the recovery limit up to constants when pK log n = Ω(nq) and log K = Ω(log n), eliminating the hard regime in that setting.A conjectured computational boundary is also stated for p = 2q = n^-α and K = n^β, with β = α.
  • Simple regime: Counting degrees and common neighbors succeeds in the simple regime but is strictly weaker than the convexified MLE for separating multiple clusters.Its limitation is a variance barrier arising from fluctuations in degrees and common-neighbor counts.

3 Main Results for Submatrix Localization

Submatrix localization asks for recovery of multiple disjoint elevated submatrices, including in a high-rank setting where their number can grow with problem dimensions. The results identify four regimes—impossible, hard, easy, and simple—with progressively faster algorithms succeeding under progressively stronger conditions.

  • Model: The model partitions rK_L rows and rK_R columns into r disjoint clusters, with mean μ inside paired submatrices and zero mean elsewhere.The goal is to recover all hidden submatrix locations from A.
  • Model: The high-rank setting allows r, K_L, K_R, and μ to scale with n_L and n_R, including an unbounded number of submatrices.The single-submatrix case r = 1 is a special case of this model.
  • Impossible regime: The impossible regime is an information barrier in which the minimax error remains large, so no algorithm can reliably locate the submatrices.The lower bound applies to arbitrary measurable estimators under the stated Gaussian and size conditions.
  • Hard regime: The hard regime is minimax-optimal up to constants: the combinatorial MLE succeeds when its condition holds, while the impossible-regime condition fails.This achievability result holds even when r grows nearly linearly, such as r = O(n/log n) when n_L = n_R = n.
  • Easy regime: The convexified MLE succeeds in the easy regime but fails below its boundary, which is μ^2 ≍ n/K^2 up to logarithmic factors.For n_L = n_R = n and K_L = K_R = K, success is guaranteed when μ^2 ≳ K log n + n/K^2.

4 Discussion and Future Work

The paper concludes that planted clustering and submatrix localization exhibit a hierarchy of algorithms trading computational speed for statistical power. It also identifies unresolved questions about computational hardness, technical assumptions, finer tradeoff spectra, and broader model settings.

  • Discussion: Successively faster algorithms succeed in successively smaller parameter regions, revealing a tradeoff between statistical and computational performance.The results apply in the high-rank setting with a growing number of clusters or submatrices.
  • Discussion: The paper suggests that the information limit may not be achievable by polynomial-time algorithms, while noting that computational hardness in the hard regime remains conjectural.The convexified MLE is conjectured to achieve the computational limit order-wise, but the conjecture is not proved.
  • Future work: Future work includes removing technical assumptions, identifying a finer continuum of tradeoffs, handling overlapping structures and unknown parameters, and proving the hard-regime conjectures.

5 Proofs for Planted Clustering

The planted clustering proof section fixes the model orientation and separates clustered from isolated nodes through two population counts.

  • Setup: The analysis assumes p > q, so within-cluster edges are more likely than cross-cluster edges.
  • Setup: There are n_1 = rK non-isolated nodes belonging to clusters and n_2 = n − rK isolated nodes outside all clusters.
  • Setup: The proof uses these counts to characterize recovery in the planted clustering model.

5.1 Proof of Theorem 2.1 and Corollary 2.2

The proof establishes planted-clustering impossibility through information-theoretic bounds and carefully constructed alternative clusterings. Fano’s inequality and combinatorial ambiguity arguments yield large minimax error under the theorem’s conditions.

  • Combining the lemmas: The theorem follows by combining the information-theoretic lemma with the local-ambiguity lemmas and translating divergence bounds into the stated parameter conditions.The proof treats separate parameter subcases before applying the appropriate lemma.
  • Information-theoretic argument: Fano’s inequality converts a bound on mutual information between the planted clustering and graph into a lower bound on minimax recovery error.The proof samples clusterings uniformly and bounds the information carried by the adjacency matrix.
  • Information-theoretic argument: A sufficient condition on the information quantity implies minimax error at least 1/2 through the entropy and mutual-information calculation.
  • Alternative hypotheses: The proof constructs many alternative cluster matrices by swapping a clustered node with another node, then bounds pairwise divergences between the induced graph distributions.This construction controls the number of distinguishable hypotheses used in the information bound.
  • Combinatorial ambiguity: The proof also creates graph ambiguities from disconnected or betrayed nodes, showing that such local configurations force estimation error for every estimator.The maximum-likelihood argument pairs clusterings with equal or greater likelihood on ambiguous graphs.
  • Combinatorial ambiguity: Second-moment bounds show that the ambiguity events occur with sufficiently large probability under the relevant conditions.The argument bounds the probability of disconnected nodes and combines symmetric events across clusters.

5.2 Proof of Theorem 2.3 and Corollary 2.4

The proof establishes recovery by showing the true cluster matrix uniquely optimizes the likelihood objective with high probability. It controls random fluctuations uniformly over feasible alternatives using concentration bounds, combinatorial counting, and divergence assumptions.

  • Proof strategy: Recovery follows once the objective gap Δ(Y) is positive for every feasible Y ≠ Y*.The gap is decomposed into an expectation term and a fluctuation term.
  • Proof strategy: The expectation contribution equals (p − q)d(Y), while the fluctuation is controlled through centered Bernoulli sums.For each fixed feasible Y, Chernoff bounds control the two fluctuation components.
  • Uniform control: Equivalence classes group feasible matrices sharing the relevant support pattern, enabling uniform control over alternatives with the same d(Y).A combinatorial lemma bounds the number of matrices and equivalence classes at each distance level.
  • Uniform control: KL-divergence assumptions on D(q∥p) and D(p∥q) provide the logarithmic separation needed for the probability bounds.The proof applies separate divergence conditions involving log(γrK)/K and log n/K.
  • Conclusion: With high probability, Y* is the unique optimal solution.The theorem follows after combining the fluctuation bounds and divergence conditions.

5.3 Proof of Theorem 2.5

The proof analyzes the convexified MLE for planted clustering and submatrix localization through concentration of the centered data matrix and nuclear-norm optimality. Under the theorem conditions, the true cluster matrix is shown to be the unique optimizer with high probability.

  • Unified setup: The argument treats planted clustering and submatrix localization with unified dimensions, cluster sizes, characteristic matrices, and projections.For planted clustering, left and right dimensions and cluster sizes coincide.
  • Unified setup: The signal matrix is represented by ν and its population counterpart Ā, with ν = p − q for clustering and ν = μ for localization.The proof relies on concentration of A − Ā.
  • Concentration bounds: A concentration proposition controls spectral and projected infinity norms of A − Ā with probability at least 1 − n^-10.The required bounds are established separately for the two models.
  • Optimality: A nuclear-norm subgradient and the convex program’s constraints show that every feasible Y ≠ Y* has strictly worse objective value.The proof concludes that Y* is the unique optimizer.
  • Concentration bounds: For planted clustering, matrix Bernstein and related bounds control the centered adjacency matrix under Kp(1 − q) ≥ c1 log n.The resulting spectral norm bound holds with probability at least 1 − n^-10.

5.5 Proof of Theorem 2.9

The proof of the simple thresholding theorem analyzes node degrees and common-neighbor counts using binomial decompositions, large-deviation bounds, and independence constructions. Under the stated conditions, all three thresholding steps recover isolation status and cluster assignments with high probability, while complementary cases produce errors.

  • Identifying isolated nodes: Node degrees decompose into independent binomial contributions from within-cluster and between-cluster edges.Non-isolated nodes have Bin(K−1,p) and Bin(n−K,q) components, while isolated nodes have Bin(n−1,q) degrees.
  • Recovering clusters: With probability at least 1 − 2n^-1, threshold comparisons separate same-cluster from different-cluster pairs and correctly identify the true clusters.The separating threshold is based on (p − q)^2K together with background terms.
  • Identifying isolated nodes: Dependence caused by adjacency-matrix symmetry is the main technical hurdle before applying large-deviation bounds.The proof partitions nodes and edges to obtain suitable independence.
  • Identifying isolated nodes: With probability at least 1/4, the isolation test misclassifies a selected node in each of the two parameter cases.Case 1 incorrectly declares a non-isolated node isolated; Case 2 incorrectly declares an isolated node non-isolated.
  • Recovering clusters: Common-neighbor counts have different expectations for node pairs within the same cluster and across different clusters.The proof compares these expectations using binomial decompositions and Bernstein bounds.

6 Proofs for Submatrix Localization

The submatrix-localization proofs establish lower bounds through Fano’s inequality and upper or failure results through objective-gap, KKT, concentration, and thresholding arguments. They show both when recovery succeeds and when convex or simple procedures fail under weaker signal conditions.

  • Minimax lower bound: Fano constructions perturb one side of the biclustering assignment to bound minimax recovery error.The alternatives differ by swapping nodes between clusters while preserving the other side.
  • Minimax lower bound: If (μ1 − μ2)^2 is at most the stated logarithmic threshold, the minimax error probability is at least 1/2.The conclusion follows from KL-divergence control and the cardinality of the alternative family.
  • Convex recovery: For the convex program, the objective gap decomposes into μd(Y) plus a centered sub-Gaussian fluctuation term.A union bound over equivalence classes controls the fluctuation uniformly over feasible matrices.
  • Convex recovery: KKT-based contradictions show that Y* is not optimal when the signal is below the convex program’s sufficient-recovery condition.The proof derives a lower bound on a dual quantity that conflicts with the theorem assumption.
  • Simple thresholding: Simple thresholding succeeds by separately identifying isolated nodes, recovering left and right clusters, and associating corresponding clusters.Each step is supported by concentration and union bounds under the theorem conditions.
  • Simple thresholding: When μ^2K_R is sufficiently small relative to n_R log n_L, thresholding misclassifies isolated and non-isolated nodes with high probability.The proof constructs nodes whose row sums cross the isolation threshold in the wrong direction.

A Proof of Lemmas 4 and 7

The proof converts candidate matrices into ordered partitions, labels clusters by overlap with the true clusters, and bounds candidate counts through misclassification structure. These bounds establish the lemma’s first part and control equivalent-class cardinalities.

  • Partition construction: Each candidate matrix induces new left and right partitions by grouping identical rows and columns, with all-zero nodes placed in isolated sets.The partitions contain r clusters of sizes KL and KR, plus isolated left and right nodes.
  • Cluster labeling: Clusters are labeled first when their overlap with a true cluster exceeds half its size, then remaining clusters are labeled through corresponding right-side overlaps.Unlabeled clusters are labeled arbitrarily after the overlap-based steps.
  • Counting reduction: The resulting partitions satisfy properties (A0)–(A2), so the number of candidates at distance t is bounded by the number of ordered partitions satisfying those properties.This is the counting reduction stated in equation (85).
  • Misclassification bounds: 4t/KR and 4t/KL bound the numbers of misclassified non-isolated left and right nodes, respectively, and the same bounds extend to isolated nodes.The extension follows because the cluster-size constraint forces a misclassified isolated node to produce a misclassified non-isolated node.
  • Final enumeration: The candidate count is then bounded by choosing misclassified-node identities and assigning them to clusters or isolation, yielding the lemma’s first-part bound.A similar argument using only non-isolated nodes bounds equivalence-class cardinalities.

B Proof of Lemma 5

The proof derives one binary relative-entropy inequality from another by substitution, then bounds the divergence separately according to whether p is at most or greater than 8q.

  • Reduction: Inequality (55) follows from (54) after substituting p = 1 − q′ and q = 1 − p′.Thus, the proof only needs to establish inequality (54).
  • Preliminary bound: The derivation uses x log x ≥ x − 1 for x ∈ [0, 1] before splitting the analysis into two cases.The case split is based on the relative sizes of p and q.
  • Case 1: p ≤ 8q: When p ≤ 8q, the divergence D(p∥q) is bounded using the relation from equations (35) and (36).The displayed passage begins the bound as D(p∥q) ≤ (p−q)^2 ..., but its remainder is not present.
  • Case 2: p > 8q: When p > 8q, the proof bounds D(p∥q) through p log p and uses p > 8q with 8 > e^2 to control the logarithmic term.The passage indicates a resulting bound involving p + q, but the displayed expression is incomplete.

C The Bernstein Inequality

The appendix states Bernstein’s inequality for independent, almost surely bounded random variables and introduces the associated variance parameter for the resulting probability bound.

  • Theorem statement: Bernstein’s theorem applies to independent random variables X1, ..., XN satisfying |Xi| ≤ M almost surely.The theorem also defines σ² from the variables’ aggregate variability.
  • Application: The theorem’s probability consequence is used after defining the uniform bound M and variance quantity σ².The supplied consequence passage is truncated and does not expose the complete probability expression.
Loading 1402.1267v3…