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

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

基本信息

批准号：
1955785
负责人：
Anupam Gupta
金额：
$ 60万
依托单位：
Carnegie-Mellon University
依托单位国家：
美国
项目类别：
Continuing Grant
财政年份：
2020
资助国家：
美国
起止时间：
2020-05-01 至 2024-04-30
项目状态：
已结题

来源：
https://www.nsf.gov/awardsearch/showAward?AWD_ID=1955785&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 的法定使命，并被认为值得支持通过使用基金会的智力优点和更广泛的影响审查标准进行评估。