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

大规模优化方法对最近机器学习和数据分析在广泛领域的成功应用至关重要。同时，统计模型的某些结构属性，如稀疏性或低阶结构，已被证明是在高维上获得有意义和准确的结果的关键。除了对大数据集的高度可伸缩性外，一些优化算法还具有可取的特性，即它们直接促进了模型的上述有价值的结构特性。该项目涉及开发、分析和实现具有如此有益的结构利用和内存效率特性的新型优化算法。该项目直接涉及对研究生的指导，以及将研究成果整合到本科水平的机器学习课程和研究生水平的优化与统计学习课程中。该项目的基础是Frank-Wolfe方法，一种特殊的结构开发的一阶梯度优化算法，以及相关的面向方向的方法学。面对面的方向自动促进结构良好、接近最优的解决方案，并具有令人鼓舞的内存效率特性。这项研究将研究在何种情况下，具有内部指导的方法，如应用于矩阵补全的凸松弛和更一般的原子范数正则化问题，保证具有较低的内存占用。此外，这个项目将把结合了面对面指导的方法扩展到新的问题类别，包括非光滑目标函数、非凸目标函数和随机梯度估计。建议的优化框架和面对面方法非常适用，并有可能在几个领域产生更广泛的影响，包括推荐系统、生物信息学、客户细分、情绪分析和医学成像。该奖项反映了NSF的法定使命，并通过使用基金会的智力优势和更广泛的影响审查标准进行评估，被认为值得支持。

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.