We propose a new learning algorithm for the Set Covering Machine and a tight data-compression risk bound that the learner can use for choosing the appropriate tradeoff between the sparsity of a classifier and the magnitude of its separating margin. Also, we show empirical results on how such a margin-sparsity trade-off can lead to better classification accuracy. This is a joint work with Francois Laviolette and Mario Marchand from Universite Laval.