Learning theory studies the extent to which meaningful patterns can be extracted from data. Two popular frameworks for the analysis of learning algorithms are statistical learning and worst-case online learning. Recent developments suggest that these two seemingly disparate frameworks are, in fact, two endpoints of a spectrum of problems which can be studied in a unified manner. The goals of this project are (a) to understand learnability and to develop efficient algorithms for a spectrum of problems corresponding to various probabilistic and non-probabilistic assumptions on the data; (b) to extend learnability results to encompass performance criteria beyond the classical notion of regret; (c) to understand the inherent complexity of reinforcement learning and to develop novel algorithms inspired by the learnability analysis; (d) to study learnability in settings with imperfect or partial information, and to understand algorithmic implications of dealing with uncertainty.
Algorithms that extract patterns from data are becoming increasingly important in the information age. However, classical methods that assume a "static" nature of the world are unable to capture the evolving character of data. Recent advances in learning theory have been on the dynamic interaction between the world and the learner. Being able to tailor the algorithms to particular assumptions on data is arguably a central goal of learning theory. The intellectual merit of this proposal includes the development of a unified theoretical framework, increasing our understanding of what is learnable by computers. Advances in this direction will likely facilitate the development of more intelligent systems, having a positive impact on technology. The interdisciplinary nature of the project will likely increase collaboration between Computer Science and Statistics.
