We thank you for your efforts in taking the time to read and review our paper. We are very happy to read your positive and supportive feedback, regarding the strength, significance, and presentation of this work.

We answer questions raised in the review below:

Section 4.1:

We appreciate your feedback regarding section 4.1. We agree that this subsection is particularly dense and throws a lot of notation at the reader, and we will definitely use some of the extra space in the camera-ready version to add explanations of the various quantities and an earlier description of the overall behavior of the algorithm. We are striving to make this work readable by a broad audience, and really appreciate your feedback helping us achieve that goal.

Theorem 3:

You are correct that both Theorems 1 and 3 have no dependence on P except $\beta$. In other words, this is a minimax analysis where $\beta$ is the only parameter constraining the family of distributions in the ``max''.

A simple example:

For the example you mentioned, if we suppose $\mathbb{C}$ is the set of linear classifiers $x \mapsto \text{sign}(\langle x,w\rangle)$ on $\mathbb{R}^d$, where $P(Y=\text{sign}(\langle X,w^\star \rangle)|X) = 1-\epsilon(X) \in [1/2,1]$ for some $w^\star$, then the VC dimension is $d$, the star number is $\infty$, and $\beta = \mathbb{E}_X[\epsilon(X)]$ under the marginal $P_X$ of $X$ (e.g., this could be Gaussian or anything). Plugging these values into the theorem provides the guarantee. (in fact, in this scenario, under an origin-centered spherical Gaussian distribution, one can show that the lead term in the bound is sharp for a choice of $\epsilon(x)$ that gets close to $1/2$ near the decision boundary of the $w^\star$ classifier) We will include some illustrative examples like this in the final version.

Running time:

For simple concept classes (where the VC dimension $d$ is considered a constant), the optimizations can typically be performed in polynomial time in the sample size $m$, as the algorithm can simply consider a subset of $O(m^d)$ concepts witnessing all possible classifications of the $m$ examples. For instance, for $\mathcal{X} = \mathbb{R}$ and $\mathbb{C}$ as the class of "interval concepts" $[a,b]$, the algorithm need only consider the concepts whose endpoints $a,b$ are at data points, so just $O(m^2)$ concepts; the optimization steps can then simply search over this polynomial-size subset of concepts to find the solutions in polynomial time (in this case, naively $O(m^7)$ time, or $O(m^5)$ if we're a little clever in the optimization for $\hat{h}_k$).

More generally, beyond such simple cases, agnostic learning (even passively) is known to be computationally hard (cryptographic hardness is known, even for linear classifiers, and NP-hardness for proper learners). However, there are natural routes toward converting the algorithmic principles in this work into practical methods. In appendix G, we discuss one possible route, involving relaxations of the non-convex optimization problems with convex optimization problems via appropriate uses of convex surrogate loss functions. (see the response to reviewer qnfZ for further discussion on this)

We thank you for your efforts in taking the time to read and review our paper, and we appreciate your positive remarks regarding the novelty of the ideas in this work.

We address specific questions raised in the review below.

The star number:

We chose to present Theorem 1 first (which is expressed purely in terms of the VC dimension), before introducing any other complexity measures, to avoid any confusion regarding the role of the star number. To be clear, the conclusion that the dominant term in the query complexity of active learning is smaller than the sample complexity of passive learning holds for every concept class, regardless of whether the star number is finite or not. As your comment suggests, it is true that Theorem 1 already provides the sharpest possible bound for most interesting concept classes. However, Theorem 3 offers a nearly-sharp bound for every concept class, offering a more complete picture of the optimal lower-order term for all classes. Both bounds are the same in the dominant term, so the distinction is only in the lower-order term, and hence this has no bearing on the qualitative conclusions of this work: active learning can improve over passive learning for every concept class in the non-realizable case.

Practicality / empirical evaluation / computational complexity:

The focus of this work is in developing new algorithmic principles for active learning, and identifying the optimal first-order query complexity for all concept classes. This was a challenging problem, which took 20 years to solve. Having resolved this question, a further step will be to develop practical methods inspired by the principles we have identified. This follows a familiar pattern in statistical learning theory. Initial work identifying algorithmic principles is often impractical at first, but may later evolve into practical learning methods. For instance, the work of Vapnik and Chervonenkis in the 60s and 70s on passive learning identified the principle of empirical risk minimization and the fundamental role of the VC dimension in characterizing the sample complexity, but does not have a direct practical implication due to the 0-1 loss being computationally challenging to optimize; only later, when combined with the idea of surrogate losses to relax the non-convex 0-1 loss to a convex loss, did we arrive at practical passive learning methods (for which we may recover theoretical guarantees under assumptions relating the minimizer of the surrogate loss to that of the 0-1 loss, based on the theory of Bartlett, Jordan, & McAuliffe 2006). A similar line has been followed in the active learning literature. While the initial methods for disagreement-based agnostic active learning (e.g., the A^2 algorithm of Balcan, Beygelzimer, & Langford 06) involved implicit direct optimizations of the 0-1 loss (making them infeasible to run) and provided a coarse theoretical understanding of the query complexity (via the disagreement coefficient analysis of Hanneke 07), only later were these methods made practical by identifying appropriate ways to replace the optimization problems implicit in the technique with convex problems (e.g., by Beygelzimer, Dasgupta, & Langford 2009, Hanneke 2014, Hanneke & Yang 2019), recovering the theoretical guarantees under assumptions relating the minimizer under the convex surrogate loss to that of the 0-1 loss. Following this line, a natural next step for the present line of work (mentioned in appendix G) is to investigate ways to replace the various optimization problems involved in the AVID algorithm with appropriate convex relaxations, while still preserving the sharp theoretical guarantees of this work under appropriate assumptions on the surrogate loss. (more on this below).

Regarding the specific practical issue of computational complexity: for simple concept classes (where the VC dimension $d$ is considered a constant), the optimizations can typically be performed in polynomial time in the sample size $m$, as the algorithm can simply consider a subset of $O(m^d)$ concepts witnessing all possible classifications of the $m$ examples. For instance, for $\mathcal{X} = \mathbb{R}$ and $\mathbb{C}$ as the class of "interval concepts" $[a,b]$, the algorithm need only consider the concepts whose endpoints $a,b$ are at data points, so just $O(m^2)$ concepts; the optimization steps can then simply search over this polynomial-size subset of concepts to find the solutions in polynomial time.

More generally, beyond such simple cases, agnostic learning (even passively) is known to be computationally hard (cryptographic hardness is known, even for linear classifiers, and NP-hardness for proper learners). However, there are natural routes toward converting the algorithmic principles in this work into practical methods. In appendix G, we discuss one possible route, involving relaxations of the non-convex optimization problems with convex optimization problems via appropriate uses of convex surrogate loss functions. Such practical modifications have been studied theoretically for both passive learning (Bartlett, Jordan, & McAuliffe 2006) and disagreement-based active learning (Hanneke 2014, Hanneke & Yang 2019), and in future work we plan to explore whether there are appropriate variations of the AVID algorithm from the present work which make use of surrogate losses to obtain a computationally efficient method (preserving the sharp query complexity guarantees, under standard assumptions regarding alignment of the surrogate loss minimizer and the 0-1 loss minimizer, as adopted in the aforementioned prior works on surrogate losses). We remark that this is not merely a matter of running essentially the same algorithm with a different loss function (as discussed in section 6.6 of Hanneke 2014, active learning can be unhelpful for optimizing a convex loss, so the surrogate loss should be used more-carefully as a mere computational tool, not an overall objective to be optimized). This approach is made even more challenging in the technique developed in this work, due to the use of improper learners and even more-so due to the maximization in Steps 5 and 6. One speculative strategy we are currently exploring is that it might be possible to approximate this maximization by solving two minimization problems with different weightings of the data to "push apart" the two minimizers (i.e., in the training set of the second function, we could weight higher the examples where the first function is wrong, to force the two functions to have diverse error regions, which is the main property we require of them); if this can be made to work, it would require significant changes to parts of the proof, but we are currently trying to work with this idea as a follow-up work.

We thank you for your efforts in taking the time to read and review our paper. We are very happy to read your positive and supportive feedback, regarding the significance, innovation, and presentation of this work.

We answer specific questions raised in the review:

Clarity:

We truly appreciate your feedback regarding mindfulness of the conceptual background needed to understand the various quantities. We are striving to make this work readable by a broad audience, and will take your comments to heart when making use of the additional page allowed in the camera-ready version.

Proper learning:

We find it an important question to determine whether the algorithm can be made proper (and we mention this in appendix G). We have thought deeply about this question, but could not reach a conclusion one way or the other (yet). While we can show the return case in Step 9 can return any element of $V_N$, the other return case, in Step 4 (the early stopping case) is quite a bit more tricky, as the returned improper hypothesis is actually better than the best-in-class concept (Lemma 17); it is unclear how to replace this improper hypothesis with a concept in the class, since at that stage we do not have a good enough resolution in $\epsilon_k$ to identify a good concept in the class, so a proper learner simply cannot have such an early stopping case. We intend to continue exploring this question in future work.

Computational complexity:

The focus of this work is in developing new algorithmic principles for active learning, and identifying the optimal first-order query complexity for all concept classes. This was a challenging problem, which took 20 years to solve. Having resolved this question, a further step will be to develop practical methods inspired by the principles we have identified. This follows a familiar pattern in statistical learning theory. Adopting the abstract perspective of working with general VC classes helps to identify the essential algorithmic principles. Then in subsequent work, focusing on more specialized scenarios, those algorithmic principles may inspire practical efficient methods. In appendix G, we discuss one possible route, involving relaxations of the non-convex optimization problems with convex optimization problems via appropriate uses of convex surrogate loss functions. Such practical modifications have been studied theoretically for both passive learning (Bartlett, Jordan, & McAuliffe 2006) and disagreement-based active learning (Hanneke 2014, Hanneke & Yang 2019), and in future work we plan to explore whether there are appropriate variations of the AVID algorithm from the present work which make use of surrogate losses to obtain a computationally efficient method (preserving the sharp query complexity guarantees, under standard assumptions regarding alignment of the surrogate loss minimizer and the 0-1 loss minimizer, as adopted in the aforementioned prior works on surrogate losses). This approach is made more challenging in the technique developed in this work, due to the use of improper learners (see above), and even more-so due to the maximization in Steps 5 and 6. One speculative strategy we are currently exploring is that it might be possible to approximate this maximization by solving two minimization problems with different weightings of the data to "push apart" the two minimizers (i.e., in the training set of the second function, we could weight higher the examples where the first function is wrong, to force the two functions to have diverse error regions, which is the main property we require of them); if this can be made to work, it would require significant changes to parts of the proof, but we are currently trying to work with this idea as a follow-up work.

We thank you for your efforts in taking the time to read and review our paper. We appreciate your positive remarks regarding the significance of the advances in this work, and the quality of presentation.

We address specific comments raised in the review below.

Overparameterized models:

The extension of the theory of active learning to overparameterized models is a very interesting and important topic for future work. It is unclear whether we should really interpret the overparameterized regime as the "realizable case", since it does not necessarily admit zero population error rate (without making strong assumptions), but rather the model is complex enough (growing with sample size) to fit the training data well. As such, the techniques in this work may still be relevant even in this case. We intend to explore in future work whether the AVID principle has implications for more specialized scenarios, including overparameterized and nonparametric learning. For instance, as one speculative idea, it may be the case that the technique of isolating the "high variance" regions where two low-error classifiers disagree can instead be identified by training two predictors on independent data sets and isolating the region where these predictors disagree, and training another predictor on additional data queried in this region. This is a possibility we intend to explore in future work.

We also remark that even overparameterized passive learning has only been understood theoretically in highly specialized scenarios, under distributional assumptions. In contrast, in this work we aim for a broad general theory, applicable to any concept class, with no distribution restrictions, so the aims are quite different. Nonetheless, there have been some works on active learning with neural networks in overparameterized and nonparametric regimes (e.g., by Nowak and others), and a factor of disagreement coefficient appears in some of those bounds (e.g., Zhu & Nowak 2022), so it is natural to wonder whether the AVID principle can again help reduce the query complexity by the factor of disagreement coefficient (as it does in the present work), and we intend to follow up this work by investigating this question.

Practicality / empirical evaluation:

The focus of this work is in developing new algorithmic principles for active learning, and identifying the optimal first-order query complexity for all concept classes. This was a challenging problem, which took 20 years to solve. Having resolved this question, a further step will be to develop practical methods inspired by the principles we have identified. This follows a familiar pattern in statistical learning theory. Initial work identifying algorithmic principles is often impractical at first, but may later evolve into practical learning methods. For instance, the work of Vapnik and Chervonenkis in the 60s and 70s on passive learning identified the principle of empirical risk minimization and the fundamental role of the VC dimension in characterizing the sample complexity, but does not have a direct practical implication due to the 0-1 loss being computationally challenging to optimize; only later, when combined with the idea of surrogate losses to relax the non-convex 0-1 loss to a convex loss, did we arrive at practical passive learning methods (for which we may recover theoretical guarantees under assumptions relating the minimizer of the surrogate loss to that of the 0-1 loss, based on the theory of Bartlett, Jordan, & McAuliffe 2006). A similar line has been followed in the active learning literature. While the initial methods for disagreement-based agnostic active learning (e.g., the A^2 algorithm of Balcan, Beygelzimer, & Langford 06) involved implicit direct optimizations of the 0-1 loss (making them infeasible to run) and provided a coarse theoretical understanding of the query complexity (via the disagreement coefficient analysis of Hanneke 07), only later were these methods made practical by identifying appropriate ways to replace the optimization problems implicit in the technique with convex problems (e.g., by Beygelzimer, Dasgupta, & Langford 2009, Hanneke 2014, Hanneke & Yang 2019), recovering the theoretical guarantees under assumptions relating the minimizer under the convex surrogate loss to that of the 0-1 loss. Following this line, a natural next step for the present line of work (mentioned in appendix G) is to investigate ways to replace the various optimization problems involved in the AVID algorithm with appropriate convex relaxations, while recovering the sharp theoretical guarantees of this work under appropriate assumptions on the surrogate loss. This is a nontrivial extension (as was the case for disagreement-based methods, as discussed in section 6.6 of Hanneke 2014), and will require significant further research. We have been thinking deeply about this question, and aim to develop such an extension in future work (more discussion of this in our reply to reviewer qnfZ).