Regularized risk minimization with the binary hinge loss and its variants
lies at the heart of many machine learning problems. Bundle methods for
regularized risk minimization (BMRM) and the closely related SVMStruct are
considered the best general purpose solvers to tackle this problem. It was
recently shown that BMRM requires $O(1/\epsilon)$ iterations to converge to an
$\epsilon$ accurate solution. In the first part of the paper we use the
Hadamard matrix to construct a regularized risk minimization problem and show
that these rates cannot be improved. We then show how one can exploit the
structure of the objective function to devise an algorithm for the binary hinge
loss which converges to an $\epsilon$ accurate solution in
$O(1/\sqrt{\epsilon})$ iterations.