A Caltech Library Service

Smoothed Online Optimization with Unreliable Predictions

Rutten, Daan and Christianson, Nicolas and Mukherjee, Debankur and Wierman, Adam (2023) Smoothed Online Optimization with Unreliable Predictions. Proceedings of the ACM on Measurement and Analysis of Computing Systems, 7 (1). Art. No. 12. ISSN 2476-1249. doi:10.1145/3579442.

[img] PDF - Published Version
Creative Commons Attribution.


Use this Persistent URL to link to this item:


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^(O̅(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.

Item Type:Article
Related URLs:
URLURL TypeDescription
Rutten, Daan0000-0002-4742-4201
Christianson, Nicolas0000-0001-8330-8964
Mukherjee, Debankur0000-0003-1678-4893
Wierman, Adam0000-0002-5923-0199
Additional Information:© 2023 Copyright held by the owner/author(s). The work was partially supported by the NSF grant CIF-2113027.
Funding AgencyGrant Number
Issue or Number:1
Record Number:CaltechAUTHORS:20230316-86070000.1
Persistent URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:120111
Deposited By: George Porter
Deposited On:17 Mar 2023 18:17
Last Modified:17 Mar 2023 18:17

Repository Staff Only: item control page