Riemannian Optimization on Relaxed Indicator Matrix Manifold

• URL: http://arxiv.org/abs/2503.20505v2
• Date: Fri, 11 Apr 2025 10:21:06 GMT
• Title: Riemannian Optimization on Relaxed Indicator Matrix Manifold
• Authors: Jinghui Yuan, Fangyuan Xie, Feiping Nie, Xuelong Li,
• Abstract summary: The indicator matrix plays an important role in machine learning, but optimizing it is an NP-hard problem.<n>We propose a new relaxation of the indicator matrix and prove that this relaxation forms a manifold, which we call the Relaxed Indicator Matrix Manifold (RIM manifold)<n>We provide several methods of Retraction, including a fast Retraction method to obtain geodesics.
• Score: 83.13494760649874
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: The indicator matrix plays an important role in machine learning, but optimizing it is an NP-hard problem. We propose a new relaxation of the indicator matrix and prove that this relaxation forms a manifold, which we call the Relaxed Indicator Matrix Manifold (RIM manifold). Based on Riemannian geometry, we develop a Riemannian toolbox for optimization on the RIM manifold. Specifically, we provide several methods of Retraction, including a fast Retraction method to obtain geodesics. We point out that the RIM manifold is a generalization of the double stochastic manifold, and it is much faster than existing methods on the double stochastic manifold, which has a complexity of \( \mathcal{O}(n^3) \), while RIM manifold optimization is \( \mathcal{O}(n) \) and often yields better results. We conducted extensive experiments, including image denoising, with millions of variables to support our conclusion, and applied the RIM manifold to Ratio Cut, we provide a rigorous convergence proof and achieve clustering results that outperform the state-of-the-art methods. Our Code in \href{https://github.com/Yuan-Jinghui/Riemannian-Optimization-on-Relaxed-Indicator-Matrix-Manifold}{here}.

Related papers

• RMLR: Extending Multinomial Logistic Regression into General Geometries [64.16104856124029]
  Our framework only requires minimal geometric properties, thus exhibiting broad applicability. We develop five families of SPD MLRs under five types of power-deformed metrics. On rotation matrices we propose Lie MLR based on the popular bi-invariant metric.
  arXiv  Detail & Related papers  (2024-09-28T18:38:21Z)
• Riemannian coordinate descent algorithms on matrix manifolds [12.05722932030768]
  We provide a general framework for developing computationally efficient coordinate descent (CD) algorithms on matrix manifold. We propose CD algorithms for various manifold such as Stiefel, Grassmann, (generalized) hyperbolic, symplectic, and symmetric positive (semi)definite. We analyze their convergence and complexity, and empirically illustrate their efficacy in several applications.
  arXiv  Detail & Related papers  (2024-06-04T11:37:11Z)
• Riemannian Bilevel Optimization [35.42472057648458]
  We focus in particular on batch and gradient-based methods, with the explicit goal of avoiding second-order information. We propose and analyze $mathrmRF2SA$, a method that leverages first-order gradient information. We provide explicit convergence rates for reaching $epsilon$-stationary points under various setups.
  arXiv  Detail & Related papers  (2024-05-22T20:49:01Z)
• Streamlining in the Riemannian Realm: Efficient Riemannian Optimization with Loopless Variance Reduction [4.578425862931332]
  This study focuses on the crucial reduction mechanism used in both Euclidean and Riemannian settings. Motivated by Euclidean methods, we introduce R-based methods to replace the outer loop with computation triggered by a coin flip. Using R- as a framework, we demonstrate its applicability to various important settings.
  arXiv  Detail & Related papers  (2024-03-11T12:49:37Z)
• FORML: A Riemannian Hessian-free Method for Meta-learning on Stiefel Manifolds [4.757859522106933]
  This paper introduces a Hessian-free approach that uses a first-order approximation of derivatives on the Stiefel manifold. Our method significantly reduces the computational load and memory footprint.
  arXiv  Detail & Related papers  (2024-02-28T10:57:30Z)
• Curvature-Independent Last-Iterate Convergence for Games on Riemannian Manifolds [77.4346324549323]
  We show that a step size agnostic to the curvature of the manifold achieves a curvature-independent and linear last-iterate convergence rate. To the best of our knowledge, the possibility of curvature-independent rates and/or last-iterate convergence has not been considered before.
  arXiv  Detail & Related papers  (2023-06-29T01:20:44Z)
• The Dynamics of Riemannian Robbins-Monro Algorithms [101.29301565229265]
  We propose a family of Riemannian algorithms generalizing and extending the seminal approximation framework of Robbins and Monro. Compared to their Euclidean counterparts, Riemannian algorithms are much less understood due to lack of a global linear structure on the manifold. We provide a general template of almost sure convergence results that mirrors and extends the existing theory for Euclidean Robbins-Monro schemes.
  arXiv  Detail & Related papers  (2022-06-14T12:30:11Z)
• First-Order Algorithms for Min-Max Optimization in Geodesic Metric Spaces [93.35384756718868]
  min-max algorithms have been analyzed in the Euclidean setting. We prove that the extraiteient (RCEG) method corrected lastrate convergence at a linear rate.
  arXiv  Detail & Related papers  (2022-06-04T18:53:44Z)
• Automatic differentiation for Riemannian optimization on low-rank matrix and tensor-train manifolds [71.94111815357064]
  In scientific computing and machine learning applications, matrices and more general multidimensional arrays (tensors) can often be approximated with the help of low-rank decompositions. One of the popular tools for finding the low-rank approximations is to use the Riemannian optimization.
  arXiv  Detail & Related papers  (2021-03-27T19:56:00Z)
• Riemannian Stochastic Proximal Gradient Methods for Nonsmooth Optimization over the Stiefel Manifold [7.257751371276488]
  R-ProxSGD and R-ProxSPB are generalizations of proximal SGD and proximal SpiderBoost. R-ProxSPB algorithm finds an $epsilon$-stationary point with $O(epsilon-3)$ IFOs in the online case, and $O(n+sqrtnepsilon-3)$ IFOs in the finite-sum case.
  arXiv  Detail & Related papers  (2020-05-03T23:41:35Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.