The query complexity of finding local minima in the lattice

In this paper we study the query complexity of finding local minimum points of a boolean function. This task occurs frequently in exact learning algor ithms for many natural classes, such as monotone DNF. O(log n)-term DNF, un ate DNF, and decision trees. On the negative side, we prove that any (possi bly randomized) algorithm that produces a local minimum of a function f cho sen from a sufficiently "rich" concept class, using a membership oracle for f, must ask Omega (n(2)) membership queries in the worst case. In particul ar, this lower bound applies to the class of decision trees. A simple algor ithm is known that achieves this lower bound. On the positive side, we show that for the class O(log n)-term DNF finding local minimum points requires only Theta (n log n) membership queries (and more generally Theta (tn) mem bership queries for t-term. DNF with t less than or equal to n). This effic ient procedure improves the time and query complexity of known learning alg orithms for the class O (log n)-term DNF. (C) 2001 Elsevier Science.