Learning $k$-Modal Distributions via Testing

Details Learning $k$-Modal Distributions via Testing Learning $k$-Modal Distributions via Testing

2011-07-13

arxiv.org/abs/1107.2700v2

Computer Science

Data Structures and Algorithms

Scientific paper

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 $\hat{p}$ such that with high probability the total variation distance between $p$ and $\hat{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 \leq \tilde{O}(\sqrt{\log n})$, 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.

Affiliated with

Also associated with

No associations

Rating

Learning $k$-Modal Distributions via Testing does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Learning $k$-Modal Distributions via Testing, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Learning $k$-Modal Distributions via Testing will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-224571