Dvoretzky-Kiefer-Wolfowitz Vs. KDE fractional convergence

Question

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.

Answer 1

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!

Answer 2

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.