We investigate the cost of privacy for a class of private statistics which are generated via the exponential mechanism. To do this, we introduce a specific regularity condition, called $(K,\mathcal{F})$-regularity. $(K,\mathcal{F})$-regularity allows us to compute the cost of privacy in terms of the sample complexity for this class of private statistics. We use our results to compute the cost of privately estimating multivariate medians based on data depth functions. We show that under certain conditions, estimating the depth median privately only adds a multiplicative $\log d$ to the sample complexity.