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.

  • $\begingroup$ Naively, I don't expect there to be a general answer which depends only on p,d and $\epsilon$. The answer ought to depend on the tail behavior of D. For a simple example take a normal distribution with mean 0 and variance 0.1 (truncated at 1 and renormalized) and the uniform distribution on [-1,1] with d=1 $\endgroup$ – Sid May 29 '15 at 21:25
  • 1
    $\begingroup$ Apparently the question is about the worst case bound over all possible distributions supported on the unit $\ell_p$-ball. $\endgroup$ – Vitaly May 30 '15 at 0:25
  • $\begingroup$ Which is the framework of this question? a homework, a thesiswork? $\endgroup$ – Brethlosze May 30 '15 at 0:49
  • $\begingroup$ This appears to be the Law of Large Numbers in its weak form. The question is about the Limit Behaviour under the theorem. As per Chebychev lemma, for $d=1$, with a $\delta(n)=s^2/(e^2 n)$ convergence of the limit, with $s^2$ an estimator of the variance, surely there are other bound for the $n$ behaviour.... $\endgroup$ – Brethlosze May 30 '15 at 1:23
  • $\begingroup$ Thanks everybody! This question appeared in my research: I want to compare estimators obtained from iid samples to an alternative model (Statistical Queries); now I have some bounds for the latter, but I don't know what is known for the former. As it was pointed out by Vitaly, the idea is to obtain a worst-case bound for arbitrary distributions, and thus bounds depending on variance are rather weak. $\endgroup$ – Cristóbal Guzmán May 30 '15 at 21:32

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.

  • $\begingroup$ This is a great answer. I'm just going to suggest 3 references: An introductory tutorial: cs.cornell.edu/~sridharan/concentration.pdf --- Related to machine learning, including a discussion on Rademacher complexity, lectures 00-004 cs.nyu.edu/~mohri/ml14 --- And if you can get your hands on it, Foundations of Machine Learning by Mohri, Rostamizadeh, and Talwalkar (2012). $\endgroup$ – justanotherbrain Jun 10 '15 at 0:31
  • $\begingroup$ I apologize for the delay. Rademacher complexity is indeed useful to tackle this question: at least we were able to effectively characterize the sample complexity for $\ell_p$-balls. However, there is an additional tool which is not mentioned in this post, so I will leave an answer about it. $\endgroup$ – Cristóbal Guzmán Jan 23 '16 at 12:32

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.


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?


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.