Abstract
Nonconvex and nonsmooth optimization problems, such as Nonnegative Matrix Factorization (NMF), often feature gradients that lack global Lipschitz continuity, rendering standard stochastic gradient methods ineffective. This paper presents the Bregman Proximal Stochastic Gradient method with Extrapolation (BPSGE), which combines the geometric flexibility of Bregman distances with the acceleration of extrapolation and the stability of variance reduction. We establish a convergence rate of $O(\epsilon^{-2})$ and prove global convergence of the iterate sequence using the Kurdyka-Łojasiewicz property. Empirical results on image clustering and matrix factorization benchmarks demonstrate that BPSGE significantly improves both convergence speed and final accuracy compared to state-of-the-art baselines.
Introduction
In machine learning and signal processing, many fundamental tasks involve minimizing cost functions that are neither convex nor globally smooth. Standard algorithms like Stochastic Gradient Descent (SGD) typically require a Lipschitz continuous gradient to guarantee convergence. However, in applications like NMF or training specific neural architectures, gradients can be "wild," changing abruptly and violating global smoothness assumptions.
While Bregman-type methods were introduced to handle such geometries by replacing Euclidean distances with more adaptable proximity measures, they have historically struggled with scalability and slow convergence in stochastic settings. This work bridges that gap by introducing a stochastic Bregman framework enhanced with extrapolation (momentum).
The BPSGE Framework
The proposed Bregman Proximal Stochastic Gradient method with Extrapolation (BPSGE) integrates three key algorithmic components:
- Bregman Distances: Instead of the standard Euclidean metric, BPSGE utilizes a kernel function $\psi$ tailored to the problem's specific constraints. This allows the algorithm to adapt to the local geometry of the objective function.
- Extrapolation (Inertia): Inspired by Nesterov’s acceleration, BPSGE incorporates an extrapolation step $\beta_k$. This "momentum" helps the algorithm navigate flat regions and narrow valleys more efficiently.
- Variance Reduction: To mitigate the noise inherent in stochastic mini-batch gradients, BPSGE integrates SAGA and SARAH frameworks. This ensures a more stable descent path toward the optimal solution.
Theoretical Contributions
A significant contribution of this work is the rigorous convergence analysis for the nonconvex and nonsmooth setting. We prove that BPSGE achieves a complexity of $O(\epsilon^{-2})$ to reach a stationary point. Furthermore, by leveraging the Kurdyka-Łojasiewicz (KŁ) property, we demonstrate that the sequence of iterates produced by the algorithm converges to a single critical point.
Experimental Evaluation
We evaluated BPSGE across several challenging benchmarks, including Graph Regularized NMF (on COIL20, PIE, TDT2) and Matrix Factorization with weakly-convex regularization (on ORL and Yale-B).
The results consistently show that the addition of extrapolation (the 'E' in BPSGE) provides a significant performance boost. For instance, in image clustering on the COIL20 dataset, BPSGE-SAGA achieved an accuracy of 89.97%, compared to 75.56% for the deterministic BPG baseline and 85.83% for the non-extrapolated stochastic version.
Key Insights
- Smooth Adaptivity: The paper reinforces that global Lipschitz constants are not strictly necessary if "smooth adaptable" pairs of functions are used, opening the door to a wider class of mathematical models.
- Extrapolation is a "Free" Boost: Experiments confirm that adding the extrapolation step consistently makes the algorithm faster without requiring significantly more computation per step.
- Robustness: The algorithm proved effective even when the regularization term was weakly convex or had nonconvex sparsity constraints, areas where many other solvers struggle to remain stable.
Limitations and Future Work
While BPSGE shows strong performance, practical implementation requires careful tuning of the extrapolation parameter $\beta_k$. While the theory provides a range of valid values, finding the optimal setting for a specific problem often relies on heuristics. Additionally, while the Bregman kernel $\psi$ offers great flexibility, selecting the ideal kernel for novel problems remains an area for expert intuition. Extending the full global proof to more restrictive, complex geometric constraints also remains an open area for further study.
Summary updated