CAREER: The Computational Complexity of Halfspace-Based Learning

University Of Texas At Austin, Austin TX

Investigators

Abstract

Algorithms for learning to classify data have important applications in almost every area of computer science including data mining, computer vision, compiler design, operating system design, speech recognition, computational biology, computational game theory, computational neuroscience, and traditional algorithm design. A common, simplifying assumption in learning theory is that labeled data can be classified by a halfspace in many dimensions. The intellectual merit of this research involves understanding the computational complexity of fundamental halfspace-based learning tasks. The investigators focus on the following three challenges: 1) develop algorithms for learning a halfspace in the presence of noise; 2) efficiently learn intersections of halfspaces; 3) prove hardness results for learning various halfspace-based concept classes. In terms of broader impact, as alluded to above, this research gives new tools for practitioners in a variety of fields including computational biology, economics, and statistics. The research relies heavily on new techniques from approximation theory and harmonic analysis to give provably efficient algorithms for learning halfspaces (also known as linear threshold functions) in malicious noise models with respect to many natural distributions. A recent polynomial-regression algorithm due to the principal investigator and his colleagues for agnostically learning halfspaces generalizes previous work in Fourier-based learning. The investigators study other applications of these techniques to discover new algorithms for learning intersections of halfspaces and, more generally, arbitrary convex sets with respect to natural distributions. In addition, the investigator applies properties of new lattice-based cryptosystems to show the intractability of learning intersections of halfspaces in distribution-free models.