Does the $k$-means algorithm converge to a local minimum if we alter the cluster assignment step? More specifically, if instead of assigning a point to the cluster whose centroid is closest to it, we assign it based on a different closest metric, will the algorithm still converge?
Surely the $SSE$ will no longer monotonically decrease as I can see in my experiments also but the algorithm does converge after a few steps. Is there any way to prove this?
No. You must put some more restrictions. As a counterexample, take a 2 observation space with an expected $2$ clusters I believe if they take the second closest centroid, the assignments will be periodic with period 2. Then again you should perhaps make more precise what should converge, the centroids themselves or the centroid assignments and centroids. Centroid asignments are usually important to have as consistent.
Also many folks here may not know about k-means as it is an algorithm and may fall outside the topic. If you will post here you should at least repose it as a math question by defining all steps of the algorithm and defining 'convergence' in terms of sequences and topology.