function $w_t = \operatorname*{argmin}_w {b}_t(w)$. The bound at iteration $t$ is chosen from a set of [“valid”]{} bounds $\mathcal{B}_t$ (see Figure \[fig:cccp\_vs\_ours\]). In practice, we assume that the members of $\mathcal{B}_t$ come from a family $\mathcal{F}$ of functions that upper bound $F$ and can be optimized efficiently, such as quadratic functions, or quadratic functions with linear constraints. Algorithm \[alg:our\_framework\] gives the outline of the approach.

This general scheme is used in both MM and [G-MM]{}. However, as we shall see in the rest of this section, MM and [G-MM]{}have key differences in the way they measure progress and the way they construct new bounds.

Progress Measure
----------------

MM measures progress with respect to the objective values. To guarantee progress over time MM requires that the bound at iteration $t$ must touch the objective function at the previous solution, leading to the following constraint: $$\begin{aligned}
    \textbf{MM constraint:}
    \hspace{1cm}
    b_t(w_{t-1}) = F(w_{t-1}). 
\label{eq:MMconstraint}\end{aligned}$$ This touching constraint, together with the fact that $w_t$ minimizes $b_t$ leads to $F(w_t) \le F(w_{t-1})$. That is, the value of the objective function is non-increasing over time.

The touching requirement is restrictive and, in practice, can make it hard to avoid local minima. In particular, this can make 