TY - JOUR
T1 - ASYMPTOTICS FOR SEMIDISCRETE ENTROPIC OPTIMAL TRANSPORT
AU - Altschuler, Jason M.
AU - Niles-Weed, Jonathan
AU - Stromme, Austin J.
N1 - Funding Information:
\ast Received by the editors August 12, 2021; accepted for publication (in revised form) December 23, 2021; published electronically March 14, 2022. https://doi.org/10.1137/21M1440165 \bfF \bfu \bfn \bfd \bfi \bfn \bfg : This work was partially supported by the National Science Foundation (NSF) Graduate Research Fellowship 1122374, a TwoSigma Ph.D. Fellowship, the NSF grant DMS-2015291, and the NDSEG Fellowship F-6749924378. \dagger Laboratory for Information and Decision Systems (LIDS), Massachusetts Institute of Technology, Cambridge, MA 02139 USA (jasonalt@mit.edu, astromme@mit.edu). \ddagger Courant Institute of Mathematical Sciences and the Center for Data Science, New York University, New York, NY 10003 USA (jnw@cims.nyu.edu).
Publisher Copyright:
© 2022 Society for Industrial and Applied Mathematics
PY - 2022
Y1 - 2022
N2 - We compute exact second-order asymptotics for the cost of an optimal solution to the entropic optimal transport problem in the continuous-to-discrete, or semidiscrete, setting. In contrast to the discrete-discrete or continuous-continuous case, we show that the first-order term in this expansion vanishes but the second-order term does not, so that in the semidiscrete setting the difference in cost between the unregularized and the regularized solutions is quadratic in the inverse regularization parameter, with a leading constant that depends explicitly on the value of the density at the points of discontinuity of the optimal unregularized map between the measures. We develop these results by proving new pointwise convergence rates of the solutions to the dual problem, which may be of independent interest.
AB - We compute exact second-order asymptotics for the cost of an optimal solution to the entropic optimal transport problem in the continuous-to-discrete, or semidiscrete, setting. In contrast to the discrete-discrete or continuous-continuous case, we show that the first-order term in this expansion vanishes but the second-order term does not, so that in the semidiscrete setting the difference in cost between the unregularized and the regularized solutions is quadratic in the inverse regularization parameter, with a leading constant that depends explicitly on the value of the density at the points of discontinuity of the optimal unregularized map between the measures. We develop these results by proving new pointwise convergence rates of the solutions to the dual problem, which may be of independent interest.
KW - entropic optimal transport
KW - optimal transport
KW - second-order asymptotics
KW - semidiscrete optimal transport
UR - http://www.scopus.com/inward/record.url?scp=85128910370&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85128910370&partnerID=8YFLogxK
U2 - 10.1137/21M1440165
DO - 10.1137/21M1440165
M3 - Article
AN - SCOPUS:85128910370
SN - 0036-1410
VL - 54
SP - 1718
EP - 1741
JO - SIAM Journal on Mathematical Analysis
JF - SIAM Journal on Mathematical Analysis
IS - 2
ER -