# Subgradient Method for K-Means Like Problem

I want to solve k-means-like problem. But at first, I wonder that we can apply subgradient method to k-means problem.

We want to find the optimal clustering $S = (S_1,S_2,...,S_k)$ such that

$${\operatorname{arg\,min}}_S \sum_{i=1}^{k} \sum_{\mathbf x \in S_i} \left\| \mathbf x - \boldsymbol\mu_i \right\|^2$$

• Your statement of the problem doesn't make sense to me. $\arg \min$ for that function will find an $S_i$ which minimizes the summations for all $\mathbf{x}$ in the given $S_i$. It doesn't seem to find an optimal clustering, though. Can you please reword your question, or put more explanation into what you're trying to achieve?
– Peter K.
Oct 31 '15 at 20:10
• I am sorry for being unclear. For k-means clustering, I want to refer to en.wikipedia.org/wiki/K-means_clustering . Nov 1 '15 at 2:54
• Why would you use the gradient to solve this? Aug 19 '18 at 16:32

I don't see why you would like to use subgradients for that. Correct me if I'm wrong, but when the problem is fully differentiable (kmeans actually is), the subgradient is the gradient vector $$\nabla f$$ itself. Then it might just equate to using an EM-like algorithm, iteratively finding the means and solving for the assignments.

If you like the optimization perspective, think of what we like to do as a joint minimization over cluster centers $$J_2(c_1,\cdots,c_m,\boldsymbol{\mu}_1, ... ,\boldsymbol{\mu}_k)=\frac{1}{m}\sum\limits_i \|\mathbf{x}_i-\boldsymbol{\mu}_{c_i}\|^2$$ where $$\mathbf{c}=(c_1,\cdots,c_m)^\top$$ denotes the cluster indices to which examples $$\{\mathbf{x}_i\}$$ are assigned. We then alternatively solve for $$\mathbf{c}$$ and $$\boldsymbol{\mu}$$.

1. Fix $$\boldsymbol{\mu}$$, solve for $$\mathbf{c}$$: $$\forall 1\leq k\leq K : C(k)\leftarrow \{i : k={\operatorname{arg\,min}}_k\|\mathbf{x}_i−\boldsymbol{\mu}_k\|^2\}$$ Note that recent techniques from optimization (See On Differentiating Parameterized $$\arg \min$$ and $$\arg \max$$ Problems with Application to Bi Level Optimization) can make this step differentiable. Otherwise, one can benefit from subgradients (see below).

2. Fix $$\mathbf{c}$$ and solve for $$\boldsymbol{\mu}$$ by running a gradient descent using: $$\nabla_{\boldsymbol{\mu}} J_2 = \sum_{i=1} 2(\boldsymbol{\mu}-\mathbf{x})^\top = 0$$

You might just use gradient descent for this. If instead, the problem is robustly formulated via an $$L_1$$ norm:

$$J_1(c_1,\cdots,c_m,\boldsymbol{\mu}_1, ... ,\boldsymbol{\mu}_k)=\frac{1}{m}\sum\limits_i |\mathbf{x}_i-\boldsymbol{\mu}_{c_i} |$$

then the estimator can be found by a median and this variant is coined K-medoids (when the center is picked on a data point) or K-medians in the case of Manhattan-distance median. It is also beneficial for discrete problems where computing a continuous mean is difficult. These problems are not differentiable everywhere and subgradients might be useful (in fact either proximal gradients or constrained minimization tools are preferred).

• Why are you saying the K-Means is differential? As it is not. You broke it into approximation using EM which its 2nd step is smooth but not the first one and not the K-Means itself.
– Royi
Jan 4 '19 at 13:45
• By the way, the Gradient in step (2) will yield the result of the this step in K-Means - Mean of the points (As this is the name - K-Means). There are many variants of which took the idea of K-Means and use different metrics for the distance (You can bring any valid metric you'd like).
– Royi
Oct 2 '19 at 1:01
• This is true. I just gave one example of a different norm. Also updated the reply (1) with a link to a paper that aims to differentiate argmin. Making this differentiable can make the whole thing differentiable. Oct 2 '19 at 2:17
• Hi, I don't see in the paper you linked a case where the optimization is over a discrete parameter. In all cases there the parameter is continuous. I might be wrong but I still think the first step isn't differentiable.
– Royi
Oct 2 '19 at 14:10
• It is not. People work around it in one way or the other. Oct 2 '19 at 14:59

You should use something like Robust Convex Clustering:

Assume that we are given $$n$$ data points and each data point is described by a $$d$$ dimensional feature vector. We collectively represent the data by a data matrix $$X \in \mathbb{R}^{d \times n}$$.
The convex clustering method clusters data points into groups via solving a convex optimization problem:

$$\arg \min_{P} \frac{1}{2} \left\| X - P \right\|_{F}^{2} + \alpha \sum_{i < j} {w}_{i, j} \left\| {P}_{i} - {P}_{j} \right\|_{p}$$

Where $$\left\| \cdot \right\|_{p}$$ is the $${L}_{p}$$ norm, $$P \in \mathbb{R}^{d \times n}$$ is the matrix consisting cluster centers and assignments, $${P}_{i}$$ is the $$i$$ -th column of the matrix $$P$$ and represents the centroid of cluster that the $$i$$ -th data point is assigned, $$\alpha$$ is a non-negative regularization parameter that controls the number of clusters. $${w}_{i, j}$$ is the weight between $$i$$ -th and $$j$$ -th data point specified by the user. Clusters are implicitly given by $$P$$ matrix and $${P}_{i} = {P}_{j}$$ means the two data points are in the same cluster. When $$\alpha$$ is zero, each data point forms a cluster since $$P$$ equals to $$X$$ when Eq. (1) reaches the optimum. As $$\alpha$$ increases, $$\left\| {P}_{i} − {P}_{j} \right\|_{p}$$ becomes smaller for all pairs so that the whole function can reach the minimal value. Hence more data points will be grouped into a cluster.

Another great reference is Splitting Methods for Convex Clustering.

As the formulation you chose is not convex and of top of that I don't think anyone has ever calculates its Sub Gradient.

## Update

I encountered another simple yet effective of K-Means - Revisiting K-Means: New Algorithms via Bayesian Nonparametrics.
It formulates the problem in as, intuitively, the Lagrange form of the K-Means with continuous parameter $$\lambda$$ instead of the discrete parameter $$k$$.