Efficient Discrepancy Testing for Learning with Distribution Shift

Summary

The paper extends the recently introduced Testable Learning with Distribution Shift (TDS) model and makes contributions in three main aspects: Universal TDS Learners, Optimal Error Guarantees via L1 Sandwiching, and Fully Polynomial-Time Testing. It presents universal TDS learners that perform well across a wide range of test distributions, achieves nearly optimal error rates by leveraging L1 sandwiching techniques, and provides efficient testing algorithms that run in fully polynomial time, particularly for intersections of halfspaces. The paper also explores the implications of these methods for various concept classes and demonstrates their application in scenarios involving distribution shifts

Strengths

- This paper extends the recently introduced Testable Learning with Distribution Shift (TDS) model by introducing Universal TDS Learners and employing L1 sandwiching techniques to achieve nearly optimal error rates. These advancements provide new methods for handling distribution shifts, particularly for intersections of halfspaces. - The theoretical foundations are robust and well-supported by detailed mathematical formulations. The use of extensive equations and rigorous proofs shows the depth of the research. - The paper is well-organized and clearly written, with each section logically building upon the previous one. Definitions, lemmas, and theorems are clearly presented, aiding in reader comprehension. - The development of efficient testing algorithms that run in fully polynomial time, especially for intersections of halfspaces, addresses significant limitations in prior work.

Weaknesses

- Lack of Experimental Validation: The paper presents extensive theoretical work but lacks empirical validation, making it difficult to assess practical performance. - Assumptions on the need for efficient implementations of the testing phase: The paper assumes that efficiency is crucial for the testing phase, especially for large pre-trained models. However, it should address how much improvement this efficiency brings to current large models and if they are substantial enough to benefit from it. - Generalization to Other Concept Classes: The focus on specific concept classes like intersections of halfspaces limits the applicability of the methods to a broader range of problems. - Clarity in Algorithm Description: The algorithm descriptions could benefit from the inclusion of pseudocode or flowcharts to enhance understanding and reproducibility.

Questions

- Can you provide evidence showing that the efficiency improvements in the testing phase are significant for current large pre-trained models, or specify at what scale of models these improvements become substantial? - Generalization to Other Concept Classes: The paper focuses on specific concept classes like intersections of halfspaces. Do you have plans or ideas for extending these methods to other concept classes? It would be helpful to understand the potential for broader application. - Clarity in Algorithm Description: The descriptions of your algorithms are mathematically detailed but could benefit from pseudocode or flowcharts. Could you provide these to enhance clarity.

Rating

7

Confidence

4

Soundness

3

Presentation

3

Contribution

4

Limitations

Yes, the authors use one section to discuss about the limitation, future work and broader impact of this paper.

Summary

Discrepancy distance is crucial in domain adaptation. The paper proposes the first set of provably efficient algorithms for testing localized discrepancy distance. This approach can generalize and improve prior work on TDS learning, and further extend to semi-parametric settings. By separating learning and testing phases, the authors obtain algorithms that run in fully polynomial time at test time.

Strengths

1.The article is well-written with clear logic, though it could benefit from improvements in some parts. 2.The authors spent great effort delivering theorems of time and sample complexity for several fundamental concept classes: 1) Classes with Low Sandwiching Degree; 2) Non-Parametric Low-Dimensional Classes; 3) Class of balanced intersections of half spaces. 3.The paper introduces algorithms for testing that run in fully polynomial time.

Weaknesses

See the questions below.

Questions

1.Does Definition 1.1 of localized discrepancy match the one with 0-1 loss described in (Zhang et al., 2020)? 2.The abstract mentions, "Our methods also extend to semi-parametric settings and yield the first positive results for low-dimensional convex sets." However, I couldn't locate this information in the main text of the paper. 3.In line 65, it is stated, “we give the first TDS learners that are guaranteed to accept whenever the test marginal falls in a wide class of distributions that are not necessarily close to the training distribution (in say statistical distance) but, instead, share some mild structural properties.” This raises the question of why emphasis is placed on some mild structural properties over statistical distance, and what exactly these mild structural properties are. 4.In line 142, it is stated, “$\lambda$ is the standard (and necessary) benchmark for the error in domain adaptation when the training and test distributions are allowed to be arbitrary.” I would appreciate it if you provide further insights about $\lambda$. For example, considering the training and test distributions are allowed to be arbitrary, is there an upper bound of $\lambda$? [1] Zhang Y., Long M., Wang J., and Jordan M., On localized discrepancy for domain adaptation. arXiv. 2020.

Rating

7

Confidence

2

Soundness

3

Presentation

3

Contribution

3

Limitations

N/A

Summary

This paper considers the problem of designing Testable Learning with Distribution Shift (TDS learning) algorithms. Through proposed algorithms for testing localized discrepancy distance, the authors give a set of efficient TDS learning algorithms. These algorithms improves all prior work in the sense that they give optimal error rates, provide universal TDS learners and have polynomial runtime.

Strengths

This work consider the novel framework of TDS learning, under which provably efficient algorithms for learning with distribution shift for certain concept classes are introduced. This shows the high novelty of this work. From significance perspective, this work generalize beyond prior works in many aspects. Also the proofs are solid, with clearly defined notations.

Weaknesses

Although "discrepancy testing" appears in the title, the discussion for testing is relatively limited. Most of the results are given in the form of TDS learners rather than discrepancy testers. Readers need to refer to the appendix to see what is actually going on for testing. I would suggest the authors to explain their testing algorithm in more detail, and explain more intuition of why this testing may work. Also, it will be good if the authors could explain more on why their testers can induce TDS learners in section 4 and 5.

Questions

See weakness. My main questions are regarding the intuition behind your tester, and how your theorems in section 4 and 5 come from proposition 3.2.

Rating

6

Confidence

2

Soundness

3

Presentation

2

Contribution

3

Limitations

No significant limitations are stated.

Summary

The paper investigates the problem of learning under distribution shift in the recently introduced framework of testable learning with distribution shifts (TDS) [Klivans et. al. 24]. In this framework, the learner receives labeled samples from the train distribution D and unlabeled samples from the test distribution D’, and is expected to either output a hypothesis with low error on D’ or correctly identify that D’ is not equal to D when that is the case. In other words, the learner runs a test to check whether D=D’ and outputs a hypothesis with low error on D’ when the test accepts. She can abstain from outputting a hypothesis when the test rejects, but the test needs to accept whp when D=D’. This paper introduces the notion of localized discrepancy test and uses it for efficient TDS learning. The localized discrepancy test estimates the discrepancy between two distributions with respect to a fixed hypothesis which makes it efficient to compute in many cases. This is in contrast to the prior notion of (non-local) discrepancy which is computed with respect to worst pair of hypotheses within a class and is therefore significantly harder to compute. Some of the salient results from the paper are as follows. 1. The prior work by Klivan et. al. (’23) showed that any class admitting low-degree polynomial approximators in the L2 sense can be efficiently TDS learned. This paper extends this result to show that approximation in the L1 sense is enough for TDS learning, and uses this result to obtain improved algorithms for constant depth circuits. 2. Gives universal TDS learner for convex sets with low intrinsic dimension and half-space intersection. The learner is universal in the sense that the corresponding test is guaranteed to accept even when the distribution D’ is not equal to D but has mild structural properties.

Strengths

The paper makes concrete improvements over the existing work on TDS learning. It is reasonably well written.

Weaknesses

While the TDS learning model was introduced from the practical motivation of learning under distribution shifts, the results in this paper (as well as the prior work) seem to be in settings far removed from practice, often relying on strong distributional assumptions. I am unsure about the significance and relevance of these results to general machine learning researchers concerned with distribution shifts in the real world.

Questions

My main concern is regarding the practical applicability of this line of work. While practical applicability is not the goal for all the theory work, in this case, the motivating question comes from practice, so connecting back to practical usefulness seems important. Could the authors explain if they see this research helping with learning under distribution shifts in real-world situations? It's okay if this paper doesn't immediately offer practical algorithms, but if the authors can discuss how this work might eventually lead to something practically useful, I would be happy to reconsider my evaluation of the paper. I might be missing something and am willing to seriously reconsider my assessment.

Rating

6

Confidence

3

Soundness

3

Presentation

3

Contribution

2

Limitations

See the weaknesses section and the question for the authors above.

Summary

Distribution shift is a well known problem where the classifier is trained on a particular data distribution encounters an input distribution far from the training set(OOD). In such a scenario it is desirable that the model performance not degrade too much, and one way to ensure this to estimate the discrepancy of the concept class wrt to the training and test distributions in the standard manner. Reasoning over the exponentially many functions in a reasonable concept class is naturally not tractable in most cases, hence the authors define a localized variant that computes the discrepancy only over a small neighbourhood of a particular reference function. The intuition behind this is that the learned functions, are well behaved enough to be near the reference hypothesis with high probability. To make the learned models robust to distribution shifts, it is essential to have learning processes that can give discrepancy guarantees and the paper takes a step towards this by providing an optimal test for a broad class of hypotheses.

Strengths

1) the problem relaxation of localized discrepancy is original and well motivated, and is likely to influence further research in the area. 2) the examples are chosen well and make the paper easy to read 3) The paper makes a timely and significant contribution to learning with discrepancy guarantees

Weaknesses

1) Since the main claim is a polytime algorithm, in addition to various speedups in the learning process, it might be interesting to look at a toy experiments to get an idea of the performance. 2) The localized discrepancy relaxation likely does not makes sense in a few situations. This needs to be a part of the paper, along the the list of cases where the notion does work. Minor typos -- 1399 (threshol) 115 (chow)

Questions

--

Rating

7

Confidence

4

Soundness

4

Presentation

4

Contribution

3

Limitations

NA