EUVIMEDEUVIMED entdecken
Crossref

Smoothed Online Optimization with Unreliable Predictions

Daan Rutten, Nicolas Christianson, Debankur Mukherjee, Adam Wierman

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.

AbstractBibliografische AngabenZitierenVerwandte Studien

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}
}
Kostenlos starten →