[Colloquium] ML Seminar Talk: Nati Srebro, TTI-C

[Julia MacGlashan]

When:              Wednesday, October 22 @ 11:00am

 

Where:            Machine Learning Seminar

TTI-C Conference Room: 1427 E. 60th St, 2nd Floor

                         

Who:                Nati Srebro, Toyota Technological Institute at Chicago

 

Title:                 Stochastic Convex Optimization

 

Recently regret bounds for online convex optimization have been derived
under very general conditions.  These results can be used also in the
stochastic batch setting by applying online-to-batch conversions.  It is
interesting to study whether stochastic guarantees can be obtained more
directly, for example using uniform convergence guarantees.  We discover a
surprising and complex situation: although the stochastic convex
optimization problem is solvable (e.g. using online-to-batch conversions),
no uniform convergence holds in the general case, and empirical minimization
might fail.

 

This is unlike the familiar case of supervised learning, where learning is
possible if and only if the empirical errors of all hypothesis converge
uniformly and so empirical minimization can be used.  The situation also
seems to contradict more general results by Vapnik on the equivalence of
stochastic optimization and uniform convergence.

 

Rather then being a difference between online methods and a global
minimization approach, we show that the key ingredient is strong convexity
and regularization.  In doing so we provide new understanding of the role of
regularization: even when regularization does not ensure uniform convergence
(which is the standard understanding of regularization), it can ensure
stability, and so ensure generalization even without uniform convergence.

 

Joint work with Karthik Sridharan and Shai Shalev-Shwartz

 

Contact:          Nati Srebro, TTI-C         nati at tti-c.org
834-7493

 

 

 

 

 

 

 

 

 

 

 

 

 

-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20081021/4acc91ec/attachment.htm