I am trying to understand given same data set and same K - will the SSE of K means be higher than K Medoids or not. both try to minimize the SSE and K-medoids is more robust to outliers - does it mean that also the SSE will be smaller?
*both converged to their optimal state
(1) The K-means algorithm attempts to minimise the WSS (within clusters sum of squares; what is apparently called SSE here). However it is only guranteed to find a local optimum, therefore there is no guarantee that the minimum is global.
(2) K-medoids as a standard does not attempt to minimise the WSS. In particular, it is not normally used with squared distances, and any robustness advantage (which is to some extent questionable; the breakdown point is zero for both) comes from avoiding squares.
(3) The squared loss function is non-robust as it weights every residual with itself, i.e., minimising it will try hard to avoid any large residual, which gives strong influence to outliers.
(4) K-medoids can in principle be used with any dissimilarity. This comprises Euclidean, squared Euclidean (which is closest to minimising WSS), L1 or anything else.
(5) In practice, K-medoids as K-means only will find a local optimum of its objective function, global optimisation is not guaranteed.
(6) It is possible, but makes little sense to use K-medoids with squared Euclidean, because if the dissimilarity is squared Euclidean, the means and not the medoids optimise the WSS. This means that K-medoids with squared Euclidean will attempt to do the same as K-means, but will do it worse. As a consequence it can be expected that K-means will have the smaller or (if the clustering is the same) equal WSS. This however cannot be mathematuically guranteed because algorithms only find local optima, and one may find the odd data set for which K-medoids finds the better one for computational reasons.
(7) The WSS itself as a loss function is very sensitive against outliers. This means that a non-robust solution may have a lower WSS. The fact that K-medoids is (in many but not necessarily all cases) more robust when not using squared Euclidean distances doesn't mean that it produces a smaller WSS, as the WSS itself is not robust.
If you mean the SSE the objective function of K-Means, then K-Means will have a not higher SSE (In any practical case it will have lower).
This is due to the fact you optimize the same function yet for K-Medoids you add constraint. So in case the optimum of K-Means had even only a single centroids of the K centroids which isn't a medoid it means K-Means had a lower SSE.
