CRII: CIF: New Structure-Exploiting and Memory-Efficient Methods for Large-Scale Optimization and Data Analysis

University Of California-Berkeley, Berkeley CA

Investigators

Abstract

Large-scale optimization methods have been paramount to the successes of recent applications of machine learning and data analysis in a wide variety of domains. At the same time, certain structural properties of statistical models, such as sparsity or low-rank structure, have proven to be crucial for obtaining meaningful and accurate results in high dimensions. In addition to being highly scalable to large datasets, some optimization algorithms have the desirable property that they directly promote the aforementioned valuable structural properties of models. This project involves developing, analyzing, and implementing novel optimization algorithms that have such beneficial structure-exploiting and also memory-efficiency properties. This project directly involves the mentoring of graduate students, as well as integration of research results into an undergraduate level machine learning course and a graduate level course in optimization and statistical learning. The foundation for this project is the Frank-Wolfe Method, a particular structure-exploiting first-order gradient optimization algorithm, and the related methodology of in-face directions. In-face directions automatically promote well-structured near-optimal solutions and have encouraging memory-efficiency properties. This research will investigate conditions whereby methods with in-face directions, as applied to convex relaxations of matrix completion and more general atomic norm regularization problems, are guaranteed to have a low memory footprint. Furthermore, this project will extend the reach of methods that incorporate in-face directions to new problem classes, including non-smooth objective functions, non-convex objective functions, and stochastic gradient estimates. The proposed optimization framework and in-face methodology applies very generally, and has potential for broader impact in several areas, including recommender systems, bioinformatics, customer segmentation, sentiment analysis, and medical imaging. This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.