On-line learning of rectangles and unions of rectangles

Abstract

We design efficient algorithms for on-line learning of axis-parallel rectangles (and for the union of two such rectangles) in the common model for on-line learning with equivalence queries. With regard to the learning of rectangles in arbitrary dimensionsd we solve the following open problem:

Is there an algorithm for on-line learning of rectangles Π ^d_i=1 {a _i ,a _i +1,...,b _i } over a discrete domain {1,...,n}^d whose error bound is polylogarithmic in the sizen ^d of the domain (i.e. polynomial ind and logn)?

We give a positive solution by introducing a new design technique that appears to be of some interest on its own. The new learning algorithm for rectangles consists of 2d separate search strategies that search for the parametersa ₁,b ₁,...,a _d ,b _d of the target rectangle. A learning algorithm with this type of modular design tends to fail because of the well known “credit assignment problem”: Which of the 2d local search strategies should be “blamed” when the global algorithm makes an error? We propose here a rather radical solution to this problem:each local search strategy that is possibly involved in an error of the global algorithm will be blamed. With this radical solution it is unavoidable that frequently local search strategies will be blamed incorrectly. We overcome this difficulty by employing local search strategies (“error tolerant binary search”) that are able totolerate such incorrect credit assignments. The structure of this learning algorithm is reminiscent of “finite injury priority constructions” in recursive function theory.

Section 4 contains another application of this design technique: an algorithm for learning the union of two rectangles in the plane.