We study the problem of oracle-efficient hybrid online learning when the
features are generated by an unknown i.i.d. process and the labels are
generated adversarially. Assuming access to an (offline) ERM oracle, we show
that there exists a computationally efficient online predictor that achieves a
regret upper bounded by $\tilde{O}(T^{\frac{3}{4}})$ for a finite-VC class, and
upper bounded by $\tilde{O}(T^{\frac{p+1}{p+2}})$ for a class with $\alpha$
fat-shattering dimension $\alpha^{-p}$. This provides the first known
oracle-efficient sublinear regret bounds for hybrid online learning with an
unknown feature generation process. In particular, it confirms a conjecture of
Lazaric and Munos (JCSS 2012). We then extend our result to the scenario of
shifting distributions with $K$ changes, yielding a regret of order
$\tilde{O}(T^{\frac{4}{5}}K^{\frac{1}{5}})$. Finally, we establish a regret of
$\tilde{O}((K^{\frac{2}{3}}(\log|\mathcal{H}|)^{\frac{1}{3}}+K)\cdot
T^{\frac{4}{5}})$ for the contextual $K$-armed bandits with a finite policy set
$\mathcal{H}$, i.i.d. generated contexts from an unknown distribution, and
adversarially generated costs.

我们提出了一种适用于未知特征生成过程的混合在线学习的、高效的预测方法，证明了该方法可在有限的 VC 类中实现具有次线性的遗憾上限，并在具有 α fat-shattering 维度的类中实现具有次线性的遗憾上限。此外，我们拓展了我们的结果到具有 K 个变化的分布转移场景，并为具有有限策略集合 H 和未知分布的 i.i.d. 生成的上下文以及敌对生成的成本的情境 K 臂赌博机建立了遗憾上限。

未知分布的高效混合在线学习

Oracle-Efficient Hybrid Online Learning with Unknown Distribution

Out-of-distribution (OOD) detection is crucial to modern deep learning
applications by identifying and alerting about the OOD samples that should not
be tested or used for making predictions. Current OOD detection methods have
made significant progress when in-distribution (ID) and OOD samples are drawn
from static distributions. However, this can be unrealistic when applied to
real-world systems which often undergo continuous variations and shifts in ID
and OOD distributions over time. Therefore, for an effective application in
real-world systems, the development of OOD detection methods that can adapt to
these dynamic and evolving distributions is essential. In this paper, we
propose a novel and more realistic setting called continuously adaptive
out-of-distribution (CAOOD) detection which targets on developing an OOD
detection model that enables dynamic and quick adaptation to a new arriving
distribution, with insufficient ID samples during deployment time. To address
CAOOD, we develop meta OOD learning (MOL) by designing a learning-to-adapt
diagram such that a good initialized OOD detection model is learned during the
training process. In the testing process, MOL ensures OOD detection performance
over shifting distributions by quickly adapting to new distributions with a few
adaptations. Extensive experiments on several OOD benchmarks endorse the
effectiveness of our method in preserving both ID classification accuracy and
OOD detection performance on continuously shifting distributions.

我们提出了一种新颖且更现实的设置，称为连续自适应离群分布检测（CAOOD），旨在开发一种能够适应动态和迅速适应新到达分布的离群分布检测模型，并且在部署期间具有不足的 ID 样本。通过设计学习和适应图表，我们开发了元离群学习（MOL），在训练过程中学习到了一个良好初始化的离群分布检测模型。在测试过程中，MOL 通过少量适应快速调整到新的分布，从而确保在不断变化的分布上具有离群分布检测性能。对几个离群分布基准测试的广泛实验证明了我们方法在保持 ID 分类准确性和离群分布检测性能方面的有效性。