We develop a modified online mirror descent framework that is suitable for building adaptive and parameter-free algorithms in unbounded domains. We leverage this technique to develop the first unconstrained online linear optimization algorithm achieving an optimal dynamic regret bound, and we further demonstrate that natural strategies based on Follow-the-Regularized-Leader are unable to achieve similar results. We also apply our mirror descent framework to build new parameter-free implicit updates, as well as a simplified and improved unconstrained scale-free algorithm.
翻译:我们开发了经修改的在线镜像下限框架,这个框架适合在无约束域内建立适应性和无参数的算法。我们利用这一技术开发了第一种不受限制的在线线性优化算法,实现了最佳动态遗憾约束,我们进一步证明基于“跟踪”的自然战略无法取得类似结果。我们还应用我们的镜像下限框架来构建新的无参数的隐性更新,以及简化和改进的无限制规模算法。