On parallel attribute-efficient learning

摘要

This paper continues our earlier work on (non)adaptive attribute-efficient learning. We consider exact learning of Boolean functions of n variables by membership queries, assuming that at most r variables are relevant. The learner works in consecutive rounds, such that the set of simultaneous queries in every round may depend on all information gained so far. For deterministic learning of specific monotone functions we prove that any strategy that uses an optimal query number needs Θ(r) rounds in the worst case. Furthermore, we make some progress regarding the constant factors in nearly query-optimal strategies. For example, we propose a strategy using roughly 2r+1+2ηlog2n queries in 3r rounds. In contrast to the limitations of deterministic strategies, there is a randomized strategy that learns monotone functions by 2O(r)+O(rlogn) expected queries in O(logr) expected rounds. Actually, this result holds in more general function classes. The second part of the paper addresses the computational complexity of parallel learning of arbitrary Boolean functions with r relevant variables. We obtain several strategies which use a constant number of rounds, O(2rpoly(rlogn)) queries, and only 2O(r)npoly(logn) computations.