<p>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.</p>

CC BY-SA 3.0
2015-10-26T05:58:41.933Z
2015-10-26T05:58:41.933Z
Vitaly
<p>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, <a href="http://arxiv.org/pdf/1201.1214v5.pdf" rel="nofollow">http://arxiv.org/pdf/1201.1214v5.pdf</a>). </p>

<p>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 <a href="http://arxiv.org/pdf/1411.2664v2.pdf" rel="nofollow">http://arxiv.org/pdf/1411.2664v2.pdf</a>) gives an example in which the concentration fails due to adaptive choice of the query. </p>

CC BY-SA 3.0
2015-10-25T14:20:15.530Z
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.
Sasho Nikolov
CC BY-SA 3.0
2015-10-25T15:59:26.893Z
@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.
Minkov
CC BY-SA 3.0
2015-10-25T16:39:11.070Z
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$.
Sasho Nikolov
CC BY-SA 3.0
2015-10-25T20:43:48.590Z
@SashoNikolov I see what you mean. I think so too. However, In this paper (Statistical Algorithms and a Lower Bound for Detecting Planted Cliques, http://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.
Minkov
CC BY-SA 3.0
2015-10-25T22:13:51.873Z
In the paper (Problem 1.1.) $n$ is the dimension of the distribution, not the number of samples.
Sasho Nikolov
CC BY-SA 3.0
2015-10-25T22:24:33.917Z
@SashoNikolov It is also the sample size of the problem. The original planted clique problem can be formulated using an $n \times n$ adjacency matrix. The closely related distributional planted biclique problem (Problem 1.1) says that the $n$ rows of the $n\times n$ adjacency matrix is i.i.d. drawn from a mixture (with $k/n$ probability containing the planted edges). So the sample size is indeed $n$.
Minkov
<machine-learning><lg.learning><st.statistics><query-complexity><privacy>
Tolerance parameter of statistical query model and adaptivity
Minkov
# Tolerance parameter of statistical query model and adaptivity

(Asked by: username_0 on 2015-10-25)

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.

**Tags:** machine-learning, lg.learning, st.statistics, query-complexity, privacy
> **Comments:**
> **username_1**: 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.  
> **username_0**: @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.  
> **username_1**: 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$.  
> **username_0**: @SashoNikolov I see what you mean. I think so too. However, In this paper (Statistical Algorithms and a Lower Bound for Detecting Planted Cliques, http://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.  
> **username_1**: In the paper (Problem 1.1.) $n$ is the dimension of the distribution, not the number of samples.  
> **username_0**: @SashoNikolov It is also the sample size of the problem. The original planted clique problem can be formulated using an $n \times n$ adjacency matrix. The closely related distributional planted biclique problem (Problem 1.1) says that the $n$ rows of the $n\times n$ adjacency matrix is i.i.d. drawn from a mixture (with $k/n$ probability containing the planted edges). So the sample size is indeed $n$.  

---

## 1 answers

### Answer by username_2 on 2015-10-26. Score: 5 | Accepted answer

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.


---

