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

处理和使用信息以做出更好决策的能力正在推动科学和工程方面的突破，这些突破正在商业中实现。机器学习是这种革命性进步背后的核心力量之一。例如，机器学习经常被用来预测不确定的信息，如道路网络中的交通或消费者对在线业务的需求。不幸的是，机器学习并不完美，而且通常容易出错。该项目的目标是设计有效的决策算法，以产生既高质量又对预测误差具有健壮性的解决方案。该项目的研究人员将组织一次工作坊，向社会传播研究成果。这项研究将被纳入课程，研究人员将开发一个关于商业和机器学习交集的本科学位课程。这个项目将为使用容易出错的机器学习预测来增强决策算法奠定基础。该项目的目标是开发算法，以高质量的预测突破最坏情况的分析障碍，并随着预测误差的增加而优雅地降低质量。开发的算法将使用预测来改善最坏情况下的运行时间，并更好地应对未来输入中的不确定性。所使用的预测将以计算学习理论为基础，并被证明是可有效学习的。该项目有以下目标。该项目将(1)调查使用预测来改善算法对基本重要问题(如匹配和流动)的运行时间；(2)使用预测为算法提供有关在线问题的不确定输入的信息，并调查各种措施以更好地衡量预测质量；以及(3)开发一种可以有效学习参数的理论。该奖项反映了NSF的法定使命，并通过使用基金会的智力优势和更广泛的影响审查标准进行评估，被认为值得支持。

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.