Learning structured distributions

Ilias Diakonikolas

Research output: Chapter in Book/Report/Conference proceedingChapter

Abstract / Description of output

Discovering hidden structure in data is one of the cornerstones of modern
data analysis. Due to the diversity and complexity of modern data sets, this
is a very challenging task and the role of efficient algorithms is of paramount
importance in this context. The majority of available data sets are in raw
and unstructured form, consisting of example points without corresponding
labels. A large class of unlabeled datasets can be modeled as samples from a
probability distribution over a very large domain. An important goal in the
exploration of these datasets is understanding the underlying distributions.
Estimating distributions from samples is a paradigmatic and fundamental
unsupervised learning problem that has been studied in statistics since the late
nineteenth century, starting with the pioneering work of Karl Pearson [55].
During the past couple of decades, there has been a large body of work in
computer science on this topic with a focus on computational efficiency.
The area of distribution estimation is well-motivated in its own right, and
has seen a recent surge of research activity, in part due to the ubiquity of
structured distributions in the natural and social sciences. Such structural
properties of distributions are sometimes direct consequences of the underlying
2 Learning Structured Distributions
application problem, or they are a plausible explanation of the model under
In this chapter, we give a survey of both classical and modern techniques
for distribution estimation, with a focus on recent algorithmic ideas developed
in theoretical computer science. These ideas have led to computationally and
statistically efficient algorithms for learning broad families of models. For the
sake of concreteness, we illustrate these ideas with specific examples. Finally,
we highlight outstanding challenges and research directions for future work.
Original languageEnglish
Title of host publicationHandbook of Big Data
PublisherCRC Press
Number of pages22
Publication statusPublished - 2016


Dive into the research topics of 'Learning structured distributions'. Together they form a unique fingerprint.

Cite this