A Universal Growth Rate for Learning with Smooth Surrogate Losses

Thank you for your appreciation of our work. Please find our detailed responses below.

Questions: 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)?

Response: We have discussed some practical implications of our analysis in Section 6 and Appendix H.

In practice, in realizable or nearly realizable cases where minimizability gaps are zero or relatively small, we believe that the logistic loss is a favorable choice because it is advantageous for optimization and its bound is independent of the number of classes. This in fact can partly explain its widespread practical application.

In other scenarios, both the number of classes and the minimizability gaps are essential in loss selection and a good choice out of the family of comp-sum losses might suggest a parameter $\tau$ closer to 2.

More generally, our theoretical analysis can help in selecting surrogate loss functions by considering several factors related to their $H$-consistency bounds:

• Their growth rate. For example, the growth rate for polyhedral surrogate losses is linear, while it is square-root for smooth losses.
• Their optimization property. For example, smooth losses are more favorable for optimization compared to polyhedral losses, particularly with deep neural networks.
• Their functional form. For example, comp-sum loss functions can vary in their forms of $H$-consistency bounds due to the dependency on the number of classes (see Section 6).
• Their approximation property. For example, the minimizability gaps differ in $H$-consistency bounds for smooth surrogate losses, even with the same growth rate (see comparison in Section 6). Also, under certain conditions, minimizability gaps can be zero or close to zero.

For smooth loss functions, in particular comp-sum losses, please see further our discussion in Section 6.2.

Thank you for your appreciation of our work. Please find our detailed responses below.

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.

Response: Indeed, smooth surrogate loss functions are the most commonly used ones in current training of neural networks. Our focus on smooth surrogate loss functions was also motivated by the fact that the prior work of Frongillo and Waggoner (2021) implies a linear growth rate for polyhedral losses. In Appendix G, we give a brief discussion comparing polyhedral losses with smooth losses.

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.

Response: Completeness means that for any instance, the set of possible scores generated by a hypothesis set spans $\mathbb{R}$. This condition is met by common hypothesis sets, for instance the family of all linear models, $H_{\mathrm{lin}} = \\{ (x,y) \mapsto W_{y} x + b_{y} \\}$, or that of multi-layer neural networks, $H_{\mathrm{NN}} = \\{ (x, y)\mapsto u_y \cdot \rho_{n}(W_{y, n}(\cdots \rho_2(W_{y, 2} \rho_1(W_{y, 1} x + b_{y, 1})+b_{y, 2})\cdots)+b_{y, n}) \\}$, where $\rho_j$ is an activation function.

More broadly, our analysis and results can be extended to bounded hypothesis sets even when completeness is not satisfied. This can be done by leveraging the characterization of the error transformation function given by Awasthi et al. [2022b] and Mao et al. [2023b] without assuming completeness.

We expect that the square root growth rate still holds in bounded cases for smooth surrogate losses. This is because, for bounded hypothesis sets, the estimation error transformation function typically admits two segments; however, our primary focus is on the segment where $t$ is close to zero, which aligns with the complete case. Thus, a similar analysis can be applied in these situations as well. We will elaborate on this in the final version.

Thank you for your appreciation of our work and for your suggestions to improve its readability. Please find our detailed responses below.

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.

Response: Thank you for your suggestions. We will continue to work on improving our presentation for readers. The addition of one extra page in the final version will also allow us to include more detailed discussions of the motivation, implications, and proof techniques in the main body.

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?

Response: $H$-consistency bounds hold for all predictors $h$ in the hypothesis set $H$ considered and for all distributions. We provide a tight analysis of their growth rate for smooth surrogate losses in both binary and multi-class classification, demonstrating that it follows a square-root function.

We suspect the reviewer refers to these square-root growth rate bounds as "local bounds" and is inquiring about "global bounds" that do not rely on growth rates. Previous works by Awasthi et al. (2022a,b) and Mao et al. (2023b,e) offer precise global bounds for both binary and multi-class classification across various commonly used loss functions, along with general methods for deriving such bounds. Our paper focuses on analyzing the growth rate of any of these bounds for smooth loss functions.

Please let us know if we are not answering the question appropriately, as we are unsure about what meant. Thank you.

2. Can the authors provide more insights on how these bounds help us select surrogate functions?

Response: Our theoretical analysis assists in selecting surrogate loss functions by considering several factors related to their $H$-consistency bounds:

• Their growth rate. For example, the growth rate for polyhedral surrogate losses is linear, while it is square-root for smooth losses.

• Their optimization property. For example, smooth losses are more favorable for optimization compared to polyhedral losses, particularly with deep neural networks.

• Their functional form. For example, comp-sum loss functions can vary in their forms of $H$-consistency bounds due to the dependency on the number of classes (see Section 6).

• Their approximation property. For example, the minimizability gaps differ in $H$-consistency bounds for smooth surrogate losses, even with the same growth rate (see comparison in Section 6). Also, under certain conditions, minimizability gaps can be zero or close to zero.

For smooth loss functions, in particular comp-sum losses, please see further our discussion in Section 6.2.

Thank you for your encouraging review. We have carefully addressed all the questions raised. Please find our detailed responses below and let us know if there is any other question.

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 consistency based bound contains the term minimizability gap which was not existent in the previous work that I cited.

Response: The results of Bartlett et al. (2006) hold only for the family of all measurable cases, that is for $H = H_{\mathrm{all}}$. They also focus exclusively on binary classification (other studies, such as those of Tewari and Bartlett (2007) and Zhang (2004) analyze certain multi-class classification loss functions).

In contrast, $H$-consistency bounds hold for arbitrary hypothesis sets. They provide the tightest possible upper bound on the estimation error for the actual loss, such as the zero-one loss, in terms of the surrogate estimation error, for an arbitrary hypothesis set $H$. They admit as special cases the excess bounds of Bartlett et al. (2006) in binary classification, when setting $H$ to $H_{\mathrm{all}}$.

For the more realistic scenario where the hypothesis set $H$ does not include all measurable functions, as demonstrated in Appendix C, under general assumptions, minimizability gap terms appear. These are necessary terms to relate the surrogate estimation error to the actual estimation error. In the special case $H = H_{\mathrm{all}}$, minimizability gaps vanish. They are also zero in realizable cases.

Thus, $H$-consistency bounds provide a strict generalization of previous work, needed to analyze the standard case where $H$ does not include all measurable functions. Our paper further provides a detailed analysis of minimizability gaps.

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?

Response: This is a very good question. It is well-established that local Rademacher complexity or small ball methods can be used to derive fast rate generalization bounds under Tsybakov noise conditions. Remarkably, under the same conditions, indeed, one can also derive more favorable $H$-consistency bounds (as shown in our concurrent work), that is with better exponents. Combining both yields more favorable generalization bounds on the actual loss, as suspected by the Reviewer. We will elaborate on this in the final version.

More generally, more favorable $H$-consistency bounds can be derived under various distributional assumptions.

3. 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 equality. Am I missing something?

Response: Like excess error bounds, $H$-consistency bounds are worst-case bounds that hold for any distribution. As noted in Lines 232-235, estimation error transformation functions provide tight $H$-consistency bounds. This means that for any $t \in [0, 1]$, there exists a hypothesis $h \in H$ and a distribution such that the inequality of the bound can be achieved. Thus, a square root growth rate for transformation functions implies a square root growth rate of estimation errors in the worst case.