Tight Convergence Rate in Subgradient Norm of the Proximal Point Algorithm

2023/01/09 by Guoyong Gu, Junfeng Yang, Gu, Guoyong +1 · 1 citation
Computer Science · Engineering · Mathematics · #90C25 #Advanced Optimization Algorithms Research #FOS: Mathematics #Optimization and Control (math.OC) #Optimization and Variational Analysis #Sparse and Compressive Sensing Techniques

paper · pdf · doi:10.48550/arxiv.2301.03175

openalex publication_date 2023/01/09 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

Proximal point algorithm has found many applications, and it has been playing fundamental roles in the understanding, design, and analysis of many first-order methods. In this paper, we derive the tight convergence rate in subgradient norm of the proximal point algorithm, which was conjectured by Taylor, Hendrickx and Glineur [SIAM J.~Optim., 27 (2017), pp.~1283--1313]. This sort of convergence results in terms of the residual (sub)gradient norm is particularly interesting when considering dual methods, where the dual residual gradient norm corresponds to the primal distance to feasibility.

Cited by

• Optimized methods for composite optimization: a reduction perspective

Related

• Explicit Convergence Rate of The Proximal Point Algorithm under R-Continuity
• A New Exact Worst-Case Linear Convergence Rate of the Proximal Gradient Method
• On the Optimal Linear Convergence Rate of a Generalized Proximal Point Algorithm
• Metric Subregularity and the Proximal Point Method
• Error bounds, quadratic growth, and linear convergence of proximal\n methods