Seminar - Paul Grigas

Friday, January 29, 2016 9:00 am - 9:00 am EST (GMT -05:00)

Title: Structure-enhancing algorithms for statistical learning problems

Speaker: Paul Grigas
Affiliation: MIT
Room: MC 5417

Abstract: For many problems in statistical machine learning and data-driven decision-making, massive datasets necessitate the use of scalable algorithms that deliver sensible (interpretable) and statistically sound solutions. In this talk, we discuss several scalable algorithms that directly promote well-structured solutions in two related contexts: (i) sparse high-dimensional linear regression, and (ii) low-rank matrix completion, both of which are particularly relevant in mod- ern machine learning. In the context of linear regression, we study several boosting algorithms which directly promote sparse solutions from the perspective of modern first-order methods in convex optimization. We use this perspective to derive the first-ever computational guarantees for existing boosting methods and to develop new algorithms with associated computational guarantees as well. In the context of matrix completion, we present an extension of the Frank- Wolfe method in convex optimization that is designed to induce near-optimal low-rank solutions for regularized matrix completion problems, and we derive computational guarantees that trade off between low-rank structure and data fidelity. For both problem contexts, we present com- putational results using datasets from microarray and recommender system applications.