Smoothed Analysis of Adaptive Adversaries

Smoothed Analysis of Adaptive Adversaries (via Zoom)

Abstract: In this talk, we discuss novel algorithmic guarantees for several online problems in the smoothed analysis model. In this model, at each time step an adversary chooses an input distribution with density function bounded above pointwise that of the uniform distribution; nature then samples an input from this distribution. Crucially, our results hold for adaptive adversaries that can base their choice of an input distribution on the decisions of the algorithm and the realizations of the inputs in the previous time steps. An adaptive adversary can nontrivially correlate inputs at different time steps with each other and with the algorithm’s current state;this appears to rule out the standard proof approaches in smoothed analysis. In this talk, we present a general technique for proving smoothed algorithmic guarantees against adaptive adversaries, in effect reducing the setting of an adaptive adversary to the much simpler case of an oblivious adversary (i.e., an adversary that commits in advance to the entire sequence of input distributions). We apply this technique to prove strong smoothed guarantees for three different problems: Online learning, online discrepancy minimization and dispersion.

The talk is based on joint works with Nika Haghtalab and Tim Roughgarden.

Bio: Abhishek Shetty is currently a PhD student in the EECS department at University of California, Berkeley. Previously, he was a student at Cornell University. Prior to joining Cornell, he was a research fellow at Microsoft Research India and prior to that completed his Bachelor's degree in mathematics at Indian Institute of Science.