[@ganchev10]. Our framework can deal with these drawbacks. Our key observation is that we can relax the constraint enforced by MM that requires the bounds to touch the objective function, and this relaxation gives us the ability to better avoid sensitivity to initialization, and to incorporate side information.

A closely related work to ours is the pseudo-bound optimization framework by @tang14, which generalizes CCCP by using [“pseudo-bounds”]{} that may intersect the objective function. In contrast, our framework still uses valid bounds, but only relaxes the touching requirement. Also, the pseudo-bound optimization framework is not as general as ours in that it is designed specifically for optimizing binary energies in MRFs, and it restricts the form of surrogate functions to parametric max-flow.

The generalized variants of EM proposed and analyzed by @gen_em and @gam are related to our work when we restrict our attention to probabilistic models and the EM algorithm. EM can be viewed as a bound optimization procedure where the likelihood function involves both the model parameters $\theta$ and a distribution $q$ over the latent variables, denoted by $F(\theta,q)$. Choosing $q$ to be the posterior leads to a lower bound on $F$ that is tight at the current estimate 