Oracle-Efficient Online Learning for Beyond Worst-Case Adversaries

Abstract

In this paper, we study oracle-efficient algorithms for beyond worst-case analysis of online learning. We focus on two settings. First, the smoothed analysis setting of [RST11,HRS22] where an adversary is constrained to generating samples from distributions whose density is upper bounded by 1/ times the uniform density. Second, the setting of K-hint transductive learning, where the learner is given access to K hints per time step that are guaranteed to include the true instance. We give the first known oracle-efficient algorithms for both settings that depend only on the pseudo (or VC) dimension of the class and parameters and K that capture the power of the adversary. In particular, we achieve oracle-efficient regret bounds of O ( T d^-1 ) and O ( T dK ) for learning real-valued functions and O ( T d^-12 ) for learning binary-valued functions. For the smoothed analysis setting, our results give the first oracle-efficient algorithm for online learning with smoothed adversaries [HRS22]. This contrasts the computational separation between online learning with worst-case adversaries and offline learning established by [HK16]. Our algorithms also achieve improved bounds for worst-case setting with small domains. In particular, we give an oracle-efficient algorithm with regret of O ( T(d |X|)^1/2 ), which is a refinement of the earlier O ( T|X|) bound by [DS16].

Tasks

Reproductions