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

Technical Summary: Error Bounds, PL Condition, and Quadratic Growth for Weakly Convex Functions, and Linear Convergences of Proximal Point Methods

Problem Statement
Many practical optimization problems, particularly in machine learning and signal processing, lack strong convexity. While first-order algorithms are known to achieve linear convergence under strong convexity, recent studies have shown that linear convergence can also be guaranteed under weaker regularity conditions (e.g., Polyak-Lojasiewicz inequality, error bounds, quadratic growth) for smooth and convex functions. However, the relationships among these conditions were not well-understood in the setting of nonsmooth, nonconvex functions. Specifically, the class of weakly convex functions (functions $f$ such that $f + \frac{\rho}{2}\|\cdot\|^2$ is convex for some $\rho \geq 0$) encompasses many modern models (e.g., nonsmooth deep networks, compositions of convex and smooth functions) but lacked a unified framework connecting these regularity conditions. Furthermore, existing proofs for the linear convergence of the Proximal Point Method (PPM) often relied on restrictive assumptions (e.g., unique minimizers, local Lipschitz continuity of the inverse subdifferential) or complex arguments.

Methodology
The paper employs tools from nonsmooth analysis, specifically the notion of slope, Ekeland's variational principle, and distance estimation lemmas, to analyze the relationships between regularity conditions. The authors define five key conditions over a sublevel set $[f \leq f^\star + \nu]$:

1. Strong Convexity (SC)
2. Restricted Secant Inequality (RSI)
3. Subdifferential Error Bound (EB)
4. Polyak-Lojasiewicz (PL) Inequality
5. Quadratic Growth (QG)

The authors utilize the slope $|\nabla f|(x) = \text{dist}(0, \hat{\partial}f(x))$ (where $\hat{\partial}f$ is the Fréchet subdifferential) to bridge the gap between smooth and nonsmooth settings. They establish logical implications and equivalences among these conditions, particularly focusing on the case where the quadratic growth constant $\mu_q$ exceeds the weak convexity parameter $\rho$.

Building on these equivalences, the paper analyzes the Proximal Point Method (PPM):
$$x_{k+1} = \text{prox}_{c_k f}(x_k) = \arg\min_x \left( f(x) + \frac{1}{2c_k}\|x - x_k\|^2 \right)$$
The authors provide a modular proof for linear convergence in both convex and weakly convex settings. They also extend the analysis to the Inexact PPM (iPPM), where subproblems are solved approximately, addressing subtleties regarding stopping criteria and feasibility (ensuring iterates remain within the domain of $f$).

Key Contributions

1. Unification of Regularity Conditions for Weakly Convex Functions:
   The paper establishes the hierarchy and equivalence of regularity conditions for $\rho$-weakly convex functions.

   • General Implication Chain: $(SC) \implies (RSI) \implies (EB) \iff (PL) \implies (QG)$.
   • Equivalence under $\mu_q > \rho$: If a $\rho$-weakly convex function satisfies Quadratic Growth with a constant $\mu_q > \rho$, then all four conditions $(RSI), (EB), (PL),$ and $(QG)$ are equivalent.
   • The authors derive explicit coefficient conversions between these conditions (summarized in Table 1 of the paper), allowing practitioners to translate constants from one condition to another.

2. Simplified Linear Convergence Proofs for PPM:
   The paper presents a simple, modular proof for the linear convergence of PPM for both convex and weakly convex functions.

   • Convex Case: Under any of the equivalent regularity conditions (PL, EB, RSI, QG), PPM achieves linear convergence for both function values and distance to the solution set. The proof relaxes previous assumptions, removing the requirement for a unique minimizer or local Lipschitz continuity of the inverse subdifferential.
   • Weakly Convex Case: The results are extended to $\rho$-weakly convex functions provided the initialization is within a sublevel set satisfying QG with $\mu_q > \rho$ and the step sizes satisfy $1/c_k > \rho$.

3. Analysis of Inexact PPM (iPPM):
   The authors clarify the nuances of inexactness and feasibility in iPPM. They establish linear convergence for iPPM under standard stopping criteria (Rockafellar's criteria A and B), provided the function satisfies QG in a neighborhood of the solution set. The proof combines a key inequality from prior literature with the modular regularity condition framework.

Results

• Theoretical: Theorem 3.1 confirms that for weakly convex functions, the equivalence of regularity conditions holds if $\mu_q > \rho$. This generalizes previous results limited to smooth or convex functions.
• Algorithmic: Theorems 4.2 and 4.3 demonstrate that PPM converges linearly with rates dependent on the regularity constants (e.g., $\omega_k = \frac{1}{1+c_k\mu_p}$). Theorem 5.3 extends this to inexact PPM, showing that as long as the inexactness is controlled (sum of errors is finite), the linear convergence rate is preserved asymptotically.
• Numerical: Experiments on Linear SVM, Lasso, and Elastic-Net problems confirm the theoretical linear convergence of PPM. The experiments utilize the YALMIP modeling package and MOSEK solver, showing fast convergence in both cost value gaps and distance to the solution set.

Significance and Claims
The paper claims to generalize the understanding of regularity conditions from smooth/convex settings to the broader class of nonsmooth weakly convex functions. By clarifying the connections between these conditions, the authors provide a unified framework that simplifies the analysis of iterative algorithms.

Specifically, the paper asserts that:

• The equivalence of conditions (RSI, EB, PL, QG) under $\mu_q > \rho$ allows for flexible analysis; one condition can be established to derive convergence results via the others.
• The proofs for PPM linear convergence are simpler and more transparent than existing literature, avoiding restrictive assumptions like unique minimizers.
• The results facilitate algorithm development for nonsmooth optimization, particularly in large-scale conic optimization and machine learning applications where weak convexity is prevalent.

The authors note that while the equivalence of these conditions was known for smooth or convex functions, extending this to the weakly convex setting and providing a clean proof for PPM (including inexact versions) constitutes the primary novelty. The work is presented as an extended version of a conference paper, with the addition of detailed proofs, coefficient conversions, and extended analysis of inexact PPM.