of $\theta$. Generalized versions of EM, such as those given by @gen_em, use distributions other than the posterior in an alternating optimization of $F$. This fits into our framework, as we use the exact same objective function, ans only change the bound construction step (which amounts picking the distribution $q$ in EM). We propose both *stochastic* and *deterministic* strategies for bound construction, and demonstrate that they lead to higher quality solutions and less sensitivity to initialization than other EM-like methods.

Proposed Optimization Framework
===============================

.5

------------------------------------------------------------------------

height 1pt

.5

.5

------------------------------------------------------------------------

height 0.5pt

.5

\[alg:our\_framework\]

$v_0 := F(w_0)$ select ${b}_t \in \mathcal{B}_t = \mathcal{B}(w_{t-1}, v_{t-1})$ as in (\[eq:valid\_bounds\_eta\]) \[alg:our\_framework:construct\_bound\] $w_t := \operatorname*{argmin}_w {b}_t(w)$ \[alg:our\_framework:optimize\_bound\] $d_t := {b}_t(w_t) - F(w_t)$ $v_t := {b}_t(w_t) - \eta d_t$ \[alg:our\_framework:vt\] **if** $d_t < \epsilon$ **break**

.5

------------------------------------------------------------------------

height 0.5pt

.5

![image](images/CCCP_vs_ours){width="55.00000%"}

We consider minimization of functions that are bounded from below. The extension to maximization is trivial. Let $F(w) : \mathbb{R} ^d\rightarrow \mathbb{R}$ be a lower-bounded function that we wish to minimize. We propose an iterative procedure that generates a sequence of solutions $w_0,w_1,\ldots$ until it converges. The solution at iteration $t\geq 1$ is obtained by minimizing an upper bound ${b}_t(w)$ to the objective 