that controls regularization and $\Delta(y, y_i)$ is a non-negative loss function that penalizes the prediction $y$ when the ground truth label is $y_i$.

**Bound construction:** As in the case of [$k$-means]{}, a convex upper bound on the LS-SVM objective can be obtained by imputing latent variables. Specifically, for each example $x_i$, we fix $z_i \in \mathcal{Z}$, and replace the maximization in the last term of the objective with a linear function $w \cdot \phi(x_i, y_i, z_i)$. This forms a family of convex piecewise quadratic bounds, $$\begin{aligned}
    \hspace{-0.23cm}\mathcal{F} \hspace{-0.1cm} = \hspace{-0.1cm} \Bigg\{ \hspace{-0.1cm} \frac{\lambda}{2} ||w||^2 + \frac{1}{n} \hspace{-0.05cm} \sum_{i=1}^n & \max_{y, z}\left( w \cdot \phi(x_i, y, z) + \Delta(y, y_i) \right) 
    - w \cdot \phi(x_i, y_i, z_i) \Bigg| \forall i, z_i \in \mathcal{Z} \hspace{-0.05cm} \Bigg\}.
    \label{eq:boundFamily_lssvm}\end{aligned}$$ The CCCP algorithm for [LS-SVM]{}selects the bound $b_t$ defined by $z^t_i=\operatorname*{argmax}_{z_i} w_{t-1} \cdot \phi(x_i, y_i, z_i)$. This particular choice is a special case of [G-MM]{}when $g({b}, w) = -{b}(w)$.

To generate random bounds from $\mathcal{B}_t$ we use the same approach as in the case of [$k$-means]{}clustering. We perform a random walk in a graph where the nodes are latent configurations leading to valid bounds, and the edges connect latent configurations that differ in a single 