MM algorithms such as CCCP sensitive to initialization [@naderi12; @multifold; @Hyun14]. The touching constraint also eliminates the possibility of using bounds that do not touch the objective function but may have other desirable properties.

In [G-MM]{}, we measure progress with respect to the bound values. It allows us to relax the touching constraint of MM, stated in (\[eq:MMconstraint\]), and require instead that, $$\begin{aligned}
\textbf{{G-MM\xspace}constraints:}
\hspace{0.3cm}
\begin{cases}
    b_1(w_0) = F(w_0) \\
    b_t(w_{t-1}) \le b_{t-1}(w_{t-1}).
\label{eq:GMMconstraint}
\end{cases}\end{aligned}$$ Note that the [G-MM]{}constraints are weaker than MM. In fact, (\[eq:MMconstraint\]) implies (\[eq:GMMconstraint\]) because $b_{t-1}$ is an upper bound on $F$.

The weaker constraints used in [G-MM]{}do not imply $F(w_t) \le
F(w_{t-1})$, but, are sufficient to ensure that $\forall t, F(w_t) \le F(w_0)$. This follows from the fact that $b_t$ is an upper bound of $F$, $w_t$ is a minimizer of $b_t(w)$, and (\[eq:GMMconstraint\]): $$\begin{aligned}
    F(w_t) & \le b_t(w_t) \le b_t(w_{t-1}) \leq \dots \notag \\
    & \le b_1(w_1) \le b_1(w_0) = F(w_0).
    \label{eq:bound_sequence_ineq}\end{aligned}$$ $$\begin{aligned}
    F(w_t) \le b_t(w_t) \le b_t(w_{t-1}) \leq \dots \le b_1(w_1) \le b_1(w_0) = F(w_0).
    \label{eq:bound_sequence_ineq}\end{aligned}$$

Bound Construction {#sec:bound_construction}
------------------

This section describes step \[alg:our\_framework:construct\_bound\] of Algorithm \[alg:our\_framework\]. To construct new bounds, [G-MM]{} considers a [“valid”]{} subset of the upper bounds in $\mathcal{F}$ 