Computational Lower Bounds for Sparse PCA

Introduction

The modern scientific landscape has been significantly transformed over the past decade by the apparition of massive datasets. From the statistical learning point of view, this transformation has led to a paradigm shift. Indeed, most novel methods consist in searching for sparse structure in datasets, whereas estimating parameters over this structure is now a fairly well understood problem. It turns out that most interesting structures have a combinatorial nature, often leading to computationally hard problems. This has led researchers to consider various numerical tricks, chiefly convex relaxations, to overcome this issue. While these new questions have led to fascinating interactions between learning and optimization, they do not always come with satisfactory answers from a statistical point of view. The main purpose of this paper is to study one example, namely sparse principal component detection, for which current notions of statistical optimality should also be shifted, along with the paradigm.

Sparse detection problems where one wants to detect the presence of a sparse structure in noisy data falls in this line of work. There has been recent interest in detection problems of the form signal-plus-noise, where the signal is a vector with combinatorial structure [ABBDL10, ACCP11, ACV13] or even a matrix [BI13, SN13, KBRS11, BKR+11]. The matrix detection problem was pushed beyond the signal-plus-noise model towards more complicated dependence structures [ACBL12, ACBL13, BR12]. One contribution of this paper is to extend these results to more general distributions.

For matrix problems, and in particular sparse principal component (PC) detection, some computationally efficient methods have been proposed, but they are not proven to achieve the optimal detection levels. [JL09, CMW12, Ma13] suggest heuristics for which detection levels are unknown and [BR12] prove suboptimal detection levels for a natural semidefinite relaxation developed in [dGJL07] and an even simpler, efficient, dual method called Minimum Dual Perturbation (MDP). More recently, [dBG12] developed another semidefinite relaxation for sparse PC detection that performs well only outside of the high-dimensional, low sparsity regime that we are interested in. Note that it follows from the results of [AW09] that the former semidefinite relaxation is optimal if it has a rank-one solution. Unfortunately, rank-one solutions can only be guaranteed at suboptimal detection levels. This literature hints at a potential cost for computational efficiency in the sparse PC detection problem.

Partial results were obtained in [BR12] who proved that their bound for MDP and SDP are unlikely to be improved, as otherwise they would lead to randomized polynomial time algorithms for instances of the planted clique problem that are believed to be hard. This result only focuses on a given testing method, but suggests the existence of an intrinsic gap between the optimal rates of detection and what is statistically achievable in polynomial time. Such phenomena are hinted at in [CJ13] but their these results focus on the behavior of upper bounds. Closer to our goal, is [SSST12] that exhibits a statistical price to pay for computational efficiency. In particular, their derive a computational theoretic lower bound using a much weaker conjecture than the hidden clique conjecture that we employ here, namely the existence of one-way permutations. This conjecture is widely accepted and is the basis of many cryptographic protocols. Unfortunately, the lower bound holds only for a synthetic classification problem that is somewhat tailored to this conjecture. It still remains to fully describe a theory, and to develop lower bounds on the statistical accuracy that is achievable in reasonable computational time for natural problems. This article aims to do so for a general sparse PC detection problem.

This paper is organized in the following way. The sparse PC detection problem is formally described in Section 2. Then, we show in Section 3 that our general detection framework is a natural extension of the existing literature, and that all the usual results for classical detection of sparse PC are still valid. Section 4 focuses on testing in polynomial time, where we study detection levels for the semidefinite relaxation developed of [dGJL07] (It trivially extends to the MDP statistic of [BR12]). These levels are shown to be unimprovable using computationally efficient methods in Section 5. This is achieved by introducing a new notion of optimality that takes into account computational efficiency. Practically, we reduce the planted clique problem, conjectured to be computationally hard already in an average-case sense (i.e. over most random instances) to obtaining better rates for sparse PC detection.

For a finite set $S$, we denote by $|S|$ its cardinality. We also write $A_{S}$ for the $|S|\times|S|$ submatrix with elements $(A_{ij})_{i,j\in S}$, and $v_{S}$ for the vector of $\mathbf{R}^{|S|}$ with elements $v_{i}$ for $i\in S$. The vector $\mathbf{1}$ denotes a vector with coordinates all equal to $1$. If a vector has an index such as $v_{i}$, then we use $v_{i,j}$ to denote its $j$th element.

The vectors $e_{i}$ and matrices $E_{ij}$ are the elements of the canonical bases of $\mathbf{R}^{d}$ and $\mathbf{R}^{d\times d}$. We also define $\mathcal{S}^{d-1}$ as the unit Euclidean sphere of $\mathbf{R}^{d}$ and $\mathcal{S}^{d-1}_{S}$ the set of vectors in $\mathcal{S}^{d-1}$ with support $S\subset\{1,\ldots,d\}$. The identity matrix in $\mathbf{R}^{d}$ is denoted by $I_{d}$.

A Bernoulli random variable with parameter $p\in$ takes values $1$ or $0$ with probability $p$ and $1-p$ respectively. A Rademacher random variable takes values $1$ or $-1$ with probability $1/2$. A binomial random variable, with distribution $\mathcal{B}(n,p)$ is the sum of $n$ independent Bernoulli random variables with identical parameter $p$. A hypergeometric random variable, with distribution $\mathcal{H}(N,k,n)$ is the random number of successes in $n$ draws from a population of size $N$ among which are $k$ successes, without replacement. The total variation norm, noted $\|\cdot\|_{\sf TV}$ has the usual definition.

The trace and rank functionals are denoted by $\mathbf{Tr}$ and $\mathbf{rank}$ respectively and have their usual definition. We denote by $T^{c}$ the complement of a set $T$. Finally, for two real numbers $a$ and $b$, we write $a\wedge b=\min(a,b)$, $a\vee b=\max(a,b)$, and $a_{+}=a\vee 0\,$.

Problem description

Let $X\in\mathbf{R}^{d}$ be a centered random vector with unknown distribution $\mathbf{P}$ that has finite second moment along every direction. The first principal component for $X$ is a direction $v\in\mathcal{S}^{d-1}$ such that the variance ${\sf V}(v)=\mathbf{E}[(v^{\top}X)^{2}]$ along direction $v$ is larger than in any other direction. If no such $v$ exists, the distribution of $X$ is said to be isotropic. The goal of sparse principal component detection is to test whether $X$ follows an isotropic distribution $\mathbf{P}_{0}$ or a distribution $\mathbf{P}_{v}$ for which there exists a sparse $v\in\mathcal{B}_{0}(k)$, $k\ll d$, along which the variance is large. Without loss of generality, we assume that under the isotropic distribution $\mathbf{P}_{0}$, all directions have unit variance and under $\mathbf{P}_{v}$, the variance along $v$ is equal to $1+\theta$ for some positive $\theta$. Note that since $v$ has unit norm, $\theta$ captures the signal strength.

To perform our test, we observe $n$ independent copies $X_{1},\ldots,X_{n}$ of $X$. For any direction $u\in\mathcal{S}^{d-1}$, define the empirical variance along $u$ by

Such inequalities are satisfied if we assume that $\mathbf{P}_{0}$ and $\mathbf{P}_{v}$ are sub-Gaussian distributions for example. Rather than specifying such an ad-hoc assumption, we define the following sets of distributions under which the fluctuations of ${\sf\widehat{V}}_{n}$ around ${\sf V}$ are of the same order as those of sub-Gaussian distributions. As a result, we formulate our testing problem on the unknown distribution $\mathbf{P}$ of $X$ as follows

Note that distributions in $\mathcal{D}_{0}$ and $\mathcal{D}_{1}^{k}(\theta)$ are implicitly centered at zero.

We argue that interesting testing procedures should be robust and thus perform well uniformly over these distributions. In the rest of the paper, we focus on such procedures. The existing literature on sparse principal component testing, particularly in [BR12] and [ACBL12] focuses on multivariate normal distributions, yet only relies on the sub-Gaussian properties of the empirical variance along unit directions. Actually, all the distributional assumptions made in [VL12, ACBL12] and [BR12] are particular cases of these hypotheses. We will show that concentration of the empirical variance as in (1) and (2) is sufficient to derive the results that were obtained under the sub-Gaussian assumption.

Recall that a test for this problem is a family $\psi=\{\psi_{d,n,k}\}$ of $\{0,1\}$-valued measurable functions of the data $(X_{1},\ldots,X_{n})$. Our goal is to quantify the smallest signal strength $\theta>0$ for which there exists a test $\psi$ with maximum test error bounded by $\delta>0$, i.e.,

Note that the constant $0.49$ is arbitrary and can be replaced by any constant $C<0.5$.

Fix a set of parameters $R\subset R_{0}$ in the sparse regime. Let $\mathcal{T}$ be a set of tests. A function $\theta^{*}$ of $(d,n,k)\in R$ is called optimal rate of detection over the class $\mathcal{T}$ if for any $(d,n,k)\in R$, it holds:

there exists a test $\psi\in\mathcal{T}$ that discriminates between $H_{0}$ and $H_{1}$ at level $\bar{c}\theta^{*}$ for some constant $\bar{c}>0$, i.e., for any $\theta\geq\bar{c}\theta^{*}$

In this case we say that $\psi\in\mathcal{T}$ discriminates between $H_{0}$ and $H_{1}$ at rate $\theta^{*}$.

for any test $\phi\in\mathcal{T}$, there exists a constant $\underline{c}_{\phi}>0$ such that $\theta\leq\underline{c}_{\phi}\theta^{*}$ implies

Moreover, if both (i) and (ii) hold, we say that $\psi$ is an optimal test over the class $\mathcal{T}$.

This an adaptation of the usual notion of statistical optimality, when one is focusing on the class of measurable functions, for $\psi_{d,n,k}:(X_{1},\ldots,X_{n})\mapsto\{0,1\}$, also known as minimax optimality [Tsy09]. In order to take into account the asymptotic nature of some classes of statistical tests (namely, those that are computationally efficient), we allow the constant $\underline{c}_{\phi}$ in (ii) to depend on the test.

Statistically optimal testing

We focus first on the traditional setting where $\mathcal{T}$ contains all sequences $\{\psi_{d,n,k}\}$ of tests.

Observe that ${\sf V}(u)=u^{\top}\Sigma\,u$ and ${\sf\widehat{V}}_{n}(u)=u^{\top}\hat{\Sigma}u$, for any $u\in\mathcal{S}^{d-1}$. Maximizing ${\sf\widehat{V}}_{n}(u)$ over $\mathcal{B}_{0}(k)$ gives the largest empirical variance along any $k$-sparse direction. It is also known as the $k$-sparse eigenvalue of $\hat{\Sigma}$ defined by

The following theorem describes the performance of the test

Assume that $(d,n,k)\in R_{0}$ and define

Then, for $\bar{\theta}<\theta<1$, the test $\psi$ defined in (5) with threshold $\tau=8\sqrt{\frac{k\log\big(\frac{6ed}{k\delta}\big)}{n}}$ , satisfies

Define $\tau_{1}=7\sqrt{k\log(2/\delta)/n}$. For $\mathbf{P}_{1}\in\mathcal{D}^{k}_{1}(\theta)$, by (2), and for $\mathbf{P}_{0}\in\mathcal{D}_{0}$, using Lemma 10, we get

To conclude the proof, observe that $\tau\leq\bar{\theta}-\tau_{1}<\theta-\tau_{1}$. ∎The following lower bound follows directly from [BR12], Theorem 5.1 and holds already for Gaussian distributions.

For all $\varepsilon>0$, there exists a constant $C_{\varepsilon}>0$ such that if

Theorems 2 and 3 imply the following result.

is the optimal rate of detection over the class of all tests.

Polynomial time testing

It is not hard to prove that approximating $\lambda_{\max}^{k}(A)$ up to a factor of $m^{1-\varepsilon},\varepsilon>0$, for any symmetric matrix $A$ of size $m\times m$ and any $k\in\{1,\ldots,m\}$ is NP-hard, by a trivial reduction to CLIQUE (see [Hås96, Hås99, Zuc06] for hardness of approximation of CLIQUE). Yet, our problem is not worst case and we need not consider any matrix $A$. Rather, here, $A$ is a random matrix and we cannot directly apply the above results.

In this section, we look for a test with good statistical properties and that can be computed in polynomial time. Indeed, finding efficient statistical methods in high-dimension is critical. Specifically, we study a test based on a natural convex (semidefinite) relaxation of $\lambda_{\max}^{k}(\hat{\Sigma})$ developed in [dGJL07].

For any $A\succeq 0$ let $\mathsf{\mathop{SDP}}_{k}(A)$ be defined as the optimal value of the following semidefinite program:

This optimization problem can be reformulated as a semidefinite program in its canonical form with a polynomial number of constraints and can therefore be solved in polynomial time up to arbitrary precision using interior point methods for example [BV04]. Indeed, we can write

where $\mathsf{\mathop{SDP}}^{(n)}_{k}$ is a $1/\sqrt{n}$-approximation of $\mathsf{\mathop{SDP}}_{k}$. [BAd10] show that $\mathsf{\mathop{SDP}}^{(n)}_{k}$ can be computed in $\mathcal{O}(kd^{3}\sqrt{n\log d})$ elementary operations and thus in polynomial time.

For all $\delta>0$, $\mathbf{P}_{0}\in\mathcal{D}_{0},\mathbf{P}_{1}\in\mathcal{D}^{k}_{1}(\theta)$, by Lemma 11 and Lemma 10, since $\mathsf{\mathop{SDP}}_{k}(\hat{\Sigma})\geq\lambda_{\max}^{k}(\hat{\Sigma})$, it holds

Clearly, this theorem, together with Theorem 3, indicate that the test based on $\mathsf{\mathop{SDP}}$ may be suboptimal within the class of all tests. However, as we will see in the next section, it can be proved to be optimal in a restricted class of computationally efficient tests.

Complexity theoretic lower bounds

In this section, we show that it is true not only of the test based on SDP but of any test computable in randomized polynomial time.

The upper bound of Theorem 5, if tight, seems to indicate that there is a gap between the detection levels that can be achieved by any test, and those that can be achieved by methods that run in polynomial time. In other words, it indicates a potential statistical cost for computational efficiency. To study this phenomenon, we take the approach favored in theoretical computer science, where our primary goal is to classify problems, rather than algorithms, according to their computational hardness. Indeed, this approach is better aligned with our definition of optimal rate of detection where lower bounds should hold for any tests. Unfortunately, it is difficult to derive a lower bound on the performance of any candidate algorithm to solve a given problem. Rather, theoretical computer scientists have developed reductions from problem A to problem B with the following consequence: if problem B can be solved in polynomial time, then so can problem A. Therefore, if problem A is believed to be hard then so is problem B. Note that our reduction requires extra bits of randomness and is therefore a randomized polynomial time reduction.

This question needs to be formulated from a statistical detection point of view. As mentioned above, $\lambda_{\max}^{k}$ can be proved to be NP-hard to approximate. Nevertheless, such worst case results are not sufficient to prove negative results on our average case problem. Indeed, the matrix is $\hat{\Sigma}$ is random and we only need to be able to approximate $\lambda_{\max}^{k}(\hat{\Sigma})$ up to constant factor on most realizations. In some cases, this small nuance can make a huge difference, as problems can be hard in the worst case but easy in average (see, e.g., [Bop87] for an illustration on Graph Bisection). In order to prove a complexity theoretic lower bound on the sparse principal component detection problem, we will build a reduction from a notoriously hard detection problem: the planted clique problem.

2 The Planted Clique problem

Fix $m\geq\kappa>2$. Let Planted Clique denote the following statistical hypothesis testing problem:

The search version of this problem [Jer92, Kuč95], consists in finding the clique planted under $H_{1}^{\sf PC}$. The decision version that we consider here is traditionally attributed to Saks [KV02, HK11]. It is known [Spe94] that if $\kappa>2\log_{2}(m)$, the planted clique is the only clique of size $\kappa$ in the graph, asymptotically almost surely (a.a.s.). Therefore, a test based on the largest clique of $G$ allows to distinguish $H_{0}^{\sf PC}$ and $H_{1}^{\sf PC}$ for $\kappa>2\log_{2}(m)$, a.a.s. This is clearly not a computationally efficient test.

For $\kappa=o(\sqrt{m})$ there is no known polynomial time algorithm that solves this problem. Polynomial time algorithms for the case $\kappa=C\sqrt{m}$ were first proposed in [AKS98], and subsequently in [McS01, AV11, DGGP10, FR10, FK00]. It is widely believed that there is no polynomial time algorithm that solves Planted Clique for any $\kappa$ of order $m^{c}$ for some fixed positive $c<1/2$. Recent research has been focused on proving that certain algorithmic techniques, such as the Metropolis process [Jer92] and the Lovàsz-Schrijver hierarchy of relaxations [FK03] fail at this task. The confidence in the difficulty of this problem is so strong that it has led researchers to prove impossibility results assuming that Planted Clique is indeed hard. Examples include cryptographic applications, in [JP00], testing for $k$-wise dependence in [AAK+07], approximating Nash equilibria in [HK11] and approximating solutions to the densest $\kappa$-subgraph problem by [AAM+11].

We therefore make the following assumption on the planted clique problem. Recall that $\delta$ is a confidence level fixed throughout the paper.

For any $a,b\in(0,1),a<b$ and all randomized polynomial time tests $\xi=\{\xi_{m,\kappa}\}$, there exists a positive constant $\Gamma$ that may depend on $\xi,a,b$ and such that

Note that $1.2\delta<1/2$ can be replaced by any constant arbitrary close to $1/2$. Since $\kappa$ is polynomial in $m$, here a randomized polynomial time test is a test that can be computed in time at most polynomial in $m$ and has access to extra bits of randomness. The fact that $\Gamma$ may depend on $\xi$ is due to the asymptotic nature of polynomial time algorithms. Below is an equivalent formulation of Hypothesis 5.2.

For any $a,b\in(0,1),a<b$ and all randomized polynomial time tests $\xi=\{\xi_{m,\kappa}\}$, there exists $m_{0}\geq 1$ that may depend on $\xi,a,b$ and such that

Note that we do not specify a computational model intentionally. Indeed, for some restricted computational models, Hypothesis 5.2 can be proved to be true for all $a<b\in(0,1)$ [Ros10, FGR+13]. Moreover, for more powerful computational models such as Turing machines, this hypothesis is conjectured to be true. It was shown in [BR12] that improving the detection level of the test based on SDP would lead to a contradiction of Hypothesis 5.2 for some $b\in(2/3,1)$. Herefater, we extend this result to all randomized polynomial time algorithms, not only those based on SDP.

3 Randomized polynomial time reduction

Our main result is based on a randomized polynomial time reduction of an instance of the planted clique problem to an instance of the sparse PC detection problem. In this section, we describe this reduction and call it the bottom-left transformation. For any $\mu\in(0,1)$, define

The condition $k\geq n^{\mu}$ is necessary since “polynomial time” is an intrinsically asymptotic notion and for fixed $k$, computing $\lambda_{\max}^{k}$ takes polynomial time in $n$. The condition $n<d$ is an artifact of our reduction and could potentially be improved. Nevertheless, it characterizes the high-dimensional setup we are interested in and allows us to shorten the presentation.

Let $B$ denote the $d\times n$ adjacency matrix of $V^{\prime}$ and let $\eta_{1},\ldots,\eta_{n}$ be $n$ i.i.d Rademacher random variables that are independent of all previous random variables. Define

Note that ${\sf bl}(G)$ can be constructed in randomized polynomial time in $d,n,k,\kappa,m$.

4 Optimal detection over randomized polynomial time tests

For any $\alpha\in$, define the detection level $\theta_{\alpha}>0$ by $\theta_{\alpha}=\sqrt{\frac{k^{\alpha}}{n}}\,.$

Fix $\alpha\in[1,2),\mu\in(0,\frac{1}{4-\alpha})$ and define

where $\xi_{m,\kappa}=\psi_{d,n,k}\circ{\sf bl}_{d,n,k,m,\kappa}$.

Fix $(d,n,k)\in R_{\mu},\alpha\in[1,2)$. First, if $G$ is an Erdős-Rényi graph, ${\sf bl}(G)=\big(X_{1}^{(G)},\ldots,X_{n}^{(G)}\big)$ is an array of $n$ i.i.d. vectors of $d$ independent Rademacher random variables. Therefore $X_{1}^{(G)}\sim\mathbf{P}_{0}^{{\sf bl}(G)}\in\mathcal{D}_{0}$.

Second, if $G$ has a planted clique of size $\kappa$, let $\mathbf{P}^{{\sf bl}(G)}$ denote the joint distribution of ${\sf bl}(G)$. The choices of $\kappa$ and $m$ depend on the relative size of $k$ and $n$. Our proof relies on the following lemma.

Fix $\beta>0$ and integers $m,\kappa,n,k$ such that $1\leq n\leq m$, $2\leq k\leq\kappa\leq m$,

Let $G\sim\mathcal{G}(2m,1/2,\kappa)$ and ${\sf bl}(G)=\big(X_{1}^{(G)},\ldots,X_{n}^{(G)}\big)\in\mathbf{R}^{d\times n}$ be defined in (8). Denote by $\mathbf{P}_{1}^{{\sf bl}(G)}$ the distribution of ${\sf bl}(G)$. Then, there exists a distribution $\mathbf{P}_{1}\in\mathcal{D}_{1}^{k}(\bar{\theta})$ such that

Let $S\subset\{1,\ldots,n\}$ (resp. $T\subset\{1,\ldots,d\}$) denote the (random) right (resp. left) vertices of $V^{\prime}$ that are in the planted biclique.

On the one hand, if $i\notin S$, i.e., if $\varepsilon^{\prime}_{i}=0$, then $X^{(G)}_{i}$ is a vector of independent Rademacher random variables. On the other hand, if $i\in S$, i.e., if $\varepsilon^{\prime}_{i}=1$ then, for any $j=1,\ldots,d$,

where $r=\{r_{ij}\}_{ij}$ is a $n\times d$ matrix of i.i.d Rademacher random variables.

where $Y_{i}^{\prime}=(Y_{i,1}^{\prime},\ldots,Y_{i,d}^{\prime})^{\top}$ and $r_{i}^{\top}$ is the $i$th row of $r$.

Note that the $\varepsilon_{i}^{\prime}$s are not independent. Indeed, they correspond to $n$ draws without replacement from an urn that contains $2m$ balls (vertices) among which $\kappa$ are of type $1$ (in the planted clique) and the rest are of type $0$ (outside of the planted clique). Denote by $\mathbf{p}_{\varepsilon^{\prime}}$ the joint distribution of $\varepsilon^{\prime}=(\varepsilon_{1}^{\prime},\ldots,\varepsilon_{n}^{\prime})$ and define their “with replacement” counterparts as follows. Let $\varepsilon_{1},\ldots,\varepsilon_{n}$ be $n$ i.i.d. Bernoulli random variables with parameter $p=\frac{\kappa}{2m}\leq\frac{1}{2}$. Denote by $\mathbf{p}_{\varepsilon}$ the joint distribution of $\varepsilon=(\varepsilon_{1},\ldots,\varepsilon_{n})$.

We also replace the distribution of the $\gamma^{\prime}_{j}$s as follows. Let $\gamma=(\gamma_{1},\ldots,\gamma_{n})$ have conditional distribution given $\varepsilon$ be given by

where $Y_{i}\in\mathbf{R}^{d}$ has coordinates given by

With this construction, the $X_{i}$s are iid. Moreover, as we will see, the joint distribution $\mathbf{P}_{1}^{{\sf bl}(G)}$ of ${\sf bl}(G)=\big(X_{1}^{(G)},\ldots,X_{n}^{(G)}\big)$ is close in total variation to the joint distribution $\mathbf{P}_{1}^{\otimes n}$ of $\big(X_{1},\ldots,X_{n}\big)$.

Note first that Markov’s inequality yields

Moreover, given $\sum_{i=1}^{n}\varepsilon_{i}=s$, we have $\sum_{i=1}^{d}\gamma_{i}\geq U\sim\mathcal{H}(2m-n,\kappa-s,n)$. It follows from [DF80], Theorem $(4)$ that

Together with the Chernoff-Okamoto inequality [Dud99], Equation (1.3.10), it yields

Combined with (11) and view of (10)$(b,c)$, it implies that with probability $1-6n/m$, it holds

Denote by $\mathbf{p}$ the joint distribution of $(\varepsilon_{1},\ldots,\varepsilon_{n},\gamma_{1},\ldots,\gamma_{d})$ and by $\mathbf{p}^{\prime}$ that of $(\varepsilon^{\prime}_{1},\ldots,\varepsilon^{\prime}_{n},\gamma^{\prime}_{1},\ldots,\gamma^{\prime}_{d})$. Using again [DF80], Theorem $(4)$ and (10)(a), we get

Since the conditional distribution of $\big(X_{1},\ldots,X_{n}\big)$ given $(\varepsilon,\gamma)$ is the same as that of ${\sf bl}(G)$ given $(\varepsilon^{\prime},\gamma^{\prime})$, we have

It remains to prove that $\mathbf{P}_{1}\in\mathcal{D}_{1}^{k}(\bar{\theta})$. Fix $\nu>0$ and define $Z\in\mathcal{B}_{0}(k)$ by

Denote by $S_{Z}\subset\{1,\ldots,d\}$, the support of $Z$. Next, observe that for any $x,\theta>0$, it holds

Therefore, since $Z$ is independent of the $r_{ij}$s, the following equality holds in distribution:

Moreover, it follows from the Chernoff-Okamoto inequality [Dud99], Equation (1.3.10), that with probability at least $1-\nu/2$, it holds

Put together, the above two displays imply that with probability $1-\nu$, it holds

Together with (13), this completes the proof. ∎

Define $N=\lceil 40/\delta\rceil$. Assume first that $k\geq M^{-1}n^{\frac{1}{4-\alpha}}$ where $M>0$ is a constant to be chosen large enough (see below). Take $\kappa=\max\big(8,M\log(N)\big)Nk\,,m=Nn.$ It implies that

Moreover, under these conditions, it is easy to check that (10) is satisfied with $\beta=1/5$ since and we are therefore in a position to apply Lemma 8. It implies that there exists $\mathbf{P}_{1}\in\mathcal{D}_{1}^{k}(\bar{\theta})$ such that $\big\|\mathbf{P}_{1}^{{\sf bl}(G)}-\mathbf{P}_{1}^{\otimes n}\big\|_{\sf TV}\leq\delta/5\,.$

Assume now that $k<M^{-1}n^{\frac{1}{4-\alpha}}$. Take $m,\kappa\geq 2$ to be the largest integers such that

Note that $\Gamma\kappa\geq(2m)^{\frac{a}{2}}$. Let us now check condition (10). It holds, for $M$ large enough,

Under these conditions, (10) is satisfied with $\beta=1/5$ and we are therefore in a position to apply Lemma 8. It implies that there exists $\mathbf{P}_{1}\in\mathcal{D}_{1}^{k}(\bar{\theta})$ such that $\big\|\mathbf{P}_{1}^{{\sf bl}(G)}-\mathbf{P}_{1}^{\otimes n}\big\|_{\sf TV}\leq\delta/5\,,$ where $\bar{\theta}:=\frac{(k-1)\kappa}{2m}\geq\frac{1}{8\Gamma(4N)^{\frac{b}{2}}}\sqrt{\frac{k^{\alpha}}{n}}$, taking $L=\min\Big(\frac{1}{4M^{\alpha-1}},\frac{1}{8\Gamma(4N)^{\frac{b}{2}}}\Big)\,,$ yields that $\mathbf{P}_{1}\in\mathcal{D}_{1}^{k}(L\theta_{\alpha})$ for any $(d,n,k)\in R_{\mu}$. Moreover,

∎Theorems 5 and 7 imply the following result.

Fix $\alpha\in[1,2),\mu\in(0,\frac{1}{4-\alpha})$. Conditionally on Hypothesis 5.2, the optimal rate of detection $\theta^{\circ}$ over the class of randomized polynomial time tests satisfies

Let $\mathcal{T}$ denote the class of randomized polynomial time tests. Since ${\sf bl}$ can be computed in randomized polynomial time, $\psi\in\mathcal{T}$ implies that $\xi=\psi\circ{\sf bl}\in\mathcal{T}$. Therefore, for all $(d,n,k)\in R_{\mu}$,

where the last inequality follows from Hypothesis 5.2 with $a,b$ as in (9). Therefore $\theta^{\circ}\geq\theta_{\alpha}$. The upper bound follows from Theorem 5. ∎

The gap between $\theta^{\circ}$ and $\theta^{*}$ in Corollary 4 indicates that the price to pay for using randomized polynomial time tests for the sparse detection problem is essentially of order $\sqrt{k}$.

Acknowledgments: Philippe Rigollet is partially supported by the National Science Foundation grants DMS-0906424 and DMS-1053987. Quentin Berthet is partially supported by a Gordon S. Wu fellowship.

References

A Technical lemmas

For all $\mathbf{P}_{0}\in\mathcal{D}_{0}$, and $t>0$, it holds

We define the following events, for all $S\subset\{1,\ldots,d\}$, $u\in\mathbf{R}^{p}$, and $t>0$

By union on all sets of cardinal $k$, it holds

Furthermore, let $\mathcal{N}_{S}$, be a minimal covering $1/4$-net of $\mathcal{S}^{S}$, the set of unit vectors with support included in $S$. It is a classical result that $|\mathcal{N}_{S}|\leq 9^{k}$ as shown in [Ver10] and that it holds

By definition of $\mathcal{D}_{0}$, $\mathbf{P}_{0}(A_{u})\leq e^{-t}$ for $|u|_{2}=1$. The classical inequality ${d\choose k}\leq\big(\frac{ed}{k}\big)^{k}$ yields the desired result. ∎

For all $\mathbf{P}_{0}\in\mathcal{D}_{0}$, and $\delta>0$, it holds

We decompose $\hat{\Sigma}$ as the sum of its diagonal and off-diagonal matrices, respectively $\hat{\Delta}$ and $\hat{\Psi}$. Taking $U=-\hat{\Psi}$ in the dual formulation of the semidefinite program [BAd10, BR12] yields

We first control the largest off-diagonal element of $\hat{\Sigma}$ by bounding $|\hat{\Psi}|_{\infty}$ with high probability. For every $i\neq j$, we have

By definition of $\mathcal{D}_{0}$, it holds for $t>0$ that

Hence, by union bound on the off-diagonal terms, we get

Taking $t=\log(4p^{2}/\delta)$ yields that under $\mathbf{P}_{0}$ with probability $1-\delta/2$,

We control the largest diagonal element of $\hat{\Sigma}$ as follows. We have by definition of $\hat{\Delta}$, for all $i$

Similarly, by union bound over the $p$ diagonal terms, it holds

Taking $t=\log(2p/\delta)$ yields, under $\mathbf{P}_{0}$ with probability $1-\delta/2$,

The desired result is obtained by plugging (15) and (16) into (14). ∎