Generalizing the "median trick" to higher dimensions? For randomized algorithms $\mathcal{A}$ taking real values, the "median trick" is a simple way to reduce the probability of failure to any threshold $\delta &gt; 0$, at the cost of only a multiplicative $t=O(\log\frac{1}{\delta})$ overhead. 
Namely, if the $\mathcal{A}$'s output falls into a "good range" $I=[a,b]$ with probability (at least) $2/3$, then running independent copies $\mathcal{A}_1,\dots,\mathcal{A}_t$ and taking the median of their outputs $a_1,\dots,a_t$ will result in a value falling in $I$ with probability at least $1-\delta$ by Chernoff/Hoeffding bounds.

Is there any generalization of this "trick" to higher dimensions, say $\mathbb{R}^d$, where the good range is now a convex set (or a ball, or any sufficiently nice and structured set)? That is, given a randomized algorithm $\mathcal{A}$ outputting values in $\mathbb{R}^d$, and a "good set" $S\subseteq \mathbb{R}^d$ such that $\mathbb{P}_r\{ \mathcal{A}(x,r) \in S \} \geq 2/3$ for all $x$, how can one boost the probability of success to $1-\delta$ with only a logarithmic cost in $1/\delta$?

(Phrased differently: given fixed, arbirary $a_1,\dots, a_t\in \mathbb{R}^d$ with the guarantee that at least $\frac{2t}{3}$ of the $a_i$'s belong to $S$, is there a procedure outputting a value from $S$? If so, is there an efficient one?)

And what is the minimum set of assumptions one needs on $S$ for the above to be achievable?

Sorry if this turns out to be trivial -- I couldn't find a reference on this question...
What you're looking for is almost the same a robust central tendency: a way of reducing a cloud of data points to a single point, such that if many of the data points are close to some "ground truth" but the rest of them are arbitrarily far away, then your output will also be close to the ground truth. The "breakdown point" of such a method is the fraction of arbitrarily-bad outliers it can tolerate. The difference is that in your case you want to replace "close to" by "within the convex hull of".

One way to capture this is with the notion of Tukey depth. A point has Tukey depth $p$ (with respect to a given set of $n$ data points) if every halfspace containing the given point also contains at least $pn$ data points. If there is a good convex subspace that you want to be inside, then a point with Tukey depth $p$ will be inside it as long as there are at least $(1-p)n$ of the data points inside it. So the breakdown point of this method is the largest value of $p$ that you can attain.

Unfortunately this breakdown point is $1/(d+1)$, not close to 1/2, both for Tukey depth and for your problem. Here's why: if your data are clustered near the $d+1$ vertices of a simplex, then as long as fewer than $1/(d+1)$ fraction of them are outliers (but you don't know which ones) then any point in the simplex is safe to pick as it will always be within the convex hull of the non-outliers. But if more than $1/(d+1)$ of the points can be outliers, there is nowhere that is safe to pick: whichever point in the simplex you choose, the outliers could be all of the points from the nearest simplex vertex, and you'd be outside the hull of the non-outliers.

If you're willing to tolerate a worse breakdown point, more like $O(1/d^2)$, there's a randomized method for finding a deep point that's polynomial in both $n$ and $d$: see my paper

Approximating center points with iterated Radon points,
K. Clarkson, D. Eppstein, G.L. Miller, C. Sturtivant, and S.-H. Teng,
9th ACM Symp. Comp. Geom., San Diego, 1993, pp. 91–98,
Int. J. Comp. Geom. &amp; Appl. 6 (3): 357–377, 1996,
http://kenclarkson.org/center/p.pdf