论文标题
通过算法等效性的非凸线在线学习
Non-convex online learning via algorithmic equivalence
论文作者
论文摘要
我们研究非凸梯度下降和凸镜下降之间的算法当量技术。首先，我们研究了在线非凸优化中的更严重的遗憾最小化问题。我们表明，在某些几何和平稳性条件下，应用于非凸功能功能的在线梯度下降是在重新聚集化下应用于凸功能的在线镜像下降的近似。在连续的时间里，与此相当的梯度流相当于与2020年的暖气相当于连续的镜像下降，但是对于类似的离散时间算法而言，理论是一个开放的问题。我们证明了一个$ O（t^{\ frac {2} {3}}）$遗憾在此环境中绑定了非convex在线渐变下降，回答了这个开放的问题。我们的分析基于一种新的简单算法等效方法。
We study an algorithmic equivalence technique between non-convex gradient descent and convex mirror descent. We start by looking at a harder problem of regret minimization in online non-convex optimization. We show that under certain geometric and smoothness conditions, online gradient descent applied to non-convex functions is an approximation of online mirror descent applied to convex functions under reparameterization. In continuous time, the gradient flow with this reparameterization was shown to be exactly equivalent to continuous-time mirror descent by Amid and Warmuth 2020, but theory for the analogous discrete time algorithms is left as an open problem. We prove an $O(T^{\frac{2}{3}})$ regret bound for non-convex online gradient descent in this setting, answering this open problem. Our analysis is based on a new and simple algorithmic equivalence method.
