Boosting with Abstention
We present a new boosting algorithm for the key scenario of binary classification with abstention where the algorithm can abstain from predicting the label of a point, at the price of a fixed cost. At each round, our algorithm selects a pair of functions, a base predictor and a base abstention function. We define convex upper bounds for the natural loss function associated to this problem, which we prove to be calibrated with respect to the Bayes solution. Our algorithm benefits from general margin-based learning guarantees which we derive for ensembles of pairs of base predictor and abstention functions, in terms of the Rademacher complexities of the corresponding function classes. We give convergence guarantees for our algorithm along with a linear-time weak-learning algorithm for abstention stumps. We also report the results of several experiments suggesting that our algorithm provides a significant improvement in practice over two confidence-based algorithms.
The papers considers a new boosting algorithm for classification with abstention. In each round, the algorithm selects a a base learner which is a pair of functions (h(x),r(x)), where h concerns classification into positive/negative labels, while r indicates the abstention region. The paper contains extensive theoretical analysis of the proposed approach, including: convex surrogates for the proposed loss function, calibration of exponential-loss convex surrogate, generalization bounds by means of Rademacher complexity, derivation of the boosting algorithm and its convergence guarantees. A short experimental study concludes the paper. 
The paper presents an interesting, and (to the best of my knowledge) novel approach to binary classification with abstention. The standard approach to this problem is via confidence-based abstention: "estimate" the class conditional probability function \eta(x) (or some monotonic transformation thereof) and reject (abstain from classification) when \eta(x) is close to 1/2. The authors points out that while this is all that is needed to find the optimal solution in the class of all classification functions (because the Bayes solution is of that form), in practical cases, when the class of functions is constrained, it can be beneficial to use a more general approach, where there are two functions, h and r, h being responsible for classification, and r -- for deciding upon rejection.  The paper contains various theoretical results concerning the proposed approach: - Convex surrogates for the original (task) loss function, with the proof of calibration of exponential convex surrogate, - Guarantees on the generalization error of the ensemble by means of the convex surrogate and the Rademacher complexity of the function class which depends on the Lipschitz constant of the convex surrogate (truncated at 1), - Derivation of new boosting algorithms based on the proposed convex surrogates using the method of projected coordinate descent, - Proof of the convergence of the projected coordinate descent, - A new type of based learner suitable for this problem -- abstention stumps, together with a method for fast selection of the optimal stump at each iteration. - A short experimental study, which is actually the weakest part of the paper due to small size of the data sets used for the comparison.  The paper is generally clearly presented, but due to numerous theoretical results, it is quite dense. I have some minor suggestions on the presentation (below) that may help the final version.  Overall, I think the contribution of the paper is strong. I am in favor of accepting it.  Minor suggestions:  l. 68: "part of our analysis is applicable to the general case" -- please explain which part. l. 82-84 and Fig. 1: the Bayes solution is not unique here. l. 98-99: repeated sentence ("ham based on the presence of some other word") l. 60, 69, 105: unify notation for open and closed intervals eq. between lines 113-114: h(x)) -> h(x) l. 121: I think it better to write \Phi_1(x) = \Phi_2(x) = \exp(x)  Theorem 1: it is not clear what are h^* and r^* -- is (h^*,r^*) a Bayes classifier for the task loss L? Also the proof of Theorem 1 is unclear. In l. 467 (Appendix): in fact when \eta(x) \in {0,1}, there is no minimizer (for example, when \eta(x)=1, the infimum is attained by r(x) -> infinity and h(x) - r(x) -> infinity). Furthermore, in l. 476-477 (Appendix) you write that the Bayes classifier (of the task loss L?) satisfies h^*(x) = \eta(x) - 1/2 and r^*(x) = |h^*|-1/2+c, but this is not true. In fact there exists Bayes classifier which satisfies that, but this is not the only one: any (h^*, r^*) is a Bayes classifier as long as sgn(h^*) = sgn(eta(x)) and sgn(r^*) = sgn(|\eta(x)-1/2|-1/2-c). This is satisfied for the solution of the surrogate if and only if b/a = 2sqrt((1-c)/c), so Theorem 1 is correct, but I think the proof should be improved.  Theorem 2: explain the notation -- R is the Rademacher complexity (define it in the Appendix to make it more self-contained).  Theorem 2: Perhaps you could add a comment below Thm 2 that it also applies to L_SB since it is an upper bound on L_MB (similar to the comment below Corollary 3)  Figure 3: (algorithm) It is unclear, what are the parameters of the algorithm. From what I understand, they are c and \beta? I would suggest to say anything about the role of \beta in the algorithm (from what I understand, it acts as a regularization strength).  Experiment: it is not explicitly stated what kind of convex surrogate is used in the BA algorithm. I guess this is exactly the algorithm presented on Figure 3 (with exponential loss, L_SB-type).  ==========  I have read the rebuttal which clarified most of the issues raised in my review.