Improved Sample Complexity for Multiclass PAC Learning

Thank you for reviewing our paper. Below, $d$ denotes DS dimension and $d_k$ denotes $k$-DS dimension.

List learning

• The advantage of reducing to list learning is that it reduces the original problem to an easier problem: list learning is easier than multiclass learning. Indeed, a multiclass learner is a list learner of any size. If a concept class is PAC learnable with some sample complexity, then it is also $k$-list PAC learnable with the same sample complexity for any size $k$. On the contrary, for any $k\ge2$, we cannot directly obtain a multiclass learner from a general $k$-list learner. If a concept class is $k$-list PAC learnable with some sample complexity, it is unclear whether it is multiclass PAC learnable and what its multiclass sample complexity is. As mentioned in line 285 (there is a typo, it should be "$\mathsf{dim}_k(\mathcal{H})\ge$'' instead of "$\mathsf{dim}_k(\mathcal{H})>$''), $d_k(\mathcal{H})$ is nonincreasing with $k$. Consequently, a $k$-list PAC learnable concept class (i.e., $d_k(\mathcal{H})<\infty$) is not necessarily multiclass PAC learnable. Thus, Theorem 2.7 and 2.11 are highly non-trivial because they reduce the harder problem of multiclass learning to the easier problem of list learning: quantitatively, if a concept class is $k$-list learnable with some error rate $r(n)$, it is also multiclass learnable with an error rate bounded by $r(n)+d\log(k)/n$.

• Regarding $\mathcal A_{\text{goodlist}}$, if there is a multiclass learner $A$ with error rate bounded by $f(d)/n$, then $A$ is also a $k$-list learner with $\epsilon_{A,\mathcal{H}}(n)\le f(d)/n$ for any $k\in\mathbb{N}$. Thus, our conjecture on list learners holds if the conjecture of the same rate on multiclass learners holds, indicating that the conjecture for such a list learner is weaker than that for a multiclass learner, hence more approachable. Moreover, in Theorem 2.10, our list learner already saves a log factor compared to the previous best list learner in [1]. It is reasonable to conjecture the removal of the remaining log factor.

• The fact that we reduced a log factor in the upper bound of multiclass sample complexity by reducing to list learning also shows its advantage. The improvement of log factors in PAC sample complexity is significant; e.g., in binary classification, though the upper bound with a $\log(1/\epsilon)$ factor was established in 1982 [2], the log factor was not removed until 2016 [3]. Given that we reduced multiclass learning to an easier problem of list learning and thus removed a log factor, we believe our paper has made a significant contribution to multiclass learning.

• Finally, with a large or infinite label space, it is natural to consider reducing the size of the label space by proposing a list learner. This idea has been adopted in [1], the first paper to establish the equivalence of multiclass PAC learnability and the finiteness of DS dimension. [1] proposed a list learner to construct a list sample compression scheme and built their multiclass learner using the labels in the list.

Lower bound

One cannot derive the $\Omega((d_k-\log\delta)/k\epsilon)$ bound using the $\Omega(d_k/kn)$ expected error lower bound in [4] as a black box since one must stick to the distribution constructed for the lower bound when applying it as a black box. Thus, for the PAC lower bound, we have to construct different hard distributions from that in [4] for both the $\log(1/\delta)/k\epsilon$ (line 486) and the $d_k/k\epsilon$ (line 511) terms. The detailed constructions are provided in the proof of Theorem 2.5 in Appendix B. To list one difference between our constructions and that in [4], our distributions are not uniform over the $\mathcal{X}$ sequence selected and depends on the parameter $\epsilon$, while theirs are uniform over the $\mathcal{X}$ sequence selected.

Finally, our major contribution is the upper bound. We include the lower bound and its proof for comparison and completeness as it is missing in the literature (see line 37 and 124).

Presentation

• We provided the reference [1, Fact 14] of the leave-one-out argument in line 102 where it first appears. We have added the reference in line 236 in the revision. The current proof outlines are concise due to the space limitation, but we believe that they convey the key points of the proof. If the reviewer has other questions regarding the proof outlines, we are glad to answer in the discussion. We will extend the proof outlines to improve the readability in the revision.

• Due to the space limitation, we have to put some definitions in the appendix, but we included the references of the definitions when they appear in the main text. We will move the important definitions in Appendix A to the main text with the additional page if the paper is accepted. We believe that we have provided intuition for the definitions. We summarized the existing results in Proposition 3.1 to motivate the idea of upper bounding the density. In Theorem 3.2, this idea is supported by its success for classes of DS dimension 1. In line 329-335, we explained the reason of considering the pivot of a concept class. In line 346-352, we provided the intuition of pivot shifting and compared it to the standard shifting in the literature. Lemma 3.7 explained the partial validity of pivot shifting, which naturally leads to Open Question 2 about the remaining validity of pivot shifting in upper bounding the density using DS dimension. We have added more explanations in words for the technical definitions to improve the readability in the revision.

[1] Brukhim et al. A characterization of multiclass learnability. 2022.

[2] Vapnik. Estimation of Dependencies Based on Empirical Data. 1982.

[3] Hanneke. The Optimal Sample Complexity of PAC Learning. 2016.

[4] Charikar and Pabbaraju. A characterization of list learnability. 2023.

Thank you for raising your rating. We will further elaborate on the technical aspects of the paper and improve its readability.

Thank you for reviewing our paper. We appreciate your positive feedback. First, we need to emphasize that in this paper, we study multiclass PAC sample complexity for general concept classes which can have infinite number of labels ($|\mathcal{Y}|=\infty$). Our results hold for general concept classes independent of the number of labels. Below, $d$ denotes DS dimension, $d_N$ denotes Natarajan dimension, and $d_G$ denotes graph dimension.

Graph dimension and Natarajan dimension

• As we have stated in line 26-28, [1] showed that a concept class is PAC learnable if and only if its DS dimension is finite. Moreover, as is detailed below, it has been shown in the literature that finite graph dimension or Natarajan dimension does not characterize multiclass PAC learnability.

• For the graph dimension, [2, Section 6] showed that finite graph dimension does not characterize multiclass PAC learnability by identifying a PAC learnable class with infinite graph dimension and infinite label space. [3, Example 1] provided a family of concept classes whose graph dimensions can be any positive integers or infinite, and all those concept classes are PAC learnable with sample complexity $\log(1/\delta)/\epsilon$. [1, Example 8] is a concept class with DS dimension 1 (thus it is PAC learnable), infinite graph dimension, and infinite label space.

• For the Natarajan dimension, [1, Theorem 2] provided a concept class with Natarajan dimension 1 and infinite DS dimension (thus it is not PAC learnable).

• Thus, graph dimension and Natarajan dimension cannot appear in the optimal PAC sample complexity. In general, for $\mathcal{H}\subseteq \mathcal{Y}^{\mathcal{X}}$, we have $d_N(\mathcal{H})\le d(\mathcal{H})\le d_G(\mathcal{H})$ [4] and for the special case of $|\mathcal{Y}|<\infty$, $d_G(\mathcal{H})\le 5\log_2(|\mathcal{Y}|)d_N(\mathcal{H})$ [3]. Quantitative scaling between those dimensions for general concept classes is still missing, and as is discussed above, there exist $\mathcal{H}$ and $\mathcal{H}'$ such that $d_N(\mathcal{H})=1$, $d(\mathcal{H})=\infty$, $d(\mathcal{H}')=1$, and $d_G(\mathcal{H}')=\infty$.

• For detailed comparisons, our lower bound in eq. (2) is better than the best lower bound in terms of Natarajan dimension in [3, Theorem 5], and the Natarajan dimension cannot upper bound the PAC sample complexity of general concept classes by [1, Theorem 2] discussed before. The graph dimension cannot lower bound the PAC sample complexity of general concept classes by the above examples of PAC learnable concept classes with infinite graph dimensions. The best upper bound in terms of the graph dimension is $O((d_G(\mathcal{H})+\log(1/\delta))/\epsilon)$ by Proposition I.5 of our paper (see also line 226), which can be infinite for PAC learnable concept classes by the examples discussed before. Moreover, by [3, Example 1], there exists $\mathcal H_i$ for all $1\le i\le\infty$ such that $d_G(\mathcal H_i)=i$ and $\mathcal{M}_{\mathcal{H}_i}(\epsilon,\delta)\le \log(1/\delta)/\epsilon$, indicating that their DS dimensions are uniformly bounded in terms of $i$. Thus, the optimal upper bound cannot depend on graph dimension, and the upper bound using graph dimension can be arbitrarily worse than our upper bound using DS dimension as our upper bound is always non-trivial with a finite gap of at most $\sqrt{d}\log(d)\log(d/\epsilon)$ from the optimal bound for PAC learnable concept classes.

Number of classes

• As mentioned before, our upper and lower bounds on multiclass PAC sample complexity are independent of the number of classes which can be infinite. We actually prove the following result. There exists an algorithm $A$ and universal constants $C_1,C_2>0$ such that for any feature space $\mathcal{X}$, label space $\mathcal{Y}$ ($|\mathcal{Y}|$ can be arbitrarily large or infinite), and concept class $\mathcal{H}\subseteq\mathcal{Y}^{\mathcal{X}}$, we have $\mathcal M_{\mathcal{H}}(\epsilon,\delta)\ge C_1({d+\log(1/\delta)})/{\epsilon}$ and $\mathcal{M}_{A,\mathcal{H}}(\epsilon,\delta) \le C_2({d^{3/2}\log(d)\log(d/\epsilon)+\log(1/\delta)})/\epsilon$. As we have listed above, there are many concept classes with infinite label space and finite DS dimension. Actually, by taking finite levels in the tree example in [1, Figure 3], we can construct a series of concept classes with DS dimension 1 and number of labels increasing to infinity. Thus, any bound that increases to infinity with the number of labels cannot be optimal and is worse than our upper bound for general concept classes. It follows that the optimal bound must be uniformly bounded with respect to the number of labels and the number of labels should not exist in the optimal bound.

We will incorporate the key points in the above discussion in the revised version of the paper.

[1] Brukhim et al. A characterization of multiclass learnability. FOCS 2022.

[2] Natarajan. Some results on learning. 1989.

[3] Daniely et al. Multiclass learnability and the ERM principle. JMLR, 2015.

[4] Daniely and Shalev-Shwartz. Optimal learners for multiclass problems. COLT 2014.

Thank you for reviewing our paper. We appreciate your positive feedback. We provided a proof sketch for Theorem 2.7 in line 229-241. We will elaborate more on it and include the proof intuition for other major theorems in the revision. We believe that the extra space can be accounted for by the additional page allowed if the paper is accepted.

Thank you for reviewing our paper. We appreciate your positive feedback. We will include the proof sketches and high-level intuitions of the results presented in the Appendix in the revised version of the paper.

Thank you for reviewing our paper. Below, $d$ denotes DS dimension and $d_G$ denotes graph dimension.

Graph dimension

• The DS dimension is the right quantity to look at here. The optimal multiclass PAC sample complexity is described by DS dimension and not by graph dimension. As is stated in line 26-28, [1] showed that a concept class is PAC learnable if and only if its DS dimension is finite. [2, Sec. 6] showed that finite graph dimension does not characterize PAC learnability by proposing a PAC learnable class with infinite graph dimension. [3, Example 1] provided a family of concept classes $\mathcal H_i$ for all $1\le i\le\infty$ such that $d_G(\mathcal H_i)=i$ and $\mathcal M_{\mathcal{H}_i}(\epsilon,\delta)\le \log(1/\delta)/\epsilon$, indicating that their DS dimensions are uniformly bounded. [1, Example 8] is a concept class with DS dimension 1 (thus it is PAC learnable) and infinite graph dimension. Thus, graph dimension cannot appear in the optimal multiclass PAC sample complexity.

• By the above examples, graph dimension cannot lower bound the PAC sample complexity of general concept classes. The best upper bound using graph dimension is $O((d_G(\mathcal{H})+\log(1/\delta))/\epsilon)$ by our Proposition I.5 (see also line 226), which can be infinite for PAC learnable classes. By [3, Example 1], the optimal upper bound cannot depend on graph dimension, and the above upper bound can be arbitrarily worse than our upper bound using DS dimension as our upper bound is always non-trivial with a finite gap of at most $\sqrt{d}\log(d)\log(d/\epsilon)$ from the optimal bound for PAC learnable classes.

• Moreover, Daniely and Shalev-Shwartz [4] did not provide optimal bound on PAC sample complexity in terms of graph dimension. Instead, in [4, Conjecture 11], they conjectured that the optimal bound is given by DS dimension. In the last paragraph, they wrote

it is known (Daniely et al., 2011) that the graph dimension does not characterize the sample complexity, since it can be substantially larger than the sample complexity in several cases.

We will include the key points in the above discussion in our revision.

Technical summary

We believe that it is necessary to include enough technical summaries to introduce results and ideas. We made efforts on providing sufficient motivation of the technical summaries. For example, in Sec. 1, we reviewed existing results in multiclass PAC learning in the first two paragraphs, motivating the introduction of the concepts in PAC learning in Sec. 1.1. In paragraph 3 of Sec. 1, we previewed our reduction to list learning, motivating the technical summary of list learning. In paragraph 4 of Sec. 1, we provided the motivation of the pivot shifting in Sec. 3. In Sec. 2.2, after the main result, we provided a technical overview in line 229-241 to explain the key points of the proof. In Sec. 2.3, we provided the intuition of Alg. 2 in the first paragraph. In Sec. 3, we built the technical summary on existing results to explain the motivation of upper bounding the density and pivot shifting. We will elaborate more on technical summary in the revision.

Comparison with previous work

We believe that our paper makes adequate comparisons with previous work. We compared our upper bound to the previous best bound (line 39 and 120) in line 49 and 288. We mentioned that a potentially sharp lower bound on PAC sample complexity is still missing in the literature in line 37 and 124. In line 244-251, we compared to the list sample compression scheme in [1] to explain how we saved a $\log(n)$ factor using sampled boosting. In line 268-271, we compared to the bound of directly invoking the learner in [1] to Alg. 2 to explain how we avoided a $\log(d)$ factor using list learning. In Prop. 3.1, we reviewed known results on density to explain the reason of bounding the density. In line 329-334, we referred to the induction technique in Haussler et al. (1994) to motivate pivot shifting. In line 348-352, we compared pivot shifting to the standard shifting technique.

Technical improvement

• We do not think that our improvement is weak. The optimal PAC sample complexity is a fundamental and difficult problem in statistical learning theory. The characterization of multiclass PAC learnability remained open for decades until recently solved by [1]. The improvement of log factors in sample complexity is highly non-trivial: e.g., in binary classification, though the upper bound with a $\log(1/\epsilon)$ factor was established in 1982 [5], the log factor was not removed until 2016 [6].

• In this paper, we focus on improving the dependence of PAC sample complexity on $\epsilon$ (equivalently, the dependence of the error rate on $n$). In learning theory, it is important to study the dependence of error rate on $n$ with $d$ fixed because a learner is typically applied to a fixed concept class with increasing $n$ so that $n$ is much larger than $d$. Moreover, by [7], our upper bound improves the universal learning rate from $\log^2(n)/n$ to $(\log n)/n$ for the concept classes studied in [7]. Ideally, we want tight dependence on each parameter. However, as tight dependence on either $d$ or $\epsilon$ is unknown, we believe it is meaningful to explore better dependence on either parameter.

• Besides the removal of a log factor, we also proposed two possible routes toward removing the remaining log factor of $\epsilon$.

[1] Brukhim et al. A characterization of multiclass learnability. 2022.

[2] Natarajan. Some results on learning. 1989.

[3] Daniely et al. Multiclass learnability and the ERM principle. 2015.

[4] Daniely and Shalev-Shwartz. Optimal learners for multiclass problems. 2014.

[5] Vapnik. Estimation of Dependencies Based on Empirical Data. 1982.

[6] Hanneke. The Optimal Sample Complexity of PAC Learning. 2016.

[7] Hanneke et al. Universal rates for multiclass learning. 2023.