2
$\begingroup$

It seems that the reasonable assumption for the tolerance parameter of statistical query model is roughly $1/\sqrt{n}$, which is obtained from concentration inequalities (see, e.g., Definition 2.3 of Statistical Algorithms and a Lower Bound for Detecting Planted Cliques, http://arxiv.org/pdf/1201.1214v5.pdf).

My question is why this is a reasonable choice. The rationale of this choice seems to come from the argument that the oracle can return the average of the query function over $n$ data points. However, since the query function is adaptively chosen, the $1/\sqrt{n}$ rate of concentration does not always hold. This is because the query function itself also depends on data and thus the independence is ruined. For example, this paper (Section A, Preserving Statistical Validity in Adaptive Data Analysis http://arxiv.org/pdf/1411.2664v2.pdf) gives an example in which the concentration fails due to adaptive choice of the query.

$\endgroup$
  • 2
    $\begingroup$ Adaptive queries are problematic when the same dataset is used to answer them. However, if you use independent samples for each new query, even if the query is based on prior queries, independence still holds. $\endgroup$ – Sasho Nikolov Oct 25 '15 at 14:20
  • $\begingroup$ @SashoNikolov I totally agree. We still have independence if we use new samples. However, this will increase the real sample size from $n$ to $T n$, where $T$ is the number of iterations. This changes the problem itself, since we only have $n$ data points. $\endgroup$ – Minkov Oct 25 '15 at 15:59
  • 2
    $\begingroup$ Well, yes, but I do not understand your question. The sample complexity of an SQ algorithm that makes T queries to an oracle with tolerance $\tau$ is on the order of $T/\tau^2$. $\endgroup$ – Sasho Nikolov Oct 25 '15 at 16:39
  • $\begingroup$ @SashoNikolov I see what you mean. I think so too. However, In this paper (Statistical Algorithms and a Lower Bound for Detecting Planted Cliques, arxiv.org/pdf/1201.1214v5.pdf), they consider the distributional planted clique problem, which has $n$ independent data points. Then according to what you said, the tolerance should be set to $\tau = \sqrt{T/n}$, instead of $\sqrt{1/n}$ as in their paper. $\endgroup$ – Minkov Oct 25 '15 at 20:43
  • $\begingroup$ In the paper (Problem 1.1.) $n$ is the dimension of the distribution, not the number of samples. $\endgroup$ – Sasho Nikolov Oct 25 '15 at 22:13
5
$\begingroup$

What you are saying is that given $N$ random samples one cannot simulate an algorithm that makes $T$ queries to VSTAT$(N)$. If the $T$ queries are chosen adaptively then one might need more samples (the best upper bound is $\sqrt{T} N$ samples). This is true but not an issue for the planted clique paper you mentioned. That paper is concerned with proving a lower bound against algorithms using VSTAT. Specifically we prove that any algorithm using a polynomial number of queries to VSTAT$(N)$ will not be able to solve the planted $k$-biclique problem for $N=\tilde{\Omega}(n^2/k^2)$ ($n$ is the number of vertices on each side). Answering even a single query to VSTAT$(N)$ requires $\Omega(N)$ samples so the lower bound reflects the difficulty of solving the problem with with $N$ (or less) samples.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.