A Universal Growth Rate for Learning with Smooth Surrogate Losses

Summary

This paper analyzes the growth rate of the H-consistency bounds (which subsume excess risk bounds) for various smooth surrogate losses commonly used in binary and multiclass classification. Specifically, for binary classification, the work establishes a tight square-root growth rate near zero (under mild conditions) for margin-based surrogate losses. For multiclass classification, the work establishes a tight square-root growth rate near zero (under mild conditions) for two families of surrogate losses: comp-sum and constrained losses. Finally, the work also studies how the number of classes affects these bounds, as well as the minimizability gaps in the bounds.

Strengths

**Originality** A comprehensive analysis of the growth rate of the H-consistency bounds (which subsume excess risk bounds) for various smooth surrogate losses commonly used in binary and multiclass classification: - For binary classification, the work establishes a tight square-root growth rate near zero (under mild conditions) for margin-based surrogate losses (Theorem 4.2). In particular, the lower bound requires weaker conditions than [Frongillo and Waggoner, 2021, Theorem 4], and the upper bound is new. - For multiclass classification, the work establishes a tight square-root growth rate near zero (under mild conditions) for two families of surrogate losses: comp-sum and constrained losses (Theorems 5.3 and 5.5). Related work has been properly cited. **Quality** The work is technically sound. Proofs are given for theoretical results. **Clarity** The paper is clearly written and well-organized. Although it is a bit dry, as a researcher working in the related field, I did not find it very hard to read. **Significance** The comprehensive analysis presented in this work promotes a deeper understanding of different surrogate losses. It is helpful for researchers studying surrogate losses and consistency.

Weaknesses

I did not find any obvious weaknesses.

Questions

1. Based on this work, do you have any concrete suggestions for practitioners to choose surrogate losses (assuming they do not know about H-consistency at all)?

Rating

8

Confidence

4

Soundness

4

Presentation

3

Contribution

4

Limitations

The authors have adequately addressed the limitations.

Summary

Since optimizing zero-one loss is intractable and it does not have properties such as differentiability, a common approach in learning theory is to replace it with a surrogate loss function. H-consistency bounds relate the excess error for surrogate loss to zero-one loss. This paper establishes a square-root growth rate near zero for smooth surrogate losses in binary and multi-class classification, providing both upper and lower bounds under mild assumptions.

Strengths

The paper proves both upper and lower bounds for H-consistency with smooth surrogate losses. Previous results only provided lower bounds, but this paper presents lower bounds with fewer conditions and also shows a matching upper bound of the square root, applicable to both binary classification and multiclass classification, such as Comp-sum losses.

Weaknesses

The paper studies only smooth surrogate losses, not piecewise linear ones such as hinge loss. However, using smooth surrogate loss functions is very common in machine learning applications.

Questions

The results are based on the assumption that the hypothesis class is complete. Can you explain why this condition is necessary and what happens to the growth rate when this is not satisfied? It seems that many practical hypothesis classes don't meet this condition.

Rating

7

Confidence

3

Soundness

3

Presentation

3

Contribution

3

Limitations

The paper does not have any potential negative societal impact.

Summary

This paper presents a comprehensive analysis of the growth rate of H-consistency bounds (and excess error bounds) for various surrogate losses for some intractable loss used in classification. The authors prove a square-root growth rate near zero for smooth margin-based surrogate losses in binary classification and comp-sum and constrained loss used in multi-class classification, providing both upper and lower bounds under mild assumptions.

Strengths

The paper provides solid analysis for the H-consistency and excess error bound and these provide good guidance for selecting good surrogate loss for classification tasks where the target loss is hard to optimize. The theoretical analysis is novel and provides good insight for handling intractable target loss.

Weaknesses

The paper should provide a more intuitive statement on the motivation and implication of these error bounds and provide more insights about the proof.

Questions

1. The error bounds are local bounds. Can the author provide insights on how to have global bounds and the neighborhood for the local bounds to hold? 2. Can the authors provide more insights on how these bounds help us select surrogate functions?

Rating

7

Confidence

2

Soundness

3

Presentation

3

Contribution

3

Limitations

N/A

Summary

The paper provides an analysis of the growth rate of H-consistency bound for surrogate losses in binary and multi-class classification. The authors prove square root growth rate near zero for smooth margin-based surrogate losses for binary classification as well as for smooth comp-sum and constrained losses for multiclass classification. Since minimizability gaps makes a big difference between the bounds of different surrogates, the authors also analyze these gaps to guide in selecting better surrogates. In section , the authors introduce H consistency bounds and they build upon this to derive results for binary and multi-class classification in later sections.

Strengths

I must say, I am not an expert in this area of research. I find this paper pretty well written. In theorem 4.2, the authors prove that the transformation function tau is precisely of the order t^2 for a class of margin based loss function that is smooth and follows some other properties as mentioned in the main statement. Hence, the growth rate for these loss functions is precisely square-root. Further, the authors derive similar result for multiclass classification for comp sum losses and constrained losses. Because there is a minimizability gap term in the H consistency bound hence even with identical growth rates, surrogate losses can vary in their H-consistency bounds. The authors show that in the case of multiclass classification, minimizability gap scales with number of classes.

Weaknesses

I have a few very basic questions, regarding the work. 1. I understand that H consistency-based bound helps convert a surrogate-based bound to a bound that we require. How is it an improvement over earlier work Bartlett et al. (Convexity, Classification, and Risk Bounds). H consistence based bound contains the term minimizability gap which was not existent in the previous work that I cited. 2. I also understand that the faster the bound for surrogate loss will be, the better bound for the actual loss could be obtained. However, I am wondering if we provide a fast rate using small ball method or local Rademacher complexity based method for the surrogates, under what conditions the fast rate for the actual loss can still be recovered or is it lost always ? It would be also great if you could explain simply the implications of getting a precise rate for the transformation function as I understand it might not give you a lower bound on the estimation error because of equation 2 is not an eqaulity. Am I missing something? I am currently giving it a borderline accept and am happy to reconsider it after the rebuttal.

Questions

See above.

Rating

5

Confidence

2

Soundness

3

Presentation

3

Contribution

3

Limitations

See above.

Increase my rating to 8

Thank you for the responses. I think this work is solid and of significant value to the learning theory community. I want to increase my rating to 8, reflecting its significance.