AF: Small: Algorithms and Data Structures with Predictions

该项目的目标是通过使用预测，例如从机器学习方法中获得的预测，为现实世界的问题开发改进的算法和数据结构。传统标准算法基于最坏情况性能进行分析；一种是考虑在最坏的输入上最坏的运行时间。如果给算法提供合适的提示或预测，例如来自确定输入属性的扫描器，它可能能够在实践中避免最坏的情况。例如，如果一个算法可以预测人们何时排队等待服务，谁只需要很短的时间，谁需要很长的时间，它就可以命令排队的人加快服务的速度，避免出现一个人挡住了整个排队等待的人的情况。鉴于机器学习技术的普遍成功，将机器学习预测纳入标准算法框架可能会在现实世界的性能方面产生重要的收益，同时仍然提供严格的性能保证。该项目的其他组成部分包括开发材料，使这项研究的结果可以纳入计算机科学课程，将学生的工作纳入研究，并通过扩大教育和研究机会来培养下一代研究人员，从而扩大对计算机的参与。标准算法和数据结构分析是基于最坏情况的性能。使用额外的信息，比如机器学习方法的预测，来改进那些可以严格证明的性能，这一想法只得到了很少的研究。确定如何使用这些附加信息提供了一种通常被称为超越最坏情况分析的新方法，它力求将算法分析扩展到传统的最坏情况方法之外。最终目标是提供框架，利用机器学习的力量，根据输入数据提供良好的预测，同时保持传统算法的鲁棒性和理论保证的优势。特别是，即使预测是错误的，表现也应该是可以理解和接受的；例如，在某些设置中，目标可能是在使用预测时，即使预测是反向提供的，性能也不应该差太多。这一研究领域旨在揭示长期存在的算法和数据结构的新亮点，同时也需要开发新的分析技术。研究者认为，这种形式的算法和数据结构很可能在现实世界的系统中无处不在，因此，对它们的理论理解对于描述它们的风险和回报是重要的。该奖项反映了美国国家科学基金会的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。

The goal of this project is to develop improved algorithms and data structures for real-world problems by making use of predictions, such as predictions obtained from machine-learning methods. Traditional standard algorithms are analyzed based on worst-case performance; one considers the worst possible running time on the worst possible input. If an algorithm is given a suitable hint, or prediction, such as from a scanner that determines properties of the input, it may be able to avoid the worst case in practice. For example, if an algorithm could predict when people were waiting in line for service who would only need a small amount of time and who would need a long amount of time, it could order people in line to speed up how quickly people were served, avoiding situations where one person held up the entire line of waiting people. Given the general success of machine-learning techniques, bringing machine-learning predictions into standard algorithmic frameworks may yield important gains in real-world performance, while still providing rigorous performance guarantees. Additional components of this project involve developing materials so that the results of this research can be included in computer science courses, incorporating student work in the research, and broadening participation in computing through expanding educational and research opportunities for developing the next generation of researchers.Standard algorithms and data-structure analysis is based on worst-case performance. The idea of using additional information, such as predictions from machine-learning methods, to improve what can be rigorously proved about performance has been only very sparsely studied. Determining how to use such additional information provides a new method of what is commonly called beyond worst-case analysis, which strives to expand algorithmic analysis beyond the traditional worst-case methods. The ultimate goal is to provide frameworks that take advantage of the power of machine learning to provide good predictions based on the input data, while maintaining the advantages of the robustness and theoretical guarantees available from traditional algorithms. In particular, performance should still remain understandable and acceptable even if predictions are wrong; for example, in some settings, a goal could be that performance should never be much worse when using predictions, even if the predictions are provided adversarially. This area of study is intended to shed new light on long-existing algorithms and data structures, as well as require development of new analysis techniques. The investigator believes that algorithms and data structures of this form are likely to become ubiquitous in real-world systems, and thus theoretical understanding of them is important to characterize their risks and rewards.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.