Shai Shalev-Shwartz, Yoram Singer

- Francesco Orabona pointed out that there is a mistake in the inductive arguments in the proofs of Theorem 1 and Theorem 2. A correct inductive argument for Theorem 2 would be the following:

Claim:

Assume that \tilde{epsilon} \geq 1 and that \epsilon > R^2 / \gamma^2 then: q(epsilon,\tilde{epsilon}) >= q(epsilon,0)

Proof:

Let a be an integer number in {1,...,\tilde{epsilon}}. Then, \epsilon + a - 1 > R^2 / \gamma^2 Therefore: q(\epsilon,a) - q(\epsilon,a-1) \geq 0 By induction we get that q(epsilon,\tilde{epsilon}) >= q(epsilon,0)

QED.

A similar argument can be derived for Theorem 1 as well.

We would like to thank Francesco for pointing out this mistake.