- Rating
- 4
- Confidence
- 3
- Informativeness
- 3
- Presentation
- 3
- Soundness
- 3
Read review
Paper summary
This paper extends the classical paper Lei (2014) "Classification with Confidence": under the ambiguity minimization problem subject to controlled positive and negative errors, the authors consider to deal with the surrogate risks of the ambiguity, positive, and negative errors, instead of Lei's plug-in classifiers. The paper progresses as follows: Section 3 discusses the generalization analysis of this problem under the 0-1 loss, Section 4 discusses its minimax lower bound, Section 5 discusses the surrogate generalization analysis, and Section 6 discusses SGD complexity. Finally, the proposed method is instantiated with a linear/MLP classifier with the hinge/squared-hinge losses, tested against Lei's approach, achieving lower ambiguity overall.
Critical strengths
- The paper is clearly written and well-organized. The paper structure "generalization analysis of 0-1 loss => lower bound => generalization analysis of surrogate loss => optimization" is very clear. Each section is concisely summarized with transparent mathematical backgrounds. Moreover, the lower bound proof is nicely illustrated in the main body.
- Well-motivated and natural extension of Lei (2014). While it is a bit surprising that nobody has extended Lei's plug-in classifier to the surrogate framework during the past decade, this work did it. This is not merely a straightforward extension but needs some discussions on the additive and multiplicative structures to aggregate positive and negative classifiers (in Definition 4), which is also nice.
Critical weaknesses
- Not very surprising techniques. The generalization analysis of the 0-1 loss and surrogate losses follows the standard approaches based on the Rademacher complexity. The analysis itself does not carry a lot of new techniques. The lower bound analysis may need a smart construction of the hard instance, which is not very immediate. The optimization guarantee is also standard; instead of dealing with heavy-tailed noises, bounded noises are supposed, which leads to the basic guarantee.
- Note that I would not say this undermines the contributions of this paper; what is solved in this paper is already great enough.
- The classification error controls are sometimes violated in practice. By looking at Table 1, and are sometimes larger than the prespecified budgets , under for example, MLP/hinge/Add. and MLP/hinge/Prod. of Vertebral Column---actually, this is the case for Lei's approach as well, though. Can we have some discussions? Given Theorem 4, the violation could possibly come from the excess error , which can be controlled in theory by using a large sample or controlling the Lipschitz continuity etc. Can any of these mitigate the constraint violation? Hopefully this point becomes another advantage over Lei's approach because we do not need the hypothesis space is well-specified.
Questions for authors
I don't have many questions. Just a few minor comments follow:
- In L.132, I don't think the subscript is necessary for the candidate region . The same applies to L.185, .
- In L.187, does "slack parameters and " indicates and , respectively?
- In L.231, the spacing is strange at "... determines ,in each pair ..."
- In L.263, should it be in the lower side of the inequality, instead of ?