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

职业：通过自对偶泛函变分计算的下一代一阶优化算法设计

• 批准号: 1943510
• 负责人: Lorenzo Orecchia
• 金额: $ 50.09万
• 依托单位: University of Chicago
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2020
• 资助国家: 美国
• 起止时间: 2020-01-15 至 2024-12-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1943510&HistoricalAwards=false
• 关键词: CAREER; Next; Generation; Design; First

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.

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

项目成果

Fair Packing and Covering on a Relative Scale

相对规模的公平包装和覆盖

• DOI: 10.1137/19m1288516
• 发表时间: 2020
• 期刊: SIAM Journal on Optimization
• 影响因子: 3.1
• 作者: Diakonikolas, Jelena;Fazel, Maryam;Orecchia, Lorenzo
• 通讯作者: Orecchia, Lorenzo

Practical Almost-Linear-Time Approximation Algorithms for Hybrid and Overlapping Graph Clustering

混合和重叠图聚类的实用近线性时间近似算法

• 发表时间: 2022
• 期刊: Proceedings of the 39th International Conference on Machine Learning (ICML 2022
• 作者: Orecchia, Lorenzo;Ameranis, Konstantinos;Tsourakakis, Charalampos;Talwar, Kunal
• 通讯作者: Talwar, Kunal