denote the data generating distribution as $D$ and regard the training set as i.i.d. samples from $D$, $\{(x_i,y_i)\}_{i=1}^n\overset{iid}{\sim} D$. Then, $-g(b,w)$ is an unbiased estimate of an expected generalization risk when the training set size is $n-1$, defined with respect to loss $\ell$: $$\begin{aligned}
&\mathbb{E}_{S\sim D^{n-1}}\left[R_D^{\ell}\left(w(S,z_S^{t-1})\right)\right]\label{eq:gen_risk}\\
\text{where} ~~~ & R_D^{\ell}(w)=\mathbb{E}_{(x,y)\sim D}\left[\min_{z}\ell(w,x,y,z)\right]\end{aligned}$$ This gives theoretical support for using the bias function defined in (\[eq:loomil\]). However, leave-one-out estimates usually have high variance and are time-consuming to compute, and in practice we found that using fewer folds ($K=10$) offers a better trade-off.

Experiments {#sec:experiments}
===========

We evaluate [G-MM]{}and MM algorithms on [$k$-means]{}clustering and [LS-SVM]{}training on various datasets. Recall from (\[eq:valid\_bounds\_eta\]) that the progress coefficient $\eta$ defines the set of valid bounds $\mathcal{B}_t$ in each step. CCCP and standard [$k$-means]{}bounds correspond to setting ${  \mbox{$\medmuskip=0mu\displaystyle\eta = 1$}}$, thus taking maximally large steps towards a local minimum of the true objective.

[**$\boldsymbol{k}$-means**]{}Clustering {#sec:experiments:clustering}
----------------------------------------

We conduct experiments on four different clustering datasets: Norm-25 [@kmeans:plusplus], D31 [@kmeans:D31], Cloud [@kmeans:plusplus], and GMM-200. Norm-25, D31, and GMM-200 are synthetic and Cloud is from real data. See the references for details about the datasets. GMM-200 was created by us. It is a Gaussian mixture model on $2$-D data with 