arXiv:2509.05930cs.LGcs.SY2025-09

提出新框架SOOTT,兼顾追踪、抗扰与平滑决策。

Smoothed Online Optimization for Target Tracking: Robust and Learning-Augmented Algorithms

  • 融合追踪、抗扰与平滑三目标的在线优化框架
  • 算法在真实负载调度中实现轨迹跟踪与鲁棒性平衡
  • 可融入不可靠预测,提升性能且不失鲁棒性

我们提出面向目标追踪的平滑在线优化(SOOTT)问题,整合三项核心目标:跟踪成本(跟随动态目标)、对抗扰动成本(抵御突发干扰)和切换成本(惩罚决策突变)。该框架适用于人工智能集群中的弹性/非弹性负载调度场景,需在长期服务协议(如大模型训练)与突发需求高峰(如实时推理)间取得平衡。我们首先提出BEST算法,具备可证明的竞争力保证。为进一步提升实际表现,提出学习增强型算法CoRT,可融合来自机器学习模型的不可信黑盒预测。理论分析表明,当预测准确时CoRT严格优于BEST,且在任意预测误差下仍保持鲁棒性。通过负载调度案例研究验证,两类算法均能有效平衡轨迹追踪、决策平滑性与外部扰动抵御能力。

原文摘要 · Abstract (English)

We introduce the Smoothed Online Optimization for Target Tracking (SOOTT) problem, a new framework that integrates three key objectives in online decision-making under uncertainty: (1) tracking cost for following a dynamically moving target, (2) adversarial perturbation cost for withstanding unpredictable disturbances, and (3) switching cost for penalizing abrupt changes in decisions. This formulation captures real-world scenarios such as elastic and inelastic workload scheduling in AI clusters, where operators must balance long-term service-level agreements (e.g., LLM training) against sudden demand spikes (e.g., real-time inference). We first present BEST, a robust algorithm with provable competitive guarantees for SOOTT. To enhance practical performance, we introduce CoRT, a learning-augmented variant that incorporates untrusted black-box predictions (e.g., from ML models) into its decision process. Our theoretical analysis shows that CoRT strictly improves over BEST when predictions are accurate, while maintaining robustness under arbitrary prediction errors. We validate our approach through a case study on workload scheduling, demonstrating that both algorithms effectively balance trajectory tracking, decision smoothness, and resilience to external disturbances.

在线优化目标追踪学习增强负载调度

Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。