# Bootstrap: the issue of overfitting

Suppose one performs the so-called non-parametric bootstrap by drawing $B$ samples of size $n$ each from the original $n$ observations with replacement. I believe this procedure is equivalent to estimating the cumulative distribution function by the empirical cdf:

http://en.wikipedia.org/wiki/Empirical_distribution_function

and then obtaining the bootstrap samples by simulating $n$ observations from the estimated cdf $B$ times in a row.

If I am right in this, then one has to address the issue of overfitting, because the empirical cdf has about N parameters. Of course, asymptotically it converges to the population cdf, but what about finite samples? E.g. if I were to tell you that I have 100 observations and I am going to estimate the cdf as $N(\mu, \sigma^2)$ with two parameters, you wouldn't be alarmed. However, if the number of parameters were to go up to 100, it wouldn't seem reasonable at all.

Likewise, when one employs a standard multiple linear regression, the distribution of the error term is estimated as $N(0, \sigma^2)$. If one decides to switch to bootstrapping the residuals, he has to realize that now there are about $n$ parameters used just to handle the error term distribution.

Could you please direct me to some sources that address this issue explicitly, or tell me why it's not an issue if you think I got it wrong.

• One way to view this "non-parametric" bootstrap is that it converts the parametric assumption of normality into a "quantity of interest" in some large, finite population (eg the mean of a Census of records). In fact, you can show that this version of the bootstrap is based on "maximum likelihood" estimates of the multinomial model, with 1 category for each distinct "type" in the population. – probabilityislogic Aug 28 '14 at 12:14

i am not completely sure i understand your question right... i am assuming you are interested in the order of convergence?

because the empirical cdf has about N parameters. Of course, asymptotically it converges to the population cdf, but what about finite samples?

Have you read any of the basics on bootstrap theory? The Problem is that it gets pretty wild (mathematically) pretty quickly.

Anyway, i recommend having a look at

van der Vaart "Asymptotic Statistics" chapter 23.

Hall "Bootstrap and Edgeworth expansions" (lengthy but concise and less handwaving than van der Vaart i'd say)

for the basics.

Chernick "Bootstrap Methods" is more aimed at users rather than mathematicians but has a section on "where bootstrap fails".

The classical Efron/Tibshirani has little on why bootstrap actually works...

Janssen and Pauls showed that bootstrapping a statistic works asymptotically, iff a central limit theorem could also have been applied. So if you compare estimating the parameters of a $\mathcal{N}(\mu,\sigma^2)$ distribution as the distribution of the statistic and estimating the statistic's distribution via bootstrap hits the point.

Intuitively, bootstrapping from finite samples underestimates heavy tails of the underlying distribution. That's clear, since finite samples have a finite range, even if their true distribution's range is infinite or, even worse, has heavy tails. So the bootstrap statistic's behaviour will never be as "wild" as the original statistic. So similar to avoiding overfitting due to too many parameters in (parametric) regression, we could avoid overfitting by using the few-parameter normal distribution.

Edit responding the comments: Remember you don't need the bootstrap to estimate the cdf. You usually use the bootstrap to get the distribution (in the broadest sense including quantiles, moments, whatever needed) of some statistic. So you don't necessarily have an overfitting problem (in terms of "the estimation due to my finite data looks too nice comparing to what I should see with the true wild distribution"). But as it turned out (by the cited paper and by Frank Harrel's comment below), getting such an overfitting problem is linked to problems with parametric estimation of the same statistics.

So as your question implied, bootstrapping is not a panacea against problems with parametric estimation. The hope that the bootstrap would help with parameter problems by controlling the whole distribution is spurious.

• It is still unclear how bootstrap manages to work given that the number of effective parameters involved in bootstrap is about the same as the samples size. I have one guess: the ultimate goal of bootstrap is not to estimate the entire distribution, but to estimate 1-2 statistics of the distribution. Therefore, despite that the empirical cdf that is embedded in the bootstrap is grossly overfitted, the 1-2 estimated statistics end up fine somehow. Did I get that right? – James Aug 27 '14 at 15:10
• The number of effective parameters is not the same as the sample size. The variance of the empirical cumulative distribution function is about the same as the variance of a parametric fit to the distribution when the distribution has 4 unknown parameters to estimate. One reason is that the empirical CDF estimates are forced to be in ascending order. – Frank Harrell Aug 27 '14 at 15:33
• Good point. Could you provide a reference? – James Aug 27 '14 at 19:31
• I wish I had one. I've shown this in the past by Monte Carlo simulation. – Frank Harrell Aug 27 '14 at 19:57
• @FrankHarrell: Do you mean $L_2$-norm of $\hat{F}-F$ or pointwise variance of $\hat{F}(x)-F(x)$? Or something else? – Horst Grünbusch Aug 28 '14 at 8:48

One source of intuition might be to compare rates of convergence for parametric CDFs vs ECDFs, for iid data.

By DKW, the empirical CDF converges to the true CDF at a $$n^{-1/2}$$ rate (not just at one point, but the supremum of the absolute difference over the whole domain of the CDFs): https://en.wikipedia.org/wiki/Dvoretzky%E2%80%93Kiefer%E2%80%93Wolfowitz_inequality http://www.stat.cmu.edu/~larry/=stat705/Lecture12.pdf

And by Berry-Esseen, the CDF of a sampling distribution for a single mean converges to its Normal limit at a $$n^{-1/2}$$ rate: https://en.wikipedia.org/wiki/Berry%E2%80%93Esseen_theorem (This is not quite what we want---we're wondering about how the estimated parametric CDF of the data converges, not about the sampling distribution. But in the simplest ideal case, where the data are Normal and $$\sigma$$ is known and we just need to estimate $$\mu$$, I imagine the rates of convergence should be the same for the data's CDF as for the mean's CDF?)

So in a certain sense, the rate at which you need to acquire more samples is the same, whether you're estimating the CDF using an empirical CDF or whether you're estimating a parameter directly using a sample-mean-type estimator. This might help justify Frank Harrell's comment that "The number of effective parameters is not the same as the sample size."

Of course, that's not the whole story. Although the rates don't differ, the constants do. And there's much more to the nonparametric bootstrap than ECDFs---you still need to do things with the ECDF once you estimate it.