权益分类	功能权益	普通用户	{{item.name}}会员
{{category.name}}	{{benefitItem.name}}

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.

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