Learning Unions of Omega(1)-Dimensional Rectangles

Abstract

We consider the problem of learning unions of rectangles over the domain [ b ]^ n , in the uniform distribution membership query learning setting, where both b and n are “large”. We obtain poly( n , log b )-time algorithms for the following classes: – poly ( n log b )- Majority of $O(\frac{\log(n \log b)} {\log \log(n \log b)})$ -dimensional rectangles. –Unions of poly(log( n log b )) many rectangles with dimension $O(\frac{\log^2 (n \log b)} {(\log \log(n \log b) \log \log \log (n \log b))^2})$ . – poly ( n log b )- Majority of poly ( n log b )- Or of disjoint rectangles with dimension $O(\frac{\log(n \log b)} {\log \log(n \log b)})$ Our main algorithmic tool is an extension of Jackson’s boosting- and Fourier-based Harmonic Sieve algorithm [13] to the domain [ b ]^ n , building on work of Akavia et al. [1]. Other ingredients used to obtain the results stated above are techniques from exact learning [4] and ideas from recent work on learning augmented AC ^ 0 circuits [14] and on representing Boolean functions as thresholds of parities [16].