Divsion of Engineering and Applied Sciences

Title: Divsion of Engineering and Applied Sciences

Research Question: How can we develop efficient algorithms for learning decision lists and parity functions on a superconstant number of variables with sublinear sample complexity?

Methodology: The researchers proposed two main approaches. First, they presented an algorithm for learning decision lists of length k using 2˜O(k1/3)logn examples and time n˜O(k1/3). This algorithm establishes a relationship between attribute-efficient learning and polynomial threshold functions and is based on a new construction of low-degree, low-weight polynomial threshold functions for decision lists.

Second, they provided an algorithm for learning an unknown parity function on k out of n variables using O(n1−1/k) examples in time polynomial in n. For k = o(logn), this yields a polynomial time algorithm with sample complexity o(n) for learning parity on a superconstant number of variables.

Results: The results show that the proposed algorithms can learn decision lists and parity functions with subexponential sample complexity and subexponential running time in the relevant parameters. The algorithms also establish a 1994 lower bound due to Beigel for the ODDMAXBIT predicate and give an essentially optimal trade-off between polynomial threshold function degree and weight.

Implications: These findings have significant implications for machine learning research. The algorithms can be applied to a wide range of learning problems, especially those characterized by an abundance of irrelevant information. The research also contributes to the ongoing debate on attribute-efficient learning and provides insights into the learnability of decision lists and parity functions.

In summary, this research presents efficient algorithms for learning decision lists and parity functions on a superconstant number of variables with sublinear sample complexity. The methods establish important relationships between attribute-efficient learning and polynomial threshold functions and provide an optimal trade-off between polynomial threshold function degree and weight.

Link to Article: https://arxiv.org/abs/0311042v1 Authors: arXiv ID: 0311042v1