TL;DR
This paper introduces a novel Riemannian smoothing steepest descent (RSSD) method to tackle a challenging class of optimization problems: minimizing non-Lipschitz, nonconvex functions on curved geometric spaces (submanifolds). The method offers theoretical guarantees of convergence to stationary points and demonstrates strong performance in numerical experiments for tasks like sparse signal recovery.
What Problem Does This Paper Address?
Many real-world problems, particularly in signal processing and computer vision, involve optimizing functions that are not "well-behaved." Specifically, these functions can be:
- Nonconvex: They have multiple local minima, making it hard to find the global best solution.
- Non-Lipschitz: Their rate of change can be unbounded, which breaks many standard optimization algorithms that rely on predictable function behavior.
- On Submanifolds: The optimization is constrained to a curved geometric space (like a sphere or a more complex manifold) rather than a simple flat Euclidean space.
Existing methods often struggle with the combination of these properties. While some techniques exist for non-Lipschitz optimization in flat spaces or for smooth optimization on manifolds, a unified approach for non-Lipschitz optimization on submanifolds has been lacking. This paper aims to fill that gap by developing a robust and theoretically sound algorithm.
Methods
The core contribution is the Riemannian Smoothing Steepest Descent (RSSD) method. Here's how it works:
- Smoothing: The non-Lipschitz objective function is approximated by a sequence of smooth functions. This is a common technique for handling non-Lipschitz functions, where a "smoothing parameter" gradually reduces to zero, making the approximation closer to the original function.
- Riemannian Geometry: The optimization is performed on a Riemannian manifold. This involves using tools like retractions (ways to "step" from a tangent space back onto the manifold) and Riemannian gradients (the equivalent of gradients on curved spaces).
- Steepest Descent: At each step, the algorithm moves in the direction of steepest descent of the smoothed function, projected onto the tangent space of the manifold.
- Adaptive Parameters: The algorithm adaptively adjusts both the smoothing parameter and a step-size parameter to ensure convergence.
- Theoretical Guarantees: The authors define new concepts like "Riemannian generalized subdifferentials" and "Riemannian gradient sub-consistency" to formally analyze the algorithm's behavior. They prove that any sequence generated by RSSD converges to a stationary point of the original non-Lipschitz problem, and under certain conditions, to a "Riemannian limiting stationary point."
Datasets
The paper does not introduce new datasets. Instead, it uses synthetic data generated for two specific problem types:
- Finding a Sparse Vector in a Subspace (FSV): This involves creating data to test the recovery of sparse signals from linear measurements, constrained to a subspace.
- Sparsely-Used Orthogonal Complete Dictionary Learning (ODL): This involves generating data to learn a dictionary that can sparsely represent given data points, with the dictionary itself being orthogonal.
These problems are formulated using variations of the $l_p$ quasi-norm minimization ($0 < p < 1$), which is inherently non-Lipschitz.
Key Insights and Ideas
- Bridging the Gap: The paper successfully extends smoothing techniques for non-Lipschitz optimization from Euclidean spaces to Riemannian submanifolds, a significant theoretical advancement.
- New Theoretical Tools: The introduction and analysis of "Riemannian generalized subdifferentials" and "Riemannian gradient sub-consistency" provide a crucial framework for understanding convergence on manifolds.
- Practical Convergence: The RSSD method is shown to converge to stationary points, which are necessary conditions for local optimality, even for these difficult non-Lipschitz problems on curved spaces.
- Efficiency Demonstrated: Numerical experiments show that the proposed RSSD method is competitive and often superior to existing methods on challenging benchmark problems.
Key Results
- Theoretical Convergence: The paper proves that the RSSD algorithm converges to stationary points of the non-Lipschitz optimization problem on submanifolds. Under the condition of Riemannian gradient sub-consistency, it further guarantees convergence to Riemannian limiting stationary points.
- Numerical Performance:
- For the $l_1$ minimization model (a Lipschitz relaxation of the sparse problem), the RSSD method (and its variant RSSD-g) consistently outperformed or matched existing methods (RGS, RBFGS) in terms of success rate across various problem sizes and tolerances. For instance, in Table 1, RSSD-g achieved 39 out of 64 best results.
- For the $l_p$ minimization model ($0 < p < 1$), which is the non-Lipschitz version, the RSSD method was the only one tested. The results in Tables 3 and 4 show that using the $l_p$ norm can lead to better performance than the $l_1$ norm, especially when an appropriate $p$ is chosen.
- In the Dictionary Learning experiments (Table 5 and Figures 1-2), the RSSD method solving the $l_p$ model ($p=0.001$) achieved significantly better sparsity levels compared to other Riemannian methods solving the $l_1$ model, demonstrating its effectiveness for highly sparse recovery.
Limitations and Future Work
- Assumption of Submanifold Structure: The method relies on the ability to perform retractions and compute Riemannian gradients, which requires knowledge of the manifold's geometric structure.
- Parameter Tuning: While the paper proposes an adaptive strategy, the performance can still be sensitive to initial parameter choices (e.g., $\theta_\mu, \theta_\delta$), and the RSSD-g variant highlights the benefit of exploring different parameter combinations.
- Future Work: The authors suggest exploring applications in areas like signal processing and computer vision, and potentially extending the method to more complex manifold structures or problem formulations. The numerical results also hint at the potential for further improvements by carefully tuning the parameters controlling the smoothing and step-size sequences.
Summary updated