The Power of Iterative Filtering for Supervised Learning with (Heavy) Contamination

Thank you for your insightful comments, and for appreciating our work! We will incorporate your feedback in future revisions.

For a comparison to previous outlier removal techniques, see lines 167–178 in the submission, as well as our response to Reviewer b2ov.

Answers to questions:

• The reason we consider the clean distribution to be realizable in the BC setting is to be in line with the classical definition of learning with nasty noise. However, our approach generalizes to agnostic BC learning. See also Definition E.1 in Appendix E, for a formal definition.
• For BC learning, we do not need to know $\eta$. For HC learning, we do require an upper bound on the contamination ratio $Q$, in order to tune the hyperparameters of the iterative polynomial filtering algorithm. See also Definitions 1.2 and 1.4, where we describe the input of a BC learner (which does not include $\eta$), and the input of an HC learner (which does include $Q$).
• In lines 36–37, we use the term “optimal” to refer to the information-theoretically optimal guarantee, which, in the BC case, is $2\eta$. Thank you for pointing out this ambiguity. Note that no algorithm (even an inefficient one) can achieve error better than $2\eta$ under bounded contamination in the general case.
• The notation $O_k(1)$ hides an arbitrary function of $k$, which is a constant when $k$ is considered constant. See also line 775.

We wish to thank the reviewer for their positive feedback and comments!

The main differences between our outlier removal algorithm and the one of [DKS18a] are twofold:

1. First, their algorithm only preserves the expectations of squared polynomials, whereas ours preserves the expectations of arbitrary polynomials with small absolute expectations under the target distribution. Note that a bound on the absolute expectation of a polynomial does imply a bound on its squared expectation via hypercontractivity (see Definition 3.1); however, the resulting bound incurs a multiplicative factor that is exponential in the degree of the polynomial.

2. Second, our bounds on the polynomial expectations over the filtered set are independent of the degree of the polynomials, while the bounds of [DKS18a] scale exponentially with the degree $\ell$ of the polynomials.

Both of these improvements are crucial in our setting, because the polynomials we are interested in have degrees that are tied to their approximation properties. In particular, applying the results of [DKS18a] directly would introduce a race condition between the approximation quality $\epsilon$ and the degree $\ell$.

See also lines 167–178 in the submission.

Thank you for your time and appreciation of our work! We are happy to incorporate your suggestions in future revisions of our paper.

Access to unlabeled examples: We would like to point out that one does not always need to know whether the clean distribution corresponds to the target $D^*$, at least in the bounded contamination case. In particular, we may first fix a target distribution of interest $D^*$ of our own choosing, and form an algorithm that is guaranteed to either produce a low-error hypothesis under the clean distribution, or certify that the clean distribution is far from $D^*$. In other words, this algorithm would work in the testable setting, meaning that it does not require any assumptions on the clean distribution, at the cost of potentially refusing to provide a solution, but only if the clean distribution happens to be far from $D^*$.

To achieve this type of guarantee, it suffices to raise a flag if the outlier removal with respect to $D^*$ removes more than an $O(\eta)$ fraction of the input examples. Since $D^*$ is chosen by the learner, we can generate our own samples, for example by using random coin flips.

The proof of correctness for this method follows the approach of Section H, where we show that our iterative polynomial filtering can be used to solve the tolerant testable agnostic learning problem. We did not define the testable version of BC-learning for clarity of presentation, but the proofs of Section H can be generalized to the BC setting as well.

Nevertheless, we agree that designing algorithms that work universally with respect to wide families of distributions (and, hence, lead to testable algorithms that accept more often) is a concrete and important direction for future work.

Answers to questions:

Q1. You are correct that the only lower bound in Table 1 is in the cell of the last row and last column. We will make this clear in future revisions.

Q2. The choice of the class of polynomials is characterized by two hyperparameters, the degree $\ell$ and the excess error rate $\epsilon$. If one is interested in achieving information-theoretically optimal guarantees (e.g., error $2\eta$ in the BC case), then the choice of $\ell$ should be as high as possible, depending on the computational budget of the learner. The hope would be that $\ell$ is large enough so that the ground truth can be approximated by degree-$\ell/2$ polynomials.

Moreover, the error of the output hypothesis on the filtered set is an accurate proxy for its error on the clean distribution, as long as the number of removed points during filtering is small. Both of these quantities can be estimated efficiently, and, therefore, one can verify whether the choice of $\ell$ is large enough.

On the other hand, if the learner can only afford small values for $\ell$ (e.g., $\ell=1$ or $2$), then it would be preferable to follow approaches of prior work on BC learning (see, e.g., [DKS18a], citation in lines 481–483). These works give guarantees for BC learning of geometric classes (like halfspaces or intersections thereof), through constant-degree polynomial filtering. For a comparison between our filtering algorithm and the one used in [DKS18a], see our response to Reviewer b2ov.

The caveats are that (1) these methods can be significantly less robust to contamination compared to ours and (2) they only seem to work for special classes. Therefore, their methods would only provide meaningful results if the contamination rate is small enough, and the ground truth lies within a structured concept class. One interesting direction for future work is extending these methods to the case of heavy contamination, when $\mathrm{opt}_{\mathrm{total}}$ takes small values.

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

In table 1, we present the upper bounds using big-$O$ and the lower bound for monotone functions (last row, last column) using $\Omega$. We will modify the caption to make this clear in future revisions.

Computing $p^*$ corresponds to a convex program over the space of coefficients of degree-$\ell$ polynomials. In particular, the objective function is linear, and $\cal{P}$ is a convex set defined by a polynomial number of linear constraints plus one quadratic constraint. See lines 869–873 in the submission (proof of Theorem 3.2) for a relevant discussion on the algorithmic implementation.

We believe that obtaining an outlier-removal algorithm that works universally over a wide family of distributions is an important direction for future work (see lines 356–360). There are several challenges towards achieving this:

1. First, the problem is non-trivial even from an information-theoretic perspective. Barring any computational considerations, one needs to be able to control the number of clean points that are removed by the filtering algorithm. However, it is unclear when this is possible for infinite-sized families of target distributions (e.g., the family of all isotropic log-concave distributions). One special case where this issue can be resolved is for concept classes with the following universal approximation property: for each function in the class, there is a low-degree approximator that works with respect to all distributions within a wide family.

2. Second, even if one could show such a universal approximation property, it is not clear how to express the universal approximation (or an appropriate relaxation thereof) as a convex constraint. To this end, the sum-of-squares framework could be useful, but none of the known results from the sum-of-squares literature seems to directly apply to our setting.

Thank you for your response. I remain convinced that this is a strong set of results and retain my score.