Simplifying Optimal Transport through Schatten-$p$ Regularization

• URL: http://arxiv.org/abs/2510.11910v1
• Date: Mon, 13 Oct 2025 20:22:28 GMT
• Title: Simplifying Optimal Transport through Schatten-$p$ Regularization
• Authors: Tyler Maunu,
• Abstract summary: We propose a new framework for recovering low-rank structure in optimal transport using Schatten-$p$ norm regularization.<n> Experiments on synthetic and real data demonstrate the method's efficiency, scalability, and ability to recover low-rank transport structures.
• Score: 3.545032646428251
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We propose a new general framework for recovering low-rank structure in optimal transport using Schatten-$p$ norm regularization. Our approach extends existing methods that promote sparse and interpretable transport maps or plans, while providing a unified and principled family of convex programs that encourage low-dimensional structure. The convexity of our formulation enables direct theoretical analysis: we derive optimality conditions and prove recovery guarantees for low-rank couplings and barycentric maps in simplified settings. To efficiently solve the proposed program, we develop a mirror descent algorithm with convergence guarantees for $p \geq 1$. Experiments on synthetic and real data demonstrate the method's efficiency, scalability, and ability to recover low-rank transport structures.

Related papers

• Adaptive Decentralized Composite Optimization via Three-Operator Splitting [8.547205551848462]
  The paper studies decentralized optimization over networks, where agents minimize a sum of it locally smooth (strongly) convex losses and plus a nonsmooth convex extended value term.<n>We propose decentralized methods wherein agents it adaptively adjust their stepsize via local backtracking procedures coupled with lightweight min-consensus protocols.
  arXiv  Detail & Related papers  (2026-02-19T16:59:34Z)
• Designing Ambiguity Sets for Distributionally Robust Optimization Using Structural Causal Optimal Transport [21.387312729118364]
  We propose incorporating structural equations, which include causal graph information, to enhance ambiguity sets.<n>We show how our method overcomes the curse of dimensionality in optimal transport problems, achieving faster shrinkage with-free order.
  arXiv  Detail & Related papers  (2025-10-01T07:26:47Z)
• Sharper Convergence Rates for Nonconvex Optimisation via Reduction Mappings [34.309687104447114]
  We show that well-designed reduction mappings improve curvature properties of the objective, leading to better-conditioned problems and theoretically faster convergence for gradient-based methods.<n>Our analysis unifies a range of scenarios where structural information at optimality is leveraged to accelerate convergence, offering a principled explanation for the empirical gains observed in such optimisation algorithms.
  arXiv  Detail & Related papers  (2025-06-10T04:03:59Z)
• Generalized Gradient Norm Clipping & Non-Euclidean $(L_0,L_1)$-Smoothness [51.302674884611335]
  This work introduces a hybrid non-Euclidean optimization method which generalizes norm clipping by combining steepest descent and conditional gradient approaches.<n>We discuss how to instantiate the algorithms for deep learning and demonstrate their properties on image classification and language modeling.
  arXiv  Detail & Related papers  (2025-06-02T17:34:29Z)
• A Novel Unified Parametric Assumption for Nonconvex Optimization [53.943470475510196]
  Non optimization is central to machine learning, but the general framework non convexity enables weak convergence guarantees too pessimistic compared to the other hand.<n>We introduce a novel unified assumption in non convex algorithms.
  arXiv  Detail & Related papers  (2025-02-17T21:25:31Z)
• Stable Nonconvex-Nonconcave Training via Linear Interpolation [51.668052890249726]
  This paper presents a theoretical analysis of linearahead as a principled method for stabilizing (large-scale) neural network training. We argue that instabilities in the optimization process are often caused by the nonmonotonicity of the loss landscape and show how linear can help by leveraging the theory of nonexpansive operators.
  arXiv  Detail & Related papers  (2023-10-20T12:45:12Z)
• Iterative Reweighted Least Squares Networks With Convergence Guarantees for Solving Inverse Imaging Problems [12.487990897680422]
  We present a novel optimization strategy for image reconstruction tasks under analysis-based image regularization. We parameterize such regularizers using potential functions that correspond to weighted extensions of the $ell_pp$-vector and $mathcalS_pp$ Schatten-matrix quasi-norms. We show that thanks to the convergence guarantees of our proposed minimization strategy, such optimization can be successfully performed with a memory-efficient implicit back-propagation scheme.
  arXiv  Detail & Related papers  (2023-08-10T17:59:46Z)
• G-TRACER: Expected Sharpness Optimization [1.2183405753834562]
  G-TRACER promotes generalization by seeking flat minima, and has a sound theoretical basis as an approximation to a natural-gradient descent based optimization of a generalized Bayes objective. We show that the method converges to a neighborhood of a local minimum of the unregularized objective, and demonstrate competitive performance on a number of benchmark computer vision and NLP datasets.
  arXiv  Detail & Related papers  (2023-06-24T09:28:49Z)
• 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)
• Fast Computation of Optimal Transport via Entropy-Regularized Extragradient Methods [75.34939761152587]
  Efficient computation of the optimal transport distance between two distributions serves as an algorithm that empowers various applications. This paper develops a scalable first-order optimization-based method that computes optimal transport to within $varepsilon$ additive accuracy.
  arXiv  Detail & Related papers  (2023-01-30T15:46:39Z)
• 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)
• Recovery Bounds on Class-Based Optimal Transport: A Sum-of-Norms Regularization Framework [21.037720934987483]
  We propose a convex OT program with a sum-of-norms regularization term, which provably recovers the underlying class structure under geometric assumptions. We provide a novel argument for the uniqueness of the optimum even in the absence of strong convexity. Our experiments show that the new regularizer not only results in a better preservation of the class structure in the data but also yields additional robustness to the data geometry.
  arXiv  Detail & Related papers  (2019-03-09T18:54:21Z)

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.