Smoothed Online Optimization with Unreliable Predictions
Smoothed Online Optimization with Unreliable Predictions
复制标题
DOI：
10.1145/3579442
复制
发表时间：
2022-02
期刊：
影响因子：
--
通讯作者：
Daan Rutten;Nicolas H. Christianson;Debankur Mukherjee;A. Wierman
中科院分区：
文献类型：
--
作者：
Daan Rutten;Nicolas H. Christianson;Debankur Mukherjee;A. Wierman
我们研究平滑在线优化问题，在此问题中，决策者必须在赋范向量空间中依次选择点，以最小化每轮的非凸命中成本以及轮次之间切换决策的成本之和。决策者可使用黑箱预言机（例如机器学习模型），它对每轮的最优决策提供不可信且可能不准确的预测。决策者的目标是在预测准确时利用这些预测，同时保证性能不会比事后最优决策序列差太多，即使预测不准确时也是如此。我们施加标准假设，即命中成本是全局α - 多面体的。我们提出一种新算法，自适应在线切换（AOS），并证明对于一大组可行的δ > 0，如果预测是完美的，它具有(1 + δ) - 竞争力，并且即使预测是对抗性的，也能保持一致有界的竞争比为2 ~ O(1/(α δ))。此外，我们证明这种权衡是必要的，并且在以下意义上几乎是最优的：任何在预测完美时具有(1 + δ) - 竞争力的确定性算法，在预测不准确时必须至少具有2 ~ Ω(1/(α δ)) - 竞争力。实际上，我们在这种权衡中观察到一种独特的阈值型行为：如果δ不在可行选项集合中，那么对于任何ζ < ∞，没有算法能在预测完美时同时具有(1 + δ) - 竞争力且在预测不准确时具有ζ - 竞争力。此外，我们通过证明任何不使用记忆的算法都无法从预测中受益，讨论了记忆在AOS中的关键作用。我们通过对微电网应用的数值研究补充了我们的理论结果。
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.