Learning in Statistical and Online Frameworks : Connections and an Optimization Viewpoint
Abstract: There are two frameworks commonly considered for machine learning problems. The first is the classical statistical learning framework where the learner is presented with a training sample of instances drawn independently from a fixed but unknown distribution. The goal of the learner is to use this training sample to pick a hypothesis that has comparatively low expected error on future instances drawn from the distribution. The second is the online learning framework where at each time step learner picks a new hypothesis and is faced with instances (that could be selected adversarially). The goal of the learner in this framework is to have a low average loss compared to that of the best hypothesis in a class of hypotheses in hindsight.
In the first part of the talk we will consider the question of when it is possible to learn under the two frameworks for very general learning problems. We will especially concentrate on the online framework. We will show that complexity measures analogous to the ones used in the classical statistical learning framework can be defined to upper bound learning rates in the online framework and that these in fact characterize learnability and rates for the "supervised learning problem". We will also look closely into convex learning problems in the online framework and characterize learning rates through geometry of the hypothesis class.
In the second part of the talk we will look at connections between learning in online and batch framework. We will specifically concentrate on convex learning problems. We will be also interested in questions of whether it is possible to learn only using access to some "local oracle" (Example gradient of the function at point of query) and if so how efficient can we be in the number of calls to the oracle. We will look into connections between problems that are efficiently statistically learnable and online learnable. We will try to reason why often online learning techniques provide good algorithms for statistical learning problems.
Speaker Bio: Karthik Sridharan is a PhD candidate working with Prof. Nathan Srebro at the Toyota Technological Institute at Chicago. He also received an MS degree in Computer Science at SUNY Buffalo in 2006. His research interests include machine learning (statistical and online learning theory), Optimization and Empirical Process Theory.