Projective Proximal Gradient Descent for Nonconvex Nonsmooth Optimization: Fast Convergence Without Kurdyka-Lojasiewicz (KL) Property

Yingzhen Yang, Ping LiICLR 2023 · OpenReview

This paper introduces a new optimization algorithm called Projective Proximal Gradient Descent (PPGD). It targets a specific but widely used class of nonconvex, nonsmooth problems, proving that they can be solved with the same "gold standard" efficiency as smooth convex problems—without needing the complex mathematical framework usually required for such proofs.

TL;DR

The authors propose PPGD, an algorithm that achieves a fast $O(1/k^2)$ local convergence rate for nonconvex, nonsmooth optimization problems where the regularizer is "piecewise convex." Crucially, it achieves this Nesterov-optimal rate without relying on the standard Kurdyka-Łojasiewicz (KŁ) property, offering a new geometric perspective on fast convergence.

What Problem Does This Paper Address?

In machine learning and statistics, we often want to minimize an objective function that is both nonconvex (it has multiple local minima or "valleys") and nonsmooth (it has sharp kinks or jumps). A classic example is sparse regression using the $\ell_0$-norm or "capped" penalties, which help select only the most important features.

Examples of piecewise convex regularizers, including the Indicator Penalty and Capped-L1.

Standard tools like Accelerated Proximal Gradient (APG) methods are incredibly fast for convex problems, hitting a convergence rate of $O(1/k^2)$. However, when things get nonconvex and nonsmooth, the math gets messy. Researchers usually turn to the Kurdyka-Łojasiewicz (KŁ) property to prove that an algorithm will converge. The downside? KŁ-based analysis often results in slower theoretical rates and can be difficult to apply intuitively.

The authors ask: Can we achieve that optimal $O(1/k^2)$ rate for a useful class of nonconvex problems by exploiting their internal structure instead?

Methods

The paper focuses on problems of the form $F(x) = g(x) + h(x)$, where $g$ is smooth and convex, but $h$ is a piecewise convex regularizer. This means $h$ is made up of several "chunks," and within each chunk, the function is convex.

The PPGD Algorithm

PPGD introduces two main innovations to the standard accelerated gradient framework:

  1. Surrogate Functions: For every convex "piece" of the regularizer, the authors construct a surrogate function that extends that piece's convexity to the entire space. This allows the algorithm to use standard proximal steps.
Illustration of surrogate functions constructed for different continuity cases of the original function.
  1. Negative-Curvature-Exploitation (NCE): This is the "secret sauce." When the algorithm's iterates jump from one convex piece to another (e.g., crossing a threshold in a capped-$\ell_1$ penalty), the NCE step checks if this transition actually helps. If the function has "negative curvature" at the boundary—meaning it drops off sharply—the algorithm exploits this to ensure a significant decrease in the objective value.
  2. Projective Operator: A novel projection step keeps the "momentum" of the acceleration from pushing the iterates into unstable regions while they are exploring different convex pieces.

Datasets

The authors evaluated PPGD on capped-$\ell_1$ regularized logistic regression using two standard image benchmarks:

  • MNIST: 70,000 images of handwritten digits (28x28 pixels).
  • CIFAR-10: 60,000 color images across 10 classes (32x32 pixels).

They specifically looked at binary classification tasks (sampling two classes) to test how quickly the algorithm could find sparse, nonconvex solutions.

Key Insights and Ideas

  • Finite Transitions: The most powerful insight is that the algorithm only transitions between different convex pieces a finite number of times. Because each transition forced by the NCE step results in a guaranteed "drop" in the objective value, the algorithm eventually "settles" into a final set of convex pieces.
  • Local Optimality is Global-Like: Once the algorithm settles into these final pieces, the problem effectively becomes convex. At this point, the NCE and Projective steps allow the algorithm to match Nesterov’s optimal $O(1/k^2)$ convergence rate.
  • Structural vs. Analytic Analysis: Instead of using the abstract KŁ property (which looks at the slope of the function), this paper uses the geometric structure (the pieces) of the regularizer to prove speed.

Key Results

  • Theoretical Speedup: The authors proved that after some finite number of iterations $k_0$, the error $F(x^{(k)}) - F(x^*)$ drops at a rate of $O(1/k^2)$. This is significantly faster than the sublinear rates typically proven for nonconvex problems.
  • Empirical Performance: In experiments on MNIST and CIFAR-10, PPGD consistently outperformed standard APG and monotone APG (mAPG). The objective value dropped much more sharply in the early iterations, and it reached a lower final value faster than the baselines.

Limitations and Future Work

  • Convexity of $g(x)$: Currently, the "smooth" part of the objective, $g(x)$, must be convex. Many deep learning problems involve a $g(x)$ (the loss function) that is itself nonconvex.
  • Piecewise Requirement: The theory relies strictly on the regularizer being piecewise convex. While this covers many popular choices (Capped-$\ell_1$, SCAD, $\ell_0$), it doesn't apply to purely smooth nonconvex regularizers.
  • Future Directions: The authors suggest extending this "piecewise" analysis to more general nonconvex functions and exploring whether the NCE strategy can be adapted for stochastic gradient descent (SGD) in deep learning.

Summary updated

Abstract

Nonconvex and nonsmooth optimization problems are important and challenging for statistics and machine learning. In this paper, we propose Projected Proximal Gradient Descent (PPGD) which solves a class of nonconvex and nonsmooth optimization problems, where the nonconvexity and nonsmoothness come from a nonsmooth regularization term which is nonconvex but piecewise convex. In contrast with existing convergence analysis of accelerated PGD methods for nonconvex and nonsmooth problems based on the Kurdyka-\L{}ojasiewicz (K\L{}) property, we provide a new theoretical analysis showing local fast convergence of PPGD. It is proved that PPGD achieves a fast convergence rate of $O(1/k^2)$ when the iteration number $k \ge k_0$ for a finite $k_0$ on a class of nonconvex and nonsmooth problems under mild assumptions, which is locally the Nesterov's optimal convergence rate of first-order methods on smooth and convex objective function with Lipschitz continuous gradient. Experimental results demonstrate the effectiveness of PPGD.
BibTeX
@inproceedings{yang2023projective,
  author = {Yingzhen Yang and Ping Li},
  title = {{Projective Proximal Gradient Descent for Nonconvex Nonsmooth Optimization: Fast Convergence Without Kurdyka-Lojasiewicz (KL) Property}},
  booktitle = {International Conference on Learning Representations},
  year = {2023},
  url = {https://openreview.net/forum?id=yEsj8pGNl1},
}
Figure