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

职业：机器学习中非凸性的祝福 - 景观分析和高效算法

• 批准号: 2337776
• 负责人: Salar Fattahi
• 金额: $ 63.55万
• 依托单位: Regents of the University of Michigan - Ann Arbor
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2024
• 资助国家: 美国
• 起止时间: 2024-06-01 至 2029-05-31
• 项目状态: 未结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=2337776&HistoricalAwards=false
• 关键词: CAREER; Blessing; Nonconvexity; Machine; Learning

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.

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