dc.contributor.author | Thibault, Alexis | |
dc.contributor.author | Chizat, Lénaïc | |
dc.contributor.author | Dossal, Charles | |
dc.contributor.author | Papadakis, Nicolas | |
dc.date.accessioned | 2020-02-03T14:32:18Z | |
dc.date.available | 2020-02-03T14:32:18Z | |
dc.date.issued | 2017 | |
dc.identifier.uri | https://basepub.dauphine.fr/handle/123456789/20514 | |
dc.language.iso | en | en |
dc.subject | Sinkhorn-Knopp Algorithm | en |
dc.subject.ddc | 621.3 | en |
dc.title | Overrelaxed Sinkhorn-Knopp Algorithm for Regularized Optimal Transport | en |
dc.type | Communication / Conférence | |
dc.description.abstracten | This article describes a method for quickly computing the solution to the regularized optimal transport problem. It generalizes and improves upon the widely-used iterative Bregman projections algorithm (or Sinkhorn-Knopp algorithm). The idea is to overrelax the Bregman projection operators, allowing for faster convergence. In practice this corresponds to elevating the diagonal scaling factors to a given power, at each step of the algorithm. We propose a simple method for establishing global convergence by ensuring the decrease of a Lyapunov function at each step. An adaptive choice of overrelaxation parameter based on the Lyapunov function is constructed. We also suggest a heuristic to choose a suitable asymptotic overrelaxation parameter, based on a local convergence analysis. Our numerical experiments show a gain in convergence speed by an order of magnitude in certain regimes. | en |
dc.relation.ispartofdate | 2017 | |
dc.subject.ddclabel | Traitement du signal | en |
dc.relation.conftitle | NIPS'17 Workshop on Optimal Transport & Machine Learning | en |
dc.relation.confdate | 2017-12 | |
dc.relation.confcity | Long Beach | en |
dc.relation.confcountry | United States | en |
dc.relation.forthcoming | non | en |
dc.description.ssrncandidate | non | en |
dc.description.halcandidate | non | en |
dc.description.readership | recherche | en |
dc.description.audience | International | en |
dc.relation.Isversionofjnlpeerreviewed | non | en |
dc.relation.Isversionofjnlpeerreviewed | non | en |
dc.date.updated | 2020-02-03T14:17:45Z | |
hal.person.labIds | 91477 | |
hal.person.labIds | 60 | |
hal.person.labIds | 1954 | |
hal.person.labIds | 27730 | |