There is growing interest in developing statistical estimators that achieve exponential concentration around a population target even when the data distribution has heavier than exponential tails. More recent activity has focused on extending such ideas beyond Euclidean spaces to Hilbert spaces and Riemannian manifolds. In this work, we show that such exponential concentration in presence of heavy tails can be achieved over a broader class of parameter spaces called CAT($\kappa$) spaces, a very general metric space equipped with the minimal essential geometric structure for our purpose, while being sufficiently broad to encompass most typical examples encountered in statistics and machine learning. The key technique is to develop and exploit a general concentration bound for the Fr\'echet median in CAT($\kappa$) spaces. We illustrate our theory through a number of examples, and provide empirical support through simulation studies.

The problem of prediction with expert advice [ Cesa-Bianchi and Lugosi, 2006 ] is a by now standard model of online learning. Traditionally studied for outcom es taking values in a vector space, less seems to be known when the outcome space is a more general metr ic space. This paper partly addresses the problem by focusing on the case of NPC spaces, i .e., geodesic metric spaces with non-positive curvature in the sense of Alexandrov. The class of NPC spaces includes many metric spaces of partic ular interest in the data sciences. Apart from Hilbert spaces, interesting examples are hyperb olic spaces [ Nickel and Kiela, 2017 ], the space of real symmetric positive-definite matrices with Log -Euclidean [ Arsigny et al., 2007 ] or Log-Cholesky [ Lin, 2019 ] Riemannian metrics and more generally all complete and sim ply connected Riemannian manifolds with non-positive sectional curvatu re.