Complexity of Inexact Proximal Point Algorithm for minimizing convex functions with Holderian Growth
Not on the map. Why?
Abstract (arXiv)
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 citeFer: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: BigOlog(1/ε) (for γ ∈ [1,2]) and BigO1/εγ - 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.
Key facts. No citing papers in the map yet (data through 7 Oct 2026). Builds on 14 of its 56 references that are in the map. First posted on arXiv 10 Aug 2021.
Builds on
14 of 56 references.
References · 14
- 2014A Proximal Stochastic Gradient Method with Progressive Variance Reductioncited by 78
- 2018How To Make the Gradients Small Stochastically: Even Faster Convex and Nonconvex SGDcited by 55
- 2015A Universal Catalyst for First-Order Optimizationcited by 54
- 2015From error bounds to the complexity of first-order descent methods for convex functionscited by 42
- 2017Catalyst Acceleration for First-order Convex Optimization: from Theory to Practicecited by 39
- 2018Subgradient methods for sharp weakly convex functionscited by 33
- 2019Cyanure: An Open-Source Toolbox for Empirical Risk Minimization for Python, C++, and soon morecited by 16
- 2015RSG: Beating Subgradient Method without Smoothness and Strong Convexitycited by 15
- 2019Adaptive Catalyst for Smooth Convex Optimizationcited by 6
- 2015New Computational Guarantees for Solving Convex Optimization Problems with First Order Methods, via a Function Growth Condition Measurecited by 5
- 2017Faster Subgradient Methods for Functions with H"olderian Growthcited by 5
- 2014Efficient First-Order Methods for Linear Programming and Semidefinite Programmingcited by 2
Built on by
Not cited yet.