Towards optimally abstaining from prediction with OOD test examples

Abstract:
A common challenge across all areas of machine learning is that training data is not distributed like test data, due to natural shifts, “blind spots,” or adversarial examples; such test examples are referred to as out-of-distribution (OOD) test examples. We consider a model where one may abstain from predicting, at a fixed cost. In particular, our transductive abstention algorithm takes labeled training examples and unlabeled test examples as input, and provides predictions with optimal prediction loss guarantees. The loss bounds match standard generalization bounds when test examples are i.i.d. from the training distribution, but add an additional term that is the cost of abstaining times the statistical distance between the train and test distribution (or the fraction of adversarial examples). For linear regression, we give a polynomial-time algorithm based on Celis-Dennis-Tapia optimization algorithms. For binary classification, we show how to efficiently implement it using a proper agnostic learner (i.e., an Empirical Risk Minimizer) for the class of interest. Our work builds on a recent abstention algorithm of Goldwasser, Kalais, and Montasser [10] for transductive binary classification.

heading: 1 Introduction
text: For learning of a class of functions F of bounded complexity, statistical learning theory guarantees low error if test examples are distributed like training examples. Thus abstention is not necessary for standard realizable prediction. However, when the test distribution Q is not the same as the distribution of training examples P , abstaining from prediction may be beneficial if the cost of abstaining α is substantially less than the cost of an error. This is particularly important when there are “blind spots” where Q(x) > P (x) = 0. Such blind spots may occur because of natural distribution shifts, or indeed may be due to adversarial attacks. Collectively, test examples that deviate from the training distribution are referred to as out of distribution (OOD) test examples. Such an extreme covariate shift scenario was analyzed for binary classification in recent work by Goldwasser, Kalais, and Montasser [10] (henceforth GKKM).
Abstaining from predicting may be useful because it is well-known to be impossible to guarantee accuracy on test examples from arbitrary Q 6= P (abstention is unnecessary under the common assumption that Q(x)/P (x) is upper-bounded) [7]. Whether one is classifying images or predicting the probability of success of a medical procedure, training data may miss important regions of test examples. As an example, Fang et al. [9] observed noticeable signs of COVID-19 in many lung scans; any model trained on data pre-2019 would not have any such instances in its training dataset. In the case of image classification, a classifier may be trained on publicly available data but may be also used on people’s private images or even adversarial spam/phishing images [21]. In settings such as medical diagnoses or content moderation, abstention may be much less costly than a misclassification. In practice, if a model abstains from making a prediction, it could be followed up by a more elaborate (and costly) model or direct human intervention. The extra costs of human intervention, or as may be the case in a medical setting, a more expensive test, needs to be traded off with the potential costs of
35th Conference on Neural Information Processing Systems (NeurIPS 2021).
misclassification. For a regression example, a model may be used to predict the success probability of a medical treatment across a population, yet examples from people that are considered high-risk for the treatment may be absent from the training data.
We begin by discussing binary classification, and then move to regression. In particular, for any distribution P over examples x ∈ X and any true classifier f : X → {0, 1} in F of VC-dimension d, the so-called Fundamental Theorem of Statistical Learning (FTSL) guarantees w.h.p. Õ(d/n) error rate1 on future examples from P using any classifier h ∈ F that agrees with f on n noiseless labeled examples [see, e.g., 20].
In Chow’s original abstention model [6], a selective classifier is allowed to either make a prediction ŷ at a loss of `(y, ŷ) ≥ 0 or abstain from predicting at a fixed small loss α > 0. Following GKKM, we consider a transductive abstention algorithm that takes as input n unlabeled test examples and n labeled training examples and predicts on a subset of the n test labels, abstaining on the rest. The goal is to minimize the average loss on the test set. (Unfortunately, the natural idea to abstain on test points whose labels are not uniquely determined by the training data can lead to abstaining on all test points even when P = Q.) GKKM give a algorithm with guarantees that naturally extend the FTSL to Q 6= P albeit at an additional cost. The word transductive refers to the prediction model where one wishes to classify a given test set rather a standard classifier that generalizes to future examples, though the two models are in fact equivalent in terms of expected error as we discuss. The term covariate shift is appropriate here as it describes settings in which Q 6= P but both train and test labels are consistent with the same f ∈ F . Without abstention, both transductive learning and covariate shift have been extensively studied [see,e.g., 1].
The principle behind our approach is illustrated through an example of Figure 1. Suppose P is the distribution Q restricted to a set S ⊂ X which contains, say, 90% of the test set, so that 10% of the unlabeled test examples are in blind spots. Say we have learned a standard classifier h ∈ F from the n labeled training examples. Hypothetically, if we knew S, then we could predict h(xi) for test xi ∈ S and abstain from predicting on xi /∈ S. If abstaining costs α, then the FTSL would naturally guarantee test loss ≤ 0.1α + Õ(d/n), because one abstains on 10% of the test examples and the remaining test examples are distributed just like P . The difficulty is that S may be too complex to learn. To circumvent this, we suggest a conceptually simple but theoretically powerful approach: choose the set of points to abstain on so as to minimize the worst-case loss over any true function f ∈ F that is also consistent with the training data. In particular, given a predictor h and a set of test points not abstained on, (ignoring efficiency) one could compute the worst-case loss over all f ∈ F that are consistent with the labeled training examples. This approach achieves optimal worst-case guarantees and, in particular inherits the natural loss guarantee one attains from abstaining outside of S discussed above. Converting this theoretical insight into an efficient algorithm is the focus of this paper, and different algorithms are needed for the case of classification and regression.
Interpretation. In the case of known P,Q, one may say there is a known unknown: the region of large Q(x)/P (x). In our model, however, even though this region is an unknown unknown, we achieve essentially the same bounds as if we knew P and Q. Thus, perhaps surprisingly, there is little additional loss for not knowing P and Q. GKKM give related guarantees, but which suffer from not knowing P,Q. In particular, even when P = Q their guarantees are Õ( √ d/n) compared
to the Õ(d/n) of FTSL, and they give a lower-bound showing Ω( √ d/n) is inherent in their “PQ” learning model. In the PQ model, the error rate on Q (mistakes that are not abstained on) and the abstention rate on future examples from P are separately bounded. In Appendix C, we show that the Chow model is stronger than PQ-learning in the sense that our guarantees imply PQ-bounds similar to theirs, but the reverse does not hold. Hence, the algorithms and guarantees in this paper extend the FTSL in both the Chow and PQ models. We also note that abstaining on predictions can either help reduce inaccuracies on marginal groups or be a source of unfairness towards a person or group of people, and it should not serve as an excuse not to collect representative data.

heading: 1.1 Classification results
text: For classification, suppose Y = {0, 1}, `(y, ŷ) := |y− ŷ| is the 0-1 loss (more general losses are considered in the body), and F is a family of functions of VC-dimension d. There is also a deterministic
1The Õ notation hides logarithmic factors.
Empirical Risk Minimization (ERM) oracle that computes ERM(x,y) ∈ arg ming∈F ∑ i `(yi, g(xi)) on any dataset x ∈ Xn,y ∈ Y n (even noisy). While it is NP-hard to efficiently compute ERM for many simple classes like disjunctions, previous reductions to ERM have proven useful with off-the-shelf classifiers (e.g., neural networks) albeit without theoretical guarantees.
The inputs to the learner are labeled training examples x̄ ∈ Xn, ȳ = f(x̄) ∈ Y n, and unlabeled test examples x ∈ Xn. For transductive learning, the goal is to predict labels for the n test examples x. A transductive abstention algorithm is also given the predictor h := ERM(x̄, ȳ), which has 0 training error, and selects a vector a ∈ [0, 1]n for the probability of abstaining on test examples x. Its loss is defined to be,
`x(f, h,a) := 1
n n∑ i=1 ai α+ (1− ai)`(f(xi), h(xi)). (1)
Our Min-Max Abstention (MMA) reduction, mentioned above, attempts to minimize the maximum test loss among classifiers consistent with the training data. In particular, it (approximately) solves the following convex optimization problem for a:
min a∈[0,1]n max g∈V `x(g, h,a). (2)
Here, V := {g ∈ F : ∀i g(x̄i) = f(x̄i)} is the version space of classifiers consistent with the training labels; thus h, f ∈ V . In other words, MMA minimizes the worst-case test loss it could possibly incur based on the labeled training and unlabeled test data. A key insight is that (2) has no unknowns, so MMA will achieve a max in (2) as low as if it knew P,Q and even f .
To solve (2), one must be able to maximize loss over V . Fortunately, GKKM showed how to solve that using a simple subroutine, which we call FLIP, that calls ERM.
Theorem 1 (Classification). For Y = {0, 1}, any n, d ∈ N, any F of VC dimension d, any f ∈ F , and any distributions P,Q over X ,
E x̄∼Pn,x∼Qn
[`x(f, h, â)] ≤ α|P −Q|TV + 2d lg 3n
n ,
where h = ERM(x̄, f(x̄)) and â = MMA(x̄, f(x̄),x, h,FLIP) ∈ [0, 1]n can be computed in time poly(n) using the ERM oracle for F .
The total variation distance |P − Q|TV, also called the statistical distance, is a natural measure of non-overlap that ranges from 0 when P = Q to 1 when P and Q have disjoint supports. The α|P − Q|TV term arises because the learner may need to abstain where P and Q do not overlap, and the other term derives directly from the same bound one gets in the case where P = Q (so |P −Q|TV = 0). These bounds are stated in terms of expected loss, because unfortunately as we show in Lemma 8, high probability bounds require Ω(α/ √ n) loss because of the variance in how Q samples are distributed. All proofs, unless otherwise stated, are deferred to Appendix F.
We generalize Theorem 1 in multiple ways. First, we point out a stronger bound in terms of a divergence Dk(P‖Q), k ≥ 1, that measures the excess of Q(x) over k · P (x). It generalizes the total variation distance |P −Q|TV between distributions P,Q:
Dk(P‖Q) := ∑ x max ( Q(x)− k · P (x), 0 ) ∈ [0, 1] (3)
|P −Q|TV := D1(P‖Q) = 1
2 ∑ x |P (x)−Q(x)| (4)
Note that if Q(x) ≤ k · P (x) for all x, then Dk(P‖Q) = 0. Second, we show this implies generalization by using a transductive abstaining algorithm to bound the expected loss with respect to future examples from Q. That is, to go alongside classifier h : X → {0, 1}, we can output abstainer A : X → [0, 1] that gives a probability of abstaining on each test example. Here, the generalization loss is,
`Q(f, h,A) := E x∼Q
[ αA(x) + (1−A(x))` ( f(x), h(x) )] .
These two generalizations are summarized by the following theorem, which we state for classification but also has a regression analog. Theorem 2 (Generalization for classification). Fix Y = {0, 1} and F of VC dimension d. For any f ∈ F , and any distributions P,Q over X ,
E x̄∼Pn,x∼Qn [`Q(f, h,A)] ≤ min k≥1
αDk(P‖Q) + 2dk lg 3n
n ≤ α|P −Q|TV +
2d lg 3n
n .
where h = ERM(x̄, f(x̄)) and abstainer A : X → [0, 1] can be computed in time poly(n) using ERM and is defined by A(x′) := MMA ( x̄, f(x̄), (x′, x2, . . . , xn), h,FLIP ) .
These guarantees use the same algorithm—to predict on a new test example x′, it simply runs MMA with a modified test set where we have replaced the first test example by x′ and returns the probability of abstaining on it.
Third, as in GKKM, guarantees hold with respect to a “white-box” adversarial model in which there is only a training distribution P and an adversary who may corrupt any number of test examples (but they are still labeled by f ). More specifically, natural train and test sets x̄, z ∼ Pn are drawn, and an adversary may form an arbitrary test set x ∈ Xn. We achieve guarantees as low as if one knew exactly which examples were corrupted and abstained on those: Theorem 3 (Adversarial classification). For any f ∈ F with d = VC(F ), any n ∈ N, δ ≥ 0 and any distribution P over X , with probability ≥ 1− δ over x̄, z ∼ Pn, the following holds simultaneously for all x ∈ Xn:
`x(f, h, â) ≤ α
n |{i : xi 6= zi}|+
2d lg 2n+ lg 1/δ
n .
where h = ERM(x̄, f(x̄)) and â = MMA(x̄, f(x̄),x, h,FLIP) ∈ [0, 1]n can be computed in time poly(n) using ERM.
In their adversarial setting, GKKM again has Õ( √ d/n) bounds. Our presentation actually begins in this adversarial framework as it is in some sense most general–adversarial robustness implies robustness to covariate shift.

heading: 1.2 Linear regression results
text: For selective linear regression, the classic problem with transductive abstention, we give a more involved but fully polynomial-time algorithm. (GKKM did not discuss regression.) Here, Y = [−1, 1], X = Bd(1) is taken to be the unit ball in d dimensions. There is now a joint distribution ν over X × Y such that: f(x) := E
ν [y|x] = w · x for some vector w with ‖w‖ ≤ 1. We write
(x̄, ȳ) ∼ νn to indicate that the n labeled training examples are drawn from ν. The loss for selective regression `x(h, f,a) is still defined as in (1) except that `(f(x), h(x)) := |f(x) − h(x)|2. Note that we are considering loss with respect to f rather than y which means that it may approach 0 for identical train and test distributions. Indeed, the additional loss term we will face due to the covariate shift is again α|P −Q|TV, where P and Q are the marginal distributions over X for ν and the test distribution, respectively.
Theorem 4 (Linear regression). Let Y = [−1, 1], n, d ∈ N, δ > 0, and X = Bd(1). Let P,Q be distributions over X and ν be a distribution over X × Y with marginal P over X . Let f(x) :=
E (x,y)∼ν [y|x] = w · x for some w ∈ Bd(1). Then,
E (x̄,ȳ)∼νn,x∼Qn
[`x(f, h, â)] ≤ α|P −Q|TV + κ log n√
n .
where κ is a constant, h = ERM(x̄, ȳ) and â = MMA(x̄, ȳ,x, h,CDT) ∈ [0, 1]n can be computed in time poly(n, d).
A technical challenge is that, as a subroutine, we need to find a linear model maximizing squared error, which is a non-convex problem. Fortunately, this step can be formulated as a Celis-DennisTapia (CDT) problem, for which efficient algorithms are known [5, 3]. Our information theoretic results generalize to more general regression in a straightforward fashion, however the algorithm for maximizing loss is non-convex and we only know how to implement it efficiently for linear regression.
Contributions and organization. The main contributions of this work are: (1) introducing and analyzing an approach for optimally abstaining in classification and regression in the transductive setting, and (2) giving an efficient abstention algorithm for linear regression and an efficient reduction for binary classification (optimal in our model). After reviewing related work, we formulate the problem in a manner that applies to both types of prediction: binary classification and regression. Section 2 gives information-theoretic bounds for selective prediction. Section 3 covers the general MMA reduction. We then focus on classification, where Section 4 gives bounds and an efficient reduction to ERM. Finally, Section 5 gives bounds and a polynomial-time abstention algorithm for linear regression.

heading: 1.3 Related work
text: There is relatively little theoretical work on selective classification tolerant to distributional shift. Early work had algorithms that could learn certain binary classes F with very strong absolute abstention and error guarantees [17, 13, 18]. However, it was impossible to learn other simple concept classes, even rectangles, in their models. GKKM was the first work to provide abstention guarantees for arbitrary classes of bounded VC dimension, achieving this with bounds that depended on |P − Q|TV. They showed that unlabeled examples (i.e., transductive learning) were provably necessary. In their PQ-learning model, specific to binary classification, they simultaneously guarantee Õ( √ d/n) errors (h(x) 6= f(x) which are not abstentions) from distribution Q and ≤ rejections on future examples from distribution P . While this latter condition may seem counter-intuitive at first, it implies guarantees in terms of total variation distance similar to the ones we give. However, they show that this approach to deriving bounds necessarily suffers from a Ω( √ d/n) inherent loss. We circumvent this lower-bound in the Chow cost model by directly optimizing over Q without regard to rejections on P . Appendix C details this comparison.
Other related work is either about selective classification or distributional shift, but not both. Work on selective classification, also called “reliable learning” and “classification with a reject option,” [6, 2, 8] study the benefits of abstaining in a model with fixed small cost α > 0. The goal is to abstain in regions where the model is inaccurate. Recent work by Bousquet and Zhivotovskiy [4] gives a (not necessarily computationally efficient) algorithm for obtaining fast rates with the Chow loss whenever the cost of abstention is bounded away from 1/2. They use this to characterize when fast rates for classification may be possible in the agnostic setting with improper learning. Finally, among the large body of prior work on transductive learning, the closest is work on transfer learning (without abstentions) [1]. Prior work on distributional shift without abstention [see, e.g., the book 16] has developed refined notions of distributional discrepancy with respect to classes of binary or real-valued functions [14]. Since the focus of our work is on abstention, we use total-variation distance. In future work, it would be interesting to see if these notions could be adapted to our setting.
Note that while our work addresses adversarial examples, it is very different from the recent line of work focused on robustness to small perturbations of the input [19, 11]. While our algorithms are not robust to such perturbations, they may at least abstain from predicting on such examples rather than misclassifying them.

heading: 1.4 Definitions
text: A table of our notation is given in Appendix A for convenience. Many of the definitions are common to classification and regression. Let X denote the instance space2 and Y denote the label space, and let F be a known family of functions from X to Y . There is an unknown target function f ∈ F to be learned.
We use boldface to indicate vectors (indexing examples), e.g., a = (a1, . . . , ak). We denote by f(a) = (f(a1), . . . , f(ak)) for function f . Throughout the paper, we assume that α and F are fixed and known. Let [n] = {1, 2, . . . , n} and 1[φ] denotes the indicator that is 1 if predicate φ holds and 0 otherwise.
There is a general base loss ` : Y × Y → R+. We extend the definition of loss to loss on a sequence x and with abstention indices A ⊆ [n]:
`x(f, h) := 1
n n∑ i=1 `(f(xi), h(xi)), `x(f, h,A) := α n |A|+ 1 n ∑ i/∈A `(f(xi), h(xi)).
We assume access to a deterministic algorithm returning ERM(x,y) ∈ arg ming∈F ∑ i `(yi, g(xi)) that runs in unit time on any dataset x ∈ Xn,y ∈ Y n (even noisy). The algorithms all take labeled training examples x̄ ∈ Xn, ȳ ∈ Y n and unlabeled test examples x ∈ Xn as input. For binary classification, as discussed, Y = {0, 1}, there are train and test distributions P,Q over X , and all examples are assumed to be labeled by f , so ȳ = f(x̄). Here, the version space of classifiers with 0 training error is defined to be VS(x̄, ȳ) := {g ∈ F : g(x̄) = ȳ}. For regression, Y = [−1, 1] and there is a train distribution ν over X × Y with marginal P over X , and it is assumed that f(x̄) := E
(x̄,ȳ)∼ν [ȳ|x̄] ∈ F . The test distribution similarly has marginal Q over
X . The version space is VS is somewhat more complicated and is defined in Section 5.
With respect to V ⊆ F (which we will generally take to be the version space), we denote the worst-case test loss of a given classifier h (with a given abstention set A) on the test set, denoted by Lx:
Lx(V, h) := max g∈V `x(g, h), Lx(V, h,A) := max g∈V `x(g, h,A). (5)

heading: 2 Information-theoretic bounds for classification and regression
text: This section bounds the statistical loss (ignoring computation time) of choosing where to abstain A so as to minimize the upper-bound Lz(V, h,A) on test loss, where the predictor h (used when not abstaining) is first fit on training data and V ⊆ F is a general version space containing the target f . For noiseless binary classification, V would simply be those classifiers consistent with f , and V is a bit different for regression. Now, for “normal” test data z ∼ Pn iid from the train distribution, a standard generalization bound would apply to the worst-case test loss Ez∼Pn [Lz(V, h)] (e.g., Õ(d/n) for binary classification with 0-1 loss). Our bounds are stated in terms of this quantity Ez∼Pn [Lz(V, h)] and can be viewed as the overhead due to P 6= Q.

heading: 2.1 Learning with adversarial test examples
text: We begin with the adversarial setting of GKKM since it is particularly simple and will imply bounds in a distributional case. Here, there is only one distribution P . First, nature picks n “natural” iid train and test examples x̄, z ∼ Pn. As mentioned, if there were no adversary, a learning algorithm might output some h in a version space V and would have a test error guarantee of Lz(V, h).
Instead, a computationally-unlimited adversary armed with knowledge of x̄, ȳ, z, f , and the learning algorithm (and its random bits), chooses an arbitrary test set x ∈ Xn by corrupting as many or few test examples as desired. If we knew z, the adversary could corrupt any γ fraction of examples, we could of course guarantee loss ≤ γα + Lz(V, h) by abstaining on the modified examples where xi 6= zi. While the learning algorithm does not see z, it can still achieve the same guarantee:
2To avoid measure-theoretic issues, for simplicity we assume that X is finite or countably infinite.
Lemma 1. [Adversarial loss] For any n ∈ N, V ⊆ F , f ∈ V , z,x ∈ Xn, h : X → Y and all A∗ ∈ arg minA⊆[n] Lx(V, h,A):
`x(f, h,A ∗) ≤ α
n ∣∣{i : xi 6= zi}∣∣+ Lz(V, h). What this means is that if the natural training and test distributions are iid from the same distribution, then no matter which examples an adversary chooses to corrupt—x may be arbitrary—if one chooses A to minimize Lx(V, h,A), one guarantees the same exact bound γα + Lz(V, h). Moreover, the adversary has no control over Lz(V, h).
Our model is also robust to what is often called a “white box” adversary that knows and can target h exactly in making its choices. Appendix F.2 has the proof of the above lemma together with an additional analysis showing that if one jointly optimizes (h,A) one achieves a guarantee of γα + Lz(V, f) where Lz(V, f) can yield an error bound that is better than that of Lz(V, h) by a constant factor. In either case, for classification, once nature has picked the natural train and test distributions, x̄, z ∼ Pn, with high probability no matter what fraction γ of test examples the adversary corrupts, the learner guarantees loss ≤ γα+ Õ(d/n). For regression, the generalization bounds are different of course.

heading: 2.2 Learning with covariate shift
text: In the covariate shift setting, there are unknown arbitrary distributions P,Q over train and test examples, respectively. For the reasons mentioned above, we focus on the (transductive) abstention problem where h and version space V are determined from training data, and we focus on the expected test error. Below we give a bound of the form α|P −Q|TV + Ez∼Pn [Lz(V, h)]. Note that the second term is a standard generalization bound for transductive learning with test data from P – the worst case test loss (e.g., Õ(d/n) for binary classification). Hence, the first term represents the overhead for P 6= Q. In fact, we get can state a tighter bound. We state bounds in terms of Dk divergence for k ≥ 1, defined in Eq. (3), which generalizes statistical distance recalling that D1(P‖Q) = |P − Q|TV. To see why total variation bounds are loose, consider a distribution P which is uniform on X = [0, 1] and Q which is uniform on [0, 1/2], so |P −Q|TV = 1/2. Clearly the error rate of any h under Q is at most twice the error rate under P , and depending on α it may be significantly cheaper not to abstain. In particular, let = Ez∼Pn [`z(f, h)] be the error of h over P . As long as < α/2, the error upper bound 2 from not abstaining at all is lower than α|P −Q|TV = α/2. The guarantee we give is: Lemma 2. [Covariate shift] For any distributions P,Q over X , any h : X → Y , n ∈ N, V ⊆ F , f ∈ V ,
E x∼Qn
[`x(f, h,A ∗)] ≤ min k≥1 αDk(P‖Q) + k E z∼Pn [Lz(V, h)] ≤ α|P −Q|TV + E z∼Pn [Lz(V, h)] ,
where the above holds simultaneously for all A∗ ∈ arg minA⊆[n] Lx(V, h,A).
In the above example, D2(P‖Q) = 0 for P,Q uniform over [0, 1] and [0, 1/2], respectively.

heading: 3 The reduction (for classification and regression)
text: The approach is conceptually simple: it chooses where to abstain so as to minimize the upper-bound on test loss Lx(V, h,A). The algorithm MMA, in particular, shows that if one can maximize loss, then one has a separation oracle that can be used to minimize this upper bound using standard techniques. In particular, the ellipsoid algorithm is used, though simpler algorithms would suffice.3
The question then becomes, how difficult is it to find a function in F that maximizes loss. For classification, this can be done using an ERM oracle and a label-flipping “trick” used by [10]. For linear regression, this can be done in polynomial time (no ERM oracle is required, and ERM is trivial for linear regression) using existing CDT solvers. We first relax from binary to fractional abstention.
3Perceptron-like algorithms would suffice as we require only optimization to polynomial (not exp.) accuracy.
Algorithm MMA Input: x̄,x ∈ Xn, ȳ ∈ Y n, h : X → Y , and approximate loss-maximizer O Output: a ∈ [0, 1]n
Find and output point in convex set K:
K := { â ∈ [0, 1]n : Lx(VS(x̄, ȳ), h, â) ≤ min
a∈[0,1]n Lx(VS(x̄, ȳ), h,a) + 1/n } by running the Ellipsoid algorithm using the following separation oracle SEP(a) to K:
Fractional abstention. Loss may be slightly lower if one is allowed fractional abstentions, or equivalently to abstain at random. This can be described by a probability ai ∈ [0, 1] for each test example xi, which indicates that we abstain with probability ai and classify according to h with probability 1 − ai. As described in the introduction, the definitions of ` and L are extended to fractional abstention vectors a ∈ [0, 1]n in the natural way:
`x(f, h,a) := 1
n n∑ i=1 aic+ (1− ai)`(f(xi), h(xi)) and Lx(V, h,a) := max g∈V `x(g, h,a).
Our task is to optimize abstention given a fixed h and x and a fixed set of candidate function g ∈ V (e.g., a version space), assuming one can maximize loss, i.e., find g ∈ V realizing maxg∈V `(g, h, â) = Lx(V, h, â).
Lemma 3 (Reduction). For any bounded loss ` : Y 2 → [0, 1], any V := VS(x̄, ȳ) ⊆ Y X , any h : X → Y , and any x ∈ Xn, the Ellipsoid algorithm can be used in MMA to find â such that,
Lx(V, h, â) ≤ min a
Lx(V, h,a) + 1
n ,
in poly(n) time and calls to approximate loss maximization oracle O provided that its outputs g = O(x̄, ȳ, h,a) ∈ V all satisfy `x(g, h,a) ≥ maxg′∈V `x(g′, h,a)− 13n .
This can be done using any standard optimization algorithm, e.g., the ellipsoid algorithm, with O serving as a separation oracle. Optimizing to within less than 1/n is not generally significant for learning purposes. Note that the Ellipsoid method is more commonly defined with a separationmembership oracle that either claims membership in the convex set K or finds a separator. As we describe in Appendix F.4 containing the proof of Lemma 3, for such optimization problems the Ellipsoid can be used with such an oracle by outputting the query with best objective value.

heading: 4 Binary classification
text: For the case of binary classification, the version space is defined as follows:
VS(x̄, ȳ) := {g ∈ F : g(xi) = yi for all i ≤ n}.
We can use generalization bounds on Lz(VS(x̄, ȳ), h) to get directly: Theorem 5 (Adversarial classification loss). For Y = {0, 1}, d = VC(F ), `(y, ŷ) = |y − ŷ|, any n ∈ N, δ > 0, the following holds with probability ≥ 1 − δ over x̄, z ∼ Pn: For all
h ∈ VS(x̄, f(x̄)),x ∈ Xn, and all A∗ ∈ arg min A⊆[n] Lx(VS(x̄, f(x̄)), h, A),
`x(f, h,A ∗) ≤ α
n ∣∣{i : xi 6= zi}∣∣+ 2d lg 2n+ lg 1/2δ n .
Proof. This follows directly from Lemma 1 and generalization bound Lemma 7 of Appendix D.
Covariate shift bounds for classification were stated in Theorems 1 and 2. Next, as observed in prior work [10], for binary classification with the 0-1 loss, one can use an ERM oracle which minimizes loss to maximize loss as needed above. This algorithm is called FLIP. Lemma 4 (FLIP). For Y = {0, 1} with `(y, ŷ) = |y− ŷ| and any h ∈ F , x̄ ∈ Xn, ȳ = h(x̄) ∈ Y n, and any a ∈ [0, 1]n,
ĝ = ERM ( 4n2 copies of (x̄i, ȳi) and b3n(1− ai)c copies of (xi, 1− h(xi)), for each i ) satisfies ĝ ∈ VS(x̄, ȳ) and `x(ĝ, h,a) ≥ Lx(VS(x̄, ȳ), h,a)− 1/3n.
In other words, one creates an artificial weighted dataset consisting of numerous copies of the training data (x̄i, ȳi) and a number of copies proportional to 1− ai of each flipped test example (xi, 1− yi). Then the classifier output by ERM is in the version space with 0 training error, due to the high weight of each (x̄i, ȳi), and approximately maximizes `x(g, h,a). If O can take weighted examples, then a dataset with only 2n samples would suffice. The proof appears in Appendix F.5.

heading: 5 Regression
text: In this section, we let Y = [−1, 1] and use the squared loss function ` : Y 2 → R+, `(y, ŷ) = (y−ŷ)2. For regression, since labels are noisy, we will not be able to use an exact version space and instead will need to define an α-approximate version space for α ≥ 0: VSα(x, h) = {g ∈ F | `x(g, h) ≤ α}. For classes F that are convex and have bounded “Rademacher complexity”, the version space can be bounded (cf. Section G for the details). Unfortunately, the label flipping “trick” used for classification cannot be applied to maximize loss for regression. The loss here is continuous and convex in ŷ, not binary, and maximizing a convex function is intractable in general. For linear functions, which have low Rademacher complexity, however, efficiently maximizing the squared error over certain constrained sets is possible, allowing us to obtain efficient algorithms.
In this subsection, we shall assume that X = {x|x ∈ Rd, ‖x‖ ≤ 1} and Y = [−1, 1]. For R > 0, let FR = {x 7→ w · x | w ∈ Rd, ‖w‖ ≤ R} be the class of linear function from X → Y parametrized by vectors with norm bounded by R. Let F := F1.
In order to design an efficient algorithm, we will use an oracle to solve the Celis-Dennis-Tapia problem (CDT): min{f(x) | g1(x) ≤ 0, g2(x) ≤ 0, x ∈ Rd}, where f is a quadratic function, gi(x) ≤ 0 for i = 1, 2 define ellipsoids and at least one of g1, g2 is strictly convex. For readability, in the lemma below, we will assume that we have oracle access to exactly solve this problem. Theorem 1.3 [3] shows that this problem can be solved in time polynomial in the bit complexity and log(ε−1), to achieve a solution that is within an additive factor ε of the optimal and each of the constraints may violate feasibility by additive factor of ε. The lemma as stated below uses an exact oracle to the CDT problem. However, this can easily be addressed by tightening the constraint set slightly and using an approximate optimal solution. As the running time is polynomial in log(1/ ), choosing an smaller than the bounds obtained by the learning algorithm suffices. The details are provided in Appendix H. Lemma 5 (Regression loss maximization). For X , Y , ` as defined above, consider F , the class of linear functions from X → Y . Assuming we have an exact oracle for the CDT problem, for any h ∈ F , x̄ ∈ Xn, ȳ ∈ Y n, x ∈ Xn, α > 0, and a ∈ [0, 1]n, there exists a polynomial time algorithm that outputs ĝ ∈ VSα(x̄, h) such that `x(ĝ, h,a) = Lx(VSα(x̄, h), h,a).

heading: 6 Conclusions
text: We have shown how transductive abstention can lead to algorithms with robustness to arbitrary covariate shift and adversarial test examples. A simple min-max approach is given to minimize the
worst-case loss and is show how to efficiently implement this approach in certain cases such as linear regression. The min-max approach enjoys both optimal guarantees in terms of test loss and essentially no cost for not knowing the train and test distributions P and Q over X .
In terms of future work, it would be interesting to generalize the abstention model to online and possibly agnostic settings, or at least understand the limits. GKKM showed a lower bound of Ω( √
OPT) for one agnostic model, though it is not clear what the right agnostic model is. Finally, it would be interesting to see if their are other applications of our min-max approach of formulating a learning problem as an optimization with no unknowns. It enables one to directly achieve upper bounds as good as if one knows the unknowns.

heading: 7 Limitations and Societal Impact
text: Our primary contributions in this paper our mathematical; the contributions, limitations and open problems in mathematical terms have already been discussed in the body of the paper.
Practical machine learning methods may be designed inspired by the algorithms in this paper. When used appropriately, we expect the societal impact of these methods to be largely positive. While in many cases, abstention on out of distribution (OOD) examples may be desirable compared to making an incorrect prediction, it is important that this approach not be used as an excuse to not collect representative data. Potential harm may be done to certain groups by having different rates of abstention among different groups, different rates of misclassification, and potential de-anonymization by revealing examples where a classifier abstained to a human.

Review summaries:
The paper considers prediction with the abstention option, with a reduced loss for abstention (Chow's model), in a setting where the test distribution can be different from the training distribution. The setting is very similar to GKKM20 except that the loss here is different (GKKM separately bounds standard risk and amount of abstention, current paper minimizes a weighted combination), and current work considers linear regression in addition to binary classification. The paper presents efficient algorithms given ERM oracles and bounds the Chow's loss of their procedures for both binary classification and linear regression. The technique involves setting abstention to minimize the abstention-equipped loss, by using a separation oracle that needs an approximate maximizer of the loss. The upper bounds depend on the variational distance between the test and training distributions plus a term which decreases with sample size.

This paper considers the abstention model in which a classifier is able to abstain from predicting (and thus paying a fixed cost) as opposed to being forced to give a prediction.   They consider a formalism in which the algorithm is given a classifer $f$ with 0 training loss, and it must make predictions for an additional $n$ test points. The classifier incurs a loss of 1 for each error it makes on the test points, but incurs loss $\alpha$ if it chooses to abstain (where $\alpha \leq 1$). Furthermore, the points in the test set are drawn from some distribution that differs from the original training distribution.   In this formalism, they give a generalization bound of a polynomial time algorithm that uses empirical risk minimization as a subroutine. The basic gist is that the overall expected lost can be bounded by the total variation between the training and test distributions along with a $\frac{O(d\logn}{n}$ term where $d$ is the VC-dimension of the classifiers.   They then apply their ideas to the setting of adversarial classification, in which adversarial examples can be thought of as being drawn from a distribution $Q$ that is very close to the original data disribution $P$. They also apply their theorem to linear regression giving a bound on how well a linear classifier can be learned. 

This paper studies agnostic transductive learning when train and test distributions have covariate shift. The objective follows Chow 57', where abstention suffers a fixed cost, and the goal is to minimize total costs of prediction error and abstentions. The paper proposes efficient algorithms for linear regression and binary classification, based on ideas from Goldwasser et al. The paper also proves lower bounds showing that the guarantee is near-optimal.

The paper studies selective prediction where abstention incurs a fixed and known cost. It extends the Fundamental Theorem of Statistical Learning to selective classification and linear regression under distributional shift. The paper also proposes min-max abstention reduction with optimal guarantees in test loss.