Expert-Calibrated Learning for Online Optimization with Switching Costs
Expert-Calibrated Learning for Online Optimization with Switching Costs
复制标题
具有转换成本的在线优化专家校准学习
DOI：
10.1145/3530894
复制
发表时间：
2022
期刊：
影响因子：
--
通讯作者：
Ren, Shaolei
中科院分区：
文献类型：
--
作者：
Li, Pengfei;Yang, Jianyi;Ren, Shaolei
我们研究在线凸优化与切换成本，一个实际上很重要，但也极具挑战性的问题，由于缺乏完整的离线信息。通过利用基于机器学习（ML）的优化器的强大功能，ML增强的在线算法（本文中也称为专家校准）已经成为最先进的技术，具有可证明的最坏情况性能保证。尽管如此，通过使用训练ML模型作为独立优化器并将其插入ML增强算法的标准实践，平均成本性能可能非常不令人满意。为了解决“如何学习”的挑战，我们提出了EC-L2 O（专家校准学习优化），它通过明确考虑下游专家校准器来训练基于ML的优化器。为了实现这一目标，我们提出了一种新的可微专家校准器，它概括了正则化在线平衡下降，并在预测误差较大时提供比纯ML预测更好的竞争比。对于训练，我们的损失函数是两个不同损失的加权和-一个最小化平均ML预测误差以获得更好的鲁棒性，另一个最小化校准后的平均成本。我们还为EC-L2 O提供了理论分析，强调专家校准甚至可以有益于平均性价比，并且EC-L2 O实现的成本与离线最佳预言机（即，尾成本比率）可以有界。最后，我们通过运行模拟来测试EC-L2 O，以实现可持续的数据中心需求响应。我们的研究结果表明，EC-L2 O可以凭经验实现较低的平均成本以及较低的竞争比现有的基线算法。
We study online convex optimization with switching costs, a practically important but also extremely challenging problem due to the lack of complete offline information. By tapping into the power of machine learning (ML) based optimizers, ML-augmented online algorithms (also referred to as expert calibration in this paper) have been emerging as state of the art, with provable worst-case performance guarantees. Nonetheless, by using the standard practice of training an ML model as a standalone optimizer and plugging it into an ML-augmented algorithm, the average cost performance can be highly unsatisfactory. In order to address the "how to learn" challenge, we propose EC-L2O (expert-calibrated learning to optimize), which trains an ML-based optimizer by explicitly taking into account the downstream expert calibrator. To accomplish this, we propose a new differentiable expert calibrator that generalizes regularized online balanced descent and offers a provably better competitive ratio than pure ML predictions when the prediction error is large. For training, our loss function is a weighted sum of two different losses --- one minimizing the average ML prediction error for better robustness, and the other one minimizing the post-calibration average cost. We also provide theoretical analysis for EC-L2O, highlighting that expert calibration can be even beneficial for the average cost performance and that the high-percentile tail ratio of the cost achieved by EC-L2O to that of the offline optimal oracle (i.e., tail cost ratio) can be bounded. Finally, we test EC-L2O by running simulations for sustainable datacenter demand response. Our results demonstrate that EC-L2O can empirically achieve a lower average cost as well as a lower competitive ratio than the existing baseline algorithms.
登录
查看更多内容
DOI：
--
发表时间：
2020-02
期刊：
arXiv: Learning
影响因子：
--
作者：
Guanya Shi;Yiheng Lin;Soon-Jo Chung;Yisong Yue;A. Wierman
通讯作者：
Guanya Shi;Yiheng Lin;Soon-Jo Chung;Yisong Yue;A. Wierman
DOI：
--
发表时间：
2021-03
期刊：
J. Mach. Learn. Res.
影响因子：
--
作者：
Tianlong Chen;Xiaohan Chen;Wuyang Chen;Howard Heaton;Jialin Liu;Zhangyang Wang;W. Yin
通讯作者：
Tianlong Chen;Xiaohan Chen;Wuyang Chen;Howard Heaton;Jialin Liu;Zhangyang Wang;W. Yin
从特征学习 MDP：通过强化学习预测然后优化顺序决策
DOI：
--
发表时间：
2021
期刊：
Neural Information Processing Systems
影响因子：
--
作者：
Kai Wang;Sanket Shah;Haipeng Chen;A. Perrault;F. Doshi;M. Tambe
通讯作者：
M. Tambe
凸身追击上
影响因子：
0.8
作者：
J. Friedman;N. Linial
通讯作者：
N. Linial
DOI：
10.1145/3374888.3374892
发表时间：
2019
期刊：
ACM SIGMETRICS Performance Evaluation Review
影响因子：
--
作者：
Gautam Goel;A. Wierman
通讯作者：
A. Wierman