Oracle-Efficient Online Learning for Smoothed Adversaries

We study the design of computationally efficient online learning algorithms under smoothed analysis. In this setting, at every step an adversary generates a sample from an adaptively chosen distribution whose density is upper bounded by 1/ times the uniform density. Given access to an offline optimization (ERM) oracle, we give the first computationally efficient online algorithms whose sublinear regret depends only on the pseudo/VC dimension d of the class and the smoothness parameter . In particular, we achieve oracle-efficient regret bounds of O( p T d 1 ) for learning real-valued functions and O( 2 ) for learning binary-valued functions. Our results establish that online learning is computationally as easy as offline learning, under the smoothed analysis framework. 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 some settings with binary-valued functions and worst-case adversaries. These include an oracle-efficient algorithm with O( p T (d|X |) 1/2 ) regret that refines the earlier O( p T |X |) bound of [DS16] for finite domains, and an oracle-efficient algorithm with O(T 3/4 d 1/2 ) regret for the transductive setting. 36th Conference on Neural Information Processing Systems (NeurIPS 2022). Method Reference Binary e O ⇣ p dT log( 1 ) ⌘ [HRS22, Thm 3.1] Real-values e O ⇣ p dT log( 1 ) ⌘ Thm F.1 Binary e O ⇣ p dT 1/2 ⌘ Thm 3.2 e O ⇣ p dT 1 ⌘ Thm 3.1 Alg-independent ⌦ ⇣ p T (d/ ) 1/2 ⌘ Thm 5.1 Algorithms 1 and 2 ⌦ ⇣ p dT 1/2 ⌘ Thm E.1 Small-domain O ⇣ p T (d|X |) 1/2 ⌘ Cor 3.3 Transductive learning O ⇣ T 3/4 d 1/4 ⌘ Cor 3.3 Regret Bound Statistical Upper Bound Prob. Coupling and ✏-Net Computational Upper Bound FTPL with Poissonization 1 oracle call per round Real/Binary-valued Relax-and-Randomize 2 oracle calls per round Lower Bound Construction for runtime o( p d/ ) Classical Settings FTPL with Poissonization