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, 指数化的组合,或强烈的组合),以及环境的性质(固定或变化)以及环境的性质(固定或变化)。作为产品,它还允许将功能的类型转换为两轮。