

























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.
此内容由惯性聚合(RSS阅读器)自动聚合整理,仅供阅读参考。 原文来自 — 版权归原作者所有。