On the sample complexity of mean estimation in $\ell_p$-norm

Question

Let $1\leq p\leq \infty$, let ${\cal D}$ be a distribution over $\mathbb{R}^d$, and assume its support is contained in the unit $p$-ball. What is the minimum number $n$ of i.i.d. samples $W_i\sim {\cal D}$, $i=1,\ldots,n$, needed to compute an estimator $\tilde W$ of the mean with the following guarantee?

$$ \mathbb{P}\{ \| \tilde W- \mathbb{E}_{W\sim {\cal D}}[W]\|_p \leq \varepsilon \} \geq 1-\delta. $$

I am particularly interested in how $n$ depends on $p$, $d$ and $\epsilon$.

I suspect this must have been studied in the past, but I haven't been able to find a reference. Other guarantees (e.g., in expectation) could also be useful.

Finally this question can be asked in more generality, considering an arbitrary norm, instead of $\|\cdot\|_p$. Any results in this direction would be very useful.

Answer 1

A closely related topic is that of concentration inequalities, which give you a bound (of the sort that you are looking for) which also depends on the number of samples (among other things). Concretely, the concept of Rademacher complexity is a standard tool to address this sort of problems. The Rademacher complexity can be understood as a permutation test, where you changes your labels randomly. When employed to the problem of estimating the mean, the bound tells you how likely is that you get close to the actual mean by chance (how concentrated are the samples around the mean, and thus, how stable are your estimates based on different samples).

To be more specific, for a sample, $X=(x_{i})$, of size $l$, drawn i.i.d. from a probability distribution, $D$, and for a real-valued function class, $F$, with domain $X$, the empirical Rademacher complexity is the random variable defined as, $$ \hat{R}_{l}(F) = E_{\sigma}\left[sup_{f \in F}\left|\frac{2}{l}\sum_{i=1}^{l}\sigma_{i}f(x_{i})\right|X\right] $$ where $\sigma = (\sigma_{1},...,\sigma_{l})$ are independent uniform $\pm1$-valued random variables. The Rademacher complexity is, $$ R_{l}(F) = E_{S \sim D}[\hat{R}_{l}(F)] = E_{S\sigma}\left[sup_{f \in F}\left|\frac{2}{l}\sum_{i=1}^{l}\sigma_{i}f(x_{i})\right|X\right] $$

The sup means that it looks for the highest correlation possible with random noise. Now, this concept is relevant because of the following theorem,

Given the above conditions, assuming that $F$ is the class of mappings from $X$ to the interval $[0,1]$, and let $(z_{i})$ be a sample of size $l$. If you fix $\delta \in (0,1)$, then with probability $1-\delta$ over random draws of size $l$, every $f \in F$ satisfies,

$$ E[f(z)] \leq \hat{E}[f(z)] + R_{l}(F) + \sqrt{\frac{ln(2/\delta)}{2l}} \leq \hat{E}[f(z)] + \hat{R}_{l}(F) + 3\sqrt{\frac{ln(2/\delta)}{2l}} $$

Notice that the hat is used to indicate the empirical expectation measured on a particular sample.

The idea is to find such a family of f´s and use the theorem. Since $D$ has a compact support, you know that $(W-E[W])^{2}/R$ is bounded in $[0,1]$, where $R$ is the radius of the ball.

Using the properties of the Rademacher complexity and a second theorem which gives you the Rademacher complexity for linear prediction (details can be found here and in great detail here), you get the following bound for your probability

$$ \sqrt{\frac{2R^{2}}{l}}\left(\sqrt2 + \sqrt{ln\frac{1}{\delta}}\right) $$

P.S. I just realized you referred to the p-norm. But still, you can use the Khintchine inequality to bound that quantity with the 2-norm.

Answer 2

Let me follow up on this question and answer. Indeed, the connection to Rademacher complexity of the linear functions from the dual body can be used to provide upper bounds for the problem. But this is not quite what Cristobal and myself are asking about. (Not to mention that the question we ask is even more fundamental).

Rademacher complexity characterizes the convergence rate of the empirical mean to the true mean. So it can give an upper bound. This upper bound is tight in many cases but we are interested in bounds that apply to any mean estimator.

We are also interested in results beyond the straightforward $L_2$ (or even $L_p$ for $p>2$ cases covered in the answer but general norms defined by a convex origin-centered body.

Answer 3

Thanks everybody for the answers. Rademacher complexity is in fact a useful tool to derive upper bounds. However, the sample complexity can also depend on the geometry of the convex body we are interested in. In this regard, one can use ideas of uniform smoothness and uniform convexity from Banach space theory to get the right rates. This is something well-known in some fields, but I haven't found a concise reference so we included the analysis in our paper (see Appendix B in http://arxiv.org/pdf/1512.09170v1.pdf)

Two questions that still remain for me are, first: How to derive lower bounds on sample complexity of empirical mean based on Rademacher complexity? This I suppose is standard, but I haven't found a reference. The second question is: Are there examples where empirical mean does not provide the best sample complexity for mean estimation?