Dealing with Range Anxiety in Mean Estimation via Statistical Queries

By Vitaly Feldman. 2016

10 citations recorded by the source corpus.

We give algorithms for estimating the expectation of a given real-valued function $\phi:X\to {\bf R}$ on a sample drawn randomly from some unknown distribution $D$ over domain $X$, namely ${\bf E}_{{\bf x}\sim D}[\phi({\bf x})]$. Our algorithms work in two well-studied models of restricted access to data samples. The first one is the statistical query (SQ) model in which an algorithm has access to an SQ oracle for the input distribution $D$ over $X$ instead of i.i.d. samples from $D$. Given a query function $\phi:X \to [0,1]$, the oracle returns an estimate of ${\bf E}_{{\bf x}\sim D}[\phi({\bf x})]$ within some tolerance $\tau$. The second, is a model in which only a single bit is communicated from each sample. In both of these models the error obtained using a naive implementation would scale polynomially with the range of the random variable $\phi({\bf x})$ (which might even be infinite). In contrast, without restrictions on access to data the expected error scales with the standard deviation of $\phi({\bf x})$. Here we give a simple algorithm whose error scales linearly in standard deviation of $\phi({\bf x})$ and logarithmically with an upper bound on the second moment of $\phi({\bf x})$. As corollaries, we obtain algorithms for high dimensional mean estimation and stochastic convex optimization in these models that work in more general settings than previously known solutions.

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

Citations in the corpus

The Power of the Hybrid Model for Mean Estimation (2018, background): “However, DP mean estimation of distributions under both the TCM and LM has been studied since the models’ introductions [17, 21, 56], and continues to be actively studied to this day [2, 15, 18, 20, 22, 28, 29, 32, 37, 39–42].”
A General Characterization of the Statistical Query Complexity (2016, methodology): “More generally, the oracle can be used to estimate of the expectation Ex∼D[φ(x)] for any real-valued function φ within Õ(σ/ √ n), where σ is the standard deviation of φ(x) (Feldman, 2016).”
Generalization for Adaptively-chosen Estimators via Stable Median (2017, methodology): “We now describe another simple and “folklore” algorithm (e.g. Raskhodnikova and Smith, 2010; Feldman, 2016) for finding an approximate median of a distribution that reduces the problem to O(log |T |) statistical queries.”