CAREER: Algorithmic foundations for practical acceleration in computational sciences

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

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.