Robust computation of optimal transport by $\beta$-potential regularization

• URL: http://arxiv.org/abs/2212.13251v1
• Date: Mon, 26 Dec 2022 18:37:28 GMT
• Title: Robust computation of optimal transport by $\beta$-potential regularization
• Authors: Shintaro Nakamura, Han Bao, Masashi Sugiyama
• Abstract summary: Optimal transport (OT) has become a widely used tool in the machine learning field to measure the discrepancy between probability distributions. We propose regularizing OT with the beta-potential term associated with the so-called $beta$-divergence. We experimentally demonstrate that the transport matrix computed with our algorithm helps estimate a probability distribution robustly even in the presence of outliers.
• Score: 79.24513412588745
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Optimal transport (OT) has become a widely used tool in the machine learning field to measure the discrepancy between probability distributions. For instance, OT is a popular loss function that quantifies the discrepancy between an empirical distribution and a parametric model. Recently, an entropic penalty term and the celebrated Sinkhorn algorithm have been commonly used to approximate the original OT in a computationally efficient way. However, since the Sinkhorn algorithm runs a projection associated with the Kullback-Leibler divergence, it is often vulnerable to outliers. To overcome this problem, we propose regularizing OT with the \beta-potential term associated with the so-called $\beta$-divergence, which was developed in robust statistics. Our theoretical analysis reveals that the $\beta$-potential can prevent the mass from being transported to outliers. We experimentally demonstrate that the transport matrix computed with our algorithm helps estimate a probability distribution robustly even in the presence of outliers. In addition, our proposed method can successfully detect outliers from a contaminated dataset

Related papers

• Robust Barycenter Estimation using Semi-Unbalanced Neural Optimal Transport [84.51977664336056]
  We propose a novel, scalable approach for estimating the textitrobust continuous barycenter. Our method is framed as a $min$-$max$ optimization problem and is adaptable to textitgeneral cost function.
  arXiv  Detail & Related papers  (2024-10-04T23:27:33Z)
• A Specialized Semismooth Newton Method for Kernel-Based Optimal Transport [92.96250725599958]
  Kernel-based optimal transport (OT) estimators offer an alternative, functional estimation procedure to address OT problems from samples. We show that our SSN method achieves a global convergence rate of $O (1/sqrtk)$, and a local quadratic convergence rate under standard regularity conditions.
  arXiv  Detail & Related papers  (2023-10-21T18:48:45Z)
• Outlier-Robust Sparse Mean Estimation for Heavy-Tailed Distributions [42.6763105645717]
  Given a small number of corrupted samples, the goal is to efficiently compute a hypothesis that accurately approximates $mu$ with high probability. Our algorithm achieves the optimal error using a number of samples scaling logarithmically with the ambient dimension. Our analysis may be of independent interest, involving the delicate design of a (non-spectral) decomposition for positive semi-definite satisfying certain sparsity properties.
  arXiv  Detail & Related papers  (2022-11-29T16:13:50Z)
• Unbalanced Optimal Transport, from Theory to Numerics [0.0]
  We argue that unbalanced OT, entropic regularization and Gromov-Wasserstein (GW) can work hand-in-hand to turn OT into efficient geometric loss functions for data sciences. The main motivation for this review is to explain how unbalanced OT, entropic regularization and GW can work hand-in-hand to turn OT into efficient geometric loss functions for data sciences.
  arXiv  Detail & Related papers  (2022-11-16T09:02:52Z)
• Outlier-Robust Optimal Transport: Duality, Structure, and Statistical Applications [25.410110072480187]
  Wasserstein distances are sensitive to outliers in the considered distributions. We propose a new outlier-robust Wasserstein distance $mathsfW_pvarepsilon$ which allows for $varepsilon$ outlier mass to be removed from each contaminated distribution.
  arXiv  Detail & Related papers  (2021-11-02T04:05:45Z)
• Optimal policy evaluation using kernel-based temporal difference methods [78.83926562536791]
  We use kernel Hilbert spaces for estimating the value function of an infinite-horizon discounted Markov reward process. We derive a non-asymptotic upper bound on the error with explicit dependence on the eigenvalues of the associated kernel operator. We prove minimax lower bounds over sub-classes of MRPs.
  arXiv  Detail & Related papers  (2021-09-24T14:48:20Z)
• SLOE: A Faster Method for Statistical Inference in High-Dimensional Logistic Regression [68.66245730450915]
  We develop an improved method for debiasing predictions and estimating frequentist uncertainty for practical datasets. Our main contribution is SLOE, an estimator of the signal strength with convergence guarantees that reduces the computation time of estimation and inference by orders of magnitude.
  arXiv  Detail & Related papers  (2021-03-23T17:48:56Z)
• $\gamma$-ABC: Outlier-Robust Approximate Bayesian Computation Based on a Robust Divergence Estimator [95.71091446753414]
  We propose to use a nearest-neighbor-based $gamma$-divergence estimator as a data discrepancy measure. Our method achieves significantly higher robustness than existing discrepancy measures.
  arXiv  Detail & Related papers  (2020-06-13T06:09:27Z)
• Regularized Optimal Transport is Ground Cost Adversarial [34.81915836064636]
  We show that regularization of the optimal transport problem can be interpreted as ground cost adversarial. This gives access to a robust dissimilarity measure on the ground space, which can in turn be used in other applications.
  arXiv  Detail & Related papers  (2020-02-10T17:28: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.