  Barycenters (aka Fr\'echet 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.
