Alexander "Sasha" Rakhlin: A few peculiar connections between deterministic worst-case prediction algorithms and probabilistic inequalities

Friday, April 1, 2016 - 1:30pm to 4:30pm
Pizza at 1:15p
D-463, Star Conf. Room
Alexander "Sasha" Rakhlin

Abstract: In this talk, we will outline several equivalences between deterministic and probabilistic statements. First, we will argue that *existence* of deterministic online algorithms can be certified via certain probabilistic inequalities. Conversely, simple worst-case prediction algorithms yield probabilistic inequalities that are otherwise difficult to prove. As an example, we will see that the number of steps required by any first-order deterministic optimization method (e.g. mirror descent) can be understood by studying lengths of random walks. The equivalence, however, extends beyond situations where we know how to construct algorithms. Time permitting, we will outline results that point to the equivalence of sample complexity in online regression with worst-case sequences, statistical learning with i.i.d. data, and nonparametric estimation in statistics. The nature of this latter phenomenon is not very clear.