BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//project/author//NONSGML v1.0//EN
CALSCALE:GREGORIAN
BEGIN:VEVENT
DTEND:20230109T120000Z
UID:da1de9b6a4cbd880f360b71b837eb5f4-387
DTSTAMP:19700101T120011Z
DESCRIPTION:Smoothed Analysis of Online Decision Making
URL;VALUE=URI:https://www.csa.iisc.ac.in/newweb/event/387/smoothed-analysis-of-online-decision-making/
SUMMARY: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	https://ashettyv.github.io/


Microsoft teams link:

https://teams.microsoft.com/l/meetup-join/19%3ameeting_ZGE3NDg5NzktMWQ0Zi00MzFmLTg5OTgtMTMyYWM4MWQyYjI2%40thread.v2/0?context=%7b%22Tid%22%3a%226f15cd97-f6a7-41e3-b2c5-ad4193976476%22%2c%22Oid%22%3a%227c84465e-c38b-4d7a-9a9d-ff0dfa3638b3%22%7d


Acknowledging the support from the Kirani family for generously supporting the seminar series.


Hosts: Aditya Subramanian, Aditya Abhay Lonkar, Rahul Madhavan & Rameesh Paul
DTSTART:20230109T120000Z
END:VEVENT
END:VCALENDAR