@articleWiegelmann2014, author = Wiegelmann, T. and Thalmann, J.K. and
Solanki, S.K., title = The Magnetic Field in the Solar Atmosphere, journal =
Astronomy and Astrophysics Review, volume = 22, pages = 78, year = 2014, doi =
10.1007/s00159-014-0078-7, url = https://doi.org/10.1007/s00159-014-0078-7

@ARTICLEsdo_telescope, author = Pesnell, W. Dean and Thompson, B. J. and
Chamberlin, P. C., title = ”The Solar Dynamics Observatory (SDO)”, journal = ,
keywords = SDO, Solar cycle, Helioseismology, Coronal, Space weather, year =
2012, month = jan, volume = 275, number = 1-2, pages = 3-15, doi =
10.1007/s11207-011-9841-3, adsurl =
https://ui.adsabs.harvard.edu/abs/2012SoPh..275….3P, adsnote = Provided by the
SAO/NASA Astrophysics Data System

@ARTICLEhmi_instrument, author = Schou, J. and Scherrer, P. H. and Bush, R. I.
and Wachter, R. and Couvidat, S. and Rabello-Soares, M. C. and Bogart, R. S.
and Hoeksema, J. T. and Liu, Y. and Duvall, T. L. and Akin, D. J. and Allard,
B. A. and Miles, J. W. and Rairden, R. and Shine, R. A. and Tarbell, T. D. and
Title, A. M. and Wolfson, C. J. and Elmore, D. F. and Norton, A. A. and
Tomczyk, S., title = ”Design and Ground Calibration of the Helioseismic and
Magnetic Imager (HMI) Instrument on the Solar Dynamics Observatory (SDO)”,
journal = , keywords = Solar Dynamics Observatory, Helioseismology,
observations, Instrumentation and data management, Magnetic fields,
photosphere, year = 2012, month = jan, volume = 275, number = 1-2, pages =
229-259, doi = 10.1007/s11207-011-9842-2, adsurl =
https://ui.adsabs.harvard.edu/abs/2012SoPh..275..229S, adsnote = Provided by
the SAO/NASA Astrophysics Data System

@ARTICLEleka_a, author = Leka, K. D. and Barnes, G., title = ”Photospheric
Magnetic Field Properties of Flaring versus Flare-quiet Active Regions. I.
Data, General Approach, and Sample Results”, journal = , keywords = Sun:
Activity, Sun: Flares, Sun: Photosphere, Techniques: Polarimetric, year =
2003, month = oct, volume = 595, number = 2, pages = 1277-1295, doi =
10.1086/377511, adsurl = https://ui.adsabs.harvard.edu/abs/2003ApJ…595.1277L,
adsnote = Provided by the SAO/NASA Astrophysics Data System

@ARTICLEleka_b, author = Leka, K. D. and Barnes, G., title = ”Photospheric
Magnetic Field Properties of Flaring versus Flare-quiet Active Regions. II.
Discriminant Analysis”, journal = , keywords = Methods: Statistical, Sun:
Activity, Sun: Flares, Sun: Photosphere, year = 2003, month = oct, volume =
595, number = 2, pages = 1296-1306, doi = 10.1086/377512, adsurl =
https://ui.adsabs.harvard.edu/abs/2003ApJ…595.1296L, adsnote = Provided by the
SAO/NASA Astrophysics Data System

@ARTICLEleka_c, author = Barnes, G. and Leka, K. D., title = ”Photospheric
Magnetic Field Properties of Flaring versus Flare-quiet Active Regions. III.
Magnetic Charge Topology Models”, journal = , keywords = Sun: Activity, Sun:
Corona, Sun: Flares, Sun: Magnetic Fields, Sun: Photosphere, year = 2006,
month = aug, volume = 646, number = 2, pages = 1303-1318, doi =
10.1086/504960, adsurl = https://ui.adsabs.harvard.edu/abs/2006ApJ…646.1303B,
adsnote = Provided by the SAO/NASA Astrophysics Data System

@inbookPandey_2023, title=Explainable Deep Learning-Based Solar Flare
Prediction with Post Hoc Attention for Operational Forecasting,
ISBN=9783031452758, ISSN=1611-3349,
url=http://dx.doi.org/10.1007/978-3-031-45275-8_38,
DOI=10.1007/978-3-031-45275-8_38, booktitle=Lecture Notes in Computer Science,
publisher=Springer Nature Switzerland, author=Pandey, Chetraj and Angryk,
Rafal A. and Georgoulis, Manolis K. and Aydin, Berkay, year=2023,
pages=567–581

@ARTICLEYi_et_al2023, author = Yi, Kangwoo and Moon, Yong-Jae and Jeong, Hyun-
Jin, title = ”Application of Deep Reinforcement Learning to Major Solar Flare
Forecasting”, journal = , keywords = Solar flares, Neural networks, The Sun,
1496, 1933, 1693, year = 2023, month = apr, volume = 265, number = 2, eid =
34, pages = 34, doi = 10.3847/1538-4365/acb76d, adsurl =
https://ui.adsabs.harvard.edu/abs/2023ApJS..265…34Y, adsnote = Provided by the
SAO/NASA Astrophysics Data System

@articleCOLLINS2021102383, title = Artificial intelligence in information
systems research: A systematic literature review and research agenda, journal
= International Journal of Information Management, volume = 60, pages =
102383, year = 2021, issn = 0268-4012, doi =
https://doi.org/10.1016/j.ijinfomgt.2021.102383, url =
https://www.sciencedirect.com/science/article/pii/S0268401221000761, author =
Christopher Collins and Denis Dennehy and Kieran Conboy and Patrick Mikalef,
keywords = Artificial intelligence, AI, Machine learning, Systematic
literature review, Research agenda, abstract = AI has received increased
attention from the information systems (IS) research community in recent
years. There is, however, a growing concern that research on AI could
experience a lack of cumulative building of knowledge, which has overshadowed
IS research previously. This study addresses this concern, by conducting a
systematic literature review of AI research in IS between 2005 and 2020. The
search strategy resulted in 1877 studies, of which 98 were identified as
primary studies and a synthesise of key themes that are pertinent to this
study is presented. In doing so, this study makes important contributions,
namely (i) an identification of the current reported business value and
contributions of AI, (ii) research and practical implications on the use of AI
and (iii) opportunities for future AI research in the form of a research
agenda.

@articleson2023three,

title=Three-day Forecasting of Solar Wind Speed Using SDO/AIA Extreme-
ultraviolet Images by a Deep-learning Model,

author=Son, Jihyeon and Sung, Suk-Kyung and Moon, Yong-Jae and Lee, Harim and
Jeong, Hyun-Jin,

journal=The Astrophysical Journal Supplement Series,

volume=267,

number=2,

pages=45,

year=2023,

publisher=IOP Publishing

@articlejeong2020solar,

title=Solar coronal magnetic field extrapolation from synchronic data with AI-
generated farside,

author=Jeong, Hyun-Jin and Moon, Yong-Jae and Park, Eunsu and Lee, Harim,

journal=The Astrophysical Journal Letters,

volume=903,

number=2,

pages=L25,

year=2020,

publisher=IOP Publishing

@articlejeong2022improved,

title=Improved AI-generated Solar Farside Magnetograms by STEREO and SDO Data
Sets and Their Release,

author=Jeong, Hyun-Jin and Moon, Yong-Jae and Park, Eunsu and Lee, Harim and
Baek, Ji-Hye,

journal=The Astrophysical Journal Supplement Series,

volume=262,

number=2,

pages=50,

year=2022,

publisher=IOP Publishing

@misckingma2022autoencoding, title=Auto-Encoding Variational Bayes,
author=Diederik P Kingma and Max Welling, year=2022, eprint=1312.6114,
archivePrefix=arXiv, primaryClass=stat.ML

@miscgoodfellow2014generative, title=Generative Adversarial Networks,
author=Ian J. Goodfellow and Jean Pouget-Abadie and Mehdi Mirza and Bing Xu
and David Warde-Farley and Sherjil Ozair and Aaron Courville and Yoshua
Bengio, year=2014, eprint=1406.2661, archivePrefix=arXiv, primaryClass=stat.ML

@mischo2020denoising, title=Denoising Diffusion Probabilistic Models,
author=Jonathan Ho and Ajay Jain and Pieter Abbeel, year=2020,
eprint=2006.11239, archivePrefix=arXiv, primaryClass=cs.LG

@miscrombach2022highresolution, title=High-Resolution Image Synthesis with
Latent Diffusion Models, author=Robin Rombach and Andreas Blattmann and
Dominik Lorenz and Patrick Esser and Björn Ommer, year=2022,
eprint=2112.10752, archivePrefix=arXiv, primaryClass=cs.CV

@miscsaharia2022palette, title=Palette: Image-to-Image Diffusion Models,
author=Chitwan Saharia and William Chan and Huiwen Chang and Chris A. Lee and
Jonathan Ho and Tim Salimans and David J. Fleet and Mohammad Norouzi,
year=2022, eprint=2111.05826, archivePrefix=arXiv, primaryClass=cs.CV

@miscli2021srdiff, title=SRDiff: Single Image Super-Resolution with Diffusion
Probabilistic Models, author=Haoying Li and Yifan Yang and Meng Chang and
Huajun Feng and Zhihai Xu and Qi Li and Yueting Chen, year=2021,
eprint=2104.14951, archivePrefix=arXiv, primaryClass=cs.CV

@miscramunno2024solar, title=Solar synthetic imaging: Introducing denoising
diffusion probabilistic models on SDO/AIA data, author=Francesco P. Ramunno
and S. Hackstein and V. Kinakh and M. Drozdova and G. Quetant and A. Csillaghy
and S. Voloshynovskiy, year=2024, eprint=2404.02552, archivePrefix=arXiv,
primaryClass=astro-ph.SR

@Articles24041151, AUTHOR = Kinakh, Vitaliy and Belousov, Yury and Quétant,
Guillaume and Drozdova, Mariia and Holotyak, Taras and Schaerer, Daniel and
Voloshynovskiy, Slava, TITLE = Hubble Meets Webb: Image-to-Image Translation
in Astronomy, JOURNAL = Sensors, VOLUME = 24, YEAR = 2024, NUMBER = 4,
ARTICLE-NUMBER = 1151, URL = https://www.mdpi.com/1424-8220/24/4/1151,
PubMedID = 38400307, ISSN = 1424-8220, ABSTRACT = This work explores the
generation of James Webb Space Telescope (JWSP) imagery via image-to-image
translation from the available Hubble Space Telescope (HST) data. Comparative
analysis encompasses the Pix2Pix, CycleGAN, TURBO, and DDPM-based Palette
methodologies, assessing the criticality of image registration in astronomy.
While the focus of this study is not on the scientific evaluation of model
fairness, we note that the techniques employed may bear some limitations and
the translated images could include elements that are not present in actual
astronomical phenomena. To mitigate this, uncertainty estimation is integrated
into our methodology, enhancing the translation’s integrity and assisting
astronomers in distinguishing between reliable predictions and those of
questionable certainty. The evaluation was performed using metrics including
MSE, SSIM, PSNR, LPIPS, and FID. The paper introduces a novel approach to
quantifying uncertainty within image translation, leveraging the stochastic
nature of DDPMs. This innovation not only bolsters our confidence in the
translated images but also provides a valuable tool for future astronomical
experiment planning. By offering predictive insights when JWST data are
unavailable, our approach allows for informed preparatory strategies for
making observations with the upcoming JWST, potentially optimizing its
precious observational resources. To the best of our knowledge, this work is
the first attempt to apply image-to-image translation for astronomical sensor-
to-sensor translation., DOI = 10.3390/s24041151

@articlemariia_drozdova, author = Drozdova, M. and Kinakh, V. and Bait, O. and
Taran, O. and Lastufka, E. and Dessauges-Zavadsky, M. and Holotyak, T. and
Schaerer, D. and Voloshynovskiy, S., title = Radio-astronomical image
reconstruction with a conditional denoising diffusion model⋆, DOI=
”10.1051/0004-6361/202347948”, url=
”https://doi.org/10.1051/0004-6361/202347948”, journal = A&A, year = 2024,
volume = 683, pages = ”A105”,

@articlejarolim_2024, author = Jarolim, Robert and Tremblay, Benoit and Munoz-
Jaramillo, Andres and Bintsi, Kyriaki-Margarita and Jungbluth, Anna and
Santos, Miraflor and Vourlidas, Angelos and Mason, James and Sundaresan,
Sairam and Downs, Cooper and Caplan, Ronald, year = 2024, month = 01, pages =
L31, title = SuNeRF: 3D Reconstruction of the Solar EUV Corona Using Neural
Radiance Fields, volume = 961, journal = The Astrophysical Journal Letters,
doi = 10.3847/2041-8213/ad12d2

@miscdhariwal2021diffusion, title=Diffusion Models Beat GANs on Image
Synthesis, author=Prafulla Dhariwal and Alex Nichol, year=2021,
eprint=2105.05233, archivePrefix=arXiv, primaryClass=cs.LG

@articlePlutino_2023, title=A new catalogue of solar flare events from soft
X-ray GOES signal in the period 1986–2020, volume=71, ISSN=0273-1177,
url=http://dx.doi.org/10.1016/j.asr.2022.11.020,
DOI=10.1016/j.asr.2022.11.020, number=4, journal=Advances in Space Research,
publisher=Elsevier BV, author=Plutino, Nicola and Berrilli, Francesco and Del
Moro, Dario and Giovannelli, Luca, year=2023, month=feb, pages=2048–2058

@misczhang2018unreasonable, title=The Unreasonable Effectiveness of Deep
Features as a Perceptual Metric, author=Richard Zhang and Phillip Isola and
Alexei A. Efros and Eli Shechtman and Oliver Wang, year=2018,
eprint=1801.03924, archivePrefix=arXiv, primaryClass=cs.CV

@ARTICLEssim, author=Zhou Wang and Bovik, A.C. and Sheikh, H.R. and
Simoncelli, E.P., journal=IEEE Transactions on Image Processing, title=Image
quality assessment: from error visibility to structural similarity, year=2004,
volume=13, number=4, pages=600-612, keywords=Image quality;Humans;Transform
coding;Visual system;Visual perception;Data mining;Layout;Quality
assessment;Degradation;Indexes, doi=10.1109/TIP.2003.819861

@miscdelbracio2024inversion, title=Inversion by Direct Iteration: An
Alternative to Denoising Diffusion for Image Restoration, author=Mauricio
Delbracio and Peyman Milanfar, year=2024, eprint=2303.11435,
archivePrefix=arXiv, primaryClass=eess.IV

@ARTICLEsunpy, doi = 10.3847/1538-4357/ab4f7a, url =
https://iopscience.iop.org/article/10.3847/1538-4357/ab4f7a, author = The
SunPy Community and Barnes, Will T. and Bobra, Monica G. and Christe, Steven
D. and Freij, Nabil and Hayes, Laura A. and Ireland, Jack and Mumford, Stuart
and Perez-Suarez, David and Ryan, Daniel F. and Shih, Albert Y. and Chanda,
Prateek and Glogowski, Kolja and Hewett, Russell and Hughitt, V. Keith and
Hill, Andrew and Hiware, Kaustubh and Inglis, Andrew and Kirk, Michael S. F.
and Konge, Sudarshan and Mason, James Paul and Maloney, Shane Anthony and
Murray, Sophie A. and Panda, Asish and Park, Jongyeob and Pereira, Tiago M. D.
and Reardon, Kevin and Savage, Sabrina and Sipőcz, Brigitta M. and Stansby,
David and Jain, Yash and Taylor, Garrison and Yadav, Tannmay and Rajul and
Dang, Trung Kien, title = The SunPy Project: Open Source Development and
Status of the Version 1.0 Core Package, journal = The Astrophysical Journal,
volume = 890, issue = 1, pages = 68-, publisher = American Astronomical
Society, year = 2020

@articleSadykov_2017, title=Relationships between Characteristics of the Line-
of-sight Magnetic Field and Solar Flare Forecasts, volume=849, ISSN=1538-4357,
url=http://dx.doi.org/10.3847/1538-4357/aa9119, DOI=10.3847/1538-4357/aa9119,
number=2, journal=The Astrophysical Journal, publisher=American Astronomical
Society, author=Sadykov, Viacheslav M. and Kosovichev, Alexander G.,
year=2017, month=nov, pages=148

@ARTICLEwang_2020, author = Wang, Jingjing and Zhang, Yuhang and Hess Webber,
Shea A. and Liu, Siqing and Meng, Xuejie and Wang, Tieyan, title = ”Solar
Flare Predictive Features Derived from Polarity Inversion Line Masks in Active
Regions Using an Unsupervised Machine Learning Algorithm”, journal = ,
keywords = Solar flares, Space weather, Classification, Solar active regions,
1496, 2037, 1907, 1974, year = 2020, month = apr, volume = 892, number = 2,
eid = 140, pages = 140, doi = 10.3847/1538-4357/ab7b6c, adsurl =
https://ui.adsabs.harvard.edu/abs/2020ApJ…892..140W, adsnote = Provided by the
SAO/NASA Astrophysics Data System

@articlejaccard, author = Jaccard, Paul, year = 1901, month = 01, pages =
547-579, title = Etude de la distribution florale dans une portion des Alpes
et du Jura, volume = 37, journal = Bulletin de la Societe Vaudoise des
Sciences Naturelles, doi = 10.5169/seals-266450

@inproceedingspil, author = Cai, Xumin and Aydin, Berkay and Ji, Anli and
Georgoulis, Manolis and Angryk, Rafal, year = 2020, month = 12, pages =
4175-4183, title = A Framework for Detecting Polarity Inversion Lines from
Longitudinal Magnetograms, doi = 10.1109/BigData50022.2020.9377808

@miscmenon2020pulse, title=PULSE: Self-Supervised Photo Upsampling via Latent
Space Exploration of Generative Models, author=Sachit Menon and Alexandru
Damian and Shijia Hu and Nikhil Ravi and Cynthia Rudin, year=2020,
eprint=2003.03808, archivePrefix=arXiv, primaryClass=cs.CV

@inproceedingsNIPS2012_c399862d, author = Krizhevsky, Alex and Sutskever, Ilya
and Hinton, Geoffrey E, booktitle = Advances in Neural Information Processing
Systems, editor = F. Pereira and C.J. Burges and L. Bottou and K.Q.
Weinberger, pages = , publisher = Curran Associates, Inc., title = ImageNet
Classification with Deep Convolutional Neural Networks, url =
https://proceedings.neurips.cc/paper_files/paper/2012/file/c399862d3b9d6b76c8436e924a68c45b-Paper.pdf,
volume = 25, year = 2012

@articlehelioviewer, author = Ireland, Jonathan and Hughitt, Vincent and
Müller, D. and Dimitoglou, George and Schmiedel, P. and Fleck, Bernhard, year
= 2009, month = 04, pages = , title = The Helioviewer Project: Discovery For
Everyone Everywhere, volume = 40

@ARTICLEkleint_lucia, author = Kleint, Lucia, title = ”First Detection of
Chromospheric Magnetic Field Changes during an X1-Flare”, journal = , keywords
= Sun: chromosphere, Sun: flares, Sun: magnetic fields, Astrophysics - Solar
and Stellar Astrophysics, year = 2017, month = jan, volume = 834, number = 1,
eid = 26, pages = 26, doi = 10.3847/1538-4357/834/1/26, archivePrefix = arXiv,
eprint = 1608.02552, primaryClass = astro-ph.SR, adsurl =
https://ui.adsabs.harvard.edu/abs/2017ApJ…834…26K, adsnote = Provided by the
SAO/NASA Astrophysics Data System

@articleSun_2022, title=Predicting Solar Flares Using CNN and LSTM on Two
Solar Cycles of Active Region Data, volume=931, ISSN=1538-4357,
url=http://dx.doi.org/10.3847/1538-4357/ac64a6, DOI=10.3847/1538-4357/ac64a6,
number=2, journal=The Astrophysical Journal, publisher=American Astronomical
Society, author=Sun, Zeyu and Bobra, Monica G. and Wang, Xiantong and Wang, Yu
and Sun, Hu and Gombosi, Tamas and Chen, Yang and Hero, Alfred, year=2022,
month=jun, pages=163

@inbookPandey_2023, title=Explainable Deep Learning-Based Solar Flare
Prediction with Post Hoc Attention for Operational Forecasting,
ISBN=9783031452758, ISSN=1611-3349,
url=http://dx.doi.org/10.1007/978-3-031-45275-8_38,
DOI=10.1007/978-3-031-45275-8_38, booktitle=Lecture Notes in Computer Science,
publisher=Springer Nature Switzerland, author=Pandey, Chetraj and Angryk,
Rafal A. and Georgoulis, Manolis K. and Aydin, Berkay, year=2023,
pages=567–581

@ARTICLEpanos, author = Panos, Brandon and Kleint, Lucia and Zbinden, Jonas,
title = ”Identifying preflare spectral features using explainable artificial
intelligence”, journal = , keywords = Sun: flares, techniques: spectroscopic,
Sun: activity, Sun: chromosphere, methods: data analysis, methods:
statistical, Astrophysics - Solar and Stellar Astrophysics, Astrophysics -
Instrumentation and Methods for Astrophysics, year = 2023, month = mar, volume
= 671, eid = A73, pages = A73, doi = 10.1051/0004-6361/202244835,
archivePrefix = arXiv, eprint = 2301.01560, primaryClass = astro-ph.SR, adsurl
= https://ui.adsabs.harvard.edu/abs/2023A&A…671A..73P, adsnote = Provided by
the SAO/NASA Astrophysics Data System

@articleGEORGOULIS2024, title = Prediction of solar energetic events impacting
space weather conditions, journal = Advances in Space Research, year = 2024,
issn = 0273-1177, doi = https://doi.org/10.1016/j.asr.2024.02.030, url =
https://www.sciencedirect.com/science/article/pii/S027311772400173X, author =
Manolis K. Georgoulis and Stephanie L. Yardley and Jordan A. Guerra and Sophie
A. Murray and Azim Ahmadzadeh and Anastasios Anastasiadis and Rafal Angryk and
Berkay Aydin and Dipankar Banerjee and Graham Barnes and Alessandro Bemporad
and Federico Benvenuto and D. Shaun Bloomfield and Monica Bobra and Cristina
Campi and Enrico Camporeale and Craig E. DeForest and A. Gordon Emslie and
David Falconer and Li Feng and Weiqun Gan and Lucie M. Green and Sabrina
Guastavino and Mike Hapgood and Dustin Kempton and Irina Kitiashvili and
Ioannis Kontogiannis and Marianna B. Korsos and K.D. Leka and Paolo Massa and
Anna Maria Massone and Dibyendu Nandy and Alexander Nindos and Athanasios
Papaioannou and Sung-Hong Park and Spiros Patsourakos and Michele Piana and
Nour E. Rawafi and Viacheslav M. Sadykov and Shin Toriumi and Angelos
Vourlidas and Haimin Wang and Jason T. L. Wang and Kathryn Whitman and Yihua
Yan and Andrei N. Zhukov, keywords = International space weather action teams,
Forecasting, Solar flares and eruptions, Methods – statistical, Methods –
machine learning, Future missions, abstract = Aiming to assess the progress
and current challenges on the formidable problem of the prediction of solar
energetic events since the COSPAR/ International Living With a Star (ILWS)
Roadmap paper of Schrijver et al. (2015), we attempt an overview of the
current status of global research efforts. By solar energetic events we refer
to flares, coronal mass ejections (CMEs), and solar energetic particle (SEP)
events. The emphasis, therefore, is on the prediction methods of solar flares
and eruptions, as well as their associated SEP manifestations. This work
complements the COSPAR International Space Weather Action Teams (ISWAT) review
paper on the understanding of solar eruptions by Linton et al. (2023)
(hereafter, ISWAT review papers are conventionally referred to as ’Cluster’
papers, given the ISWAT structure). Understanding solar flares and eruptions
as instabilities occurring above the nominal background of solar activity is a
core solar physics problem. We show that effectively predicting them stands on
two pillars: physics and statistics. With statistical methods appearing at an
increasing pace over the last 40 years, the last two decades have brought the
critical realization that data science needs to be involved, as well, as
volumes of diverse ground- and space-based data give rise to a Big Data
landscape that cannot be handled, let alone processed, with conventional
statistics. Dimensionality reduction in immense parameter spaces with the dual
aim of both interpreting and forecasting solar energetic events has brought
artificial intelligence (AI) methodologies, in variants of machine and deep
learning, developed particularly for tackling Big Data problems. With
interdisciplinarity firmly present, we outline an envisioned framework on
which statistical and AI methodologies should be verified in terms of
performance and validated against each other. We emphasize that a homogenized
and streamlined method validation is another open challenge. The performance
of the plethora of methods is typically far from perfect, with physical
reasons to blame, besides practical shortcomings: imperfect data, data gaps
and a lack of multiple, and meaningful, vantage points of solar observations.
We briefly discuss these issues, too, that shape our desired short- and long-
term objectives for an efficient future predictive capability. A central aim
of this article is to trigger meaningful, targeted discussions that will
compel the community to adopt standards for performance verification and
validation, which could be maintained and enriched by institutions such as
NASA’s Community Coordinated Modeling Center (CCMC) and the community-driven
COSPAR/ISWAT initiative.

@articleopencv_library, author = Bradski, G., citeulike-article-id = 2236121,
journal = Dr. Dobb’s Journal of Software Tools, keywords = bibtex-import,
posted-at = 2008-01-15 19:21:54, priority = 4, title = The OpenCV Library,
year = 2000


# Concentration of empirical barycenters in metric spaces

Victor-Emmanuel Brunel  CREST-ENSAE<EMAIL_ADDRESS>Jordan
Serres  CREST-ENSAE<EMAIL_ADDRESS>
###### Abstract

Barycenters (aka Fréchet means) were introduced in statistics in the 1940’s
and popularized in the fields of shape statistics and, later, in optimal
transport and matrix analysis. They provide the most natural extension of
linear averaging to non-Euclidean geometries, which is perhaps the most basic
and widely used tool in data science. In various setups, their asymptotic
properties, such as laws of large numbers and central limit theorems, have
been established, but their non-asymptotic behaviour is still not well
understood. In this work, we prove finite sample concentration inequalities
(namely, generalizations of Hoeffding’s and Bernstein’s inequalities) for
barycenters of i.i.d. random variables in metric spaces with non-positive
curvature in Alexandrov’s sense. As a byproduct, we also obtain PAC guarantees
for a stochastic online algorithm that computes the barycenter of a finite
collection of points in a non-positively curved space. We also discuss
extensions of our results to spaces with possibly positive curvature.

##  1 Introduction

Statistics and machine learning are more and more confronted with data that
lie in non-linear spaces. For instance, in spatial statistics (e.g.,
directional data), computational tomography (e.g., data in quotient spaces
such as in shape statistics, collected up to rigid transformations), economics
(e.g., optimal transport, where data are discrete measures), etc. Moreover,
data that are encoded as very high dimensional vectors may have a much smaller
intrinsic dimension, for instance, if they are lying on small dimensional
submanifolds of the Euclidean space: In that case, leveraging the possibly
non-linear geometry of the data can be a powerful tool in order to
significantly reduce the dimensionality of the problem at hand. Even though
more and more algorithms are developed to work with such data [31, 34, 40,
41], there are still very little theory for uncertainty quantification,
especially in non-asymptotic regimes, which are pervasive in machine learning.
In this work, we prove statistical results for barycenters of data points,
which are the most natural extension of linear averaging to the context of
non-linear geometries. Namely, we extend the notion of sub-Gaussian random
variables to the case of metric spaces and, under a non-positive curvature
condition, we prove versions of both Hoeffding and Bernstein concentration
inequalities. Finally, we discuss extensions of our results to the case of
metric spaces with possibly positive curvature.

A complete metric space $(M,d)$ is called non-positively curved (NPC for
short) if for all pairs $(x,y)\in M$, there exists $m\in M$ satisfying the
following:

$d(z,m)^{2}\leq\frac{1}{2}(d(z,x)^{2}+d(z,y)^{2}-\frac{1}{2}d(x,y)^{2}),$ (1)

for all $z\in M$. NPC spaces are known to induce a lot of regularity. Namely,
any two points $x,y\in M$ are connected by a unique (constant speed) geodesic
$\gamma_{x,y}$, i.e., a continuous mapping $\gamma=\gamma_{x,y}:[0,1]\to M$
satisfying $d(\gamma(s),\gamma(t))=|s-t|d(x,y)$, for all $s,t\in[0,1]$.
Geodesics generalize line segments in Euclidean spaces, as shortest paths from
one point $x$ to another point $y$. Moreover, the point $z$ in (1) is unique,
given by the midpoint of $x$ and $y$, i.e., $z=\gamma_{x,y}(1/2)$. Finally,
the distance function $d$ is geodesically convex jointly in both variables and
for all $x_{0}\in M$, the function $\frac{1}{2}d(x_{0},\cdot)^{2}$ is
$1$-strongly geodesically convex. A function $f$ is called geodesically convex
(resp. strongly geodesically convex) if it is convex (resp. strongly convex)
along any geodesic $\gamma_{x,y},x,y\in M$, i.e.,
$f(\gamma_{x,y}(t))\leq(1-t)f(x)+tf(y)$, for all $x,y\in M$ and $t\in[0,1]$.
We refer the reader to [36, 14] for more information on NPC spaces and to [7]
for a detailed account on convexity in metric spaces. Just to cite a few
examples, the family of NPC spaces include:

  * •

Euclidean and Hilbert spaces;

  * •

Hyperbolic spaces and, more generally, Cartan-Hadamard manifolds, i.e. simply
connected, complete, Riemannian manifolds with everywhere non-positive
sectional curvature [36, Proposition 3.1];

  * •

Metric trees: These are trees embedded in the Euclidean plane, in which the
distance between any two points is the Euclidean length of the (unique)
shortest path between them;

  * •

The space $\mathcal{S}_{p}$ of symmetric positive definite matrices of size
$p$ (for any fixed integer $p\geq 1$) equipped with the following distance:
For any $A,B\in\mathcal{S}_{p}$,

$d(A,B)=\|\log(A^{-1/2}BA^{-1/2})\|_{\textsf{F}},$

where $\|M\|_{\textsf{F}}=\sqrt{\text{Tr}(MM^{\top})},\forall
M\in\mathbb{R}^{p\times p}$, is the Fröbenius norm. This construction is
important in the study of matrix geometric means, as we will explain below, in
Section 3.3. For a detailed account on this space and matrix geometric means,
we refer the reader to [9] and the references therein.

A natural way to extend the notion of averaging from linear to metric spaces
is through the notion of barycenters. Given $x_{1},\ldots,x_{n}\in M$ ($n\geq
1$), a barycenter of $x_{1},\ldots,x_{n}$ is any minimizer $b\in M$ of
$\sum_{i=1}^{n}d(x_{i},b)^{2}$. One can easily check that if $(M,d)$ is a
Euclidean or Hilbert space, the minimizer is unique and it is given by the
average of $x_{1},\ldots,x_{n}$; Note, however, that this is not true in
general normed spaces. In NPC spaces, a barycenter of $x_{1},\ldots,x_{n}$ is
thus a solution to a strongly convex optimization problem, so it always exists
and it is unique. More generally, given a probability distribution $\mu$ with
two moments on $(M,d)$, one can define the barycenter of $\mu$ as the unique
minimizer $b\in M$ of $\int_{M}d(x,b)^{2}\mathop{}\\!\mathrm{d}\mu(x)$. Here,
we say that $\mu$ has two moments if and only if the function
$d(x_{0},\cdot)^{2}$ is integrable with respect to $\mu$ for some (and hence,
by the triangle inequality, for all) $x_{0}\in M$. It is easy to check that
for all pairs $x,y\in M$ and for all $t\in[0,1]$, the barycenter of
$(1-t)\delta_{x}+t\delta_{y}$ (aka weighted barycenter of $x$ and $y$, with
respective weights $1-t$ and $t$) is simply given by $\gamma_{x,y}(t)$. For
instance, the barycenter of $x$ and $y$ is the midpoint of $x$ and $y$. The
barycenter of a probability distribution can be interpreted as an extension of
the notion of expectation in non-linear spaces. Fortunately, defining the
barycenter of $\mu$ actually only requires that $\mu$ has one moment, and its
barycenter is a minimizer $b$ of
$\int_{M}(d(x,b)^{2}-d(x,b_{0})^{2})\mathop{}\\!\mathrm{d}\mu(x)$ for any
fixed $b_{0}\in M$; One can easily check that the minimizer does not depend on
the choice of $b_{0}$. Another interpretation of the barycenter is the point
that minimizes an expected displacement cost as measured with the quadratic
distance. This is why barycenters have gained a lot of importance in optimal
transport theory in the past 15 years, particularly with applications to
economics theory [2].

Barycenters were initially introduced in statistics by [21] in the 1940’s, and
later by [25], where they were better known as Fréchet means, or Karcher
means. They were popularized in the field of shape statistics [26] and optimal
transport [2, 18, 29, 17, 27, 5, 6].

An alternative construction of barycenters, which is computationally much
simpler, is defined iteratively as follows. Given $n$ points
$x_{1},\ldots,x_{n}$, the inductive barycenter is defined as the point
$s_{n}$, where $s_{1}=x_{1},s_{2}=\gamma_{s_{1},x_{2}}(1/2)$ and for
$k=3,\ldots,n$, $s_{k}=\gamma_{s_{k-1},x_{k}}(1/k)$. Barycenters and inductive
barycenters do not coincide (unless $M$ is Euclidean or Hilbert) because of
the lack of associativity of barycenters in non-linear spaces. Compared to
barycenters, inductive barycenters have the advantage that they can be easily
updated if the points $x_{1},\ldots,x_{n}$ come sequentially, in an online
fashion. Their computation does not imply to solve an optimization problem,
and only requires to know geodesics in $M$. However, a drawback of this
construction is that it depends on the order of $x_{1},\ldots,x_{n}$. As we
will see below, this drawback in very minor in a statistical context, since
this dependence vanishes as $n$ grows large and $s_{n}$ becomes closer and
closer to the barycenter of $x_{1},\ldots,x_{n}$, in a stochastic framework.
Moreover, as pointed out in [34], the inductive barycenter of
$x_{1},\ldots,x_{n}$ is the output of an online proximal gradient algorithm to
approximate their barycenter, when the $x_{i}$’s are available one at a time.
Indeed, for $i=1,\ldots,n$, let $f_{i}=d(\cdot,x_{i})^{2}$. Then, the
barycenter of $x_{1},\ldots,x_{n}$ minimizes the convex function
$f=f_{1}+\ldots+f_{n}$ and an online proximal gradient algorithm which starts
at $y_{1}=x_{1}$ outputs, at each step $t=2,\ldots,n$, the point $y_{t}\in M$
which minimizes $f_{t}(y)+\frac{1}{2\lambda_{t}}d(y,y_{t-1})^{2}$, $y\in M$,
where $\lambda_{t}$ is a varying stepsize, here, $\lambda_{t}=(2t)^{-1}$.

Let $\mu$ be a probability measure in $(M,d)$ with two (or, again, one would
suffice) moments and let $b^{*}$ be its barycenter. Let $X_{1},\ldots,X_{n}$
be i.i.d. random variables in $M$ with distribution $\mu$. Here, $n\geq 1$ is
the sample size and is fixed. We are interested in the estimation of $b^{*}$
based on $X_{1},\ldots,X_{n}$. Let $\hat{b}_{n}$ be their barycenter (referred
to as empirical barycenter) and $S_{n}$ be their inductive barycenter.

Existence and uniqueness of barycenters are, in general, hard problems [1, 38,
39]. Asymptotic theory is well understood for empirical barycenters in various
setups, particularly laws of large numbers [42] and central limit theorems in
Riemannian manifolds (a smooth structure on $M$ is a natural assumption in
order to derive central limit theorems) [12, 13, 11, 20, 19]. Only very few
non-asymptotic results have been proven so far, most of which hold under
fairly technical conditions. First, [36, Theorem 4.7] bounded the expected
value of $d(S_{n},b^{*})^{2}$ in NPC spaces. Namely,
$\mathbb{E}[d(S_{n},b^{*})^{2}]\leq\frac{\sigma^{2}}{n}$ where
$\sigma^{2}=\mathbb{E}[d(X_{1},b^{*})^{2}]$ can be interpreted as the variance
of $X_{1}$. [28, Corollary 11] provides the same inequality for $\hat{b}_{n}$,
under the extra constraint that $(M,d)$ has curvature bounded from below. At a
high level, this means that the space $(M,d)$ is not branching (i.e., a
geodesic cannot split, unlike, for instance, in metric trees) and this ensures
some regularity of the tangent cones of $M$. They also extended their result
to spaces $(M,d)$ that are not necessarily NPC, but that satisfy a so-called
hugging condition. However, except for NPC spaces, there is no explicit metric
space that satisfy such a condition. Several non-asymptotic, high probability
bounds are also known for empirical and inductive barycenters. [28] proposes a
definition of sub-Gaussian random variables (eq. (3.10)), closely related to
the one we give below, and proves (Theorem 12), under the hugging condition
mentioned above, a nearly sub-Gaussian tail bound (with a residual term that
decays exponentially fast with $n$) for the empirical barycenter of i.i.d.
sub-Gaussian random variables around the population barycenter $b^{*}$. [3]
obtain concentration inequalities for the empirical barycenter $\hat{b}_{n}$
of i.i.d., bounded random variables with non-parametric rates, under some
metric entropy conditions on $(M,d)$, some of which being similar in spirit to
requiring $M$ to have finite dimension. Finally, most closely related to our
work, [22] proves a Hoeffding-type inequality for the inductive barycenter
$S_{n}$ of i.i.d., bounded random variables in NPC spaces, with particular
focus on metric trees and finite dimensional Hadamard manifolds. In our
Corollary 3.4 below, we improve his results in two ways. First, we
significantly improve the constants. Second, our bound contains two terms.
First, a bias term, which does not contain the probability level $\delta$.
This is the only term where the dimension of the space may appear, through the
variance $\sigma^{2}$ of $X_{1}$. Hence, the second term, which is the sub-
gaussian term (since it is proportional to $\sqrt{\log(1/\delta)}$), is
decoupled from the variance of $X_{1}$.

The paper is organized as follows. In Section 2, we introduce tools from the
concentration of measure theory that will allow us to derive non-asymptotic
bounds for convergence of empirical barycenters. In Section 3, we derive
Hoeffding and Bernstein concentration inequalities for empirical barycenters
in NPC spaces. In Section 4, we extend the previous results in the case of non
identically distributed random variables (but with the same theoretical
barycenter). Finally, in Section 5, we treat the case of possibly positively
curved spaces, and derive an optimal rate concentration bound depending on the
radius of the space.

In what follows, for any positive integer $n$ and any metric space $(M,d)$, we
denote by $d_{1}$ (without mention of the dependence on $n$, for simplicity)
the $L^{1}$ product metric on $M^{n}$, defined as
$d_{1}((x_{1},\ldots,x_{n}),(y_{1},\ldots,y_{n}))=d(x_{1},y_{1})+\ldots+d(x_{n},y_{n})$.

##  2 The Laplace transform and Sub-Gaussian random variables in metric spaces

###  2.1 Laplace transform

In this section, we gather information on the Laplace transform of probability
measures on metric spaces. It will allow us to study precisely the
concentration phenomenon of barycenters in NPC spaces and in particular to
deal with sub-Gaussian random variables in such spaces. Let $(M,d)$ be a
metric space (not necessarily NPC). Denote by $\mathcal{F}$ the class of all
functions $f:M\to\mathbb{R}$ that are $1$-Lipschitz, i.e., such that
$|f(x)-f(y)|\leq d(x,y)$ for all $x,y\in M$. Let $X$ be a random variable in
$M$. For all $k\geq 1$, we say that $X$ has $k$ moments if
$\mathbb{E}[d(X,x_{0})^{k}]$ is finite, where $x_{0}$ is any arbitrary point
in $M$ (note that this definition does not depend on the choice of $x_{0}$).
The Laplace transform of a random variable $X$ that has at least one moment is
defined as (see [30, Section 1.6])

$\Lambda_{X}(\lambda):=\sup_{f\in\mathcal{F}}\mathbb{E}[e^{\lambda(f(X)-\mathbb{E}[f(X)])}],\quad\lambda\geq
0.$ (2)

Note that if $X$ has one moment, then so does $f(X)$, for all
$f\in\mathcal{F}$. Let us underline the following property of the Laplace
transform, whose proof can be found in [30, Proposition 1.15].

######  Lemma 2.1.

If $X_{1},\ldots,X_{n}$ are independent random variables on $(M,d)$ with at
least one moment, then the Laplace transform of the random vector
$(X_{1},\ldots,X_{n})$ in $(M^{n},d_{1})$ satisfies

$\Lambda_{(X_{1},\ldots,X_{n})}\leq\Lambda_{X_{1}}\ldots\Lambda_{X_{n}},$

where we recall that $d_{1}$ is the $L^{1}$ product metric on $M^{n}$.

Finally, we state the following property of the Laplace transform, when a
Lipschitz function is applied to a random variable.

######  Lemma 2.2.

Let $(M^{(1)},d^{(1)})$ and $(M^{(2)},d^{(2)})$ be metric spaces and
$\Phi:M^{(1)}\to M^{(2)}$ be an $L$-Lipschitz function, where $L>0$. Then, for
all random variables $X$ in $M^{(1)}$ with at least one moment,

$\Lambda_{\Phi(X)}(\lambda)\leq\Lambda_{X}(\lambda L),\quad\forall\lambda\geq
0.$

###  2.2 Sub-Gaussian random variables

######  Definition 2.3.

A random variable $X$ in $(M,d)$ is called $K^{2}$-sub Gaussian ($K\geq 0$) if
and only if its Laplace transform satisfies

$\Lambda_{X}(\lambda)\leq
e^{\frac{\lambda^{2}K^{2}}{2}},\quad\forall\lambda\geq 0.$ (3)

This definition of sub-Gaussian random variables is stronger than the standard
definition given in Euclidean spaces, where the Laplace transform is only
defined as a supremum over linear functions, not over all Lipschitz functions.
However, in the context of metric spaces, this definition seems most
appropriate because of the lack of linear functions and, as will be seen in
Lemma 2.7 below, allows us to treat bounded random variables. Moreover, as
opposed to the definition suggested in [28], it does not depend on any
reference point in $M$.

Sub-Gaussian random variables are well understood and play a very important
role in the Euclidean setup. In particular, they are known to enjoy good
concentration properties [37, Section 2.5]. Note that a sub-Gaussian random
variable automatically has infinitely many moments.

The following lemma extends important properties of sub-Gaussian random
variables in metric spaces.

######  Lemma 2.4.

Let $X$ be a random variable in $(M,d)$. The following propositions are
equivalent.

  1. (i)

$X$ is $K^{2}$-sub-Gaussian $(K>0)$.

  2. (ii)

For all $f\in\mathcal{F}$,

$P(|f(X)-\mathbb{E}[f(X)]|\geq t)\leq 2e^{-t^{2}/(2K^{2})}.$

  3. (iii)

For all $f\in\mathcal{F}$,

$\mathbb{E}[e^{a(f(X)-\mathbb{E}[f(X)])^{2}}]\leq 2,$

where $a=\frac{\log 2}{16eK^{2}}$.

In particular, Lemma 2.4 indicates that if $X$ is $K^{2}$-sub-Gaussian, for
some $K>0$, then for any $\delta\in(0,1)$ and for any fixed point $x_{0}\in
M$, it holds with probability at least $1-\delta$ that

$d(X,x_{0})\leq\mathbb{E}[d(X,x_{0})]+K\sqrt{2\log(2/\delta)}.$

The next two propositions show that the sub-Gaussian property is preserved by
products and by Lipschitz transformations.

######  Proposition 2.5.

Let $X_{1},\ldots,X_{n}$ be independent random variables in $M$ such that each
$X_{i}$ is $K_{i}^{2}$-sub-Gaussian for some $K_{i}>0$. Then, the $n$-uple
$(X_{1},\ldots,X_{n})$ is $(K_{1}^{2}+\ldots+K_{n}^{2})$-sub-Gaussian on the
product metric space $(M^{n},d_{1})$.

###### Proof.

This is a direct consequence of Lemma 2.1. ∎

######  Proposition 2.6.

Let $(M^{(1)},d^{(1)})$ and $(M^{(2)},d^{(2)})$ be metric spaces and let $X$
be a random variable in $M_{1}$. Let $K,L>0$. If $X$ is $K^{2}$-sub-Gaussian
and $\Phi:M^{(1)}\to M^{(2)}$ is $L$-Lipschitz, then $\Phi(X)$ is
$(L^{2}K^{2})$-sub Gaussian.

###### Proof.

Let $g:M^{(2)}\rightarrow\mathbb{R}$ be a $1$-Lipschitz function such that
$g(\Phi(X))$ is centered, and let $\tilde{g}:=L^{-1}g\circ\Phi$. Then,
$\tilde{g}:M^{(1)}\rightarrow\mathbb{R}$ is $1$-Lipschitz and $\tilde{g}(X)$
is centered, so we have

$\displaystyle\mathbb{E}e^{\lambda g(\Phi(X))-\mathbb{E}[g(\Phi(X))]}$
$\displaystyle=\mathbb{E}e^{\lambda L(\tilde{g}(X)-\mathbb{E}[\tilde{g}(X)])}$
$\displaystyle\leq\Lambda_{\mu}(\lambda L)$ $\displaystyle\leq
e^{\lambda^{2}L^{2}K^{2}/2}.$

We conclude by taking the supremum over all such functions $g$. ∎

Let us conclude this section by stating an important lemma from [30], which,
similarly to Hoeffding’s lemma for real-valued random variables, indicates
that bounded random variables are always sub-Gaussian.

######  Lemma 2.7.

[30, Proposition 1.16] Let $X$ be a bounded random variable in the metric
space $(M,d)$, i.e. $d(x_{0},X)\leq C$ a.s. for some $x_{0}\in M$ and $C>0$.
Then, $X$ is $4C^{2}$-sub-Gaussian.

##  3 Concentration of empirical barycenters in NPC spaces

###  3.1 Lipschitz property of barycenters

The last ingredient in order to prove concentration of empirical barycenters
and inductive barycenters in NPC spaces is their Lipschitz property, which we
state in the next proposition. Denote by $B_{n}:M^{n}\to M$ the function that
maps any $n$-uple to its (uniquely defined) barycenter and by $\tilde{B}_{n}$
the function that maps any $n$-uple to its inductive barycenter.

######  Proposition 3.1.

Assume that $(M,d)$ is an NPC space. Then, both functions $B_{n}$ and
$\tilde{B}_{n}$ are $(1/n)$-Lipschitz, $M^{n}$ being equipped with the $L^{1}$
product metric $d_{1}$.

###### Proof.

The proof for the inductive barycenter function $\tilde{B}_{n}$ follows from a
simple induction and it can be found in [22, Lemma 3.1].

The $1$-Lipschitz property of $B_{n}$ follows from two different arguments,
which we both give here, because they are both instructive. Let
$\mathcal{P}^{1}(M)$ be the set of all probability measures on $(M,d)$ with
finite first moment. For $\mu\in\mathcal{P}^{1}(M)$, let $B(\mu)$ be its
barycenter, i.e., the (unique) minimizer $b\in M$ of
$\mathbb{E}[d(X,b)^{2}-d(X,b_{0})^{2}]$, where $X\sim\mu$ and $x_{0}\in M$ is
arbitrarily fixed.

The first argument follows from [31, Theorem 3.4], which provides a
deterministic connection between barycenters and their inductive versions. Let
$(x_{1},\ldots,x_{n})$ and $(y_{1},\ldots,y_{n})$ be two $n$-uples in $M$. We
extend these $n$-uples into periodic infinite sequences by setting, for all
positive integers $k$, $x_{k}=x_{r_{k}}$ and $y_{k}=y_{r_{k}}$, where $r_{k}$
is the unique integer between $1$ and $n$ such that $k-r_{k}$ is a multiple of
$n$. Then, [31, Theorem 3.4] indicates that
$\tilde{B}_{k}(x_{1},\ldots,x_{k})$ and $\tilde{B}_{k}(y_{1},\ldots,y_{k})$
converge to $B_{n}(x_{1},\ldots,x_{n})$ and $B_{n}(y_{1},\ldots,y_{n})$
respectively, as $k\to\infty$. Moreover, thanks to the $(1/(qn))$-Lipschitz
feature of $\tilde{B}_{qn}$ proved above, one has, for all positive integers
$q$,

$\displaystyle
d(\tilde{B}_{qn}(x_{1},\ldots,x_{qn}),\tilde{B}_{qn}(y_{1},\ldots,y_{qn}))$
$\displaystyle\quad\quad\leq\frac{1}{qn}\sum_{k=1}^{qn}d(x_{k},y_{k})=\frac{1}{n}\sum_{k=1}^{n}d(x_{k},y_{k}).$

Taking the limit as $q\to\infty$ yields the $(1/n)$-Lipschitz property of
$B_{n}$.

The second argument uses Jensen’s inequality, which implies that the
barycenter functional $B$ is contractive over $\mathcal{P}^{1}(M)$, equipped
with the Wasserstein distance $W_{1}$ [36, Theorem 6.3]. More precisely, for
all probability measures $\mu,\nu\in\mathcal{P}^{1}(M)$, it holds that
$d(B(\mu),B(\nu))\leq W_{1}(\mu,\nu)$, where
$W_{1}(\mu,\nu)=\inf_{X\sim\mu,Y\sim\nu}\mathbb{E}[d(X,Y)]$. Now, fix two
$n$-uples $(x_{1},\ldots,x_{n})$ and $(y_{1},\ldots,y_{n})$ in $M^{n}$ and set
$\mu=n^{-1}\sum_{i=1}^{n}\delta_{x_{i}}$ and
$\nu=n^{-1}\sum_{i=1}^{n}\delta_{y_{i}}$. It is clear that
$B(\mu)=B_{n}(x_{1},\ldots,x_{n})$ and $B(\nu)=B_{n}(y_{1},\ldots,y_{n})$.
Moreover,
$W_{1}(\mu,\nu)\leq\frac{1}{n}(d(x_{1},y_{1})+\ldots+d(x_{n},y_{n}))$, which
can be seen by taking the coupling $(X,Y)$ of $\mu$ and $\nu$ such that
$P(X=a_{i},Y=b_{i})=\frac{1}{n},i=1,\ldots,n$. ∎

######  Remark 3.2.

The above proposition actually only requires that $(M,d)$ is a Buseman space,
i.e., a metric space $(M,d)$ such that the metric $d$ is geodesically convex
jointly in both variables. This property is weaker than the NPC property,
since any NPC space is a Buseman space, but, for instance, strictly convex
normed spaces are Buseman but not NPC.

###  3.2 A concentration inequality for barycenters of sub-Gaussian random
variables

We are now in position to state our first main result, which implies
concentration of the empirical barycenter and the inductive barycenter of
i.i.d. sub-Gaussian random variables in an NPC metric space. This result is a
direct consequence of Propositions 2.5 and 2.6 above.

######  Theorem 3.3.

Let $(M,d)$ be an NPC space and $X_{1},...,X_{n}$ be independent random
variables in $(M,d)$ such that for all $i=1,\ldots,n$, $X_{i}$ is
$K_{i}^{2}$-sub-Gaussian, for some $K_{i}>0$. Then both the empirical and
inductive barycenters of $X_{1},...,X_{n}$ are
$\frac{K_{1}^{2}+\ldots+K_{n}^{2}}{n^{2}}$-sub Gaussian.

As a consequence, thanks to Lemma 2.4, for all $1$-Lipschitz functions
$f:M\to\mathbb{R}$ and for all $\delta\in(0,1)$, it holds with probability at
least $1-\delta$ that

$f(T_{n})\leq\mathbb{E}[f(T_{n})]+\bar{K}_{n}\sqrt{\frac{\log(1/\delta)}{n}},$
(4)

where $T_{n}$ is either the empirical or the inductive barycenter of
$X_{1},\ldots,X_{n}$ and $\bar{K}_{n}=\sqrt{K_{1}^{2}+\ldots+K_{n}^{2}}$.

Assume that $X_{1},\ldots,X_{n}$ are i.i.d. and let $b^{*}$ be their
(population) barycenter. Denote by $\hat{b}_{n}$ their empirical barycenter
and by $\tilde{b}_{n}$ their inductive barycenter. Then, of particular
interest is taking $f=d(\cdot,b^{*})$ in (4). Let
$\sigma^{2}=\mathbb{E}[d(X_{1},b^{*})^{2}]$ be the variance of $X_{1}$. When
$T_{n}$ is the inductive barycenter of $X_{1},\ldots,X_{n}$, it follows from
Sturm’s law of large numbers [36, Theorem 4.7] that
$\mathbb{E}[d(T_{n},b^{*})]\leq\frac{\sigma}{\sqrt{n}}$. When $T_{n}$ is the
empirical barycenter of $X_{1},\ldots,X_{n}$, the same inequality holds thanks
to [28, Corollary 11] when the space $(M,d)$ has moreover its curvature
bounded from below. Therefore, we get the following corollary.

######  Corollary 3.4.

Under the same assumptions and notation as in Theorem 3.3, let $T_{n}$ be
either the empirical or the inductive barycenter of $X_{1},\ldots,X_{n}$. If
$T_{n}$ is the empirical barycenter $\hat{b}_{n}$, further assume that $(M,d)$
has curvature bounded from below. Then, for all $\delta\in(0,1)$, it holds
with probability at least $1-\delta$ that

$d(T_{n},b^{*})\leq\frac{\sigma}{\sqrt{n}}+K\sqrt{\frac{\log(1/\delta)}{n}}$

We can now state Hoeffding’s inequality in global NPC spaces.

######  Corollary 3.5.

Let $(M,d)$ be a NPC space, and let $X_{1},...,X_{n}$ be i.i.d random
variables and assume that $X_{1}\in B(x_{0},C)$ almost surely, for some
$x_{0}\in M$ and $C>0$. Let $T_{n}$ be either the empirical or the inductive
barycenter of $X_{1},\ldots,X_{n}$. If $T_{n}$ is the empirical barycenter
$\hat{b}_{n}$, further assume that $(M,d)$ has curvature bounded from below.
Then, for all $\delta\in(0,1)$, it holds with probability at least $1-\delta$
that

$d(T_{n},b^{*})\leq\frac{\sigma}{\sqrt{n}}+2C\sqrt{\frac{\log(1/\delta)}{n}}.$

The left hand side of this concentration inequality contains two terms. The
first one is a bias term, which simply controls the expected distance from
$T_{n}$ to $b^{*}$ and the second one is a stochastic term, which contains the
probability level $\delta$. If $(M,d)$ is a Hilbert space (which is a special
instance of NPC spaces), this inequality actually reads as

$d(T_{n},b^{*})\leq\sqrt{\frac{\mathrm{tr}\Sigma}{n}}+2C\sqrt{\frac{\log(1/\delta)}{n}},$

where $\Sigma$ is the covariance operator of $X_{1}$. For instance, if
$M=\mathbb{R}^{p}$ equipped with the Euclidean structure and $\Sigma$ is the
identity matrix, then $\mathrm{tr}\Sigma=p$ and the dimension of $M$ only
appears in the bias term, not the stochastic one. This is why Corollary 3.4 is
a significant improvement over Funano’s result [22].

As a consequence of Corollary 3.4, we get the following algorithmic PAC
guarantee for the computation of the barycenter of $n$ fixed points
$x_{1},\ldots,x_{n}$ ($n\geq 1$) in an NPC space $(M,d)$. Fix $\varepsilon>0$
and $\delta\in(0,1)$. Sample $m$ integers $I_{1},\ldots,I_{m}$ independently,
uniformly at random between $1$ and $n$, and set
$X_{1}=x_{I_{1}},\ldots,X_{m}=x_{I_{m}}$, which are i.i.d. random variables
with distribution $\mu=n^{-1}\sum_{i=1}^{n}\delta_{x_{i}}$. Finally,
iteratively compute $\tilde{b}_{m}$, the inductive barycenter of
$X_{1},\ldots,X_{m}$.

######  Corollary 3.6.

Denote by $b^{*}$ the barycenter of $x_{1},\ldots,x_{n}$. Let $D$ be the
diameter of the set $\\{x_{1},\ldots,x_{n}\\}$. Then, if
$m\gtrsim\frac{D^{2}}{\varepsilon^{2}}\max(1,\log(1/\delta))$, it holds that
$d(\tilde{b}_{m},b^{*})\leq\varepsilon$ with probability at least $1-\delta$.

The proof of this corollary simply uses the fact that the variance
$\sigma^{2}$ of $\mu$, which is supported on a set of diameter $D$, is bounded
by $4D^{2}$. To the best of our knowledge, Corollary 3.6 is the first PAC
guarantee for the computation of barycenters in metric spaces. Note that this
bound can even be further improved, using Theorem 3.7 below, see Section 3.4.

In comparison to this guarantee, [31, Theorem 3.4] gives a deterministic
guarantee for finding an $\varepsilon$-approximation of the barycenter of
$x_{1},\ldots,x_{n}$, after $\frac{n(D^{2}+\sigma^{2})}{\varepsilon^{2}}$
steps: The complexity of their algorithm is $n$ times worse than ours, where
$n$ is the number of input points.

Perhaps surprinsingly, the sample complexity bound given in Corollary 3.6 does
not require any bound on some notion of dimension of the space $M$. However,
the algorithm implicitly requires the computation of geodesic segments, at
each iteration of the sequence of inductive barycenters
$\tilde{b}_{1},\ldots,\tilde{b}_{m}$. Such computations have a complexity
which, in general, shall depend on the dimension (in a certain sense) of $M$.
When $(M,d)$ is a metric tree, the computation of the inductive barycenters
simply requires to identify the shortest paths between any two points, which
can be done efficiently.

###  3.3 An example: Matrix geometric means

In this section, we consider the computation of the geometric mean of $n$
symmetric, positive definite matrices $A_{1},\ldots,A_{n}\in\mathcal{S}_{p}$
($p\geq 1$). Recall that the geometric mean of $A_{1},\ldots,A_{p}$ is their
barycenter, associated with the metric
$d(A,B)=\|\log(A^{-1/2BA^{-1/2}}\|_{\textsf{F}}$, for all
$A,B\in\mathcal{S}_{p}$. It is known that $\mathcal{S}_{p}$, equipped with
this metric, is an NPC space [9, Proposition 5]. The geometric mean of two
matrices $A,B\in\mathcal{S}_{p}$ is the matrix
$A\\#B=A^{1/2}(A^{-1/2}BA^{-1/2})^{1/2}A^{1/2}$ and more generally, the
geodesic segment between $A$ and $B$ is given by
$\gamma_{A,B}(s)=A^{1/2}(A^{-1/2}BA^{-1/2})^{s}A^{1/2}$, also denoted by
$A\\#_{s}B$, for all $s\in[0,1]$.

The sequence of inductive barycenters is defined as follows:

  * •

$S_{1}=A_{1}$;

  * •

$S_{2}=S_{1}\\#A_{2}=A_{1}^{1/2}(A_{1}^{-1/2}A_{2}A_{1}^{-1/2})^{1/2}A_{1}^{1/2}$;

  * •

For $k=2,\ldots,m$,
$S_{k}=S_{k-1}\\#_{\frac{1}{k}}A_{k}=S_{k-1}^{1/2}(S_{k-1}^{-1/2}A_{k}S_{k-1}^{-1/2})^{1/k}S_{k-1}^{1/2}$.

Exact computation of each $S_{k},k=2,\ldots,m$, requires matrix products and
eigendecompositions, whose complexity depends on the size $p$ of the matrices.
In fact, there are faster ways to compute good approximations of $A\\#_{s}B$,
for $A,B\in\mathcal{S}_{p}$ and $s\in[0,1]$, e.g., by using integral
representations and Gaussian quadrature: We refer, for instance, to [8, 35]
for more details.

###  3.4 Bernstein inequality: A refinement in the case of small variance

In this section, we derive a Bernstein inequality refining Hoeffding’s lemma
in the case where the $X_{i}$’s have a small variance, i.e., much smaller than
the diameter of their support.

######  Theorem 3.7.

Let $(M,d)$ be an NPC space and $X_{1},\ldots,X_{n}$ be i.i.d. random
variables in $(M,d)$. Assume that $d(X_{1},x_{0})\leq C$ almost surely, for
some $x_{0}\in M$ and $C>0$. Then, for all $1$-Lipschitz functions
$f:M\to\mathbb{R}$ and for all $\delta\in(0,1)$,

$f(T_{n})\leq\mathbb{E}[f(T_{n})]+\min\left(2\sigma\sqrt{\frac{\log(1/\delta)}{n}},\frac{8C\log(1/\delta)}{3n}\right),$

where $T_{n}$ denotes either the empirical or the inductive barycenter of
$X_{1},...,X_{n}$ and $\sigma^{2}=\mathbb{E}[d(X_{1},b^{*})^{2}]$ denotes the
variance of $X_{1}$, with $b^{*}$ the barycenter of the distribution of
$X_{1}$.

When the $X_{i}$’s have a very small variance, i.e., significantly smaller
than the diameter $C$ of their support, this inequality greatly improves
Corollary 3.4. By taking $f=d(\cdot,b^{*})$, we obtain the following version
of Bernstein’s inequality in NPC spaces.

######  Corollary 3.8.

With the same assumptions and notation as in Theorem 3.7, let $T_{n}$ be
either the empirical or the inductive barycenter of $X_{1},\ldots,X_{n}$. If
$T_{n}$ is the empirical barycenter $\hat{b}_{n}$, further assume that $(M,d)$
has curvature bounded by below. Then, with probability at least $1-\delta$, it
holds that

$d(T_{n},b^{*})\leq\frac{\sigma}{\sqrt{n}}+\max\left(2\sigma\sqrt{\frac{\log(1/\delta)}{n}},\frac{8C\log(1/\delta)}{3n}\right).$

###### Proof of Theorem 3.7.

For all $\lambda\geq 0$ and $f\in\mathcal{F}$, let
$\psi(\lambda,f)=\log\mathbb{E}[e^{\lambda(f(X_{1})-\mathbb{E}[f(X_{1})])}]$,
for $\lambda\geq 0$ and $f\in\mathcal{F}$. Using the inequality $\log(u)\leq
1-u$, for all $u>0$, it holds that

$\displaystyle\psi(\lambda,f)\leq$
$\displaystyle\quad\mathbb{E}\left[e^{\lambda(f(X_{1})-\mathbb{E}[f(X_{1})])}-1-\lambda(f(X_{1})-\mathbb{E}f(X_{1}))\right],$

for all $\lambda\geq 0$ and $f\in\mathcal{F}$. Since $X_{1}\in B(x_{0},C)$
almost surely, we have that $f(X_{1})-\mathbb{E}f(X_{1})\leq 2C$, for all
$f\in\mathcal{F}$. Therefore, since the map $u\mapsto\frac{e^{u}-1-u}{u^{2}}$
is increasing, we obtain that

$\displaystyle\psi(\lambda,f)$
$\displaystyle\leq\mathbb{E}\left[\frac{e^{2\lambda C}-1-2\lambda
C}{4C^{2}}(f(X_{1})-\mathbb{E}f(X_{1}))^{2}\right]$
$\displaystyle=\frac{e^{2\lambda C}-1-2\lambda
C}{4C^{2}}\mathrm{Var}(f(X_{1})).$

Moreover, for all $f\in\mathcal{F}$, $\mathrm{Var}(f(X_{1}))\leq\sigma^{2}$.
Indeed,

$\displaystyle\mathrm{Var}(f(X_{1}))$
$\displaystyle=\mathbb{E}\left[(f(X_{1})-\mathbb{E}[f(X_{1})])^{2}\right]$
$\displaystyle\leq\mathbb{E}\left[(f(X_{1})-f(b^{*}))^{2}\right]$ (5)
$\displaystyle\leq\mathbb{E}\left[d(X_{1},b^{*})^{2}\right]$
$\displaystyle=\sigma^{2},$

where (5) follows from the fact that
$\mathbb{E}\left[(f(X_{1})-\mathbb{E}[f(X_{1})])^{2}\right]\leq\mathbb{E}\left[(f(X_{1})-a)^{2}\right]$
for all $a\in\mathbb{R}$, and in particular for $a=f(b^{*})$.

By Lemma 2.1, it follows that

$\Lambda_{X_{1},\ldots,X_{n}}(\lambda)\leq
e^{\frac{n\sigma^{2}}{4C^{2}}(e^{2\lambda C}-1-2\lambda C)},$

for all $\lambda\geq 0$. Now, let $T_{n}$ be either the empirical or the
inductive barycenter of $X_{1},\ldots,X_{n}$. It follows from Proposition 3.1
and Lemma 2.2 that

$\Lambda_{T_{n}}(\lambda)\leq e^{\frac{n\sigma^{2}}{4C^{2}}(e^{2\lambda
C/n}-1-2\lambda C/n)},$

for all $\lambda\geq 0$.

By Chernoff’s bound, we obtain, for all $f\in\mathcal{F}$,

$\displaystyle P\left(f(T_{n})-\mathbb{E}f(T_{n})\geq t\right)$
$\displaystyle\leq e^{-\lambda
t}\mathbb{E}e^{\lambda(f(T_{n})-\mathbb{E}f(T_{n}))}$ $\displaystyle\leq
e^{-\lambda t+\log\Lambda_{T_{n}}(\lambda)}$
$\displaystyle\leq\exp\left[-\lambda t+\left(e^{\frac{2\lambda
C}{n}}-1-\frac{2\lambda C}{n}\right)\frac{n\sigma^{2}}{4C^{2}}\right].$

By optimizing in $\lambda\geq 0$, we find the best one to be
$\lambda=\frac{n}{2C}\log\left(1+\frac{2Ct}{\sigma^{2}}\right)$ and therefore,

$P\left(f(T_{n})-\mathbb{E}f(T_{n})\geq
t\right)\leq\exp\left(-\frac{n\sigma^{2}}{4C^{2}}\,h\left(\frac{2Ct}{\sigma^{2}}\right)\right)$

where $h(u)=(1+u)\log(1+u)-u$, for all $u\geq 0$. Since
$h(u)\geq\frac{u^{2}}{2(1+\frac{u}{3})}$ for all $u\geq 0$, we obtain

$P\left(f(T_{n})-\mathbb{E}f(T_{n})\geq
t\right)\leq\exp\left(-\frac{nt^{2}}{2(\sigma^{2}+\frac{2Ct}{3})}\right),$

which yields the desired result. ∎

######  Remark 3.9.

In the above concentration inequalities, we assume that the space $(M,d)$ has
curvature bounded by below, when we consider empirical barycenters. The reason
is to be able to apply the bound on the expectation of $d(\hat{b}_{n},b^{*})$
proven in [28, Corollary 11]. Indeed, for general NPC spaces, there is no
available upper bound on $\mathbb{E}[d(\hat{b}_{n},b^{*})]$ (however, the
bound that is available for $S_{n}$ [36, Theorem 4.7] is valid in any NPC
space). We do believe that the bound
$\mathbb{E}[d(\hat{b}_{n},b^{*})^{2}]\leq\frac{\sigma^{2}}{n}$ is valid in all
NPC spaces, even those with no lower bound on the curvature, i.e., those that
can be branching. The simplest and most natural example of an NPC space with
no lower curvature bound is a metric tree. Indeed, such a space is
$\textrm{CAT}(\kappa)$, for all $\kappa\in\mathbb{R}$, since all the geodesic
triangles are flat (see Section 5.1 for formal definitions). In a metric tree,
barycenters are known to be sticky, i.e., even a large perturbation of some of
the points $x_{1},\ldots,x_{n}$ may result in no change of their barycenter
[36, Proposition 5.7]. In particular, barycenters are more rigid in such
spaces and empirical barycenters are known to have faster asymptotic rates
[24]. This is why we expect that their behavior should not be worse than in
NPC spaces with lower curvature bounds.

Theorem 3.7 yields the following algorithmic corollary, which is a refinement
of Corollary 3.6.

######  Corollary 3.10.

Recall the notation of Corollary 3.6. Let $D$ be the diameter of the set
$\\{x_{1},\ldots,x_{n}\\}$ and $\sigma^{2}=\min_{b\in
M}\frac{1}{n}\sum_{i=1}^{n}d(x_{i},b)^{2}$. Then, if

$m\gtrsim\max\left(\frac{\sigma^{2}}{\varepsilon^{2}},\frac{D}{\varepsilon}\right)\log(1/\delta),$
(6)

it holds that $d(\tilde{b}_{m},b^{*})\leq\varepsilon$ with probability at
least $1-\delta$.

In practice, of course, computing $\sigma^{2}$ can be costly. However, in (6),
it can be replaced by any upper bound, such as $\frac{1}{n}d(x_{i},b)^{2}$ for
any fixed $b\in M$, or $\frac{1}{n^{2}}\sum_{1\leq i,j\leq
n}d(x_{i},x_{j})^{2}$. Computing $\frac{1}{n}d(x_{i},b)^{2}$ only requires $n$
computations, but the choice of $b$ can be suboptimal. On the other hand,
computing $\frac{1}{n^{2}}\sum_{1\leq i,j\leq n}d(x_{i},x_{j})^{2}$ requires a
quadratic (in $n$) number of computations, but yields a tight bound on
$\sigma^{2}$, up to a factor $2$. Indeed, one has the following lemma.

######  Lemma 3.11.

Let $X$ be a random variable in $M$ with two moments and let $Y$ be an
independent copy of $M$. Let $\sigma^{2}=\min_{b\in M}\mathbb{E}[d(X,b)^{2}]$.
Then,

$\sigma^{2}\leq\mathbb{E}[d(X,Y)^{2}]\leq 2\sigma^{2}.$

###### Proof.

The right hand side is obvious thanks to the triangle inequality (and it does
not require independence of $X$ and $Y$). For the left hand side, denote by
$F(b)=\mathbb{E}[d(X,b)^{2}]$, for all $b\in M$. Then, $\sigma^{2}=\min_{b\in
M}F(b)$ and independence of $X$ and $Y$ yields that $\sigma^{2}\leq
F(Y)=\mathbb{E}[d(X,Y)^{2}|Y]$. The result follows by taking the expectation
on both sides. ∎

The concentration inequalities given in Theorems 3.4 and 3.8 can be extended
to the case when the $X_{i}$’s are independent but not identically
distributed, which is the object of next section.

##  4 Concentration inequalities for non-identically distributed random
variables

In this section, we extend Corollary 3.4 and 3.8 to the case where
$X_{1},\ldots,X_{n}$ are independent, but not identically distributed, and
share the same barycenter $b^{*}$.

######  Theorem 4.1.

Let $(M,d)$ be a NPC space, and let $X_{1},...,X_{n}$ be independent random
variables with same barycenter $b^{*}\in M$. Further assume that for all
$i=1,\ldots,n$, $X_{i}\in B(x_{i},C_{i})$ almost surely, for some $x_{i}\in M$
and $C_{i}>0$. Let $T_{n}$ be either the empirical or the inductive barycenter
of $X_{1},\ldots,X_{n}$. If $T_{n}=\hat{b}_{n}$, further assume that $M$ has a
curvature lower bound. Then, for all $\delta\in(0,1)$, it holds with
probability at least $1-\delta$ that

$d(T_{n},b^{*})\leq\frac{\overline{\sigma}_{n}}{\sqrt{n}}+\overline{C}_{n}\sqrt{\frac{\log(1/\delta)}{n}},$

where
$\overline{\sigma}_{n}=\sqrt{\frac{\sigma_{1}^{2}+\ldots+\sigma_{n}^{2}}{n}}$
and $\overline{C}_{n}=\sqrt{\frac{C_{1}^{2}+\ldots+C_{n}^{2}}{n}}.$

###### Proof.

The proof is similar to that of Proposition 3.4, and the main difference is in
bounding the bias term $\mathbb{E}[d(T_{n},b^{*})]$. When $T_{n}$ is the
empirical barycenter, a close inspection of the proof of [28, Corollary 11]
indicates that the $X_{i}$’s need not be identically distributed and one
readily obtains
$\mathbb{E}[d(\hat{b}_{n},b^{*})]\leq\frac{\overline{\sigma}_{n}}{\sqrt{n}}$.
When $T_{n}$ is the inductive barycenter, we adapt the proof of [36, Theorem
4.7] and obtain the following lemma.

∎

######  Lemma 4.2.

Let $X_{1},\ldots,X_{n}$ be independent random points with two moments in an
NPC space $(M,d)$ and with same barycenter $b^{*}$. Then,

$\mathbb{E}[d(S_{n},b^{*})^{2}]\leq\frac{\sigma_{1}^{2}+\ldots+\sigma_{n}^{2}}{n^{2}},$

where $\sigma^{2}=\mathbb{E}[d(X_{i},b^{*})^{2}]$ is the variance of $X_{i}$,
for $i=1,\ldots,n$.

###### Proof.

The proof of this lemma follows the same lines as the proof of [36, Theorem
4.7] and proceeds by induction on $n$. Denote by
$V_{n}=\mathbb{E}[d(S_{n},b^{*})^{2}]$ and by
$F_{n}(x)=\mathbb{E}[d(X_{n},x)^{2}]$, for all $x\in M$. Then, by the
$2$-geodesic strong convexity of the squared distance to any given point, one
obtains

$\displaystyle V_{n}$
$\displaystyle\leq\mathbb{E}\left[\left(1-\frac{1}{b}\right)d(S_{n-1},b^{*})^{2}+\frac{1}{n}d(X_{n},b^{*})^{2}-\frac{n-1}{n^{2}}d(S_{n-1},X_{n})^{2}\right]$
$\displaystyle=\frac{n-1}{n}V_{n-1}+\frac{\sigma_{n}^{2}}{n}-\frac{n-1}{n^{2}}\mathbb{E}[F_{n}(S_{n-1})],$

where we use the fact that $X_{n}$ and $S_{n-1}$ are independent, by
construction of $S_{n-1}$ (which only depends on $X_{1},\ldots,X_{n-1}$). Now,
again by the $2$-geodesic strong convexity of the squared distance to any
given point, we obtain that $F_{n}$ is also $2$-geodescailly strongly convex,
yielding $F(S_{n})\geq F(b^{*})+d(S_{n},b^{*})^{2}$ almost surely, since
$b^{*}$ is the minimizer of $F_{n}$ by assumption. Therefore, it follows that

$\displaystyle V_{n}$
$\displaystyle\leq\frac{n-1}{n}V_{n-1}+\frac{\sigma_{n}^{2}}{n}-\frac{n-1}{n^{2}}\sigma_{n}^{2}-\frac{n-1}{n^{2}}V_{n-1}$
$\displaystyle=\frac{(n-1)^{2}}{n^{2}}V_{n-1}+\frac{\sigma_{n}^{2}}{n^{2}}.$

In other words, $n^{2}V_{n}\leq(n-1)^{2}V_{n-1}+\sigma_{n}^{2}$. Since, by
definition of $S_{1}$, $V_{1}=\sigma_{1}^{2}$, the result follows by
induction.

∎

Finally, we also have the following generalization of Corollary 3.8 when the
$X_{i}$’s are not identically distributed.

######  Theorem 4.3.

Let $(M,d)$ be an NPC space and $X_{1},\ldots,X_{n}$ be independent random
variables in $(M,d)$. Assume that $d(X_{i},x_{0})\leq C$ almost surely, for
all $i=1,\ldots,n$, for some fixed $x_{0}\in M$ and $C>0$. let $T_{n}$ be
either the empirical or the inductive barycenter of $X_{1},\ldots,X_{n}$. If
$T_{n}$ is the empirical barycenter $\hat{b}_{n}$, further assume that $(M,d)$
has curvature bounded by below. Then, for all $\delta\in(0,1)$, it holds with
probability at least $1-\delta$ that

$d(T_{n},b^{*})\leq\frac{\overline{\sigma}_{n}}{\sqrt{n}}+\min\left(2\overline{\sigma}_{n}\sqrt{\frac{\log(1/\delta)}{n}},\frac{8C\log(1/\delta)}{3n}\right),$

where $\overline{\sigma}_{n}$ is as in Theorem 4.1.

In Theorem 4.1, when $X_{1},\ldots,X_{n}$ do not even share the same
barycenter, we still have the following fact, for any fixed $b\in M$. For any
$\delta\in(0,1)$, it holds with probability at least $1-\delta$ that

$d(T_{n},b)\leq\mathbb{E}[d(T_{n},b)]+\overline{C}_{n}\sqrt{\frac{\log(1/\delta)}{n}}.$

However, it is not clear what $b$ to choose in order to make the first term as
small as possible. If $b_{1},\ldots,b_{n}$ are the respective population
barycenters of $X_{1},\ldots,X_{n}$ (i.e., each $b_{i}$ minimizes
$\mathbb{E}[d(X_{i},b)^{2}]$ over $b\in M$), a natural candidate for $b$ would
be the barycenter of $b_{1},\ldots,b_{n}$.

######  Open question.

Let $X_{1},\ldots,X_{n}$ be independent random variables in $M$, with two
moments. For each $i=1,\ldots,n$, let $b_{i}$ be the barycenter of $X_{i}$ and
$\sigma_{i}^{2}=\mathbb{E}[d(X_{i},b_{i})^{2}]$ its variance. Is it true that

$\mathbb{E}[d(\hat{b}_{n},b_{n}^{*})^{2}]\leq\frac{\overline{\sigma}_{n}^{2}}{n},$

where $b_{n}^{*}$ is the barycenter of $b_{1},\ldots,b_{n}$ and
$\overline{\sigma}_{n}^{2}=\frac{\sigma_{1}^{2}+\ldots+\sigma_{n}^{2}}{n}$, as
in Theorem 4.1?

##  5 Beyond non-positively curved spaces

It is natural to ask whether Theorems 3.3 and 3.7 still hold, perhaps with
worse constants and/or rates, without the non-positive curvature assumption. A
natural framework to do that is the notion of CAT spaces. Briefly, a metric
space is said to be $\textrm{CAT}(\kappa)$, $\kappa\in\mathbb{R}$, when its
triangles are thinner than they would be in the model space of curvature
$\kappa$ (hyperbolic plane if $\kappa<0$, Euclidean plane if $\kappa=0$ and
$2$-dimensional sphere of radius $1/\kappa$ if $\kappa>0$): See [14, 15] for
an introduction to CAT spaces. In this terminology, NPC spaces are
$\textrm{CAT}(0)$ spaces. An important example of at $\textrm{CAT}(\kappa)$
space, which is closely related to optimal transport theory, for $\kappa>0$,
is the space of all symmetric positive definite matrices of size $p\geq 1$,
with all eigenvalues that are at least $\sqrt{3/(2\kappa)}$ [32, Proposition
2], equipped with the Bures-Wasserstein metric. The Bures-Wasserstein metric
between any two symmetric positive definite matrices $A,B$ in
$\mathbb{R}^{p\times p}$ is given by
$W_{2}(\mathcal{N}(0,A),\mathcal{N}(0,B))$, where $W_{2}$ is the
$2$-Wasserstein distance and $\mathcal{N}(0,A)$ is the $p$-variate centered
Gaussian distribution with covariance matrix $A$. We refer the reader to [10]
for more information about the Bures-Wasserstein metric. Let us first
introduce some background on CAT spaces.

###  5.1 Background on CAT spaces

In this section, we give the precise definition of CAT spaces. We refer the
reader to the book [4] for a complete view on the topic. First, we introduce a
family of model spaces that will allow us to define local and global curvature
bounds in the sequel. Let $\kappa\in\mathbb{R}$.

####  $\kappa=0$: Euclidean plane

Set $M_{0}=\mathbb{R}^{2}$, equipped with its Euclidean metric. This model
space corresponds to zero curvature, is a geodesic space where geodesics are
unique and given by line segments.

####  $\kappa>0$: Sphere

Set $M_{\kappa}=\frac{1}{\sqrt{\kappa}}\mathbb{S}^{2}$: This is the
$2$-dimensional Euclidean sphere, embedded in $\mathbb{R}^{3}$, with center
$0$ and radius $1/\sqrt{\kappa}$, equipped with the arc length metric:
$d_{\kappa}(x,y)=\frac{1}{\sqrt{\kappa}}\arccos(\kappa x^{\top}y)$, for all
$x,y\in M_{\kappa}$. This is a geodesic space where the geodesics are unique
except for antipodal points, and given by arcs of great circles. Here, a great
circle is the intersection of the sphere with any plane going through the
origin.

####  $\kappa<0$: Hyperbolic space

Set $M_{\kappa}=\frac{1}{\sqrt{\kappa}}\mathbb{H}^{2}$, where
$\mathbb{H}^{2}=\\{(x_{1},x_{2},x_{3})\in\mathbb{R}^{3}:x_{3}>0,x_{1}^{2}+x_{2}^{2}-x_{3}^{2}=-1\\}$.
The metric is given by
$d_{\kappa}=\frac{1}{\sqrt{-\kappa}}\textrm{arccosh}(-\kappa\langle
x,y\rangle)$, for all $x,y\in M_{\kappa}$, where $\langle
x,y\rangle=x_{1}y_{1}+x_{2}y_{2}-x_{3}y_{3}$. This is a geodesic space where
geodesics are always unique and are given by arcs of the intersections of
$M_{\kappa}$ with planes going through the origin.

For $\kappa\in\mathbb{R}$, let $D_{\kappa}$ be the diameter of the model space
$M_{\kappa}$, i.e., $\displaystyle D_{\kappa}=\begin{cases}\infty\mbox{ if
}\kappa\leq 0\\\ \frac{\pi}{\kappa}\mbox{ if }\kappa>0\end{cases}$.

Let $(M,d)$ be a geodesic space, i.e., a metric space where any two points
have at least one geodesic between them. The notion of curvature (lower or
upper) bounds for $(M,d)$ is defined by comparing the triangles in $M$ with
triangles with the same side lengths in model spaces.

######  Definition 5.1.

A (geodesic) triangle in $M$ is a set of three points in $M$ (the vertices)
together with three geodesic segments connecting them (the sides).

Given three points $x,y,z\in S$, we abusively denote by $\Delta(x,y,z)$ a
triangle with vertices $x,y,z$, with no mention to which geodesic segments are
chosen for the sides (geodesics between points are not necessarily unique, as
seen for example on a sphere, between any two antipodal points). The perimeter
of a triangle $\Delta=\Delta(x,y,z)$ is defined as
$\mathrm{per}(\Delta)=d(x,y)+d(y,z)+d(x,z)$. It does not depend on the choice
of the sides.

######  Definition 5.2.

Let $\kappa\in\mathbb{R}$ and $\Delta$ be a triangle in $M$ with
$\mathrm{per}(\Delta)<2D_{\kappa}$. A comparison triangle for $\Delta$ in the
model space $M_{\kappa}$ is a triangle $\bar{\Delta}\subseteq M_{\kappa}$ with
same side lengths as $\Delta$, i.e., if $\Delta=\Delta(x,y,z)$, then
$\bar{\Delta}=\Delta(\bar{x},\bar{y},\bar{z})$ where $\bar{x},\bar{y},\bar{z}$
are any points in $M_{\kappa}$ satisfying

$\begin{cases}d(x,y)=d_{\kappa}(\bar{x},\bar{y})\\\
d(y,z)=d_{\kappa}(\bar{y},\bar{z})\\\
d(x,z)=d_{\kappa}(\bar{x},\bar{z}).\end{cases}$

Note that a comparison triangle in $M_{\kappa}$ is always unique up to rigid
motions. We are now ready to define curvature bounds. Intuitively, we say that
$(M,d)$ has global curvature bounded from above (resp. below) by $\kappa$ if
all its triangles (with perimeter smaller than $2D_{\kappa}$) are thinner
(resp. fatter) than their comparison triangles in the model space
$M_{\kappa}$.

######  Definition 5.3.

Let $\kappa\in\mathbb{R}$. We say that $(M,d)$ has global curvature bounded
from above (resp. below) by $\kappa$ if and only if for all triangles
$\Delta\subseteq M$ with $\mathrm{per}(\Delta)<2D_{\kappa}$ and for all
$x,y\in\Delta$, $d(x,y)\leq d_{\kappa}(\bar{x},\bar{y})$ (resp. $d(x,y)\leq
d_{\kappa}(\bar{x},\bar{y})$), where $\bar{x}$ and $\bar{y}$ are the points on
a comparison triangle $\bar{\Delta}$ in $M_{\kappa}$ that correspond to $x$
and $y$. We then call $(M,d)$ a $\textrm{CAT}(\kappa)$ (resp.
$\textrm{CAT}^{+}(\kappa)$) space.

###  5.2 Barycenters in CAT spaces

Now, the goal of the next section is to derive some non-asymptotic
concentration bounds for the empirical barycenters in $\textrm{CAT}(\kappa)$
spaces when $\kappa>0$. It is well known that barycenters may no longer be
unique in such spaces. For instance, any point on the equator is a barycenter
of the North and South poles, on any sphere. However, it is known that if a
probability measure on a $\textrm{CAT}(\kappa)$ space, with $\kappa>0$, is
supported within a small enough ball, then it does have a unique barycenter
[38, Theorem B]. This is related to the following convexity property of the
squared distance to any fixed point [33, Proposition 3.1].

######  Lemma 5.4.

Let $(M,d)$ be a $\textrm{CAT}(\kappa)$ space, with $\kappa>0$ and let
$x_{0}\in M$. Then, for all $\varepsilon\in(0,\frac{\pi}{2\sqrt{\kappa}}]$,
$\frac{1}{2}d(x_{0},\cdot)^{2}$ is $k_{\varepsilon}$-geodesically strongly
convex on the ball
$B\left(x_{0},\frac{\pi}{2\sqrt{\kappa}}-\varepsilon\right)$, with
$k_{\varepsilon}=(\pi-2\sqrt{\kappa}\varepsilon)\tan(\varepsilon\sqrt{\kappa})$.

This strong convexity property implies a variance inequality in
$\textrm{CAT}(\kappa)$ spaces of small diameter for $\kappa>0$ .

######  Lemma 5.5.

Let $(M,d)$ be a $\textrm{CAT}(\kappa)$ space with $\kappa>0$, let $x_{0}\in
M$ and let $\varepsilon\in(0,\frac{\pi}{2\sqrt{\kappa}}]$. Let $X$ be a random
variable in $M$ with values in the ball
$B\left(x_{0},\frac{\pi}{2\sqrt{\kappa}}-\varepsilon\right)$ almost surely.
Then it satisfies the following variance inequality

$d^{2}(z,b^{*})\leq\frac{2}{k_{\varepsilon}}\mathbb{E}\left[d^{2}(z,X)-d^{2}(b^{*},X)\right],\quad\forall
z\in M,$ (7)

where
$k_{\varepsilon}=(\pi-2\sqrt{\kappa}\varepsilon)\tan(\varepsilon\sqrt{\kappa})$,
and $b^{*}$ denotes the Fréchet mean of the law of $X$.

Note that $k_{\varepsilon}\in(0,2)$, for all
$\varepsilon\in(0,\frac{\pi}{2\sqrt{\kappa}})$. Moreover
$k_{\varepsilon}\xrightarrow[\varepsilon\to 0]{}0$, and
$k_{\varepsilon}\xrightarrow[\varepsilon\to\frac{\pi}{2\sqrt{\kappa}}]{}2$. So
when the diameter tends to zero, the convexity tends to be the same as in the
Euclidean case, whereas when the diameter tends to be maximal (i.e.
$\frac{\pi}{2\sqrt{\kappa}}$), the geodesic strong convexity may no longer
hold.

###### Proof.

By [33, Proposition 3.1], we know that for all $p\in M$, the functions
$z\mapsto d^{2}(z,p)$ are $k_{\varepsilon}$-convex on the ball
$B\left(x_{0},\frac{\pi}{2\sqrt{\kappa}}-\varepsilon\right)$. Moreover,
$b^{*}$ is in the ball by [38, Theorem B]. It follows that the function
$z\mapsto\mathbb{E}\left[d^{2}(z,X)-d^{2}(b^{*},X)\right]$ is also
$k_{\varepsilon}$-convex on the ball. Therefore, by taking $z_{t}$ the joining
geodesic between $b^{*}$ and $z$ (it exists and is unique because the ball is
small enough), and for $p=b^{*}$, by definition of the barycenter, we get that
for $t\in[0,1]$,

$\displaystyle 0$
$\displaystyle\leq\mathbb{E}\left[d^{2}(z_{t},X)-d^{2}(b^{*},X)\right]$
$\displaystyle\leq
t\,\mathbb{E}\left[d^{2}(z,X)-d^{2}(b^{*},X)\right]-\frac{k_{\varepsilon}}{2}t(1-t)d^{2}(z,b^{*})$

Therefore,

$t\,\mathbb{E}\left[d^{2}(z,X)-d^{2}(b^{*},X)\right]\geq\frac{k_{\varepsilon}}{2}t(1-t)d^{2}(z,b^{*}),$

yielding the result by dividing by $t$ and letting $t$ goes to zero. ∎

In order to derive a non asymptotic bounds on the convergence of the empirical
barycenter in $\textrm{CAT}(\kappa)$ spaces for $\kappa>0$, we have to require
the following.

######  Assumption 5.6.

The metric space $(M,d)$ is $\textrm{CAT}(\kappa)$ for some $\kappa>0$ and
there are positive constants $A,p>0$ such that for all $x\in M$ and for all
$\alpha,r>0$ with $\alpha\leq r$,

$N(B(x,r),\alpha)\leq\left(\frac{Ar}{\alpha}\right)^{p},$ (8)

where $N(B(x,r),\alpha)$ denotes the smallest integer $N\geq 1$ such that the
ball $B(x,r)$ can be covered by $N$ balls of radius $\alpha$.

######  Remark 5.7.

The logarithm of the quantity $N(B(x,r),\alpha)$ is known as the metric
entropy of $B(x,r)$ and is used in the theory of empirical processes (see e.g.
[23]). If, for instance, $M$ is a Riemannian manifold of dimension $p$ with
bounded curvature, then it satisfies (8) with the same $p$ as exponent. This
can be easily seen by a volumetric argument using estimates of the volumes of
balls in Riemannian manifolds, see, e.g., [16, Section III]. Therefore, (8)
characterizes, in some way, the finiteness of the dimension of $M$.

We can now state the following concentration inequality in the framework of
$\textrm{CAT}(\kappa)$ spaces ($\kappa>0$).

######  Theorem 5.8.

Let $(M,d)$ be a $\textrm{CAT}(\kappa)$ space, $\kappa>0$, satisfying
Assumption 5.6. Let $x_{0}\in M$ and
$\varepsilon\in(0,\frac{\pi}{2\sqrt{\kappa}}]$. Let $X_{1},...,X_{n}$ be i.i.d
random variables such that $X_{1}\in
B\left(x_{0},\frac{\pi}{2\sqrt{\kappa}}-\varepsilon\right)$ almost surely.
Denote by $b^{*}$ the population barycenter of $X_{1}$ and let $\hat{b}_{n}$
be the empirical barycenter of $X_{1},\ldots,X_{n}$. Then, for all
$\delta\in(0,1)$, it holds with probability at least $1-\delta$ that

$d(\hat{b}_{n},b^{*})\leq
c\left(\frac{A}{\varepsilon\kappa}\sqrt{\frac{p}{n}}+\frac{1}{\varepsilon^{3/2}\kappa}\sqrt{\frac{\log(2/\delta)}{n}}\right),$

where $c>0$ is a universal constant and $A$ is the constant from Assumption
5.6.

###### Proof.

The proof is based on an application of [3, Theorem 2.1]. It is possible to
use this theorem thanks to Assumption 5.6 and Lemma 5.5. By a careful analysis
of its proof with the constants $D=p$, $C=A$,
$K_{1}=\sqrt{\frac{\pi}{2\sqrt{\kappa}}-\varepsilon}$,
$K_{2}=2\left(\frac{\pi}{2\sqrt{\kappa}}-\varepsilon\right)$,
$K_{3}=\frac{2}{(\pi-2\sqrt{\kappa}\varepsilon)\tan(\varepsilon\sqrt{\kappa})}$,
and $\alpha=\beta=1$, we obtain that for all $\delta\in(0,1)$, with
probability at least $1-\delta$,

$\sqrt{\frac{k_{\varepsilon}}{2}}d(\hat{b}_{n},b^{*})\leq
3c_{1}\sqrt{\frac{p}{n}}+3c_{2}\sqrt{\frac{\log(2/\delta)}{n}},$

where

$k_{\varepsilon}=(\pi-2\sqrt{\kappa}\varepsilon)\tan(\varepsilon\sqrt{\kappa}),$
$c_{1}=\frac{96\sqrt{2A}\left(\frac{\pi}{2\sqrt{\kappa}}-\varepsilon\right)}{\sqrt{(\pi-2\sqrt{\kappa}\varepsilon)\tan(\varepsilon\sqrt{\kappa})}}=\frac{96\sqrt{A}\sqrt{\frac{\pi}{2\sqrt{\kappa}}-\varepsilon}}{\sqrt{2\kappa\tan(\varepsilon\sqrt{\kappa})}}$

and

$c_{2}=\frac{4\left(\frac{\pi}{2\sqrt{\kappa}}-\varepsilon\right)}{\sqrt{(\pi-2\sqrt{\kappa}\varepsilon)\tan(\varepsilon\sqrt{\kappa})}}+\frac{16}{3}\sqrt{\left(\frac{\pi}{2\sqrt{\kappa}}-\varepsilon\right)}=\sqrt{\frac{\pi-2\varepsilon\sqrt{\kappa}}{\kappa}}\left(\frac{2}{\sqrt{\tan(\varepsilon\sqrt{\kappa}})}+\frac{16}{3\sqrt{2}}\right).$

Hence, with probability at least $1-\delta$, one has

$d(\hat{b}_{n},b^{*})\leq\frac{288\sqrt{A}}{\sqrt{\kappa}\tan(\varepsilon\sqrt{\kappa})}\sqrt{\frac{p}{n}}+\frac{1}{\sqrt{\kappa\tan(\varepsilon\sqrt{\kappa})}}\left(\frac{6\sqrt{2}}{\sqrt{\tan(\varepsilon\sqrt{\kappa})}}+16\right)\sqrt{\frac{\log(2/\delta)}{n}},$

which proves the result by noting that $\tan x\geq x$ for all $x\in[0,\pi/2)$.
∎

Acknowledgments: The second author would like to thanks Miklós Pálfia and
Takomi Yokota for useful discussion.

## References

  * [1] Bijan Afsari.  Riemannian $l^{p}$-center of mass: existence, uniqueness, and convexity.  Proceedings of the American Mathematical Society, 139(2):655–673, 2011.
  * [2] Martial Agueh and Guillaume Carlier.  Barycenters in the wasserstein space.  SIAM Journal on Mathematical Analysis, 43(2):904–924, 2011.
  * [3] A. Ahidar-Coutrix, T. Le Gouic, and Q. Paris.  Convergence rates for empirical barycenters in metric spaces: curvature, convexity and extendable geodesics.  Probab. Theory Related Fields, 177(1-2):323–368, 2020.
  * [4] Stephanie Alexander, Vitali Kapovitch, and Anton Petrunin.  An invitation to Alexandrov geometry.  SpringerBriefs in Mathematics. Springer, Cham, 2019.  CAT(0) spaces.
  * [5] Jason M Altschuler and Enric Boix-Adsera.  Wasserstein barycenters can be computed in polynomial time in fixed dimension.  J. Mach. Learn. Res., 22:44–1, 2021.
  * [6] Jason M Altschuler and Enric Boix-Adsera.  Wasserstein barycenters are np-hard to compute.  SIAM Journal on Mathematics of Data Science, 4(1):179–203, 2022\.
  * [7] Miroslav Bacák.  Convex analysis and optimization in hadamard spaces.  In Convex Analysis and Optimization in Hadamard Spaces. de Gruyter, 2014.
  * [8] Rajendra Bhatia.  Positive definite matrices.  In Positive Definite Matrices. Princeton university press, 2009\.
  * [9] Rajendra Bhatia and John Holbrook.  Riemannian geometry and matrix geometric means.  Linear algebra and its applications, 413(2-3):594–618, 2006.
  * [10] Rajendra Bhatia, Tanvi Jain, and Yongdo Lim.  On the bures–wasserstein distance between positive definite matrices.  Expositiones Mathematicae, 37(2):165–191, 2019.
  * [11] Rabi Bhattacharya and Lizhen Lin.  Omnibus clts for Fréchet means and nonparametric inference on non-euclidean spaces.  Proceedings of the American Mathematical Society, 145(1):413–428, 2017.
  * [12] Rabi Bhattacharya and Vic Patrangenaru.  Large sample theory of intrinsic and extrinsic sample means on manifolds.  Annals of statistics, 31(1):1–29, 2003.
  * [13] Rabi Bhattacharya and Vic Patrangenaru.  Large sample theory of intrinsic and extrinsic sample means on manifolds: II.  Annals of statistics, pages 1225–1259, 2005.
  * [14] Martin R Bridson and André Haefliger.  Metric spaces of non-positive curvature, volume 319.  Springer Science & Business Media, 2013.
  * [15] Dmitri Burago, Yuri Burago, and Sergei Ivanov.  A course in metric geometry, volume 33.  American Mathematical Society, 2022.
  * [16] Isaac Chavel.  Riemannian geometry: a modern introduction, volume 98.  Cambridge university press, 2006.
  * [17] Sebastian Claici, Edward Chien, and Justin Solomon.  Stochastic wasserstein barycenters.  In International Conference on Machine Learning, pages 999–1008. PMLR, 2018.
  * [18] Marco Cuturi and Arnaud Doucet.  Fast computation of wasserstein barycenters.  In International conference on machine learning, pages 685–693. PMLR, 2014.
  * [19] Benjamin Eltzner, Fernando Galaz-Garcia, Septhan F Huckemann, and Wilderich Tuschmann.  Stability of the cut locus and a central limit theorem for Fréchet means of Riemannian manifolds.  arXiv preprint arXiv:1909.00410, 2019.
  * [20] Benjamin Eltzner and Stephan F Huckemann.  A smeary central limit theorem for manifolds with application to high-dimensional spheres.  The Annals of Statistics, 47(6):3360–3381, 2019.
  * [21] Maurice Fréchet.  Les éléments aléatoires de nature quelconque dans un espace distancié.  Ann. Inst. H. Poincaré, 10:215–310, 1948.
  * [22] Kei Funano.  Rate of convergence of stochastic processes with values in $\mathbb{R}$-trees and Hadamard manifolds.  Osaka J. Math., 47(4):911–920, 2010.
  * [23] Evarist Giné.  Empirical processes and applications: an overview.  Bernoulli, 2(1):1–38, 1996.  With a discussion by Jon A. Wellner and a rejoinder by the author.
  * [24] Thomas Hotz, Sean Skwerer, Stephan Huckemann, Huiling Le, J Stephen Marron, Jonathan C Mattingly, Ezra Miller, James Nolen, Megan Owen, and Vic Patrangenaru.  Sticky central limit theorems on open books.  Annals of Applied Probability, 2013.
  * [25] Hermann Karcher.  Riemannian center of mass and mollifier smoothing.  Communications on pure and applied mathematics, 30(5):509–541, 1977\.
  * [26] David George Kendall, Dennis Barden, Thomas K Carne, and Huiling Le.  Shape and shape theory, volume 500.  John Wiley & Sons, 2009.
  * [27] Alexey Kroshnin, Nazarii Tupitsa, Darina Dvinskikh, Pavel Dvurechensky, Alexander Gasnikov, and Cesar Uribe.  On the complexity of approximating wasserstein barycenters.  In International conference on machine learning, pages 3530–3540. PMLR, 2019.
  * [28] T. Le Gouic, Q. Paris, P. Rigollet, and A.J. Stromme.  Fast convergence of empirical barycenters in Alexandrov spaces and the Wasserstein space.  J. Eur. Math. Soc., 2022.
  * [29] Thibaut Le Gouic and Jean-Michel Loubes.  Existence and consistency of wasserstein barycenters.  Probability Theory and Related Fields, 168(3):901–917, 2017.
  * [30] Michel Ledoux.  The concentration of measure phenomenon, volume 89 of Mathematical Surveys and Monographs.  American Mathematical Society, Providence, RI, 2001.
  * [31] Yongdo Lim and Miklós Pálfia.  Weighted deterministic walks for the least squares mean on hadamard spaces.  Bulletin of the London Mathematical Society, 46, 05 2014.
  * [32] Estelle Massart, Julien M Hendrickx, and P-A Absil.  Curvature of the manifold of fixed-rank positive-semidefinite matrices endowed with the bures–wasserstein metric.  In Geometric Science of Information: 4th International Conference, GSI 2019, Toulouse, France, August 27–29, 2019, Proceedings, pages 739–748. Springer, 2019.
  * [33] Shin-ichi Ohta.  Convexities of metric spaces.  Geom. Dedicata, 125:225–250, 2007.
  * [34] Shin-ichi Ohta and Miklós Pálfia.  Discrete-time gradient flows and law of large numbers in Alexandrov spaces.  Calc. Var. Partial Differential Equations, 54(2):1591–1610, 2015\.
  * [35] Barry Simon.  Loewner’s Theorem on Monotone Matrix Functions.  Springer, 2019.
  * [36] Karl-Theodor Sturm.  Probability measures on metric spaces of nonpositive curvature.  In Heat kernels and analysis on manifolds, graphs, and metric spaces (Paris, 2002), volume 338 of Contemp. Math., pages 357–390. Amer. Math. Soc., Providence, RI, 2003.
  * [37] Roman Vershynin.  High-dimensional probability: An introduction with applications in data science, volume 47.  Cambridge university press, 2018.
  * [38] Takumi Yokota.  Convex functions and barycenter on CAT(1)-spaces of small radii.  J. Math. Soc. Japan, 68(3):1297–1323, 2016.
  * [39] Takumi Yokota.  Convex functions and $p$-barycenter on ${\rm CAT}(1)$-spaces of small radii.  Tsukuba J. Math., 41(1):43–80, 2017.
  * [40] Hongyi Zhang and Suvrit Sra.  First-order methods for geodesically convex optimization.  In Conference on Learning Theory, pages 1617–1638. PMLR, 2016.
  * [41] Hongyi Zhang and Suvrit Sra.  Towards riemannian accelerated gradient methods.  arXiv preprint arXiv:1806.02812, 2018.
  * [42] Herbert Ziezold.  On expected figures and a strong law of large numbers for random elements in quasi-metric spaces.  In Transactions of the Seventh Prague Conference on Information Theory, Statistical Decision Functions, Random Processes and of the 1974 European Meeting of Statisticians, pages 591–602. Springer, 1977.