The Computational Intractability of Machine Learning Tasks

机器学习任务的计算难处理性

• 批准号: 0728536
• 负责人: Adam Klivans
• 金额: $ 25万
• 依托单位: University of Texas at Austin
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2007
• 资助国家: 美国
• 起止时间: 2007-09-01 至 2012-02-29
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0728536&HistoricalAwards=false
• 关键词: Computational; Intractability; Machine; Learning; Tasks

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.

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