A Near-Optimal Total Complexity for the Inexact Accelerated Proximal Gradient Method via Quadratic Growth

Abstract

We consider the optimization problem ${\min }_{x\in {\mathbb{R}}^n}F(x):=f(x)+\ddot{I}‰(Ax)$, where $f$ is an $L$-Lipschitz smooth function, and $\ddot{I}‰$ is a proper, lower semicontinuous, and convex function. We prove in this paper that when $\ddot{I}‰$ is a conic polyhedral function, the inexact accelerated proximal gradient method (IAPG), employed in a double-loop structure, achieves a total complexity of $\mathcal{O}(\ln (1/\epsilon )/\sqrt{\epsilon })$ measured by the total number of calls to the proximal operator of the convex conjugate $\ddot{I}{‰}^{\star }$ and the gradient of $f$ to achieve $\epsilon$-optimality in function value. To the best of our knowledge, this improves upon the best-known complexity for IAPG. The key theoretical ingredient is a quadratic growth condition on the dual of the inexact proximal problem, which arises from the conic polyhedral structure of $\ddot{I}‰$ and implies linear convergence of the inner proximal gradient loop. To validate these findings, we conduct numerical experiments on a robust TV-${\ell }_2$ signal recovery problem, demonstrating fast convergence.

66 pages, 7 figures