IDEAS home Printed from https://ideas.repec.org/a/spr/operea/v22y2022i2d10.1007_s12351-020-00589-z.html
   My bibliography  Save this article

An LP-based, strongly-polynomial 2-approximation algorithm for sparse Wasserstein barycenters

Author

Listed:
  • Steffen Borgwardt

    (University of Colorado Denver)

Abstract

Discrete Wasserstein barycenters correspond to optimal solutions of transportation problems for a set of probability measures with finite support. Discrete barycenters are measures with finite support themselves and exhibit two favorable properties: there always exists one with a provably sparse support, and any optimal transport to the input measures is non-mass splitting. It is open whether a discrete barycenter can be computed in polynomial time. It is possible to find an exact barycenter through linear programming, but these programs may scale exponentially. In this paper, we prove that there is a strongly-polynomial 2-approximation algorithm based on linear programming. First, we show that an exact computation over the union of supports of the input measures gives a tight 2-approximation. This computation can be done through a linear program with setup and solution in strongly-polynomial time. The resulting measure is sparse, but an optimal transport may split mass. We then devise a second, strongly-polynomial algorithm to improve this measure to one with a non-mass splitting transport of lower cost. The key step is an update of the possible support set to resolve mass split. Finally, we devise an iterative scheme that alternates between these two algorithms. The algorithm terminates with a 2-approximation that has both a sparse support and an associated non-mass splitting optimal transport. We conclude with some sample computations and an analysis of the scaling of our algorithms, exhibiting vast improvements in running time over exact LP-based computations and low practical errors.

Suggested Citation

  • Steffen Borgwardt, 2022. "An LP-based, strongly-polynomial 2-approximation algorithm for sparse Wasserstein barycenters," Operational Research, Springer, vol. 22(2), pages 1511-1551, April.
    • Handle: RePEc:spr:operea:v:22:y:2022:i:2:d:10.1007_s12351-020-00589-z
    DOI: 10.1007/s12351-020-00589-z
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s12351-020-00589-z
    File Function: Abstract
    Download Restriction: Access to the full text of the articles in this series is restricted.
    File URL: https://libkey.io/10.1007/s12351-020-00589-z?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. Sébastien Gadat & Ioana Gavra & Laurent Risser, 2018. "How to Calculate the Barycenter of a Weighted Graph," Mathematics of Operations Research, INFORMS, vol. 43(4), pages 1085-1118, November.
    2. Pierre-André Chiappori & Robert McCann & Lars Nesheim, 2010. "Hedonic price equilibria, stable matching, and optimal transport: equivalence, topology, and uniqueness," Economic Theory, Springer;Society for the Advancement of Economic Theory (SAET), vol. 42(2), pages 317-354, February.
    3. A. Galichon & P. Henry-Labord`ere & N. Touzi, 2014. "A stochastic control approach to no-arbitrage bounds given marginals, with an application to lookback options," Papers 1401.3921, arXiv.org.
    4. Mathias Beiglbock & Pierre Henry-Labord`ere & Friedrich Penkner, 2011. "Model-independent Bounds for Option Prices: A Mass Transport Approach," Papers 1106.5929, arXiv.org, revised Feb 2013.
    5. Ethan Anderes & Steffen Borgwardt & Jacob Miller, 2016. "Discrete Wasserstein barycenters: optimal transport for discrete data," Mathematical Methods of Operations Research, Springer;Gesellschaft für Operations Research (GOR);Nederlands Genootschap voor Besliskunde (NGB), vol. 84(2), pages 389-409, October.
    6. Éva Tardos, 1986. "A Strongly Polynomial Algorithm to Solve Combinatorial Linear Programs," Operations Research, INFORMS, vol. 34(2), pages 250-256, April.
    7. Mathias Beiglböck & Pierre Henry-Labordère & Friedrich Penkner, 2013. "Model-independent bounds for option prices—a mass transport approach," Finance and Stochastics, Springer, vol. 17(3), pages 477-501, July.
    8. G. Carlier & I. Ekeland, 2010. "Matching for teams," Economic Theory, Springer;Society for the Advancement of Economic Theory (SAET), vol. 42(2), pages 397-418, February.
    9. Miles Lubin & Iain Dunning, 2015. "Computing in Operations Research Using Julia," INFORMS Journal on Computing, INFORMS, vol. 27(2), pages 238-248, May.
    10. repec:dau:papers:123456789/6728 is not listed on IDEAS
    Full references (including those not matched with items on IDEAS)

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Ethan Anderes & Steffen Borgwardt & Jacob Miller, 2016. "Discrete Wasserstein barycenters: optimal transport for discrete data," Mathematical Methods of Operations Research, Springer;Gesellschaft für Operations Research (GOR);Nederlands Genootschap voor Besliskunde (NGB), vol. 84(2), pages 389-409, October.
    2. Julio Backhoff-Veraguas & Gudmund Pammer, 2019. "Stability of martingale optimal transport and weak optimal transport," Papers 1904.04171, arXiv.org, revised Dec 2020.
    3. Acciaio, B. & Backhoff-Veraguas, J. & Zalashko, A., 2020. "Causal optimal transport and its links to enlargement of filtrations and continuous-time stochastic optimization," Stochastic Processes and their Applications, Elsevier, vol. 130(5), pages 2918-2953.
    4. Matteo Burzoni & Marco Frittelli & Marco Maggis, 2015. "Model-free Superhedging Duality," Papers 1506.06608, arXiv.org, revised May 2016.
    5. Lim, Tongseok, 2020. "Optimal martingale transport between radially symmetric marginals in general dimensions," Stochastic Processes and their Applications, Elsevier, vol. 130(4), pages 1897-1912.
    6. Mathias Beiglbock & Alexander M. G. Cox & Martin Huesmann & Nicolas Perkowski & David J. Promel, 2015. "Pathwise super-replication via Vovk's outer measure," Papers 1504.03644, arXiv.org, revised Jul 2016.
    7. Acciaio, Beatrice & Larsson, Martin, 2017. "Semi-static completeness and robust pricing by informed investors," LSE Research Online Documents on Economics 68502, London School of Economics and Political Science, LSE Library.
    8. Benjamin Jourdain & Gudmund Pammer, 2023. "An extension of martingale transport and stability in robust finance," Papers 2304.09551, arXiv.org.
    9. Mathias Beiglbock & Marcel Nutz & Florian Stebegg, 2019. "Fine Properties of the Optimal Skorokhod Embedding Problem," Papers 1903.03887, arXiv.org, revised Apr 2020.
    10. Marcel Nutz & Florian Stebegg, 2016. "Canonical Supermartingale Couplings," Papers 1609.02867, arXiv.org, revised Nov 2017.
    11. Stephan Eckstein & Michael Kupper, 2018. "Computation of optimal transport and related hedging problems via penalization and neural networks," Papers 1802.08539, arXiv.org, revised Jan 2019.
    12. Julio Backhoff-Veraguas & Gudmund Pammer & Walter Schachermayer, 2024. "The Gradient Flow of the Bass Functional in Martingale Optimal Transport," Papers 2407.18781, arXiv.org.
    13. Ruodu Wang & Zhenyuan Zhang, 2022. "Simultaneous Optimal Transport," Papers 2201.03483, arXiv.org, revised May 2023.
    14. Tongseok Lim, 2014. "Optimal martingale transport between radially symmetric marginals in general dimensions," Papers 1412.3530, arXiv.org, revised Feb 2018.
    15. Yan Dolinsky & H. Soner, 2014. "Robust hedging with proportional transaction costs," Finance and Stochastics, Springer, vol. 18(2), pages 327-347, April.
    16. Nassif Ghoussoub & Young-Heon Kim & Tongseok Lim, 2017. "Optimal Brownian Stopping between radially symmetric marginals in general dimensions," Papers 1711.02784, arXiv.org.
    17. Beatrice Acciaio & Mathias Beiglböck & Gudmund Pammer, 2021. "Weak transport for non‐convex costs and model‐independence in a fixed‐income market," Mathematical Finance, Wiley Blackwell, vol. 31(4), pages 1423-1453, October.
    18. Julio Backhoff-Veraguas & Daniel Bartl & Mathias Beiglböck & Manu Eder, 2020. "Adapted Wasserstein distances and stability in mathematical finance," Finance and Stochastics, Springer, vol. 24(3), pages 601-632, July.
    19. Ariel Neufeld & Antonis Papapantoleon & Qikun Xiang, 2023. "Model-Free Bounds for Multi-Asset Options Using Option-Implied Information and Their Exact Computation," Management Science, INFORMS, vol. 69(4), pages 2051-2068, April.
    20. Tongseok Lim, 2023. "Replication of financial derivatives under extreme market models given marginals," Papers 2307.00807, arXiv.org.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:spr:operea:v:22:y:2022:i:2:d:10.1007_s12351-020-00589-z. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Sonal Shukla or Springer Nature Abstracting and Indexing (email available below). General contact details of provider: http://www.springer.com .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.