Sample complexity of unbalanced entropic OT

• URL: http://arxiv.org/abs/2606.24987v1
• Date: Tue, 23 Jun 2026 14:25:47 GMT
• Title: Sample complexity of unbalanced entropic OT
• Abstract summary: This paper studies the sample complexity of entropic unbalanced OT at the level of the optimal coupling.<n>We develop a translation-invariant dual formulation, prove compactness and strong convexity properties for the intrinsic dual variables.<n>The results clarify why regularization is a practical necessity in machine learning applications.
• Score: 19.649505951280137
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Optimal transport (OT) has become a central language for comparing probability measures, but exact balanced OT is often both too rigid for data with missing, created, or destroyed mass and subject to unfavorable high-dimensional sample complexity. Entropic regularization and unbalanced relaxations address these limitations in complementary ways. Entropy smooths the geometry, improves statistical behavior, and enables fast Sinkhorn-type algorithms, while unbalanced marginal penalties replace hard conservation constraints by divergence terms adapted to noisy empirical data. This paper studies the sample complexity of entropic unbalanced OT at the level of the optimal coupling, rather than only the scalar transport value. We develop a translation-invariant dual formulation, prove compactness and strong convexity properties for the intrinsic dual variables, and convert these geometric estimates into high-probability finite-sample bounds for empirical couplings. The results clarify why regularization is a practical necessity in machine learning applications: it softens the curse of dimensionality, reduces the number of samples needed for stable transport estimation, and keeps the resulting estimators compatible with scalable Sinkhorn-type solvers.

Related papers

• Two-Step MV-DeepONet: Probabilistic Operator Learning for Uncertainty Propagation Driven by Random Input Fields [2.110303171517621]
  We develop a two-step mean-variance DeepONet (two-step MV-DeepONet) through two principal modifications.<n>We show improved generalization, more structured uncertainty bands, and accurate recovery of off-diagonal correlation patterns compared with Prob-DeepONet.
  arXiv  Detail & Related papers  (2026-08-10T03:21:10Z)
• Semi-Supervised Conditional Generative Learning through Stochastic Interpolation and Sufficient Representations [12.299177496689621]
  We propose a semi-supervised framework combining conditional intrinsic with low-dimensional latent representations.<n>RepG decomposes generation into two stages: label-dependent latent sampling and high-dimensional reconstruction.
  arXiv  Detail & Related papers  (2026-07-18T09:21:53Z)
• Achieving $\widetilde{O}(1/ε)$ Sample Complexity for Bilinear Systems Identification under Bounded Noises [2.6857362061342998]
  This paper studies finite-sample set-membership identification for discrete-time bilinear systems under bounded symmetric log-cavecon disturbances.<n>Compared with existing finite-sample results for linear systems, we consider the more challenging bilinear setting with trajectory-dependent regressors and allow marginally stable dynamics with mean-square state growth.
  arXiv  Detail & Related papers  (2026-03-21T13:40:01Z)
• Stability and Generalization of Push-Sum Based Decentralized Optimization over Directed Graphs [55.77845440440496]
  Push-based decentralized communication enables optimization over communication networks, where information exchange may be asymmetric.<n>We develop a unified uniform-stability framework for the Gradient Push (SGP) algorithm.<n>A key technical ingredient is an imbalance-aware generalization bound through two quantities.
  arXiv  Detail & Related papers  (2026-02-24T05:32:03Z)
• Equivariant Evidential Deep Learning for Interatomic Potentials [55.6997213490859]
  Uncertainty quantification is critical for assessing the reliability of machine learning interatomic potentials in molecular dynamics simulations.<n>Existing UQ approaches for MLIPs are often limited by high computational cost or suboptimal performance.<n>We propose textitEquivariant Evidential Deep Learning for Interatomic Potentials ($texte2$IP), a backbone-agnostic framework that models atomic forces and their uncertainty jointly.
  arXiv  Detail & Related papers  (2026-02-11T02:00:25Z)
• Geometry-Aware Optimal Transport: Fast Intrinsic Dimension and Wasserstein Distance Estimation [32.357350666094156]
  We introduce a tuning-free estimator of $textOT_c(, hat)$ that utilizes the semi-dual OT functional and, remarkably, requires no OT solver.<n>This framework unlocks significant computational and statistical advantages in practice.<n> Numerical experiments demonstrate that our geometry-aware pipeline effectively mitigates the discretization error bottleneck.
  arXiv  Detail & Related papers  (2026-02-04T08:56:28Z)
• Variational Entropic Optimal Transport [67.76725267984578]
  We propose Variational Entropic Optimal Transport (VarEOT) for domain translation problems.<n>VarEOT is based on an exact variational reformulation of the log-partition $log mathbbE[exp(cdot)$ as a tractable generalization over an auxiliary positive normalizer.<n> Experiments on synthetic data and unpaired image-to-image translation demonstrate competitive or improved translation quality.
  arXiv  Detail & Related papers  (2026-02-02T15:48:44Z)
• 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)
• Neural Optimal Transport Meets Multivariate Conformal Prediction [58.43397908730771]
  We propose a framework for conditional vectorile regression (CVQR)<n>CVQR combines neural optimal transport with quantized optimization, and apply it to predictions.
  arXiv  Detail & Related papers  (2025-09-29T19:50:19Z)
• ROTI-GCV: Generalized Cross-Validation for right-ROTationally Invariant Data [5.830619388189558]
  Two key tasks in high-dimensional regularized regression are tuning the regularization strength for accurate predictions and estimating the out-of-sample risk.<n>We introduce a new framework, ROTI-GCV, for reliably performing cross-validation under challenging conditions.
  arXiv  Detail & Related papers  (2024-06-17T15:50:00Z)
• Distributionally robust risk evaluation with a causality constraint and structural information [0.0]
  We approximate test functions by neural networks and prove the sample complexity with Rademacher complexity.<n>Our framework outperforms the classic counterparts in the distributionally robust portfolio selection problem.
  arXiv  Detail & Related papers  (2022-03-20T14:48:37Z)
• On the Double Descent of Random Features Models Trained with SGD [78.0918823643911]
  We study properties of random features (RF) regression in high dimensions optimized by gradient descent (SGD) We derive precise non-asymptotic error bounds of RF regression under both constant and adaptive step-size SGD setting. We observe the double descent phenomenon both theoretically and empirically.
  arXiv  Detail & Related papers  (2021-10-13T17:47:39Z)

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.