Tolerant Algorithms for Learning with Arbitrary Covariate Shift

We thank the reviewer for their time and effort.

Question 1. We note that, while we provide most of the technical details of our proofs in the appendix, we do provide a high-level explanation of our results in the main part, including Theorem 3.1 (see lines 189–223). In fact, the comparison with [DKS18] partly explains the technical differences between Theorem 3.1 and results on outlier removal from prior work. Given the reviewer’s feedback, however, we will add some further technical details in the main paper.

Question 2. We respectfully disagree with the reviewer’s comment that our statements lack precision. Note that the parameter $\lambda$ is defined in the preliminaries (lines 146–148). Moreover, in Lemma B.2, the premise regarding $f$ is that $f(x) = 0$ for any $x$ that satisfies some property (the one described in line 693, i.e., that $p(x)^2$ is more than $B$ for some polynomial $p$ with low second moment) and not all $x$. We will clarify these points in the main paper and we are happy to address any further specific concerns that the reviewer may have.

Question 3. The algorithms we propose are efficient in the dimension of the input, which is a standard goal in learning theory (see, for example, the classical work of [KKMS08]). In the presence of label noise, the exponential dependence on the parameter $\epsilon$ cannot be removed, even if one assumes that there is no distribution shift (see [DKPZ21]). Additionally, when there is no label noise, the algorithm of Theorem 4.3 for PQ learning of halfspaces is quasi-polynomial in all parameters and is optimal in the SQ framework (see [KSV24a]).

Question 4. Theorem 3.1 is stated for the second moment for two reasons. First, using the second moment enables the use of spectral methods for the outlier removal procedure and is a common approach for prior results on outlier removal. Second, it is sufficient for our purposes, since the difference of the upper and lower $\mathcal{L}_2$ sandwiching approximators is itself a polynomial with low second moment under the target distribution. Subsequently, we can use the outlier removal procedure to find a subset of the input set over which the bound on the squared difference of the sandwiching approximators is preserved.

[KKMS08] Adam Tauman Kalai, Adam R Klivans, Yishay Mansour, and Rocco A Servedio. Agnostically learning halfspaces. SIAM Journal on Computing, 37(6):1777–1805, 2008.

[DKPZ21] Diakonikolas, Ilias, Daniel M. Kane, Thanasis Pittas, and Nikos Zarifis. "The optimality of polynomial regression for agnostic learning under gaussian marginals in the SQ model." In Conference on Learning Theory, pp. 1552-1584. PMLR, 2021.

[KSV24a] Adam R Klivans, Konstantinos Stavropoulos, and Arsen Vasilyan. Learning intersections of halfspaces with distribution shift: Improved algorithms and sq lower bounds. 37th Annual Conference on Learning Theory, COLT, 2024.

We thank the reviewer for their time and appreciation of our work.

• Lines 62-63: We will clarify this point, thank you for pointing out.

• Lines 111-117: Our work is indeed the first to consider distribution-specific PQ-learning at all. Prior work involved reductions to other learning primitives like agnostic or reliable agnostic learning, but the reductions did not preserve the marginal distributions and, hence, the resulting algorithms were inherently distribution-free.

We thank the reviewer for their constructive feedback. We will carefully go through our proofs in the appendix to fix all typos for future revisions. Regarding the specific questions of the reviewer:

Question 1. You are correct that Equation (B.2) should have the square of Frobenius norm on the left side. Thank you for pointing out that typo. This will in turn slightly change the bound of the equation between lines 677 and 678, where we will instead use the fact that $\mathbb{E}_{S_i}[||I-M^{-1/2}M_iM^{-1/2}||_2] \le \sqrt{ \mathbb{E} _{S_i}[||I-M^{-1/2}M_iM^{-1/2}||_F^2]} \le \frac{(dk)^{O(k)}}{N^{1/4}}$. The statement of line 678 is still true for some sufficiently large constant $C$.

We now give the omitted details for Equation (B.2). We start with the second equality. We have $\mathbb{E}_ {x\sim D}[ r_{j}(x) r_{j'}(x) ] = e_{j}^{T} e_{j'}$, which is zero if $j=j’$ and 1 otherwise (by the equation starting directly after line 669). We also have $e_j^T M^{-1/2}=r_j^T$ and $M^{-1/2} e_{j’}= r_{j’}$ and therefore $e_j^T M^{-1/2} M_i M^{-1/2} e_{j’}= r_j^T M_i r_{j’}$ which equals to $\mathbb{E}_ {x \sim S_i}[r_{j}(x) r_{j'}(x)]$.

Now we explain the third equality, after adding $\mathbb{E}_ {S_i}$ (the expectation over the random selection of the elements of $S_i$) in the beginning of the second line, which is missing due to a typo. Since the set $S_i$ is composed from i.i.d. samples from $D$, the quantity $\mathbb{E}_ {S_i}(\mathbb{E}_ {x \sim D}[r_{j}(x) r_{j'}(x)]-\mathbb{E}_ {x \sim S_i}[r_{j}(x) r_{j'}(x)])^2$ equals to the variance of the random variable $\mathbb{E}_ {x \sim S_i}[r_{j}(x) r_{j'}(x)] = \frac{1}{|S_i|}\sum_{x\in S_i}r_{j}(x) r_{j'}(x)$ (the randomness is over the choice of $S_i$). Since the choice of elements of $S_i$ is i.i.d. from $D$, we can use the fact that the variance of a sum of i.i.d. variables equals to the sum of their variances. Overall, we have that the variance of $\mathbb{E}_ {x \sim S_i}[r_{j}(x) r_{j'}(x)]$ equals to $\frac{1}{|S_i|}\mathrm{Var}_ {x \sim D}[r_{j}(x) r_{j'}(x)]$. Finally, we substitute $|S_i|=\sqrt{N}$.

Question 2. Even though the polynomial $r_j r_{j’}$ is of degree $2k$, it has the extra property of being a product of two degree-k polynomials. If $(r_j(x) r_{j’}(x))^2>B^2$ it has to either be the case that $(r_j(x))^2>B$ or $(r_{j’}(x))^2>B$. The probability of either of those events can be bounded by referring to the definition of $k$-tameness.

Question 3. We confirm that the additive term $\Delta$ is indeed not necessary in the second line of Equation (B.4). We will correct this typo in the revision. We however note that the third line of Equation (B.4) should still have an additive term of $2\Delta$ (replacing the current value $\Delta$ with the value $2\Delta$ entails changing $\Delta$ to $\Delta/2$ in the line after line 701 and does not change the conclusion on line 702). The third line of Equation (B.4) follows from the second line of Equation (B.4) (with $\Delta$ removed) as follows. By triangle inequality, the second line of Equation (B.4) can be upper-bounded by a sum of terms if we let $u_j$ denote $\mathbb{E}_ {x \sim S} [f(x) \mathbf{1}_ {j\Delta \leq (p(x))^2 < (j+1)\Delta } ]$ and $v_j$ denote $\mathbb{E}_ {x \sim D’} [f(x) \mathbf{1}_ {j\Delta \leq (p(x))^2 < (j+1)\Delta } ]$, then by the triangle inequality we see that the second line of Equation (B.4) is at most $\sum_{j=0}^{B/\Delta}( (j \Delta) |u_j - v_j| + \Delta u_j + \Delta v_j)$. We also observe that $j \Delta \leq B$, and $\sum_{j=0}^{B/\Delta} u_j \leq 1$ and $\sum_{j=0}^{B/\Delta} v_j \leq 1$ which bounds the whole expression by $2\Delta+B\sum_{j=0}^{B/\Delta}( |u_j - v_j|).$

Question 4. Thank you for pointing this out, we added a short claim that proves that there indeed exists a value of $\tau_i$ satisfying the condition, assuming certain high-probability events take place. The proof is based on a simple averaging argument. In particular, $\tau_i$ is defined as the threshold such that the current set $S_i ^{\text{filtered}}$ contains unreasonably many points $x$ such that $(p_i(x))^2 >\tau_i$. If such a threshold $\tau_i$ did not exist, then $S_i ^{\text{filtered}}$ would not satisfy line 919 (which is a contradiction).

More formally, for the sake of contradiction, suppose that for every $\tau \ge 0$ it is the case that

Since every element $x$ of $S_i^ {\text{filtered}}$ satisfies $(p_i(x))^2 \le B_0$ we have

Combining Equations (1) and (2) gives

which in turn is bounded by $\frac{10}{\alpha} ( \Delta_0 B_0 + \mathbb{E}_ {x \sim S_D} [ (p_i(x))^2 \cdot 1_{x \le B_0} ] )$. Additionally, since $S_D$ is assumed to satisfy property (3) in Claim 1, and $\hat{M}$ is assumed to satisfy Equation (E.1) (see line 929), we have $\mathbb{E}_ {x \sim S_D} \left[ (p_i(x))^2 \cdot 1_ {(p_i(x))^2 \le B_0} \right] \le 2\mathbb{E}_ {x \sim D}[(p_i(x))^2] \le \frac{11}{5} (p_i)^T \hat{M} (p_i) \le \frac{11}{5} \le 5$. Overall, we have bounded $\frac{1}{N} \sum_{x \in S_i^ {\text{filtered}}} (p_i(x))^2$ by $\frac{10}{\alpha} \left( \Delta_0 B_0 + 5 \right)$, which contradicts the premise that $\frac{1}{N} \sum_{x \in S_i^ {\text{filtered}}} (p_i(x))^2 > \frac{50}{\alpha} (1 + \Delta_0 B_0)$, finishing the proof.

We wish to thank the anonymous reviewer for their constructive feedback and suggestions.

Gaussian assumption: The reviewer is correct that the outlier removal procedure works under weaker assumptions than Gaussianity. In particular, it will work for any tame distribution (see lines 155–158 for a definition). However, in order to obtain our PQ learning results, we also make use of the existence of low degree $\mathcal{L}_2$-sandwiching approximators. The existence of such approximators has been proven in prior work for the Gaussian distribution as well as for the uniform distribution over the hypercube. Nonetheless, we believe that simple classes like halfspaces and halfspace intersections admit low-degree sandwiching approximators with respect to other distributions as well and establishing appropriate bounds is an interesting direction for future work. The important relevant properties are, in general, both concentration and the anti-concentration of the Gaussian distribution, which are, for example, also satisfied by strongly log-concave distributions.

Reasonable pairs: Definition 4.5 indeed consists of 3 properties. The first one is the existence of sandwiching approximators, which is known to be important for learning in the presence of distribution shift by prior work on TDS learning [KSV24b]. The second one is the tameness condition, which is important for the outlier removal procedure and was introduced in the work of [DKS18] for similar purposes. The third one ensures generalization for polynomial regression. We will add an appropriate discussion in future revisions.

[DKS18] Ilias Diakonikolas, Daniel M Kane, and Alistair Stewart. Learning geometric concepts with nasty noise. In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, pages 1061–1073, 2018.

[KSV24b] Adam R Klivans, Konstantinos Stavropoulos, and Arsen Vasilyan. Testable learning with distribution shift. 37th Annual Conference on Learning Theory, 2024.

Thank you for your time and for appreciating our work. In Definition 4.5, the distribution $\mathcal{D}$ represents some distribution over the features, which is unlabeled. We instead typically use $\mathcal{D}^{\mathrm{train}}$ to denote the labeled training distribution (see lines 136–137 and also Definition 4.1).