Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 8: Top 50% of accepted NeurIPS papers, clear accept
review_content: 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. 

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. 
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.

There 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. 
limitations_and_societal_impact: Yes.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: 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.
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.

Limitations: 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.

[1] O. Bousquet, N. Zhivotovskiy. Fast classification rates without standard margin assumptions, 2021. Information and Inference: A Journal of the IMA

-----------------------------
Post rebuttal edit:

I 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).
limitations_and_societal_impact: I did not find a discussion of limitations, potential societal impact is reasonably addressed.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: 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.
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:

1. The algorithms only work for linear models, and do not seem to be able to generalize to more expressive models.
2. Techniques for binary classification are mostly from Goldwasser et al., although the ellipsoidal algorithm for regression is new.
3. The algorithms rely on poly(n) calls to an ERM procedure on poly(n) examples, which may be time-consuming in practice.

Typos:
1. Line 323.

limitations_and_societal_impact: N/A
review_title: null

final_score: rating: 7: Good paper, accept
review_content: 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.
main_review: The paper builds upon GKKM to study selective classification and regression, with adversarial test examples and covariate shift.
It 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.
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_title: null

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)