Technion

Computer Science Colloquium

Time+Place : Wednesday 29/02/2012 14:30 room 337-8 Taub  Bld.
Speaker    : Nati Srebro NOTE UNUSUAL DAY
Affiliation: Toyota Technological Institute and University of Chicago.
Host       : Ran El-Yaniv
Title      : Matrix Learning: A Tale of Two Norms

Abstract   :
There has been much interest in recent years in various ways of
constraining  the complexity of matrices based on factorizations into a
product of two  simpler matrices.  Such measures of matrix complexity can
then be used as  regularizers for such tasks as matrix completion,
collaborative filtering,  multi-task learning and multi-class learning. In
this talk I will discuss two  forms of matrix regularization which constrain
the norm of the factorization,  namely the trace-norm (aka nuclear-norm) and
the so-called max-norm (aka  $\gamma_2:\ell_1\rightarrow\ell_\infty$ norm).
I will both argue that  they are independently motivated and often better
model data then rank  constraints, as well as explore their relationships to
the rank.  In particular,  I will discuss how simple low-rank matrix
completion guarantees can be obtained  using these measures, and without
various "incoherence" assumptions.  I will  present both theoretical and
empirical arguments for why the max-norm might  actually be a better
regularizer, as well as a better convex surrogate for  the rank.

Based on joint work with Rina Foygel, Jason Lee, Ben Recht, Russ

Short Bio:

Following undergraduate studies in Mathematics and in Computer Science  at
the Technion, Nati Srebro obtained his PhD from MIT in 2004,  He  was a
research fellow in the Machine Learning Group at the University  of Toronto
and a visiting scientist at IBM Research Haifa Labs.  He is  currently an
Associate Professor at the Toyota Technological Institute  at Chicago and at
the University of Chicago.

----------------------------------------------------------