EECS/IDSS Special Seminar: Lester Mackey "Matrix Completion and Matrix Concentration"


Event Speaker: 

Lester Mackey

Event Location: 


Event Date/Time: 

Tuesday, February 9, 2016 - 4:00pm

Abstract: Abstract: The goal in matrix completion is to recover a matrix from a small subset of noisy entries. Webscale
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
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.
BIO: Lester Mackey is an assistant professor of Statistics and, by courtesy, of Computer Science at Stanford
University (PhD in Computer Science and MA in Statistics from UC Berkeley; BSE in Computer Science from
Princeton U.). Lately, he has been developing and analyzing scalable algorithms for ranking,
recommender systems, approximate posterior inference, high-energy physics, and the social good. He
was an organizer of the second place team in the Netflix Prize competition for collaborative filtering, a
member of the first place team in the Prize4Life ALS disease progression prediction challenge, and a
recipient of the best student paper award at the International Conference on Machine Learning.