Timezone: »
Poster
Oracle-Efficient Online Learning for Smoothed Adversaries
Nika Haghtalab · Yanjun Han · Abhishek Shetty · Kunhe Yang
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.
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
-
2021 : One for One, or All for All: Equilibria and Optimality of Collaboration in Federated Learning »
Richard Phillips · Han Shao · Avrim Blum · Nika Haghtalab -
2021 : One for One, or All for All: Equilibria and Optimality of Collaboration in Federated Learning »
Richard Phillips · Han Shao · Avrim Blum · Nika Haghtalab -
2022 : Invited Talk: Nika Haghtalab »
Nika Haghtalab -
2022 Spotlight: Leveraging the Hints: Adaptive Bidding in Repeated First-Price Auctions »
Wei Zhang · Yanjun Han · Zhengyuan Zhou · Aaron Flores · Tsachy Weissman -
2022 Spotlight: Lightning Talks 3B-1 »
Tianying Ji · Tongda Xu · Giulia Denevi · Aibek Alanov · Martin Wistuba · Wei Zhang · Yuesong Shen · Massimiliano Pontil · Vadim Titov · Yan Wang · Yu Luo · Daniel Cremers · Yanjun Han · Arlind Kadra · Dailan He · Josif Grabocka · Zhengyuan Zhou · Fuchun Sun · Carlo Ciliberto · Dmitry Vetrov · Mingxuan Jing · Chenjian Gao · Aaron Flores · Tsachy Weissman · Han Gao · Fengxiang He · Kunzan Liu · Wenbing Huang · Hongwei Qin -
2022 Poster: Leveraging the Hints: Adaptive Bidding in Repeated First-Price Auctions »
Wei Zhang · Yanjun Han · Zhengyuan Zhou · Aaron Flores · Tsachy Weissman -
2022 Poster: On-Demand Sampling: Learning Optimally from Multiple Distributions »
Nika Haghtalab · Michael Jordan · Eric Zhao -
2022 Poster: Beyond the Best: Distribution Functional Estimation in Infinite-Armed Bandits »
Yifei Wang · Tavor Baharav · Yanjun Han · Jiantao Jiao · David Tse -
2021 : (Live) Invited Talk: Nika Haghtalab (UC Berkeley) on Collaborative Machine Learning: Training and Incentives »
Nika Haghtalab -
2021 Workshop: Learning in Presence of Strategic Behavior »
Omer Ben-Porat · Nika Haghtalab · Annie Liang · Yishay Mansour · David Parkes -
2020 Poster: Smoothed Analysis of Online and Differentially Private Learning »
Nika Haghtalab · Tim Roughgarden · Abhishek Shetty -
2020 Spotlight: Smoothed Analysis of Online and Differentially Private Learning »
Nika Haghtalab · Tim Roughgarden · Abhishek Shetty