AF: Medium: Dropping Convexity: New Algorithms, Statistical Guarantees and Scalable Software for Non-convex Matrix Estimation

University Of Texas At Austin, Austin TX

Investigators

Abstract

An image from your camera is a matrix of numbers, but most matrices of numbers would not look like an image -- the matrix of numbers in an image reflect structure from the scene. Many applications of data analysis across science, engineering, and business can be viewed as taking a matrix of observations and fitting low-rank or otherwise structured matrices to explain their relationships. Image and video analysis is not the only example; the problem arises in structural analysis of social networks, divining user preferences for new products and services, and many other analysis tasks. As the scale and dimensionality of these problems increases, the data analyst is faced with a gap between rigor and scale: theoretically sound algorithms often have requirements (e.g. repeated/random access to data) that are feasible only on medium-scale datasets, and even then may not provide answers in "interactive time" (i.e. smallish time scales required for a human interactively analyzing data). Thus practice has turned towards methods that lack rigorous guarantees, but that are scalable and have been observed to provide decent approximation. This project aims to narrow this gap by two technical observations: (a) Recognizing that fast matrix inference necessitates non-convex algorithms, it focuses on developing a rigorous analysis of the same, and (b) by explicitly incorporating big-data architectures (out of core, and distributed multicore) in the algorithm design and statistical analysis stage itself. it focuses on several specific tasks, including pass-efficient low-rank approximation, minimizing general convex functions over the non-convex set of low-rank matrices, robust matrix estimation, and non-linear and kernel matrix settings. The project trains graduate students in the mathematical and computational development important for data analysis. The promise of big data can only be realized by scaling infrastructure with data to continue to provide statistically meaningful insights; this project aims to realize this promise for a large suite of matrix estimation problems.