# Smoothed Online Combinatorial Optimization Using Imperfect Predictions

arXiv: https://arxiv.org/abs/2204.10979 · HTML: https://mlsanity.com/paper/2204.10979/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 13 of its 36 references that are in the map.
- First posted on arXiv 23 Apr 2022.

## Builds on (most cited first, 13 of 13)

- [Introduction to Online Convex Optimization](https://mlsanity.com/paper/1909.05207/) (2019)
- [Online metric algorithms with untrusted predictions](https://mlsanity.com/paper/2003.02144/) (2020)
- [Online Optimization with Predictions and Switching Costs: Fast Algorithms and the Fundamental Limit](https://mlsanity.com/paper/1801.07780/) (2018)
- [Chasing Nested Convex Bodies Nearly Optimally](https://mlsanity.com/paper/1811.00999/) (2018)
- [A Tale of Two Metrics: Simultaneous Bounds on Competitiveness and Regret](https://mlsanity.com/paper/1508.03769/) (2015)
- [Chasing Convex Bodies Optimally](https://mlsanity.com/paper/1905.11968/) (2019)
- [Online Convex Optimization Using Predictions](https://mlsanity.com/paper/1504.06681/) (2015)
- [Leveraging Predictions in Smoothed Online Convex Optimization via Gradient-based Algorithms](https://mlsanity.com/paper/2011.12539/) (2020)
- [Metrical task systems on trees via mirror descent and unfair gluing](https://mlsanity.com/paper/1807.04404/) (2018)
- [Augmenting Max-Weight with Explicit Learning for Wireless Scheduling with Switching Costs](https://mlsanity.com/paper/1808.01618/) (2018)
- [Competitively Chasing Convex Bodies](https://mlsanity.com/paper/1811.00887/) (2018)
- [Online Monotone Optimization](https://mlsanity.com/paper/1608.07888/) (2016)
- [An Optimization Framework For Online Ride-sharing Markets](https://mlsanity.com/paper/1612.03797/) (2016)

## Abstract (arXiv)

Smoothed online combinatorial optimization considers a learner who repeatedly chooses a combinatorial decision to minimize an unknown changing cost function with a penalty on switching decisions in consecutive rounds. We study smoothed online combinatorial optimization problems when an imperfect predictive model is available, where the model can forecast the future cost functions with uncertainty. We show that using predictions to plan for a finite time horizon leads to regret dependent on the total predictive uncertainty and an additional switching cost. This observation suggests choosing a suitable planning window to balance between uncertainty and switching cost, which leads to an online algorithm with guarantees on the upper and lower bounds of the cumulative regret. Empirically, our algorithm shows a significant improvement in cumulative regret compared to other baselines in synthetic online distributed streaming problems.