























In this paper, we revisit the concentration inequalities for the supremum of the cumulative distribution function (CDF) of a real-valued continuous distribution as established by Dvoretzky, Kiefer, Wolfowitz and revisited later by Massart in two seminal papers. We focus on the concentration of the \emph{local} supremum over a sub-interval, rather than on the full domain. That is, denoting $U$ the CDF of the uniform distribution over $[0,1]$ and $U_n$ its empirical version built from $n$ samples, we study $P(\sup_{u\in[\underline{u},\overline{u}]}U_n(u)-U(u)>ε)$ for different values of $\underline{u},\overline{u}\in[0,1]$. Such local controls naturally appear for instance when studying estimation error of spectral risk-measures (such as the conditional value at risk), where $[\underline{u},\overline{u}]$ is typically $[0,α]$ or $[1-α,1]$ for a risk level $α$, after reshaping the CDF $F$ of the considered distribution into $U$ by the general inverse transform $F^{-1}$. Extending a proof technique from Smirnov, we provide exact expressions of the local quantities $P(\sup_{u\in[\underline{u},\overline{u}]}U_n(u)-U(u)>ε)$ and $P(\sup_{u\in [\underline{u},\overline{u}]}U(u)-U_n(u)>ε)$ for each $n,ε,\underline{u},\overline{u}$. Interestingly these quantities, seen as a function of $ε$, can be easily inverted numerically into functions of the probability level $δ$. Although not explicit, they can be computed and tabulated. We plot such expressions and compare them to the classical bound $\sqrt{\frac{\ln(1/δ)}{2n}}$ provided by Massart inequality. Last, we extend the local concentration results holding individually for each $n$ to time-uniform concentration inequalities holding simultaneously for all $n$, revisiting a reflection inequality by James, which is of independent interest for the study of sequential decision making strategies.
此内容由惯性聚合(RSS阅读器)自动聚合整理,仅供阅读参考。 原文来自 — 版权归原作者所有。