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.