6
$\begingroup$

Let $F_n$ be the empirical distribution obtained from an i.i.d. sample of the distribution $F:R ^d \to [0, 1]$. Kiefer (1961) shows that the convergence of the empirical distribution is like $$ P\left( \left\lVert F_n - F\right\rVert_\infty > z \right) \le K \exp \left( - \left(2 - \epsilon\right) n z^2 \right) $$ where the constant $K$ depends on the dimension $d$ and the threshold $\epsilon >0$.

What is the order of the constant $K$?
Is it like $2^d$ or is it much smaller?

In the prood for the case $d=1$, I see that $K$ is approximatively the tail of some distribution, so it is small. For higher dimensions, the proof proceed by induction and I don't see how the value of $K$ evolves.

Definition of $F_n$:
For a vector $x$ in $R^d$, DKW defines the empirical distribution as the number of sample point $X_i$ satisfying $X_i < x$, coordinate-wise; divided by the number of sampled points $n$.

Reference:
DKW wiki
DKW d=1: Dvoretzky, Kiefer, Wolfowitz 1958
DKW d>1: Kiefer, Wolfowitz, 1958
DKW d>1, sharp exponent: Kiefer, 1961

Improve this question
$\endgroup$

3 Answers 3

Reset to default
1
$\begingroup$

For any distribution $F$ over the naturals $\mathbb{N}$, one can show the following DKW-type inequality: $$ \mathbb{P}(||F-F_n||_\infty > 1/\sqrt{n}+\epsilon) \le \exp(-2n\epsilon^2) $$ (in fact, it's known for the more general Markov case, see http://projecteuclid.org/euclid.jap/1421763330 )

I started to write something about $F$ being well-approximated by discrete distributions, but now I think the question may be ill-posed. How do you define the empirical $F_n$ in dimension $d>1$? In $R^1$ you can count how many sample points appeared to the left of $x$; what's the higher-dimensional analogue? For that matter, what's the analogue of a CDF in higher dimensions?

I'm leaving my answer because I think it's relevant for some reasonable reformulation of the question. The bottom line is that you should get dimension-free constants.

Improve this answer
$\endgroup$
1
  • $\begingroup$ The ECDF used by DKW is: given a vector $x$ in $R^d$, count the number of sample point $X_i$ that satisfies $X_i \le x$, coordinate-wise; divide by $n$. I see, I approximate $F$ by a step function supported on the natural number. $\endgroup$
    – user24451
    Apr 20, 2016 at 21:42
1
$\begingroup$

I recently found the constant is 2d asymptotically,

https://www.sciencedirect.com/science/article/pii/S016771522100050X

https://en.wikipedia.org/wiki/Dvoretzky%E2%80%93Kiefer%E2%80%93Wolfowitz_inequality

Improve this answer
$\endgroup$
1
$\begingroup$

I wrote the paper and the answer is 2d, at least asymptotically. In my paper, I actually prove that Kiefer’s lower bound argument is wrong. There are a handful of papers that also reach the incorrect conclusion. Largely based on Kiefer’s faulty 1958 counter example.

Improve this answer
$\endgroup$
1
  • $\begingroup$ This post is old, so I'm not sure if this comment gets noticed. I am currently trying to read your paper. I am wondering what happens when the dimension is also as large as number of points, say k > n? Should there not be a relation between $n$ and $k$ for this relation to be true? Else, if $n$ (and thus $k$) keeps growing, then the bound keeps getting tighter and tighter. That means - say 1000 samples in $R^{1000}$ yield a weaker bound than 2000 samples in $R^{2000}$. That means the number of samples keep dominating over the embedding dimension. Is that correct? $\endgroup$
    – Arnab
    May 2, 2022 at 22:16

Your Answer

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