CaltechAUTHORS
  A Caltech Library Service

Online Optimization with Untrusted Predictions

Rutten, Daan and Christianson, Nicolas and Mukherjee, Debankur and Wierman, Adam (2022) Online Optimization with Untrusted Predictions. . (Unpublished) https://resolver.caltech.edu/CaltechAUTHORS:20220304-172345101

[img] PDF - Submitted Version
See Usage Policy.

1MB

Use this Persistent URL to link to this item: https://resolver.caltech.edu/CaltechAUTHORS:20220304-172345101

Abstract

We examine the problem of online optimization, where a decision maker must sequentially choose points in a general metric 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 any desired δ > 0, it is (1 + 2δ)-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.


Item Type:Report or Paper (Discussion Paper)
Related URLs:
URLURL TypeDescription
https://doi.org/10.48550/arXiv.2202.03519arXivDiscussion Paper
ORCID:
AuthorORCID
Rutten, Daan0000-0002-4742-4201
Christianson, Nicolas0000-0001-8330-8964
Mukherjee, Debankur0000-0003-1678-4893
Wierman, Adam0000-0002-5923-0199
Subject Keywords:online algorithms, online optimization, competitive analysis, metrical task systems
DOI:10.48550/arXiv.2202.03519
Record Number:CaltechAUTHORS:20220304-172345101
Persistent URL:https://resolver.caltech.edu/CaltechAUTHORS:20220304-172345101
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:113734
Collection:CaltechAUTHORS
Deposited By: George Porter
Deposited On:07 Mar 2022 20:51
Last Modified:07 Mar 2022 20:51

Repository Staff Only: item control page