Some of the strongest results obtained to date from the theoretical study of machine learning have used methods from discrete Fourier analysis. This project seeks both to further apply these methods to answer significant open theoretical machine learning questions and to develop practical applications of several Fourier results. Specifically, three tasks are planned. (1) Extend results obtained under the PI's prior NSF-funded project to further improve the asymptotic run time of a key component of many Fourier-base algorithms. (2) Apply Fourier techniques to several interesting open problems, particularly those concerning the practically inspired problem of learning form data corrupted by various noise processes. (3) Implement and empirically evaluate a variety of Fourier-based algorithms, including those developed as part of the first two tasks, as well as others. Applications considered include extracting rules from artificial neural networks and pruning decision trees. In addition to anticipated advancements in our knowledge about machine learning, this project will contribute substantially to the research training of one or more undergraduate students at a largely undergraduate institution.
