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):

with:

(5) | |||

(6) |

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

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

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.