Analyze Accelerated Mirror Descent via High-Resolution ODEs

Mirror descent, which can be seen as generalization of gradient descent for solving constrained optimization problem, has found a variety applications in many fields. As growing demand of solving high-dimensional constrained optimization problem, accelerated form of mirror descent has been proposed, along with its corresponding low-resolution ordinary differential equations (ODEs) framework has been studied. However, The low-resolution ODEs are unable to distinguish between Polyak’s heavy-ball method and Nesterov’s accelerated gradient method. This problem also arises with the low-resolution ODEs for accelerated mirror descent. To address this issue, we derive the high-resolution ODEs for accelerated mirror descent and propose a general Lyapunov function framework to analyze its convergence rates in both continuous time and discrete time. Furthermore, we demonstrate that the accelerated mirror descent can minimize the squared gradient norm at an inverse cubic rate by using the high-resolution ODEs framework. In the end, we extend the high-resolution ODEs framework for the accelerated mirror descent method to analyze the accelerated higher-order mirror descent and obtain finer convergence results.