ScoreQuant

Result · D-GUARDED-LLOYD

Exact gains guard Lloyd proposals

Proved herepublication: internal

Read the proof and evidence →

Meaning

Accepting a Lloyd proposal only after an exact objective check preserves monotonicity.

Scientific context

Batch reassignment is available as a proposal generator, but every proposal it produces is accepted only on the exact objective, never taken on faith, because the unguarded step is not monotone (D-LLOYD-NONMONOTONE). This guard is part of the solver contract rather than an optional safeguard. Setting guard="exchange" hands the proposed labels to the exact exchange engine, so the reported state stays compilable afterward.

Statement

A batch Lloyd/Voronoi reassignment may be used as a proposal, but monotonicity is restored only by accepting proposals that improve the exact D objective.

practical acceleration

Closest prior work

Nearest prior work

Relationships

Rests on

The full chain beneath it

Open next door

In the library

Carried by MahalanobisLloydConfig. Reference.

Every object and refusal

Local graph
Local map of Guarded D-Lloyd proposal is monotone when accepted by exact objective2 prerequisites to the left, 0 results it enables or questions it raises to the right, 0 boundary cases below.Adaptive Mahalanobis Lloyd need not increase DAdaptive Mahalanobis…Exact finite D log-determinant gainExact finite D log-de…Guarded D-Lloyd proposal is monotone when accepted by exact objectiveGuarded D-Lloyd propo…
Prerequisites to the left, what it enables or raises to the right, boundary cases below. Open in the map.

Proof

D9. Adaptive Mahalanobis Lloyd is not monotone

The batch iteration “compute I−1I^{-1} → nearest-centroid reassignment → recompute II” can decrease log⁡det⁡I\log\det I.

Reason:

log⁡det⁡J≤log⁡det⁡I+tr⁡(I−1(J−I)),\log\det J \le \log\det I+\operatorname{tr}(I^{-1}(J-I)),

so the fixed-metric tangent is an upper bound, not a minorizer.

Measured suite: decreasing steps occurred in 57/300 instances; one explicit example loses about 0.137 nat.

From D-optimality · chapter contents