PAC learning axis-aligned rectangles with respect to product distributions from multiple-instance examples

We describe a polynomial-time algorithm for learning axis-aligned rectangles in Q(d) with respect to product distributions from multiple-instance examples in the PAC model. Here, each example consists of n elements of Q(d) together with a label indicating whether any of the n points is in the rectangle to be learned. We assume that there is an unknown product distribution D over Q(d) such that all instances are independently drawn according to D. The accuracy of a hypothesis is measured by the probability that it would incorrectly predict whether one of n more points drawn from D was in the rectangle to be learned. Our algorithm achieves accuracy epsilon with probability 1 - delta in O(d(5)n(12)/epsilon(20)log(2)nd/epsilon delta) time.