A PAC-Bayesian Perspective on Structured Prediction with Implicit Loss
  Embeddings
  Many practical machine learning tasks can be framed as Structured prediction
problems, where several output variables are predicted and considered
interdependent. Recent theoretical advances in structured prediction have
focused on obtaining fast rates convergence guarantees, especially in the
Implicit Loss Embedding (ILE) framework. PAC-Bayes has gained interest recently
for its capacity of producing tight risk bounds for predictor distributions.
This work proposes a novel PAC-Bayes perspective on the ILE Structured
prediction framework. We present two generalization bounds, on the risk and
excess risk, which yield insights into the behavior of ILE predictors. Two
learning algorithms are derived from these bounds. The algorithms are
implemented and their behavior analyzed, with source code available at
\url{https://github.com/theophilec/PAC-Bayes-ILE-Structured-Prediction}.
