Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: summary: This paper sets out to extend the PAC-Bayes framework to establish new generalization bounds for multi-class classification with M classes of errors extending the 0-1 risk. The main results appear to be Theorem 3 and Corollary 7, which generalize previously known results in this space, and can recover those existing results. My biggest concern about this paper is that I don't find the problem setup inspiring. In particular, the only worked out examples are in Section 4. The novel and interesting piece seems to be the definition of kl^-1, but I find the study to be thin. To sum everything up, I think the derived results appear to be correct; there is some novelty in proofs; but the setup of the problem is not well motivated and it is not clear how these results may be used to derive intuition or practical algorithms. 
strengths_and_weaknesses: Strengths 
* The paper is clearly written and the theoretical derivations are clearly discussed

* Theorem 3 extends the existing results in the literature, and the proof requires some nice extension of existing results including Lemma 5.

* Corollary 7 is also a nice extension of the existing results. While I did not follow its proof closely, the form of the result appears to be meaningful.

* The new results motivate some new study, including a new definition of kl^-1 that seems to be interesting.

Weaknesses:

* The setup of the problem is not well motivated, and the study has not resulted in deriving new intuitions.

* The new definition of kl^-1 is not well motivated and the details around it are thin.


questions: * As one example I can think of: can you say anything about balancing false positive rate and false negative rate in a binary classification? 

* In particular, can you probably make any connections with the fairness literature where the goal might be to equalize false positive rate and false negative rate?
limitations: As it currently stands, the impact of the paper is not well quantifiable.
review_title: null

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: summary: The paper studies the PAC-Bayes generalization bound, which is an important topic and has been successfully applied to produce non-vacuous generalization bounds for neural network. The authors extend the existing results to the multiclass setting by introducing the discretized error types, which is a disjoint partition of the assembly of model prediction and ground truth labels. Based on the results, the authors further provide an abstract implementation of the method which can be applied to the real tasks.
strengths_and_weaknesses: Strength:

1.The derived theorems hold for multiclass problem and soft labels, which has a wide range of applications to the real learning tasks. Such results in the PAC-Bayes literature have not been well-studied yet.

2.Although there are no empirical studies to validate the results, the authors provide abstract implementation of the algorithm for better understanding the applications of the theorems.

3.The paper is well presented and easy to understand. Detailed proofs are provided in the paper and supplementary material. 

Weakness:

1.The technical contribution is somewhat weak in my view. The authors leverage the discretized error types to incorporate the entire confusion matrix, but many steps of the proofs mainly follow existing results.

2.For the minor problems, there are some flaws in the paper, e.g., incorrect citations in L13 in the paper.

questions: Although the discretized error types can be arbitrary in the theorem, are there any suggestions to set this parameter in the real tasks?

Can you make more detailed discussion about your results that whether they are vacuous or not?

limitations: N/A
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: The paper deals with multi-class classification with a vector of $M$ possible error types. The paper establishes a PAC-Bayes bound for the convergence of the empirical error vector to the expected one,  under some convex distance measure (Thm. 3), and gives a more explicit bound for the kl-measure between the Multininomial distributions parametrized by those two corresponding vectors (Cor. 7). Finally, the paper discusses how the result of Cor.7 can yield a bound for the individual error types, and how to derive a gradient-based algorithm that minimizes the bound.

strengths_and_weaknesses: ### Strengths

1. The problem of multi-class generalization bounds for the confusion matrix is interesting.
2. The main results (Thm. 3, Cor. 7) seem elegant and non-trivial to derive. 

### Weaknesses

1. The writing can be improved - for example - paragraph 38-48 is hard to follow, The structure of the paper can be improved, currently, the main contributions are hard to discern from smaller details.

2. Classical PAC-Bayes bounds (e.g. Maurer ‘04) can account for non-zero-one losses.  An alternative route to deriving bounds on the divergence of the empirical confusion matrix from the expected one, under some matrix norm, can be using those classical bounds for each error type and then using the union bound. How does this simple approach compares to the results in the paper?  I think the paper lacks comparisons to possible simpler approaches.

3. In the introduction, the authors describe a problem where each error type is associated with a different loss value $\ell_j \in [0, \infty)$. However, if am not mistaken, the bound presented in Thm 3. and Cor. 7 seem to only deal with $\ell_j \in {0,1}$.

4. There are also no explicit results for the convergence of the confusion matrix under some matrix norms.
I may have not understood correctly the results, in that case, I suggest the authors improve the clarity of these issues, by emphasizing the corresponding formulations and results. 

5. There is no experimental validation for the suggested algorithm and for the bounds.



questions: 1. 
Line 170 -  I didn’t understand the comment about $m’$. How is the formulation with $\beta$ more general?

limitations: No further limitations
review_title: null

Meta-review: metareview: 
The consensus was that the reviewers were not convinced that the results were significant, and did not see significant fundamental novelty in the analysis.

confidence: Certain
Decision: Reject