# Error bounds, PL condition, and quadratic growth for weakly convex functions, and linear convergences of proximal point methods

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

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 28 Dec 2023.

## Built on by (most cited first, 7 of 7)

- [Learning to optimize with guarantees: a complete characterization of linearly convergent algorithms](https://mlsanity.com/paper/2508.00775/) (2025)
- [Efficient Combinatorial Optimization via Heat Diffusion](https://mlsanity.com/paper/2403.08757/) (2024)
- [Statistical Inference for Online Algorithms](https://mlsanity.com/paper/2505.17300/) (2025)
- [Error Bound Analysis for the Regularized Loss of Deep Linear Neural Networks](https://mlsanity.com/paper/2502.11152/) (2025)
- [Stability and Generalization for Bellman Residuals](https://mlsanity.com/paper/2508.18741/) (2025)
- [Gradient Dominance in the Linear Quadratic Regulator: A Unified Analysis for Continuous-Time and Discrete-Time Systems](https://mlsanity.com/paper/2602.22577/) (2026)
- [Trajectory-Restricted Optimization Conditions and Geometry-Aware Linear Convergence](https://mlsanity.com/paper/2604.17067/) (2026)

## Abstract (arXiv)

Many practical optimization problems lack strong convexity. Fortunately, recent studies have revealed that first-order algorithms also enjoy linear convergences under various weaker regularity conditions. While the relationship among different conditions for convex and smooth functions is well-understood, it is not the case for the nonsmooth setting. In this paper, we go beyond convexity and smoothness, and clarify the connections among common regularity conditions in the class of weakly convex functions, including textitstrong convexity, textitrestricted secant inequality, textitsubdifferential error bound, textitPolyak-Lojasiewicz inequality, and textitquadratic growth. In addition, using these regularity conditions, we present a simple and modular proof for the linear convergence of the proximal point method (PPM) for convex and weakly convex optimization problems. The linear convergence also holds when the subproblems of PPM are solved inexactly with a proper control of inexactness.