The broad goal of this line of research is to give a principled answer to the question, "What sort of data is efficiently learnable, and by what algorithms?" The current state-of-the-art in machine learning is that there is an overwhelming number of possible algorithms that can be tried on a new machine learning problem, with no clear understanding of which techniques can be expected to work on which problems. Further, it is often the case that machine learning algorithms that work well "in theory" do not perform as well "in practice," and vice versa. The PIs have outlined a plan for resolving these difficulties, finding a unification of disparate methods via the Polynomial Method, and investigating how efficient this method can be. On a more immediate level the PIs will aim for broad impact through advising and guiding graduate students and widely disseminating research results.
Specifically, the PIs will investigate the effectiveness of the "Polynomial Method" in machine learning theory. The PIs observe that nearly all learning algorithms, in theory and in practice, can be viewed as fitting a low-degree polynomial to data. The PIs plan to systematically develop this Polynomial Method of learning by working on the following three strands of research:
1. Understand the extent to which low-degree polynomials can fit different natural types of target functions, under various data distributions and noise rates. This research involves novel methods from approximation theory and analysis.
2. Develop new algorithmic methods for finding well-fitting polynomials when they exist. Here the PIs will work to adapt results in geometry and probability for the purposes of identifying and eliminating irrelevant data.
3. Delimit the effectiveness of the Polynomial Method. The PIs will show new results on the computational intractability of learning intersections of linear separators, and on learning linear separators with noise.
