Computational barriers in minimax submatrix detection

Introduction

Statistical inference of structured large matrices lies at the heart of many applications involving massive datasets, such as matrix completion, functional genomics, community detection and clustering; see, for instance, and the references therein. Many of these detection and estimation problems have been investigated from a decision theoretic viewpoint, where one first establishes a minimax lower bound for any test or estimator and then constructs a specific procedure which attains the lower bound within a constant or logarithmic factor.

An important element absent from the foregoing decision theoreticparadigm is computational complexity. This aspect is especially relevant in the context of high-dimensional statistical inference, where computationally efficient procedures (e.g., convex programming, iterative algorithms, etc.) are highly desirable. However, it has been empirically observed in several basic detection and estimation problems that popular low-complexity algorithms fail to attain the minimax rates; see, for example, . This invites the following question: how much do we need to back off from the statistical optimality due to computational complexity constraints? In this paper, we revisit the sparse submatrix detection problem that has been studied in , where the goal is to detect a small submatrix with elevated mean in a large noisy matrix. Motivations for this detection problem include biclustering for analyzing microarray data and community detection in social networks , etc.

In this problem, the key parameters are the matrix dimension $p$, the block size $k$ and the signal magnitude $\lambda$. Clearly, it is easier to detect the submatrix if either $k$ or $\lambda$ increases. Throughout the paper, we focus on the asymptotic setting where $p$ tends to infinity and both $k=k(p)$ and $\lambda=\lambda(p)$ are functions of $p$, though we typically drop the explicit dependence on $p$ for conciseness.

The optimal total probability of error is denoted by

the necessary and sufficient condition for reliably detecting the submatrix has been characterized by Butucea and Ingster (, Theorems 2.1 and 2.2): ${\mathcal{E}}^{*}\to 0$ if

and, conversely, ${\mathcal{E}}^{*}\to 1$ if

From this point forward, we say reliable detection is statistically possible if ${\mathcal{E}}^{*}\to 0$ and a sequence of tests $\{\phi_{p}\}$ reliably detects the submatrix if ${\mathcal{E}}(\phi_{p})\to 0$.

To reliably detect the submatrix under condition (6), Butucea and Ingster proposed a test involving enumerating all $k\times k$ submatrices of $X$, which is asymptotically optimal but computationally intensive. It is unclear from first principles whether statistically optimal detection can be achieved using computationally efficient procedures. Thus an intriguing question is in order: under the optimal condition (6) so that ${\mathcal{E}}^{*}\to 0$, is there a sequence of computationally efficient tests $\{\phi_{p}\}$ such that ${\mathcal{E}}(\phi_{p})\to 0$?

2 The penalty incurred by complexity constraints

To approach the computational hardness of the submatrix detection problem rigorously, we need to investigate the computational cost of testing procedures in a complexity theoretic sense. However, an immediate hurdle for the Gaussian model (1) is that computational complexity is not well defined for all tests dealing with nondiscrete distributions since the observation cannot be represented by finitely many bits almost surely. To propose a paradigm for complexity-constrained hypotheses testing, we consider a sequence of discretized Gaussian models which is asymptotically equivalent to the original model in the sense of Le Cam and hence preserves the statistical difficulty of the problem. More importantly, the computational complexity of tests on the discretized model can be appropriately defined. See Section 3 for details.

Next, we take the standard reduction approach in complexity theory: we show that if the signal magnitude is smaller than a certain threshold, detecting the submatrix is computationally no easier than certain well-known intractable problems. In other words, if an efficient method existed for submatrix detection, it would lead to an efficient solution to this problem. In this paper, we use the planted clique problem as the benchmark, which deals with detecting whether a given instance of an Erdős–Rényi random graph of size $N$ contains a planted clique of size $\kappa$. It is widely believed that the detection problem cannot be solved in randomized polynomial time when $\kappa=o(\sqrt{N})$, which we shall refer to as the planted clique hypothesis. For the precise statement and further discussions, see Definition 1 and Hypothesis 1 in Section 4.

Assuming the planted clique hypothesis, our main finding (Theorem 2 in Section 4) characterizes when it is possible to achieve reliable detection using computationally efficient procedures and when it is impossible. The core of the arguments lies in a randomized polynomial-time reduction scheme which maps the $N\times N$ adjacency matrix of the random graph in the planted clique problem to a $p\times p$ random matrix in polynomial time. It is worth noting that when $k\geq p^{\alpha}$ for some $\alpha\geq\frac{1}{2}$, the cardinality of the graph $N$ is not equal to the size of the matrix $p$ but rather chosen to be $p^{1+\delta}$ (omitting log factor), where $\delta>0$ depends on $\alpha$. On the other hand, $\kappa$ can always be chosen as a constant multiple of $k$.

Our main result can be illustrated by focusing on the following asymptotic regime, where the submatrix size grows according to $k=\Theta(p^{\alpha})$, and the signal magnitude decays as $\lambda=\Theta(p^{-\beta})$ for fixed constants $\alpha\in(0,1)$ and $\beta\in$The regime of $\beta>1$ is not interesting since the hypotheses are indistinguishable even if the submatrix becomes the whole matrix ($k=p$). as $p\to\infty$. For any two numbers $a$ and $b$, let $a\wedge b=\min(a,b)$ and $a\vee b=\max(a,b)$. Define

The statistical and computational feasibility of the submatrix detection problem is demonstrated in Figure 1, where the $(\alpha,\beta)$-plane is divided into three regions: {longlist}[(2)]

$\beta>\beta^{*}$ (top region): reliable detection of the submatrix is statistically impossible because the signal is too weak.

$\beta<\beta^{\sharp}$ (right triangular region): reliable submatrix detection is achievable by computationally efficient tests.

$\beta^{\sharp}<\beta<\beta^{*}$ (lower left triangular region): reliable detection is statistically possible but computationally intractable, in the sense that it is at least as hard as solving the planted clique problem of a particular configuration, which is intractable under the planted clique hypothesis. Therefore, the tractability of the submatrix detection problem undergoes a sharp transition: in the moderately sparse regime where $\alpha\in({2}/{3},1)$, computational constraints incur no penalty on the statistical performance. In contrast, in the highly sparse regime where $\alpha\in(0,{2}/{3})$, achieving the statistical optimal boundary requires computational resources that are powerful enough to solve the planted clique problem, and, consequently, computationally efficient procedures require significantly higher signal-to-noise ratio to detect the submatrix.

The complexity-theoretic limits for the submatrix detection problem also lead to interesting findings for the related support recovery problem when the signal submatrix is present . Moreover, it also sheds light on the statistical and computational tradeoff in the problem of estimating block sparse matrices . In particular, we show the surprising result that the hardness of minimax estimation can crucially depend on the loss function, in the sense that attaining the minimax estimation rate can be computationally easy for one type of loss functions but hard for the other.

3 Related works

Despite the vast body of literature on developing computationally efficient procedures with optimal statistical performance for problems such as compressed sensing, rigorous results on inferential limits of statistical problems under computational complexity constraints are comparatively limited. A representative work is the investigation of the complexity of detecting sparse principal components by Berthet and Rigollet , which is one of the motivations of the present paper. Sparse principal component detection refers to the problem of testing $N(0,I_{p})$ against $N(0,I_{p}+avv^{\prime})$ for $k$-sparse unit vector $v$ based on $n$ i.i.d. observations . Since the model is not discrete, as previously mentioned, the difficulty of ill-defined computational complexity is also present. In , the authors relaxed the Gaussian detection problem to a composite testing problem that includes discrete distributions, where the empirical projection variances of the null and alternative hypotheses satisfy respective uniform $\chi^{2}$-tail type concentration inequalities. In the regime of $p^{\delta}\leq k\leq p^{\alpha}$ for some absolute constants $0<\delta\leq\alpha<\frac{1}{2}$ and $n\leq p$, they showed that the computable detection rate for the deviation of the largest principal component from the rest of the spectrum is no smaller than $\sqrt{\frac{k^{b}}{n}}$ for any $b<2$, which far exceeds the minimax detection rate of $\sqrt{\frac{k}{n}\log p}$.

Although both the authors of current paper and Berthet and Rigollet use the planted clique hypothesis for studying complexity theoretic lower bounds, there are a few important differences. First, Berthet and Rigollet extend the original “simple vs. composite” Gaussian sparse principal component detection problem into a “composite versus composite” testing problem, and the data no longer needs to be Gaussian. As a consequence, more distributions are included in both the null and alternative hypotheses, and thus constructing the reduction scheme becomes easier than for the original Gaussian hypotheses. In contrast, the current paper considers an asymptotically equivalent discretized model which is faithful to the original Gaussian submatrix detection problem in . Second, the computational lower bounds in are established only when the sparsity level satisfies $p^{\delta}\leq k\leq p^{\alpha}$ for $0<\delta\leq\alpha<\frac{1}{2}$. In comparison, due to a new reduction scheme, the current paper provides a more complete characterization of the computational limits for all $k\geq p^{\delta}$ and any $\delta>0$. Last but not least, we propose an asymptotic equivalence framework in the sense of Le Cam, which preserves the statistical nature of the problem and, at the same time, allows rigorous statements of computational complexity of testing procedures. The approach via asymptotically equivalent discretized experiments is potentially useful in future works dealing with nondiscrete distributions.

In addition, some researchers have studied the minimax sub-optimality of certain computationally efficient methodologies, such as those based on convex relaxations, in an array of problems including estimating sparse eigenvectors , support recovery for sparse submatrices , combinatorial testing , community detection , etc. In some of the papers, the authors also conjecture that the minimax rate optimality cannot be achieved by any computationally efficient algorithms. From a different viewpoint, Chandrasekaran and Jordan consider the tradeoff between computation and statistical performance within a specific family of algorithms parameterized by the level of convex relaxations in the classical normal mean estimation problem. In contrast, the goal of the present paper is to investigate the impact of complexity constraint on any statistical procedure for the submatrix detection problem.

4 Organization of the paper

The rest of the paper is organized as follows. In Section 2, we study test statistics for submatrix detection under Gaussian models. To incorporate computational complexity into the decision theoretic problem, we introduce in Section 3 a sequence of asymptotically equivalent discretized models and show that the minimax detection results (6)–(7) remain unchanged under these models. In Section 4, we state our main result in Theorem 2 under the planted clique hypothesis and present its proof with a concrete randomized polynomial-time procedure that reduces the planted clique problem to a Bayesian version of the submatrix detection problem. We discuss some related problems in Section 5. Section 6 presents additional proofs for results in earlier sections.

5 Notation

Test statistics for submatrix detection

To prepare for later investigation, we first study three test statistics for the submatrix detection problem (1)–(1.1). The first two are the linear and the scan test statistics proposed in ,

In addition, we also consider the maximum test statistic

The following lemma gives nonasymptotic bounds on the Type-I${}+{}$II error probabilities on tests based on these statistics. Recall the definition of ${\mathcal{M}}(p,k,\lambda)$ in (1.1).

For $T_{\max}$ in (9), set $\tau^{\prime\prime}=\sqrt{(4+c)\log p}$. Then

Asymptotically equivalent discretized model

Gaussian distributions serve as good statistical models for many real-world datasets. However, as an idealized approximation, Gaussian experiment does not capture the finite-precision nature of statistical computing systems in reality. As mentioned in Section 1, it is an ill-defined problem to investigate the computational complexity of testing the Gaussian hypothesis (1) since the data do not admit any representation using finite bits. Therefore a new paradigm is needed in order to make sense of hypothesis testing with complexity constraints in general. There are two goals of the paradigm: {longlist}[(a)]

to provide a rigorous framework for quantifying the complexity of statistical inference involving continuous, for example, Gaussian, distributions and

to preserve the statistical difficulty of the original problem in the sense of Le Cam’s asymptotic equivalence. In this section, we propose such a paradigm based on discretizing the original Gaussian experiment, which achieves both of the above goals.

The function $[\cdot]_{t}$ naturally extends to matrices componentwise: for $A=(A_{ij})$, $[A]_{t}=([A_{ij}]_{t})$.

Recall the submatrix detection problem (1). To model statistical inference with finite precision and complexity constraints, let us consider the same testing problem based on the discretized data $[X]_{t}$. In other words, the hypotheses are

Asymptotic equivalence

where the infimum is over all probability transition kernels from $({\mathsf{X}},{\mathcal{F}})$ to $({\mathsf{Y}},{\mathcal{G}})$ , Theorem 1.7, page 29. The Le Cam distance between ${\mathcal{P}}$ and ${\mathcal{Q}}$ is

For the proof of Theorem 1, see the supplement . An immediate consequence of Theorem 1 on submatrix detection is the following: Since the difference between the optimal Type-I${}+{}$II error probabilities for the Gaussian hypotheses and the discretized hypotheses is upper bounded by their Le Cam distance , Theorem 2.2, which vanishes as $p\to\infty$, we conclude that testing on discretized data has no impact on the statistical performance asymptotically in the high-dimensional setting. In particular, conclusion (6)–(7) continues to hold for testing (14).

Complexity theoretic limits

Let $A\in\{0,1\}^{N\times N}$ be the adjacency matrix of a random graph drawn from either ${\mathcal{G}}(N,1/2)$ or ${\mathcal{G}}(N,1/2,\kappa)$. The planted clique problem of parameters $(N,\kappa)$, denoted by $\mathsf{PC}(N,\kappa)$, refers to the hypothesis testing problem of

The planted clique problem has a long history in the theoretical computer science literature. It is known that finding the clique is statistically impossible when $\kappa=o(\log N)$. Moreover, a greedy algorithm succeeds if $\kappa\geq c\sqrt{N\log N}$ for some constant $c>0$ . Using spectral methods, Alon, Krivelevich and Sudakov provided the first polynomial time detection algorithm when $\kappa=c\sqrt{N}$, with later improvements obtained in, for example, . However, it is widely believed that the detection problem cannot be solved in randomized polynomial time when $\kappa=o(\sqrt{N})$, which can be summarized as the following planted clique hypothesis. This version is similar to , Conjecture 4.13, and , Hypothesis $\mathsf{B}_{\mathsf{PC}}$.

For any sequence $\{\kappa_{N}\}$ such that $\limsup_{N\to\infty}\frac{\log\kappa_{N}}{\log N}<1/2$ and any sequence of randomized polynomial-time testsFormally, randomized polynomial-time tests belong to the BPP complexity class. Interested readers are referred to standard textbooks on computational complexity theory (e.g., , Chapter 7) for the formal definitions and discussions. Intuitively speaking, randomized polynomial-time tests refer to algorithms with output space $\{0,1\}$, which have access to external random numbers and whose running time is bounded by a polynomial of the input length regardless of the random numbers. $\{\psi_{N}\}$,

Various hardness results in theoretical computer science have been established based on the planted clique hypothesis, for example, approximating the Nash equilibrium , independence testing , certifying the restricted isometry property for compressed sensing measurement matrices , etc. Also, several cryptographic schemes have been proposed assuming the intractability of finding planted cliques or bicliques . Recently, the average-case hardness of planted clique has been established under certain computation models; see, for example, .

The main result of the current paper is the following.

Assume that Hypothesis 1 holds. Consider testing the discrete hypotheses (14) with $t=t(p)=4{\lceil{\log_{2}p}\rceil}$ in the asymptotic regime (5). If, for some absolute constant $\delta>0$,

there exists no sequence of randomized polynomial-time tests $\{\phi_{p}\}$ such that $\liminf_{p\to\infty}{\mathcal{E}}(\phi_{p})<{2}/{3}$ for testing (14). Conversely, if

there is a sequence of linear-time tests $\{\phi_{p}\}$ such that ${\mathcal{E}}(\phi_{p})\to 0$.

It should be noted that the sub-polynomial factor difference, that is, ${p}/{k^{2+\delta}}$ versus ${p}/{k^{2}}$, in the first part of (16) and (17) is a direct consequence of Hypothesis 1. In contrast, the logarithmic factor difference in the second part of (16) and (17) can potentially be closed by employing better reduction argument and/or more sophisticated testing procedures such as those based on spectral methods, which we leave as a future direction.

The remainder of this section is devoted to proving Theorem 2, with auxiliary lemmas proved in Section 6. First, in Section 4.1 we provide some intuition on how the planted clique problem is related to the submatrix detection problem (1) under the Gaussian model. Next, in Section 4.2 we prove that under the asymptotically equivalent discretized model, every randomized polynomial time submatrix detector for (14) leads to a randomized polynomial time solver for the planted clique problem of appropriate parameters with almost identical performance. Finally, a proof of Theorem 2 is presented in Section 4.3.

We first explain how the submatrix detection problem can be reduced from the planted clique problem under the original Gaussian model. These results are presented as the precursor of the randomized polynomial time reduction for the discretized model in Section 4.2, as well as to provide insights into the hardness of the submatrix detection problem. A connection between the two problems has also been previously hinted at in .

An important step in the following reduction scheme is to map any random edge to an $N(0,1)$ random variable and any edge in the clique to an $N(\mu,1)$ random variable with some positive mean value $\mu$. Although this goal might not be achievable exactly, we describe below a strategy to achieve it approximately.

To this end, for any $M\geq 3$ and $0<\mu\leq\frac{1}{2M}$, let $c_{0}=(1-2\overline{\Phi}(M))^{-1}$ and $c_{1}=[1-\overline{\Phi}(M-\mu)-\overline{\Phi}(M+\mu)]^{-1}$. We define two distributions ${\mathcal{F}}_{1}$ and ${\mathcal{F}}_{0}$ with the respective density functions

Here both $f_{0}$ and $f_{1}$ are well-defined probability density functions. In particular, the conditions $M\geq 3$ and $0\leq\mu\leq\frac{1}{2M}$ ensure that $f_{0}\geq 0$. In what follows, both $M$ and $\mu$, and thereby ${\mathcal{F}}_{0}$ and ${\mathcal{F}}_{1}$, depend on $N$, though we suppress the dependence for notational convenience.

In other words, ${\mathcal{L}}(B_{ij}|(A_{0})_{ij}=0)={\mathcal{F}}_{0}$ and ${\mathcal{L}}(B_{ij}|(A_{0})_{ij}=1)={\mathcal{F}}_{1}$.

Therefore, (20), (21) and (22) collectively define a deterministic function

which can be computed in $O(N^{2})$ number of flops. The reason that we call the first step “Gaussianization” is due to the following lemma, which ensures that for appropriately chosen $M$ and $\mu$, the marginal distribution of $B_{ij}$ is close to the Gaussian distribution of unit variance and mean zero (resp., $\mu$) if $(A_{0})_{ij}$ corresponds to a random edge (resp., an edge in the clique).

Let $N\geq 6$. Let $\xi$ be a Bernoulli random variable. Let $W$ be a random variable such that for $i\in\{0,1\}$, the conditional distribution of $W|\xi=i$ follows $f_{i}$ in (4.1) where $M\geq 3$ and $\mu\leq\frac{1}{2M}$. Then:

The following two lemmas characterize the law of $X=g(A,B_{0},B_{1})$ when either $H_{0}^{G}$ or $H_{1}^{G}$ in (15) holds.

Suppose $H_{0}^{G}$ holds and $N\geq 2p\geq 6$. Let $M\geq\sqrt{6\log N}$. Then

A careful examination of the proof of Lemma 4 in Section 6.4 reveals that the prior $\pi$ is in fact supported on a subset $\widetilde{\mathcal{M}}(p,k,\lambda)\subset{\mathcal{M}}(p,k,\lambda)$ where

and $\lambda=\frac{2\mu p}{N}$. In other words, any matrix in $\widetilde{\mathcal{M}}(p,k,\lambda)$ contains a nonzero rectangular submatrix whose row and column support sizes are between $k$ and $20k$. This observation will be useful for studying the hardness of estimation in Section 5.2.

Combining Lemmas 3 and 4, the following theorem shows that any submatrix detector leads to a test with almost identical error probability for a planted clique problem, whose parameters $(N,\kappa)$ depend on the parameters $(p,k,\lambda)$ of the submatrix detection problem.

By the definition of the total variation distance, Lemma 3 implies that under $H_{0}^{G}$,

Since $\beta=\beta_{0}+\beta_{1}$, the desired error bound (28) follows from

where the last inequality is due to assumption (27) on $\phi$.

Although the reduction scheme $g$ can be implemented in $O(N^{2})$ flops, its computational complexity is ill defined since it involves computing sums of continuous random variables and processing infinitely many bits. This issue will be addressed by a quantization argument in the next subsection when we deal with the discretized models.

2 Randomized polynomial-time reduction for discretized models

In this section, we show that with slight modifications, the scheme introduced in Section 4.1 can be made into a randomized polynomial-time reduction from the planted clique problem to the submatrix detection problem under discretized models in rigorous complexity-theoretic sense.

For the discretized model ${\mathcal{P}}^{(p,t)}$ introduced in Section 3, the reduction scheme from the planted clique model follows the same steps in Section 4.1, except that both the input $(B_{0},B_{1})$ and the output $X$ are now discretized.

To this end, we first define discrete approximations, denoted by $Q_{0}$ and $Q_{1}$, to the densities $f_{0}$ and $f_{1}$ defined in (4.1). Let $w,T$ be integers to be chosen based on $t,M$ and $N$. Recall the quantization operator defined in (13) and that $B_{0}$ and $B_{1}$ consist of i.i.d. entries drawn from densities $f_{0}$ and $f_{1}$, respectively, which are supported on $[-M,M]$ by definition. Note that each $[(B_{0})_{ij}]_{w}$ is drawn from a distribution with atoms $x_{i}$ and probability mass function (p.m.f.) $p_{i}$ for $i\in[M2^{w+1}]$. To find a dyadic approximation for the p.m.f., let $q_{i}=\lfloor p_{i}2^{T}\rfloor 2^{-T}$ for $i=2,\ldots,M2^{w}$ and $q_{1}=\lfloor p_{1}2^{T}\rfloor 2^{-T}+1-\sum_{i\geq 2}q_{i}$, where

Denote by $Q_{0}$ the discrete distribution with atoms $x_{i}$ and probability masses $q_{i}$. Similarly, define $Q_{1}$ as the dyadic approximation for the distribution of $[(B_{1})_{ij}]_{w}$.

The reduction scheme operates as follows: first, generate $\breve{B_{i}}$ consisting of i.i.d. entries drawn from $Q_{i}$ for $i=0,1$. Next, replace the matrices $B_{0}$ and $B_{1}$ in (20) by their discretized version $\breve{B}_{0}$ and $\breve{B}_{1}$, and denote the resulting matrix by $\breve{B}$. Applying (21)–(22) to $\breve{B}$, we obtain $\breve{X}$ and output its quantized version $[\breve{X}]_{t}$. Implementing the above steps yields a deterministic function

First we discuss the complexity for generating the auxiliary random variables used in the reduction scheme. Note that each $(\breve{B}_{0})_{ij}$ is drawn from $Q_{0}$ whose atoms $x_{i}$ can be represented by ${\lceil{\log_{2}M}\rceil}+w$ bits and the p.m.f. $q_{i}$ is a dyadic rational with $T$ bits. Therefore sampling from the distribution $Q_{0}$ can be done using the inverse CDFMore sophisticated random number generators for discrete distributions (such as Walker’s alias method which requires linear time for preprocessing and constant time per sample) can be found in , Section 3.4.1. by outputting $x_{J}$, where $J=\min\{j\dvtx\sum_{i=1}^{j}q_{i}\leq U2^{-T}\}$ and $U$ is a random integer uniformly distributed on $[2^{T}]$. Consequently, sampling from $Q_{0}$ requires $O(M2^{w}T)$ preprocessing time to compute the CDF, and $T$ fair coin flips and $O(\log M+w)$ time per sample (via binary search). Furthermore, discretizing each entry $\breve{X}_{ij}$ to $[\breve{X}_{ij}]_{t}$ involves keeping the first $t$ bits after the binary point, which can be computed in $O(t)$ time. Therefore we conclude that $\breve{g}$ can be computed using $O(({\lceil{\log_{2}M}\rceil}+w+t)N^{2})$ number of binary operations.

To summarize, the randomized reduction scheme requires $O(N^{2}T)$ random bits and $O(M2^{w}T+N^{2}(\log M+w+t))$ computation, where $T$ is defined in (31). As we will show in Section 4.3, for all cases of interest in this paper, we can set $N=O(p^{2})$ and $M,w,t=O(\log_{2}{p})=O(\log_{2}{N})$. Therefore, our reduction for discretized models $A\mapsto\breve{g}(A,\breve{B}_{0},\breve{B}_{1})$ is a randomized polynomial-time reduction.

Combining the two lemmas, we obtain the following result analogously to Theorem 3.

3 Proof of Theorem \texorpdfstring22

We start with the lower bound. Without loss of generality, we can assume that $\lambda\geq{1}/{p}$ since when $\lambda<{1}/{p}$, both conditions in (7) hold in the asymptotic regime (5), and the problem is statistically impossible. Let the sequence $\{(k(p),\lambda(p))\}$ satisfy (5) and (16). Let $\{\phi_{p}\}$ be a sequence of randomized polynomial time tests. For conciseness we drop the indices in $k(p),\lambda(p)$ and $\phi_{p}$. Suppose for the sake of contradiction that

On the other hand, we have $N\leq{p}/{\lambda}\leq p^{2}$, where the last inequality holds since we have assumed $\lambda\geq{1}/{p}$. Applying Theorem 4 with $w=16{\lceil{\log_{2}p}\rceil}\geq t+12\log_{2}p\geq t+6\log_{2}N$, we conclude from (38) that the randomized test $\psi(\cdot)=\phi(\breve{g}(\cdot,\breve{B}_{0},\breve{B}_{1}))$ satisfies

In view of Remark 5, $A\mapsto\breve{g}(A,\breve{B}_{0},\breve{B}_{1})$ is a randomized polynomial-time reduction. By the assumption on $\phi$, $\psi$ as a composition of $\phi$ and $\breve{g}$ is a randomized polynomial-time test for $\mathsf{PC}(N,\kappa)$. Therefore, (40) contradicts Hypothesis 1 in view of (39).

Discussion

In this paper, assuming the planted clique hypothesis, we have demonstrated a phase transition phenomenon on gaps between the optimal statistical performance with and without computational complexity constraints for the submatrix detection problem. The hardness result in Theorem 2 has important consequences on the hardness of two related problems, namely, support recovery and matrix estimation under submatrix sparsity, both of which are more difficult than detection and require stronger signal level. To discuss computational complexity of statistical procedures, we focus on the discretized models introduced in Section 3 throughout the current section.

As previously studied in , the goal of support recovery is to identify the minimum $\lambda$ such that, under the alternative hypothesis $H_{1}$ in (1), the submatrix can be consistently located. According to Theorems 1 and 2 of , for all $k\leq p/2$, one needs $\lambda=\Omega(\sqrt{\log(p)/k})$ to recover the support consistently under the parameter space (1.1). Compared with (6)–(7), this coincides with the minimum signal strength required for detecting the submatrix when $k=O(p^{\alpha})$ for $\alpha<{2/3}$, but is much larger when $k=\Omega(p^{\alpha})$ for $\alpha>{2/3}$.

2 Hardness of estimation depends on norm

We now consider the computational aspect of the related problem of estimating the mean matrix with submatrix sparsity under squared norm losses. Denote the set of $k\times k$-sparse matrices by

which includes both the zero matrix and the set $\widetilde{\mathcal{M}}(p,{\lfloor{k/20}\rfloor},\lambda)$ [defined in (3)] for any $\lambda>0$.

Given the noisy observation $X=\theta+Z$, where $Z$ consists of standard Gaussian entries, the minimax risk

has been obtained in , Section 4, within universal constant factors using convex geometry and information-theoretic arguments for all unitarily invariant norms,To be precise, note that the minimax rates in are obtained for the Gaussian model. Since the loss function is unbounded, one cannot directly conclude from asymptotic equivalence that the same rate applies to the discretized model. Nevertheless, it is straightforward to extend the arguments in , Section 4.1, to show that the rate of $\Psi_{\|\cdot\|}(p,k)$ applies to the discretized model in Section 3 as long as $t=\Omega(\sqrt{\log p})$, independent of the unitarily invariant norm. In particular, the lower bound in , Section 4.1.1, applies verbatim due to the data processing inequality of the KL divergence, which is attained by the same estimator defined in , Section 4.1.2, if $2^{-t}\leq 1/\sqrt{p}$. in particular, satisfies

which is within a logarithmic term of $k^{{2}/{q}+1}$. Next we discuss the computational cost of estimation by focusing on the asymptotic regime where $k=\Theta(p^{\alpha})$ for some $\alpha\in(0,1)$. In view of the relationship between testing and estimation, we can use the construction in Lemmas 3–4 for the detection problem

since the risk is clearly nondecreasing in $k$.

On the constructive side, an estimation error of

Comparing the minimax rate (43) with the computationally lower and upper bounds (44)–(45), we obtain the following result, assuming Hypothesis 1:

For $q\in$, using the entrywise thresholding estimator defined above, the minimax rate is attained within a logarithmic factor simultaneously for all $k$;

More generally, one can show that for all quadratic norms (see , page 95), entrywise thresholding is near optimal (within a sub-polynomial factor) among all computationally efficient estimators. This extends the above result since Schatten-$q$ norm is quadratic if and only if $q\in[2,\infty]$.

Proofs

We present below the proofs of Lemmas 1–4. The proofs of Theorem 1 and Lemmas 5 and 6 are deferred to the supplement .

2 Proof of Lemma \texorpdfstring22

For the first claim, the marginal density function of $W$ is $f_{1}$ in (4.1). So by definition,

were the last inequality is due to the fact that for any $0<\mu\leq\frac{1}{2M}$, $(M-\mu)^{2}\geq(M-\frac{1}{2M})^{2}\geq M^{2}-1$. For the second claim, the marginal density function of $W$ is $f=\frac{1}{2}(f_{0}+f_{1})=c_{0}\varphi(x){\mathbf{1}_{\{{|x|\leq M}\}}}$. Thus

3 Proof of Lemma \texorpdfstring33

We need the following result on the total variation between product distributions.

$\mathsf{TV}(\prod_{i=1}^{n}P_{i},\prod_{i=1}^{n}Q_{i})\leq\sum_{i=1}^{n}\mathsf{TV}(P_{i},Q_{i})$.

Recall the dual representation of the total variation ,

Here, the first inequality is due to the data processing inequality for the total variation , the second last inequality is due to Lemma 7 and the last inequality is due to Lemma 2.

4 Proof of Lemma \texorpdfstring44

Recall that $N$ is even with $N_{2}=N/2$. When $A\sim{\mathcal{G}}(N,1/2,\kappa)$, let $V\subset[N]$ denote the vertex subset of size $\kappa$ on which the planted clique in $A$ is supported. For any subset $S\subset\{N_{2}+1,\dots,N\}$, we have $S-N_{2}\subset[N_{2}]$. Further define

By the definition of $X$, for each $a,b\in[p]$, we can define sets

occurs with high probability. To this end, first note that

Note that conditioning on the size $|V_{1}|=\kappa_{1}$, the set $V_{1}$ is chosen uniformly at random among all $\kappa_{1}$ subsets of $[N_{2}]$. Thus, for any $\kappa_{1}\in[\kappa/4,3\kappa/4]$ and $c_{0}=1/20$,

Then we apply (21) and (22) to $\widetilde{B}$ instead of $B$ to obtain a $p\times p$ random matrix $\widetilde{X}$. The intuition is that ${\widetilde{B}}$ and ${\widetilde{X}}$ correspond to the ideal input and output of the reduction scheme, in the sense that the ${\mathcal{L}}({\widetilde{X}})$ is, as we show next, close to a desired mixture on the alternative hypotheses. Our choice of the distribution ${\mathcal{F}}_{0}$ and ${\mathcal{F}}_{1}$ ensures that $B$ is close to the ideal case ${\widetilde{B}}$ in total variation, and the data processing inequality guarantees that the output $X$ is also close to ${\widetilde{X}}$.

To this end, note that conditioned on $V$, for each $a,b\in[p]$, we have

where the last inequality is due to (6.4). In view of (55), this completes the proof.

[id=suppA] \stitleSupplement to “Computational barriers in minimax submatrix detection” \slink[doi]10.1214/14-AOS1300SUPP \sdatatype.pdf \sfilenameaos1300_supp.pdf \sdescriptionWe provide proofs of Theorem 1 and Lemmas 5 and 6.

References