Smoothed Online Optimization for Target Tracking: Robust and Learning-Augmented Algorithms
This work addresses the challenge of balancing long-term and sudden demands in AI cluster scheduling, representing an incremental advance in online optimization methods.
The paper tackles the problem of online decision-making under uncertainty by introducing the Smoothed Online Optimization for Target Tracking (SOOTT) framework, which integrates tracking, adversarial perturbation, and switching costs, and presents robust and learning-augmented algorithms that improve performance in workload scheduling scenarios.
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.