论文标题
通过内存和竞争控制的在线优化
Online Optimization with Memory and Competitive Control
论文作者
论文摘要
本文为新颖的在线优化问题提供了竞争性算法。我们考虑学习者试图最大程度地减少击球成本和转换成本的总和，该设置取决于以前的$ 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.
