Transcription
今天最后一位是我们来自Udub的团队，由Nice指导。今天我将讨论线性与核匪徒中的重度噪声。这是一项近期工作，与来自N US的Kevin和John合作。基本上，在嘈杂的环境中，通常的假设是奖励或数据是有界的，或者具有次高斯行为，但这真的是我们在真实世界数据中看到的吗？似乎并非如此，有很多例子，比如金融市场的回报，或者计算机网络中数据包的延迟，或者其他事物，我们看到的是超高斯，甚至是所谓的重尾噪声，其在期望值周围的尾部衰减不是指数级的，而是多项式的，或者比指数级慢。所以我们希望能够提供能够处理这种重尾噪声的机器学习算法。我们所做的假设是一个最小的假设，即这种噪声具有1加epsilon有界矩。所以它甚至可以有无限方差。
作为开始的例子，我们来看多臂匪徒，我们有n个臂，期望奖励为mu1到mun，但我们观察到的是mui加上噪声eta，其中eta可以是重尾的。那么，像UCB这样的常用算法是如何做的呢？它做的是经验均值加上置信度界。这里的问题是，当噪声是重尾的时，这个置信度界会变得更大，并且次优。特别是对于这里的经验均值，我们发现它以delta的多项式形式缩放，而我们希望，如果它是次高斯的话，我们会有这种很好的界限，它会以delta的对数形式缩放。所以我们想做的是改变这种估计方式，以便这些算法能够工作。正如我所说，经验均值不是最优的。
所以，对于稳健的均值估计器，这实际上是一个非常丰富且活跃的统计学领域。有许多不同的均值估计器。一个简单的东西是截断均值。它表示，如果数据在经验上离均值太远，我们就将其丢弃，然后计算那里的经验均值。这会产生一个人为的界限方差。另一个想法是均值中位数，我猜你们很多人都熟悉。还有更多更复杂的估计器。它们都表明，当我们对重尾噪声有一个有界的一加epsilon矩时，置信度界会像这样缩放，其中之前我们有根号t在分母中，现在我们有t的epsilon除以1加epsilon。
所以，回到我们正在研究的线性匪徒问题，我们有的是一个RD的子集，而不是离散的臂，期望奖励是未知的参数theta星，我们再次遇到这种重尾噪声。这里的问题是，将这种均值紧致的均值估计器扩展到RD实际上并非易事，而且具有挑战性。许多其他工作也尝试过这样做，但例如对于Huber损失回归，或者仅仅是将均值中位数泛化到RD，问题在于它实际上不是最优的，它以d的形式缩放，但维度依赖性不是最优的，因为我们假设如果我们为数据数量的缩放付出更多，我们至少希望维度依赖性能好一些。问题是是否真的可以做到这一点，我们回答是的，这是可能的。
所以，想法是，让我们使用这种均值紧致的均值估计器，通过单独估计每个臂在其自身方向上的值，然后在最后进行拼接。所以基本上是这样一个流程，首先我们将数据转换为随机变量，估计每个xi的a转置theta星，然后使用稳健的均值估计器计算每个臂的a的hat，然后通过寻找最小距离theta来最终确定我们的估计。这部分基本上可以看作是一次性的最小二乘法，基本上用一个数据点。我们表明，这可以这样缩放，数据数量的依赖性与之前相同，但重要的是这里的参数是MSAR，我稍后会讲到，它取决于动作集的几何形状以及一加epsilon噪声发生的情况，那里有一个负号在表达式中。
>> 在这里。>> 是的。>> 哦，不，这是逆。基本上。>> 是的。A是期望的AA转置。>> 是的。>> 所以，是的。>> 我明白了，但我以为你在做某种回归。>> 所以你取a转置之间的差值。>> 是的。好的。>> 是的，基本上，所以，是的，这就是它所做的，然后，是的，回到这个M星实际上是什么，是的，这里我假设数据来自一个分布，当我们做匪徒时，我们可以控制这个分布。所以基本上我们想最小化这里的MSAR，因为它是唯一依赖于分布的项。所以，是的，这就是MSAR，它有点违反直觉，它实际上意味着什么，但是为了让它更熟悉，如果epsilon等于1，也就是有限方差的情况，那么它就变成了协方差矩阵的范数，对于那些熟悉实验设计的人来说，这相当于找到一个G最优设计。但是对于小于1的epsilon，它变得更有趣，因为我将要讲到的，对于某些几何形状，我们看到了加速，并且从几何角度来思考，对于epsilon为1，我们试图找到一个最小体积的包围椭球来计算数据集，但对于小于1的epsilon，它变成了一个最小体积的超椭球。其中，是的，一个LP加epsilon球的alpha变换。
所以，最后，我们所做的是，我们将这个估计器与这个实验设计结合起来，使用分阶段消除法，它增加了指数级的误差阈值。我们从这个lambda设计中采样，然后消除次优臂。我们表明，在minimax terms中，遗憾的缩放是这样的，如果epsilon小于1，那么我们改进了d的依赖性界限。是的，正如我所说，有趣的是，因为MSAR是动作依赖的，我们在某些几何形状中看到了加速，例如LP范数，如果p小于1加epsilon。这也扩展到核匪徒，其中维度是无限的。基本上，在算法设计中，我们不关心维度。只有MSAR很重要，我们表明对于许多核，例如许多参数，我们表明存在亚线性遗憾，而以前我们不知道它是否存在。
是的，是的，所以总而言之，我今天想谈的是，重尾奖励从根本上改变了问题的结构，如果你不通过不同的估计器和不同的设计来考虑它，那么你处理它的方式就是次优的。即使是对于开始时的数据也是如此，例如，有一项工作表明，即使你开始时的数据不是重尾的，并且你进行了随机梯度下降，你最终也可能得到一个重尾分布。是的，这里还有一些开放问题，我的意思是还有很多开放问题。在线性情况下的问题仍然存在，我们展示的d依赖性2epsilon除以1加epsilon的下界对于L2范数来说仍然存在差距，但正如你所见，这两个之间仍然存在差距，我们不确定哪个是紧的。是的，还有一个问题是，对于每种几何形状，实际的MSAR是什么？我们展示了一些几何形状的加速，但仍然存在一个问题，哪些几何形状实际上提供了加速，哪些没有。是的，作为一个在正常随机设置中的点，几何形状无关紧要，因为Kish和Wolffits。是的，这在尾部情况下很有趣。在可实现的情况下，通常的假设是我们至少可以访问最小二乘Oracle，但在这里，在重尾情况下，数据假设可能需要从根本上改变，因为例如，访问一个1加epsilon的最小化器而不是一个最小二乘Oracle。
是的，谢谢。[掌声]
>> 嗯，所以当你谈论最优设计标准时，对吧，你有这个1加epsilon指数。>> 是的。>> 你怎么计算它？所以如果指数是2，我们有像Frank-Wolfe风格的算法，对吧？你有任何这样的算法吗？>> 所以这是，所以是的，这实际上是凸的，因为epsilon在0和1之间，但是，是的，基本上你应该，这总是小于这个范数。所以最坏的情况，我们实际上使用的是，我们可以使用Frank-Wolfe，并使用一个G最优设计，然后我们得到最坏的情况，但在特定几何形状的情况下，我们可以只使用梯度，然后找到一个好的解决方案。好的。>> 哦，等等，我可以问个问题吗？>> 是的。>> 等等。所以，我想回到最开始。所以，比如这里最天真的算法，我想是使用某种稳健的均值估计器，然后在这个东西上做类似UCB的东西。>> 是的。是的。>> 这个算法有下界吗？比如我们知道这种方法不能达到你正在获得的速率吗？哦，这里>> 哪个>> 比如你最后获得的速率。>> 是的。用你的算法，我们知道这种方法是否会封顶，它无法获得相同的速率？>> 哦>> 如果你要做自然的分析，是的，是的，我不太确定分析是否松散，但那些类型的算法都会依赖。>> 是的。是的。我只是好奇一个算法特定的，它表明对于那些算法来说它是紧的，或者类似的东西。哦，不，不，我没见过。但是，是的，就是这样。>> 好的。>> 所以，我们现在感谢所有演讲者，然后去参加一个海报会议。[掌声]