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

点击翻译按钮获取中文摘要

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.