STA/BST 290 Seminar: Cho-Jui Hsieh

STA 290 Seminar Series

Tuesday, March 3rd 2015, 3:10pm, Location: 1127 Kemper HallRefreshments at 2:30pm, 1127 Kemper Hall

Speaker:          Cho-Jui Hsieh (University of Texas, Austin)

Title:                Exploiting Structure in Large-Scale Machine Learning Problems

Abstract:          With an immense growth of data, there is a great need for solving large-scale machine learning problems. Classical optimization algorithms usually cannot scale up due to huge amount of data and/or model parameters. In this talk, I will show that the scalability issues can often be resolved by exploiting three types of structure in machine learning problems: problem structure, model structure, and data distribution. This central idea can be applied to many machine learning problems, including kernel machines for classification or regression, matrix factorization for recommender systems, and structure learning for graphical models.

To demonstrate this central idea, I will describe a Newton-like algorithm for solving the L1-regularized Gaussian maximum likelihood estimator (MLE). This estimator has strong statistical guarantee in recovering a sparse inverse covariance, but requires solving a difficult non-smooth log-determinant program with number of parameters that scale quadratically with number of random variables.

State-of-the-art methods thus cannot handle more than 20,000 random variables. I will present a Newton-like algorithm for solving this problem. By exploiting structure of problem, model, and data distribution, our proposed algorithm can solve 1 million dimensional L1-regularized Gaussian MLE (which has 1-trillion parameters) in one day using a single machine.