Accelerated optimization algorithms and ordinary differential equations: the convex non Euclidean case

Abstract We study the connections between ordinary differential equations and optimization algorithms in a non-Euclidean setting. We propose a novel accelerated algorithm for minimizing convex functions over a convex constrained set. This algorithm is a natural generalization of Nesterov’s accelerated gradient descent method to the non-Euclidean setting and can be interpreted as an additive Runge-Kutta algorithm. The algorithm can also be derived as a numerical discretization of the ODE suggested by Krichene et al. in 2015. We use Lyapunov functions to establish convergence rates for the ODE and show that the discretizations considered achieve acceleration beyond the setting studied by Krichene and his coworkers. Finally, we discuss how the proposed algorithm connects to various equations and algorithms in the literature.