Optimizing $Z$ in the Setting of Schapire $\&$ Singer (1998)

In the case where each component of $\vec{v}$ is restricted to the set $\{-1,+1\}$, Schapire $\&$ Singer (1998) give a way to choose $\alpha$ to minimize $Z$ for any possible choice of $\vec{v}$ (using our notation):

$$\alpha = \frac{1}{2} \log\left(\frac{W^+}{W^-}\right) \:\:,$$ (4)

with:

$$W^+ = \sum_{o,k,j} {w((o,k,j))[\hspace{-0.055cm}[\vec{v}[j] - \vec{v}[k] = 2]\hspace{-0.055cm}]} \:\:,$$ (5)

$$W^- = \sum_{o,k,j} {w((o,k,j))[\hspace{-0.055cm}[\vec{v}[j] - \vec{v}[k] = -2]\hspace{-0.055cm}]} \:\:.$$ (6)

Replacing this value of $\alpha$ in eq. (2), gives the following new expression for $Z$:

$$Z = W^0 + 2\sqrt{W^+ W^-} \:\:,$$ (7)

with $W^0=\sum_{o,k,j} {w((o,k,j))[\hspace{-0.055cm}[\vec{v}[j] - \vec{v}[k] = 0]\hspace{-0.055cm}]}$. Schapire $\&$ Singer (1998) raise the problem of minimizing $Z$ as defined in equations (2) and (7). We now show that it is polynomial.

Theorem 4   Minimizing $Z$ as defined either in equations (2), (3) or (7) is polynomial when the components of $\vec{v}_i$ are restricted to the set $\{-1,+1\}$.

Proof: See the Appendix. $\hbox{\vrule width 0.8pt \vbox to6pt{\hrule depth 0.8pt width 5.2pt \vfill\hrule depth 0.8pt}\vrule width 0.8pt}$
A rather striking result given the conjecture of Schapire $\&$ Singer (1998) is that it is the maximization of $Z$, and not its minimization, which is $NP$-Hard. While this is not the purpose of the present paper (we are interested in minimizing $Z$), we have chosen to give here a brief proof sketch of the result, which uses classical reductions from well-known $NP$-Hard problems.

Theorem 5   Maximizing $Z$ as defined either in equations (2), (3) or (7) is $NP$-Hard when the components of $\vec{v}_i$ are restricted to the set $\{-1,+1\}$.

Proof sketch: See the Appendix. $\hbox{\vrule width 0.8pt \vbox to6pt{\hrule depth 0.8pt width 5.2pt \vfill\hrule depth 0.8pt}\vrule width 0.8pt}$