  We present an efficient method for training slack-rescaled structural SVM.
Although finding the most violating label in a margin-rescaled formulation is
often easy since the target function decomposes with respect to the structure,
this is not the case for a slack-rescaled formulation, and finding the most
violated label might be very difficult. Our core contribution is an efficient
method for finding the most-violating-label in a slack-rescaled formulation,
given an oracle that returns the most-violating-label in a (slightly modified)
margin-rescaled formulation. We show that our method enables accurate and
scalable training for slack-rescaled SVMs, reducing runtime by an order of
magnitude compared to previous approaches to slack-rescaled SVMs.
