BIGDATA: F: Multiaffine Constrained Optimization for High-Dimensional Big Data Models

This project addresses fundamental questions about properties of optimization models involving multiaffine functions and algorithms for solving them. Multiaffine functions are functions of variables, or blocks of variables, that are linear in them when all other variables, or blocks of variables, are held fixed. Optimization problems of this type arise in a wide variety of big data applications in science, engineering, medicine, statistics and social media, including machine learning, computer vision, medical and hyperspectral imaging, and tensor models to name just a few. Because these problems often involve massive amounts of data and huge numbers of variables, this project will attempt to develop efficient distributed and probabilistic approaches, enabling solutions to be obtained more rapidly than is currently possible. It is expected that the methodology that is developed will have a pervasive influence on practice in the interdisciplinary field of data science. The project will demonstrate this methodology on data sets from specific applications from a wide range of fields and disseminate the results through websites, code release and conference talks and tutorials, as well as through interactions with faculty and students from various applied disciplines in Columbia University's Data Science Institute, female students through the Society of Women Engineers at Columbia, and the hosting of high school students from under-represented minorities through Columbia University's Young Scholars Program.

While providing important tools for solving real world problems, the project is also expected to have a major impact on the theoretical underpinnings of the Alternating Direction Method of Multipliers (ADMM) and an understanding of the optimization landscape of multiaffine problems arising in data analysis. ADMM has become a major algorithmic approach for solving problems in both parallel and distributed computational settings, because of its ability to transform the computationally intensive process of solving a difficult problem into an iterative procedure that involves solving simpler problems that are coupled by a system of linear equations. The project will expand ADMMs applicability by enabling these problems to be coupled by multiaffine constraints. The project will combine this multiaffine ADMM (M-ADMM) approach with stochastic and/or distributed approaches that are provably efficient and scalable. For stochastic M-ADMM methods, how to reduce variance and importance sampling will be studied. For distributed settings, how to incorporate both centralized and decentralized concensus constraints into an M-ADMM framework will be investigated, as will asynchronous variants. The project will empirically study how to distribute the the computational effort of M-ADMM, both according to blocks of data and groups of parameters in high dimensional models. Because multiaffine problems are highly nonconvex, the solutions obtained by M-ADMM are in general only guaranteed to be local optima. It is known however, that for certain multiaffine optimization problems, every local minimum is a global minimum and every saddle point has a direction of strict negative curvature under reasonable assumptions. The project will attempt to expand these kinds of results to more general multiaffine constrained problems and study the ability of M-ADMM for avoiding stagnating near saddle points.

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.