Learning k-Modal Distributions via Testing
Constantinos Daskalakis, Ilias Diakonikolas, Rocco A. Servedio · 2012
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 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 is at most ∊. We give an efficient algorithm for this problem that runs in time poly(k, log(n), 1/ε). For , the number of samples used by our algorithm is very close (within an Õ(log(1/∊)) factor) to being information-theoretically optimal. Prior to this work computationally efficient algorithms were known only for the cases k = 0, 1 [Bir87b, Bir97]. A novel feature of our approach is that our learning algorithm crucially uses a new 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.