Non-convex online learning via algorithmic equivalence
We study an algorithmic equivalence technique between nonconvex 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.