[Ml-stat-talks] Fwd: [talks] Colloquium Speaker: Lester Mackey Today, 12:30pm

Barbara Engelhardt bee at princeton.edu
Mon Dec 14 09:23:53 EST 2015

Reminder of talk of interest today.

---------- Forwarded message ----------
From: Nicole E. Wagenblast <nwagenbl at cs.princeton.edu>
Date: Mon, Dec 14, 2015 at 9:00 AM
Subject: [talks] Colloquium Speaker: Lester Mackey Today, 12:30pm
To: "Talks (colloquium)" <talks at lists.cs.princeton.edu>

Colloquium Speaker- Joint talk with CSML
Lester Mackey, Stanford University
Monday, December 14, 12:30pm
Computer Science 105

Matrix Completion and Matrix Concentration

The goal in matrix completion is to recover a matrix from a small subset of
noisy entries. Web-scale instances of this problem include collaborative
filtering for recommendation and link prediction in social networks. Many
modern matrix completion algorithms provide strong recovery guarantees but
scale poorly due to the repeated and costly computation of truncated SVDs.
To address this deficiency, in the first part of this talk, I will
introduce Divide-Factor-Combine (DFC), a parallel divide-and-conquer
framework for boosting the scalability of a matrix completion algorithm
while retaining its theoretical guarantees. Our experiments demonstrate the
near-linear to super-linear speed-ups attainable with this approach, and
our analysis shows that DFC enjoys high-probability recovery guarantees
comparable to those of its base algorithm.

Fundamental to our analysis – and to the analyses of many matrix completion
procedures – are matrix concentration inequalities that characterize the
fluctuations of a random matrix about its mean. In the second part of this
talk, I will show how Stein’s method of exchangeable pairs can be used to
derive concentration inequalities for matrix-valued random elements. When
applied to a sum of independent random matrices, this approach yields
matrix generalizations of the classical inequalities due to Hoeffding,
Bernstein, Khintchine, and Rosenthal. The same technique delivers bounds
for sums of dependent random matrices and more general matrix functionals
of dependent random elements.
talks mailing list
talks at lists.cs.princeton.edu
To edit subscription settings or remove yourself, use this link:
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.cs.princeton.edu/pipermail/ml-stat-talks/attachments/20151214/8314eb15/attachment.html>

More information about the Ml-stat-talks mailing list