Tolerant Algorithms for Learning with Arbitrary Covariate Shift

Summary

This paper studies the problem of PAC learning with covariate shift. In particular, it examines two specific learning frameworks: one is PQ learning, where a learner is allowed to "absent" from some testing samples but is required to have good accuracy for the retained samples; the other is TDS learning, where one is allowed to completely absent if the testing distribution is detected to be far from the training distribution. From a technical point of view, the paper is restricted to cases when the covariate distribution is Gaussian or uniform and when the concept class is nicely approximated by polynomials of low degree (i.e., the so-called "sandwiching" functions). The main contribution appears to extend prior results to handle arbitrary fractions of outliers and provide tighter bounds.

Strengths

While I'm not an expert in PAC learning using polynomial regression, this paper appears to provide some interesting technical results. The outlier removal algorithm introduced in Theorem 3.1 seems to be an interesting technical primitive for handling outliers in low-degree polynomial regressions. Although the settings considered in this paper are fairly restrictive, the results seem to provide a valuable step toward understanding learning with abstention in covariate shift.

Weaknesses

The main weakness of the paper, in my opinion, is the presentation. The paper is very hard to read, especially for those who are not immediately familiar with the relevant literature. I outline the following specific comments: 1. The main text as written does not provide much technical information. For example, Theorem 3.1 is supposed to be the main technical ingredient of the paper, but the proof overview provides nearly no information. Due to the limited time period of the NeurIPS review, I don't have time to delve into the technical details provided in the appendix. I suggest the authors provide a much more detailed overview in the main text. It does not necessarily need to include all the technical details, but it should provide enough information on the logical flow. Perhaps the "Comparison with [DKS18]" section can be omitted to save space? 2. The theorem statements are sometimes framed very sloppily. For example, the $\lambda$ in Theorem 4.1 was never defined (though it appears in the proof); in Lemma B.2., the sentence "we have f(x) = 0 for all x such that..." does not make sense to me, as the subsequent quantifier has nothing to do with x, referring to f(x)=0 always. Since there are too many sloppy statements like this, I lack the energy to check the details carefully. 3. The authors claim to provide "efficient learning algorithms," but all the computational complexities scale exponentially with respect to the error parameters $\epsilon$. Did I miss something? Can this parameter be selected as a constant and be boosted in some way? 4. Is there a specific reason why Theorem 3.1 is stated for the second moment? Is it due to Lemma B.1? Given these reasons, although I believe this paper has some interesting technical contributions, it would require substantial revision to be suitable for publication at NeurIPS.

Questions

See above.

Rating

6

Confidence

3

Soundness

3

Presentation

2

Contribution

2

Limitations

N/A

Summary

The authors consider the problem of efficiently learning a concept class under distribution shift, i.e. in the setting where the training data and testing data are drawn from different distributions. They study two frameworks: PQ learning and TDS learning. In the former, the learner is allowed to abstain from classifying a part of the test samples. In the latter, the learner is allowed to abstain entirely if the test distribution is 'visibly' different from the training distribution. The paper has two main contributions. First, in the PQ setting, the authors obtain the first dimensionally-efficient learning algorithms, under the assumption that the training data is nicely distributed (Gaussian or uniform on the cube) and the concept class is simple (intersection of halfspaces or low-complexity formulas). Second, in the TDS setting, under the same assumptions, they provide the first efficient algorithms that tolerate small distribution shift in TV-distance. This generalizes earlier results which only tolerate shift 'in the moments' of the distribution (which is a weaker notion). The proof of these results consists roughly of two steps. First, the authors adapt/improve an existing spectral technique for outlier-removal to show that the test data can be pruned so that it satisfies a 'low-degree spectral boundedness property', without removing too many samples. Second, they show that this spectral boundedness property suffices to apply low-degree polynomial regression to the PQ/TDS-learning problems (in certain settings). In order to do so, they rely on the notion of 'L2-sandwiching polynomials' of [KSV24b]. The important distinction w.r.t. [KSV24b] is that, there, the authors rely on a 'moment-matching property' (which is stronger than spectral boundedness, and in particular, not always satisfied even if the training and test data are close in TV-distance).

Strengths

- The paper achieves strong and novel results in an area which I believe to be of interest to the Neurips community. It falls in a line of research focussing on relaxing (or testing) distributional assumptions in algorithmic learning theory, which has recently received a lot of interest. In particular, I like that the paper goes beyond the 'moment-matching' approach of earlier works. - I find the combination of ideas from [KSV24b] and outlier removal to obtain the main results very insightful. - The paper is very well written: the key technical ideas are exposed clearly, and it is easy even for the non-expert to graps the main concepts. Furthermore, the results and some of their consequences are positioned clearly in the existing literature. Lastly, the technical background (on learning models, previous algorithms etc.) is well presented. - The work leaves open some directions for future research, and I think it is likely that its ideas will be applied to obtain future results in this area.

Weaknesses

- Arguably, much of the technical 'heavy-lifting' to obtain the results of this paper is done by the 'L2-sandwiching' of [KSV24b], and to a lesser extend the outlier removal technique of [DKS18] (which the authors do significantly improve on). - The results apply only to very simple concept classes. It would have been nice to have guarantees in more complicated settings as well, e.g. for (low-degree) polynomial threshold functions. Similarly, the distributional assumptions on the training data are quite restrictive (although it should be noted that this is not uncommon in the literature).

Questions

- l62-63: In testable learning, one does not test whether the underlying distribution is actually Gaussian (which is not possible), but rather whether it shares some important characterics with a Gaussian distributions (e.g. its low-degree moments match). I guess the word 'indirectly' is meant to allude to this distinction, but I think this phrasing could be confusing. - l111-117: It is not clear to me from this paragraph if any work on *distribution-specific* PQ-learning was done before this paper. In particular, it think it would be good to clarify if 1) this work gives the first *efficient* distribution-specific PQ algorithm (but inefficient *distribution-specific* algorithms had been considered, or 2) this work is the first to consider distribution-specific PQ-learning at all.

Rating

8

Confidence

4

Soundness

4

Presentation

4

Contribution

3

Limitations

Adequately addressed

Summary

This work proposes methods for learning under covariance shifts. In particular, it studies PQ learning and TDS learning models. It provides an algorithm based on filtering technique. Given sample access to two distributions, the algorithm produces a filter that rejects points from the second distribution which attains large values on some degree-k polynomial, and does not reject many values of the first distribution. This algorithm is then applied to learning some function classes (halfspaces and classes with low sandwiching degree) in PQ learning model and to tolerant TDS learning model. In the former model authors obtain a computationally-efficient algorithm, and in the latter an algorithm which does not reject a distribution even if there exists a small but non-negligible shift.

Strengths

1. Paper provides novel results in the PQ learning and TDS learning. Solving these learning models is important, since in practice algorithms need to perform well under covariate shifts. 2. Core algorithm of the paper is versatile, as the authors show how to apply it to multiple other learning settings (e.g. learning with nasty noise). 3. For TDS learning, prior works rejected distribution with a very small distributional shift. This work provides an algorithm which gives non-trivial results even if the distance between distributions is larger. 4. This work suggests a novel technique to bound number of iterations of their algorithm through the use of potential function. 5. The main text of the paper is well-written.

Weaknesses

I find the main weakness of the paper is the quality of the proofs in the appendix. They are often inaccurately written and require a lot of time to understand the arguments because of the typos. But it seems that there are some inaccuracies in the proofs of the core results beyond typos, which I highlight in the 'Questions' section.

Questions

My main question is about Appendix B, which I believe is crucial for the proof of all technical theorems. I find this section not carefully written with inconsistent notation and typos, which makes it hard to follow the arguments. Next, I focus on the parts which were not merely typos: 1. I do not follow equation (B.2). First of all, it should be square of the Frobenius norm. But still second and third step is unclear. Could the authors explain these steps in more detail? 2. If I understand correctly, equation (B.3) requires $2k$-tameness, instead of $k$-tameness. This is because $r_j(x)r_{j’}(x)$ are of degree $2k$. 3. Equation (B.4): I do not follow first inequality, where does first $\Delta$ come from? Since $f(x)(p(x))^2 = \sum_{j = 0}^{B / \Delta} f(x)(p(x))^2 \mathbb{I}(j\Delta \leq (p(x))^2 < (j+1)\Delta)$, we obtain that $\lvert E_{x\sim S} f(x) (p(x))^2 - E_{x\sim D'} f(x)(p(x))^2\rvert \leq \sum_j \lvert E_{x\sim S} f(x) (p(x))^2 \mathbb{I}_j - E_D f(x) (p(x))^2 \mathbb{I}_j \rvert$, and there is no additive $\Delta$? $(\mathbb{I}_j := \mathbb{I}(j\Delta \leq p(x)^2 < (j+1)\Delta)$ 4. Line 922: Can authors clarify why there exists such $\tau_i$? it seems that if I increase $\tau$, then the value on the left decreases to 0, while the value on the right stays positive? I will consider changing my score when authors address these questions.

Rating

6

Confidence

4

Soundness

2

Presentation

2

Contribution

3

Limitations

There are no ethical limitations in this work.

Summary

This paper studies two fundamental learning setups, namely PQ learning and TDS learning (Testable Learning with distribution shift), both motivated by covariate shift. In PQ learning, the algorithm is given labeled samples from $\mathcal D^{\text{train}}$ over $\mathbb R^d \times \{0, 1\}$ with marginal distribution $D$, and unlabeled samples from some test distribution $\mathcal D^{\text{test}}$ (also over $\mathbb R^d \times \{0, 1\}$). Assume that there is some common hypothesis $h$ that achieves a small error $\lambda$ under both $\mathcal D^{\text{train}}$ and $\mathcal D^{\text{test}}$, the goal of the learning algorithm is to output a selector $g: \mathbb R^d \mapsto \{0, 1\}$ and a classifier $\hat h$ such that (i) $\hat h$ achieves a small error with respect to $\mathcal D^{\text{test}}$ restricted to the acceptance region of $g$, and (ii) most samples from $D$ will not be rejected by $g$. The main contribution is an algorithm that works when (i) the marginal $D$ of $\mathcal D^{\text{train}}$ satisfies some polynomial concentration properties (including isotropic log-concave) and (ii) the hypothesis class admits $L_2$ sandwiching polynomial under $D$. In particular, it achieves a rejection rate of $\eta$ and an accuracy guarantee of $O( \lambda / \eta )$. The bounds are optimal when one sets $\eta = \sqrt{\lambda}$ to balance the rejection rate and accuracy. In tolerant TDS learning, the algorithm similarly has labeled sample access to $D^{\text{train}}$ and unlabeled sample access to $D^{\text{test}}$. In addition, the algorithm is allowed to reject $\mathcal D^{\text{test}}$ when it finds that the marginals of $D^{\text{train}}$ and $\mathcal D^{\text{test}}$ are at least $\theta$-far from each other in TV distance. The name ``tolerance'' follows exactly from the constraint that the algorithm is not allowed to reject when $D^{\text{train}}$ and $\mathcal D^{\text{test}}$ are close but not identical to each other. Their algorithm works in a setup similar to the PQ learning case and achieves a final error of $O(\lambda) + 2 \theta + \epsilon$, where $\lambda$ is the optimal error of some common hypothesis under $\mathcal D^{\text{train}}$ and $\mathcal D^{\text{test}}$ (the sum of the two errors), $\theta$ is the tolerance in TV distance, and $\epsilon$ is the error parameter. The core technique is a spectral based outlier removal procedure that resembles that from [DKS18] that performs filtering on the dataset until the $L_2$ norm of any polynomial under the empirical distribution becomes at most a constant factor of its $L_2$ norm under the reference distribution (the marginal of $\mathcal D^{\text{train}}$). However, the analysis in the current work is tighter, and in particular exhibits non-trivial guarantees even if $\mathcal D^{\text{test}}$ is very far from $\mathcal D^{\text{train}}$ in total variation distance, which is crucial in the technique's application in PQ learning. After ensuring that the spectral of the dataset is appropriately bounded, the algorithm runs polynomial regression, and its guarantees mainly follow from the existence of $L_2$ sandwiching polynomials.

Strengths

The application of spectral outlier removal in the context of distribution shift is natural and turns out to b quite powerful. The most surprising part is that the procedure works even when the TV distance between the test and the training distributions is more than $1/2$. A naive application of spectral outlier removal will not work in this case as the filter may end up removing all points from the dataset (since the standard guarantee only says that the filter remove more "bad" points than "good" points). The analysis of this work circumvents the issue, and characterizes a tradeoff between the rejection rate $\alpha$ and the final bound on the $L_2$ norm of polynomials. This makes PQ learning possible even when the TV distance between $\mathcal D^{\text{train}}$ and $\mathcal D^{\text{test}}$ approaches $1$ (albeit with a cost of having larger learning error in the end).

Weaknesses

A recent work [CKKSV24] shows that non-tolerant TDS learning can also be accomplished when the hypothesis classes has $L_1$ sandwiching polynomials. This makes TDS learning of some important hypothesis classes such as $AC_0$ circuits and quadratic threshold functions possible. However, the technique of spectral outlier removal in this work seems only applicable when one has $L_2$ sandwiching polynomial as otherwise one cannot easily replace moment-matching with spectral boundedness.

Questions

In Definition 4.5, should it be "from some distribution $\mathcal D^{\text{train}}$" instead of "from some distribution $\mathcal D$"?

Rating

8

Confidence

4

Soundness

3

Presentation

3

Contribution

4

Limitations

Yes, they have.

Summary

This work considers learning under distribution shift. Here, a learner receives i.i.d labeled data from $D_{train}$, along with i.i.d unlabled data from $D_{test}$. It then builds a classifier with the goal of achieving high accuracy over $D_{test}$. Under arbitrary conditions, this task is impossible, so in the PQ-learning framework the classifier is allowed to abstain from prediction for points with a frequency close to the total-variation distance between $D_{train}$ and $D_{test}$. This work also considers the TDS setting in which the learner is allowed to completely abstain from prediction if it believes its inputs are drawn from a different data distribution. The main technical idea of this work is an outlier detection scheme, which (efficiently) computes an outlier detection function $g$ meant to distinguish the points in the training sample from $D_{test}$ that are "far" from the support of $D_{train}$. Their outlier procedure works by iteratively utilizing a quadratic program to find a polynomial of degree k that strongly distinguishes an outlier set. They then remove points until the outlier set only consists of points where the polynomial solution evaluates to very large amounts. The overall idea here is that similar distributions (i.e. if $D_{train} = D_{test}$) will lead to similar polynomial evaluations over them, and consequently the existence of a "separating" polynomial serves as a means to detecting where the distributions differ. This idea is reflected in their first result, which shows that the output of this scheme results in a funtion $g$ such that upon filtering with $g$, polynomial evaluations over the test and training distribution must be bounded within a factor of each other (based on tolerance parameters). They additionally bound the runtime of their algorithm. The only requirement for this theorem to hold is that the training distribution must satisfy regularity conditions based on the degree of polynomials being used, and they subsequently show that these conditions are met by isotropic log-concave distributions. Utilizing this technical idea, this work proceeds by giving PQ-learning algorithm for half-spaces over Gaussian training distributions. Despite the limited scope of this case, this work neverthless provides the first dimension-efficient solution to this problem. Then, this work continues with a more general result for PQ-learning, which, under a condition of "reasonableness" for a pair $(D, F)$, gives an efficient learning algorithm. Under the same condition, this work concludes by giving results for success in the related TDS setting.

Strengths

This paper offers a solution to well-known theoretical problem that achieves the best known bounds. I particularly like that their algorithms are computationally efficient (in addition to enjoying the typical performance guarantees). Their technical idea for outlier detection (which forms the core of the paper) is relatively well explained and seems to me an innovative way to approach outlier detection.

Weaknesses

The latter half of the paper is fairly burdened with algebra and consequently a bit difficult to follow. I would have appreciated a greater focus on intuition with more of the technical details being left to the appendix.

Questions

1. Could you give some intuition for why you began your PQ-results for Gaussian distributions? The outlier-detection procedure works for a more general set of distributions, so it would be interesting if you could spell out the additional properties of Gaussians that make your first result possible. 2. Could you similarly give more intuition about the $(F, D)$-reasonableness condition? The definition feels rather extensive (given 3 conditions in it) and i consequently feel it could merit a longer discussion. As it is currently written, it feels a bit convoluted to me.

Rating

7

Confidence

4

Soundness

4

Presentation

2

Contribution

3

Limitations

Yes.