Next: Optimizing in our Setting Up: Calculating Rule Vectors using Previous: Calculating Rule Vectors using

### Optimizing in the Setting of Schapire Singer (1998)

In the case where each component of is restricted to the set , Schapire Singer (1998) give a way to choose to minimize for any possible choice of (using our notation):

 (4)

with:
 (5) (6)

Replacing this value of in eq. (2), gives the following new expression for :
 (7)

with . Schapire Singer (1998) raise the problem of minimizing as defined in equations (2) and (7). We now show that it is polynomial.

Theorem 4   Minimizing as defined either in equations (2), (3) or (7) is polynomial when the components of are restricted to the set .

Proof: See the Appendix.
A rather striking result given the conjecture of Schapire Singer (1998) is that it is the maximization of , and not its minimization, which is -Hard. While this is not the purpose of the present paper (we are interested in minimizing ), we have chosen to give here a brief proof sketch of the result, which uses classical reductions from well-known -Hard problems.

Theorem 5   Maximizing as defined either in equations (2), (3) or (7) is -Hard when the components of are restricted to the set .

Proof sketch: See the Appendix.

Next: Optimizing in our Setting Up: Calculating Rule Vectors using Previous: Calculating Rule Vectors using