Summary
The authors suggest an approach for controlling errors of various types (simultaneously) within a PAC-Bayes framework. They derive a high probability bound on the KL divergence between the empirical and distribution risk vectors. This generalizes earlier work in the binary case by Maurer, 2004 and Begin et al 2016. The authors propose a method for using this bound as a (differentiable) training objective via considering a linear combination of the elements of the risk vector and inverting the resulting binary KL divergence.
Strengths
- The main result seems to be a creative and potentially useful extension of the PAC-Bayesian framework.
- Results are generally introduced with some explanation, and given more context after the result, which improves readability.
Weaknesses
- The framework considered would be better motivated by providing a specific example (ideally with an experiment) indicating the usefulness of the method (and illustrating why existing approaches with a union bound are insufficient).
- The authors included the NeurIPS checklist from last year (and not from this year).
- The proof of theorem 2 is very long and either an outline/proof sketch should be provided at the beginning, or the proof should be broken into lemmas/propositions to improve readability.
Questions
- Is it really not possible to upper bound arbitrary linear combinations of different types of risk with a union bound? I would think that bounding finitely many would place linear constraints on other linear combinations, allowing at least some bounds to be derived. It isn’t immediately obvious to me how sharp the resulting bounds would be, or if indeed this approach leads to non-vacuous bounds, but I’d appreciate the authors commenting on this and adding some discussion on the topic if the answer to my question is that it is possible.
- How would $\ell$ be chosen in practice when defining the objective function? It seems the whole purpose of the framework is to provide useful bounds simultaneously for many types of predictive errors. But it also seems the choice of $\ell$ will have a large impact on how well a method trained with proposed approach will perform on tasks that weight certain types of errors heavily.
Limitations
- The authors acknowledge limited experiments as a limitation of the current work. I agree that this is a limitation. In particular, I wonder whether similar results can be obtained using held-out data, and whether or not the bounds derived this way are competitive with this approach. In the one experiment provided, half of MNIST was used to define the prior, while have was used for optimization of the bound. It seems possible that a similar breakdown of data between a training and validation set (trying directly via cross-entropy loss) might lead to similar model performance and tighter bounds on the risk (as in the cases considered in Foong et al). It isn’t immediately obvious whether it is easy to directly invert the multinomial CDF to derive tight bounds on various datasets as in the binary case using holdout data. But I’m curious to hear the authors’ thoughts on this approach.
- The authors point out that the bound is limited to discrete cases. This seems reasonable, and there are many discrete problems where the bound might be useful. I think finding a concrete problem (dataset, with a plausible decision depending on balancing error types) where this bound might be useful would be more convincing to address this limitation than extending the work to continuous problems.
Minor points:
- Line 147: $S_{m,n}^{>0}$ isn’t the interior of $S_{m,n}$ in a topological sense, assuming $S_{m,n}$ is considered with the discrete topology, which seems the natural choice. Otherwise, I don’t know what is meant by interior.
- Line 198: "Different different"