用预测提升算法性能，同时保证严格可靠性。
Learning-Augmented Algorithms: Guarantees, Construction Mechanisms, and System-Level Implications
- 设计五种构建方法，融合预测与确定性保障
- 明确预测误差与算法性能的权衡关系
- 适合关注算法鲁棒性与实际系统落地的研究者
学习增强型算法在使用有缺陷的预测的同时，仍能保持形式化的性能保证。本综述整合了预测接口、误差度量、一致性和鲁棒性的权衡关系，以及在线优化、缓存、学习数据结构、图问题和机制设计中的五类代表性构造机制。通过一个正交的理论层面维度，区分了达到的上界与匹配的渐近依赖关系。形式化保证与实证系统证据被明确分离，并对预测代价、反馈机制和组合性进行了详尽处理。由此形成的综合框架给出了有限端到端推理的充分条件，并指出了成本感知预测、内生误差、语义预测器和基准测试等开放问题。
原文摘要 · Abstract (English)
Learning-augmented algorithms use fallible predictions while retaining formal performance guarantees. This survey synthesizes prediction interfaces, error measures, consistency--robustness trade-offs, and five representative construction mechanisms across online optimization, caching, learned data structures, graph problems, and mechanism design. An orthogonal theorem-level axis distinguishes achieved upper bounds from matched asymptotic dependence. Formal guarantees are separated from empirical systems evidence, with explicit treatment of prediction cost, feedback, and composition. The resulting synthesis states sufficient conditions for limited end-to-end reasoning and delineates open problems in cost-aware prediction, endogenous error, semantic predictors, and benchmarking.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。