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.
