Optimal uniform sampling for
stable geometric median coresets

Abstract

Uniform sampling need not approximate the cost of every candidate median, but it can preserve their relative quality throughout the candidate space. We prove that the worst-case sample complexity of constructing stable Euclidean geometric median coresets by unweighted uniform sampling without replacement is $\Theta(\varepsilon^{-2})$ . For every dataset, $O(\varepsilon^{-2})$ sampled points suffice in every dimension, with the whole dataset used if it is smaller. For each $0<\varepsilon<1/4$ , with probability at least $4/5$ , every $(1+\varepsilon)$ sample-cost comparison implies a $(1+17\varepsilon)$ population-cost comparison, simultaneously for all candidate pairs. This removes the $\log(1/\varepsilon)$ factor from the bound of Carmel, Krauthgamer, and Petruschka (APPROX/RANDOM 2026). The matching lower bound holds for the same sampling rule even for distinct points on the line. The proof represents distance as squared Hilbert distance, reducing all comparison errors to linear functionals of one empirical mean error. A finite-population variance bound controls this vector, and the triangle inequality converts the resulting error into a relative guarantee. The argument extends to negative-type metrics and gives the same optimal rate in $\ell_{1}^{d}$ , resolving the dimension-independence conjecture of Carmel and Krauthgamer (ICLR 2026).

Note. This paper was generated entirely by AI, including MiMo, using an automated research pipeline developed by Chenghua Liu and Hanyu Li.

1 Introduction

Uniform sampling offers a simple way to reduce the input to a median problem, but it cannot preserve every candidate cost. Consider a population consisting of $n-1$ points at the origin and one point at distance $R$ . A sample of $m$ points without replacement misses the outlier with probability $1-m/n$ . On that event, the origin has zero sample cost and positive population cost, irrespective of how large $R$ is. Thus a relative approximation to the entire objective asks more of a uniform sample than it can provide.

Preserving only near-optimal centers is sufficient for unconstrained optimization, but need not suffice once the center is required to lie in a subset of the ambient space. The best feasible center may be far from the unconstrained optimum. Stable coresets, introduced by Carmel and Krauthgamer [2], retain the comparisons needed in this situation: whenever one center is approximately as good as another on the sample, the same comparison holds on the population with controlled loss. The guarantee applies to every pair at once. Consequently, a single sample supports all restrictions of the candidate domain, including restrictions chosen after the sample is drawn.

For $1$ -median in $\ell_{1}^{d}$ , Carmel and Krauthgamer [2, Theorem 1.4] obtained stable coresets of size $O(\varepsilon^{-2}\log d)$ by uniform sampling and conjectured that the dimension dependence could be removed. For the Euclidean geometric median, Carmel, Krauthgamer, and Petruschka [1, Theorem 1.1] removed that dependence and proved the bound $O(\varepsilon^{-2}\log(1/\varepsilon))$ . Their construction uses uniform sampling without replacement; embeddings and an iterative size-reduction argument enter only its analysis. We prove that $O(\varepsilon^{-2})$ samples suffice with the same stability parameters and success probability. A matching lower bound for the same sampling rule shows that the remaining logarithm is unnecessary, even though the guarantee ranges over an unbounded space of candidate centers.

Write $F_{A}$ for the average distance to a dataset $A$ and $\mathrm{OPT}=\min_{z}F_{P}(z)$ . The relevant error is a difference of costs, rather than a cost itself. Subtracting two costs cancels terms that are common to the two centers, as formalized by the relative cost-difference framework of [2, Theorem 3.1] and its all-pairs version in [1, Section 3]. Yet centering alone does not yield an absolute error bound on the scale of the optimum: for a population of $2m-1$ zeroes and one distant point, missing the outlier gives comparison error $2\mathrm{OPT}$ at distant candidate centers on an event of probability $1/2$ (Remark 2.5). In particular, a uniform bound of order $\mathrm{OPT}/\sqrt{m}$ is false. The proof must retain the dependence on the candidate locations until the final relative normalization.

A squared-Hilbert representation of Euclidean distance does exactly this. If $\Phi$ is anchored at a population median and $v_{A}$ is the average feature vector of $A$ , expansion of squared distances gives

[F_{P}(x)-F_{P}(y)]-[F_{Q}(x)-F_{Q}(y)]=2\left\langle\Phi(x)-\Phi(y),v_{Q}-v_{P}\right\rangle.

Every pair is controlled by the same empirical mean error. Its squared norm has expectation at most $\mathrm{OPT}/m$ , so the comparison error is of order $\sqrt{\left\lVert x-y\right\rVert_{2}\mathrm{OPT}/m}$ on one event of high probability. Both $\left\lVert x-y\right\rVert_{2}$ and $2\mathrm{OPT}$ are at most $F_{P}(x)+F_{P}(y)$ . This yields relative error $O(m^{-1/2})$ without a union bound over centers. One additional first-moment estimate at the population median then converts relative cost differences into stable comparisons. The sample remains unweighted, and neither the median nor the feature map is computed.

The representation itself is classical [3]. Its connection to coreset construction is discussed in [2, Section 1.4]; related empirical-mean identities appear in energy distance [4, Proposition 14 and Theorem 22] and in integration bounds for support points [5, Theorem 4]. The estimate above uses the metric triangle inequality to make that mean control relative to the two candidate costs. The same argument therefore applies in negative-type metric spaces. In $\ell_{1}^{d}$ , it gives the optimal $\Theta(\varepsilon^{-2})$ rate and settles the conjecture in [2, Section 1.2].

1.1 Model and main result

We treat a dataset $P=(p_{1},\ldots,p_{n})\in(\mathbb{R}^{d})^{n}$ as indexed, with $d,n\geq 1$ . Thus repeated locations are allowed, but the sample indices are distinct. For every nonempty finite indexed dataset $A$ , define

F_{A}(z):=\frac{1}{|A|}\sum_{p\in A}\left\lVert z-p\right\rVert_{2},\qquad z\in\mathbb{R}^{d},

(1)

where sums count multiplicities. A uniform sample of size $m$ , $1\leq m\leq n$ , means

I\sim\operatorname{Unif}\binom{[n]}{m},\qquad Q=(p_{i})_{i\in I},\qquad[n]:=\{1,\ldots,n\}.

All sampled points have equal weight. Normalizing costs by dataset size does not change any comparison within a dataset.

Definition 1.1 (Stable coreset).

For $\varepsilon,\eta\geq 0$ , a nonempty indexed subdataset $Q$ of $P$ is a stable $(\varepsilon,\eta)$ -coreset if, simultaneously for all $x,y\in\mathbb{R}^{d}$ ,

F_{Q}(x)\leq(1+\varepsilon)F_{Q}(y)\quad\Longrightarrow\quad F_{P}(x)\leq(1+\eta)F_{P}(y).

(2)

For $0<\varepsilon<1/4$ , let $m_{2}(\varepsilon)$ be the least positive integer $M$ such that, for every dimension $d$ , every indexed dataset $P$ of size $n$ , and every integer $M\leq m\leq n$ , a uniform sample of size $m$ is a stable $(\varepsilon,17\varepsilon)$ -coreset with probability at least $4/5$ . This is a threshold guarantee for all larger sample sizes, not a claim that stability is monotone under adding points to a particular sample. When $n<M$ , returning $Q=P$ satisfies the desired implication deterministically.

Theorem 1.2 (Optimal uniform sample complexity).

(i)
Let $0<\varepsilon<1/4$ and $\lceil 20\varepsilon^{-2}\rceil\leq m\leq n$ . For every $d\geq 1$ and every indexed dataset $P\in(\mathbb{R}^{d})^{n}$ , a uniform sample $Q$ of size $m$ is a stable $(\varepsilon,17\varepsilon)$ -coreset with probability at least $4/5$ .
(ii)
Let $0<\varepsilon\leq 1/100$ . For every integer $1\leq m\leq\varepsilon^{-2}/24200$ , there exist $n\geq m$ and a set $P\subset\mathbb{R}$ of $n$ distinct points such that a uniform sample of size $m$ fails to be a stable $(\varepsilon,17\varepsilon)$ -coreset with probability at least $2/5$ .

Consequently,

m_{2}(\varepsilon)=\Theta(\varepsilon^{-2})\qquad(\varepsilon\to 0).

The lower bound concerns the sample returned by uniform sampling, without reweighting or postprocessing; arbitrary weighted coresets are outside its scope. Its obstruction is already one-dimensional: two nearly balanced clusters have a population preference of order $\varepsilon$ , while a sample smaller than order $\varepsilon^{-2}$ has a constant probability of reversing that preference. The proof in Section 3 makes the clusters consist of distinct points and controls the without-replacement distribution directly.

Section 2 proves the upper bound. In Section 4, the negative-type extension separates the case of an attained population median from the case of an approximate reference point. The latter permits arbitrarily small constant-factor sample overhead when the infimum is not attained. An alternative Euclidean proof in Appendix A averages one-dimensional empirical-distribution errors over Gaussian projections.

2 Uniform comparison and the stable-coreset bound

Fix a geometric median $\mu$ of $P$ , and put

\mathrm{OPT}:=F_{P}(\mu)=\min_{z\in\mathbb{R}^{d}}F_{P}(z).

A median exists: $F_{P}$ is continuous, and $F_{P}(z)\geq\left\lVert z\right\rVert_{2}-n^{-1}\sum_{i}\left\lVert p_{i}\right\rVert_{2}$ tends to infinity as $\left\lVert z\right\rVert_{2}\to\infty$ . We use $\mu$ only to set the variance scale. The feature map below is defined on the entire candidate domain, which is needed to compare arbitrary centers after the sample has been drawn.

Lemma 2.1 (Squared-Hilbert representation).

Let $\gamma_{d}$ be standard Gaussian measure on $\mathbb{R}^{d}$ , let $\lambda$ be Lebesgue measure on $\mathbb{R}$ , and let $H=L_{2}(\mathbb{R}^{d}\times\mathbb{R},\gamma_{d}\otimes\lambda)$ be the real Hilbert space. For $x\in\mathbb{R}^{d}$ , define

\Phi(x)(g,t):=\left(\frac{\pi}{2}\right)^{1/4}\bigl(\mathbf{1}_{\{t\leq\left\langle g,x\right\rangle\}}-\mathbf{1}_{\{t\leq\left\langle g,\mu\right\rangle\}}\bigr).

Then $\Phi(x)\in H$ , $\Phi(\mu)=0$ , and

\left\lVert\Phi(x)-\Phi(y)\right\rVert_{H}^{2}=\left\lVert x-y\right\rVert_{2}\qquad(x,y\in\mathbb{R}^{d}).

(3)

In particular, $\left\lVert\Phi(p)\right\rVert_{H}^{2}=\left\lVert p-\mu\right\rVert_{2}$ .

Proof.

For $a,b\in\mathbb{R}$ ,

\int_{\mathbb{R}}\left|\mathbf{1}_{\{t\leq a\}}-\mathbf{1}_{\{t\leq b\}}\right|^{2}\,dt=|a-b|.

For $g\sim\gamma_{d}$ and $z\in\mathbb{R}^{d}$ , $\left\langle g,z\right\rangle$ is a centered Gaussian of variance $\left\lVert z\right\rVert_{2}^{2}$ , so $\mathbb{E}_{g}|\left\langle g,z\right\rangle|=\sqrt{2/\pi}\left\lVert z\right\rVert_{2}$ . Tonelli’s theorem therefore gives

\left\lVert\Phi(x)-\Phi(y)\right\rVert_{H}^{2}=\sqrt{\frac{\pi}{2}}\,\mathbb{E}_{g}|\left\langle g,x-y\right\rangle|=\left\lVert x-y\right\rVert_{2}.

Taking $y=\mu$ proves square integrability and the anchored norm identity. ∎

The subtraction of the indicator at $\mu$ has two roles: it makes the features square-integrable, and it identifies their average squared norm with $\mathrm{OPT}$ . No bound on an individual feature norm is required.

For any nonempty finite indexed dataset $A$ , define

v_{A}:=\frac{1}{|A|}\sum_{p\in A}\Phi(p),\qquad b_{A}:=\frac{1}{|A|}\sum_{p\in A}\left\lVert\Phi(p)\right\rVert_{H}^{2}=F_{A}(\mu).

We write the pairwise comparison error as

\Delta_{P,Q}(x,y):=[F_{P}(x)-F_{P}(y)]-[F_{Q}(x)-F_{Q}(y)].

(4)

Lemma 2.2 (Cost-difference identity).

For every $z\in\mathbb{R}^{d}$ ,

F_{A}(z)=\left\lVert\Phi(z)\right\rVert_{H}^{2}-2\left\langle\Phi(z),v_{A}\right\rangle+b_{A}.

(5)

Consequently, for every $x,y\in\mathbb{R}^{d}$ ,

\Delta_{P,Q}(x,y)=2\left\langle\Phi(x)-\Phi(y),v_{Q}-v_{P}\right\rangle.

(6)

Proof.

By (3),

F_{A}(z)=\frac{1}{|A|}\sum_{p\in A}\left\lVert\Phi(z)-\Phi(p)\right\rVert_{H}^{2}.

Expanding each square gives (5). Subtract the formulas for $x$ and $y$ , and then subtract the resulting identities for $P$ and $Q$ . The squared-norm terms and the constants $b_{A}$ cancel, yielding (6). ∎

The identity isolates the only random quantity needed for every comparison: $v_{Q}-v_{P}$ . Although the features need not be bounded by a common diameter, their population second moment is $\mathrm{OPT}$ . The exact variance formula below also accounts for the dependence between sampled indices.

Lemma 2.3 (Finite-population variance).

Let $h_{1},\ldots,h_{n}$ belong to a real Hilbert space $H$ , and let $I$ be a uniformly random $m$ -element subset of $[n]$ , where $1\leq m\leq n$ . Set

\bar{h}:=\frac{1}{n}\sum_{i=1}^{n}h_{i},\qquad\bar{h}_{I}:=\frac{1}{m}\sum_{i\in I}h_{i}.

If $n>1$ , then

\mathbb{E}\left\lVert\bar{h}_{I}-\bar{h}\right\rVert_{H}^{2}=\frac{n-m}{m(n-1)}\,\frac{1}{n}\sum_{i=1}^{n}\left\lVert h_{i}-\bar{h}\right\rVert_{H}^{2}.

(7)

For $h_{i}=\Phi(p_{i})$ , this implies

\mathbb{E}\left\lVert v_{Q}-v_{P}\right\rVert_{H}^{2}\leq\frac{\mathrm{OPT}}{m}.

(8)

The inequality also holds for $n=1$ .

Proof.

Suppose $n>1$ . Put $w_{i}=h_{i}-\bar{h}$ and $J_{i}=\mathbf{1}_{\{i\in I\}}$ . Since $\sum_{i}w_{i}=0$ ,

\sum_{i\neq j}\left\langle w_{i},w_{j}\right\rangle=-\sum_{i}\left\lVert w_{i}\right\rVert_{H}^{2}.

Using $\mathbb{E}J_{i}=m/n$ and $\mathbb{E}J_{i}J_{j}=m(m-1)/(n(n-1))$ for $i\neq j$ , we obtain

	$\displaystyle\mathbb{E}\left\lVert\bar{h}_{I}-\bar{h}\right\rVert_{H}^{2}$	$\displaystyle=\frac{1}{m^{2}}\left[\frac{m}{n}\sum_{i}\left\lVert w_{i}\right\rVert_{H}^{2}+\frac{m(m-1)}{n(n-1)}\sum_{i\neq j}\left\langle w_{i},w_{j}\right\rangle\right]$
		$\displaystyle=\frac{n-m}{mn(n-1)}\sum_{i}\left\lVert w_{i}\right\rVert_{H}^{2}.$

This proves (7). For the feature vectors,

\frac{1}{n}\sum_{i}\left\lVert\Phi(p_{i})-v_{P}\right\rVert_{H}^{2}=\frac{1}{n}\sum_{i}\left\lVert\Phi(p_{i})\right\rVert_{H}^{2}-\left\lVert v_{P}\right\rVert_{H}^{2}\leq\mathrm{OPT}.

Together with $(n-m)/(n-1)\leq 1$ , this gives (8). If $n=1$ , then $Q=P$ and the mean error is zero. ∎

The remaining geometric factor in (6) is $\left\lVert\Phi(x)-\Phi(y)\right\rVert_{H}=\sqrt{\left\lVert x-y\right\rVert_{2}}$ . It can grow with the centers, but the sum of their population costs grows enough to absorb it. This is the point at which the metric structure enters the proof.

Proposition 2.4 (Simultaneous relative comparison).

For $1\leq m\leq n$ , with probability at least $9/10$ , a uniform sample $Q$ satisfies

|\Delta_{P,Q}(x,y)|\leq\sqrt{\frac{20}{m}}\,[F_{P}(x)+F_{P}(y)]\qquad\text{for all }x,y\in\mathbb{R}^{d}.

(9)

Proof.

If $\mathrm{OPT}=0$ , all data points coincide with $\mu$ , so $F_{Q}=F_{P}$ . Assume $\mathrm{OPT}>0$ . By (8) and Markov’s inequality, the event

\left\lVert v_{Q}-v_{P}\right\rVert_{H}^{2}\leq\frac{10\mathrm{OPT}}{m}

(10)

has probability at least $9/10$ . For all $x,y\in\mathbb{R}^{d}$ , the triangle inequality averaged over the population and the optimality of $\mu$ give

\left\lVert x-y\right\rVert_{2}\leq F_{P}(x)+F_{P}(y),\qquad 2\mathrm{OPT}\leq F_{P}(x)+F_{P}(y).

(11)

Fix a sample satisfying (10). By (3), (6), and Cauchy–Schwarz,

	$\displaystyle\|\Delta_{P,Q}(x,y)\|$	$\displaystyle\leq 2\sqrt{\left\lVert x-y\right\rVert_{2}}\,\left\lVert v_{Q}-v_{P}\right\rVert_{H}$
		$\displaystyle\leq 2\sqrt{\frac{10\left\lVert x-y\right\rVert_{2}\mathrm{OPT}}{m}}$
		$\displaystyle\leq\sqrt{\frac{20}{m}}\,[F_{P}(x)+F_{P}(y)].$

Since the event (10) does not depend on $x, y$ , the conclusion holds simultaneously for every pair. ∎

Remark 2.5 (Why the error must depend on the center).

A uniform absolute bound of order $\mathrm{OPT}/\sqrt{m}$ for $\sup_{z}|\Delta_{P,Q}(z,\mu)|$ cannot hold with success probability greater than $1/2$ for all populations. To see this, let $m\geq 2$ , choose $R>0$ , and take an indexed population of $2m-1$ zeroes and one point at $R$ . Then $\mu=0$ , $\mathrm{OPT}=R/(2m)$ , and a uniform sample of size $m$ misses $R$ with probability exactly $1/2$ . On that event, every $z\geq R$ satisfies

|\Delta_{P,Q}(z,0)|=\frac{R}{m}=2\mathrm{OPT}.

For any fixed constant $C$ , this exceeds $C\mathrm{OPT}/\sqrt{m}$ when $m>C^{2}/4$ . The valid estimate in the preceding proof instead has scale $\sqrt{\left\lVert z-\mu\right\rVert_{2}\mathrm{OPT}/m}$ . Inequalities (11) convert this location-dependent scale into the relative comparison bound without imposing a diameter restriction.

Relative control of cost differences does not yet bound the term $\varepsilon F_{Q}(y)$ in an approximate sample comparison. To do so, it is enough to bound the sample cost at a single reference point. The next lemma recovers one-sided cost domination from that bound and the comparison estimate, then applies the relative cost-difference framework of [2, Theorem 3.1]. This requires no two-sided approximation to individual costs.

Lemma 2.6 (Stability from relative comparison).

Let $0<\varepsilon<1/4$ . Suppose that

|\Delta_{P,Q}(x,y)|\leq\varepsilon[F_{P}(x)+F_{P}(y)]\qquad\text{for all }x,y\in\mathbb{R}^{d},

(12)

and that

F_{Q}(\mu)\leq 10\mathrm{OPT}.

(13)

Then $Q$ is a stable $(\varepsilon,17\varepsilon)$ -coreset of $P$ .

Proof.

We first compare each sample cost with its population counterpart. Applying (12) to $z,\mu$ gives

$\displaystyle F_{Q}(z)$	$\displaystyle\leq F_{P}(z)-\mathrm{OPT}+F_{Q}(\mu)+\varepsilon[F_{P}(z)+\mathrm{OPT}]$
	$\displaystyle\leq(1+\varepsilon)F_{P}(z)+(9+\varepsilon)\mathrm{OPT}$
	$\displaystyle\leq(10+2\varepsilon)F_{P}(z),$	(14)

where the last step uses $\mathrm{OPT}\leq F_{P}(z)$ . This one-sided estimate controls the slack in an approximate comparison. If $F_{Q}(x)\leq(1+\varepsilon)F_{Q}(y)$ , then

	$\displaystyle F_{P}(x)-F_{P}(y)$	$\displaystyle\leq F_{Q}(x)-F_{Q}(y)+\varepsilon[F_{P}(x)+F_{P}(y)]$
		$\displaystyle\leq\varepsilon F_{Q}(y)+\varepsilon[F_{P}(x)+F_{P}(y)]$
		$\displaystyle\leq\varepsilon(10+2\varepsilon)F_{P}(y)+\varepsilon[F_{P}(x)+F_{P}(y)].$

Hence

(1-\varepsilon)F_{P}(x)\leq(1+11\varepsilon+2\varepsilon^{2})F_{P}(y).

(15)

Since

(1+17\varepsilon)(1-\varepsilon)-(1+11\varepsilon+2\varepsilon^{2})=\varepsilon(5-19\varepsilon)>0,

(15) implies $F_{P}(x)\leq(1+17\varepsilon)F_{P}(y)$ . No division by a cost is needed. ∎

Proof of Theorem 1.2(i).

If $m=n$ or $\mathrm{OPT}=0$ , then $F_{Q}=F_{P}$ , and stability holds deterministically. Otherwise, Proposition 2.4 and $m\geq 20\varepsilon^{-2}$ give (12) with probability at least $9/10$ . Uniform sampling also gives

\mathbb{E}F_{Q}(\mu)=F_{P}(\mu)=\mathrm{OPT}.

Thus (13) holds with probability at least $9/10$ by Markov’s inequality. A union bound shows that both events hold with probability at least $4/5$ , without requiring independence. Lemma 2.6 completes the proof. ∎

3 Optimality for uniform sampling

Put two clusters near $0$ and $1$ , with a population imbalance of order $\varepsilon$ . The population then favors one endpoint by more than the permitted stability loss. A sample with a majority from the other cluster reverses that comparison. We show that this happens with constant probability when $m\varepsilon^{2}$ is small: choose the population large enough to approximate the hypergeometric law by a binomial law, then compare that binomial law with the unbiased one. Small perturbations of size $O(\varepsilon^{2})$ make every point distinct without changing either cost comparison. This refines the two-location construction in [1, Appendix A] for the stated without-replacement guarantee.

Proof of Theorem 1.2(ii).

Fix $0<\varepsilon\leq 1/100$ and an integer $1\leq m\leq\varepsilon^{-2}/24200$ . Put

\rho:=\frac{\varepsilon^{2}}{100},\qquad n\geq\max\left\{\frac{2}{\varepsilon},\,10m(m-1),\,m\right\},

where $n$ is an integer. Set

n_{A}:=\left\lfloor\frac{(1-10\varepsilon)n}{2}\right\rfloor,\qquad n_{B}:=n-n_{A}.

Choose $n_{A}$ distinct points in $[-\rho,\rho]$ and $n_{B}$ distinct points in $[1-\rho,1+\rho]$ , obtaining disjoint sets $A$ and $B$ . Both cardinalities are positive. Let $P=A\sqcup B$ , and write

\theta:=1-\frac{2n_{A}}{n},\qquad p_{A}:=\frac{n_{A}}{n}=\frac{1-\theta}{2},\qquad p_{B}:=\frac{n_{B}}{n}=\frac{1+\theta}{2}.

The rounding error satisfies

10\varepsilon\leq\theta<10\varepsilon+\frac{2}{n}\leq 11\varepsilon.

(16)

We first compare the population costs at $0$ and $1$ . The locations of the two clusters give

F_{P}(0)\geq p_{B}(1-\rho),\qquad F_{P}(1)\leq p_{A}+\rho.

Moreover,

	$\displaystyle p_{B}-(1+17\varepsilon)p_{A}$	$\displaystyle=\theta-\frac{17\varepsilon}{2}(1-\theta)$
		$\displaystyle\geq\frac{3}{2}\varepsilon+85\varepsilon^{2}.$

Since $\theta\leq 11/100$ and $\varepsilon\leq 1/100$ , we have $p_{B}+1+17\varepsilon<2$ . Therefore

	$\displaystyle F_{P}(0)-(1+17\varepsilon)F_{P}(1)$	$\displaystyle\geq p_{B}-(1+17\varepsilon)p_{A}-\rho(p_{B}+1+17\varepsilon)$
		$\displaystyle>\frac{3}{2}\varepsilon+85\varepsilon^{2}-2\rho>0.$

In particular,

F_{P}(0)>(1+17\varepsilon)F_{P}(1).

(17)

Now let $S=|Q\cap A|$ and $s=S/m$ . On the event $S\geq\lceil m/2\rceil$ ,

F_{Q}(0)\leq 1-s+\rho\leq\frac{1}{2}+\rho,\qquad F_{Q}(1)\geq s(1-\rho)\geq\frac{1}{2}(1-\rho).

Our choice of $\rho$ gives $\rho(3+\varepsilon)\leq\varepsilon$ , which is equivalent to

\frac{1}{2}+\rho\leq(1+\varepsilon)\frac{1}{2}(1-\rho).

Thus this event implies $F_{Q}(0)\leq(1+\varepsilon)F_{Q}(1)$ , contradicting stability by (17).

The cost inequalities reduce failure of stability to a single counting event. Its probability can be estimated without a central limit theorem. The variable $S$ is hypergeometric with population size $n$ , number of marked indices $n_{A}$ , and sample size $m$ . Let

Z_{\theta}\sim\operatorname{Bin}\left(m,\frac{1-\theta}{2}\right),\qquad Z_{0}\sim\operatorname{Bin}\left(m,\frac{1}{2}\right).

For probability laws $U, V$ on a common finite set, write $d_{\mathrm{TV}}(U,V)=\tfrac{1}{2}\sum_{a}|U(a)-V(a)|$ , and let $\mathcal{L}(W)$ denote the law of a random variable $W$ .

Draw $m$ independent uniform indices from $[n]$ . Conditional on no collision, the ordered tuple is uniform over injective tuples. If a collision occurs, replace the tuple by an independent uniform injective tuple. The resulting tuple has the without-replacement law, and the two cluster counts agree whenever there was no collision. Hence

d_{\mathrm{TV}}(\mathcal{L}(S),\mathcal{L}(Z_{\theta}))\leq\frac{m(m-1)}{2n}\leq\frac{1}{20}.

(18)

The remaining discrepancy is the bias of the binomial law. We control it through the affinity of the underlying product measures, so the relevant quantity is $m\theta^{2}$ , rather than $m\theta$ . For laws $U, V$ , define $a(U,V):=\sum_{w}\sqrt{U(w)V(w)}$ . Cauchy–Schwarz gives

	$\displaystyle d_{\mathrm{TV}}(U,V)$	$\displaystyle=\frac{1}{2}\sum_{w}\|\sqrt{U(w)}-\sqrt{V(w)}\|(\sqrt{U(w)}+\sqrt{V(w)})$
		$\displaystyle\leq\frac{1}{2}\sqrt{(2-2a(U,V))(2+2a(U,V))}=\sqrt{1-a(U,V)^{2}}.$

For the product laws

U_{\theta}=\operatorname{Ber}\left(\frac{1-\theta}{2}\right)^{\otimes m},\qquad U_{0}=\operatorname{Ber}\left(\frac{1}{2}\right)^{\otimes m},

the sum defining $a$ factors across coordinates, so

a(U_{\theta},U_{0})^{2}=\left(\frac{1+\sqrt{1-\theta^{2}}}{2}\right)^{m}.

Taking the sum of the Bernoulli coordinates cannot increase total variation, by the triangle inequality on each fiber of the summation map. Using $1-u^{m}\leq m(1-u)$ for $0\leq u\leq 1$ , and $1-\sqrt{1-\theta^{2}}\leq\theta^{2}$ , we obtain

d_{\mathrm{TV}}(\mathcal{L}(Z_{\theta}),\mathcal{L}(Z_{0}))\leq\sqrt{1-\left(\frac{1+\sqrt{1-\theta^{2}}}{2}\right)^{m}}\leq\sqrt{\frac{m\theta^{2}}{2}}.

(19)

By (16) and the bound on $m$ , $m\theta^{2}\leq 121/24200=1/200$ , so the last expression is at most $1/20$ . Symmetry gives $\mathbb{P}[Z_{0}\geq\lceil m/2\rceil]\geq 1/2$ . Combining this with (18) and (19) yields

\mathbb{P}\left[S\geq\left\lceil\frac{m}{2}\right\rceil\right]\geq\frac{1}{2}-\frac{1}{20}-\frac{1}{20}=\frac{2}{5}.

This proves part (ii). In particular, for all sufficiently small $\varepsilon$ , every positive integer at most $\lfloor\varepsilon^{-2}/24200\rfloor$ fails to be a valid threshold in the definition of $m_{2}(\varepsilon)$ . Together with part (i), this proves $m_{2}(\varepsilon)=\Theta(\varepsilon^{-2})$ . ∎

4 Extensions to negative-type metrics

The Euclidean argument used a squared-Hilbert representation to linearize costs and the triangle inequality to normalize the resulting error. These are separate requirements: the representation alone would not justify the relative comparison step. Both are available in a negative-type metric space. We use the squared-Hilbert characterization: a metric space $(X,\mathsf{d})$ is of negative type if there exist a real Hilbert space $H$ and a map $\Psi:X\to H$ such that

\mathsf{d}(a,b)=\left\lVert\Psi(a)-\Psi(b)\right\rVert_{H}^{2}\qquad(a,b\in X).

(20)

This is equivalent to the usual condition $\sum_{i,j}c_{i}c_{j}\mathsf{d}(x_{i},x_{j})\leq 0$ for every finite choice of points and real coefficients satisfying $\sum_{i}c_{i}=0$ [3, 4]. In this section, costs and stability are defined on $X$ by

F_{A}(z):=\frac{1}{|A|}\sum_{p\in A}\mathsf{d}(z,p),\qquad z\in X,

with the implication in Definition 1.1 required for all $x,y\in X$ .

Corollary 4.1 (Attained medians in negative-type metrics).

Let $(X,\mathsf{d})$ satisfy (20), and let $P$ be a nonempty finite indexed dataset whose population $1$ -median is attained in $X$ . For $0<\varepsilon<1/4$ and $\lceil 20\varepsilon^{-2}\rceil\leq m\leq|P|$ , a uniform sample of size $m$ is a stable $(\varepsilon,17\varepsilon)$ -coreset with probability at least $4/5$ .

Proof.

Let $\mu$ attain $\mathrm{OPT}=\min_{z\in X}F_{P}(z)$ , and set $\Phi(z)=\Psi(z)-\Psi(\mu)$ . Then $\left\lVert\Phi(p)\right\rVert_{H}^{2}=\mathsf{d}(p,\mu)$ . The cost-difference identity and finite-population variance calculation in Lemmas 2.2 and 2.3 apply to this map. Also,

\mathsf{d}(x,y)\leq F_{P}(x)+F_{P}(y),\qquad 2\mathrm{OPT}\leq F_{P}(x)+F_{P}(y).

The first inequality is the metric triangle inequality averaged over $P$ ; the second follows from optimality. These give the comparison estimate (9) by exactly the three inequalities in the proof of Proposition 2.4. Finally, $\mathbb{E}F_{Q}(\mu)=\mathrm{OPT}$ , and the scalar calculation in Lemma 2.6 gives stability on the intersection of the same two $9/10$ -probability events. If $\mathrm{OPT}=0$ , all points coincide and the conclusion is deterministic. ∎

For $\ell_{1}^{d}$ , the required representation is coordinatewise and a median is attained in every coordinate. Thus the extension removes the dimension factor without passing through a finite-dimensional Euclidean embedding.

Corollary 4.2 (The $\ell_{1}$ metric).

Let $m_{1}(\varepsilon)$ be the threshold defined as $m_{2}(\varepsilon)$ , with $\ell_{1}$ costs in place of Euclidean costs. Then $m_{1}(\varepsilon)=\Theta(\varepsilon^{-2})$ . The upper bound and the one-dimensional lower bound have the constants of Theorem 1.2.

Proof.

For $a\in\mathbb{R}$ , define

\psi(a)(t):=\mathbf{1}_{\{t\leq a\}}-\mathbf{1}_{\{t\leq 0\}}\quad\text{in }L_{2}(\mathbb{R},\lambda).

Then $\left\lVert\psi(a)-\psi(b)\right\rVert_{2}^{2}=|a-b|$ . The direct-sum map $\Psi(x)=(\psi(x_{1}),\ldots,\psi(x_{d}))$ therefore satisfies

\left\lVert\Psi(x)-\Psi(y)\right\rVert_{H}^{2}=\sum_{j=1}^{d}|x_{j}-y_{j}|=\left\lVert x-y\right\rVert_{1}.

Choosing a median in each coordinate gives an attained population $1$ -median. Corollary 4.1 proves the upper bound. On the line, the $\ell_{1}$ and Euclidean distances agree, so Section 3 proves the lower bound. ∎

Attainment was used to choose an anchor whose cost equals the lower bound on all candidate costs. An anchor within a factor $1+\delta$ of the infimum changes the variance bound by this factor and introduces one additional term in the scalar stability calculation. Tracking these two changes gives the following version, which also covers metric spaces without an attained median.

Proposition 4.3 (Approximate reference points).

Let $(X,\mathsf{d})$ satisfy (20), and let $P$ be a nonempty finite indexed dataset in $X$ . Suppose that, for some $\mu\in X$ and $\delta\geq 0$ ,

\alpha:=\inf_{z\in X}F_{P}(z),\qquad T:=F_{P}(\mu)\leq(1+\delta)\alpha.

0<\varepsilon<\frac{1}{4},\qquad\delta<\frac{5-19\varepsilon}{9+\varepsilon},\qquad\left\lceil 20(1+\delta)\varepsilon^{-2}\right\rceil\leq m\leq|P|,

then a uniform sample of size $m$ is a stable $(\varepsilon,17\varepsilon)$ -coreset with probability at least $4/5$ . Consequently, the conclusion of Corollary 4.1 holds without attainment after an arbitrarily small constant-factor increase in the sample-size bound.

Proof.

If $T=0$ , all data points coincide with $\mu$ , and $F_{Q}=F_{P}$ . Assume $T>0$ , and anchor $\Psi$ at $\mu$ . The resulting feature means satisfy

\mathbb{E}\left\lVert v_{Q}-v_{P}\right\rVert_{H}^{2}\leq\frac{T}{m}\leq\frac{(1+\delta)\alpha}{m}.

Markov’s inequality gives $\left\lVert v_{Q}-v_{P}\right\rVert_{H}^{2}\leq 10T/m$ with probability at least $9/10$ . On this event, the cost-difference identity and the inequalities

\mathsf{d}(x,y)\leq F_{P}(x)+F_{P}(y),\qquad 2\alpha\leq F_{P}(x)+F_{P}(y)

give, simultaneously for all $x,y\in X$ ,

	$\displaystyle\|\Delta_{P,Q}(x,y)\|$	$\displaystyle\leq 2\sqrt{\frac{10\mathsf{d}(x,y)T}{m}}$
		$\displaystyle\leq\sqrt{\frac{20(1+\delta)}{m}}\,[F_{P}(x)+F_{P}(y)]$
		$\displaystyle\leq\varepsilon[F_{P}(x)+F_{P}(y)].$

Here $\Delta_{P,Q}$ is defined by (4) using $\mathsf{d}$ -costs. Separately, $\mathbb{E}F_{Q}(\mu)=T$ , so $F_{Q}(\mu)\leq 10T$ with probability at least $9/10$ . Both events hold with probability at least $4/5$ .

On their intersection, for every $z\in X$ ,

	$\displaystyle F_{Q}(z)$	$\displaystyle\leq F_{P}(z)-T+F_{Q}(\mu)+\varepsilon[F_{P}(z)+T]$
		$\displaystyle\leq(1+\varepsilon)F_{P}(z)+(9+\varepsilon)T$
		$\displaystyle\leq\bigl[10+2\varepsilon+(9+\varepsilon)\delta\bigr]F_{P}(z),$

where $T\leq(1+\delta)\alpha\leq(1+\delta)F_{P}(z)$ . Thus any comparison $F_{Q}(x)\leq(1+\varepsilon)F_{Q}(y)$ implies

(1-\varepsilon)F_{P}(x)\leq\bigl[1+11\varepsilon+2\varepsilon^{2}+\varepsilon(9+\varepsilon)\delta\bigr]F_{P}(y).

The difference between $(1+17\varepsilon)(1-\varepsilon)$ and the bracketed coefficient is

\varepsilon\bigl[5-19\varepsilon-(9+\varepsilon)\delta\bigr]>0.

This proves stability.

Finally, if $\alpha=0$ , then for every pair of data indices $i, j$ and every $z\in X$ ,

\mathsf{d}(p_{i},p_{j})\leq\mathsf{d}(p_{i},z)+\mathsf{d}(p_{j},z)\leq 2|P|F_{P}(z).

Taking the infimum over $z$ shows that all data points coincide, so their common point attains the minimum. Therefore nonattainment implies $\alpha>0$ . For every $\delta>0$ , the definition of the infimum then provides a point $\mu$ with $F_{P}(\mu)\leq(1+\delta)\alpha$ . For each $0<\varepsilon<1/4$ , the permitted upper bound on $\delta$ is positive, so $\delta$ can be chosen arbitrarily small. More uniformly, since $(5-19\varepsilon)/(9+\varepsilon)>1/37$ on this interval, any $0<\delta<1/37$ works for every $0<\varepsilon<1/4$ . As before, if the requested sample size exceeds $|P|$ , one returns $P$ . ∎

Appendix A An alternative proof by projected distribution functions

There is a second way to obtain the Euclidean comparison bound without covering the candidate space. In one dimension, a cost difference is an integral over the interval between the two candidates, so its error is bounded by the largest empirical-distribution discrepancy. Averaging the square of this discrepancy over Gaussian projections yields one random quantity that controls every pair of centers. The proof below implements this route directly under sampling without replacement; its larger constant does not affect the $\varepsilon^{-2}$ rate.

Proposition A.1 (Projection-based comparison).

Let $P\in(\mathbb{R}^{d})^{n}$ be indexed, and let $Q$ be a uniform sample of size $1\leq m\leq n$ . With probability at least $9/10$ ,

|\Delta_{P,Q}(x,y)|\leq\sqrt{\frac{320\pi}{m}}\,[F_{P}(x)+F_{P}(y)]\qquad\text{for all }x,y\in\mathbb{R}^{d}.

(21)

Consequently, for $0<\varepsilon<1/4$ and $\lceil 320\pi\varepsilon^{-2}\rceil\leq m\leq n$ , the sample is a stable $(\varepsilon,17\varepsilon)$ -coreset with probability at least $4/5$ .

Proof.

If $m=n$ , then $F_{Q}=F_{P}$ . Suppose $m<n$ , so $n\geq 2$ . Fix $g\in\mathbb{R}^{d}$ , order the values $\left\langle g,p_{i}\right\rangle$ , and break ties by index. Let $S_{k}$ count sampled indices among the first $k$ positions, and put

D_{k}:=\frac{S_{k}}{m}-\frac{k}{n},\qquad 0\leq k\leq n.

Write

G_{A,g}(t):=\frac{1}{|A|}\sum_{p\in A}\mathbf{1}_{\{\left\langle g,p\right\rangle\leq t\}},\qquad K_{g}:=\sup_{t\in\mathbb{R}}|G_{Q,g}(t)-G_{P,g}(t)|.

The distribution functions change only at projected data values; ties restrict the eligible prefix endpoints. Hence

K_{g}\leq\max_{0\leq k\leq n}|D_{k}|.

(22)

For a fixed sample, $K_{g}$ is measurable in $g$ : the supremum can be taken over the finitely many thresholds $\left\langle g,p_{i}\right\rangle$ , and all resulting comparisons are measurable.

We first control all prefixes in the projected ordering. Sampling without replacement gives a finite-population bridge; dividing its centered count by the number of unrevealed positions produces a martingale. Forward and reverse orderings let us use it away from its singular endpoint. Specifically, for every fixed $g$ ,

\mathbb{E}_{Q}K_{g}^{2}\leq\frac{16}{m}.

(23)

For $0\leq k<n$ , define

M_{k}:=\frac{S_{k}-km/n}{n-k}.

Let $\mathcal{F}_{k}$ reveal the sample membership of the first $k$ ordered indices. Conditional on $\mathcal{F}_{k}$ , the remaining $m-S_{k}$ sampled indices are uniform among $n-k$ positions. Thus

\mathbb{E}[S_{k+1}\mid\mathcal{F}_{k}]=S_{k}+\frac{m-S_{k}}{n-k},

and substitution gives $\mathbb{E}[M_{k+1}\mid\mathcal{F}_{k}]=M_{k}$ for $0\leq k<n-1$ .

Let $r=\lfloor n/2\rfloor$ . The sample membership indicators have variance $(m/n)(1-m/n)$ and pairwise covariance $-(m/n)(1-m/n)/(n-1)$ . Summing over the first $r$ positions yields

\operatorname{Var}(S_{r})=r\frac{m}{n}\left(1-\frac{m}{n}\right)\frac{n-r}{n-1},

\mathbb{E}M_{r}^{2}=\frac{r(m/n)(1-m/n)}{(n-1)(n-r)}\leq\frac{m}{n(n-1)}.

Since $D_{k}=(n-k)M_{k}/m$ , Doob’s $L_{2}$ maximal inequality gives

\mathbb{E}\max_{0\leq k\leq r}|D_{k}|^{2}\leq\frac{n^{2}}{m^{2}}\,4\mathbb{E}M_{r}^{2}\leq\frac{4n}{m(n-1)}\leq\frac{8}{m}.

For the reversed ordering, the discrepancy of a prefix of length $n-k$ is $-D_{k}$ . Applying the same estimate in that ordering bounds the expected squared maximum over $\lceil n/2\rceil\leq k\leq n$ by $8/m$ . These two ranges cover all integer indices from $0$ to $n$ . The square of their combined maximum is at most the sum of the two squared maxima, proving (23).

For $a,b\in\mathbb{R}$ , let $h_{a,b}(t)=|a-t|-|b-t|$ , and let $\nu_{g}$ be the difference between the normalized empirical measures of $Q$ and $P$ after projection onto $g$ . The derivative $h_{a,b}^{\prime}$ vanishes outside the interval between $a$ and $b$ and has absolute value $2$ inside it. The signed measure $\nu_{g}$ has total mass zero. Integrating $h_{a,b}(t)=a-b+\int_{-\infty}^{t}h_{a,b}^{\prime}(u)\,du$ against this finite signed measure therefore gives

	$\displaystyle\left\|\int h_{a,b}(t)\,d\nu_{g}(t)\right\|$	$\displaystyle=\left\|\int_{\mathbb{R}}h_{a,b}^{\prime}(t)[G_{Q,g}(t)-G_{P,g}(t)]\,dt\right\|$
		$\displaystyle\leq 2\|a-b\|K_{g}.$		(24)

Values at the finitely many atoms do not affect the Lebesgue integral.

For $g\sim\gamma_{d}$ , the identity $\left\lVert z\right\rVert_{2}=\sqrt{\pi/2}\,\mathbb{E}_{g}|\left\langle g,z\right\rangle|$ and (24) imply, for every fixed sample $Q$ ,

	$\displaystyle\|\Delta_{P,Q}(x,y)\|$	$\displaystyle\leq 2\sqrt{\frac{\pi}{2}}\,\mathbb{E}_{g}\bigl[\|\left\langle g,x-y\right\rangle\|K_{g}\bigr]$
		$\displaystyle\leq 2\sqrt{\frac{\pi}{2}}\,\left\lVert x-y\right\rVert_{2}\bigl(\mathbb{E}_{g}K_{g}^{2}\bigr)^{1/2}.$

All integrals are finite because $K_{g}\leq 1$ and Gaussian linear functionals have finite first and second moments. By Tonelli’s theorem and (23),

\mathbb{E}_{Q}\mathbb{E}_{g}K_{g}^{2}\leq\frac{16}{m}.

Markov’s inequality gives $\mathbb{E}_{g}K_{g}^{2}\leq 160/m$ with probability at least $9/10$ . On this one event, the preceding bound and $\left\lVert x-y\right\rVert_{2}\leq F_{P}(x)+F_{P}(y)$ prove (21) for all $x, y$ simultaneously.

When $m\geq 320\pi\varepsilon^{-2}$ , this gives (12). Combining it with the event $F_{Q}(\mu)\leq 10\mathrm{OPT}$ and Lemma 2.6 proves the stability assertion by the same union bound as in Section 2. The zero-optimum case is deterministic. ∎

References

[1] Amir Carmel, Robert Krauthgamer, and Nir Petruschka. Optimal stable coresets for geometric median via uniform sampling. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2026), volume 392 of Leibniz International Proceedings in Informatics, pages 30:1–30:14, 2026. https://doi.org/10.4230/LIPIcs.APPROX/RANDOM.2026.30.
[2] Amir Carmel and Robert Krauthgamer. Stable coresets: Unleashing the power of uniform sampling. In 14th International Conference on Learning Representations (ICLR 2026), 2026. https://openreview.net/forum?id=sOpAa8iR0A.
[3] I. J. Schoenberg. Metric spaces and positive definite functions. Transactions of the American Mathematical Society, 44(3):522–536, 1938. https://doi.org/10.1090/S0002-9947-1938-1501980-0.
[4] Dino Sejdinovic, Bharath Sriperumbudur, Arthur Gretton, and Kenji Fukumizu. Equivalence of distance-based and RKHS-based statistics in hypothesis testing. The Annals of Statistics, 41(5):2263–2291, 2013. https://doi.org/10.1214/13-AOS1140.
[5] Simon Mak and V. Roshan Joseph. Support points. The Annals of Statistics, 46(6A):2562–2592, 2018. https://doi.org/10.1214/17-AOS1629.

	$\displaystyle\left\|\int h_{a,b}(t)\,d\nu_{g}(t)\right\|$	$\displaystyle=\left\|\int_{\mathbb{R}}h_{a,b}^{\prime}(t)[G_{Q,g}(t)-G_{P,g}(t)]\,dt\right\|$
		$\displaystyle\leq 2\|a-b\|K_{g}.$		(24)

Optimal uniform sampling for stable geometric median coresets

Abstract

1 Introduction

1.1 Model and main result

Definition 1.1 (Stable coreset).

Theorem 1.2 (Optimal uniform sample complexity).

2 Uniform comparison and the stable-coreset bound

Lemma 2.1 (Squared-Hilbert representation).

Proof.

Lemma 2.2 (Cost-difference identity).

Proof.

Lemma 2.3 (Finite-population variance).

Proof.

Proposition 2.4 (Simultaneous relative comparison).

Proof.

Remark 2.5 (Why the error must depend on the center).

Lemma 2.6 (Stability from relative comparison).

Proof.

Proof of Theorem 1.2(i).

3 Optimality for uniform sampling

Proof of Theorem 1.2(ii).

4 Extensions to negative-type metrics

Corollary 4.1 (Attained medians in negative-type metrics).

Proof.

Corollary 4.2 (The ℓ1 metric).

Proof.

Proposition 4.3 (Approximate reference points).

Proof.

Appendix A An alternative proof by projected distribution functions

Proposition A.1 (Projection-based comparison).

Proof.

References

Optimal uniform sampling for
stable geometric median coresets

Corollary 4.2 (The $\ell_{1}$ metric).