Towards optimally abstaining from prediction with OOD test examples
Authors: Adam Tauman Kalai
Varun Kanade
Venue: NeurIPS 2021 Spotlight (2021)
Keywords: Selective classification
covariate shift
classification with a reject option

Abstract: A common challenge across all areas of machine learning is that training data is not distributed like test data, due to natural shifts or adversarial examples; such 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 recent work of Goldwasser, Kalais, and Montasser (2020) who gave error and abstention guarantees for transductive binary classification.

Towards optimally abstaining from prediction with OOD test examples
Adam Tauman Kalai Microsoft Research
Varun Kanade University of Oxford
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, give a polynomial-tine algorithm based on Celis-Dennin 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 recent abstention algorithm of Goldwasser, Kalais, and Montasser [10] for transductive binary classification.
Introduction
For learning class of functions F of bounded complexity, statistical learning theory guarantees low стrоr 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 a substantially less than the cost of an error. This is particularly important when there are "blind spots" where Q(x) > P(x) = O. 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 recent work by Goldwasser, Kalais, and Montasser [10] (henceforth GKKM).
Abstaining from predicting may be useful because is well-known to be impossible guarantee accuracy on test examples from arbitrary Q * P. (abstention is unnecessary under the common assumption that ((=)/ (a:) upper-bounded) 7 Whether one classifying images or predicting the probability of success of medical procedure, training data may miss important regions of test examples. As an example, Fang al. [9] observed noticeable signs of COVID- in many lung scans; any model trained on data 2re-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 '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 model abstains from making prediction, it could be followed up by more elaborate (and costly) model or direct human intervention. The extra costs of human intervention, or as may be the case in medical setting, more expensive test, needs to be traded off with the potential costs of
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

misclassification. For a regression example, model may be used to predict the success probability of 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 I E X and any true classifier f : X + {0, 1f in F of VC-dimension d, the so-called Fundamental Theorem of Statistical Learning (FTSL) guarantees w.h.p. O(d/n) error rate on future examples from P using any classifier h F that agrees with on n noiseless labeled examples [see, e.g., 20].
In Chow's original abstention model (6, selective classifier is allowed either make prediction at a loss of E(y. 9) 2 0 or abstain from predicting at a fixed small loss a > O. Following GKKM, we consider transductive abstention algorithm that takes as input n unlabeled test examples and 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 & 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 & P but both train and test labels are consistent with the same f E F. Without abstention, both transductive learning and covariate shift have been extensively studied [see,e.g..]] M..
The principle behind our approach is illustrated through an example of Figure I Suppose P is the distribution Q restricted unlabeled test examples are in blind spots. Say we have learned standard classifier h E F from the n labeled training examples. Hypothetically. if we knew S, then we could predict h(z;) for test I; E S and abstain from predicting on z; & S. If abstaining costs a, then the FTSL would naturally guarantee test loss < 0.1a + (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 may be too complex to learn. To circumvent this, we suggest a conceptually simple but theoretically powerful approach: choose the set of points abstain on so as to minimize the worst-case loss over any true function I F that is also consistent with the training data. In particular, given a predictor l and set of test points not abstained on, (ignoring efficiency) one could compute the worst-case loss over all f E F that are consistent with the labeled training examples. This approach achieves optimal worst-case guarantees and, in particular inherits the natural loss guarantce 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.
set S C X which contains, say, 90% of the test set, so that 10% of the
Interpretation. In the case of known Q. one may say there is a known unknown: the region of large (z))/((z). 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 Ó ((vd/)) compared to the Ö(d/n) of FTSL, and they give a lower-bound showing S2( / /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- no-udounds 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 person or group of people, and it should not serve as an excuse not to collect representative data.
1.1 Classification results
For classification, suppose Y = {0, 1). E(y, = vy is the 0-1 loss (more general losses are con- sidered in the body), and F is family of functions of VC-dimension d. There is also deterministic
'The Ô notation hides logarithmic factors.
2

---

f? h
f?
+ positive training example
negative training example
test point we classify
test point we abstain on
S
Figure 1: A simple illustration of our approach when the training distribution P is the test distribution Q restricted a (blue) set We use classifier fit on the labeled training data. We choose the subset of test examples to abstain so as to minimize the worst-case loss over possible f's consistent with the training data. This gives a better worst-case loss than if we knew and did the obvious thing of abstaining on all test S.
Empirical Risk Minimization (ERM) oracle that computes ERM(x. ) E arg min E, E(yi, g(x;)) ) on any dataset E X" Y" (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 E X" y = f(x) E Y", and unlabeled test examples E X For transductive learning, the goal is to predict labels for the n test examples transductive abstention algorithm is also given the predictor := ERM(X. y). which has 0 training error, and selects vector E [0, 1|" for the probability of abstaining on test examples x. Its loss is defined to be,
1 Eo a.a + (1 (1- (()))
Ex a)
Our Min-Mat Abstention (MMA) reduction, mentioned above, attempts 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 max (x(g, h,a) n gEV
is the version space of classifiers consistent with the training labels; thus h, f E 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 knew P, P and even f.
Here, V (g F
To solve 2 one must be able to maximize loss over V. Fortunately, GKKM showed how to solve that using simple subroutine, which call FLIP, that calls ERM.
Theorem (Classification), For Y {0, any d E N, any F of VC dimension d any f F, and any distributions P. Q over X,
RmPr Qm [ex h1 a)] S alP Q1Tv + 2dlg
n
where h ERM(X, f(x) and = MMA(X, fxx), h, FLIP) E [o, 1]"h can be computed in time poly(n) using the ERM oracle for F.
The total variation distance IP Q/rv, also called the statistical distance, is natural measure of non-overlap that ranges from when P Q when P and Q have disjoint supports. The a - Q/rv 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
Q (so 1P-QITv 0). These bounds are stated in terms of expected loss, because unfortunately as we show in Lemma high probability bounds require l( ((a/Vn) loss because of the variance 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
divergence (Pl 1, that measures the excess of ((x) over k P(z). generalizes the total
variation distance PP Q TV between distributions P. P.Q:
(x([)) = Σ max (axx)(()) - k: P(x), 0) E [0, 1]
(3)
P Q|TV Di-IIV=D(PPIQQ) 1 Σ P(x) (())
(4)
Note that if Q(x) S k- P(x) for all x, then (P(()))) =
Second, we show this implies generalization by using 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 probability of abstaining on each test example. Here, the generalization loss is,
lo == E
[o A(r) + (1 (()))
=
These two generalizations are summarized by the following theorem, which state for classification but also has a regression analog.
Theorem 2 (Generalization for classification). Fix {0, 1} and F of VC dimension d. For any F, and any distributions P, Q over X,
PmPmXXQQ (, & min a (P(())))) 2dk lg 3n k21
az Q|rv 2d 3n
E
n
n
where h ERM(&, (()) and abstainer A X + [0, can be computed in time poly(n) using ERM and is defined by A(x') == MMA 2, f()), (a', .2..... Fn), h, h, FLIP).
These guarantees use the same algorithm-to predict on new test example x', it simply runs MMA with modified test set where we have replaced the first test example by x' and returns the probability of abstaining it.
Third, as in GKKM, guarantees hold with respect to a "white-box: adversarial model in which there is only training distribution P and 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 ~ p are drawn, and an adversary may form an arbitrary test set X We achieve guarantees low as if one knew exactly which examples were corrupted and abstained on those:
Theorem 3 (Adversarial classification). For any f E F with d VC(F), any E N, 2 0 and any distribution P over X, with probability 2 - å over X, ~ P", the following holds simultaneously for all x E X":
a S (x
= (i [ x, # 21}++ n
2d 2n + 1g/
n
where h ERM(X, f(x) and MMA(X, f(x), x, h, FLIP) E [0, 11"h can be computed in time (oly(n) using ERM.
In their adversarial setting, GKKM again has Ō( 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.
1.2 Linear regression results
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 Ba(1) is taken to be the unit ball in d dimensions. There is now a joint distribution over x such that: f(x) == [g|=] = w z for some vector with || S We write
(x,F) ~ nd to indicate that the n labeled training examples are drawn from v. The loss for selective regression (h, f. is still defined as in (1) except that ((((),, h(x)) := (xx - 12. Note that we are considering loss with respect to / rather than y/ which means that may approach 0 for identical train and test distributions. Indeed, the additional loss term we will face due to the covariate
shift is again a - Q/rv, where and Q are the marginal distributions over X for v and the test distribution, respectively.

---

Theorem 4 (Linear regression), Let Y L n. d E 8> 0, and X = Ba(1). Let P.Q be distributions over X and be a distribution over X x Y with marginal P over X. Let f(x) == [| w x for some w E Ba(1). Then, (a.y)
E
k llg
E (x. (=5))vm'x [B a)] S all Q/rv +
vn
where K. is constant, = ( y) and à MMA(X. h. CDT) E [0, 1]" can be computed in time poly(n,d) d).
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-Dennis- Tapia (CDT) problem, for which efficient algorithms are known [5 3 Our information theoretic results generalize to more general regression in straightforward fashion, however the algorithm for maximizing loss is non-convex and we only know how 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 manner that applies to both types of prediction: binary classification and regression. Section gives information--heerrtie 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 bounds and a polynomial-tine abstention algorithm for linear regression.
2
1.3 Related work
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 concept classes, even rectangles, 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|T They showed that unlabeled examples (i.e., transductive learning) were provably necessary. In their PQ-learning model, specific to binary classification, they simultaneously guarantee Ö(/d//) errors (h(z) * f()) 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, 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 52( ( d//n) inherent loss. We circumvent this lower-bourd in the Chow cost model by directly optimizing over Q without regard to details this comparison.
1 18
However, it was impossible to learn other simple
rejections on P. Appendix C
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 reject option," study the benefits of abstaining in a model with fixed small cost a > The goal in regions where the model is inaccurate. Recent work by Bousquet and Zhivotovskiy [4] gives (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 transfer learning (without abstentions) [ Prior work on distributional shift without abstention [see, e.g., the book [6) has developed refined notions of distributional discrepancy with respect to classes of binary real-valued functions [4]. Since the focus of our work is on abstention, we use total- iaal-vvrittion distance. In future work, it would be interesting see if these notions could be adapted to our setting.
abstain
Note that while our work addresses adversarial examples, 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 least abstain from predicting on such examples rather than misclassifying them.
5

---

1.4 Definitions
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 space and Y denote the label space, and let F be a known family of functions from to Y. There an unknown target function I' E F to be learned.
(2)) We denote by fa) = (f(a),,... f(ax)) for function f. Throughout the paper, we assume that a and F' are fixed and known. Let [n] (1,2,.... nu and [ø] denotes the indicator that if predicate e holds and 0 otherwise.
We use boldface indicate vectors (indexing examples), e.g., (a1, (d1.-..,,0
There is general base loss é Y Y +R_ We extend the definition of loss to loss on sequence x and with abstention indices A _ [n]:
" 7I Σ {f(a))) ((f.h,
b(f.b)
-|A| +
Σ
(f(x)))
72
T2
id
We assume access to deterministic algorithm returning ERM(x, y) E arg mintge F E, ((vi, that runs in unit time on any dataset x E X",,y , E Y (even noisy).
The algorithms all take labeled training examples x E X", E Y and unlabeled test examples x E X as input. For binary classification, as discussed, Y {0, there are train and test distributions P, Q over X, and all examples are assumed to be labeled by f. so y fxx). Here, the version space of classifiers with 0 training error defined to be VS(X, y) {gg
g(x) = y}.
For regression, Y = |-1, 1] and there is train distribution V over X x with marginal P over X, E
and it is assumed that f(ø)= (2.9)~v
E 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 S F (which we will generally take to be the version space), denote the worst-case test loss of a given classifier h (with a given abstention set A) on the test set, denoted by Ix:
gEV Ix (V, max Ex ht), LV A) = max (x(g, h, A).
(5)
gEV
2 Informationn-heorriic bounds for classification and regression
This section bounds the statistical loss (innoring computation time) of choosing where to abstain A so as to minimize the upper-bound Lg (V, h, A) on test loss, where the predictor (used when not abstaining) is first fit training data and V C 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 bit different for regression. Now, for "normal" test data distribution, a standard generalization bound would apply to the worst-case test loss Ez- (V, (e.g., Ö(d/n) for binary classification with 0-1 loss). Our bounds are stated in terms of this quantity Eg LZ (V, h)] and can be viewed the overhead due to P Q.
pn iid from the train
2.1 Learning with adversarial test examples
We begin with the adversarial setting of GKKM since it is particularly simple and will imply bounds in distributional case. Here, there only one distribution P. First, nature picks n "natural" iid train and test examples 8, z ~ p 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 (V, h).
Instead, a computationallly-nninn unnlimitd adversary armed with knowledge of x, z. and the learning algorithm (and its random bits), chooses an arbitrary test x E X by corrupting as many few test examples as desired. If we knew z, the adversary could corrupt any fraction of examples, we could of course guarantee loss S aa + L, (V, h) by abstaining x; # z, While the learning algorithm does not see z, it can still achieve the same guarantee:
the modified examples where
To avoid measure- measure-theoretic theoretic issues, for simplicity assume that X is finite countably infinite.

---

Lemma 1. [Adversarial loss] For any E A arg migminggiv ( A):
z. x Y and all - [i: n
&(f.h,
21 L2(V,
What this means is that if the natural training and test distributions are iid from the same distribution, then matter which examples an adversary chooses to corrupt-x may be arbitrary-iff one chooses to minimize Lx Lx(V, ht A), one guarantees the same exact bound ya + Lz(V, h). Moreover, the adversary has control over hV)
Our model is also robust what is often called "white box" adversary that knows and can target h exactly in making its choices. Appendix [22 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 ya (V. where [V, can yield an error bound that is better than that of (V, h) by constant factor. In either case, for classification, once nature has picked the natural train and test distributions, &, z pa. with high probability no matter what fraction Y of test examples the adversary corrupts, the learner guarantees loss S 7aa ((drn). For regression, the generalization bounds are different course.
2.2 Learning with covariate shift
In the covariate shift setting, there are unknown arbitrary distributions P. Q over train and test examples, respectively. For the reasons mentioned above, focus the (transductive) abstention problem where and version space V are determined from training data, and we focus on the expected test error. Below give bound of the form a Q/Tv F= (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., ((d/m) n) for binary classification). Hence, the first term represents the overhead for P + Q. In fact, get can state tighter bound.
We state bounds in terms of Dj divergence for & 2 1, defined Eq. 33, which generalizes statistical distance recalling that D₁ (PIIQ)
P - Q rrv. To see why total variation bounds are loose, consider a distribution P which is uniform on = [o. 1] and Q which is uniform on [0, 1/2], so PP-Q/TV 1/2. Clearly the eπrоr rate of any l under Q is at most twice the error rate under P. and depending on a it may be significantly cheaper not to abstain. In particular, let e = Ez-p= [ (f. (f, h)] be the error of h over P. As long
a./2, the error upper bound 2e from not abstaining at all is lower than a - Q rv = a/2. The guarantee we give is: Lemma 2. [Covariate shift] For any distributions P, Q over X, any h: X 3--+0 +Y,EN,,V fEV,
E x--Q" (&x,,,,,, A*)
min a m R21
(PIIQ) + (V, S apP Q|Tv + E 2~P
[L](V, h)),
where the above holds simultaneously for all A arg Tx h A).
In the above example, D2(PIIQ) 0 for P,Q uniform over [0, 1] and |o, 1/2], respectively.
3 The reduction (for classification and regression)
The approach is conceptually simple: it chooses where to abstain so as to minimize the upper-bound on test loss LV,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 partieular, the ellipsoid algorithm is used, though simpler algorithms would suffice
The question then becomes, how difficult is to find a function in F that maximizes loss. For classification, this can be done using an ERM oracle and a Lubel-flipping "trick" used by [10]. For linear regression, this can be done 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.
PPrceptron like algorithms would suffice as require only optimization polynomial (not exp.) accuracy.
7

---

Algorithm MMA
Input: x, X", E Y", h: X + Y, and approximate foss-maximizer O Output: a E (0, 1]
Find and output point in convex set K:
å [0. 1]" L)
min (V. 1/m a
by running the Ellipsoid algorithm using the following separation oracle SEP(a) K:
1. If a & [0, 1J", ie., a, $ [0, 1], then output unit vector with ;; 1 a; ; -
< 0.
2. Otherwise, output separator
V ((g(a)))))) where = h, a). l/ge VS(x, maximizes (g h a) to within 1/(3n).
: (c ((g(21), (.C
Figure 2:
The reduction MMA for computing abstention probabilities using approximate loss maximization oracle O whose output E y) maximizes (x(g, h, a) to within 1/3n. Ellipsoid runtime analysis in Lemma
Fractional abstention. Loss may be slightly lower if one is allowed fractional abstentions, or cquivalently to abstain at random. This be described by probability a, [0, for each test example I;, which indicates that we abstain with probability a, and classify according to with probability 1 a,, As described in the introduction, the definitions of l and L are extended to fractional abstention vectors a [0, 1]"d in the natural way:
Ex (x h. a)
Σ aec (1-a; (x) and L, a) max (x a).
gEV
Our task is to optimize abstention given a fixed h and x and a fixed set of candidate function 9 E (e.g.. version space), assuming one can maximize loss, i.e. find g E V realizing maxgev E(g, h, hV,
Lemma 3 (Reduction). For any bounded loss E Y + 0, 1]. any V == VS(X,)) C Y any h: + Y. and any x E X", the Ellipsoid algorithm can be used in MMA to find à such that,
LV h. < min LV, 1
in poly(n) time and calls approximate loss maximization oracle O provided that its outputs = -(x,y, h, a) all satisfy Ex(g. h, a) 2 maxgev Ex(g', h, a) 3n'
This can be done using any standard optimization algorithm, c.g., the ellipsoid algorithm, with O serving as separation oracle. Optimizing to within less than 1/n. is not generally significant for learning purposes. Note that the Ellipsoid method more commonly defined with separation- membership oracle that either claims membership in the convex set K or finds a separator. As we describe in Appendix [.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.
4 Binary classification
For the case of binary classification, the version space defined as follows:
VS(X, = tg E F g(x,) y/ for all < n).
We can use generalization bounds on (VS(X y). It) to get directly:
Theorem 5 (Adversarial classification loss). For = (0, 1}, = VC(F), f(y.0) () =ly ly 5
any E N, 8 > 0, the following holds with probability 1 over 8, pm; For all

---

h E VS(X, f(x)), E X", and all A E earg Lin f(x)), h, A),
AC
2d 2n + lg 1/26
A 5 [i [i: # x
Proof. This follows directly from Lemma and generalization bound Lemma of Appendix
Covariate shift bounds for classification were stated in Theorems I and 2 Next, observed in prior
work [1O], for binary classification with the 0-1 loss, one can use an ERM oracle which minimizes loss maximize loss as needed above. This algorithm is called FLIP.
Lemma 4 (FLIP). For Y = (0,1) with E(y, 9) ly أن and any h E. and any E [0, 1]"
h(x) E Y".
9 ERM (4n² copies of (Ts, Tc) and [3n(1 a:) copies of (xi, 1 h(xx)), for each i)
satisfies E VS( y) and Ex 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 (āi, yt) and number of copies proportional 1 a, of each Slipped test example (ar4, y1 Then the classifier output by ERM is in the version space with training error, due to the high weight of each (æ,, Øt), 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
5 Regression
In this section, we = and use the squared loss function E y2 R2, f(y, = (y- ;) For regression, since labels noisy, will not be able use exact version space and instead will need to define an a-approximate version space for a 2 0: VS, h) = {g E F (x(g h)) S a}. For classes F that are convex and have bounded "Rademacher complexity", the version space can be bounded (cf. Section 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 ÿ, 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 = {a|x IRd || < 1} and Y = For R 0, let FR {z + w- x w E Rd, ||w||| < R} be the class of linear function from X + Y parametrized by vectors with norm bounded by R. Let := F1.
In order to design an efficient algorithm, we will use an oracle to solve the Celis-Dennic Tapia problem (CDT): min min( (n (x)
< 0, (ar) 0, Rd), where f is quadratic function, (x(x) < for = 1,2 define ellipsoids and at least one of gı, 92 is strictly convex. For readability, in the lemma below,
will assume that have oracle access exactly solve this problem. Theorem 1.3 [3] shows that this problem can be solved in time polynomial in the bit complexity and log(s-1), achieve a solution that is within an additive factor of the optimal and each of the constraints may violate feasibility by additive factor of e. 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 rumning time is polynomial in (o((//c), choosing an smaller than the bounds obtained by the learning algorithm suffices. The details are provided in Appendix H
Lemma (Regression loss maximization). For X, Y, E 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 X y", X", O, and [0, 1)ah there exists a polynomial time algorithm that outputs E VS (x, h) such that Ex(ğ, h, a) = Lx (VSS (x,h). a))
6 Conclusions
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 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 generalize the abstention model to online and possibly agnostic settings, or at least understand the limits. GKKM showed a lower bound of ((VOPT) for one agnostic model, though it is not clear what the right agnostic model is. Finally, would be interesting to 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 if one knows the unknowns.
7 Limitations and Societal Impact
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 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 classifier abstained a human.
References
[1] Andrew Arnold, Ramesh Nallapati, and William W Cohen. A comparative study of methods for transductive transfer learning. In Seventh IEEE international conference on data mining workshops (ICDMW 2007), pages 77-82. IEEE, 2007.
[2] Peter L Bartlett and Marten H Wegkamp. Classification with a reject option using a hinge loss. Journal of Machine Learning Research, 9(8), 2008.
[3] Daniel Bienstock. A note on polynomial solvability of the CDT problem. SIAM Journal on Optimization, 26(1):488-4) 498, 2016
[4] Olivier Bousquet and Nikita Zhivotovskiy. Fast classification rates without standard margin assumptions. Information and Inference: A Journal of the IMA, 04 2021. ISSN 2049-8772. doi: 10.1093/maiia//aaab000 URL URLhttps :tttpp:://or //doi. org 10. 1093/ htt///mmaaiiiaaban
[5] M. R. Celis, J. E. Dennis, Jr., and R. A. Tapia. A trust region strategy for nonlinear equality constrained optimization. Numerical Optimization 1984, pages 71-82, 1985.
[6] Chi- Chi-Keung Chow. An optimum character recognition system using decision functions. IRE Transactions on Electronic Computers, 4:247-254, 1957.
[7] Corinna Cortes, Yishay Mansour, and Mehryar Mohri. Learning bounds for importance weighting. In Advances in Neural Information Processing Systems, volume 23, pages 442-450, 2010.
[8] Corinna Cortes, Giulia DeSalvo, and Mehryar Mohri. Learning with rejection. In International Conference on Algorithmic Learning Theory, pages 67-82. Springer, 2016
[9] Yicheng Fang, Huangqi Zhang, Jicheng Xie, Minjie Lin, Lingjun Ying. Peipei Pang, and Wenbin Ji. Sensitivity of chest et for 19v Comparison to rt-per. Radiology, 11--111115--111, 2020. doi: 10. 148/radiol. 201220003...222
PMID: 32073353.
[10] Shafi Goldwasser, Adam Tauman Kalai, Yael Tauman Kalai, and Omar Montasser. Selective classification algorithms provably robust to arbitrary adversarial examples. In Advances in Neural Information Processing Systems, 2020. URL https: /tttps:///rxiiv arxiv org/abs.s/.ooo 2207 .51445
10

---

[11] lan J. Goodfellow, Jonathon Shlens, and Christian Szegedy. Explaining and harnessing adversar- ial examples. Proceedings of the 3rd International Conference on Learning Representations. ICLR, 2015. httt::tppppp/t// httpaawwwwi.gaiiaaaaaa/a abs/ 1412. 6572
[12] Martin Grötschel, László Lovász, and Alexander Schrijver. Geometric algorithms and combina- torial optimization, volume 2. Springer Science & Business Media, 2012.
[13] Lihong Li, Michael L Littman, Thomas J Walsh, and Alexander L Strehl. Knows what it knows: a framework for self-aware learning. Machine learning, 82(3):399-443, 2011.
[14] Yishay Mansour, Mehryar Mohri, and Afshin Rostamizadeh. Domain adaptation: Learning bounds and algorithms. In COLT 2009 The 22nd Conference Learning Theory, Montreal, Quebec, Canada, June 18-21, 2009, 2009. URL http: /www cs http://ww....glll..aaaaaaaaaaa/a cat..llot//////0000000... papers/003 http:/000...pfppaeepee..ee
[15] Mehryar Mohri, Afshin Rostamizadeh, and Ameet Talwalkar. Foundations of machine learning. MIT press, 2018.
[16] Joaquin Shionero-Candell Masashi Sugiyama, Anton Schwaighofer, and Neil D Lawrence. Dataset shift in machine learning. The MIT Press, 2009.
[17] Ronald L.. Rivest and Robert H. Sloan. Learning complicated concepts reliably and usefully (extended abstract). In Tom Mitchell and Reid Smith, editors, Proceedings AAAI-88, pages 635-640, AAAI, 1988.
[18] Amin Sayedi, Morteza Zadimoghaddam, and Avrim Blum. Trading off mistakes and don't t-know predictions, In Advances in Neural Information Processing Systems, pages 2092-2100, 2010.
[19] Christian Szegedy, Wojeiech Zaremba. Ilya Sutskever, Joan Bruna, Dumitru Erhan, lan Goodfel- low, and Rob Fergus. Intriguing properties of neural networks. In 2nd International Conference on Learning Representations, ICLR 2014, Conference Track Proceedings, 2014.
[20] Vladimir N. Vapnik. Statistical Learning Theory. Wiley-Interscienee 1998.
[21] Kan Yuan, Di Tang, Xiaojing Liao, Xiaofeng Wang, Xuan Feng, Yi Chen, Menghan Sun, Haoran Lu, and Kehuan Zhang. Stealthy porm: Understanding real-world adversarial images for illicit online promotion. 2019 JEEE Symposium on Security and Privacy (SP), pages 952-966, 2019.
Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes]
(c) Did you discuss any potential negative societal impacts of your work? [Yes] See introduction.
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes] In supplementary materials.
3. If you ran experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or URL)? [N/A]
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [N/A]

---

(c) Did you report error bars (e.g., with respect to the random seed after running experi- ments multiple times)? [N/A]
(d) Did you include the total amount of compute and the type of resources used (c.g., type of GPUs, internal cluster, cloud provider)? [N/A]
4. If you are using existing assets (e.g., code, data, models) or curating/releasig new assets...
(a) If your work uses existing assets, did you cite the creators? [N/A]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either in the supplemental material or as URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you're using/curating? [N/A]
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, applicable? [N/A]
(b) Did you describe any potential participant risks, with links Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
12


Reviews:
[{"review_id": "n5o91NbJxu2", "reviewer": "Reviewer_zQKS", "summary": "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.", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The paper uses a general reduction algorithm for computing the min-max abstention. The paper minimizes Chow's loss with an efficient reduction to loss maximization using a separation oracle. Learning with covariate shift and adversarial examples is a significant research question, and modeling with reduced cost of abstention may be useful in some cases. The comparison to prior work GKKM20 and a summary of the results is clearly stated.\n\nLimitations: The use of Chow's risk model gives faster convergence than GKKM20 which the current paper references throughout. However similar fast convergence is also known in prior work using Chow's risk in standard learning (without covariate shift) in [1] below which the authors do not cite. It would be useful to understand how the techniques differ. Also it is unclear to me in what sense are the bounds optimal, since there do not seem to be any lower bounds. The min-max approach is conceptually straightforward and use prior work as oracles. For the binary classification the reduction is polynomial time, but still depends on an ERM.\n\n[1] O. Bousquet, N. Zhivotovskiy. Fast classification rates without standard margin assumptions, 2021. Information and Inference: A Journal of the IMA\n\n-----------------------------\nPost rebuttal edit:\n\nI thank the authors for their response and have increased my rating. While it is still a concern for me that an important related work was missed by the authors, the additional clarifications and changes proposed by the authors are useful. I also suggest adding a paragraph or section discussing limitations of the work (as suggested in NeurIPS guidelines).", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "I did not find a discussion of limitations, potential societal impact is reasonably addressed.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "mUFzjQnWdpv", "reviewer": "Reviewer_5Vsa", "summary": "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. \n\nThey 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. \n\nIn 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. \n\nThey 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. ", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "This paper provides an elegant formalism along with a relatively decent performing algorithm. It is a non-trivial result that also leaves a lot of room for further work. I also find this abstraction particularly relevant to the open problem of defending against adversarial examples, which can be thought of as a form of OOD generalization.\n\nThere are a few smaller ideas in the paper I liked a lot as well. For example, if the test risk was defined with respect to a single o.o.d point, it would be difficult to make much progress as a single point could plausibly be drawn from any distribution. By having the algorithm simultaneously label $n$ points, it is able to adopt deeper strategies about when it chooses to abstain, and when it chooses to label. In particular, it feels important that the algorithm is able to learn from a new test distribution by just seeing unlabeled examples. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2 hours"}, "extra_text": {}}, {"review_id": "aS5dAgp3jD0", "reviewer": "Reviewer_UTdk", "summary": "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.", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The paper builds upon GKKM to study selective classification and regression, with adversarial test examples and covariate shift.\nIt provides not only bounds for test loss, but also an efficient algorithm for abstaining in linear regression and an efficient reduction for binary classification. Although there is little empirical verification, the results provide decent theoretical value.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Without concrete examples, it is hard to understand why the proposed algorithm and all the theorems are important. Besides, it may be better to describe in the beginning what the problem/challenge is that the paper tries to tackle, instead of directly diving into details. Empirical evaluation to demonstrate the importance of the theoretic results and to show the effectiveness of the proposed algorithm will also be highly helpful.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "Kw8N2MAvsZ", "reviewer": "Reviewer_Lekf", "summary": "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.", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The paper is well-written, with clear motivations and comparison with previous works. The theoretical parts are rigorous, and the proofs are modularized and easy to follow. There are a few weaknesses:\n\n1. The algorithms only work for linear models, and do not seem to be able to generalize to more expressive models.\n2. Techniques for binary classification are mostly from Goldwasser et al., although the ellipsoidal algorithm for regression is new.\n3. The algorithms rely on poly(n) calls to an ERM procedure on poly(n) examples, which may be time-consuming in practice.\n\nTypos:\n1. Line 323.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "N/A", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper considers a setting in which one may have different train/test distributions, but the predictor can choose to abstain at a cost of \alpha. All reviewers believed that the results were interesting, non-trivial, and clearly-stated, and all four recommended acceptance. What criticisms there were were adequately addressed in the author response.

Please be sure to make any changes that have been promised to the reviewers, and seriously consider attempting to address any other concerns that they might have raised, in particular  UTdk's request for concrete examples.
Decision: Accept (Spotlight)