AF: Small: Learnability, Randomness, and Lower Bounds

这个项目的动机是计算复杂性理论和机器学习理论研究领域之间的新联系。计算复杂性理论旨在通过确定解决问题所需的计算资源(如CPU时间、内存空间或电路面积)来了解哪些问题可以在计算机上有效地解决。这个领域的中心是著名的P与NP问题，鉴于已发现的数千个不同的NP完全问题，该问题几乎影响到每一个科学和工程学科。机器学习理论研究计算机从数据中学习的程度，以及它们根据已学到的知识做出未来预测和分类的能力。已经发现了一些强大的学习算法，但计算机能否被编程来完成许多学习任务仍然是一个悬而未决的问题。计算复杂性和机器学习都旨在了解计算的能力和局限性，但这两个领域研究的问题类型不同，使用的技术也不同。这项研究将使用这两个领域中每一个领域的技术和想法来影响另一个领域，具体地说，目的是证明结果的“下限”。这项研究将利用算法随机性提供的一个新的优势来将复杂性和学习问题联系起来。学习算法将被用来为解决计算复杂性问题所需的计算资源建立下限。相反的方向将被研究，以应用技术和思想从计算复杂性，以表明“属性有效的”学习算法不存在于某些概念类。算法的随机性和Kolmogorov复杂性将被用来提高我们对学习算法的能力和局限性的理解，这项研究将提高我们对计算复杂性的理解，这对许多计算发挥作用的科学和工程领域具有参考价值。这个项目旨在更好地了解计算机可以高效地完成哪些学习任务，这对人工智能的基础有应用。特别是，这项研究将确定必须克服的新障碍，以便设计成功的自动学习系统。计算复杂性理论和机器学习理论之间将产生更大的协同效应，为未来在这些领域的合作和跨学科工作奠定基础。

This project is motivated by new connections between the research fields of computational complexity theory and machine learning theory. Computational complexity theory aims to understand which problems can be solved efficiently on a computer by determining the amounts of computational resources such as CPU time, memory space, or circuit area that are required to solve problems. At the center of this field is the famous P vs. NP question which impacts virtually every scientific and engineering discipline, given the thousands of diverse NP-complete problems that have been discovered. Machine learning theory studies the extent to which computers can learn from data and their ability to make future predictions and classifications based on what has been learned. Some powerful learning algorithms have been discovered, but whether computers can be programmed to accomplish many learning tasks remains an open question.Both computational complexity and machine learning aim to understand the capabilities and limitations of computation, but the two fields study different types of problems and use different kinds of techniques. This research will employ techniques and ideas from each of these two fields to impact the other field, specifically with the goal of proving "lower bound" results. This research will be accomplished by making use of a new vantage point provided by algorithmic randomness to relate complexity and learning problems. Learning algorithms will be utilized to establish lower bounds on the computational resources required to solve problems in computational complexity. The converse direction will be investigated to apply techniques and ideas from computational complexity to show that "attribute-efficient" learning algorithms do not exist for certain concept classes. Algorithmic randomness and Kolmogorov complexity will be used to improve our understanding of the capabilities and limitations of learning algorithms.This research will improve our understanding of computational complexity, which is informative to many areas of science and engineering where computation plays a role. This project aims to better understand what learning tasks can be accomplished efficiently by computers, which has applications to the foundations of artificial intelligence. In particular, this research will identify new obstacles that must be overcome in order to design successful automatic learning systems. A greater synergy will be developed between computational complexity theory and machine learning theory, with the benefit of laying a foundation for future collaboration and interdisciplinary work across these fields.