Statistical query model with Gaussian noise?

Question

Kearns' statistical query model is a well-known learning model with noise tolerance. The statistical query oracle takes as input a statistical query of the form $\{\chi, \tau\}$. Here $\chi$ is any mapping of a labeled example to $\{0, 1\}$ and $\tau \in [0, 1]$ is called the noise tolerance. The oracle returns an estimate for the expectation $\mathbf{E}\chi$, that is, the probability that $\chi = 1$. The additive error of this estimate is at most $\tau$.

The statistical query oracle only guarantees an upper bound of the noise and Kearns' model mentions nothing about the noise distribution. Is there any query oracle in computational learning theory that can answer a statistical query with normal distributed noise? That is, the oracle takes as input a statistical query of the form $\{\chi, \sigma^2\}$ and returns the estimate of $\mathbf{E}\chi$ with additive error of Gaussian distribution $\mathcal{N}(0, \sigma^2)$.

I think this model is reasonable because Gaussian noise is a common assumption in many problems. Also, for central limit theorem, the estimate will converge to a Gaussian distribution (but we are not able to control the variance).

Answer 1

We know something close to what you want.

If you look at Ke Yang's "Honest Statistical Queries" -- there is no noise at all, but only "sampling error". In this model, you pass in a parameter $t$, and the Oracle takes $t$ samples, honestly evaluates the passed-in function (onto {0,1}), and returns the average value of the function on the samples.

In effect, this estimates the expected value of the function. It is easy to see that this Oracle samples from the Binomial distribution $B(t, E_{x \sim D}(f(x))$. For small skew and large $t$, this is approximated by the Normal. We extended this to explicitly consider variance here.

The punchline, basically, is that SQ lower bounds still hold in this non-adversarial noise setting. Actually the SQ lower bounds are even harsher because they work for sample sizes $t=1$, where the algorithm sees the result of its function evaluation on every random sample (and can average or do anything by itself).