A uniform Dvoretzky-Kiefer-Wolfowitz inequality
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2023
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866909719654825984 |
|---|---|
| author | Bartl, Daniel Mendelson, Shahar |
| author_facet | Bartl, Daniel Mendelson, Shahar |
| contents | We show that under minimal assumptions on a class of functions $\mathcal{H}$ defined on a probability space $(\mathcal{X},μ)$, there is a threshold $Δ_0$ satisfying the following: for every $Δ\geqΔ_0$, with probability at least $1-2\exp(-cΔm)$ with respect to $μ^{\otimes m}$,
\[ \sup_{h\in\mathcal{H}} \sup_{t\in\mathbb{R}} \left| \mathbb{P}(h(X)\leq t) - \frac{1}{m}\sum_{i=1}^m 1_{(-\infty,t]}(h(X_i)) \right| \leq \sqrtΔ;\]
here $X$ is distributed according to $μ$ and $(X_i)_{i=1}^m$ are independent copies of $X$.
The value of $Δ_0$ is determined by an unexpected complexity parameter of the class $\mathcal{H}$ that captures the set's geometry (Talagrand's $γ_1$-functional).
The bound, the probability estimate and the value of $Δ_0$ are all optimal up to a logarithmic factor. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2312_06442 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | A uniform Dvoretzky-Kiefer-Wolfowitz inequality Bartl, Daniel Mendelson, Shahar Probability We show that under minimal assumptions on a class of functions $\mathcal{H}$ defined on a probability space $(\mathcal{X},μ)$, there is a threshold $Δ_0$ satisfying the following: for every $Δ\geqΔ_0$, with probability at least $1-2\exp(-cΔm)$ with respect to $μ^{\otimes m}$, \[ \sup_{h\in\mathcal{H}} \sup_{t\in\mathbb{R}} \left| \mathbb{P}(h(X)\leq t) - \frac{1}{m}\sum_{i=1}^m 1_{(-\infty,t]}(h(X_i)) \right| \leq \sqrtΔ;\] here $X$ is distributed according to $μ$ and $(X_i)_{i=1}^m$ are independent copies of $X$. The value of $Δ_0$ is determined by an unexpected complexity parameter of the class $\mathcal{H}$ that captures the set's geometry (Talagrand's $γ_1$-functional). The bound, the probability estimate and the value of $Δ_0$ are all optimal up to a logarithmic factor. |
| title | A uniform Dvoretzky-Kiefer-Wolfowitz inequality |
| topic | Probability |
| url | https://arxiv.org/abs/2312.06442 |