21
$\begingroup$

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 > 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...

$\endgroup$
  • 3
    $\begingroup$ In the special case that $S$ is a cuboid, does it work if you use the median trick in each dimension individually? So sample a bunch of points, then take the median of their coordinates in dimension 1, 2, ..., d, and then you obtain a point in $\mathbb{R}^d$. Maybe you'll need $O(\log(d/\epsilon))$ samples with this strategy? $\endgroup$ – Robin Kothari Sep 15 '15 at 16:01
  • 1
    $\begingroup$ In the one dimensional case, usually you know $b-a$ but not the exact interval (although even if you don't know $b-a$ the median trick still works). Should we assume we know $S$ but only up to translation? Up to translation and scaling? $\endgroup$ – Sasho Nikolov Sep 15 '15 at 19:31
  • $\begingroup$ @SashoNikolov I reckon this would be the most "general generalization" indeed (e.g., we only know $S$ is a "good ball of diameter $\varepsilon$"). $\endgroup$ – Clement C. Sep 15 '15 at 19:33
  • 1
    $\begingroup$ Well, what Thomas wrote in his answer is even more general: he assumes that $S$ ($G$ in his answer) is an unknown convex set. $\endgroup$ – Sasho Nikolov Sep 15 '15 at 19:37
17
$\begingroup$

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. & Appl. 6 (3): 357–377, 1996, http://kenclarkson.org/center/p.pdf

$\endgroup$
  • $\begingroup$ Yep. In addition I would mention that one can use eps-nets eps-approximations and their various friends as a way to get a small sample that approximates such depth measures well. You do not get a single point, but you get way more information. $\endgroup$ – Sariel Har-Peled Sep 16 '15 at 4:26
  • $\begingroup$ With your paper's terminology, is there a known efficient way to verify a $\hspace{1.41 in}$ claimed $\beta$-center for rational numbers $\beta \hspace{.02 in}$? $\;$ $\endgroup$ – user6973 Sep 16 '15 at 21:24
  • $\begingroup$ If by "efficient" you mean polynomial in the dimension, then I don't know of such a result. My paper only finds one point, it doesn't give you more information about the spatial distribution of depth (such as Sariel alludes to above). $\endgroup$ – David Eppstein Sep 17 '15 at 2:28
  • $\begingroup$ Thank you! Putting aside considerations of efficiency (for now), this looks like saying that for the general case of arbitrary convex sets, there is no way to boost constant probability to arbitrary probability? (since the fraction of good points needs to be greater than $1-\frac{1}{d+1}$? (or did I miss something -- looking back to it, it feels like the second formulation I ave does not capture the idea of "independent repetitions,", where we would have in hand several sets of points, each of which having at least a $2/3$ fraction of good points.) $\endgroup$ – Clement C. Sep 17 '15 at 19:24
  • 1
    $\begingroup$ One point, several points, or not, if all you know is that there exists a convex set but not where it is, and you want to be able to boost the probability of being in the correct set to better then d/(d+1), then the fraction of good points needs to be at least d/(d+1) to get around the simplex example. For otherwise, an adversary could give you data in the form of a simplex and choose randomly an epsilon-neighborhood of one face of the simplex as the convex set; even if you guess a point near a vertex of the simplex at random, you will have at least 1/(d+1) probability of choosing incorrectly. $\endgroup$ – David Eppstein Sep 17 '15 at 20:39
14
$\begingroup$

This is a neat question and I've thought about it before. Here's what we came up with:

You run your algorithm $n$ times to get outputs $x_1, \cdots, x_n \in \mathbb{R}^d$ and you know what with high probability a large fraction of $x_i$s fall into some good set $G$. You don't know what $G$ is, just that it is convex. The good news is that there is a way to get a point in $G$ with no further information about it. Call this point $f(x_1, \cdots, x_n)$.

Theorem. For all natural numbers $n$ and $d$, there exists a function $f : (\mathbb{R}^d)^n \to \mathbb{R}^d$ such that the following holds. Let $x_1 ... x_n \in \mathbb{R}^d$ and let $G \subset \mathbb{R}^d$ be a convex set satisfying $$\frac{1}{n}\left|\left\{ i \in [n] : x_i \in G \right\}\right| > \frac{d}{d+1}.$$ Then $f(x_1, ..., x_n) \in G$. Moreover, $f$ is computable in time polynomial in $n^d$.

Note that, for $d=1$, we can set $f$ to be the median. So this shows how to generalise the median for $d>1$.

Before proving this result, note that it is tight: Let $n=d+1$ and let $x_1, \cdots, x_d$ be the standard basis elements and $x_{d+1}=0$. Any subset of $d$ of the points is contained in an affine space $G$ of dimension $d-1$ (which is uniquely defined by those points). But no point is contained in all of those affine spaces. Hence there is some convex $G$ that contains $n\cdot d/(d+1)=d$ points but doesn't contain $f(x_1, \cdots, x_n)$, whatever value that takes.

Proof. We use the following result.

Helly's Theorem. Let $K_1 ... K_m$ be convex subsets of $\mathbb{R}^d$. Suppose the intersection of any $d+1$ $K_i$s is nonempty. Then the intersection of all $K_i$s is nonempty.

Click here for a proof of Helly's Theorem.

Now to prove our theorem:

Let $k<n/(d+1)$ be an upper bound on the number of points not in $G$. Consider all closed halfspaces $K_1 ... K_m \subset \mathbb{R}^d$ containing at least $n-k$ points with their their boundary containing a set of points of maximal rank (this is a finite number of halfspaces as each $K_i$ is defined by $d+1$ points on its boundary).

The complement of each $K_i$ contains at most $k$ points. By a union bound, the intersection any $d+1$ $K_i$s contains at least $n-k(d+1)$>0 points. By Helly's theorem (since halfspaces are convex), there is a point in the intersection of all the $K_is$. We let $f$ be a function that computes an arbitrary point in the intersection of the $K_i$s.

All that remains is to show that the intersection of the $K_i$s is contained in $G$.

Without loss of generality, $G$ is the convex hull of a subset of the points with full rank. That is, we can replace $G$ with the convex hull of the points it contains. If this does not have full rank, we can simply apply our theorem in lower dimension.

Each face of $G$ defines a halfspace, where $G$ is the intersection of these halfspaces. Each of these halfspaces contains $G$ and hence contains at least $n-k$ points. The boundary of one of these half spaces contains a face of $G$ and hence contains a set of points of maximal rank. Thus each of these halfspaces is a $K_i$. Thus the intersection of all $K_i$s is contained in $G$, as required.

To compute $f$, set up a linear program where the linear constraints correspond to $K_i$s and a feasible solution corresponds to a point in the intersection of all the $K_i$s. Q.E.D.

Unfortunately, this result is not very practical in the high-dimensional setting. A good question is whether we can compute $f$ more efficiently:

Open Problem. Prove the above theorem with the additional conclusion that $f$ can be computed in time polynomial in $n$ and $d$.

Aside: We can also change the problem to get an efficient solution: If $x_1, \cdots, x_n$ have the property that strictly more than half of them lie in a ball $B(y,\varepsilon)$, then we can find a point $z$ that lies in $B(y,3\varepsilon)$ in time polynomial in $n$ and $d$. In particular, we can set $z=x_i$ for an arbitrary $i$ such that strictly more than half of the points are in $B(z,2\varepsilon)$.

$\endgroup$
  • $\begingroup$ I think you basically reinvented Tukey depth as David Eppstein outlines below :) $\endgroup$ – Suresh Venkat Sep 16 '15 at 8:12
7
$\begingroup$

There is a notion of the median of a set of points in high-dimensions and general norms which is known under various names. It is just the point that minimizes the sum of distances to all the points in the set. It is known to have a similar confidence amplification property as the usual median with a small multiplicative increase in the distance. You can find the details in Theorem 3.1 of this paper: http://arxiv.org/pdf/1308.1334.pdf

One nice thing that this paper shows is that the factor by which the distance increases can be made any constant >1 if you can amplify from arbitrarily high (but constant < 1) confidence.

Edit: there is another recent paper on the topic by Hsu and Sabato http://arxiv.org/pdf/1307.1827v6.pdf It mostly analyzes and applies the procedure in which the point in the set with the smallest median distance to the rest of the points is used. This procedure can be used with any metric but only gives an approximation factor of 3.

$\endgroup$
  • $\begingroup$ Thanks, this looks nice! I only skimmed it so far, but (unless I'm mistaken or skipped too fast over it), it deals with the specific case of $S$ being a $p$-ball; is that correct? $\endgroup$ – Clement C. Sep 17 '15 at 19:20
  • 1
    $\begingroup$ Not really. The result is stated for all Banach spaces. For any body that is origin-centered and symmetric around its center there is a corresponding norm in which this body is the unit ball. Since for the purposes of your question we can assume without loss of generality that the convex body is origin-centered we get the result holds for every centrally symmetric convex body. Perhaps with some mild effort the result can be extended to general convex bodies. $\endgroup$ – Vitaly Sep 18 '15 at 6:16
  • 1
    $\begingroup$ You need to know the norm in order to compute the minimizer for that norm, though — if you know only that there is a norm but not what it is, you're out of luck. $\endgroup$ – David Eppstein Sep 18 '15 at 16:08
  • 1
    $\begingroup$ You are right, David. You need to know the norm. (This translates to knowing the convex body up to the center and scaling). $\endgroup$ – Vitaly Sep 18 '15 at 20:25
  • $\begingroup$ I was thinking of this approach, but then thought of this counterexample for arbitrary convex sets. How does it play in to these results? Let $X$ be distributed in the plane as follows: with probability $0.9$, uniform on $(-1,0)$ and $(+1,0)$, with probability $0.1$, equal to $(0,0.0001)$. The convex "good" set is the line from $(-1,0)$ to $(1,0)$. But if we take many samples, then the generalized median will be one of the sampled points located at $(0,0.0001)$. Generalize this easily to higher dimensions using a hyperplane and a point slightly offset. $\endgroup$ – usul Sep 19 '15 at 12:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.