Riemannian Optimization on the Oblique Manifold for Sparse Simplex Constraints via Multiplicative Updates

• URL: http://arxiv.org/abs/2503.24075v2
• Date: Wed, 21 May 2025 13:54:57 GMT
• Title: Riemannian Optimization on the Oblique Manifold for Sparse Simplex Constraints via Multiplicative Updates
• Authors: Flavia Esposito, Andersen Ang,
• Abstract summary: Low-rank optimization problems with sparse simplex constraints involve variables that must satisfy nonnegativity, sparsity, and sum-to-one conditions.<n>We propose a novel manifold optimization approach to tackle these problems efficiently.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Low-rank optimization problems with sparse simplex constraints involve variables that must satisfy nonnegativity, sparsity, and sum-to-one conditions, making their optimization particularly challenging due to the interplay between low-rank structures and constraints. These problems arise in various applications, including machine learning, signal processing, environmental fields, and computational biology. In this paper, we propose a novel manifold optimization approach to tackle these problems efficiently. Our method leverages the geometry of oblique rotation manifolds to reformulate the problem and introduces a new Riemannian optimization method based on Riemannian gradient descent that strictly maintains the simplex constraints. By exploiting the underlying manifold structure, our approach improves optimization efficiency. Experiments on synthetic datasets compared to standard Euclidean and Riemannian methods show the effectiveness of the proposed method.

Related papers

• Efficient Optimization with Orthogonality Constraint: a Randomized Riemannian Submanifold Method [10.239769272138995]
  We propose a novel approach to solve problems in machine learning.<n>We introduce two strategies for updating the random submanifold.<n>We show how our approach can be generalized to a wide variety of problems.
  arXiv  Detail & Related papers  (2025-05-18T11:46:44Z)
• Riemannian Optimization on Relaxed Indicator Matrix Manifold [83.13494760649874]
  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) We provide several methods of Retraction, including a fast Retraction method to obtain geodesics.
  arXiv  Detail & Related papers  (2025-03-26T12:45:52Z)
• Implicit Riemannian Optimism with Applications to Min-Max Problems [23.421903887404618]
  We introduce an optimistic online learning algorithm for Hadamard problems. Our method can handle in-mani-fold constraints, and matches the best known bounds on the Euclidean setting.
  arXiv  Detail & Related papers  (2025-01-30T14:31:28Z)
• Improved Approximation Algorithms for Low-Rank Problems Using Semidefinite Optimization [2.1485350418225244]
  We construct an analogous relax-then-sample strategy for low-rank optimization problems.<n>We derive a semidefinite relaxation and a randomized rounding scheme, which obtains near-optimal solutions.<n>We numerically illustrate the effectiveness and scalability of our relaxation and our sampling scheme.
  arXiv  Detail & Related papers  (2025-01-06T11:31:41Z)
• Structured Regularization for Constrained Optimization on the SPD Manifold [1.1126342180866644]
  We introduce a class of structured regularizers, based on symmetric gauge functions, which allow for solving constrained optimization on the SPD manifold with faster unconstrained methods. We show that our structured regularizers can be chosen to preserve or induce desirable structure, in particular convexity and "difference of convex" structure.
  arXiv  Detail & Related papers  (2024-10-12T22:11:22Z)
• Symplectic Stiefel manifold: tractable metrics, second-order geometry and Newton's methods [1.190653833745802]
  We develop explicit second-order geometry and Newton's methods on the symplectic Stiefel manifold. We then solve the resulting Newton equation, as the central step of Newton's methods. Various numerical experiments are presented to validate the proposed methods.
  arXiv  Detail & Related papers  (2024-06-20T13:26:06Z)
• 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)
• Improving Diffusion Models for Inverse Problems Using Optimal Posterior Covariance [52.093434664236014]
  Recent diffusion models provide a promising zero-shot solution to noisy linear inverse problems without retraining for specific inverse problems. Inspired by this finding, we propose to improve recent methods by using more principled covariance determined by maximum likelihood estimation.
  arXiv  Detail & Related papers  (2024-02-03T13:35:39Z)
• Riemannian stochastic optimization methods avoid strict saddle points [68.80251170757647]
  We show that policies under study avoid strict saddle points / submanifolds with probability 1. This result provides an important sanity check as it shows that, almost always, the limit state of an algorithm can only be a local minimizer.
  arXiv  Detail & Related papers  (2023-11-04T11:12:24Z)
• Linearization Algorithms for Fully Composite Optimization [61.20539085730636]
  This paper studies first-order algorithms for solving fully composite optimization problems convex compact sets. We leverage the structure of the objective by handling differentiable and non-differentiable separately, linearizing only the smooth parts.
  arXiv  Detail & Related papers  (2023-02-24T18:41:48Z)
• Simplifying Momentum-based Positive-definite Submanifold Optimization with Applications to Deep Learning [24.97120654216651]
  We show how to solve difficult differential equations with momentum on a submanifold. We do so by proposing a generalized version of the Riemannian normal coordinates. We use our approach to simplify existing approaches for structured covariances and develop matrix-inverse-free $2textnd$orders for deep learning with low precision by using only matrix multiplications.
  arXiv  Detail & Related papers  (2023-02-20T03:31:11Z)
• Riemannian Optimization for Variance Estimation in Linear Mixed Models [0.0]
  We take a completely novel view on parameter estimation in linear mixed models by exploiting the intrinsic geometry of the parameter space. Our approach yields a higher quality of the variance parameter estimates compared to existing approaches.
  arXiv  Detail & Related papers  (2022-12-18T13:08:45Z)
• Consistent Approximations in Composite Optimization [0.0]
  We develop a framework for consistent approximations of optimization problems. The framework is developed for a broad class of optimizations. A programming analysis method illustrates extended nonlinear programming solutions.
  arXiv  Detail & Related papers  (2022-01-13T23:57:08Z)
• On Riemannian Approach for Constrained Optimization Model in Extreme Classification Problems [2.7436792484073638]
  A constrained optimization problem is formulated as an optimization problem on matrix manifold. The proposed approach is tested on several real world large scale multi-label datasets.
  arXiv  Detail & Related papers  (2021-09-30T11:28:35Z)
• Optimization on manifolds: A symplectic approach [127.54402681305629]
  We propose a dissipative extension of Dirac's theory of constrained Hamiltonian systems as a general framework for solving optimization problems. Our class of (accelerated) algorithms are not only simple and efficient but also applicable to a broad range of contexts.
  arXiv  Detail & Related papers  (2021-07-23T13:43:34Z)
• On Constraints in First-Order Optimization: A View from Non-Smooth Dynamical Systems [99.59934203759754]
  We introduce a class of first-order methods for smooth constrained optimization. Two distinctive features of our approach are that projections or optimizations over the entire feasible set are avoided. The resulting algorithmic procedure is simple to implement even when constraints are nonlinear.
  arXiv  Detail & Related papers  (2021-07-17T11:45:13Z)
• Unified Convergence Analysis for Adaptive Optimization with Moving Average Estimator [75.05106948314956]
  We show that an increasing large momentum parameter for the first-order moment is sufficient for adaptive scaling.<n>We also give insights for increasing the momentum in a stagewise manner in accordance with stagewise decreasing step size.
  arXiv  Detail & Related papers  (2021-04-30T08:50:24Z)
• Divide and Learn: A Divide and Conquer Approach for Predict+Optimize [50.03608569227359]
  The predict+optimize problem combines machine learning ofproblem coefficients with a optimization prob-lem that uses the predicted coefficients. We show how to directlyexpress the loss of the optimization problem in terms of thepredicted coefficients as a piece-wise linear function. We propose a novel divide and algorithm to tackle optimization problems without this restriction and predict itscoefficients using the optimization loss.
  arXiv  Detail & Related papers  (2020-12-04T00:26:56Z)
• Conditional gradient methods for stochastically constrained convex minimization [54.53786593679331]
  We propose two novel conditional gradient-based methods for solving structured convex optimization problems. The most important feature of our framework is that only a subset of the constraints is processed at each iteration. Our algorithms rely on variance reduction and smoothing used in conjunction with conditional gradient steps, and are accompanied by rigorous convergence guarantees.
  arXiv  Detail & Related papers  (2020-07-07T21:26:35Z)
• Support recovery and sup-norm convergence rates for sparse pivotal estimation [79.13844065776928]
  In high dimensional sparse regression, pivotal estimators are estimators for which the optimal regularization parameter is independent of the noise level. We show minimax sup-norm convergence rates for non smoothed and smoothed, single task and multitask square-root Lasso-type estimators.
  arXiv  Detail & Related papers  (2020-01-15T16:11:04Z)

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.