1. A lower bound on the target-excess error is not as informative as an upper bound. Is it possible to derive an upper bound on the target-excess error under appropriate conditions?
It seems that there might have been a misunderstanding on the reviewer's side: we actually provide matching upper-bound (Theorem 4.6 in Section 4.8), and even more so, show that the bound can be achieved adaptively, i.e., with no prior knowledge of the discrepancy between distributions. Together with the lower-bound, our results therefore establish information-theoretic limits for the problem. We emphasize that the lower-bound in fact holds very generally, against any hypothesis class (of VC $\geq$ 3), and any value of the discrepancy (transfer-exponent) and therefore tightly captures the problem.
2. The algorithm requires knowledge of the VC dimension.
We first note that the assumption of known VC is common in theoretical works and in fact we know very few results where such an assumption is not made. This is because, the exact VC or an upper-bound thereof is known for many of the common hypothesis classes encountered in the theoretical literature, e.g., linear to polynomial classes, classification trees, fixed architecture Neural networks, etc.
However, we agree with the reviewer that in practice, we might not know the tightest upper-bound for a given choice of models, and theory works on uniform concentration then prescribes the use of notions such as Empirical Rademacher Complexity (ERC) which may be estimable in principle (but often not practical). All our upper bounds hold also under ERC (this is evident in our concentration arguments), and we will make sure to emphasize this.
3. The notation in inequality (4.1) is a little redundant. Since $h^*_{S,\alpha}$ is a solution to the source problem... there is no need to use the max function.
It appears that the reviewer must have missed a nuance in the definition; the notation is not actually redundant: $h^*_{S,\alpha}$ is the best classifier among $\mathcal{H}_{\alpha} = \\{h\in \mathcal{H}: R_0(h)\leq \alpha\\}\$.
However, in the definition, $h$ belongs to a larger class, namely $ \mathcal{H}_{\alpha+r} =\\{h\in \mathcal{H}: R_0(h)\leq \alpha+r\\}$. Hence, the difference of the risks can be negative.
4. The theoretical results mainly rely on the previous techniques.
Neyman-Pearson classification, as discussed in the first part of the paper, is inherently different from traditional classification. Already, as argued in the first set of results, widely differing distributions may admit the same optimal classifiers (see Section 3).
More generally, while some of the tools may appear similar, the analysis requires fundamentally different approaches. For instance a main difficulty arises from the fact that excess risks could be negative as explained above, due to the fact that a learner may operate on a different subset $\mathcal{H}_{a+r}$ of $\mathcal{H}$ since it can only estimate $\mathcal{H}_a$ from data.
5. There is no experiment.
We refer the reviewer to our answer to a similar question by Reviewer 3fJQ (question 2). Namely, we do not claim to propose a new procedure. Rather the procedure is of a theoretical nature and mainly serves to establish that the lower-bound of Theorem 4.4 is attainable in principle, even without prior knowledge of distributional conditions. We re-emphasize that our main aim in this work is theoretical, and is to shed some needed insights on the limits of performance in outlier transfer.
Questions:
There are several typos:
Thanks for bringing the typos to our attention. We fixed them and uploaded a revised version.