Timezone: »

 
Poster
Oracle-Efficient Online Learning for Smoothed Adversaries
Nika Haghtalab · Yanjun Han · Abhishek Shetty · Kunhe Yang

Thu Dec 01 02:00 PM -- 04:00 PM (PST) @ Hall J #824
in Poster Session 6 »
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/\sigma$ 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 $\sigma$. In particular, we achieve \emph{oracle-efficient} regret bounds of $ O ( \sqrt{T d\sigma^{-1}} ) $ for learning real-valued functions and $ O ( \sqrt{T d\sigma^{-\frac{1}{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 ( \sqrt{T(d |\mathcal{X}|)^{1/2} })$ regret that refines the earlier $O ( \sqrt{T|\mathcal{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.
Keywords: Online Learning · Smoothed Analysis · Computational Efficiency
[ Paper]  [ Poster]  [ OpenReview] 

Author Information

Nika Haghtalab (University of California, Berkeley)
Yanjun Han (Massachusetts Institute of Technology)
Abhishek Shetty (UC Berkeley)
Kunhe Yang (UC Berkeley)

More from the Same Authors