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的法定使命，并被认为是值得通过基金会的知识分子和更广泛影响的评论标准来评估值得支持的。

项目成果

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

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

• 发表时间: 2022
• 期刊: and Programming
• 作者: 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
• 作者: Aditya Bhaskara;Sreenivas Gollapudi;Sungjin Im;Kostas Kollias;Kamesh Munagala

Min-Max Submodular Ranking for Multiple Agents

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

• 发表时间: 2023
• 期刊: Proceedings of the AAAI Conference on Artificial Intelligence
• 作者: Chen, Q.;Im, S.;Moseley, B.;Xu, C.;Zhang, R.
• 通讯作者: Zhang, R.

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

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

• 发表时间: 2023
• 期刊: Machine Learning and Knowledge Discovery in Databases
• 作者: Im, Sungjin;Moseley, Benjamin;Xu, Chenyang;Zhang, Ruilong
• 通讯作者: Zhang, Ruilong

Algorithms with Prediction Portfolios

具有预测投资组合的算法

• 发表时间: 2022
• 期刊: Advances in neural information processing systems
• 作者: Dinitz, Michael;Im, Sungjin;Lavastida, Thomas;Moseley, Benjamin;Vassilvitskii, Sergei
• 通讯作者: Vassilvitskii, Sergei