This paper is about hypothesis testing of Gaussian Hidden Clique problem. It shows that, for any \epsilon, the case where there exists a planted clique of size L = (1-\epsilon) \sqrt{n} cannot be distinguished against the case where there is no hidden clique, using spectral methods. This complements the positive result of [12], where it is possible to distinguish the two cases using a spectral method, when L > (1+\epsilon) \sqrt{n}. The main technical contribution is a general analysis based on rank-1 perturbation of order-k symmetric Gaussian tensors, which may be of independent interest.

Quality: The result is technically sound as far as I have checked.

Clarity: The paper is well-written overall; I am confused about Equation (24) -- why does it follow directly from Lemma 5?

Originality: Although the proof technique based on Lemma 2 is quite interesting, to be honest, I am not able to evaluate the novelty since I am not familiar with the relevant literature of proving such lower bound.

Significance: the paper establishes an interesting result, which nicely complements the previous positive result on spectral methods. But the downside is that this is only a lower bound for ``spectral methods", which makes the usage rather restrictive. It seems that extending this lower bound to any efficient detection algorithm is not easy, since the technique heavily relies on the fact that the eigenvalues are conjugation-invariant.

This paper is about hypothesis testing of Gaussian Hidden Clique problem using spectral methods. The techniques are general, the results are interesting and nicely complements the existing lower bound.

The authors consider the following problem:

Given a symmetric matrix X of dimension n, design a spectral test (a statistical test that depends only on the eigenvalues of X)

to distinguish between the following two hypotheses:

H_0 = all elements are drawn from N(0,1)

H_{1,L} = there exists a submatrix that is drawn from N(1,1)

It is known that when L >= (1-\epsilon)\sqrt(n) there is a simple test (involving checking the top eigenvalue) to distinguish H_0 and H_{1,L}.

What the authors show is that the result is tight and that no spectral test is reliable for L \leq (1-\epsilon)\sqrt(n).

The authors also prove results regarding the analogous tensor variant in particular distinguishing among H_0: X = Z H_1: X = \beta v^{\otimes k} + Z

The papers' contribution is primarily theoretical and there are no experiments.

Questions/Concerns:

(1) It's not entirely clear to me what the machine learning applications are for such a problem.

(2) Could the authors explain why the eigenvalue distribution of \beta * vv^T + Z is the same as Z if the norm of v is fixed?

(3) Is there some intuition to why examining the top eigenvalue is sufficient for the gaussian clique problem (if L is large enough?)

(3) I don't have an intuitive understanding of Theorem 1. In particular, why spectral contiguity of H_{1,L} with respect to H_0 implies that no spectral test is reliable for L <= (1-\epsilon)\sqrt(n).

The authors prove some theoretical lower bounds for the gaussian hidden

clique problem in both matrices and tensors.

The contributions of the paper are primarily theoretical (i.e. no experiments).

I am not familiar with the related work and have some questions about some of the concepts that I detail below.

The paper provides a result on how the eigenvalues of a random matrix can be exploited to answer the detection problem "Gaussian hidden clique problem". The authors provide a tight result on how for small size of planted clique, the eigenvalues are not enough for the detection problem.

Revise the first sentence in the abstract. It is a very long sentence, and it is hard to read and understand it. I also suggest to move some of the related works discussion provided at the end of paper to the beginning in the introduction section.

The paper has a reasonable contribution, and it is clearly written.

We thank the reviewers for their useful and insightful comments. Our responses to some of the issues are summarized below:

1) Reviewer 2 asks for further pointers of applications of our result to the NIPS

community and notes that perturbations of matrices of

rank greater than one is of interest to researchers in machine learning.

Of course, spectral clustering provides another broad set of

application for spectral methods. Our approach may provide insights into the

limitations of spectral clustering. The main technical is to deal with higher-rank

structures, which we believe to be feasible.

2) Reviewer 2 correctly observes that our results are asymptotic, hence the

question arises to what extent they apply to finite instances that are encountered

in practice.

All calculations are explicit, and in principle we can derive explicit bounds on the

total variation distance for each fixed k. For instance in Eq. (27) the integral yields

E\Lambda^2 \le 1 + C'/n^{(k/2)-1}

for k\ge 3

Hence allready for $k=4$ the total variation decays at a linear rate.

3) Reviewer 2, raises the issue of spectral algorithms that use eigenvectors in

addition to eigenvalues. We believe that establishing the limitations

of such methods is of great interest. However, It should be noted that proving

unconditional hardness results for detection problems which consider both

eigenvectors and eigenvalues is unlikely, as the whole matrix is determined by its

eigenvalues and eigenvectors (up to permutations).

4) We thank reviewer 3 for his suggestion regarding the first sentence. We will make the first sentence shorter and easier to parse.

5) Reviewer 5 asks about Equation (24) -- why does it follow directly from Lemma 5?

This is a large deviations calculation. Eq. (24) follows from Lemma 5 applying Varadhan's lemma.

We agree that this point deserves a clarification in the text-we will add such a clarification.