Non-convex online learning via algorithmic equivalence

Understand

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.