Smoothed Online Optimization with Unreliable Predictions
Proceedings of the ACM on Measurement and Analysis of Computing Systems · 27.02.2023 · 7 (1) · 1-36
DOI: 10.1145/3579442 ↗Kurz gefasst
Fachartikel in der Zeitschrift Proceedings of the ACM on Measurement and Analysis of Computing Systems, online erschienen am 02.03.2023. Verfasst von Daan Rutten und 3 weiteren Autor:innen. Die Arbeit wurde bisher 9-mal zitiert (Crossref) und nennt 66 Literaturangaben. Gefördert von: NSF.
Abstract (Originalsprache)
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~O (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~Ω (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 ζ-competitive when predictions are inaccurate for any ζ < ∞. 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.
Förderung
- NSF
Zitieren
APA
Rutten, D., Christianson, N., Mukherjee, D., & Wierman, A. (2023). Smoothed Online Optimization with Unreliable Predictions. Proceedings of the ACM on Measurement and Analysis of Computing Systems, 7(1), 1-36. https://doi.org/10.1145/3579442
Vancouver
Rutten D, Christianson N, Mukherjee D, Wierman A. Smoothed Online Optimization with Unreliable Predictions. Proceedings of the ACM on Measurement and Analysis of Computing Systems. 2023;7(1):1-36. doi:10.1145/3579442
BibTeX
@article{Rutten2023,
author = {Rutten, Daan and Christianson, Nicolas and Mukherjee, Debankur and Wierman, Adam},
title = {Smoothed Online Optimization with Unreliable Predictions},
journal = {Proceedings of the ACM on Measurement and Analysis of Computing Systems},
year = {2023},
volume = {7},
number = {1},
pages = {1--36},
doi = {10.1145/3579442}
}
EUVIMED