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

RI: Medium: Learning to Search: Provable Guarantees and Applications

RI：媒介：学习搜索：可证明的保证和应用

基本信息

批准号：
1901403
负责人：
Maria-Florina Balcan
金额：
$ 120万
依托单位：
Carnegie-Mellon University
依托单位国家：
美国
项目类别：
Standard Grant
财政年份：
2019
资助国家：
美国
起止时间：
2019-10-01 至 2024-09-30
项目状态：
已结题

来源：
https://www.nsf.gov/awardsearch/showAward?AWD_ID=1901403&HistoricalAwards=false
关键词：
RI Medium Learning Search Provable

项目摘要

AI and optimization are used in a wide range of scientific and business applications. Much of AI and optimization in turn are powered by search techniques such as branch and bound. These search techniques are used to intelligently explore a large number of possible solutions to a problem in order to come up with the best solution for the problem at hand. Unfortunately, in the worst case, their running time can be exponential, and much effort goes into the design of adjustable search strategies that can have a large effect on runtime, solution quality, or both. Tuning these strategies is typically done manually by experts. Recently there has been work on automated tuning of some variations of search, but these methods have not come with performance guarantees, and in general there is little theoretical understanding of what kinds of guarantees one might hope to achieve. The goal of this project is to provide new machine learning approaches with strong provable guarantees for customizing search techniques and automatically determining a nearly optimal search strategy for any given problem domain. This project aims to provide formal guarantees for its procedures as well as techniques that scale up to larger and more complex problems than currently possible. The algorithms and models developed in this research will be driven by, and applied to, optimization problems at the core of important real-world applications including kidney exchange and combinatorial auction design. These are domains where improved optimization procedures have significant impact. Specific goals in this project include: (1) Developing effective tree search strategies (including branch-and-bound methods) via machine learning that are widely applicable, scalable, and have strong provable guarantees. (2) Learning branching and node selection strategies together, and learning admissible heuristics for informed search techniques including A* search. (3) Applying algorithms developed to solve key challenges in two important application domains: Kidney Exchange and Automated Mechanism Design. (4) Learning how to branch in the context of decision-tree learning, an important machine learning paradigm, and in particular in the design of heuristics for top-down decision-tree induction. The project will impact artificial intelligence, optimization, machine learning, theory of computing, as well as many areas that require repeatedly solving hard optimization problems from a given domain. This includes kidney exchange and mechanism design which can have a broad impact across society and commerce. In addition to advising both graduate and undergraduate students on topics connected to this project, research progress will be integrated in the curricula of several courses at Carnegie-Mellon University and course materials will be made available on the web worldwide.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.

人工智能和优化被广泛应用于科学和商业应用。许多人工智能和优化反过来都是由分支和边界等搜索技术驱动的。这些搜索技术用于智能地探索问题的大量可能解决方案，以便为手头的问题提出最佳解决方案。不幸的是，在最坏的情况下，它们的运行时间可能呈指数级增长，并且需要花费大量精力设计可调整的搜索策略，这可能对运行时间、解决方案质量或两者都有很大影响。这些策略的调优通常由专家手动完成。最近已经有了一些关于自动调优某些搜索变体的工作，但是这些方法并没有提供性能保证，而且一般来说，对于希望实现哪种保证的理论理解很少。该项目的目标是提供新的机器学习方法，为定制搜索技术提供强大的可证明保证，并为任何给定的问题领域自动确定几乎最优的搜索策略。该项目旨在为其程序和技术提供正式的保证，以扩大规模，解决比目前可能解决的更大、更复杂的问题。本研究中开发的算法和模型将由重要现实世界应用的核心优化问题驱动并应用于优化问题，包括肾脏交换和组合拍卖设计。在这些领域中，改进的优化过程会产生重大影响。该项目的具体目标包括：(1)通过机器学习开发有效的树搜索策略（包括分支定界方法），这些策略广泛适用，可扩展，并且具有强大的可证明保证。(2)共同学习分支和节点选择策略，学习包括A*搜索在内的知情搜索技术的可接受启发式。(3)应用算法解决肾脏交换和自动化机制设计两个重要应用领域的关键挑战。(4)学习如何在决策树学习（一种重要的机器学习范式）的背景下进行分支，特别是在自上而下决策树归纳的启发式设计中。该项目将影响人工智能、优化、机器学习、计算理论，以及许多需要从给定领域反复解决困难优化问题的领域。这包括肾脏交换和机制设计，可以对整个社会和商业产生广泛的影响。除了就与该项目相关的主题向研究生和本科生提供建议外，研究进展还将整合到卡内基梅隆大学的几门课程的课程中，课程材料将在全球范围内的网络上提供。该奖项反映了美国国家科学基金会的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。

项目成果

期刊论文数量（96）

专著数量（0）

科研奖励数量（0）

会议论文数量（0）

专利数量（0）

Learning Predictions for Algorithms with Predictions

通过预测来学习算法的预测

DOI：
发表时间：
2022
期刊：
Advances in Neural Information Processing Systems
影响因子：
0
作者：
Khodak, Mikhail;Balcan, Maria Florina;Talwalkar, Ameet;Vassilvitskii, Sergei
通讯作者：
Vassilvitskii, Sergei

Efficient Decentralized Learning Dynamics for Extensive-Form Coarse Correlated Equilibrium: No Expensive Computation of Stationary Distributions Required

用于扩展形式粗相关均衡的高效分散学习动态：不需要昂贵的平稳分布计算