Learning k-Modal Distributions via Testing

Constantinos Daskalakis, Ilias Diakonikolas, Rocco A. Servedio

Research output: Working paper

Abstract / Description of output

A k -modal probability distribution over the domain {1,...,n} is one whose histogram has at most k "peaks" and "valleys." Such distributions are natural generalizations of monotone (k=0 ) and unimodal (k=1 ) probability distributions, which have been intensively studied in probability theory and statistics.
In this paper we consider the problem of \emph{learning} an unknown k -modal distribution. The learning algorithm is given access to independent samples drawn from the k -modal distribution p , and must output a hypothesis distribution p ^ such that with high probability the total variation distance between p and p ^ is at most $\eps.$
We give an efficient algorithm for this problem that runs in time $\poly(k,\log(n),1/\eps)$. For k≤O ~ (logn − − − − √ ) , the number of samples used by our algorithm is very close (within an $\tilde{O}(\log(1/\eps))$ factor) to being information-theoretically optimal. Prior to this work computationally efficient algorithms were known only for the cases k=0,1.
A novel feature of our approach is that our learning algorithm crucially uses a new \emph{property testing} algorithm as a key subroutine. The learning algorithm uses the property tester to efficiently decompose the k -modal distribution into k (near)-monotone distributions, which are easier to learn.
Original languageEnglish
PublisherComputing Research Repository (CoRR)
Volumeabs/1107.2700
Publication statusPublished - 2011

Fingerprint

Dive into the research topics of 'Learning k-Modal Distributions via Testing'. Together they form a unique fingerprint.

Cite this