Seminars
View all Seminars | Download ICal for this eventSmoothed Analysis of Online Decision Making
Series: Bangalore Theory Seminars
Speaker: Abhishek Shetty UC Berkeley
Date/Time: Jan 09 11:00:00
Location: CSA Seminar Hall (Room No. 254, First Floor)
Abstract:
We establish novel techniques to analyze algorithms in the smoothed analysis model for online decision making. In this model, at each step, an adversary chooses the input from distribution with density bounded above by the uniform distribution. Crucially, these techniques hold for adaptive adversaries that can choose distributions based on the decisions of the algorithm and the previous realizations of the inputs. Our technique effectively reduces the setting of adaptive adversaries to the simpler oblivious adversaries. The main application is to show that, in this model, online learning is as easy as offline learning. That is, we show that the regret against smoothed adversaries is captured by the offline complexity measure, VC dimension. Furthermore, we design efficient algorithms for online learning, circumventing impossibility results in the worst case.
Based on joint works with Nika Haghtalab, Yanjun Han, Tim Roughgarden and Kunhe Yang.
Speaker Website Link
Microsoft teams link:
Link
Acknowledging the support from the Kirani family for generously supporting the seminar series.
Hosts: Aditya Subramanian, Aditya Abhay Lonkar, Rahul Madhavan & Rameesh Paul