  In Euclidean spaces, the empirical mean vector as an estimator of the
population mean is known to have polynomial concentration unless a strong tail
assumption is imposed on the underlying probability measure. The idea of
median-of-means tournament has been considered as a way of overcoming the
sub-optimality of the empirical mean vector. In this paper, to address the
sub-optimal performance of the empirical mean in a more general setting, we
consider general Polish spaces with a general metric, which are allowed to be
non-compact and of infinite-dimension. We discuss the estimation of the
associated population Frechet mean, and for this we extend the existing notion
of median-of-means to this general setting. We devise several new notions and
inequalities associated with the geometry of the underlying metric, and using
them we study the concentration properties of the extended notions of
median-of-means as the estimators of the population Frechet mean. We show that
the new estimators achieve exponential concentration under only a second moment
condition on the underlying distribution, while the empirical Frechet mean has
polynomial concentration. We focus our study on spaces with non-positive
Alexandrov curvature since they afford slower rates of convergence than spaces
with positive curvature. We note that this is the first work that derives
non-asymptotic concentration inequalities for extended notions of the
median-of-means in non-vector spaces with a general metric.
