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

2023/12/28 by Liao, Feng-Yi, Ding, Lijun, Zheng, Yang · 13 citations
#FOS: Electrical engineering #FOS: Mathematics #Optimization and Control (math.OC) #Systems and Control (eess.SY) #electronic engineering #information engineering

paper · doi:10.48550/arxiv.2312.16775

Abstract

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 strong convexity, restricted secant inequality, subdifferential error bound, Polyak-Łojasiewicz inequality, and quadratic 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.

Cited by

• Data-Driven Analysis of First-Order Methods via Distributionally Robust Optimization
• Star Quasiconvexity: an Unified Approach for Linear Convergence of First-Order Methods Beyond Convexity
• First-order majorization-minimization meets high-order majorant: Boosted inexact high-order forward-backward method
• A Retraction-free Method for Nonsmooth Minimax Optimization over a Compact Manifold
• New Classes of Non-monotone Variational Inequality Problems Solvable via Proximal Gradient on Smooth Gap Functions
• Policy Optimization in Robust Control: Weak Convexity and Subgradient Methods
• Proximal gradient methods in Banach spaces
• LeAP-SSN: A Semismooth Newton Method with Global Convergence Rates
• Stability and Generalization for Bellman Residuals
• Learning to optimize with guarantees: a complete characterization of linearly convergent algorithms
• Set Smoothness Unlocks Clarke Hyper-stationarity in Bilevel Optimization
• A Stochastic Gradient Descent Method for Globally Minimizing Nearly Convex Functions
• Statistical Inference for Online Algorithms
• On the resolution of ℓ₁-norm minimization via a two-metric adaptive projection method

Related

• Error bounds, quadratic growth, and linear convergence of proximal methods
• The restricted strong convexity revisited: Analysis of equivalence to error bound and quadratic growth
• Linear Convergence and Error Bounds for Optimization Without Strong Convexity
• Local convergence of an inexact proximal algorithm for weakly convex functions
• Proximal methods avoid active strict saddles of weakly convex functions