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

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

• 批准号: 2422926
• 负责人: Anupam Gupta
• 金额: $ 60万
• 依托单位: New York University
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2024
• 资助国家: 美国
• 起止时间: 2024-01-01 至 2025-04-30
• 项目状态: 未结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=2422926&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的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。