论文标题
在线镜像下降和双重平均：在动态案例中保持步伐
Online mirror descent and dual averaging: keeping pace in the dynamic case
论文作者
论文摘要
在线镜像下降（OMD）和双重平均（DA）（在线凸优化的两种基本算法）在与固定学习率一起使用时具有非常相似（有时相同）的性能保证。但是，在动态学习率下，OMD证明不如DA，即使在常见的环境中，例如通过专家建议进行预测，也会感到遗憾。我们通过称为稳定化的简单技术来修改OMD算法。通过仔细和模块化的方式修改经典的OMD收敛分析，从而给予OMD的基本相同的抽象遗憾，并为DA提供了同样的遗憾，从而可以简单而灵活。这些界限的简单推论表明，即使在动态学习率下，OMD都具有稳定和DA的稳定性保证。我们还阐明了OMD和DA之间的相似性，并显示了简单的条件，在这些条件下，稳定性的OMD和DA会产生相同的迭代。
Online mirror descent (OMD) and dual averaging (DA) -- two fundamental algorithms for online convex optimization -- are known to have very similar (and sometimes identical) performance guarantees when used with a fixed learning rate. Under dynamic learning rates, however, OMD is provably inferior to DA and suffers a linear regret, even in common settings such as prediction with expert advice. We modify the OMD algorithm through a simple technique that we call stabilization. We give essentially the same abstract regret bound for OMD with stabilization and for DA by modifying the classical OMD convergence analysis in a careful and modular way that allows for straightforward and flexible proofs. Simple corollaries of these bounds show that OMD with stabilization and DA enjoy the same performance guarantees in many applications -- even under dynamic learning rates. We also shed light on the similarities between OMD and DA and show simple conditions under which stabilized-OMD and DA generate the same iterates.
