Learning k-Modal Distributions via Testing

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.