bound on $F$ by fixing the latent variables $(z_1, \dots, z_n)$ to certain values instead of minimizing over these variables. Bounds constructed this way are quadratic convex functions of $w=(\mu_1,\ldots,\mu_k)$, $$\begin{aligned}
    \mathcal{F} = \left\{\sum_{i=1}^n || x_i - \mu_{z_i} ||^2 \;\middle|\; \forall i,\; z_i \in \{1,\ldots, k\}^n \right\}.
    \label{eq:boundFamily_kmeans}\end{aligned}$$ The [$k$-means]{}algorithm is an instance of MM methods. The algorithm repeatedly assigns each example to its nearest center to construct a bound, and then updates the centers by optimizing the bound. We can set $g({b}, w) = -{b}(w)$ in [G-MM]{}to obtain the [$k$-means]{}algorithm. We can also define $g$ differently to obtain a [G-MM]{}algorithm that exhibits other desired properties. For instance, a common issue in clustering is cluster starvation. One can design a bias function that encourages balanced clusters by selecting $g$ appropriately. We can select a random bound from $\mathcal{B}_t$ by sampling a latent configuration ${  \mbox{$\medmuskip=0mu\displaystylez=(z_1, \dots, z_n)$}}$ uniformly from the set of configurations leading to valid bounds. Specifically, we start from a valid initial configuration ([$k$-means]{}solution) and do a random walk on a graph whose nodes are latent configurations defining valid bounds. The neighbors of a latent configuration $z$ are the latent configurations that can be obtained by changing the 