点击数: 更新日期: 2023-11-15
中文题目：具有多预测的非平稳在线凸优化
论文题目：Nonstationary Online Convex Optimization with Multiple Predictions
录用期刊/会议：【Information Sciences】 (JCR Q1 top)
原文DOI： https://doi.org/10.1016/j.ins.2023.119862
原文链接：
https://www.sciencedirect.com/science/article/pii/S0020025523014470
录用/见刊时间：31 Oct 2023 Accept
封面图片：
封面摘要：本文通过引入多个预测改进了非平稳在线凸优化的动态后悔上界。我们的算法遵循元-专家框架, 并结合了乐观隐式更新的最新进展。论文的源程序已经公开。欢迎索取。
作者列表：
1） 孟庆鑫 中国石油大学（北京）信息科学与工程学院 控制科学与工程 博2018
2） 刘建伟 中国石油大学（北京）信息科学与工程学院 自动化系 教师
文章简介:
摘要:
本文关注完全信息非平稳在线凸优化的动态后悔。最新的分析表明：与Hedge相结合的隐式在线镜像下降（IOMD）实现了的动态后悔上界，其中表示损失函数随时间的变化，度量比较器序列路径长度，它反映了比较器序列的非平稳性；乐观的IOMD（OptIOMD）达到了的动态后悔的上界，其中表示从损失函数到任意预测序列的累积距离，是路径长度的上限。为了进一步抑制动态后悔，我们提出了一种名为Hedge-OptIOMD的算法，通过多个预测器，实现了的动态后悔上界，其中标示损失函数到第个预测器序列的累积距离。我们还通过数值实验验证了Hedge-OptIOMD的优势。
背景与动机:
许多分析乐观算法的文献研究了任意的单一预测，或使用前一轮损失函数作为预测器以建立具有损失函数时间变化性的上界。由于受到如下结论的启发：乐观算法中预测的准确性决定了后悔上界的水平，元-专家框架能够跟踪最佳专家，因此，本文着重于扩展元-专家框架以适应多个预测，以达到覆盖更广泛的潜在良性环境的目的。我们希望在维持最坏情况下的动态后悔的同时，追踪最佳预测算法。
然而，多个预测引发了元层的困难。通常，元层和专家层共享相同的预测，直接将多个预测引入专家层会导致这些预测进入元层。为了让元层能够追踪最佳预测，需要额外的Hedge算法。
设计与实现:
完整的Hedge-OptIOMD算法伪代码如Algorithm 1所示：
Hedge-OptIOMD算法的框架图如图1所示：
图1. The Logic Diagram of Algorithm 1.
实验结果及分析:
对于现实世界的温度预测任务，我们使用了2012年至2017年30个美国和加拿大城市以及两个以色列城市，特拉维夫和埃拉特的历史每小时温度数据。数据可在https://www.kaggle.com/datasets/ selffishgene/ history - hour - the weather上获得。为了使数据在短时间内表现出快速变化的特点，我们将每4小时的记录替换为其平均值。我们使用了4组预测器，包括前三轮损失函数和一个LSTM预测器。我们将蒙特利尔、波士顿、特拉维夫地区和埃拉特的数据用于测试，其余28组数据用于训练LSTM。实验结果验证了元层的跟踪能力。
图2. Performance of Algorithms on Temperature Forecasts for Four Cities.
结论:
这项工作改进了现有的完全信息非平稳在线凸优化的动态后悔上界。
我们设计了一种名为Hedge-OptIOMD的算法，通过多个预测增加了对环境的适应性。我们的算法遵循元-专家框架，并结合了乐观隐式更新的最新进展。
需要指出，隐式更新的每一步都需要解决一个凸优化问题，而元-专家框架进一步增加了计算量。尽管Zhao et al. (2022) 提出了降低非平稳投影算法复杂性的约化机制，但这种方法不适用于一般的隐式更新。是否存在能自动对抗任意路径长度的单一算法仍是一个未解决的问题。
作者简介:
孟庆鑫 自动化系2018级博士生。研究兴趣：在线凸优化、凸分析。
通讯作者简介:
刘建伟，教师，学者。发表学术研究论文280多篇。研究领域涉及在线学习（包括强化学习，赌博机算法，持续学习，长尾学习）；图像视频显著性目标检测，解纠缠表示学习，光场和神经场模型，以及图像视频少样本变化检测；自然语言理解中的知识补全，图神经网络；不平衡数据处理；非线性预测与控制。