Combinatorial methods in density estimation

By Luc Devroye, Gábor Lugosi. 2001

906 citations recorded by the source corpus.

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

Distributed Simulation and Distributed Inference (2018, background): “With more than a century of history (see the books [Tsy09, DL01]), distribution learning has recently seen a surge of interest in the computer science community as well, with a focus on discrete domains (see e.g. [ Dia16] for a survey of these recent developments).”
Distribution-Free Distribution Regression (2013, methodology): “For example, in functional regression (Ferraty and Vieu [2006]) the covariate is a function instead of a finite dimensional vector.”
Robust Estimators in High Dimensions without the Computational Intractability (2016, neutral): “Our results fit in the framework of density estimation, a classical problem in statistics with a rich history and extensive literature (see e.g., [27], [28], [29], [30], [31]).”
Being Robust (in High Dimensions) Can Be Practical (2017, neutral): “Since the VC-dimension of the set of all halfspaces is d + 1, this follows from the VC inequality [DL01], since we have more than Ω( d/ ( δ/ (4 ν log(1 /δ )) 2 ) samples.”
Hadamard Response: Estimating Distributions Privately, Efficiently, and with Little Communication (2018, background): “The problem has a rich, and vast literature (see e.g. [6, 39, 17, 18], and many others), with the primary goal of statistical eﬃciency, namely minimizing the sample complexity for estimation, which is the ﬁrst resource we consider.”
Communication Complexity in Locally Private Distribution Estimation and Heavy Hitters (2019, background): “Distribution estimation is a classical task in the centralized setting, where R observes the true samples X n , and it is known that [28] Distribution estimation under ε -LDP is also well studied in the past few years [29, 15, 30, 31, 32, 33, 34].”
Robust kernel density estimation (2008, methodology): “Since the sample mean is sensitive to outliers, we estimate it robustly via M -estimation, yielding a robust kernel density estimator (RKDE).”
Model-based RL in Contextual Decision Processes: PAC bounds and Exponential Improvements over Model-free Approaches (2018, methodology): “Now we deﬁne This construction is based on the Scheffé estimator, which was originally developed for density estimation in total variation (Devroye and Lugosi, 2012).”
FLAMBE: Structural Complexity and Representation Learning of Low Rank MDPs (2020, background): “See Devroye and Lugosi (2012); Sun et al. (2019) for more details.”
Concentration inequalities for Markov chains by Marton couplings and spectral methods (2012, unknown): “1 (due to [6]).”
Private Hypothesis Selection (2019, methodology): “6 describes the approach and privatization of [4] in more detail, which are morally equivalent to what we discuss here.”
Bandwidth selection in kernel density estimation: Oracle inequalities and adaptive minimax optimality (2010, background): “Devroye and Lugosi (1996, 1997, 2001) established oracle inequalities for s = 1.”
Estimation of Renyi Entropy and Mutual Information Based on Generalized Nearest-Neighbor Graphs (2010, methodology): “A version of the classical Kiefer-Dvoretzky-Wolfowitz theorem due to Massart gives a convenient way to do it; see e.g. Devroye and Lugosi (2001).”
A theory of transfer learning with applications to active learning (2012, methodology): “However, to derive results under the more general conditions we consider here, we require a more involved method: specifically, the minimum distance skeleton estimate explored by Yatracos (1985), Devroye and Lugosi (2001), specified as follows.”
Testing Identity of Structured Distributions (2014, background): “The well-known Vapnik-Chervonenkis (VC) inequality (see e.g., [DL01, p.31]) provides the information-theoretically optimal sample size to learn an arbitrary distribution q over [ n ] in this metric.”
Robust estimation via robust gradient estimation (2018, methodology): “We now consider the Huber contamination model and propose a heuristic based on Scheffe’s tournament estimator [6, 42] for hyper-parameter selection.”