CAREER: Algorithmic foundations for practical acceleration in computational sciences

非凸优化是许多具有深远社会影响的工程应用的核心，特别是通过机器学习/人工智能引发的浪潮：物理学、医疗保健、生物学、软件工程、化学和材料科学等领域。然而，由于缺乏理论，从业者通常只是简单地遵循试错程序，导致启发式。当启发式被证明是可证明的算法时，对科学界乃至整个社会来说，这是一个迫切的需要。该提案的目标是建立算法基础，以及理论，以加速在这种情况下解决问题。这构成了快速算法设计在机器学习、信息处理和优化研究中的一个活跃研究领域。了解如何使用高效的算法获得卓越的性能，对于实际和安全的应用学习具有最终意义。这项研究的困难/风险恰恰在于任务的非凸性，即现有知识无法带来更深入的理解。其目的是提供在实际环境中更快更好地执行的方法，以及介绍证明其性能的理论。考虑到任务的难度和多样性，PI将专注于三个研究领域：i)结构丰富问题的更快收敛，特别关注矩阵分解机器学习问题；Ii)在更一般的非凸场景中的算法加速，特别关注（浅）神经网络架构；iii)现代机器学习系统中的加速技术，如修剪技术、分布式协议和超参数调优。上面提到的目标是相互补充的：它们的组合形成了一个统一的数学框架，这将为我们提供一些非凸工具在ML和优化研究中工作的原因和方式。PI将研究和分析算法在文本分析、图像分类和实际难组合问题等方面的应用。提议的研究将分析非凸场景中经典动量之外的想法，例如算法隐式正则化，超参数调优，深度矩阵分解，近点算法和鲁棒性，以及彩票假设，仅举几例。长期目标是在非凸环境中对实际方法进行严格的表征，希望它们有可能变成一种设计更快更好算法的技术。该奖项反映了美国国家科学基金会的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。

Non-convex optimization lies at the heart of many engineering applications with far-reaching societal impacts, especially through the wave that machine learning/artificial intelligence triggers: physics, healthcare, biology, software engineering, chemistry and materials science, among other areas. However, given the lack of theory, practitioners often simply follow trial-and-error procedures, leading to heuristics. Characterizing when heuristics turn out to be provable algorithms is one pressing need for the scientific community, and indeed society as a whole. The goal of the proposal is to build algorithmic foundations, along with theory, that accelerate problem solving in such scenarios. This constitutes the design of fast algorithms as an active research area in machine learning, information processing, and optimization research. Understanding how remarkable performance is obtained using efficient algorithms is of ultimate significance towards practical and safely applicable learning. The difficulty/risk of this research lies exactly in the non-convex nature of the tasks, where existing knowledge does not lead to a deeper understanding.The aim is to provide methodologies that perform faster and better in practical settings, as well as introduce theory that justifies their performance. Given the difficulty and diversity of the task, the PI will focus on three research areas: i) faster convergence in structure-rich problems, with a special focus on matrix-factorized machine learning problems; ii) algorithmic acceleration in more general non-convex scenarios, with a special focus on (shallow) neural network architectures; and iii) acceleration techniques in modern ML systems, such as pruning techniques, distributed protocols and hyperparameter tuning. The objectives mentioned above complement each other: their combination results in a unified mathematical framework that will provide insights on why and how several non-convex tools work in ML and optimization research. The PI will study and analyze algorithms with applications in text analytics, image classification, and practical hard combinatorial problems, among others. The proposed research will analyze ideas beyond classical momentum in non-convex scenarios, such as algorithmic implicit regularization, hyper-parameter tuning, deep matrix factorization, proximal point algorithms and robustness, and lottery-ticket hypotheses, just to name a few. The long-term goal is the rigorous characterization of practical methods in non-convex settings, with the hope that they could potentially turn into a technology for designing faster and better algorithms.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.