Instance optimal learning of discrete distributions

By Gregory Valiant, Paul Valiant. 2016

62 citations recorded by the source corpus.

We consider the following basic learning task: given independent draws from an unknown distribution over a discrete support, output an approximation of the distribution that is as accurate as possible in L1 distance (equivalently, total variation distance, or "statistical distance"). Perhaps surprisingly, it is often possible to "de-noise" the empirical distribution of the samples to return an approximation of the true distribution that is significantly more accurate than the empirical distribution, without relying on any prior assumptions on the distribution. We present an instance optimal learning algorithm which optimally performs this de-noising for every distribution for which such a de-noising is possible. More formally, given n independent draws from a distribution p, our algorithm returns a labelled vector whose expected distance from p is equal to the minimum possible expected error that could be obtained by any algorithm, even one that is given the true unlabeled vector of probabilities of distribution p and simply needs to assign labels---up to an additive subconstant term that is independent of p and goes to zero as n gets large. This somewhat surprising result has several conceptual implications, including the fact that, for any large sample from a distribution over discrete support, prior knowledge of the rates of decay of the tails of the distribution (e.g. power-law type assumptions) is not significantly helpful for the task of learning the distribution. As a consequence of our techniques, we also show that given a set of n samples from an arbitrary distribution, one can accurately estimate the expected number of distinct elements that will be observed in a sample of any size up to n log n. This sort of extrapolation is practically relevant, particularly to domains such as genomics where it is important to understand how much more might be discovered given larger sample sizes, and we are optimistic that our approach is practically viable.

Subfields: Artificial Intelligence

How researchers see this paper

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

In Artificial Intelligence

Citations in the corpus

Learning Discrete Distributions from Untrusted Batches (2017, background): “Beyond this worst-case setting, there has also been signiﬁcant work considering this learning problem with the goal of developing “instance optimal” algorithms that leverage whatever structure might be present in the given distribution (see e.g. [OS15, VV16]).”
Statistical Windows in Testing for the Initial Distribution of a Reversible Markov Chain (2018, methodology): “…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. (2017b,a); Valiant and Valiant (2014, 2016)).”
Learning Populations of Parameters (2017, background): “Such a multiset can be used to estimate useful properties of the distribution that do not depend on the labels of the domain of the distribution, such as the entropy or support size of the distribution, or the number of elements likely to be observed in a new, larger sample [12, 17].”