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.
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:
- 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.
- 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.
- 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