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

这个项目解决了涉及多重仿射函数的优化模型的性质和求解它们的算法的基本问题。多重仿射函数是变量或变量块的函数，当所有其他变量或变量块保持不变时，变量或变量块在其中是线性的。这种类型的优化问题出现在科学、工程、医学、统计和社交媒体的各种大数据应用中，包括机器学习、计算机视觉、医学和高光谱成像以及张量模型等。由于这些问题往往涉及大量数据和大量变量，该项目将试图开发有效的分布式和概率方法，使解决方案能够比目前可能的更快地获得。预计所开发的方法将对数据科学跨学科领域的实践产生普遍影响。该项目将在来自广泛领域的特定应用的数据集上演示这种方法，并通过网站、代码发布、会议演讲和教程来传播结果，通过与哥伦比亚大学数据科学研究所不同应用学科的教职员工和学生的互动，通过哥伦比亚大学女工程师协会的女学生，以及通过哥伦比亚大学的青年学者计划接待来自未被充分代表的少数族裔的高中生。在为解决现实世界的问题提供重要工具的同时，预计该项目还将对乘子交替方向法(ADMM)的理论基础和对数据分析中出现的多仿射问题的优化前景的理解产生重大影响。ADMM已经成为在并行和分布式计算环境中解决问题的主要算法方法，因为它能够将解决困难问题的计算密集型过程转换为涉及解决由线性方程组耦合的较简单问题的迭代过程。该项目将通过使这些问题与多仿射约束相结合来扩大ADMMS的适用性。该项目将把这种多仿射ADMM(M-ADMM)方法与随机和/或分布式方法结合起来，这些方法被证明是有效和可扩展的。对于随机M-ADMM方法，将研究如何减少方差和重要性抽样。对于分布式设置，将研究如何将集中式和分散式合并约束纳入M-ADMM框架，以及异步变体。该项目将实证研究如何根据高维模型中的数据块和参数组来分配M-ADMM的计算量。由于多重仿射问题是高度非凸的，M-ADMM得到的解一般只保证是局部最优解。然而，对于某些多重仿射优化问题，在合理的假设下，每个局部极小值都是全局极小值，每个鞍点都有一个严格的负曲率方向。该项目将尝试将这些类型的结果扩展到更一般的多仿射约束问题，并研究M-ADMM避免在鞍点附近停滞不前的能力。该奖项反映了NSF的法定使命，并通过使用基金会的智力优势和更广泛的影响审查标准进行评估，被认为值得支持。

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.