论文标题
具有不同规范的自适应在线学习
Adaptive Online Learning with Varying Norms
论文作者
论文摘要
给定规范的任何增加的顺序$ \ | \ cdot \ | _0，\ dots，\ | \ cdot \ | _ {t-1} $，我们提供了一个在线凸出优化算法，输出某些域中的$ w_t $在某些域中$ w $在convex损失中的某些范围$ \ ell_t $ \ ell_t： $ r_t（u）= \ sum_ {t = 1}^t \ ell_t（w_t） - \ ell_t（u）\ le \ tilde o \ left（\ | | | | _ {t-1} \ sqrt {\ sqrt {\ sum_ {\ sum_ {\ sum_ { \ | g_t \ | _ {t-1，\ star}^2} \ right）$，其中$ g_t $是$ w_t $的$ \ ell_t $的子级别。我们的方法不需要调整$ u $的值，并允许任意凸出$ W $。我们将此结果应用于获得新的“全矩阵”风格的遗憾界限。在此过程中，我们提供了全矩阵Adagrad算法的新检查，这表明在先验分析后有更高的学习率值可显着提高。我们使用新技术来调整Adagrad，并实现了我们在混凝土算法中的改进。
Given any increasing sequence of norms $\|\cdot\|_0,\dots,\|\cdot\|_{T-1}$, we provide an online convex optimization algorithm that outputs points $w_t$ in some domain $W$ in response to convex losses $\ell_t:W\to \mathbb{R}$ that guarantees regret $R_T(u)=\sum_{t=1}^T \ell_t(w_t)-\ell_t(u)\le \tilde O\left(\|u\|_{T-1}\sqrt{\sum_{t=1}^T \|g_t\|_{t-1,\star}^2}\right)$ where $g_t$ is a subgradient of $\ell_t$ at $w_t$. Our method does not require tuning to the value of $u$ and allows for arbitrary convex $W$. We apply this result to obtain new "full-matrix"-style regret bounds. Along the way, we provide a new examination of the full-matrix AdaGrad algorithm, suggesting a better learning rate value that improves significantly upon prior analysis. We use our new techniques to tune AdaGrad on-the-fly, realizing our improved bound in a concrete algorithm.
