[Colloquium] Karthik Sridharan's Defense

[Liv Leader]

Date:  Wednesday, October 19, 2011

Time:  10:30 AM

Title: LEARNING FROM AN OPTIMIZATION VIEWPOINT

Abstract:

Optimization has always played a central role in machine learning. The
connection between optimization and learning is deep : one can phrase
learning problems as optimization problems. In this dissertation I take this
viewpoint to analyze learning problems. The dissertation can be divided into
two parts.

The first part deals with the question of learnability and learning rates in
the statistical and online learning settings. In the statistical learning
framework, through an example of a stochastic convex optimization problem we
first show that the usual tools from empirical process theory fail in
general. We then characterize learnability through the notion of stability
of learning algorithms and provide a generic algorithm for learning in this
setting. Moving to the online learning framework we develop tools analogous
to complexity measure tools from statistical learning theory like Rademacher
complexity, covering numbers etc. We show that these tools can be used to
characterize online learnability for supervised learning problems and build
a generic algorithm for these problems.

While the first part mainly focused on the question of learnability, in the
second part, restricting our attention to convex learning problems, we also
address the issue of tractability of learning algorithms through oracle
complexity of the problem. For online convex learning problems, using the
concept of martingale type from Banach space geometry, we show that online
mirror descent algorithm is always near optimal. Moving to the statistical
learning framework, we show that while mirror descent may not be always
optimal, for most reasonable convex problems, mirror descent is still near
optimal both in terms of rates and oracle complexity. While establishing
these results we also show that for a large class of high dimensional
optimization problems, mirror descent is near optimal.

Committee :  David McAllester, Arkadi Nemirovski, Alexander Razborov, Nathan
Srebro (advisor)

-- 
Liv Leader
Human Resources Coordinator

Toyota Technological Institute
6045 S Kenwood Ave
Chicago, IL 60637
Phone- (773) 702-5033
Fax-     (773) 834-9881
Email-  lleader at ttic.edu <jam at ttic.edu>
Web-   www.ttic.edu
 <http://www.ttic.edu/>



-- 
Liv Leader
Human Resources Coordinator

Toyota Technological Institute
6045 S Kenwood Ave
Chicago, IL 60637
Phone- (773) 702-5033
Fax-     (773) 834-9881
Email-  lleader at ttic.edu <jam at ttic.edu>
Web-   www.ttic.edu
<http://www.ttic.edu/>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20111010/72f6fbfb/attachment.htm