Asymptotic Minimax Character of the Sample Distribution Function and of the Classical Multinomial Estimator

By A. Dvoretzky, J. Kiefer, J. Wolfowitz. 1956

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 − β .”
High-Confidence Off-Policy Evaluation (2015, methodology): “Anderson (AM) inequality: The Anderson inequality (Anderson 1969) is based on the Dvoretzky-Kiefer-Wolfowitz inequality (Dvoretzky, Kiefer, and Wolfowitz 1956), and the variant we use here is with the optimal constants found by Massart (1990).”
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).”
A System for Massively Parallel Hyperparameter Tuning (2018, background): “Intuitively, in the ﬁrst rung with n evaluated conﬁgurations, the number of mispromoted conﬁgurations is roughly √ n , since the process resembles the convergence of an empirical cumulative distribution function (CDF) to its expected value (Dvoretzky et al., 1956).”
Massively Parallel Hyperparameter Tuning (2018, background): “, the Dvoretzky-Kiefer-Wolfowitz inequality (Dvoretzky et al., 1956)).”
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.”
Testing Shape Restrictions of Discrete Distributions (2015, background): “11 ([32, 40]) Let D be a distribution over [n].”
An exponential inequality for the distribution function of the kernel density estimator, with applications to adaptive estimation (2009, background): “Another direct consequence is a Dvoretzky–Kiefer–Wolfowitz [10] type inequality (up to constants) for the distribution function of the classical kernel density estimator with mean-integrated-squared error (MISE) optimal (and other) bandwidths.”
Sequential estimation of quantiles with applications to A/B testing and best-arm identification (2019, methodology): “Szörényi et al. include a confidence sequence valid over quantiles and time, derived via a union bound applied to the DKW inequality (Dvoretzky et al., 1956, Massart, 1990), similar to the bound used by Darling and Robbins (1968, Theorem 4).”
Minimax optimality of permutation tests (2020, methodology): “This argument may be formally justified using the Dvoretzky-Kiefer-Wolfowitz inequality (Dvoretzky et al., 1956).”
Sharper Bounds for Gaussian and Empirical Processes (1994, unknown): “[3].”
Information-Theoretically Secret Key Generation for Fading Wireless Channels (2009, methodology): “Lemma 1: [26] Let X1, · · · , Xn be real-valued, i.”
Meritocratic Fairness for Cross-Population Selection (2017, methodology): “As we show, our bound has a tighter dependence on p ij , which gives better utility guarantee than using the standard DKW inequality of Dvoretzky et al. (1956).”