Convergence Analysis of Linear Coupling with Inexact Proximal Operator

Abstract

Linear coupling is recently proposed to accelerate first-order algorithms by linking gradient descent and mirror descent together, which is able to achieve the accelerated convergence rate for first-order algorithms. This work focuses on the convergence analysis of linear coupling for convex composite minimization when the proximal operator cannot be exactly computed. It is of particular interest to study the convergence of linear coupling because it not only achieves the accelerated convergence rate for first-order algorithm but also works for generic norms. We present convergence analysis of linear coupling by allowing the proximal operator to be computed up to a certain precision. Our analysis illustrates that the accelerated convergence rate of linear coupling with inexact proximal operator can be preserved if the error sequence of inexact proximal operator decreases in a sufficiently fast rate. More importantly, our analysis leads to better bounds than existing works on inexact proximal operator. Experiment results on several real-world datasets verify our theoretical results.