Several optimization problems in machine learning, data mining and graph theory can be expressed as quadratic maximization problems, subject to integrality, positivity, or sparsity constraints. These include Sparse PCA, Densest Subgraph, Nonnegative matrix factorization, MaxCut, Maximum clique and many others. These problems are known to be computationally intractable and, in many cases, hard to approximate. WNCG Profs.
WNCG Ph.D Students Dimitris Papailiopoulos and Yannis Mitliagkas, along with WNCG Professors Alex Dimakis and Constantine Caramanis, have developed an efficient low-rank framework for finding dense components of graphs with billions of connections.
WNCG Ph.D. student Chris Milling, along with WNCG Professors Constantine Caramanis and Sanjay Shakkottai, and Technion Professor Shie Mannor, have developed efficient algorithms for quickly and efficiently determining if an epidemic is spreading through a social network.
WNCG Prof. Constantine Caramanis along with Ph.D. student Ioannis Mitliagkas and MSR Bangalore researcher Dr. Prateek Jain, have obtained the first-ever linear-memory algorithm for Principal Component Analysis. Their algorithm is efficient to implement, needs to see each data point only once, and works even in the setting of many missing entries.
In two recent papers, Caramanis, Chen, Sanghavi and Yi obtain the best known statistical and computational complexity bounds for mixed regression.