Efficient Discrepancy Testing for Learning with Distribution Shift

We wish to thank the reviewer for their constructive feedback and for appreciating our work.

• The fully polynomial-time testers we propose in this work apply to the class of balanced halfspace intersections. There are two important implications of our results related to current large pre-trained models: (1) we can experimentally evaluate our proposed efficient testers through applying them to the last layers of large networks, since the last layers correspond to simple classes like halfspaces or halfspace intersections and (2) our localized discrepancy tester for halfspace intersections demonstrates that fully polynomial-time discrepancy testing is possible, even for classes for which there is no known fully polynomial-time provable learning algorithm. The second implication motivates further study of the localized discrepancy testing problem for more complex concept classes, like deep neural networks.

• We agree with the reviewer that generalizing our results to broader concept classes is an interesting open direction. That said, our results capture several fundamental concept classes like constant-depth circuits, low-degree PTFs (see Table 1), low-dimensional convex sets (section 4) and halfspace intersections (section 5). As mentioned above, TDS learning of these classes can also be useful for neural networks, since the last layers typically correspond to some simpler class. Moreover, our work hints at potential end-to-end extensions to other classes by extracting the exact properties we used to obtain our results (see for example Remark 5.4 and lines 394–400).

• Due to space limitations, we only provided pseudocode for our algorithms in the appendix (see Algorithms 1,2 and 3). Given the additional space for the camera-ready version, we will consider adding some pseudocode in the main paper for clarity. We can also add pseudocode for the boundary proximity tester in Appendix E.

We wish to thank the anonymous reviewer for their feedback.

1. Our Definition 1.1 is a generalization of the localized disparity discrepancy w.r.t. 0-1 loss as described in (Zhang et al., 2020). In particular, they use a specific notion of neighborhood (which corresponds to the disagreement neighborhood of definition E.2 we define in the appendix). However, we can also define the localized discrepancy with respect to other notions of neighborhood, like the global neighborhood (see definition C.2) or the subspace neighborhood (see definition D.2). Different notions of neighborhood correspond to different localized discrepancy testers.

2. For the results on semi-parametric classes see section 4, where we propose TDS learners for low-dimensional convex sets (which is a semi-parametric class of functions).

3. Line 65 emphasizes that our testers will certify low test error even in the presence of large amounts of distribution shift, as long as the distribution shift is benign in the sense that the test distribution is structured. The appropriate structural properties are described in lines 273–275 for Theorem 4.2 and in lines 324–326 for Theorem 5.1 and essentially correspond to (1) an upper bound on the fourth moment and (2) anti-concentration. In other words, while distributions with small statistical distance look similar, our testers will accept distributions that are very different from the training distribution, as long as they satisfy some structural properties.

4. The error parameter $\lambda$ encodes the relationship between the training and test labels. It is small when there is some classifier $f^*$ in the given concept class that has both low training and low test error, i.e., both the training and the test labels are approximately generated by $f^*$. Conversely, if the test labels are opposite from the training labels, $\lambda$ will always be $1$. Since there are no test labels available, we cannot hope for an error guarantee better than $\lambda$ (see proposition 1 in [KSV’24]).

[KSV’24] Adam R Klivans, Konstantinos Stavropoulos, and Arsen Vasilyan. Testable learning with distribution shift. The Thirty Seventh Annual Conference on Learning Theory, 2024

We thank the reviewer for their feedback.

We would like to clarify that we propose 3 different discrepancy testers, one for each of the sections 3, 4 and 5 (see proposition 3.2, appendix D.1 and appendix E1). The relevant discussion can be found in lines 103–109 and high-level descriptions for the three testers can be found in lines 110–116 (for chow matching tester), lines 117–123 (for cylindrical grids tester) and lines 124–130 (for boundary proximity tester). Moreover, in lines 285–316 we provide the intuition behind the cylindrical grids tester (used for the results of section 4) and in lines 354–378 we provide the intuition behind the boundary proximity tester (used for the results of section 5).

Due to space limitations, we had to move formal statements regarding our discrepancy testers in the appendix, but, given the additional space of the camera ready version, we will add some more details in sections 4 and 5 accordingly.

Moreover, to avoid confusion, we will explicitly state in section 1.2 that we propose three different testers.

We are happy to provide further clarifications regarding the testers of sections 4 and 5 if the reviewer has any questions not addressed in lines 285–316 and lines 354–378.

Thanks for your question about "strong assumptions". The goal of this line of work is precisely to remove the strong assumptions inherent in all prior work in the fields of distribution shift and domain adaptation. More precisely, all prior work requires an assumption on both the train distribution D and test distribution D’, as it requires the discrepancy distance between D and D’ to be small to obtain meaningful generalization bounds. Instead, we are able to come up with the first efficient algorithms to test a (localized) version of this quantity, without taking any assumptions on D’. Additionally, we can remove assumptions on D as well by combining our work with so-called testable learning algorithms (effectively we can test the assumptions we need for D and reject if they are not satisfied). Finally, it is possible to relax the assumptions we take on D to say bounded distributions, which is quite reasonable to assume in practice (this observation will appear in forthcoming work).

Let us further explain why we think taking an assumption on D– the training distribution– is practically reasonable: consider the following now extremely common scenario: someone trains a foundation model on a labeled data set. In this scenario, the learner has a lot of control over the training set; for example, in the health or bio domains the training data can be subsampled from large databases to satisfy various properties. What we want to avoid is making an assumption about an unseen test set, as it may come from a radically different distribution. The recent line of work on TDS learning and this paper in particular actually give efficient algorithms with meaningful guarantees in this scenario, whereas all prior work requires an assumption on some notion of distance between D and D’ that cannot be efficiently verified.

Another practical example: assume we have built a foundation model and wish to determine if it will perform well on a new unseen test set. We can view the last layer of this network as a linear classifier with respect to a distribution of weights on the next to last layer of the network. We can even verify certain properties of this distribution (such as boundedness). Then determining if this foundation model will succeed is precisely a TDS learning problem as described in the submission.

Our work, in particular, makes three important contributions towards more practically relevant algorithms, by giving TDS learners that: (1) can handle more classes (i.e., degree-2 PTFs, constant-depth circuits and convex sets), (2) accept more often, since they are guaranteed to accept wide classes of benign distribution shifts (see the universal TDS learners of Theorems 4.2 and 5.1) and (3) run in fully polynomial time at test time, even for classes for which no fully polynomial learning algorithms are known (see section 5).

To summarize, we have removed the onerous assumptions prior work made on both the train and test distributions and have given a path forward for new efficient algorithms to determine if a foundation model will succeed on unseen test sets. We therefore feel these ideas will have a major practical impact. Distribution shift is certainly one of the most critical issues for trustworthy ML.

We wish to thank the reviewer for their comments and for appreciating our work.

• We agree that experimental evaluation of our algorithms would be interesting, but we believe that a thorough, dedicated evaluation would be preferable and more suitable for future work, since the scope of this paper is theoretical.

• The appropriate localized discrepancy relaxation of the testing phase depends on the guarantees one can ensure during training. For example, if the training algorithm is guaranteed to approximately recover the relevant subspace (see Theorem D.13), then testing the localized discrepancy with respect to the subspace neighborhood (see Definition D.2) is appropriate. We refer the reviewer to lines 103–109 for a relevant discussion and lines 110–130 for examples of the appropriate relaxation in different scenarios. We will clarify this point in future revisions.