CAM Colloquium: Karthik Sridharan (Computer Science, Cornell) - Sequential Prediction and The Burkholder Method

Location

Frank H. T. Rhodes Hall 655

Description

Abstract: At the get go, sequential prediction and martingale inequalities don't seem obviously related. But in this presentation we will see how the concepts are inherently interlinked. Specifically we will see how the online prediction framework for sequential predictions is inherently tied to certain martingale inequalities. Using (and extending) the Burkholder Method, we show how one can construct functions that certify/characterize the probabilistic inequalities involving these martingales and if fact can be used in design of adaptive online machine learning algorithms. To demonstrate the power of the proposed method, we develop a novel online strategy for matrix prediction that attains a regret bound corresponding to the variance term in matrix concentration inequalities. We present a linear-time/space prediction strategy for parameter free supervised learning with linear classes and general smooth norms. We will finally use this insight to help us get a step closer to what I shall term Plug-&-Play ML. That is, help us move a step towards building machine learning systems automatically. Bio: Karthik Sridharan is an assistant professor at the department of Computer Science at Cornell University. Prior to that, he was a postdoctoral research associate at the University of Pennsylvania jointly with Alexander Rakhlin and Michael Kearns. He obtained his PhD from Toyota Technological Institute at Chicago, where his thesis advisor was Nathan Srebro. HIs primary area of research is theoretical machine learning.