Gradient projection algorithms improve optimization on curved surfaces
Retraction-Based Gradient Projection Algorithms on Manifolds
Machine Learning
Summary
Optimizing a problem often involves moving straight towards the best solution, but sometimes the problem lives on a curved space called a manifold, making things tricky. The authors came up with a way to do these optimization steps on curved spaces using special moves called retractions. They also proved their methods will reliably get closer to the best solution and tested them on tasks like filling in missing parts of images. This helps solve problems where data naturally lies on curved shapes, improving accuracy and efficiency.
What this means in practice
- •For computer vision engineers: Complete missing or corrupted image data by efficiently optimizing low-rank approximations with reliable convergence on curved data spaces.
- •For machine learning practitioners: Optimize models or data that lie on curved geometries by applying retraction-based gradient projection algorithms for improved performance.
Authors
Conglong Xu, Hao Wu
Abstract
We introduce a framework for retraction-based convex optimization on Riemannian manifolds, which includes a notion of retraction-specific convex sets and retraction-based gradient projection algorithms. The standard theory of gradient projection algorithms generalizes easily to this framework. Within this framework, we establish convergence results for retraction-based gradient projection algorithms with various stepsize rules. As an application, we use our framework to study the weighted low-rank approximation. We also provide numerical validation of our convergence results on the image completion task.