{PAC-Bayesian Collective Stability}
Ben London, Bert Huang, Ben Taskar, Lise Getoor · 2014
Recent results have shown that the gener-alization error of structured predictors de-creases with both the number of examples and the size of each example, provided the data distribution has weak dependence and the predictor exhibits a smoothness property called collective stability. These results use an especially strong definition of collective stability that must hold uniformly over all inputs and all hypotheses in the class. We investigate whether weaker definitions of col-lective stability suffice. Using the PAC-Bayes framework, which is particularly amenable to our new definitions, we prove that generaliza-tion is indeed possible when uniform collec-tive stability happens with high probability over draws of predictors (and inputs). We then derive a generalization bound for a class of structured predictors with variably convex inference, which suggests a novel learning ob-jective that optimizes collective stability. 1