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 modern 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 computational results using datasets from microarray and recommender system applications.

Bio

Paul Grigas is a fifth year Ph.D. student in Operations Research at MIT.  His research interests include large-scale convex optimization, statistical machine learning, and data-driven decision making.  Paul is also interested in applications in online advertising and data analytics, among other areas.  Paul was recently awarded the 2015 INFORMS Optimization Society Student Paper Prize, and he was the recipient of an NSF Graduate Research Fellowship.  Before coming to MIT, Paul earned a B.S. in Operations Research and Information Engineering from Cornell University.