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

AF：小：从统计到最坏情况学习：统一框架

• 批准号: 1116928
• 负责人: Alexander Rakhlin
• 金额: $ 49.11万
• 依托单位: University of Pennsylvania
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2011
• 资助国家: 美国
• 起止时间: 2011-07-01 至 2016-06-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1116928&HistoricalAwards=false
• 关键词: AF; Small; Statistical; Worst; Case

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.

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