The Computational Intractability of 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.