Complexity of Inexact Proximal Point Algorithm for minimizing convex functions with Holderian Growth
This work provides theoretical complexity guarantees for optimization algorithms, which is incremental but useful for researchers in numerical optimization dealing with nonsmooth convex functions.
The paper derives nonasymptotic iteration complexity bounds for exact and inexact Proximal Point Algorithms (PPA) when minimizing convex functions with Holderian growth, showing rates of O(log(1/ε)) for γ in [1,2] and O(1/ε^{γ-2}) for γ>2, and recovers known results like finite convergence for sharp minima and linear convergence for quadratic growth, even with deterministic noise.
Several decades ago the Proximal Point Algorithm (PPA) started to gain a long-lasting attraction for both abstract operator theory and numerical optimization communities. Even in modern applications, researchers still use proximal minimization theory to design scalable algorithms that overcome nonsmoothness. Remarkable works as \cite{Fer:91,Ber:82constrained,Ber:89parallel,Tom:11} established tight relations between the convergence behaviour of PPA and the regularity of the objective function. In this manuscript we derive nonasymptotic iteration complexity of exact and inexact PPA to minimize convex functions under $γ-$Holderian growth: $\BigO{\log(1/ε)}$ (for $γ\in [1,2]$) and $\BigO{1/ε^{γ- 2}}$ (for $γ> 2$). In particular, we recover well-known results on PPA: finite convergence for sharp minima and linear convergence for quadratic growth, even under presence of deterministic noise. Moreover, when a simple Proximal Subgradient Method is recurrently called as an inner routine for computing each IPPA iterate, novel computational complexity bounds are obtained for Restarting Inexact PPA. Our numerical tests show improvements over existing restarting versions of the Subgradient Method.