CAREER: Efficient Learning Algorithms for Rich Function Classes

Columbia University, New York NY

Investigators

Abstract

Systems which learn from data are by now widely used in many areas, and such systems will doubtless be even more ubiquitous in the future. As learning-based systems proliferate and are applied to larger and larger domains, the need for provably effective and efficient learning algorithms grows correspondingly more acute. The object of the proposed research is to design and analyze such algorithms. More specifically, building on the PI's previous work in this area, the two main research goals of this career development proposal are: 1. To develop algorithms which can efficiently learn rich and important classes of Boolean functions in well-studied models of computational learning. Major focuses of this work will be (a) learning Disjunctive Normal Form (DNF) formulas, which are a standard form of knowledge representation; (b) learning various classes of Boolean circuits, which can be substantially more expressive than DNF formulas; and (c) learning in the presence of irrelevant information, i.e. learning functions which depend only on a small unknown subset of domain attributes. We note that previous work in this area has uncovered many interesting and useful connections between these learning problems and complexity-theoretic structural questions about Boolean functions. An important aspect of this research (and indeed a key component of our methodology) is to continue to explore and exploit these connections between learning and complexity. 2. To develop and analyze other well-motivated models for computational learning, and to develop efficient learning algorithms for Boolean function classes in these models. Anticipated research directions here include (a) giving efficient average-case learning algorithms for important concept classes for which no efficient worst-case algorithms are known; (b) developing a theory of learning from nonmalicious random examples; and (c) studying the role of quantum computation in learning theory. Each of these directions has the potential to yield positive learning results which go beyond what can be achieved in current standard learning models. This research plan is closely integrated with a plan to achieve broader impact through education which involves students at all levels. Highlights of the education plan include: (a) developing new computational learning theory courses and other theory courses at Columbia University for target audiences ranging from undergraduates to advanced graduate students; (b) introducing undergraduates to the excitement of research by actively engaging them in research, both in undergraduate courses and in extracurricular projects; (c) advising and guiding graduate students in their development as researchers and educators; and (d) building a strong theory group at Columbia by maintaining regular theory group meetings and organizing events such as Theory Day.