1
$\begingroup$

The DKW bound says, roughly and under very general assumptions, that the empirical CDF of $n$ iid samples of a random variable $X$ converges to the exact CDF of $X$ exponentially with the number of samples.

On the other hand, it is known that for smooth PDFs (densities), a KDE estimator, which is optimal in the min-max sense, converges no faster then $n^{-1}$, where $n$ is the number of samples [*].

My question: How can it be that the estimation of a CDF is so efficient, compared to the estimation of the PDF, which is often just the derivative of the CDF? How is this "gap" be explained mathematically?

  • See AB Tsybakov, Introduction to nonparametric estimation.
$\endgroup$
2
$\begingroup$

This has nothing to do with the pdf, cdf, the DKW bound or kernel estimation. Like BatWannaBe suggested, you're actually confusing two types of convergence, convergence in probability: $$\mathbb P(|X_n - X^*| > \epsilon) \rightarrow 0$$ for any fixed $\epsilon$, and convergence in mean (or $L_2$ norm): $$\mathbb E[|X_n - X^*|^2] \rightarrow 0$$ Taking for example the simplest situation, the estimation of the mean $\mu$ by the empirical mean $\hat \mu_n$, you have both $$\mathbb E[||\hat{\mu}_n - \mu|^2] = \frac{\sigma^2}{n}$$ by simple arithmetic for any random variable with finite variance, and $$\mathbb P(|\hat{\mu}_n - \mu| > \epsilon) \leq e^{-2n(b-a)^2 \epsilon^2}$$using Hoeffding's bound for any bounded random variable. No contradiction here!

$\endgroup$
1
$\begingroup$

I don't know anything about KDE, so I can't really help you there. However, iirc, it's the probability of the deviation of the ECDF from the CDF being less than or equal to a constant error term that has an exponential rate of convergence. On the other hand, if you kept that probability constant, the error term has a $\sqrt{n}$ rate of convergence.

$\endgroup$

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.