Proof of Theorem 6

To avoid confusion, we call $Z'$ the value of $Z$ computed over the transformed set of examples, and $U(\vec{u})$ for $U\in \{Z, Z'\}$ and $\vec{u}\in\{\vec{v}^*,\vec{v}\}$ as the value of criterion $U$ using vector $\vec{u}$. It is simple to obtain a ``sufficient'' bound to check the theorem. We have

$$Z(\vec{v}) = Z'(\vec{v}) - \sum_{ \begin{array}{c} S\subseteq V\\ \vert S\ver... ...times \sum_{j\in S\backslash \{i\}} {e^{-\frac{1}{2}\vec{v}[j]}}}\right)} \:\:,$$ (30)

$$Z'(\vec{v}^*) = Z(\vec{v}^*) + \sum_{ \begin{array}{c} S\subseteq V\\ \vert S\ve... ...mes \sum_{j\in S\backslash \{i\}} {e^{-\frac{1}{2}\vec{v}^*[j]}}}\right)} \:\:.$$ (31)

Here, $W_S$ is the sum of weights of the examples in the original set, whose vectors have ``1'' matching the elements of $S$. Note that $Z'(\vec{v}) \leq Z'(\vec{v}^*)$, since our algorithm is optimal, and we obtain

$$\begin{eqnarray*} \lefteqn{Z(\vec{v})}\\ & \leq & Z(\vec{v}^*) + \sum_{ \begin... ...kslash \{i\}} {e^{-\frac{1}{2}\vec{v}[j]}}\right]}\right)} \:\:. \end{eqnarray*}$$

By taking only the positive part of the right-hand side, and remarking that

• $\forall S \subseteq V, \vert S\vert>1, \forall i \in S$, $\sum_{j\in S\backslash \{i\}} {e^{-\frac{1}{2}\vec{v}^*[j]}} \leq e\left(\frac{... ...c-\vert S\vert}\right) \sum_{j\in V\backslash S} {e^{-\frac{1}{2}\vec{v}^*[j]}}$ (the right sum is $\geq (c-\vert S\vert)e^{-\frac{1}{2}}$ and the left one is $\leq (\vert S\vert-1)\sqrt{e}$),
• the coefficient of $W_S$ in $Z^*$ is $\rho_S=\sum_{i \in S} {e^{\frac{1}{2}\vec{v}^*[i]}\times \sum_{j\in V\backslash S} {e^{-\frac{1}{2}\vec{v}^*[j]}}}$,

we get

$$\begin{eqnarray*} Z(\vec{v}) & \leq & Z(\vec{v}^*) + \sum_{ \begin{array}{c} S\s... ...< & Z(\vec{v}^*) \left(1+\left(\frac{e}{c-k}\right)\right) \:\:, \end{eqnarray*}$$

as claimed.