To deal with changing environments, a new performance measure -- adaptive regret, defined as the maximum static regret over any interval, was proposed in online learning. Under the setting of online convex optimization, several algorithms have been successfully developed to minimize the adaptive regret. However, existing algorithms lack universality in the sense that they can only handle one type of convex functions and need apriori knowledge of parameters. By contrast, there exist universal algorithms, such as MetaGrad, that attain optimal static regret for multiple types of convex functions simultaneously. Along this line of research, this paper presents the first universal algorithm for minimizing the adaptive regret of convex functions. Specifically, we borrow the idea of maintaining multiple learning rates in MetaGrad to handle the uncertainty of functions, and utilize the technique of sleeping experts to capture changing environments. In this way, our algorithm automatically adapts to the property of functions (convex, exponentially concave, or strongly convex), as well as the nature of environments (stationary or changing). As a by product, it also allows the type of functions to switch between rounds.


翻译:为了应对不断变化的环境,在网上学习中提出了一个新的业绩计量 -- -- 适应性遗憾,定义为任何间隔内的最大静态遗憾。在在线康夫克斯优化的设置下,成功开发了几种算法,以尽量减少适应性遗憾。然而,现有的算法缺乏普遍性,因为其只能处理一种类型的康夫克斯功能,需要优先了解参数。相反,存在着通用算法,例如MetaGrad,这些算法同时为多种类型的康夫克斯功能取得最佳静态遗憾。在这一研究线上,本文件提出了第一个尽量减少康夫克斯功能适应性遗憾的通用算法。具体地说,我们借用了在MetaGrad保持多种学习率的想法,以处理功能的不确定性,并利用睡眠专家的技能来捕捉变化的环境。这样,我们的算法自动适应功能的属性(convex, 指数化的组合,或强烈的组合),以及环境的性质(固定或变化)以及环境的性质(固定或变化)。作为产品,它还允许将功能的类型转换为两轮。

0
下载
关闭预览

相关内容

在数学中,定义在n维区间上的实值函数,如果函数的图上任意两点之间的线段位于图上,称为凸函数。同样地,如果函数图上或上面的点集是凸集,则函数是凸的。
商业数据分析,39页ppt
专知会员服务
159+阅读 · 2020年6月2日
【Nature论文】深度网络中的梯度下降复杂度控制
专知会员服务
38+阅读 · 2020年3月9日
深度强化学习策略梯度教程,53页ppt
专知会员服务
178+阅读 · 2020年2月1日
Stabilizing Transformers for Reinforcement Learning
专知会员服务
58+阅读 · 2019年10月17日
《DeepGCNs: Making GCNs Go as Deep as CNNs》
专知会员服务
30+阅读 · 2019年10月17日
【深度学习视频分析/多模态学习资源大列表】
专知会员服务
91+阅读 · 2019年10月16日
机器学习入门的经验与建议
专知会员服务
92+阅读 · 2019年10月10日
MIT新书《强化学习与最优控制》
专知会员服务
275+阅读 · 2019年10月9日
灾难性遗忘问题新视角:迁移-干扰平衡
CreateAMind
17+阅读 · 2019年7月6日
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
Transferring Knowledge across Learning Processes
CreateAMind
27+阅读 · 2019年5月18日
逆强化学习-学习人先验的动机
CreateAMind
15+阅读 · 2019年1月18日
强化学习的Unsupervised Meta-Learning
CreateAMind
17+阅读 · 2019年1月7日
Unsupervised Learning via Meta-Learning
CreateAMind
42+阅读 · 2019年1月3日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
spinningup.openai 强化学习资源完整
CreateAMind
6+阅读 · 2018年12月17日
Hierarchical Imitation - Reinforcement Learning
CreateAMind
19+阅读 · 2018年5月25日
Arxiv
0+阅读 · 2021年7月5日
A General and Adaptive Robust Loss Function
Arxiv
8+阅读 · 2018年11月5日
VIP会员
相关VIP内容
商业数据分析,39页ppt
专知会员服务
159+阅读 · 2020年6月2日
【Nature论文】深度网络中的梯度下降复杂度控制
专知会员服务
38+阅读 · 2020年3月9日
深度强化学习策略梯度教程,53页ppt
专知会员服务
178+阅读 · 2020年2月1日
Stabilizing Transformers for Reinforcement Learning
专知会员服务
58+阅读 · 2019年10月17日
《DeepGCNs: Making GCNs Go as Deep as CNNs》
专知会员服务
30+阅读 · 2019年10月17日
【深度学习视频分析/多模态学习资源大列表】
专知会员服务
91+阅读 · 2019年10月16日
机器学习入门的经验与建议
专知会员服务
92+阅读 · 2019年10月10日
MIT新书《强化学习与最优控制》
专知会员服务
275+阅读 · 2019年10月9日
相关资讯
灾难性遗忘问题新视角:迁移-干扰平衡
CreateAMind
17+阅读 · 2019年7月6日
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
Transferring Knowledge across Learning Processes
CreateAMind
27+阅读 · 2019年5月18日
逆强化学习-学习人先验的动机
CreateAMind
15+阅读 · 2019年1月18日
强化学习的Unsupervised Meta-Learning
CreateAMind
17+阅读 · 2019年1月7日
Unsupervised Learning via Meta-Learning
CreateAMind
42+阅读 · 2019年1月3日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
spinningup.openai 强化学习资源完整
CreateAMind
6+阅读 · 2018年12月17日
Hierarchical Imitation - Reinforcement Learning
CreateAMind
19+阅读 · 2018年5月25日
Top
微信扫码咨询专知VIP会员