CAREER: Automated Analysis and Design of Optimization Algorithms

职业：优化算法的自动分析和设计

• 批准号: 2136945
• 负责人: Laurent Lessard
• 金额: $ 46.73万
• 依托单位: Northeastern University
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2021
• 资助国家: 美国
• 起止时间: 2021-06-15 至 2024-10-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=2136945&HistoricalAwards=false
• 关键词: CAREER; Automated; Analysis; Design; Optimization

Iterative optimization algorithms lie at the heart of modern data-intensive applications such as machine learning, computer vision, and data science. Society has become increasingly reliant on such algorithms for commerce, transportation, healthcare, emergency response, and national security. Despite their critical role in society, algorithms are typically designed and tuned using insight from experts, extensive numerical simulations, and other heuristics. This research develops a more principled understanding and approach to algorithm design that automatically accounts for sensitivity to parameter choice, robustness to noise, and other sources of uncertainty. This approach enables algorithms to be engineered in a way that guarantees performance and safety, which is similar to how airplanes, skyscrapers, and computer hardware are built.Iterative algorithms may be viewed as dynamical systems with feedback. In gradient-based descent methods, for example, gradients are evaluated at each step and used to compute subsequent iterates. By treating algorithms as control systems, this research leverages tools from robust control (specifically: integral quadratic constraints, graphical methods, and semidefinite representation) to analyze and ultimately synthesize a variety of algorithms under different assumptions in an efficient, scalable, and systematic manner. This research also involves collaborative efforts in the areas of graph structure learning of gene regulatory networks and interactive machine learning, which serve to test and validate new algorithm designs.

迭代优化算法是机器学习、计算机视觉和数据科学等现代数据密集型应用的核心。社会越来越依赖这种算法来进行商业，交通，医疗保健，应急响应和国家安全。尽管算法在社会中发挥着关键作用，但它们通常是使用专家的洞察力、广泛的数值模拟和其他数学方法来设计和调整的。这项研究开发了一个更有原则的理解和方法，算法设计，自动占参数选择的敏感性，噪声的鲁棒性，和其他来源的不确定性。这种方法使算法能够以保证性能和安全的方式进行设计，这类似于飞机，摩天大楼和计算机硬件的建造方式。迭代算法可以被视为具有反馈的动力系统。例如，在基于梯度的下降方法中，梯度在每一步都被评估，并用于计算后续的迭代。通过将算法视为控制系统，本研究利用鲁棒控制的工具（具体而言：积分二次约束，图形方法和半定表示），以高效，可扩展和系统的方式在不同的假设下分析并最终合成各种算法。这项研究还涉及基因调控网络的图结构学习和交互式机器学习领域的合作，这些领域用于测试和验证新的算法设计。

项目成果

The Analysis of Optimization Algorithms: A Dissipativity Approach

• DOI: 10.1109/mcs.2022.3157115
• 发表时间: 2022-05
• 期刊: IEEE Control Systems
• 作者: Laurent Lessard

A Unified Analysis of First-Order Methods for Smooth Games via Integral Quadratic Constraints

• 发表时间: 2020-09
• 期刊: J. Mach. Learn. Res.
• 作者: Guodong Zhang;Xuchao Bao;Laurent Lessard;R. Grosse

Absolute Stability via Lifting and Interpolation

通过提升和插值实现绝对稳定性

• DOI: 10.1109/cdc51059.2022.9993272
• 发表时间: 2022
• 期刊: 2022 IEEE 61st Conference on Decision and Control
• 作者: Scoy, Bryan Van;Lessard, Laurent
• 通讯作者: Lessard, Laurent

A Tutorial on a Lyapunov-Based Approach to the Analysis of Iterative Optimization Algorithms

• DOI: 10.1109/cdc49753.2023.10384074
• 发表时间: 2023-09
• 期刊: 2023 62nd IEEE Conference on Decision and Control (CDC)
• 作者: Bryan Van Scoy;Laurent Lessard

A Tutorial on the Structure of Distributed Optimization Algorithms

分布式优化算法结构教程

• DOI: 10.1109/cdc49753.2023.10383319
• 发表时间: 2023
• 期刊: 2023 62nd IEEE Conference on Decision and Control (CDC
• 作者: Van Scoy, Bryan;Lessard, Laurent
• 通讯作者: Lessard, Laurent