Learning $k$-Modal Distributions via Testing

Constantinos Daskalakis, Ilias Diakonikolas, Rocco A. Servedio

A $k$-modal probability distribution over the discrete domain $\{1,...,n\}$ is one whose histogram has at most $k$ "peaks" and "valleys." Such distributions are natural generalizat…