Learning problems that involve combinatorial objects are ubiquitous - they include the prediction of graphs, assignments, rankings, trees, groups of discrete labels or preferred sets of a user; the expression of prior structural knowledge for regularization, the identification of sets of important variables, or inference in discrete probabilistic models.