CAREER: The Computational Complexity of Halfspace-Based Learning

用于学习分类数据的算法在计算机科学的几乎每个领域都有重要的应用，包括数据挖掘、计算机视觉、编译器设计、操作系统设计、语音识别、计算生物学、计算博弈论、计算神经科学和传统算法设计。 学习理论中一个常见的简化假设是，标记数据可以在许多维度上通过半空间进行分类。这项研究的智力价值包括理解基本的基于半空间的学习任务的计算复杂性。 研究人员专注于以下三个挑战：1）开发在存在噪声的情况下学习半空间的算法; 2）有效地学习半空间的交叉点; 3）证明学习各种基于半空间的概念类的困难结果。 在更广泛的影响方面，如上所述，这项研究为包括计算生物学，经济学和统计学在内的各个领域的从业者提供了新的工具。这项研究在很大程度上依赖于近似理论和调和分析的新技术，以提供可证明有效的算法来学习恶意噪声模型中的半空间（也称为线性阈值函数）。 最近的多项式回归算法，由于主要研究者和他的同事不可知学习半空间推广以前的工作傅立叶为基础的学习。 研究人员研究这些技术的其他应用，以发现学习半空间交叉点的新算法，更一般地说，关于自然分布的任意凸集。 此外，研究人员应用新的基于格的密码系统的属性，以显示在分布自由模型中学习半空间的交叉点的困难性。

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.