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'( ) ≤ Z'( I *), since our algorithm is optimal, and we obtain Z( )

------- - ----- Z(v ) + VI | S | > 1
By taking only the positive part of the right-hand side, and remarking that
- ∀ S ⊆ V, | S| > 1, Vi ∈ S, ∑ j ∈ s\{i} e- to 'll ≤ e ( ξ - β ) ∑ j ∈ v\s e- to 'll (the right sum

is ≥ (c − | S | ) e − ≥ and the left one is ≤ ( | S | − 1 ) √ e ),
- the coefficient of W 5 in Z* is ρ 5 = ∑ i e s e z t* lil × ∑ j e v\s e- z t* lil we get

$$Z({\vec{v}})$$
Z( v ) - VI | S | > 1 Z(v ) + Wsss v Z(v v
as claimed.

## Proof Of Lemma 2

Z becomes in that case

$$Z\;\;=\;\;\;W_{+}e^{-\frac{1}{2}\Delta}+W_{-}\,e^{\frac{1}{2}\Delta}\;\;,$$

(32)
where ∆ = v [1] − v [0]. There are five different values for ∆ , giving rise to nine different l

$$\Delta=\quad+2$$

) = v = ( − 1 , +1) ,

$$\begin{array}{r l}{\Delta=}&{{}+1}\\ {\Delta=}&{{}0}\\ {\Delta=}&{{}-1}\\ {\Delta=}&{{}-2}\end{array}$$
$$\begin{array}{l}{{\Rightarrow\vec{v}=\left(-1,0\right)\lor\vec{v}=\left(0,+1\right)~,}}\\ {{\Rightarrow\vec{v}=\left(-1,-1\right)\lor\vec{v}=\left(0,0\right)\lor\vec{v}=\left(+1,+1\right)~,}}\\ {{\Rightarrow\vec{v}=\left(0,-1\right)\lor\vec{v}=\left(+1,0\right)~,}}\\ {{\Rightarrow\vec{v}=\left(+1,-1\right)~.}}\end{array}$$
