AF: Small: From Statistical to Worst-Case Learning: A Unified Framework

学习理论研究从数据中提取有意义模式的程度。两种流行的学习算法分析框架是统计学习和最坏情况在线学习。最近的事态发展表明，这两个看似不同的框架，实际上是一系列问题的两个端点，可以以统一的方式进行研究。该项目的目标是：（a）了解可学习性，并为与数据上的各种概率和非概率假设相对应的一系列问题开发有效算法;（B）扩展可学习性结果，以涵盖经典遗憾概念之外的性能标准;（c）了解强化学习的内在复杂性，并开发受可学习性分析启发的新算法;（d）研究在不完全或部分信息的情况下的可学习性，并了解处理不确定性的算法所涉问题，从数据中提取模式的算法在信息时代变得越来越重要。然而，传统的方法，假设一个“静态”的性质的世界是无法捕捉不断变化的字符的数据。学习理论的最新进展是关于世界与学习者之间的动态互动。能够根据数据的特定假设定制算法可以说是学习理论的核心目标。这一建议的智力价值包括发展一个统一的理论框架，增加我们对计算机可学习内容的理解。这一方向的进展可能会促进更智能系统的开发，对技术产生积极影响。该项目的跨学科性质可能会增加计算机科学和统计学之间的合作。

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.