Mirror Duality in Convex Optimization

Abstract

While first-order optimization methods are usually designed to efficiently reduce the function value $f(x)$, there has been recent interest in methods efficiently reducing the magnitude of $\nabla f(x)$, and the findings show that the two types of methods exhibit a certain symmetry. In this work, we present mirror duality, a one-to-one correspondence between mirror-descent-type methods reducing function value and reducing gradient magnitude. Using mirror duality, we obtain the dual accelerated mirror descent (dual-AMD) method that efficiently reduces $\ddot{I}{ˆ}^{\ast }(\nabla f(x))$, where $\ddot{I}ˆ$ is a distance-generating function and $\ddot{I}{ˆ}^{\ast }$ quantifies the magnitude of $\nabla f(x)$. We then apply dual-AMD to efficiently reduce $\Vert \nabla f(\cdot ){\Vert }_q$ for $q\in [2,\infty )$ and to efficiently compute $\epsilon$-approximate solutions of the optimal transport problem.