BriefGPT.xyz
Nov, 2013
可预测序列的优化、学习和游戏
Optimization, Learning, and Games with Predictable Sequences
HTML
PDF
Alexander Rakhlin, Karthik Sridharan
TL;DR
提供了乐观镜面下降算法的几个应用：将其用于线下优化中的镜像近端算法、扩展到 Holder 平滑函数、并将结果应用于鞍点问题；将其用于有限零和矩阵博弈中，为两个强耦合玩家提供最小化最大值均衡的渐进速率 O((log T)/T)；再考虑问题的部分信息版本并将结果应用于凸规划，展示了近似最大流问题的简单算法。
Abstract
We provide several applications of
optimistic mirror descent
, an online learning algorithm based on the idea of predictable sequences. First, we recover the
mirror prox
algorithm for offline optimization, prove a
→