RUI: Fourier Analysis of Learning Problems and Function Classes

Duquesne University, Pittsburgh PA

Investigators

Abstract

The general area within which this research is performed is known as computational learning theory. The starting point for research in this area is typically the definition of mathematical models of what the term ``learning'' may mean in a variety of settings. The concept of learning captured by these models is then formally analyzed, frequently leading to algorithms for solving learning problems within the models as well as to proofs that certain problems cannot be solved. These learning-theoretic models and results lend support to more applied work in machine learning, which in turn has demonstrated utility in applications ranging from e-commerce to advanced research on vehicles that drive themselves. This project adds to the existing body of learning-theoretic knowledge in a number of ways, including analysis of a relatively new model called Probably Exactly Correct learning, development of an algorithm that learns arguably the broadest class of functions yet shown to be learnable (majority of AC0 functions), and work toward extending hardness results for learnability of a fundamental class, the class of parity functions. The key tool used in these and other project tasks is Fourier analysis of classes of functions. While the primary purpose of the Fourier analysis is to support research into learning questions, a side benefit is the enhancement of our understanding of several interesting classes of functions, such as majority of AC0. Furthermore, this project provides a stimulating research experience to undergraduate and master's students at a university that, from an NSF perspective, is largely an undergraduate institution.