The Tight Constant in the Dvoretzky-Kiefer-Wolfowitz Inequality

By Pascal Massart. 1990

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

Citations in the corpus

The power of synergy in differential privacy: Combining a small curator with local randomizers (2019, background): “Speciﬁcally, by the Dvoretzky-Kiefer-Wolfowitz inequality [23, 45], assuming that n and m are at least Ω 1 α 4 log( 1 β ) , this happens with probability at least 1 − β .”
Wasserstein Fair Classification (2019, background): “Since P ∈ { P S , P ¯ S } ∪ { P S a } a ∈A are all continuous, the Dvorestky-Kiefer-Wolfowitz theorem (see main theorem in Massart (1990) ) and the condition min (cid:2) ¯ N, min a (cid:2) N a (cid:3)(cid”
Being Robust (in High Dimensions) Can Be Practical (2017, background): “, 1986), and under certain models it is in fact optimal in terms of its resilience to noise (Dvoretzky et al., 1956; Massart, 1990; Chen, 1998; Daskalakis & Kamath, 2014; Diakonikolas et al., 2017).”
Open Category Detection with PAC Guarantees (2018, methodology): “Our key theoretical tool is a ﬁnite sample result on the uniform convergence of empirical CDF functions (Massart, 1990).”
DELTA METHOD IN LARGE DEVIATIONS AND MODERATE DEVIATIONS FOR ESTIMATORS (2011, background): “The detailed description onM -estimators can be found in Serfling (1980). Jurečková, Kallenberg and Veraverbeke (1988), Arcones (2002) and Inglot and Kallenberg (2003) studied moderate deviations for M -estimators.”
Consistency of the kernel density estimator: a survey (2012, background): “Using the inequality of Dvoretzky et al. (1956), using Massart’s constant (Massart 1990), it holds for arbitrary λ > 0: P ( ||Fn(x)− F (x)||∞ > λ√ n ) ≤ 2 exp(−2λ2).”
Concentration inequalities for Markov chains by Marton couplings and spectral methods (2012, result): “When taken together, our results generalise the well-known Dvoretzky-Kiefer-Wolfowitz inequality (see [11], [37]) to the total variational distance case, for Markov chains.”
On the Convergence of the Empirical Distribution (2012, background): “A uniform strong law of large numbers is provided by the DvoretzkyKiefer-Wolfowitz inequality [6, 10] P (”
Simple Bounds for the Convergence of Empirical and Occupation Measures in 1-Wasserstein Distance (2011, background): “As a consequence of the celebrated Dvorestky-Kiefer-Wolfowitz theorem (see [25], [30]), we have the following : if μ ∈ P(R) has a continuous c.”
Differentially Private Release and Learning of Threshold Functions (2015, unknown): “This follows from using the Dvoretzky-Kiefer-Wolfowitz inequality [DKW56, Mas90] in place of Theorem 4.11.”
Finite Sample Differentially Private Confidence Intervals (2017, background): “Moreover, the Dvoretzky-Kiefer-Wolfowitz inequality (Massart, 1990) tells us that with high probability the empirical estimates are close to the population parameters: P X∼D ( max k |p̂k − pk| > β ) ≤ 2 exp(−2nβ2).”
Random Differential Privacy (2011, result): “We will report on these results in future work.”