# Smoothed Online Optimization with Unreliable Predictions

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

## Key facts

- Cited by 10 papers in the map (data through 14 Oct 2026).
- Builds on 29 of its 71 references that are in the map.
- First posted on arXiv 7 Feb 2022.

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

- [A Review of Uncertainty Quantification in Deep Learning: Techniques, Applications and Challenges](https://mlsanity.com/paper/2011.06225/) (2020)
- [Competitive caching with machine learned advice](https://mlsanity.com/paper/1802.05399/) (2018)
- [The Primal-Dual method for Learning Augmented Algorithms](https://mlsanity.com/paper/2010.11632/) (2020)
- [Online metric algorithms with untrusted predictions](https://mlsanity.com/paper/2003.02144/) (2020)
- [Secretary and Online Matching Problems with Machine Learned Advice](https://mlsanity.com/paper/2006.01026/) (2020)
- [Optimal Robustness-Consistency Trade-offs for Learning-Augmented Online Algorithms](https://mlsanity.com/paper/2010.11443/) (2020)
- [Thinking Fast and Slow: Optimization Decomposition Across Timescales](https://mlsanity.com/paper/1704.07785/) (2017)
- [Scheduling with Predictions and the Price of Misprediction](https://mlsanity.com/paper/1902.00732/) (2019)
- [Secretaries with Advice](https://mlsanity.com/paper/2011.06726/) (2020)
- [Learning Augmented Energy Minimization via Speed Scaling](https://mlsanity.com/paper/2010.11629/) (2020)
- [Smoothed Online Convex Optimization in High Dimensions via Online Balanced Descent](https://mlsanity.com/paper/1803.10366/) (2018)
- [Beyond Online Balanced Descent: An Optimal Algorithm for Smoothed Online Optimization](https://mlsanity.com/paper/1905.12776/) (2019)
- [Revisiting Smoothed Online Learning](https://mlsanity.com/paper/2102.06933/) (2021)
- [Flow Time Scheduling with Uncertain Processing Time](https://mlsanity.com/paper/2103.05604/) (2021)
- [Learnable and Instance-Robust Predictions for Online Matching, Flows and Load Balancing](https://mlsanity.com/paper/2011.11743/) (2020)
- [Smoothed Online Optimization for Regression and Control](https://mlsanity.com/paper/1810.10132/) (2018)
- [Online learning over a finite action set with limited switching](https://mlsanity.com/paper/1803.01548/) (2018)
- [Pareto-Optimal Learning-Augmented Algorithms for Online Conversion Problems](https://mlsanity.com/paper/2109.01556/) (2021)
- [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)
- [Chasing Convex Bodies with Linear Competitive Ratio](https://mlsanity.com/paper/1905.11877/) (2019)
- [Semi-Online Bipartite Matching](https://mlsanity.com/paper/1812.00134/) (2018)
- [Online Optimization with Predictions and Non-convex Losses](https://mlsanity.com/paper/1911.03827/) (2019)
- [Leveraging Predictions in Smoothed Online Convex Optimization via Gradient-based Algorithms](https://mlsanity.com/paper/2011.12539/) (2020)
- [Optimal Algorithms for Right-Sizing Data Centers- Extended Version](https://mlsanity.com/paper/1807.05112/) (2018)
- [Online Capacity Scaling Augmented With Unreliable Machine Learning Predictions](https://mlsanity.com/paper/2101.12160/) (2021)
- [A Model for Learned Bloom Filters and Related Structures](https://mlsanity.com/paper/1802.00884/) (2018)
- [Algorithms for Right-Sizing Heterogeneous Data Centers](https://mlsanity.com/paper/2107.14692/) (2021)

## Built on by (most cited first, 10 of 10)

- [Online Conversion with Switching Costs: Robust and Learning-Augmented Algorithms](https://mlsanity.com/paper/2310.20598/) (2023)
- [Learning for Edge-Weighted Online Bipartite Matching with Robustness Guarantees](https://mlsanity.com/paper/2306.00172/) (2023)
- [Robust Learning for Smoothed Online Convex Optimization with Feedback Delay](https://mlsanity.com/paper/2310.20098/) (2023)
- [Best of Both Worlds Guarantees for Smoothed Online Quadratic Optimization](https://mlsanity.com/paper/2311.00181/) (2023)
- [Learning-augmented Online Minimization of Age of Information and Transmission Costs](https://mlsanity.com/paper/2403.02573/) (2024)
- [Partially Lazy Gradient Descent for Smoothed Online Learning](https://mlsanity.com/paper/2601.15984/) (2026)
- [Learning-Augmented Decentralized Online Convex Optimization in Networks](https://mlsanity.com/paper/2306.10158/) (2023)
- [Capacity Provisioning Motivated Online Non-Convex Optimization Problem with Memory and Switching Cost](https://mlsanity.com/paper/2403.17480/) (2024)
- [Optimistic Learning for Communication Networks](https://mlsanity.com/paper/2504.03499/) (2025)
- [Fairness-Regularized Online Optimization with Switching Costs](https://mlsanity.com/paper/2512.11131/) (2025)

## Abstract (arXiv)

We examine the problem of smoothed online optimization, where a decision maker must sequentially choose points in a normed vector space to minimize the sum of per-round, non-convex hitting costs and the costs of switching decisions between rounds. The decision maker has access to a black-box oracle, such as a machine learning model, that provides untrusted and potentially inaccurate predictions of the optimal decision in each round. The goal of the decision maker is to exploit the predictions if they are accurate, while guaranteeing performance that is not much worse than the hindsight optimal sequence of decisions, even when predictions are inaccurate. We impose the standard assumption that hitting costs are globally α-polyhedral. We propose a novel algorithm, Adaptive Online Switching (AOS), and prove that, for a large set of feasible δ > 0, it is (1+δ)-competitive if predictions are perfect, while also maintaining a uniformly bounded competitive ratio of 2^tildeO(1/(α δ)) even when predictions are adversarial. Further, we prove that this trade-off is necessary and nearly optimal in the sense that any deterministic algorithm which is (1+δ)-competitive if predictions are perfect must be at least 2^tildeOmega(1/(α δ))-competitive when predictions are inaccurate. In fact, we observe a unique threshold-type behavior in this trade-off: if δ is not in the set of feasible options, then no algorithm is simultaneously (1 + δ)-competitive if predictions are perfect and zeta-competitive when predictions are inaccurate for any zeta < ∞. Furthermore, we discuss that memory is crucial in AOS by proving that any algorithm that does not use memory cannot benefit from predictions. We complement our theoretical results by a numerical study on a microgrid application.