Centroid Conditions for Squared-Distance Optima

Why Optimal Centers Are Connected to Cell Means

Squared-distance clustering assigns each observation to a nearest center and measures the resulting distortion. If the assignments stayed fixed, the best location for a center would be the mean of the observations assigned to it. The subtle point is that the nearest-center risk does not keep assignments fixed when a center moves. To derive a centroid condition for a locally optimal codebook, we therefore need to know when the assignment can be treated as locally stable.

This tutorial gives that derivative argument when ties occur with probability zero, then examines what changes for empty cells and boundary ties. The condition is a necessary condition for local optimality; it does not by itself establish that a codebook is locally or globally optimal.

Definition: Let $X$ be a random vector in $\mathbb{R}^d$, and let $C=(c_1,\ldots,c_K)$ be a codebook of $K$ centers in $\mathbb{R}^d$. Its squared-distance risk is $$ R(C)=E\left[\min_{1\leq j\leq K}\|X-c_j\|^2\right]. $$ The closed Voronoi cell of $c_j$ is $V_j(C)=\{x:\|x-c_j\|\leq \|x-c_\ell\|\text{ for every }\ell\}$. The unique-nearest region is $U_j(C)=\{x:\|x-c_j\|<\|x-c_\ell\|\text{ for every }\ell\ne j\}$. A cell has positive mass if $P(X\in U_j(C))>0$; its mean is $E[X\mid X\in U_j(C)]$.

The closed cells can overlap on their boundaries. The unique-nearest regions do not overlap, but they need not cover points tied between centers. When ties have probability zero, they cover $X$ with probability one, so they provide an unambiguous assignment for risk calculations.

The Centroid Condition

Assume $X$ has compact support, and $C$ is a local minimizer of $R$ in $(\mathbb{R}^d)^K$. Compact support ensures the expectations and derivative bounds below are finite. Suppose also that $P(X\text{ has more than one nearest center in }C)=0$. Under these conditions, perturbing a center has a well-defined first-order effect: almost every observation retains its nearest-center label for sufficiently small perturbations.

Theorem: Under the assumptions above, every positive-mass unique-nearest region satisfies $$ c_j=E[X\mid X\in U_j(C)]. $$ Equivalently, $E[\mathbf{1}_{\{X\in U_j(C)\}}(X-c_j)]=0$ for each $j$. This is a necessary first-order condition, not a sufficient condition for local optimality.

Proof. Choose arbitrary vectors $h_1,\ldots,h_K\in\mathbb{R}^d$ and perturb the centers along $C(t)=(c_1+th_1,\ldots,c_K+th_K)$. At a point with a unique nearest center $c_j$, the positive gap between its squared distance to $c_j$ and its distances to the other centers ensures that $c_j+th_j$ remains nearest for all sufficiently small $|t|$. At that point, the derivative of the minimum squared distance at $t=0$ is therefore $-2(X-c_j)\cdot h_j$.

To interchange this derivative and expectation, write $g_t(x)=\min_j\|x-c_j-th_j\|^2$. For any two finite lists of real numbers, the difference between their minima is bounded in absolute value by the largest absolute difference between corresponding entries. Consequently, for $0<|t|\leq 1$, $$ \left|\frac{g_t(x)-g_0(x)}{t}\right| \leq 2\max_j\|x-c_j\|\|h_j\|+\max_j\|h_j\|^2. $$ The right side is bounded on the compact support of $X$. Dominated convergence now gives $$ \left.\frac{d}{dt}R(C(t))\right|_{t=0} =-2\sum_{j=1}^K E[\mathbf{1}_{\{X\in U_j(C)\}}(X-c_j)]\cdot h_j. $$ Since $C$ is a local minimizer, this derivative is zero for every choice of the vectors $h_j$: the derivative in any direction and in its opposite direction must both be nonnegative. Varying one $h_j$ at a time shows that each displayed expectation vector is zero. If $p_j=P(X\in U_j(C))>0$, then $$ 0=E[\mathbf{1}_{\{X\in U_j(C)\}}(X-c_j)] =p_j\big(E[X\mid X\in U_j(C)]-c_j\big). $$ Dividing by $p_j$ proves the centroid condition. $\square$

Worked Example: Two Cells Under a Uniform Distribution

Let $X$ be uniform on $[0,1]$, and consider the two centers $c_1=1/4$ and $c_2=3/4$. The centers are equally distant from $x=1/2$, and every other point has a unique nearest center. The tie point has probability zero.

The unique-nearest regions, up to their probability-zero endpoint, are $[0,1/2)$ and $(1/2,1]$. Each has probability $1/2$. Their conditional means are $$ E[X\mid X\in[0,1/2)]=\frac{(1/2)^2/2}{1/2}=\frac14,\qquad E[X\mid X\in(1/2,1]]=\frac{(1^2-(1/2)^2)/2}{1/2}=\frac34. $$ Thus each center equals its cell mean, as required by the centroid condition for a locally optimal codebook with these cells.

The risk can also be checked directly. Since the density is one, $$ R(C)=\int_0^{1/2}(x-1/4)^2\,dx+\int_{1/2}^1(x-3/4)^2\,dx =\frac{1}{96}+\frac{1}{96}=\frac{1}{48}. $$ For example, the first integral is $\big((1/4)^3-(-1/4)^3\big)/3=1/96$. This calculation verifies the distortion, while the derivative argument—not the risk value alone—explains the centroid condition.

Worked Example: Checking Cell Means in a Discrete Model

Suppose $X$ takes the values $-2,-1,2,3$ with probabilities $0.2,0.3,0.2,0.3$, respectively. Consider $c_1=-1.4$ and $c_2=2.6$. The boundary between these centers is their midpoint, $({-1.4+2.6})/2=0.6$, so the first two support points have unique nearest center $c_1$, and the last two have unique nearest center $c_2$. There are no ties.

The first cell has probability $0.2+0.3=0.5$ and mean $$ \frac{0.2(-2)+0.3(-1)}{0.5}=\frac{-0.7}{0.5}=-1.4. $$ The second cell also has probability $0.5$, and its mean is $$ \frac{0.2(2)+0.3(3)}{0.5}=\frac{1.3}{0.5}=2.6. $$ Both centers satisfy the centroid condition. The risk is $$ 0.2(-2+1.4)^2+0.3(-1+1.4)^2+0.2(2-2.6)^2+0.3(3-2.6)^2 =0.072+0.048+0.072+0.048=0.24. $$ This example checks the cell assignments, conditional means, and risk separately; satisfying the mean equations alone would not prove that some other codebook could not have lower risk.

What the Centroid Equation Says for Fixed Assignments

There is a useful identity behind the centroid condition. It describes the best center for a fixed cell, without asserting that the cell assignments remain fixed when the codebook changes.

Result: Let $A$ be an event with $P(A)=p>0$, assume $E[\|X\|^2\mathbf{1}_A]<\infty$, and write $\mu=E[X\mid A]$. For every $a\in\mathbb{R}^d$, $$ E[\mathbf{1}_A\|X-a\|^2] =E[\mathbf{1}_A\|X-\mu\|^2]+p\|a-\mu\|^2. $$ Thus $\mu$ uniquely minimizes the squared-distance loss contributed by $A$.

Derivation. Write $X-a=(X-\mu)+(\mu-a)$, expand the squared norm, and take expectations: $$ E[\mathbf{1}_A\|X-a\|^2] =E[\mathbf{1}_A\|X-\mu\|^2] +2(\mu-a)\cdot E[\mathbf{1}_A(X-\mu)] +p\|\mu-a\|^2. $$ The middle term is zero because $E[\mathbf{1}_A(X-\mu)]=p(E[X\mid A]-\mu)=0$. This proves the identity. Since $p>0$, the last term is nonnegative and vanishes only when $a=\mu$. $\square$

This fixed-cell identity explains why replacing each center by its assigned-cell mean decreases or preserves the loss for those assignments. But the nearest-center risk is based on the best assignment after the centers move. The identity alone does not show that a codebook is optimal, or that a proposed cell partition remains a Voronoi partition after a center update.

Worked Example: An Empty Cell Has No Centroid

Let $X$ equal $-1$ or $1$, each with probability $1/2$, and use $K=3$ centers $c_1=-1$, $c_2=1$, and $c_3=10$. The risk is zero because every observation coincides with one of the first two centers. Since risk is nonnegative, this codebook is globally optimal, hence also locally optimal.

The unique-nearest region of $c_3$ has probability zero: neither possible observation is closer to $10$ than to its matching center. There is no conditional mean $E[X\mid X\in U_3(C)]$, because the conditioning event has probability zero. The centroid condition therefore makes a statement only about the two positive-mass cells, whose means are $-1$ and $1$. An empty cell cannot be handled by dividing its moment equation by its mass; its center may instead be redundant, as it is here.

Boundary Ties Need a Separate Derivative

When an observation is tied between several nearest centers, a perturbation can change which center is nearest immediately. The derivative is then not generally the derivative for one arbitrarily selected cell. For a codebook $C$, define the active set $A_C(x)=\{j:\|x-c_j\|^2=\min_\ell\|x-c_\ell\|^2\}$. Under compact support, the right directional derivative along $h=(h_1,\ldots,h_K)$ is $$ \lim_{t\downarrow0}\frac{R(C+th)-R(C)}{t} =E\left[\min_{j\in A_C(X)}\{-2(X-c_j)\cdot h_j\}\right]. $$ At a tie, the smallest of the active centers' first-order changes determines the right derivative. This is why assigning a tied observation to one cell by convention does not justify using the unique-nearest derivative proof.

In fact, if a positive-probability set is tied between distinct centers, $C$ cannot be a local minimizer under these compact-support conditions. To see why, translate every center by the same vector $v$, so $h_j=v$. Let $D(v)$ denote the right directional derivative. The formula gives $$ D(v)+D(-v) =-2E\left[\max_{j\in A_C(X)}(X-c_j)\cdot v-\min_{j\in A_C(X)}(X-c_j)\cdot v\right]\leq 0. $$ If distinct centers $c_j,c_\ell$ are both active on a positive-mass set, choose $v=c_j-c_\ell$. Their projections $(X-c_j)\cdot v$ and $(X-c_\ell)\cdot v$ differ by a nonzero constant, so the range in the expectation is strictly positive on that set. Hence $D(v)+D(-v)<0$. At a local minimizer both directional derivatives would have to be nonnegative, a contradiction. Ties between coincident centers are different: their active first-order changes under translation agree, but an arbitrary division of tied observations between duplicate labels still need not define meaningful individual cell means.

Worked Example: A Tie That Invalidates a Naive Centroid Check

Let $X=0$ with probability one and take centers $c_1=-1$ and $c_2=1$. The observation lies on their Voronoi boundary, and $R(C)=1$. If a tie-breaking rule assigns the observation to the first center, that assigned cell has mean $0$, not $c_1=-1$. This mismatch is not a violation of the theorem: the no-positive-mass-ties assumption fails, and the codebook is not locally optimal.

Indeed, move only the first center to $-1+\varepsilon$, where $0<\varepsilon<1$. The observation is then closer to that center, and $$ R(-1+\varepsilon,1)=(1-\varepsilon)^2 =1-2\varepsilon+\varepsilon^2<1, $$ because $0<\varepsilon<1$ implies $\varepsilon^2<2\varepsilon$. The risk has a first-order decrease. The example shows both why an arbitrary tie assignment cannot be used as a derivative argument and why a centroid mismatch should prompt a check of the hypotheses rather than an immediate claim about optimality.

Common Mistakes and Practical Meaning

Using the mean condition as a proof of optimality. The condition is necessary under the stated assumptions. It does not rule out a different codebook with lower risk or establish that the current assignment stays fixed after a move.
Applying the equation to an empty cell. When $P(X\in U_j(C))=0$, the conditional mean is undefined. The moment equation is then zero without identifying $c_j$.
Treating closed Voronoi cells as a disjoint partition. Their boundaries can overlap. If boundary probability is positive, an arbitrary tie-breaking rule may change the cell means and does not supply the derivative used in the theorem.
Ignoring the squared-distance assumption. The mean minimizes squared-distance loss. A different distortion can have a different optimizing representative; the median, for example, is associated with absolute-distance loss.

The centroid condition is useful because it links a continuous optimization problem over center locations to the distribution of observations in their nearest-center regions. It also clarifies the scope of mean-based updates: a center should match its cell mean at a differentiable local optimum with positive cell mass, while empty cells and tied assignments require separate analysis.

Check Your Understanding

Use the assumptions and distinctions developed above to answer these questions.

Why does the centroid theorem require a positive-mass cell before writing a conditional mean?
Which step in the derivative proof uses the assumption that ties have probability zero?
For a fixed event $A$, what does the squared-distance identity imply about the loss at a center $a\ne E[X\mid A]$?
In the empty-cell example, why can the third center be part of a globally optimal codebook without satisfying a centroid equation?
For an observation tied between two distinct centers, why can an arbitrary tie-breaking rule give the wrong first-order change in risk?