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

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

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.