Show simple item record

Capacity Constrained Entropic Optimal Transport, Sinkhorn Saturated Domain Out-Summation and Vanishing Temperature

hal.structure.identifierCEntre de REcherches en MAthématiques de la DEcision [CEREMADE]
dc.contributor.authorBenamou, Jean-David*
hal.structure.identifierCEntre de REcherches en MAthématiques de la DEcision [CEREMADE]
dc.contributor.authorMartinet, Mélanie*
dc.date.accessioned2020-06-12T09:15:18Z
dc.date.available2020-06-12T09:15:18Z
dc.date.issued2020-05
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/20879
dc.language.isoenen
dc.subjectEntropic regularizationen
dc.subjectSinkhorn Algorithmen
dc.subjectOptimal transporten
dc.subjectConvex optimizationen
dc.subject.ddc515en
dc.titleCapacity Constrained Entropic Optimal Transport, Sinkhorn Saturated Domain Out-Summation and Vanishing Temperatureen
dc.typeDocument de travail / Working paper
dc.description.abstractenWe propose a new method to reduce the computational cost of the Entropic Optimal Transport in the vanishing temperature (ε) limit. As in [Schmitzer, 2016], the method relies on a Sinkhorn continuation "ε-scaling" approach; but instead of truncating out the small values of the Kernel, we rely on the exact "out-summation" of saturated domains for a modified constrained Entropic Optimal problem. The constraint depends on an additional parameter λ. In pratice λ = ε also vanishes and the constraint disappear. Using [Berman, 2017], the convergence of the (ε, λ) continuation method based on this modified problem is established. We then show that the saturated domain can be over estimated from the previous larger (ε, λ). On the saturated zone the solution is constant and known and the domain can be "out-summed" (removed) from Sinkhorn algorithm. The computational and cost and memory foot print is shown to be almost linear thanks again to an estimate given by [Berman, 2017]. This is confirmed on 1-D numerical experiments.en
dc.publisher.nameCahier de recherche CEREMADEen
dc.publisher.cityParisen
dc.identifier.citationpages49en
dc.identifier.urlsitehttps://hal.archives-ouvertes.fr/hal-02563022en
dc.subject.ddclabelAnalyseen
dc.description.ssrncandidatenonen
dc.description.halcandidatenonen
dc.description.readershiprechercheen
dc.description.audienceInternationalen
dc.date.updated2020-06-12T09:08:09Z
hal.author.functionaut
hal.author.functionaut


Files in this item

Thumbnail
Name:
OTEL.pdf
Size:
6.433Mb
Format:
PDF
View/Open

This item appears in the following Collection(s)

Show simple item record