  For sets $\mathcal Q$ and $\mathcal Y$, the generalized Fr\'echet mean $m \in
\mathcal Q$ of a random variable $Y$, which has values in $\mathcal Y$, is any
minimizer of $q\mapsto \mathbb E[\mathfrak c(q,Y)]$, where $\mathfrak c \colon
\mathcal Q \times \mathcal Y \to \mathbb R$ is a cost function. There are
little restrictions to $\mathcal Q$ and $\mathcal Y$. In particular, $\mathcal
Q$ can be a non-Euclidean metric space. We provide convergence rates for the
empirical generalized Fr\'echet mean. Conditions for rates in probability and
rates in expectation are given. In contrast to previous results on Fr\'echet
means, we do not require a finite diameter of the $\mathcal Q$ or $\mathcal Y$.
Instead, we assume an inequality, which we call quadruple inequality. It
generalizes an otherwise common Lipschitz condition on the cost function. This
quadruple inequality is known to hold in Hadamard spaces. We show that it also
holds in a suitable way for certain powers of a Hadamard-metric.
