揭示学习增强算法中一致性、鲁棒性与平滑性间的多重权衡关系
On Tradeoffs in Learning-Augmented Algorithms
- 发现学习增强算法存在多重权衡，不能同时优化所有性能指标
- 在分布信息已知时，平均表现与鲁棒性难以兼顾
- 为算法设计提供新视角，适合关注理论边界的研究者
学习增强算法近年来受到广泛关注。这类算法利用可能不准确的预测，必须具备一致性、鲁棒性和平滑性三个关键特性。在已知预测分布信息的场景下，要求算法具有良好的期望性能。通常，算法设计需在一致性和鲁棒性之间进行自然权衡，先前工作致力于实现特定问题的帕累托最优权衡。然而，在某些设置中，这会牺牲平滑性。本文表明，某些问题中存在一致性、鲁棒性、平滑性与平均性能之间的多重权衡。
原文摘要 · Abstract (English)
The field of learning-augmented algorithms has gained significant attention in recent years. These algorithms, using potentially inaccurate predictions, must exhibit three key properties: consistency, robustness, and smoothness. In scenarios where distributional information about predictions is available, a strong expected performance is required. Typically, the design of these algorithms involves a natural tradeoff between consistency and robustness, and previous works aimed to achieve Pareto-optimal tradeoffs for specific problems. However, in some settings, this comes at the expense of smoothness. This paper demonstrates that certain problems involve multiple tradeoffs between consistency, robustness, smoothness, and average performance.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。