ScoreQuant

Counterexample · D-LLOYD-NONMONOTONE

Lloyd reassignment can reduce D

Counterexamplepublication: internal

Read the proof and evidence →

Meaning

Updating the Mahalanobis metric and reassigning all observations need not increase the determinant objective.

Scientific context

The obvious algorithm — freeze the metric, reassign every row to its nearest centre, recompute — is not monotone for the determinant objective. One such step can decrease the log determinant. A committed eight-row, two-dimensional, three-cell example loses 0.136521 nat in a single step, and a seeded census recorded 57 decreasing steps out of 300.

The reason is ordinary: the tangent of a concave function is an upper bound, not a lower one, so the usual monotonicity argument for Lloyd-type iteration does not transfer to the determinant criterion. Consequently, the batch iteration is only usable as a proposal generator whose proposals are accepted on the exact objective (D-GUARDED-LLOYD).

No prior-art search has been recorded for this specific counterexample; it is possible that adaptive-metric Lloyd non-monotonicity already appears in the determinant-clustering computational literature.

Statement

Batch recomputation of I^{-1}, nearest-centroid reassignment, and centroid update can decrease the true logdet objective.

solver design guardrail

Where it stops

Refuted by

  • Counterexample fixtureCE-D-LLOYD-001

    Reassigning all rows to their nearest centroid under the current I_q^{-1} Mahalanobis metric, then recomputing centroids, monotonically increases log det I_q.

Relationships

Enables

Open next door

In the library

Carried by MahalanobisLloydConfig. Reference.

Every object and refusal

Local graph
Local map of Adaptive Mahalanobis Lloyd need not increase D0 prerequisites to the left, 1 results it enables or questions it raises to the right, 1 boundary cases below.Guarded D-Lloyd proposal is monotone when accepted by exact objectiveGuarded D-Lloyd propo…Adaptive Mahalanobis Lloyd need not increase DAdaptive Mahalanobis…CE-D-LLOYD-001CE-D-LLOYD-001
Prerequisites to the left, what it enables or raises to the right, boundary cases below. Open in the map.

The example

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

Evidence: COUNTEREXAMPLES/CE-D-LLOYD-001.json. Measured, never theorem authority.