In this work we revisit two classic high-dimensional online learning problems, namely regression and linear contextual bandits, from the perspective of adversarial robustness. Existing works in algorithmic robust statistics make strong distributional assumptions that ensure that the input data is evenly spread out or comes from a nice generative model. Is it possible to achieve strong robustness guarantees even without distributional assumptions altogether, where the sequence of tasks we are asked to solve is adaptively and adversarially chosen? We answer this question in the affirmative for both regression and linear contextual bandits. In fact our algorithms succeed where convex surrogates fail in the sense that we show strong lower bounds categorically for the existing approaches. Our approach is based on a novel way to use the sum-of-squares hierarchy in online learning and in the absence of distributional assumptions. Moreover we give extensions of our main results to infinite dimensional settings where the feature vectors are represented implicitly via a kernel map.

本文从对抗鲁棒性的角度重新审视了两个经典的高维在线学习问题，即线性回归和情境地图，并探究了无需假设数据分布，直接从全局角度保证它们对抗鲁棒的可行性。具体方法是通过交替最小化策略将普通最小二乘法嵌入到简单的凸约束计算不完整数据下的最优加权分布，并证明该方法在污染程度方面具有最佳的可重复性和完整性。

在线和分布自由鲁棒性: 带Huber污染的回归和上下文臂