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

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

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.