On Structured Output Training: Hard Cases and an Efficient Alternative

We consider a class of structured prediction problems for which the assumptions made by state-of-the-art algorithms fail. To deal with exponentially sized output sets, these algorithms assume, for ins