CRII: AF: Faster Iterative Decisions within First-order Optimization Methods
CRII:AF:一阶优化方法中更快的迭代决策
基本信息
- 批准号:1850182
- 负责人:
- 金额:$ 17.5万
- 依托单位:
- 依托单位国家:美国
- 项目类别:Standard Grant
- 财政年份:2019
- 资助国家:美国
- 起止时间:2019-06-01 至 2022-05-31
- 项目状态:已结题
- 来源:
- 关键词:
项目摘要
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的法定使命,并已被认为是值得的支持,通过评估使用基金会的智力价值和更广泛的影响审查标准。
项目成果
期刊论文数量(3)
专著数量(0)
科研奖励数量(0)
会议论文数量(0)
专利数量(0)
Reusing Combinatorial Structure: Faster Iterative Projections over Submodular Base Polytopes
重用组合结构:子模基多面体上的更快迭代投影
- DOI:
- 发表时间:2021
- 期刊:
- 影响因子:0
- 作者:Moondra, J;Mortagy, H;Gupta, S
- 通讯作者:Gupta, S
Walking in the Shadow: A New Perspective on Descent Directions for Constrained Minimization
行走在阴影中:约束最小化下降方向的新视角
- DOI:
- 发表时间:2020
- 期刊:
- 影响因子:0
- 作者:Mortagy, H;Gupta, S;Pokutta, S
- 通讯作者:Pokutta, S
Electrical flows over spanning trees
跨树上的电流
- DOI:10.1007/s10107-020-01614-x
- 发表时间:2021
- 期刊:
- 影响因子:2.7
- 作者:Gupta, Swati;Khodabakhsh, Ali;Mortagy, Hassan;Nikolova, Evdokia
- 通讯作者:Nikolova, Evdokia
{{
item.title }}
{{ item.translation_title }}
- DOI:
{{ item.doi }} - 发表时间:
{{ item.publish_year }} - 期刊:
- 影响因子:{{ item.factor }}
- 作者:
{{ item.authors }} - 通讯作者:
{{ item.author }}
数据更新时间:{{ journalArticles.updateTime }}
{{ item.title }}
- 作者:
{{ item.author }}
数据更新时间:{{ monograph.updateTime }}
{{ item.title }}
- 作者:
{{ item.author }}
数据更新时间:{{ sciAawards.updateTime }}
{{ item.title }}
- 作者:
{{ item.author }}
数据更新时间:{{ conferencePapers.updateTime }}
{{ item.title }}
- 作者:
{{ item.author }}
数据更新时间:{{ patent.updateTime }}
Swati Gupta其他文献
Hydroxamic Acid Derivatives as Potential Anticancer Agents
异羟肟酸衍生物作为潜在的抗癌剂
- DOI:
- 发表时间:
2013 - 期刊:
- 影响因子:0
- 作者:
M. Gupta;Gagandip Singh;Swati Gupta - 通讯作者:
Swati Gupta
EFFICACY AND SAFETY OF PHOTOTHERAPY IN TREATING PITYRIASIS LICHENOIDES CHRONICA IN PAEDIATRIC PATIENTS
光疗治疗儿童慢性苔藓样糠疹的疗效和安全性
- DOI:
10.36106/ijsr/9401836 - 发表时间:
2021 - 期刊:
- 影响因子:0
- 作者:
Swati Gupta;C. Namdeo;K. Bhatia - 通讯作者:
K. Bhatia
Therapeutic Role of Peroxisome Proliferator-Activated Receptors Gamma in the Treatment of Fibrosis
过氧化物酶体增殖物激活受体γ在纤维化治疗中的治疗作用
- DOI:
10.7439/ijbr.v7i6.3390 - 发表时间:
2016 - 期刊:
- 影响因子:0
- 作者:
G. Tripathi;Swati Gupta - 通讯作者:
Swati Gupta
Scalable Robust and Adaptive Inventory Routing
可扩展的稳健和自适应库存路由
- DOI:
- 发表时间:
2016 - 期刊:
- 影响因子:0
- 作者:
D. Bertsimas;Swati Gupta;J. Tay - 通讯作者:
J. Tay
Effect of Mitomycin-C Inactivation on Expression Pattern of Pluripotency Related Transcriptional Factors in Buffalo Fetal Fibroblasts and Wharton's Jelly
丝裂霉素-C 灭活对水牛胎儿成纤维细胞和沃顿胶中多能性相关转录因子表达模式的影响
- DOI:
10.5958/2277-940x.2015.00071.6 - 发表时间:
2015 - 期刊:
- 影响因子:0
- 作者:
M. S. Parmar;Swati Gupta;A. Somal;S. Pandey;V. Chandra;G. Sharma - 通讯作者:
G. Sharma
Swati Gupta的其他文献
{{
item.title }}
{{ item.translation_title }}
- DOI:
{{ item.doi }} - 发表时间:
{{ item.publish_year }} - 期刊:
- 影响因子:{{ item.factor }}
- 作者:
{{ item.authors }} - 通讯作者:
{{ item.author }}
{{ truncateString('Swati Gupta', 18)}}的其他基金
CAREER: Advancing Equity in Selection Problems Through Bias-Aware Optimization
职业:通过偏差感知优化促进选择问题的公平性
- 批准号:
2239824 - 财政年份:2023
- 资助金额:
$ 17.5万 - 项目类别:
Standard Grant
相似国自然基金
基于前瞻性队列的双酚AF联合果糖加重代谢损伤的靶向代谢组学研究
- 批准号:2025JJ30049
- 批准年份:2025
- 资助金额:0.0 万元
- 项目类别:省市级项目
U2AF2-circMMP1信号轴促进结直肠癌进展的分子机制研究
- 批准号:2025JJ80723
- 批准年份:2025
- 资助金额:0.0 万元
- 项目类别:省市级项目
U2AF2精氯酸甲基化调控RNA转录合成在MTAP缺失骨肉瘤T细胞耗竭中的机制研究
- 批准号:
- 批准年份:2024
- 资助金额:0 万元
- 项目类别:青年科学基金项目
BDA-366通过MYD88/NF-κB/PGC1β通路杀伤 KMT2A/AF9 AML细胞的机制研究
- 批准号:
- 批准年份:2024
- 资助金额:15.0 万元
- 项目类别:省市级项目
Lu AF21934减少缺血性脑卒中导致的神经损伤的机制研究
- 批准号:
- 批准年份:2024
- 资助金额:0.0 万元
- 项目类别:省市级项目
H2S介导剪接因子BraU2AF65a的S-巯基化修饰促进大白菜开花的分子机制
- 批准号:32372727
- 批准年份:2023
- 资助金额:50 万元
- 项目类别:面上项目
AF9通过ARRB2-MRGPRB2介导肠固有肥大细胞活化促进重症急性胰腺炎发生MOF的研究
- 批准号:82300739
- 批准年份:2023
- 资助金额:30 万元
- 项目类别:青年科学基金项目
剪接因子U2AF1突变在急性髓系白血病原发耐药中的机制研究
- 批准号:82370157
- 批准年份:2023
- 资助金额:49 万元
- 项目类别:面上项目
线粒体活性氧介导的胎盘早衰在孕期双酚AF暴露致婴幼儿神经发育迟缓中的作用
- 批准号:82304160
- 批准年份:2023
- 资助金额:30 万元
- 项目类别:青年科学基金项目
U2AF2-circMMP1调控能量代谢促进结直肠癌肝转移的分子机制
- 批准号:82303789
- 批准年份:2023
- 资助金额:30 万元
- 项目类别:青年科学基金项目
相似海外基金
CRII: AF: Efficiently Computing and Updating Topological Descriptors for Data Analysis
CRII:AF:高效计算和更新数据分析的拓扑描述符
- 批准号:
2348238 - 财政年份:2024
- 资助金额:
$ 17.5万 - 项目类别:
Standard Grant
CRII: AF: The Impact of Knowledge on the Performance of Distributed Algorithms
CRII:AF:知识对分布式算法性能的影响
- 批准号:
2348346 - 财政年份:2024
- 资助金额:
$ 17.5万 - 项目类别:
Standard Grant
CRII: AF: Streaming Approximability of Maximum Directed Cut and other Constraint Satisfaction Problems
CRII:AF:最大定向切割和其他约束满足问题的流近似性
- 批准号:
2348475 - 财政年份:2024
- 资助金额:
$ 17.5万 - 项目类别:
Standard Grant
Collaborative Research: AF: Medium: The Communication Cost of Distributed Computation
合作研究:AF:媒介:分布式计算的通信成本
- 批准号:
2402836 - 财政年份:2024
- 资助金额:
$ 17.5万 - 项目类别:
Continuing Grant
Collaborative Research: AF: Medium: Foundations of Oblivious Reconfigurable Networks
合作研究:AF:媒介:遗忘可重构网络的基础
- 批准号:
2402851 - 财政年份:2024
- 资助金额:
$ 17.5万 - 项目类别:
Continuing Grant
AF: Small: Problems in Algorithmic Game Theory for Online Markets
AF:小:在线市场的算法博弈论问题
- 批准号:
2332922 - 财政年份:2024
- 资助金额:
$ 17.5万 - 项目类别:
Standard Grant
Collaborative Research: AF: Small: New Directions in Algorithmic Replicability
合作研究:AF:小:算法可复制性的新方向
- 批准号:
2342244 - 财政年份:2024
- 资助金额:
$ 17.5万 - 项目类别:
Standard Grant
Collaborative Research: AF: Small: Exploring the Frontiers of Adversarial Robustness
合作研究:AF:小型:探索对抗鲁棒性的前沿
- 批准号:
2335411 - 财政年份:2024
- 资助金额:
$ 17.5万 - 项目类别:
Standard Grant
NSF-BSF: Collaborative Research: AF: Small: Algorithmic Performance through History Independence
NSF-BSF:协作研究:AF:小型:通过历史独立性实现算法性能
- 批准号:
2420942 - 财政年份:2024
- 资助金额:
$ 17.5万 - 项目类别:
Standard Grant
Collaborative Research: AF: Medium: Algorithms Meet Machine Learning: Mitigating Uncertainty in Optimization
协作研究:AF:媒介:算法遇见机器学习:减轻优化中的不确定性
- 批准号:
2422926 - 财政年份:2024
- 资助金额:
$ 17.5万 - 项目类别:
Continuing Grant