AF: Small: Learnability, Randomness, and Lower Bounds

该项目的动机是计算复杂性理论和机器学习理论研究领域之间的新联系。 计算复杂性理论旨在通过确定解决问题所需的计算资源（如CPU时间，内存空间或电路面积）来了解哪些问题可以在计算机上有效解决。 这个领域的中心是著名的P vs. NP问题，它几乎影响了每一个科学和工程学科，因为已经发现了数千个不同的NP完全问题。 机器学习理论研究计算机可以从数据中学习的程度，以及它们根据所学到的知识进行未来预测和分类的能力。 一些强大的学习算法已经被发现，但计算机是否可以被编程来完成许多学习任务仍然是一个悬而未决的问题。计算复杂性和机器学习都旨在了解计算的能力和局限性，但这两个领域研究不同类型的问题，并使用不同类型的技术。 这项研究将采用这两个领域的技术和思想来影响另一个领域，特别是为了证明“下限”的结果。 这项研究将通过利用算法随机性提供的一个新的Vantage位置来实现复杂性和学习问题。 学习算法将被用来建立所需的计算资源的下限，以解决计算复杂性的问题。 匡威的方向将调查应用技术和计算复杂性的想法，以表明“属性有效”的学习算法不存在某些概念类。 数学随机性和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.