CRII: AF: Faster Iterative Decisions within First-order Optimization Methods

CRII：AF：一阶优化方法中更快的迭代决策

• 批准号: 1850182
• 负责人: Swati Gupta
• 金额: $ 17.5万
• 依托单位: Georgia Tech Research Corporation
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2019
• 资助国家: 美国
• 起止时间: 2019-06-01 至 2022-05-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1850182&HistoricalAwards=false
• 关键词: CRII; AF; Faster; Iterative; Decisions

At the heart of most user-centric algorithms today is an optimization engine trying to provide the best decision with the information observed so far in time. Examples include recommending preferred items to new consumers, computing least congested routes in a road network with changing traffic, distributing power radially over electricity grids with changing demand, and so on. All these problems have an inherent "combinatorial" structure that constrains the possible decisions one can take. This combinatorial structure becomes even more complex when these decisions are required to incorporate fairness and reduce disparate impact, such as a balanced representation of female/male scientists when a search query for "scientists" is made. These combinatorial problems are computationally challenging, necessitating rigorous yet fast algorithms to run these efficiently in real-world scenarios where decisions must be made in real-time. A large class of optimization methods prevalent in learning applications, the so-called first-order optimization methods, work by repeatedly solving perturbations of similar combinatorial subproblems. This research project will explore whether the knowledge of "how" the solution was computed to previous subproblems within first-order optimization methods can be used to speed up computations in subsequent iterations. This project has the potential of speeding up a wide range of applications whenever a constrained decision with combinatorial structure must be made in real-time as mentioned above. The interdisciplinary nature of this work, spanning first-order optimization methods and combinatorial algorithms, will benefit students helping prepare a stronger and a holistic STEM workforce with impact in a large number of applications - at both undergraduate and graduate levels.This project serves as a cornerstone for proper integration of first-order optimization methods (like Frank-Wolfe (FW), mirror descent (MD) and their variants) and the theory of combinatorial optimization with wide-ranging applications. It brings together the theory of data structures, approximation algorithms, parametric analysis in combinatorial optimization and the computational requirements of iterative first-order optimization methods to achieve amortized speeds ups in overall runtime. MD and FW variants rely only on the function value and gradient information at a single data point in each iteration and this property has rendered these methods to be used in numerous real-time machine learning applications. When making constrained combinatorial decisions as described above, these methods repeatedly compute two main subproblems: (i) linear optimization in each iteration of the FW variants, and (ii) projections or convex minimization in each iteration of the MD variants. With this award, the investigator will explore (a) identification of combinatorial primitives suitable for amortized analysis within first-order methods, (b) use of previously discovered tight cuts for iterative projections within mirror descent variants, (c) decomposition of convex problems, (d) construction of smarter warm start solutions for first-order optimization, (e) weaker but relevant approximate models and algorithms for repeated perturbed subproblems. With recent results closing the gap of possible convergence rates for first-order optimization in various settings, these questions have become of paramount importance to enable the next scale up in runtime of constrained decision-making to real-time user-centric applications.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.

当今大多数以用户为中心的算法的核心是优化引擎，试图根据迄今为止观察到的信息提供最佳决策。示例包括向新消费者推荐首选商品、根据交通变化计算道路网络中最不拥堵的路线、根据需求变化在电网上径向分配电力等等。所有这些问题都有一种固有的“组合”结构，限制了人们可以做出的可能决策。当这些决策需要纳入公平性并减少不同的影响时，例如在进行“科学家”搜索查询时平衡女性/男性科学家的代表性时，这种组合结构变得更加复杂。这些组合问题在计算上具有挑战性，需要严格而快速的算法才能在必须实时做出决策的现实场景中有效地运行这些组合问题。学习应用中流行的一大类优化方法，即所谓的一阶优化方法，通过重复解决类似组合子问题的扰动来工作。 该研究项目将探讨一阶优化方法中“如何”计算先前子问题的解决方案的知识是否可用于加速后续迭代中的计算。如上所述，每当必须实时做出组合结构的约束决策时，该项目就有可能加速广泛的应用。这项工作的跨学科性质，涵盖一阶优化方法和组合算法，将有利于学生帮助培养一支更强大、更全面的 STEM 劳动力队伍，对本科生和研究生层面的大量应用产生影响。该项目作为正确集成一阶优化方法（例如 Frank-Wolfe (FW)、镜像下降 (MD) 及其变体）和具有广泛应用的组合优化理论的基石。它汇集了数据结构理论、近似算法、组合优化中的参数分析以及迭代一阶优化方法的计算要求，以实现整体运行时间的摊销加速。 MD 和 FW 变体仅依赖于每次迭代中单个数据点的函数值和梯度信息，这一特性使得这些方法可用于许多实时机器学习应用。当做出如上所述的约束组合决策时，这些方法重复计算两个主要子问题：（i）FW 变体的每次迭代中的线性优化，以及（ii）MD 变体的每次迭代中的投影或凸最小化。凭借该奖项，研究人员将探索（a）识别适合一阶方法中摊销分析的组合基元，（b）使用先前发现的紧密切割在镜像下降变体中进行迭代投影，（c）凸问题的分解， (d) 构建用于一阶优化的更智能的热启动解决方案，(e) 针对重复扰动子问题的较弱但相关的近似模型和算法。随着最近的结果缩小了各种设置中一阶优化的可能收敛率的差距，这些问题对于实现约束决策的运行时规模到实时以用户为中心的应用程序的下一次扩展变得至关重要。该奖项反映了 NSF 的法定使命，并通过使用基金会的智力价值和更广泛的影响审查标准进行评估，被认为值得支持。

项目成果

Walking in the Shadow: A New Perspective on Descent Directions for Constrained Minimization

行走在阴影中：约束最小化下降方向的新视角

• 发表时间: 2020-12
• 期刊: Advances in neural information processing systems
• 作者: Mortagy, H;Gupta, S;Pokutta, S
• 通讯作者: Pokutta, S

Reusing Combinatorial Structure: Faster Iterative Projections over Submodular Base Polytopes

重用组合结构：子模基多面体上的更快迭代投影

• 发表时间: 2021-12
• 期刊: Advances in neural information processing systems
• 作者: Moondra, J;Mortagy, H;Gupta, S
• 通讯作者: Gupta, S

Electrical flows over spanning trees

跨树上的电流

• DOI: 10.1007/s10107-020-01614-x
• 发表时间: 2021-02
• 期刊: Mathematical Programming
• 影响因子: 2.7
• 作者: Gupta, Swati;Khodabakhsh, Ali;Mortagy, Hassan;Nikolova, Evdokia
• 通讯作者: Nikolova, Evdokia