CAREER: Blessing of Nonconvexity in Machine Learning - Landscape Analysis and Efficient Algorithms

一个优化问题的可处理性通常是通过它是否能被写成一个凸规划来评估的。然而，最近几年，人们对什么被认为是优化中的易处理的观点发生了转变：随着非凸模型几乎完全用于现代机器学习(ML)，越来越明显的是，可以用凸性来换取表示或灵活性。然而，利用这种力量需要付出高昂的成本。首先，经典优化理论断言，在没有凸性的情况下，高效的大规模算法产生的解可能不享有任何最优性保证，这在ML的安全关键应用中可能是有害的。其次，许多现代非凸优化问题都非常大，计算成本高得离谱。这种对计算能力的贪婪需求使得释放非凸模型的全部表示能力变得困难，特别是在无法访问大量计算资源的领域中。本项目的目标是通过设计可靠和高效的计算方法来训练ML中的非凸模型，从而降低上述成本。特别是，这个项目旨在揭示ML中非凸问题的独特结构，使它们变得容易处理，最终将非凸性从诅咒转化为祝福。该项目将整合各种针对K-12、本科生和研究生的教育项目。值得注意的是，将与资源不足的学校建立新的合作伙伴关系，帮助来自低收入家庭的学生介绍新的大学机会。为了扩大这些方案的影响，这些经验将以短文的形式与不同的社区分享。此外，所有的资料都将提供给公众使用。这个项目的目的是弥合优化和统计学习之间的长期差距。虽然现代统计学习倾向于非凸模型良好的泛化和表示性质，但经典优化理论认为，在非凸场景中，实用算法不可避免地难以恢复全局最优解。这个项目挑战了传统的范式，即只根据优化算法找到全局最优的能力来评估它们的性能。事实上，这个项目将断言，在ML中的许多实用的非凸模型，从低阶矩阵恢复到深度神经网络，都具有局部解，这些局部解不仅比它们的全局同行更容易获得，而且更接近真实解，产生更小的泛化误差。该项目旨在通过围绕真实解决方案对非凸模型的优化前景进行系统分析，并设计可靠和高效的算法来在有意义的环境和规模中解决这些问题，来形式化这一基本见解。该奖项反映了NSF的法定使命，并通过使用基金会的智力优势和更广泛的影响审查标准进行评估，被认为值得支持。

The tractability of an optimization problem is often assessed by whether it can be written as a convex program. Yet recent years have witnessed a shift in perspective on what is deemed tractable in optimization: with nonconvex models being used almost exclusively in modern machine learning (ML), it has become increasingly clear that convexity can be traded for representation or flexibility. However, harnessing this power comes at steep costs. First, classical optimization theory asserts that in the absence of convexity, efficient large-scale algorithms generate solutions that may not enjoy any optimality guarantee, which can be detrimental in safety-critical applications of ML. Second, many modern nonconvex optimization problems are overwhelmingly large with outrageously high computational costs. This voracious appetite for computing power makes it difficult to unlock the full representation power of nonconvex models, especially in domains that lack access to substantial computing resources. The goal of this project is to lower the above costs by designing reliable and efficient computational methods for training nonconvex models in ML. In particular, this project aims to uncover the distinct structures of the nonconvex problems in ML that make them tractable, ultimately transmuting nonconvexity from a curse to a blessing. The project will integrate a variety of educational programs for K-12, undergraduate, and graduate students. Notably, new partnerships will be forged with under-resourced schools to help introduce new college opportunities to students from low-income families. To broaden the impact of these programs, the experiences will be shared with different communities in the form of short articles. Furthermore, all the materials will be made available for public use.This project aims to bridge a longstanding gap between optimization and statistical learning. While modern statistical learning favors nonconvex models for their favorable generalization and representation properties, classical optimization theory argues that practical algorithms inevitably struggle to recover globally optimal solutions in nonconvex scenarios. This project challenges the conventional paradigm that evaluates the performance of optimization algorithms solely based on their ability to find global optima. In fact, this project will assert that numerous practical nonconvex models in ML, from low-rank matrix recovery to deep neural networks, possess local solutions that are not only more tractable to obtain than their global counterparts, but also closer to the true solutions, yielding smaller generalization errors. This project aims to formalize this fundamental insight by conducting a systematic analysis of the optimization landscape of nonconvex models around the true solutions, and designing reliable and efficient algorithms to solve them in meaningful settings and scales.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.