The Computational Intractability of Machine Learning Tasks

本研究涉及到理解计算复杂性的基本机器学习问题。特别是，研究者们研究了哪些经典的学习问题不太可能有有效的解决方案。就更广泛的影响而言，这一系列研究有助于从业者和算法设计者，因为它概述了创建强大学习系统的基本障碍。例如，我们能否减少密码学中的困难开放问题(例如：（例如，分解）和复杂性理论（例如，np完全语言）在机器学习中的某些问题？如果是这样，这就提供了强有力的证据，证明特定的机器学习问题是无可救药地难以解决的。另一个研究途径是证明在有限学习模型中推断函数所需资源的无条件允许边界。这项研究的智力价值在于在密码学和复杂性理论（特别是通信复杂性）的问题与学习理论的问题之间找到新的简化。例如，PI研究了基于格的密码学在机器学习中的影响，并研究了其对DNF学习问题的影响。此外，PI研究了通信复杂性的使用，以排除通过任意特征的小集合学习简单概念类的可能性。我们进一步描述了傅里叶分析在证明众所周知的统计查询学习模型的下界中的作用。最后，本文探讨了np完备性与电路复杂度在适当学习和特定分布查询学习的一般问题上的关系。

This research involves understanding the computational complexity offundamental machine learning problems. In particular, theinvestigators study which classic learning problems are unlikely toadmit efficient solutions. In terms of broader impact, this line ofresearch aids practitioners and algorithm designers as it outlinesfundamental stumbling blocks for creating powerful learning systems.For example, can we reduce difficult open problems from cryptography(e.g., factoring) and complexity theory (e.g., NP-complete languages)to certain problems in machine learning? If so, this provides strongevidence that particular machine learning problems are hopelesslyintractable. Another avenue of research is to prove unconditionallower bounds on the resources required to infer functions inrestricted learning models.The intellectual merit of the research lies in finding new reductionsbetween problems in cryptography and complexity theory-- in particularcommunication complexity-- and problems from learning theory. Forexample, the PI studies the impact of lattice-based cryptography inmachine learning and examines its implications for the DNF learningproblem. Additionally, the PI researches the use of communicationcomplexity to rule out learning simple concept classes via small setsof arbitrary features. We further delineate the role of Fourieranalysis in proving lower bounds in the well known model ofStatistical Query learning. Finally, this research investigates therelationships between NP-completeness and circuit complexity togeneral questions about proper learning and distribution-specificquery learning.