Learning-Augmented Online Minimization with Dual Predictions

We present learning-augmented algorithms for two general classes of online minimization problems: metrical task systems and laminar set cover. Both algorithms achieve improved theoretical guarantees using machine-learned predictions of an optimal solution to the dual linear program. Unlike optimal primal solutions, which can change drastically under tiny instance perturbations, these dual solutions are much more stable, which ensures the existence of good (and learnable) predictions for families of similar instances. While previous work has used dual predictions in offline settings and for online maximization problems, our algorithms are, to the best of our knowledge, the first demonstration that such dual predictions can be effective for online minimization. Our theoretical results are complemented by experiments on the $k$-server problem and the parking permit problem.

We study how machine learning can help algorithms make good decisions when the future is uncertain. We focus on two settings. One involves repeatedly choosing a state, location, or mode of operation, where changing the choice incurs a cost but staying put in a non-ideal position may also become expensive over time. The other involves buying from a hierarchy of options, such as daily, weekly, or monthly permits, to meet certain demands. The key idea is to use machine-learned predictions not of the final decisions the algorithm should make, but of a more stable mathematical object called a dual solution. Final decisions can be very sensitive: a tiny change in the input may completely change the best solution. Dual solutions, by contrast, tend to vary more smoothly across similar problem instances, making them easier to predict reliably. Using such predictions, we design online algorithms with stronger theoretical guarantees than standard worst-case algorithms when the predictions are good, while still retaining robustness when they are imperfect. While previous uses of dual predictions were mainly for offline problems or online maximization problems, we show that dual predictions can also be useful for online minimization problems, where the goal is to keep costs low over time. We support our theoretical results with a brief experimental section on two classic examples: the $k$-server problem, which models coordinating servers to respond to incoming requests, and the parking permit problem, which models deciding when to buy short-term or long-term permits without knowing future parking needs.