Collaborative Research: AF: Medium: Algorithms Meet Machine Learning: Mitigating Uncertainty in Optimization

协作研究：AF：媒介：算法遇见机器学习：减轻优化中的不确定性

基本信息

批准号：
1955703
负责人：
Debmalya Panigrahi
金额：
$ 61.57万
依托单位：
Duke University
依托单位国家：
美国
项目类别：
Continuing Grant
财政年份：
2020
资助国家：
美国
起止时间：
2020-05-01 至 2025-04-30
项目状态：
未结题

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

项目摘要

Algorithmic decision-making is ubiquitous in the modern era. Our society uses algorithms to solve problems ranging from making investment decisions in personal financial planning, to allocating resources in large-scale computing systems such as data centers. Often, these problems are difficult because of uncertainty about the future. In algorithmic theory, traditionally conservative approaches are used which provide relatively weak but highly robust guarantees that hold no matter how the future unfolds. In practice, a more promising alternative is the use of machine-learning techniques to make algorithmic choices for the future based on knowledge of past data. By implicitly assuming that the future will mirror the past, one can provide stronger guarantees and better empirical performance. However, the "worst-case" robustness of the previous approach is not available, which is important if the implicit assumption of 'past predicts the future' no longer holds true. This project seeks to combine the two approaches and get the best of both worlds by exploring the interface between algorithm design and machine learning. The end goal is a comprehensive toolbox for algorithmic decision-making under uncertainty that is both robust and has good performance. In addition to this research component, the project will train graduate and undergraduate researchers in theoretical computer science, with an emphasis on participation of underrepresented groups.The investigators' approach is to rethink each of these individual toolboxes to take advantage of the other -- namely incorporating machine-learned advice in algorithm design, and conversely, training machine learning models for algorithmic objectives. The main intellectual thrust of this project is to use machine-learned predictions to improve the quality of algorithms, and conversely, to design learning models that can be specifically trained for optimization objectives. This will be explored in two main directions: the first part considers Machine Learning as a Black Box. Here, the optimization algorithm merely consumes the predictions from the learning model. This is often the case in practice, particularly when the predictions are generated by complex systems such as deep neural networks. In this case, the focus will be on ensuring that we do not over-fit the predictions, on deciding what input parameters to predict in the first place, and on choosing between multiple alternative prediction models based on their relative accuracy, reliability, and costs. In the second part (Machine Learning as a White Box), the focus is on a more integrated design, where the optimization algorithm interacts with the learning model at runtime and ask adaptives queries. More ambitiously, the project explores a significant redesign of the end-to-end system, including the learning models and the optimization algorithms, for specific optimization tasks. This work will rely on techniques from online algorithms, stochastic and robust optimization, and learning theory, and build connections between these fields to address the central questions of algorithmic decision making under uncertainty.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.

算法决策在现代时代无处不在。我们的社会使用算法来解决从个人财务计划中的投资决策到在大规模计算系统（例如数据中心）中的资源等问题。通常，由于对未来的不确定性，这些问题很困难。在算法理论中，使用传统上保守的方法，这些方法可提供相对较弱但高度强大的保证，无论未来如何发展，都可以保证。实际上，一个更有希望的替代方法是使用机器学习技术根据过去数据的知识为未来做出算法选择。通过隐式假设未来会反映过去，人们可以提供更强大的保证和更好的经验绩效。但是，先前方法的“最坏”鲁棒性不可用，这很重要，如果“过去预测未来”的隐含假设不再是正确的。该项目旨在结合两种方法，并通过探索算法设计和机器学习之间的界面来获得两全其美。最终目标是在不确定性下进行算法决策制定的全面工具箱，既强大又具有良好的性能。除了该研究组件外，该项目还将培训理论计算机科学领域的毕业生和本科研究人员，重点是参与代表性不足的组。研究人员的方法是重新考虑这些单独的工具箱，以利用其他工具箱 - 即将机器学习的建议纳入算法设计中，相反，训练机器学习模型为算法目标。该项目的主要智力推力是使用机器学习的预测来提高算法的质量，相反，设计可以专门培训以进行优化目标的学习模型。这将在两个主要方向上进行探讨：第一部分将机器学习视为黑匣子。在这里，优化算法仅消耗学习模型中的预测。在实践中通常是这种情况，尤其是当预测是由复杂系统（例如深神经网络）产生的。在这种情况下，重点将是确保我们不要过度拟合预测，决定首先要预测的输入参数，并根据其相对准确性，可靠性和成本在多个替代预测模型之间进行选择。在第二部分中（机器学习为白框），重点是更集成的设计，在此期间，优化算法在运行时与学习模型相互作用并询问自适应剂查询。该项目更加雄心勃勃地探讨了端到端系统的重大重新设计，包括学习模型和优化算法，用于特定的优化任务。这项工作将依靠在线算法，随机和强大的优化以及学习理论以及在这些领域之间建立联系以解决不确定性下算法决策的主要问题。该奖项反映了NSF的法定任务，并被认为是值得支持的支持，通过使用基金会的智力优点和更广泛影响的评论标准进行评估。

项目成果

期刊论文数量（16）

专著数量（0）

科研奖励数量（0）

会议论文数量（0）

专利数量（0）

Online Combinatorial Auctions

在线组合拍卖

DOI：
10.1137/1.9781611976465.70
发表时间：
2021
期刊：
Proceedings of the annual ACMSIAM symposium on discrete algorithms
影响因子：
0
作者：
Deng, Yuan;Panigrahi, Debmalya;Zhang, Hanrui
通讯作者：
Zhang, Hanrui

Online Graph Algorithms with Predictions

DOI：
10.1137/1.9781611977073.3
发表时间：
2021-12
期刊：
ArXiv
影响因子：
0
作者：
Y. Azar;Debmalya Panigrahi;Noam Touitou
通讯作者：
Y. Azar;Debmalya Panigrahi;Noam Touitou

Online Paging with Heterogeneous Cache Slots

DOI：
10.48550/arxiv.2206.05579
发表时间：
2022-06
期刊：
ArXiv
影响因子：
0
作者：
M. Chrobak;Samuel Haney;Mehraneh Liaee;Debmalya Panigrahi;R. Rajaraman;Ravi Sundaram;N. Young
通讯作者：
M. Chrobak;Samuel Haney;Mehraneh Liaee;Debmalya Panigrahi;R. Rajaraman;Ravi Sundaram;N. Young

Customizing ML Predictions for Online Algorithms