Timezone: »

 
Poster
Adaptive Oracle-Efficient Online Learning
Guanghui Wang · Zihao Hu · Vidya Muthukumar · Jacob Abernethy

Wed Nov 30 02:00 PM -- 04:00 PM (PST) @ Hall J #533
in Poster Session 4 »
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 $\textit{oracle-efficient}$ methods, address this problem by dispatching to an $\textit{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, most 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 $\textit{approximability}$ (which is spiritually related to sufficient conditions provided in (Dudí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.
Keywords: Online Learning · small-loss bound · oracle efficiency · adaptive online learning

Author Information

Guanghui Wang (Georgia Institute of Technology)
Zihao Hu (Georgia Institute of Technology)
Vidya Muthukumar (Georgia Institute of Technology)
Jacob Abernethy (Georgia Institute of Technology)

More from the Same Authors