CAREER: Next-Generation Design of First-Order Optimization Algorithms by the Calculus of Variations of Self-Dual Functionals

大规模优化问题的解决方案是许多现代计算应用（包括人工智能和数据分析）背后的基本构建块。随着机器学习系统被输入更多的数据并被要求推断更复杂的概念，需要改进的方法来解决更大、更多样化的优化问题。应对这一挑战的最成功的方法是基于一类简单的算法：一阶方法。这些算法通过使用局部的、易于计算的信息迭代地更新当前解来构造从给定的初始解到最优解的路径。例如，集中体现一阶方法的梯度下降，通过在局部导致解的最大改进的方向上移动来简单地更新当前解。该项目通过描述一阶方法的原则设计的新框架，对一阶方法采取了创造性和潜在的变革性观点，一个消除了许多猜测和工艺，目前需要推进最先进的状态或扩展其应用到新的设置。新框架背后的技术见解是查看第一-秩序的方法类似于经典的物理系统，其中简单的，当地的法律规范系统的演变驱动出现的全球结构的形式不变，即，守恒量，如能量或动量，以及变分原理，即，被隐式优化的量，例如动作。这一见解将通过微积分变化的经典数学理论进行阐述，并被用来为广泛的优化问题设计可扩展的算法。通过整合对机器学习和数据科学至关重要的连续数学技术，与该项目相关的教育活动将使算法基础的核心本科课程现代化。该奖项反映了NSF的法定使命，并通过使用基金会的智力价值和更广泛的影响审查标准进行评估，被认为值得支持。

The solution of large-scale optimization problems is a fundamental building block behind many modern applications of computing, including artificial intelligence and data analytics. As machine-learning systems are fed more data and asked to infer more complex concepts, there is a need for improved methods for solving the underlying larger and more varied optimization problems. The most successful approaches to meet this challenge are based on a simple class of algorithms: first-order methods. These algorithms construct a path from a given initial solution to an optimal solution by iteratively updating the current solution using local, easy-to-compute information. For example, gradient descent, which epitomizes first-order methods, simply updates the current solution by moving in the direction that locally leads to the largest improvement in the solution. The project takes a creative and potentially transformative viewpoint on first-order methods by describing a new framework for their principled design, one that removes much of the guesswork and craftsmanship that are currently required to advance the state of the art or to extend their application to novel settings.The technical insight behind the new framework is to view the computational power of first-order methods as analogous to that of classical physical systems, in which simple, local laws regulating the system’s evolution drive the emergence of global structure in the form of invariants, i.e., conserved quantities such as energy or momentum, and variational principles, i.e., quantities that are implicitly optimized, such as action. This insight will be expounded through the classical mathematical theory of the calculus variations and exploited to design scalable algorithms for a broad range of optimization problems. By incorporating techniques from continuous mathematics that are crucial to machine learning and data science, the educational activities associated with this project will modernize the core undergraduate curriculum in the foundations of 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.