PaperlayerView exact revision on arXiv

Source-linked AI summary

Computational barriers in minimax submatrix detection

Zongming Ma, Yihong Wu

arXiv:1309.5914v4math.STcs.IT

TL;DR

The paper studies how computational constraints alter minimax submatrix detection in Gaussian noise. It uses asymptotically equivalent discretized models and planted-clique reductions to characterize the resulting computational-statistical tradeoff. The main result is a sparsity-dependent phase transition, alongside consequences for support recovery and loss-dependent estimation hardness.

  • Problem

    The paper asks how much statistical optimality must be sacrificed when computationally efficient procedures are required for submatrix detection.

  • Method

    The paper combines asymptotically equivalent discretized Gaussian models with a randomized polynomial-time reduction from planted clique.

  • Results

    The paper establishes a sparsity-dependent phase transition: efficient detection is substantially penalized for α∈(0,2/3), while no statistical penalty occurs for α∈(2/3,1).

  • Takeaways & Limitations

    Computational hardness affects submatrix detection, support recovery, and minimax estimation differently across sparsity regimes and loss functions.

  • Takeaways & Limitations

    The stated sub-polynomial gap follows from the planted clique hypothesis, while a logarithmic gap may potentially be narrowed by better reductions or testing procedures.

Abstract

from arXiv · show

This paper studies the minimax detection of a small submatrix of elevated mean in a large matrix contaminated by additive Gaussian noise. To investigate the tradeoff between statistical performance and computational cost from a complexity-theoretic perspective, we consider a sequence of discretized models which are asymptotically equivalent to the Gaussian model. Under the hypothesis that the planted clique detection problem cannot be solved in randomized polynomial time when the clique size is of smaller order than the square root of the graph size, the following phase transition phenomenon is established: when the size of the large matrix $p\to\infty$, if the submatrix size $k=Θ(p^α)$ for any $α\in(0,{2}/{3})$, computational complexity constraints can incur a severe penalty on the statistical performance in the sense that any randomized polynomial-time test is minimax suboptimal by a polynomial factor in $p$; if $k=Θ(p^α)$ for any $α\in({2}/{3},1)$, minimax optimal detection can be attained within constant factors in linear time. Using Schatten norm loss as a representative example, we show that the hardness of attaining the minimax estimation rate can crucially depend on the loss function. Implications on the hardness of support recovery are also obtained.

1. Introduction.

The paper asks how computational constraints affect statistically optimal submatrix detection and develops a complexity-theoretic framework based on discretized Gaussian models and planted-clique reductions. It identifies a sparsity-dependent transition: computational procedures are substantially penalized for highly sparse submatrices but can attain optimal detection in a moderately sparse regime, with consequences for estimation and support recovery.

  • Problem formulation: The submatrix problem tests a zero-mean Gaussian matrix against alternatives containing a k×k block whose entries are at least λ.The key parameters are matrix dimension p, block size k, and signal magnitude λ.
  • Problem formulation: Reliable detection is statistically possible when the optimal total error E* tends to zero, but enumerating all k×k submatrices is computationally intensive.The paper asks whether computationally efficient tests can achieve the statistically optimal boundary.
  • Computational framework: The paper discretizes the Gaussian model because finite-bit representations are needed to define computational complexity rigorously, while preserving asymptotic statistical equivalence.The framework addresses the mismatch between continuous Gaussian observations and finite-precision computation.
  • Computational framework: Under the planted clique hypothesis, a randomized polynomial-time reduction maps graph instances to matrix instances and characterizes when efficient reliable detection is possible or impossible.The planted clique benchmark assumes detection is not randomized-polynomial-time solvable for clique sizes smaller than the square root of graph size.
  • Phase transition: For β♯ < β < β*, detection is statistically possible but computationally intractable under the planted clique hypothesis.This intermediate region separates the statistical detection boundary from the efficiently computable boundary.
  • Phase transition: When α∈(0,2/3), efficient procedures require substantially higher signal-to-noise ratio, whereas for α∈(2/3,1), computational constraints incur no statistical penalty.The transition is described for k growing as a power of p and is accompanied by implications for support recovery and loss-dependent estimation hardness.

2. Test statistics for submatrix detection.

The section introduces linear, scan, and maximum test statistics for submatrix detection and states error guarantees for the linear and scan tests under their respective conditions.

  • Three statistics are studied: the linear test, the scan test, and the maximum test.
  • Lemma 1 provides nonasymptotic Type-I + II error bounds for tests based on these statistics.
  • The linear test’s error tends to zero when the first condition in (6) holds.
  • The scan test’s error tends to zero under the second condition in (6) when its threshold constant is sufficiently small.
  • Bounds for the maximum statistic are later used to establish achievability.

3. Asymptotically equivalent discretized model.

The paper addresses the ill-defined computational complexity of Gaussian testing by discretizing the experiment while preserving its statistical difficulty through Le Cam asymptotic equivalence.

  • Gaussian observations lack finite-bit representations, making computational complexity ill defined for tests on the original model.
  • The proposed paradigm aims to quantify computational complexity for continuous distributions and preserve the original problem’s statistical difficulty.
  • The paper achieves both goals by discretizing the original Gaussian experiment.
  • The quantization map [·]t rounds real values onto the dyadic grid 2^-tZ.

Discretized models.

The discretized model applies coordinatewise quantization to Gaussian data, yielding finite-bit observations whose testing complexity is well defined while retaining the original testing formulation.

  • Quantization extends componentwise from real numbers to matrices through [A]t = ([Aij]t).
  • The discretized testing problem uses the quantized data [X]t in place of the original observations.
  • The induced discrete distribution is supported on the grid (2^-tZ)^{p×p}.
  • Each quantized matrix can be represented by finitely many bits, so computational complexity is well defined for tests on the discretized data.
  • With t = Θ(log p), the quantized data have coordinate entropy H([Xij]t) = t + O(1) as t →∞.
  • The worst-case Type-I + II error and optimal error are defined analogously for the discretized hypotheses.
  • The paper studies quantization accuracy of order p^-c by taking t = Θ(log p).

Asymptotic equivalence.

The discretized Gaussian experiment is asymptotically equivalent to the original experiment under logarithmic quantization precision, so discretization preserves asymptotic testing performance.

  • Le Cam distance measures the discrepancy between statistical experiments through transition kernels and their induced distributions.
  • Two experiment sequences are asymptotically equivalent when their Le Cam distance tends to zero.
  • For t ≥ (3 + ε)log_2 p, the Gaussian and discretized experiment sequences are asymptotically equivalent.
  • Theorem 1 bounds the distance between the Gaussian and discretized experiments by 2p^2 2^(-2t/3).
  • Because the Le Cam distance vanishes, discretized-data testing has asymptotically unchanged statistical performance.
  • Linear and scan tests applied to quantized data attain vanishing error under their respective detection conditions.
  • Restricting tests to the σ-algebra generated by quantization cells makes each test constant on those cells and preserves the testing hypotheses’ equivalence.

4. Complexity theoretic limits.

The paper connects submatrix detection to planted clique to characterize computational limits. Under the planted clique hypothesis, sparse submatrices incur a polynomial statistical penalty, while sufficiently larger submatrices permit efficient optimal detection.

  • Planted clique connection: The planted clique problem supplies the computational-hardness benchmark for submatrix detection.The reduction relates randomized polynomial-time submatrix tests to planted clique tests.
  • Computational model: Randomized polynomial-time tests are algorithms with binary outputs, external randomness, and polynomially bounded running time.These tests are identified with the BPP complexity class.
  • Sparse regime: For k = Θ(p^α) with α ∈ (0,2/3), efficient detection requires a higher signal level than the statistical optimum.When α ∈ (0,1/2), the lower bound includes a logarithmic factor; when α ∈ [1/2,2/3), it is Ω(p^(1−2α−δ)) for any δ > 0).
  • Sparse regime: The efficient signal requirement exceeds the statistical optimum by a polynomial factor in p in the sparse regime.Thus computational complexity severely limits statistical performance when α ∈ (0,2/3).
  • Less sparse regime: When k ≥ p^α for some α > 2/3, the condition p/k^2 → ∞ dominates both bounds and a linear-complexity test attains statistically optimal detection.The relevant statistics Tlin and Tmax both have linear complexity.
  • Open gap: The sub-polynomial gap p/k^(2+δ) versus p/k^2 follows directly from the planted clique hypothesis, while a logarithmic gap may be reducible.The paper leaves improved reductions or spectral procedures as future work.

Randomized reduction.

The reduction maps planted-clique adjacency matrices into submatrix-detection instances through Gaussianization, partitioning, averaging, and quantization. The discretized construction preserves the relevant distributions while remaining computable in randomized polynomial time.

  • Block construction: The reduction partitions the Gaussianized matrix into ℓ^2 p × p blocks and averages them after scaling by ℓ.These steps produce the p × p output matrix used for submatrix detection.
  • Gaussianization: Gaussianization maps random edges and clique edges approximately to N(0,1) and N(µ,1) variables, respectively.The construction uses distributions F0 and F1 whose total variation distances from the target Gaussian laws are controlled.
  • Alternative support: The reduction’s induced prior is supported on matrices containing a nonzero rectangular submatrix with row and column supports between k and 20k.This support property is later used to study estimation hardness.
  • Reduction guarantee: A submatrix detector yields a planted-clique test with nearly the same error probability, up to the reduction’s approximation error.The resulting planted-clique test has Type-I + II error bounded by ε + β.
  • Complexity: The continuous reduction has ill-defined bit complexity because it processes continuous random variables, motivating the quantization step.The discretized construction addresses this issue in a rigorous complexity-theoretic sense.
  • Discretization: Quantization replaces the continuous auxiliary variables and output with discrete versions, using a finer input grid to control output approximation error.Choosing w > t is essential for controlling the error introduced by quantizing the input.
  • Complexity: For the regimes considered, N = O(p^2) and M,w,t = O(log^2 p), making the discretized reduction randomized polynomial-time.Its computation uses O(N^2T) random bits and O(M^(2w)T + N^2(log M + w + t)) operations.

5. Discussion.

The discussion establishes computational gaps for submatrix detection and extends the hardness analysis to support recovery and matrix estimation. It also shows that estimation hardness depends on the loss, with Schatten norms exhibiting different computational behavior across q.

  • 5. Discussion.: The planted-clique-based hardness result creates a phase transition between statistically optimal performance with and without computational constraints.The paper studies this transition through discretized models while retaining asymptotic statistical equivalence to the Gaussian setting.
  • 5.1. Support recovery.: Support recovery requires stronger signal than detection, and its computational barrier is at least a constant-factor version of the detection barrier.A support estimator can be converted into a detector by thresholding the sum over the estimated support.
  • 5.1. Support recovery.: For k = O(p^α) with α < 2/3, computationally efficient support recovery cannot achieve the statistically required signal level under the planted-clique hypothesis.The corresponding question for statistically optimal support recovery remains open when k = Θ(p^α) with α > 2/3.
  • 5.2. Hardness of estimation depends on norm.: Entrywise thresholding is near optimal among computationally efficient estimators for quadratic norms, including Schatten-q norms exactly when q ∈ [2,∞].The comparison is between computationally efficient upper bounds and the minimax rate obtained for the estimation problem.
  • 5.2. Hardness of estimation depends on norm.: For Schatten-q loss, q ∈ [1,2] permits polynomial-time estimation within a logarithmic factor of the minimax rate, whereas q > 2 can impose computational hardness.When q ∈ (2,∞] and k = Θ(p^α) for α ∈ (0, 2/(2+q)), entrywise thresholding is optimal within a sub-polynomial factor among randomized polynomial-time estimators.

6. Proofs.

The proofs establish the reduction machinery connecting planted-clique instances to submatrix models and control the resulting distributional approximations. Total variation bounds, conditioning, and Gaussian mean calculations support the reduction's validity.

  • 6. Proofs.: The proof section supplies the deferred proofs for the paper's main theorems and supporting lemmas.The proofs of Theorem 1 and Lemmas 5 and 6 are deferred to the supplement, while the displayed section develops the remaining arguments.
  • 6. Proofs.: A coupling argument bounds total variation between product distributions by the sum of coordinatewise discrepancies.Independent optimal couplings are combined into a product coupling, after which the union bound gives the result.
  • 6. Proofs.: The planted-clique reduction splits the clique vertices into two parts and embeds their cross-product into a Gaussian matrix with elevated means.Conditioned on the planted set, entries in the cross-product have mean µ and unit variance, while other entries have mean zero and unit variance.
  • 6. Proofs.: The transformed matrix is close in total variation to a mixture of submatrix alternatives, using data processing and conditioning on a high-probability event.For fixed planted vertices, the transformed matrix has independent Gaussian entries and corresponds to a parameter in the submatrix model on the good event.
  • 6. Proofs.: For rows and columns intersecting the planted vertex sets, the transformed Gaussian entries have means at least µ.This lower bound supplies the elevated-mean structure needed for the reduction to a submatrix alternative.
Loading 1309.5914v4…