  When samples have internal structure, we often see a mismatch between the
objective optimized during training and the model's goal during inference. For
example, in sequence-to-sequence modeling we are interested in high-quality
translated sentences, but training typically uses maximum likelihood at the
word level. The natural training-time loss would involve a combinatorial
problem -- dynamic programming-based global sequence alignment -- but solutions
to combinatorial problems are not differentiable with respect to their input
parameters, so surrogate, differentiable losses are used instead. Here, we show
how to perform gradient descent over combinatorial optimization algorithms that
involve continuous parameters, for example edge weights, and can be efficiently
expressed as linear programs. We demonstrate usefulness of gradient descent
over combinatorial optimization in sequence-to-sequence modeling using
differentiable encoder-decoder architecture with softmax or Gumbel-softmax, and
in image classification in a weakly supervised setting where instead of the
correct class for each photo, only groups of photos labeled with correct but
unordered set of classes are available during training.
