Related papers: Optimization over the intersection of manifolds

Optimization over the intersection of manifolds

URL: http://arxiv.org/abs/2605.22736v1
Date: Thu, 21 May 2026 17:08:00 GMT
Title: Optimization over the intersection of manifolds
Abstract summary: We prove that the regularities -- clean intersection and intrinsicity -- are equivalent, which yields a tractable projection onto the tangent space of the intersection.<n>We propose a geometric method that employs a retraction on only one manifold and updates the intersection along two directions.<n>Under intrinsicity, we derive the convergence rate for both the feasibility and optimality measures, and show that every accumulation point is first-order stationary.
Score: 8.902244235284229
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: Optimization over the intersection of two manifolds arises in a broad range of applications, but is hindered by the coupled geometry of the feasible region. In this paper, we prove that the regularities -- clean intersection and intrinsic transversality -- are equivalent, which yields a tractable projection onto the tangent space of the intersection. Therefore, we propose a geometric method that employs a retraction on only one manifold and updates the iterate along two orthogonal directions. Specifically, the iterates stay on one manifold, and the two directions are responsible for asymptotically approaching the other manifold and decreasing the objective function, respectively. Under intrinsic transversality, we derive the convergence rate for both the feasibility and optimality measures, and show that every accumulation point is first-order stationary. Numerical experiments on problems stemming from sparse and low-rank optimization, including fitting spherical data, approximating hyperbolic embeddings on real data, and computing compressed modes, demonstrate the effectiveness of the proposed method.

Related papers

Fitting Unknown Number of Hyperplanes with Manifold Optimization [57.48093263119306]
Fitting unknown number of linearplanes to data is a fundamental yet challenging problem in machine learning.<n>Existing approaches often struggle with optimum optima or lack geometric consistency.
arXiv Detail & Related papers (2026-05-27T14:02:20Z)
Revisiting Zeroth-Order Optimization: Minimum-Variance Two-Point Estimators and Directionally Aligned Perturbations [57.179679246370114]
We identify the distribution of random perturbations that minimizes the estimator's variance as the perturbation stepsize tends to zero.<n>Our findings reveal that such desired perturbations can align directionally with the true gradient, instead of maintaining a fixed length.
arXiv Detail & Related papers (2025-10-22T19:06:39Z)
Decentralized Online Riemannian Optimization Beyond Hadamard Manifolds [9.940555460165545]
We analyze a curvature-aware geodesic step that enables a convergence beyond Hadamard linear distances.<n>We employ gradient, smoothing techniques, and we demonstrate $O(sqrtT)$ regret bound through the same subity analysis.
arXiv Detail & Related papers (2025-09-09T14:14:46Z)
Sampling and estimation on manifolds using the Langevin diffusion [45.57801520690309]
Two estimators of linear functionals of $mu_phi $ based on the discretized Markov process are considered.<n>Error bounds are derived for sampling and estimation using a discretization of an intrinsically defined Langevin diffusion.
arXiv Detail & Related papers (2023-12-22T18:01:11Z)
Warped geometric information on the optimisation of Euclidean functions [43.43598316339732]
We consider optimisation of a real-valued function defined in a potentially high-dimensional Euclidean space. We find the function's optimum along a manifold with a warped metric. Our proposed algorithm, using 3rd-order approximation of geodesics, tends to outperform standard Euclidean gradient-based counterparts.
arXiv Detail & Related papers (2023-08-16T12:08:50Z)
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)
Lifting the Convex Conjugate in Lagrangian Relaxations: A Tractable Approach for Continuous Markov Random Fields [53.31927549039624]
We show that a piecewise discretization preserves better contrast from existing discretization problems. We apply this theory to the problem of matching two images.
arXiv Detail & Related papers (2021-07-13T12:31:06Z)
Matrix factorisation and the interpretation of geodesic distance [6.445605125467574]
Given a graph or similarity matrix, we consider the problem of recovering a notion of true distance between the nodes. We show that this can be accomplished in two steps: matrix factorisation, followed by nonlinear dimension reduction.
arXiv Detail & Related papers (2021-06-02T16:11:33Z)
Random extrapolation for primal-dual coordinate descent [61.55967255151027]
We introduce a randomly extrapolated primal-dual coordinate descent method that adapts to sparsity of the data matrix and the favorable structures of the objective function. We show almost sure convergence of the sequence and optimal sublinear convergence rates for the primal-dual gap and objective values, in the general convex-concave case.
arXiv Detail & Related papers (2020-07-13T17:39:35Z)
Manifold Learning via Manifold Deflation [105.7418091051558]
dimensionality reduction methods provide a valuable means to visualize and interpret high-dimensional data. Many popular methods can fail dramatically, even on simple two-dimensional Manifolds. This paper presents an embedding method for a novel, incremental tangent space estimator that incorporates global structure as coordinates. Empirically, we show our algorithm recovers novel and interesting embeddings on real-world and synthetic datasets.
arXiv Detail & Related papers (2020-07-07T10:04:28Z)

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