Seminar by Purushottam Kar
Beyond Regret Revisited
Purushottam Kar
Microsoft Research, India
Date: Monday, May 29th, 2014
Time: 10:00 AM
Venue: CS103.Abstract:
Techniques for implementing online learning and optimization routines have been established as valuable tools for designing scalable solvers for problems such as classification and regression. There use has allowed traditional machine learning to effortlessly extend to regimes with distributed and streaming data access.
Thus far, research in online learning has mainly focused on traditional notions of "regret" that has yielded a deep understanding of the limits of learnability in the online setting under classification and regression like losses. For several critical machine learning applications such as biometrics and medicine, such loss functions (e.g. hinge loss, least squares loss) fall short in terms of their discriminatory power. Instead ranking losses such as precision@top and (partial) area under the ROC curve are the performance measures of choice.
Traditional online learning fails to take into account such "non decomposable" loss functions. In this work we present a framework that seamlessly extends traditional notions so as to accommodate these loss functions as well as provide an equally crisp theoretical characterization of the same in terms of low-regret algorithms and online-to-batch conversion bounds.
This is joint work with Prateek Jain at Microsoft Research and Harikrishna Narasimhan at IISc.