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劳动力，并在大量应用中产生影响。与广泛应用的组合优化。它汇集了数据结构的理论，近似算法，组合优化中的参数分析以及迭代一阶优化方法的计算要求，以实现整体运行时的摊销速度UPS。 MD和FW变体仅依赖于每个迭代中一个数据点的函数值和梯度信息，并且该属性已渲染这些方法以在众多实时机器学习应用程序中使用。如上所述，在做出约束的组合决策时，这些方法反复计算两个主要子问题：（i）在FW变体的每种迭代中进行线性优化，以及（ii）MD变体的每种迭代中的投影或最小化。 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子问题。随着最近的结果缩小了在各种环境中一阶优化的可能收敛速率的差距，这些问题至关重要，这对于实时决策的运行时间与实时用户为中心的应用程序的运行时间变得至关重要。该奖项反映了NSF的法规任务，并认为通过基金会的知识优点和广泛的critia criter scritia crietia criter critia criter scritia criter critia critia critia criter critia critia criter critia critia critia critia critia critia critia criter critia criter critia crietia均值得一提。