Technion, IEM faculty - Operations Research seminar
Speaker:  Nathan Srebro, Toyota Technological Institute, Chicago, USA
Title:    Optimization, Learning and the Universality of Mirror Descent
Date:     14/11/2011
Time:     12:30
Place:    Bloomfield-527
Abstract: I will discuss deep connections between Statistical
Learning, Online Learning and Optimization. I will show that there is
a tight correspondence between the sample size required for learning
and the number of local oracle accesses required for optimization,
and the same measures of "complexity" (e.g. the fat-shattering
dimension or Rademacher complexity) control both of them.
Furthermore, I will show how the Mirror Descent method, and in
particular its stochastic/online variant, is in a strong sense
"universal" for online learning, statistical learning and
optimization. That is, for a general class of convex
learning/optimization problems, Mirror Descent can always achieve a
(nearly) optimal guarantee. In the context of statistical learning,
this also implies that for a broad generic class of convex problems,
learning can be done optimally (in the worst-case agnostic-PAC sense)
with a single pass over the data. Joint work with Karthik Sridharan
and Ambuj Tewari, and mostly based on Sridharan's PhD Thesis.
You can watch the rest of the seminar plan at our web site
Or-seminar mailing list
Technion Math. Net (TECHMATH)
Editor: Michael Cwikel   <> 
Announcement from:  <>