On Learning Distributions from their Samples

By Sudeep Kamath, Alon Orlitsky, Dheeraj Pichapati, Ananda Theertha Suresh. 2015

140 citations recorded by the source corpus.

Subfields: Probabilistic & Bayesian Methods, Statistical Learning Theory

How researchers see this paper

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

In Probabilistic & Bayesian Methods

In Statistical Learning Theory

Citations in the corpus

Optimal Schemes for Discrete Distribution Estimation Under Locally Differential Privacy (2017, background): “This problem has been studie d n the non-private setting [5], [6], where we can learn the distribution from the raw samples.”
Discrete Distribution Estimation under Local Privacy (2016, background): “From (Kamath et al., 2015), the asymptotic performance of the empirical estimator under the (cid:96) 1 loss functions is given by where for any p ∈ S k .”
Learning Discrete Distributions from Untrusted Batches (2017, methodology): “For ℓ 1 error (equivalently, “total variation distance” or “statistical distance”), it is easy to show that the expected worst-case error is Θ( n/k ), and the recent work [KOPS15] establishes the exact ﬁrst-order coeﬃcients of this loss.”
Hadamard Response: Estimating Distributions Privately, Efficiently, and with Little Communication (2018, background): “| In non-private setting, the sample complexity of distribution estimation under these distances is known even including precise constants [10, 34].”
On the Equivalence between Positional Node Embeddings and Structural Graph Representations (2019, background): “An interesting question for future work is how well can we learn distributions (representations) from (node embeddings) samples, extending (Kamath et al., 2015) to graph representations.”
Statistical Windows in Testing for the Initial Distribution of a Reversible Markov Chain (2018, methodology): “…improved sample complexity over the basic approach of using the empirical distribution (see e.g. Chan et al. (2013); Daskalakis et al. (2012); Kamath et al. (2015); Diakonikolas et al. (2014); Daskalakis et al. (2015); Diakonikolas (2016); Diakonikolas and Kane (2016); Diakonikolas et al.…”
Competitive Distribution Estimation: Why is Good-Turing Good (2015, background): “Following [8], researchers have studied rn(∆k) and related quantities [9].”
Distributed Statistical Estimation of High-Dimensional and Nonparametric Distributions (2018, background): “In the centralized case, it has been shown in [3]–[5] that the minimax L1 risk of discrete distribution estimation is Θ( √ S n ).”
Optimal schemes for discrete distribution estimation under local differential privacy (2017, methodology): “In this paper, we consider the minimax estimation problem of a discrete distribution with support size k under locally differential privacy (see [6], [7] for the non-private setting).”
On the Robustness of Information-Theoretic Privacy Measures and Mechanisms (2018, background): “, the 1-minimax setting in [28] and references therein.”
Asymptotically optimal private estimation under mean square loss (2017, background): “This problem has been studied in the non-private setting [5], [6], where we can learn the distribution from the raw samples.”