3
$\begingroup$

Consider a standard statistical estimation problem with iid real observations $\{X_i\}_{i=1}^N$. For a collection of real functions $\mathcal{F}$, I want to get an estimate of the uniform rate of convergence

$E[\sup_{f\in\mathcal{F}} (\frac{1}{N}\sum_i f(X_i) - E[f(X)])^2]$

For a single square integrable $\mathcal{F}=\{f\}$, the above quantity is classically $O(N^{-1})$. Given $f$ bounded and equicontinuous, the results of Ranga Rao* show that $\sup_{f}\{\frac{1}{N}\sum_i f(X_i) - E[f(X)]\}\to 0$ almost surely, but don't provide a rate.

I can show, assuming $\mathcal{F}$ is a family of functions which are bounded with bounded derivatives (uniformly both in space and $\mathcal{F}$) and $P$ is a measure under which $X$ has a $C^3$ density, that an error of $O(N^{-2/5 })$ is guaranteed (this comes from using a kernel density estimator as an interim step).

It seems a better estimate, under less assumptions, should be possible - does anyone know a source?

*R. Ranga Rao, Relations between Weak and Uniform convergence of measures with applications, Ann. Math. Stat, 1962

$\endgroup$
5
  • 1
    $\begingroup$ Can you add a link to your derivation of $O(N^{-2/3})$? $\endgroup$ Jul 28, 2016 at 13:51
  • $\begingroup$ Ok, I realized an error in my argument, so the error is only $O(N^{-2/5})$. A summary is as follows: Let $\phi_{Nh}$ be a kernel density estimator with bandwidth $h$, for example, $\phi_{Nh}(x) = (F_n(x+h)-F_n(x-h))/2h$ where $F_n$ is the empirical cdf. For any $f$ in $\mathcal{F}$, direct calculation shows a uniform bound $|\frac{1}{N}\sum f(X_i) - \int f(x) \phi_{Nh}(x) dx| = O(h).$ From standard kernel estimation(see e.g. Rosenblatt, 1955) we have $E(\phi_{Nh}(y)-\phi(y))^2 = O((nh)^{-1}+h^4)$ uniformly in $y$. $\endgroup$
    – Sam Cohen
    Jul 28, 2016 at 16:30
  • $\begingroup$ As $\phi_{Nh}$ and $\phi$ are both densities, writing $g=\phi_{Nh}-\phi$, Markov's inequality shows that $(\int f g)^2 \leq 2C(k (\int_{-k}^k g^2) + 4 k^{-2})$ where $C$ is a bound on $f$, and hence, taking $h=N^{-1/5}$, $k = N^{1/5}$, integrating and adding, we get the estimate of total error, (ignoring constants) $E[\sup_f (N^{-1}\sum f(X_i) - \int f(x) \phi(x) dx)^2] = O(h^2) + O(k^2/(Nh) + k^2 h^4 + k^{-2}) = O(N^{-2/5})$ $\endgroup$
    – Sam Cohen
    Jul 28, 2016 at 16:36
  • $\begingroup$ All right. What makes you believe that this result can be improved? $\endgroup$ Jul 28, 2016 at 17:03
  • $\begingroup$ I just realized that this argument also requires that $X$ has a first moment under $P$. In general, if $X$ has a $r$th moment under $P$, then by tweaking Markov's inequality you can get $O(N^{-(2/(3+2/r))})$ (which gives my original $O(N^{-2/3})$ when $P$ is compactly supported). I think it can be improved because using a kernel density estimator introduces quite a lot of error, and does not form part of the original problem. $\endgroup$
    – Sam Cohen
    Jul 28, 2016 at 17:41

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.