Online Learning: Stochastic, Constrained, and Smoothed Adversaries
Online Learning: Stochastic, Constrained, and Smoothed Adversaries
复制标题
在线学习：随机、受限和平滑的对手
DOI：
--
复制
发表时间：
2011
期刊：
影响因子：
--
通讯作者：
Ambuj Tewari
中科院分区：
文献类型：
--
作者：
A. Rakhlin;Karthik Sridharan;Ambuj Tewari
学习理论主要集中在两个主要的学习场景：经典的统计设置，其中实例是独立同分布的。来自固定分布，以及对抗性场景，其中在每个时间步，都会向玩家展示一个对抗性选择的实例。可以说，在现实世界中，这些假设都不合理。我们定义了对手的移动受到限制的游戏的极小极大值，捕获数据的随机和非随机假设。基于顺序对称化方法，我们定义了分布相关的 Rademacher 复杂度的概念，适用于从独立同分布到独立同分布的一系列问题。到最坏的情况。这些界限让我们立即推断出变异类型的界限。我们研究了一个平滑的在线学习场景，结果表明，指数级的少量噪声可以使具有无限 Littlestone 维度的函数类变得可学习。
Learning theory has largely focused on two main learning scenarios: the classical statistical setting where instances are drawn i.i.d. from a fixed distribution, and the adversarial scenario wherein, at every time step, an adversarially chosen instance is revealed to the player. It can be argued that in the real world neither of these assumptions is reasonable. We define the minimax value of a game where the adversary is restricted in his moves, capturing stochastic and non-stochastic assumptions on data. Building on the sequential symmetrization approach, we define a notion of distribution-dependent Rademacher complexity for the spectrum of problems ranging from i.i.d. to worst-case. The bounds let us immediately deduce variation-type bounds. We study a smoothed online learning scenario and show that exponentially small amount of noise can make function classes with infinite Littlestone dimension learnable.