Establishing Linear Surrogate Regret Bounds for Convex Smooth Losses via Convolutional Fenchel–Young Losses

Thank you for your helpful advice! The answers to the questions are summarized below, and we will integrate the discussions into the revised manuscript.

Q1. There exist typos, and the notations are confusing at times.

A1. Thank you for pointing out this issue! We will fix the typo at line 120. For the selector function and the related "$\pi$-argmax link", we will use $\mathbf{\sigma}$ as an alternative. For the dimension of encoding, we will use $D$ instead of $\varrho$ for clarity.

Q2. Are there other ways of systematically producing couplings between negentropy and target loss? If so, do some of these lead to less tractable losses?

A2. Thank you for your insightful question! Another systematic framework for combining target loss and a negentropy is also a special case of Fenchel--Young loss [1], where the prediction link is defined via a Bregman projection onto a polytope determined by the target loss. While this approach offers a broad and principled method for designing prediction links, the resulting surrogate regret bound remains of square-root type, as shown in Proposition 5 of [1]. In contrast, our proposed loss achieves a linear surrogate regret bound.

Q3. I was expecting a discussion of optimization tradeoffs. My understanding is that while polyhedral losses lacking smoothness may not achieve fast rates for excess risk, their structure should allow for faster optimization (except maybe in the stochastic optimization setting, assuming no interpolation).

A3. Thank you for your constructive advice! The standard analysis of the subgradient method implies that Conv-FY losses and polyhedral losses are optimized with convergence rates $O(1/T)$ and $O(1/\sqrt{T})$, respectively, where $T$ is the number of iterations. Beyond this, it is left open to exploit specific structures arising from polyhedral losses to achieve faster optimization.

[1]. Blondel, M.. Structured prediction with projection oracles. In NeurIPS, 2019.

Thank you for your constructive suggestions and acknowledgment! We summarize the answers to the questions below:

Q1. To help with the presentation, it is beneficial to add plots that give insight into the geometry.

A1. Thank you for the suggestion! A visualization for the binary margin loss case is provided in Appendix E, where we directly compare the proposed convolutional Fenchel–Young (Conv-FY) loss (generated by Shannon negentropy for binary loss) with the logistic loss. The appendix also illustrates the corresponding probability estimators induced by both losses. In the revised manuscript, we will further emphasize these plots.

Q2.  It is beneficial to comment on what inspired examining Convolutional Fenchel–Young Losses as a candidate loss which is smooth that satisfies linear regret rates.

A2. Thank you for the insightful suggestion! While the smoothness of Conv-FY losses follows from the classical duality between strong convexity and smoothness, and the linear regret bound leverages the regret decomposition induced by infimal convolution (as discussed around line 291), the more fundamental motivation stems from the interplay with Theorem 4 of [1]. Specifically, Theorem 4 shows that a smooth loss with local strong convexity around the decision boundary cannot achieve linear regret. In contrast, the Conv-FY loss is not locally strongly convex near the boundary, thereby breaking local strong convexity and circumventing this limitation. This key intuition is illustrated and elaborated in the “Further Discussions” section of Appendix E, and we will move it earlier into the main text in the revised manuscript to better motivate our approach.

Q3. Section 3.6 talks about a Fisher-consistent estimator. Could you add to the appendix a formal definition?

A3. Many thanks for your reminder! We will add a formal definition of the Fisher-consistent probability estimator in the Appendix that characterizes it as a function of $\mathbb{R}^\varrho\rightarrow\mathbb{R}^\varrho$.

[1]. Frongillo, R., and Waggoner, B. Surrogate regret bounds for polyhedral losses. In NeurIPS, 2021.

Many thanks for your valuable suggestions! We will fix the typos in the revised manuscript, and the questions and corresponding answers are summarized below:

Q1. It is beneficial to evaluate the proposed surrogate loss on multiclass classification benchmarks.

A1. Thank you for your advice! We evaluate the performance and report the validation accuracy of our proposed loss in Section 4 on the ImageNet-1k dataset [1] with ResNet-50 [2]. Our experimental setup follows the default configuration of the PyTorch ImageNet training script: we use SGD with a momentum of 0.9, training for 120 epochs with a mini-batch size of 256. The initial learning rate is set to 0.1 and divided by 10 every 30 epochs. For comparison, we also report results using the standard cross-entropy loss under the same configuration. All experiments are conducted using 8 GeForce RTX 4090 GPUs, and we report the average validation accuracy and running time per epoch over 5 runs.

Interestingly, our proposed loss slightly outperforms the standard cross-entropy loss in validation accuracy, as shown in the table above. This improvement is observed without any additional tuning, indicating the potential of our approach.

Q2. The interpretation that $T(p)$ is an affinely transformed Bayes risk of the target loss should be defined more precisely.

A2. Thank you for pointing out this issue! We will emphasize in the revised manuscript that this interpretation holds in the case that $p$ is in the convex hull of $\{\rho(1),\cdots,\rho(K)\}$, i.e., there exists $\eta\in\Delta^{K}$ that $p=\mathbb{E}{\small y\sim\eta}[\rho(y)]$. This interpretation also holds when $p=\rho(y)$,which is a special case of $p=\mathbb{E}{\small y\sim\eta}[\rho(y)]$ by setting $\eta =e_{y}.$

[1]. Deng, J., Dong, W., Socher, R., Li, L.-J., Li, K., and Fei-Fei, L. Imagenet: A large-scale hierarchical image database. In CVPR, 2009.

[2]. He, K., Zhang, X., Ren, S. and Sun, J. Deep residual learning for image recognition. In CVPR, 2016.

Thank you for your valuable suggestions! We summarized the questions and provide the responses below:

Q1. While this is primarily a theoretical paper, it would strengthen the practical relevance and validate the results from an empirical point of view to provide results of empirical evaluation.

A1. Thank you for your advice! To provide experimental evaluations for our proposed results, we use our proposed loss in Section 4 as an example and evaluate its accuracy on the ImageNet-1k dataset [1] with ResNet-50 [2]. Our experimental setup follows the default configuration of the PyTorch ImageNet training script: We use SGD with a momentum of 0.9, training for 120 epochs with a mini-batch size of 256. The initial learning rate is set to 0.1 and divided by 10 every 30 epochs. For comparison, we also report results using the standard cross-entropy loss under the same configuration. All experiments are conducted using 8 GeForce RTX 4090 GPUs, and we report the average validation accuracy over 5 runs.

Interestingly, our proposed loss slightly outperforms the standard cross-entropy loss in validation accuracy, as shown in the table above. This improvement is observed without any additional tuning, indicating the potential of our approach. Meanwhile, we also observes that the computation time for standard method and our method per epoch are similar, demonstrating the efficiency of our proposed loss. These results also confirm the compatibility of our loss with mini-batch and distributed optimization.

Q2. How do these losses behave under the stochastic setting of SGD with mini-batches?

A2. Thank you for your question! As observed in our experiment on ImageNet-1k, optimization with mini-batch SGD successfully renders a model with higher accuracy. Meanwhile, as reported before, our loss's computation time is similar to the standard cross-entropy loss, which validates the compatibility of our loss with mini-batches.

Q3. The computational complexity of the approach should be discussed in relation to standard loss computations.

A3. Thank you for your advice! The constant that dominates the computation complexity for both standard losses and our proposed losses depends largely on the type of tasks, and we analyzed three important tasks in our work: multiclass classification, classification with rejection, and multilabel ranking.

• In multiclass classification, the constant dominates the complexity is the class number $K$. As shown in Lemma 18 of Section 4, the time complexity of our proposed loss is $O(K \log K)$. This is due to a sorting operation, which can be optimized to $O(K)$ as noted in footnote 1 of [3]. Meanwhile, the standard cross-entropy loss has a time complexity of $O(K)$ that is dominated by the softmax computation. This indicates that the complexities of our loss and the standard loss are comparable. The experimental results on ImageNet-1k also support this, which shows similar per-epoch computation times.

• In classification with rejection, a similar time complexity $O(K)$ of our proposed loss is also analyzed in Lemma 22 of Appendix D.1. This matches to popular existing methods [4, 5] that requires a similar time complexity.

• For the task of multilabel ranking, the time complexity is often dominated by the number of labels/items to be ranked $\varrho=\log_2 K$. We analyzed them in Lemma 23 of Appendix D.2, and get a result of $O(\varrho\log\varrho)$, while existing methods [6,7]'s complexity is from $O(\varrho)$ to $O(\varrho^2)$.

We appreciate your comment and will move the time complexity discussions from the Appendix to the main body in the revised version to improve clarity.

Q4. Could you characterize problems where your approach would be inferior to existing methods? E.g., when $N$ is small or when computational resources are limited?

A4. Thank you for the thoughtful question! As noted in Theorem 13, a smaller number of prediction candidates $N$ actually leads to a tighter bound, and thus does not pose a disadvantage to our method. As for limited computational resources, while our loss involves slightly more structure, as discussed in A3, we have analyzed the time complexity of our loss and found it to be comparable to standard losses such as cross-entropy, both in theory and in terms of empirical runtime. Therefore, even in resource-constrained settings, we do not anticipate a clear disadvantage compared with existing losses.

A limitation may arise when we are interested in second-order optimization. While efficient first-order gradient oracle is provided in Lemma 12 and experimentally validated, the Hessian computation is not very straightforward, which is an interesting direction for future exploration.

[1]. Deng, J., Dong, W., Socher, R., Li, L.-J., Li, K., and Fei-Fei, L. Imagenet: A large-scale hierarchical image database. In CVPR, 2009.

[2]. He, K., Zhang, X., Ren, S., and Sun, J. Deep residual learning for image recognition. In CVPR, 2016.

[3]. Martins, A. and Astudillo, R. From softmax to sparsemax: A sparse model of attention and multi-label classification. In ICML, 2016.

[4]. Charoenphakdee, N., Cui, Z., Zhang, Y., and Sugiyama, M. Classification with rejection based on cost-sensitive classification. In ICML, 2021.

[5]. Cao, Y., Cai, T., Feng, L., Gu, L., Gu, J., An, B., Niu, G., and Sugiyama, M. Generalizing consistent multi-class classification with rejection to be compatible with arbitrary losses. In NeurIPS, 2022.

[6]. Menon, A. K., Rawat, A. S., Reddi, S., and Kumar, S. Multilabel reductions: what is my loss optimising? In NeurIPS, 2019.

[7]. Gao, W., and Zhou, Z. H. On the consistency of multi-label learning. In COLT, 2011.