论文标题
通过不可靠的预测平滑在线优化
Smoothed Online Optimization with Unreliable Predictions
论文作者
论文摘要
我们研究了平滑在线优化的问题，在该问题中，决策者必须在规范的矢量空间中依次选择点，以最大程度地减少每轮，非凸击成本的总和，以及在回合之间切换决策的成本。决策者可以访问黑盒甲骨文，例如机器学习模型，该模型可提供对每回合中最佳决策的不受信任且可能不准确的预测。决策者的目标是如果预测准确，则可以利用预测，同时确保绩效也不比事后最佳决策的最佳序列差得多，即使预测不准确。我们施加了以下标准假设，即打击成本在全球$α$ - 多利核。我们提出了一种新颖的算法，自适应在线切换（AOS），并证明，对于一大批可行的$Δ> 0 $，如果预测是完美的，则是$（1+δ）$ - 同时还保持均匀界限的竞争比率，即$ 2^{\ tilde {\ tilde {\ mathcal exion {\ Mathcal}（1）对抗性。此外，我们证明，从某种意义上说，这种权衡是必要的，几乎是最佳的，因为\ emph {any}确定性算法是$（1+δ）$ - 如果预测是完美的，则必须至少$ 2^{\tildeΩ（1/（αΔ）} $ - 当预测是有竞争力的竞争时，实际上，我们在这种权衡中观察到独特的阈值型行为：如果$δ$不在可行的选项中，那么\ emph {no}算法是同时$（1 +δ）$ - 如果预测是完美的，并且$ζ$ - 竞争是完美的，而预测是inaccurate for noccurate for noccurate for $ emm emm eftty $。此外，我们通过证明任何不使用内存的算法都无法从预测中受益，从而讨论了内存在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^{\tilde{\mathcal{O}}(1/(αδ))}$ even when predictions are adversarial. Further, we prove that this trade-off is necessary and nearly optimal in the sense that \emph{any} deterministic algorithm which is $(1+δ)$-competitive if predictions are perfect must be at least $2^{\tildeΩ(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 \emph{no} algorithm is simultaneously $(1 + δ)$-competitive if predictions are perfect and $ζ$-competitive when predictions are inaccurate for any $ζ< \infty$. 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.
