Reviews: A Learning Error Analysis for Structured Prediction with Approximate Inference

This paper is on the important topic of learning with approximate inference. Previous work, e.g., Kulesza and Pereira (2007), has demonstrated the importance of matching parameter update rules and inference approximation methods. This paper presents a new update rule based on PAC Bayes bounds, which is fairly agnostic to the inference algorithm used -- it assumes a multiplicative error bound on model score and supports both over and under approximations. The example given in section 3.2 is a great illustration of how approximation error is more subtle than we might think it is. Sometimes an approximate predictor can fit the training data better because it represents a different family of functions!