Toward Attribute Efficient Learning of Decision Lists and Parities

Adam R. Klivans; Rocco A. Servedio

Toward Attribute Efficient Learning of Decision Lists and Parities

Adam R. Klivans, Rocco A. Servedio; 7(20):587−602, 2006.

Abstract

We consider two well-studied problems regarding attribute efficient learning: learning decision lists and learning parity functions. First, we give an algorithm for learning decision lists of length k over n variables using 2^{Õ(k^1/3)} log n examples and time n^{Õ(k^1/3)}. This is the first algorithm for learning decision lists that has both subexponential sample complexity and subexponential running time in the relevant parameters. Our approach is based on a new construction of low degree, low weight polynomial threshold functions for decision lists. For a wide range of parameters our construction matches a lower bound due to Beigel for decision lists and gives an essentially optimal tradeoff between polynomial threshold function degree and weight.

Second, we give an algorithm for learning an unknown parity function on k out of n variables using O(n^1-1/k) examples in poly(n) time. For k=o(log n) this yields the first polynomial time algorithm for learning parity on a superconstant number of variables with sublinear sample complexity. We also give a simple algorithm for learning an unknown length-k parity using O(k log n) examples in n^k/2 time, which improves on the naive n^k time bound of exhaustive search.