Online Optimization with Memory and Competitive Control
Online Optimization with Memory and Competitive Control
复制标题
DOI：
--
复制
发表时间：
2020-02
期刊：
影响因子：
--
通讯作者：
Guanya Shi;Yiheng Lin;Soon-Jo Chung;Yisong Yue;A. Wierman
中科院分区：
文献类型：
--
作者：
Guanya Shi;Yiheng Lin;Soon-Jo Chung;Yisong Yue;A. Wierman
针对一类新的带记忆的在线优化问题，提出了竞争算法。我们考虑一个设置，学习者寻求最小化的命中成本和切换成本，取决于以前的$p$决定的总和。此设置泛化平滑在线凸优化。所提出的方法，乐观正则化在线平衡下降，实现了恒定的，无量纲的竞争比。此外，我们展示了具有记忆的在线优化与具有对抗性干扰的在线控制之间的联系。这种联系，反过来，导致一个新的恒定竞争的政策，丰富的在线控制问题。
This paper presents competitive algorithms for a novel class of online optimization problems with memory. We consider a setting where the learner seeks to minimize the sum of a hitting cost and a switching cost that depends on the previous $p$ decisions. This setting generalizes Smoothed Online Convex Optimization. The proposed approach, Optimistic Regularized Online Balanced Descent, achieves a constant, dimension-free competitive ratio. Further, we show a connection between online optimization with memory and online control with adversarial disturbances. This connection, in turn, leads to a new constant-competitive policy for a rich class of online control problems.