# Complexity of Inexact Proximal Point Algorithm for minimizing convex functions with Holderian Growth

arXiv: https://arxiv.org/abs/2108.04482 · HTML: https://mlsanity.com/paper/2108.04482/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 14 of its 56 references that are in the map.
- First posted on arXiv 10 Aug 2021.

## Builds on (most cited first, 14 of 14)

- [A Proximal Stochastic Gradient Method with Progressive Variance Reduction](https://mlsanity.com/paper/1403.4699/) (2014)
- [How To Make the Gradients Small Stochastically: Even Faster Convex and Nonconvex SGD](https://mlsanity.com/paper/1801.02982/) (2018)
- [A Universal Catalyst for First-Order Optimization](https://mlsanity.com/paper/1506.02186/) (2015)
- [From error bounds to the complexity of first-order descent methods for convex functions](https://mlsanity.com/paper/1510.08234/) (2015)
- [Catalyst Acceleration for First-order Convex Optimization: from Theory to Practice](https://mlsanity.com/paper/1712.05654/) (2017)
- [Subgradient methods for sharp weakly convex functions](https://mlsanity.com/paper/1803.02461/) (2018)
- [Cyanure: An Open-Source Toolbox for Empirical Risk Minimization for Python, C++, and soon more](https://mlsanity.com/paper/1912.08165/) (2019)
- [RSG: Beating Subgradient Method without Smoothness and Strong Convexity](https://mlsanity.com/paper/1512.03107/) (2015)
- [Adaptive Catalyst for Smooth Convex Optimization](https://mlsanity.com/paper/1911.11271/) (2019)
- [New Computational Guarantees for Solving Convex Optimization Problems with First Order Methods, via a Function Growth Condition Measure](https://mlsanity.com/paper/1511.02974/) (2015)
- [Faster Subgradient Methods for Functions with H"olderian Growth](https://mlsanity.com/paper/1704.00196/) (2017)
- [Efficient First-Order Methods for Linear Programming and Semidefinite Programming](https://mlsanity.com/paper/1409.5832/) (2014)
- [Proximal point algorithm, Douglas-Rachford algorithm and alternating projections: a case study](https://mlsanity.com/paper/1501.06603/) (2015)
- [An adaptive proximal point algorithm framework and application to large-scale optimization](https://mlsanity.com/paper/2008.08784/) (2020)

## 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.