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

Collaborative Research: AF: Small: Foundations of Algorithms Augmented with Predictions

合作研究：AF：小型：预测增强的算法基础

基本信息

批准号：
2121745
负责人：
Sungjin Im
金额：
$ 25万
依托单位：
University of California - Merced
依托单位国家：
美国
项目类别：
Standard Grant
财政年份：
2022
资助国家：
美国
起止时间：
2022-01-01 至 2024-12-31
项目状态：
已结题

来源：
https://www.nsf.gov/awardsearch/showAward?AWD_ID=2121745&HistoricalAwards=false
关键词：
Collaborative Research AF Small Foundations

项目摘要

The ability to process and use information to make better decisions is driving breakthroughs in science and engineering, and they are being materialized in business. Machine learning is one of the central forces behind such revolutionary progress. For example, machine learning is often used to make predictions for uncertain information such as traffic in a road network or consumer demand for an online business. Unfortunately, machine learning is imperfect and commonly error-prone. The goal of this project is to design efficient decision-making algorithms that result in solutions that are both high-quality and robust to error in the predictions. The investigators of this project will organize a workshop to disseminate research findings to the community. The research will be incorporated into courses and the investigators will develop an undergraduate degree program on the intersection of business and machine learning. This project will develop the foundations of augmenting decision-making algorithms with error-prone machine-learned predictions. The project’s goal is to develop algorithms that break through worst-case analysis barriers with high-quality predictions and have graceful degradation in quality as the error in the predictions grows. The algorithms developed will use predictions to improve the worst-case running time and better cope with uncertainties in the future input. The predictions used will be grounded in computational learning theory and be shown to be efficiently learnable. The project has the following goals. The project will (1) investigate using predictions to improve the running time of algorithms for problems of fundamental importance such as matchings and flows; (2) use predictions to give algorithms information about uncertain inputs for online problems and investigate various measures to better gauge the prediction quality; and (3) develop a theory for which parameters can be efficiently learned.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）使用预测为算法提供有关在线问题的不确定输入的信息，并研究各种措施以更好地衡量预测质量;以及（3）开发一种可以有效学习参数的理论。该奖项反映了NSF的法定使命，并被认为值得通过使用基金会的智力价值进行评估来支持和更广泛的影响审查标准。

项目成果

期刊论文数量（8）

专著数量（0）

科研奖励数量（0）

会议论文数量（0）

专利数量（0）

Almost Tight Approximation Hardness for Single-Source Directed k-Edge-Connectivity

单源定向 k 边连接的近乎严格的近似硬度

DOI：
发表时间：
2022
期刊：
and Programming
影响因子：
0
作者：
Liao, Chao;Chen, Qingyun;Laekhanukit, Bundit;Zhang, Yuhao
通讯作者：
Zhang, Yuhao

Online Learning and Bandits with Queried Hints

DOI：
10.48550/arxiv.2211.02703
发表时间：
2022-11
期刊：
影响因子：
0
作者：
Aditya Bhaskara;Sreenivas Gollapudi;Sungjin Im;Kostas Kollias;Kamesh Munagala
通讯作者：
Aditya Bhaskara;Sreenivas Gollapudi;Sungjin Im;Kostas Kollias;Kamesh Munagala

Min-Max Submodular Ranking for Multiple Agents

多个智能体的最小-最大子模排序

DOI：
发表时间：
2023
期刊：
Proceedings of the AAAI Conference on Artificial Intelligence
影响因子：
0
作者：
Chen, Q.;Im, S.;Moseley, B.;Xu, C.;Zhang, R.
通讯作者：
Zhang, R.

Online State Exploration: Competitive Worst Case and Learning-Augmented Algorithms

在线状态探索：竞争最坏情况和学习增强算法

DOI：
发表时间：
2023
期刊：
Machine Learning and Knowledge Discovery in Databases
影响因子：
0
作者：
Im, Sungjin;Moseley, Benjamin;Xu, Chenyang;Zhang, Ruilong
通讯作者：
Zhang, Ruilong

Algorithms with Prediction Portfolios

具有预测投资组合的算法

DOI：
发表时间：
2022
期刊：
Advances in neural information processing systems
影响因子：
0
作者：
Dinitz, Michael;Im, Sungjin;Lavastida, Thomas;Moseley, Benjamin;Vassilvitskii, Sergei
通讯作者：
Vassilvitskii, Sergei