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.