Venue: NeurIPS 2022 Conference

Reviews:

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: This paper considers an extension of the work by Bousquet, Hanneke, Moran, Van Handel, and Yehudayoff on universal learning, and the work by Alon, Hanneke, Holzman, and Moran on the partial concept classes to the multiclass classification problems. 
In the first part of the paper, the authors consider the same setting as in the universal learning paper, and aim for finding the distribution-dependent rates for the decay of the risk. Similar to the universal learning paper, they show that a trichotomy occurs. More precisely, they show that by replacing the VC dimension with the Natarjan dimension in the universal learning paper, one can prove similar results.
In the second part of the paper, the authors consider the problem of partial concept classes. In this section, the authors, by recent results on the performance of the one-inclusion graph algorithm for multi-class problems, propose a learning algorithm for partial concept classes. More precisely, they show that the learnability in this setting can be identified by natural extension of Natarjan dimension to partial concept classes.

strengths_and_weaknesses: In general, I find this paper very interesting. To me, it seems that the authors follow very closely the results in “a theory of universal learning “ and “A Theory of PAC Learnability of Partial Concept Classes “ to obtain the results. I think this does not affect the quality of the paper. Having said that, I think the authors should discuss with more details the new ideas and techniques beyond the existing ones that they use in the paper. I have checked the proof of the learning algorithm for the partial concept classes, and it follows very closely from the existing results. Therefore, I think 1) the authors should highlight the technical challenges for extending the existing techniques, 2) the authors should discuss why the other dimensions instead of Natarjan dimensions such as graph dimension do not work for these problems.

questions: 1- The authors should discuss why they do not consider other dimensions such as Graph dimensions, the Pseudo-dimension, etc. 

2- What are the obstacles for obtaining the high probability versions of the bounds for the universal learning problems?

3- Is the dependence of your results on the number of classes optimal? In light of recent results for infinite classes in characterization of multiclass learnability by Brukhim, Carmon, Dinur, Moran, and Yehudayoff, how can one extend the results to infinite classes?

4- For partial concept classes, in prop 2 the authors provide a sufficient condition for success of ERM. How about the necessary condition? 

5- In the partial concept classes paper, the authors also present results for the agnostic case. What are the obstacles for proving such a result in the multi-class setting?
 

limitations: The authors provide a list of open problems and future directions.
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: This paper studies the problem of multiclass classification with a bounded number of different labels. It mainly extends the main results of [1] and [2] to the multiclass case.

Firstly, the paper provides a complete characterization of the achievable learning rates that holds for every fixed distribution in the universal learning setting and shows that for any concept class, the optimal learning rate is either exponential, linear or arbitrarily slow.

Secondly, the paper considers the structured data, which is captured by partial concept classes proposed by [2].

[1] Olivier Bousquet, Steve Hanneke, Shay Moran, Ramon Van Handel, and Amir Yehudayoff. A theory of universal learning. In Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing, pages 532–541, 2021.
[2] Noga Alon, Steve Hanneke, Ron Holzman, and Shay Moran. A theory of pac learnability of partial concept classes. In 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS), pages 658–671. IEEE, 2022.
strengths_and_weaknesses: Strengths:
1. This paper extends the main works of [1] and [2] to multi-class classification case. The total work has a good contribution to introducing new frameworks beyond the PAC framework in the multiclass setting. I do like the definition of Natarajan-littlestone tree, which is used to generalize the main results of universal learning framework to the multiclass setting.
3. This paper describes the technique overview and proof sketches to help understanding the main tools and techniques used in this paper.

Weaknesses:
1. Some proofs of the main results, e.g. results in Section 1.3, seem to be an adaption of that in [2], except for the difference between the binary setting and multi-class setting. Hence I have some concerns regarding the novelty of this paper.


[1] Olivier Bousquet, Steve Hanneke, Shay Moran, Ramon Van Handel, and Amir Yehudayoff. A theory of universal learning. In Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing, pages 532–541, 2021.

[2] Noga Alon, Steve Hanneke, Ron Holzman, and Shay Moran. A theory of pac learnability of partial concept classes. In 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS), pages 658–671. IEEE, 2022.
questions: 1. As a theoretical work, some of the extensions in the paper just follow the standard idea that generalizing definitions from the binary case to multiclass case (For example, the extension from the Littlestone dimension to the multiclass Littlestone dimension is similar to the standard extension from the VC dimension to the Natarajan dimension. It is similar for the definition of NL tree) and the main results are very similar to those in [1] and [2], hence I have some concerns regarding the technical novelty of this paper. I would appreciate it If the authors can list out some techniques that do not appear in [1] or [2], except for the old-fashioned generalization trick mentioned above. I may adjust the rating according to the quality of the list.
2. Since some characterizations of hypotheses may be very intractable when we extend the binary setting to the multiclass setting. For example, we can exactly calculate the VC dimension of linear binary classifiers, yet we can only bound the order of Natarajan dimension of linear multiclass clasifiers. As a result, I am wondering the practicality of the proposed definitions. Specifically, is it traceable to calculate the Natarajan/multiclass Littlestone tree of some common multiclass hypothetical classes, e.g. linear multiclass classifier class? 


[1] Olivier Bousquet, Steve Hanneke, Shay Moran, Ramon Van Handel, and Amir Yehudayoff. A theory of universal learning. In Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing, pages 532–541, 2021.
[2] Noga Alon, Steve Hanneke, Ron Holzman, and Shay Moran. A theory of pac learnability of partial concept classes. In 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS), pages 658–671. IEEE, 2022.
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 authors relax multiclass PAC learning in two directions:
1) Allow the sample complexity to depend on the distribution (whereas in classical PAC learning the sample complexity shall hold for _all_ distributions over the domain).
2) Allow hypotheses to be partial functions, i.e. be defined not everywhere in the domain (in contrast to the classical PAC, where hypotheses must always be total functions).

In direction 1), which the authors call the theory of _universal_ learning, the work of [Bousquet et al. (STOC 2021)](https://dl.acm.org/doi/abs/10.1145/3406325.3451087) is generalized from binary to multiclass classification, namely:
- The learning rate trichotomy is shown: learning occurs either at an exponential or linear or arbitrarily slow rate (in sample size).
- Characterization of learnability in terms of Littlestone and Natarajan-Littlestone trees is given.
- The optimal algorithms for each of the learning rates are presented, while they are not ERMs.

In direction 2), which the authors refer to as the PAC theory of learnability of _partial_ concept classes, the authors generalized the work of [Alon et al. (FOCS 2021)](https://ieeexplore.ieee.org/abstract/document/9719837) again from the binary case to the multiclass one:
- The definition of the Natarajan dimension in the case of partial classes is introduced, and through it a characterization of the learnability of partial classes and (lower & upper) bounds on sample complexity are given.
- It is shown that the learnability of a partial class $\mathbb{H}$ does not imply the learnability of a total class $\bar{\mathbb{H}}$ that _disambiguates_ $\mathbb{H}$.
- The connection between $k$-class partial learnability and $(k + 1)$-class total learnability (when the value "undefined" is treated as an additional label) is established.
strengths_and_weaknesses: *Strengths*

- A solid work that generalizes the recent two theories from the binary case to the multiclass one. That said, these two recent theories were built in an attempt to bridge the gap between learning theory and applied machine/deep learning practices.

*Weaknesses*

- I am most concerned about the presentation of the material: the density of the narrative is highly heterogeneous throughout the text of the paper. The introduction is well-written, and the motivation of the two proposed theories is immediately clear to the reader. The part about the universal theory of learning is already denser, and by the end of this part it is already difficult to understand what is at stake without looking into the Appendix and googling. The part about partial classes is the most dense, and I personally had to familiarize myself with the binary case first (Alon et al., FOCS 2021) before I could understand anything in this part. My impression is that this submission is an attempt to compress a journal article to the size of a conference paper, and the compression was done very unevenly.
- Although both theories try to fill the gap between the theory and practice of machine learning, I honestly did not understand the connection of one theory with another. More precisely, I can imagine a setup where both theories are combined, but this will be a separate framework.
- In the theory of partial classes, (yet) there is no such simple and clear principle as ERM (This is more about the original work of Alon et al. (2021), but nonetheless). I understand that (for example) in applied deep learning, SGD is not an arbitrary ERM. But after all, SGD is ubiquitous and extremely successful _approximate_ ERM in deep learning. If this theory claims to be an extension of the classical PAC theory explaining modern learning phenomena, I would like to have a simple and understandable learning principle (rather than resorting to improper learning with a transductive algorithm).
questions: Have you tried to find a less obfuscated partial class to prove Theorem 16? Your class relies on the class from Alon et al. (2021), which in turn relies on the superpolynomial separation between the chromatic number and the biclique partition number, which in turn is based on a series of 4 reductions in graph theory and complexity theory ...
limitations: Understanding the paper requires familiarity with the two previous works on which it is based (and beyond).
review_title: null

Meta-review: metareview: This work is an extension of the theories of partial concept classes and the universal learning framework to multi-class classification tasks. The reviewers have found the work well-rounded and correct, and of substantial interest to the learning theory sub-community at NeurIPS. A drawback might be that this submission might appear as a natural follow up work on previously established results.
confidence: Certain
Decision: Accept