TY - JOUR
T1 - On PAC learning algorithms for rich Boolean function classes
AU - Hellerstein, Lisa
AU - Servedio, Rocco A.
N1 - Funding Information:
We thank Adam Klivans for helpful suggestions in preparing this survey, and we thank an anonymous referee for useful suggestions regarding the presentation. The first author was supported in part by NSF Award IIS-0534908, while visiting the University of Wisconsin, Madison. The second author was supported in part by NSF CAREER award CCF-0347282, by NSF award CCF-0523664 and by a Sloan Foundation Fellowship.
PY - 2007/9/24
Y1 - 2007/9/24
N2 - We give an overview of the fastest known algorithms for learning various expressive classes of Boolean functions in the Probably Approximately Correct (PAC) learning model. In addition to surveying previously known results, we use existing techniques to give the first known subexponential-time algorithms for PAC learning two natural and expressive classes of Boolean functions: sparse polynomial threshold functions over the Boolean cube {0, 1}n and sparse GF2 polynomials over {0, 1}n.
AB - We give an overview of the fastest known algorithms for learning various expressive classes of Boolean functions in the Probably Approximately Correct (PAC) learning model. In addition to surveying previously known results, we use existing techniques to give the first known subexponential-time algorithms for PAC learning two natural and expressive classes of Boolean functions: sparse polynomial threshold functions over the Boolean cube {0, 1}n and sparse GF2 polynomials over {0, 1}n.
KW - Computational learning theory
KW - PAC learning
KW - Polynomial threshold function
UR - http://www.scopus.com/inward/record.url?scp=34548203510&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=34548203510&partnerID=8YFLogxK
U2 - 10.1016/j.tcs.2007.05.018
DO - 10.1016/j.tcs.2007.05.018
M3 - Article
AN - SCOPUS:34548203510
SN - 0304-3975
VL - 384
SP - 66
EP - 76
JO - Theoretical Computer Science
JF - Theoretical Computer Science
IS - 1
ER -