Adaptive Oracle-Efficient Online Learning
Adaptive Oracle-Efficient Online Learning
复制标题
DOI：
10.48550/arxiv.2210.09385
复制
发表时间：
2022-10
期刊：
影响因子：
--
通讯作者：
Guanghui Wang;Zihao Hu;Vidya Muthukumar;Jacob D. Abernethy
中科院分区：
文献类型：
--
作者：
Guanghui Wang;Zihao Hu;Vidya Muthukumar;Jacob D. Abernethy
经典的在线学习和决策算法具有实现最佳性能保证的优点，但在大规模实现时受到计算复杂性的限制。最近更复杂的技术，我们称之为oracle-efficient方法，通过调度一个离线优化oracle来解决这个问题，这个离线优化oracle可以搜索一个指数级（甚至无限）的决策空间，并选择在任何数据集上执行最好的决策。但是，尽管具有计算可行性的好处，但oracle-efficient算法有一个主要的限制：虽然在最坏情况下表现良好，但它们不能很好地适应友好的环境。在本文中，我们考虑了两个这样友好的场景，(a)“小损失”问题和(b) IID数据。我们提供了一个新的框架，用于设计在我们称之为近似性（在精神上与Dud\ {i}k等人，[2020]提供的充分条件相关）的特定条件下，具有oracle-efficient并且能够很好地适应小损失环境的follow-the- perturd -leader算法。我们确定了一系列现实世界的设置，包括在线拍卖和转导在线分类，其近似性成立。我们还将该算法扩展到IID数据设置，并在oracle-efficient设置中建立“两全其美”的边界。
The classical algorithms for online learning and decision-making have the benefit of achieving the optimal performance guarantees, but suffer from computational complexity limitations when implemented at scale. More recent sophisticated techniques, which we refer to as oracle-efficient methods, address this problem by dispatching to an offline optimization oracle that can search through an exponentially-large (or even infinite) space of decisions and select that which performed the best on any dataset. But despite the benefits of computational feasibility, oracle-efficient algorithms exhibit one major limitation: while performing well in worst-case settings, they do not adapt well to friendly environments. In this paper we consider two such friendly scenarios, (a)"small-loss"problems and (b) IID data. We provide a new framework for designing follow-the-perturbed-leader algorithms that are oracle-efficient and adapt well to the small-loss environment, under a particular condition which we call approximability (which is spiritually related to sufficient conditions provided by Dud\'{i}k et al., [2020]). We identify a series of real-world settings, including online auctions and transductive online classification, for which approximability holds. We also extend the algorithm to an IID data setting and establish a"best-of-both-worlds"bound in the oracle-efficient setting.