An inexact Bregman proximal gradient method and its inertial variants

In this paper, we develop an inexact Bregman proximal gradient (iBPG) method based on a novel two-point inexact stopping condition, and establish the iteration complexity of $mathcal{O}(1/k)$ as well as the convergence of the sequence under some proper conditions. To improve the convergence speed, we further develop an inertial variant of our iBPG (denoted by v-iBPG) and show that it has the iteration complexity of $mathcal{O}(1/k^{gamma})$, where $gammageq1$ is a restricted relative smoothness exponent. Thus, when $gamma>1$, the v-iBPG readily improves the $mathcal{O}(1/k)$ convergence rate of the iBPG. In addition, for the case of using the squared Euclidean distance as the kernel function, we further develop a new inexact accelerated proximal gradient (iAPG) method, which can circumvent the underlying feasibility difficulty often appearing in existing inexact conditions and inherit all desirable convergence properties of the exact APG under proper summable-error conditions. Finally, we conduct some preliminary numerical experiments for solving a relaxation of the quadratic assignment problem to demonstrate the convergence behaviors of the iBPG, v-iBPG and iAPG under different inexactness settings.