Establishing Linear Surrogate Regret Bounds for Convex Smooth Losses via Convolutional Fenchel–Young Losses
Authors: Yuzhou Cao
Han Bao
Lei Feng
Bo An
Venue: NeurIPS 2025 spotlight ()
Keywords: Surrogate regret bounds
Excess risk bounds
Fenchel-Young losses
Primary area: theory
TL;DR: We construct a family of smooth convex loss with linear surrogate regret bounds via infimal convolution and Fenchel–Young losses, overcoming the smoothness–regret trade-off for arbitrary discrete target losses.

Abstract: Surrogate regret bounds, also known as excess risk bounds,
bridge the gap between the convergence rates of surrogate and target losses. The regret transfer is lossless if the surrogate regret bound is linear.
While convex smooth surrogate losses are appealing in particular due to the efficient estimation and optimization, 
the existence of a trade-off between the loss smoothness and linear regret bound has been believed in the community.
Under this scenario, the better optimization and estimation properties of convex smooth surrogate losses may inevitably deteriorate after undergoing the regret transfer onto a target loss.
We overcome this dilemma for arbitrary discrete target losses
by constructing a convex smooth surrogate loss,
which entails a linear surrogate regret bound composed with a tailored
prediction link. 
The construction is based on Fenchel--Young losses generated by the *convolutional negentropy*,
which are equivalent to the infimal convolution of a generalized negentropy and the target Bayes risk.
Consequently, the infimal convolution enables us to derive a smooth loss while maintaining the surrogate regret bound linear.
We additionally benefit from the infimal convolution to have a consistent estimator of the underlying class probability.
Our results are overall a novel demonstration of how convex analysis penetrates into optimization and statistical efficiency in risk minimization.

Establishing Linear Surrogate Regret Bounds for Convex Smooth Losses via Convolutional Fenchel-Young Losses
Yuzhou Cao
Han Bao² Lei Feng
Bo An
College of Computing and Data Science, Nanyang Technological University
The Institute of Statistical Mathematics
School of Computer Science and Engineering, Southeast University Skywork AI
srcchou00@@entu.edie Coan@ntu.edu..s fenglei euu.
bao.hant Saan@ism.ac iss..c..jppppppp....
Abstract
Surrogate regret bounds, also known excess risk bounds, bridge the gap between the convergence rates of surrogate and target losses. The regret transfer is lossless if the surrogate regret bound is linear. While convex smooth surrogate losses are appealing in particular due to the efficient estimation and optimization, the existence of trade-off between the loss smoothness and linear regret bound has been believed in the community. Under this scenario, the better optimization and estimation properties of convex smooth surrogate losses may inevitably deteriorate after undergoing the regret transfer onto a target loss. We overcome this dilemma for arbitrary discrete target losses by constructing a convex smooth surrogate loss, which entails linear surrogate regret bound composed with tailored prediction link. The construction is based on Senchel-Young losses generated by the convolu- tional negentropy, which are equivalent to the infimal convolution of generalized negentropy and the target Bayes risk. Consequently, the infimal convolution en- ables us to derive smooth loss while maintaining the surrogate regret bound linear. We additionally benefit from the infimal convolution have a consistent estimator of the underlying class probability. Our results are overall novel demonstration of how convex analysis penetrates into optimization and statistical efficiency in risk minimization.
Introduction
The risk of machine learning model is often measured by the expectation of target loss l that quantifies the error between the model prediction í and natural label y. However, minimizing the target risk over a dataset is often computationally hard because target prediction problem usually discretely structured, including multiclass, multilabel, top-k prediction problems. For this reason, tractable surrogate risk induced by a surrogate loss L(0. y) serves as an essential proxy with a score d The resulting surrogate optimization is longer discretely constrained.
An ideal surrogate loss should be convex, smooth (or entailing a Lipschitz continuous gradient), and calibrated toward given target prediction problem. Convexity and smoothness have been fundamental both optimization and statistical estimation-indeel classical optimization theory reveals that convex smooth functions can be optimized with first-order methods more efficiently than
"Corresponinng author.
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

In addition, several studies have demonstrated that the convexity and smoothness can further enhance fast rates in the risk estimation 87, 98.. Meanwhile, calibration is regarded as minimal requirement on surrogate losses, ensuring that the surrogate risk minimization
non-smooth functions 67 83
To establish relationship between surrogate and target risks, surrogate regret bounds play a crucial role. Therein the regret (or the suboptimality) of a target
leads to the target risk minimization [22 88
loss is controlled by that of a surrogate loss through a non-decreasing rate function & : |R20 + R20- surrogate regret bound can be informally written as follows: for any score vector E Rd and a class distribution 17.
Regret, (ggret,(((0),) S &a (Regret,, (0,
where yp is a prediction link that converts a score vector 0 into a target prediction cp(0). If the regret rate function is linear (b) ((r), which is the best possible dlta-indeependent) regret rate then the optimization and estimation errors of the surrogate loss are optimally translated to the target loss. For example, under the binary classification target loss, Bartlett et al. [22 demonstrated that the linear regret rate is possible with the hinge loss. Later, symmetric losses [24] and polyhedral losses [39] were shown yield the linear regret rate. Unfortunately, these loss functions lack either convexity or smoothness, which deteriorates the optimization and estimation errors of the surrogate regret, even if they enjoy linear regret bounds. By contrast, square-root regret rate (/(r) = O(VF) is common for convex smooth surrogate losses, such as the logistic, exponential, and squared losses [12] 69, (39]. These losses typically enjoy better optimization and estimation properties, yet suffer from larger target regrets due to the suboptimal regret rate. Therefore, it has been open to develop convex smooth surrogate loss without sacrificing the linear regret rate.
then
Notwithstanding, the previous literature in this line has implied that such an ideal surrogate loss may be inconceivable. Mahdavi al. [50] considered this question with an interpolated loss between the hinge (non-smooth) and logistic (smooth) losses and showed that we inevitably face the trade- off between generalization and optimization unless strong distributional assumptions are imposed. Further, Frongillo and Waggoner (39 proved that locally smooth and strongly convex losses must suffer from a square-root regret rate at least. Ramaswamy et al. (76) blame convex smooth losses for redundantly modeling continuous class distributions, which is unnecessary if our goal is merely to solve discrete target problems.
In this paper, we demonstrate that this seemingly impossible trade-off can be overcome for arbitrary discrete target losses. Specifically, of Young losses [16] - framework to generate a loss function from a generalized negentropy and its conjugate. In a nutshell, our main results are summarized as follows:
build a convex smooth surrogate loss built upon the framework
For any discrete target loss E, there exist a convex smooth surrogate loss (defined over score O E Rdd) and prediction link ip such that the surrogate regret bound I holds with some linear rate ((r)= = O(r).
Theorem (Informal version of Theorem 15
This existence is proved constructively, which provides a systematic framework on the construction of convex smooth surrogate losses and their corresponding prediction links with linear surrogate regret bounds. Our high-level construction, which significantly leverages convex analysis and is detailed in Section 3.1 proceeds as follows. First, user chooses a strongly convex negentropy with some regularity conditions, such as the Shannon negentropy. We encode the structure of a target loss l into the chosen base negentropy by adding the negative Bayes risk of f. This additivity eventually translates into the infimal convolution in the induced Fenchel-Young loss, which we call the convolutional Fenchel-Young loss. The convolutional Fenchel-Young loss is endowed with the convexity and smoothness arising from the base negentropy, shown in Section 3.2 Then we can obtain a prediction link via the infimal convolution. Paired with the convolutional wwwpooutiooaaeenneeeee-e-ee
Tenchel-Young
loss, it admits a linear surrogate regret bound, demonstrated in Section 3.3
In addition, improve the multiplicative term in the initial linear surrogate regret bound in Sec- tion 3.4 to make the bound tighter, which exploits the low-rank structure of a target loss f. As a by-product of the loss smoothness, we can provide Fisher-consistent probability estimator of the un- derlying probability in Section 3.5 Finally, Section 4 instantiates the framework of the convolutional Fenchel-Young loss for the multiclass classification problem, highlighting the efficient computation
2 Readers should distinguish this calibration property from calibrated prediction
A8
A super-lines bound is possible with distribution-deeeedent losses 99). which we do not consider here.

---

of the prediction link. More examples of target prediction problems, such as classification with rejection and multilabel ranking, are available Appendix D
1.1 Related Works
Surrogate losses for general discrete prediction problems. A discrete prediction problem aims to predict that minimizes discrete target loss E(1, y) over the class distribution, and the study of convex surrogates for É is of significant interest. Extensive research has been conducted on surrogate losses for specific discrete tasks, including but not limited to classification [12 101
85
66
64 81
top-k [95] 90], and multilabel learning [40] 100 54 49 65].
In contrast to ad-hoc approaches, recent studies have advanced the principled design of calibrated convex surrogate losses for general discrete prediction problems, without imposing restrictions on the target losses. In Ramaswamy and Agarwal 773 and Ramaswamy et al. (75), surrogate losses based on the squared loss and error correcting output codes are proposed, respectively, which embed the structure of a target problem into a surrogate loss and are shown to be calibrated with the corresponding target losses. The design of calibrated surrogate losses has also been extensively 70 68 69 23], where the structural/low-
studied in the context of structured prediction 229 74 26 27
rank properties of target losses are exploited to construct more efficient surrogates. As opposed to the smooth losses utilized in the works above, polyhedral losses [34, 35 37 have attracted attention recently, which provides a systematic framework for efficiently constructing calibrated yet non-smooth convex losses based on a discrete target loss.
Surrogate regret bounds. Surrogate regret bounds have been well studied for margin losses under binary and multiclass classification [10] Similarly, proper losses 21 42
12 89 84 56 (6). where the target loss is the 0-1 loss. have been shown to provide surrogate regret bounds w.r.t the L1 distance between the estimated and true class probabilities [77 g D which facilitates analyses for downstream tasks. For structured prediction, surrogate regret bounds are sometimes called comparison inequalities (26 70 68 [4]. which are typically of square- root type. Notably, Frongillo and Waggoner 39 demonstrated that polyhedral losses exhibit linear surrogate regret bounds for general discrete prediction problems, covering various piecewise linear non-smooth losses 995 76 as special cases. However, they lack the smoothness. To the contrary, Mao et al. 53 and Mao et al. [22 propose smooth losses with linear regret rates but lacking convexity.
78
Whereas growing line of research has focused on H-consistency analyze how the restriction to hypothesis space H affects consistency [48 99 7.. we implicilly suppose that the hypothesis space all measurable functions because the analysis often more transparent and it is reasonable to suppose that the hypothesis space is sufficiently expressive under the overparametriiztion regime. The extension to cccoosist rather straightforward by integrating the minimizability gap
52
55
54 57 51
2
Preliminaries
Let [d] == {1,2. .d} and I-I is the Iverson bracket. The p-norm is denoted by || llp-- which we assume to be the 2-norm unless otherwise noted. Let = ER U {oo} be the extended real-line and A = {n Rg ||dl| = 1} the d-simplex. For set S Rd, int(S) and relint(S) are its interior and relative interior, respectively, and conv(S) is its convex hull. The indicator function is denoted by Il _2 + {0, +00). where ls( 0 if 0 E S and too otherwise. For function f: .Rd + R. domms) (f) = {0 E IRd /(0) < } is its effective domain. A function f is extended to be set-valued with slight abuse of notation by S(S) = (s()) a E S). The Fenchel conjugate of Q is (0) == sUPpedom(()) {0) p - 1(p)). The identity matrix is I. The canonical basis of the Euclidean space is denoted by )e.). where the dimensionality depends on the contexts.
2.1 Discrete Prediction Problems and Target Losses
Let ) = [K] be the finite class space. The class distribution on y is A such that class Y = has probability Πy. A discrete prediction problem aims to find target prediction t from the finite
'This condition can be relaxed to the well-specified hypothesis space, under which the hypothesis space is required to contain at least one population risk minimizer, rather than the entire space of measurable functions.
3

---

prediction space D = [N] for each by minimizing discrete targer loss e y x 3 + R over y 17. The averaged target loss is called the target risk: R, (t.. n) Ey--y y) {n, ((t). where E(t) E R² the loss vector such that E(t), ftt, y) for each y E y. The Bayes risk of l n is R, = gi Rt, 7),, which is a concave function of n. The suboptimality of a prediction t w.rt. the target loss over a class distribution is characterized by the target regret, which is the gap between its risk and the Bayes risk.
Definition (Target regret) Given a discrete target loss t, the target regret of prediction w.r.t. a class probability 7 A is defined as follows:
Regret, n) Re(t, - R2(n).
(2)
Equivalent lower-dimensional decomposition. By encoding every possible class label E y into the canonical basis ey E IR K we can express any target loss in the following form:
((1,y) = (())-
An equivalent but more efficient decomposition of (3 known Structure Encoding Loss Functions (SELF), was introduced in Ciliberto et al. [26]. which allows lower-dimensional label encodings. It has been widely used to construct efficient loss functions, and further generalized via Affine Decomposition in Blondel [14] (12)]. We also adopt a general form to represent discrete target losses.
Definition 3 ((p, ( /ecooposiition) For a discrete target loss l 5 y + R, its (p. RP)- decomposition is given as follows:
= (P())) + cly),
where p y + +R is a label encoding function that maps discrete labels into the d-dimensional
Euclidean space, 40 5 - Rd is the corresponding loss encoding function, and e y + R is the remainder independent of prediction t.
This loss decomposition contains the Affine Decomposition 14 (12)). Any discrete target loss admits such a decomposition via the trivial choice p(y) = Ey, (1) = (t),, and c O with d = K, which immediately recovers (3). With properly chosen p. the encoded cardinality d can often be greatly smaller than K, particularly in the context of structured prediction. For example, consider multilabel classification, where ) y [K]. K = 2d, and each y [K] corresponds to unique binary vector v3y) E 10" representing set of binary labels. Suppose our target loss is the Hamming loss Er y) == 1 (v(L) + vvv)) - ((v()), (y))) which is the Hamming distance between v(I) and v(y). This entails the decomposition p(y) = 1 (v), (t = v(t), and c(y) 1 m(y). Here, d = log, K significantly reduces the dimensionality from the cardinality of y. We refer reader to Blondel [14 Appendix A] and Appendix D for more examples of discrete prediction problems.
The cardinality d of label encoding p closely related to surrogate regret bounds later in Section 3.4
2.2 Surrogate Losses and Surrogate Regret Bounds
Unlike discrete target losses assessing a discrete prediction t E 5. a surrogate loss L Rd x y
receives a continuous score 0 e Rd. Then prediction link y RR + y is used to transform a score 0 prediction Its risk and Bayes risk defined as Rg (0, n)) EE, Ey (L0, y)] = (n, L()) and R2 (n) := infeeg R2 (0, n)), respectively, where L( = [L(O, =)] The regret of surrogate loss is defined as the gap between the risk of score and the Bayes risk, similar to the target regret.
Definition 4 (Surrogate regret) Given surrogate loss L, the surrogate regret of score O w.r.t. class probability n E A is defined as follows:
Regret, == R2, n7) (n)
(5)
For desirable surrogate loss, the convergence of its surrogate regret will dominate the target regret. That is, for a fixed class distribution n, convergent 0 such that Regret, (0, + 0 should imply (egret,(y((O), 17) - This convergence relationship indicates that the target regret minimization can be achieved by the minimization of the surrogate regret adopted with an appropriate prediction link. A surrogate regret bound offers a quantitative characterization of this relationship through a regret rate function vi, which is the key focus of this work.

---

Definition 5 (Surrogate regret bound) A surrogate loss L and prediction link & entail surrogate
regret bound w.Et. target l with a non-decreasing regret rate function &b R20 + Rzo satisfying (0) = 0 if the following inequality holds:
Regret, (ggrett((((0),10) n) S (ORegret(((,n1))) for any (0, n) E R A
While a linear regret rate (r)) (r)) is the best possible, previously know linear-rate losses either non-smooth or non-convex, including the (non-smooth) hinge loss [12] and (non-convex)
sigmoid loss [24]. These loss functions may face challenges in optimization and estimation [87]. In
this work, we aim to develop framework that facilitates the use of convex smooth surrogates with linear surrogate regret bounds.
2.3 Fenchel-Young Loss
In this work, we build upon Fenchel- Younh losses 16 18 59 construct convex smooth surrogates equipped with linear regret rate functions. Let us review Fenchel- Cenchel-Young losses first.
Definition 6 (Fenchel-Young loss) For Ω : Rd + R, the associated Fenchel-Young loss Lo dom(S2") x dom( - Rzo defined as follows:
Ln p) k(p) (0) (0,p).
Similar constructions can also be found in Duchi et al. multiclass classification. The function 52 is often regarded as a generalized negentropy, which equals the negative of the Bayes risk of its induced Moachel-Yuung loss. Fenchel-Young losses often impose additional requirements on the domains l2 and I tailored to specific target problems, and we will highlight them when necessary.
33 Agarwal et al. (2] which focus on
Fenchel-Youne losses possess favorable properties: they are inherently convex (in score 0) by definition. Moreover, we can use the map (0) to obtain the mean Ey-,)pp(y)] which is the class distribution 7 under multiclass classification with p(y) = ey' or linear properties general []] Many common losses are encompassed in Fenchel-Young Young losses, including the cross-entropy loss, squared loss, and Singer loss BT. For example, 2(p) = 2 ||ppl 2 + IA (p) generates the sparsemax loss, which induces the sparsemax as a Fisher-consistent estimator of (58)
2
Connections to information geometry. While Fenchel- losses systematically defined under the convex-anas -naalyic formulation, it also has a longstanding history in information geometry. particularly through its connection to the Bregman divergence and related generalizations (72). In Blondel et al. [66. it is noted that a Fenchel-Young loss can be interpreted as the mixed-type Bregman divergence [4] When Ω is of Legendre-type, 52 can yield the dual coordinate system and the Younh loss is further equivalent to the canonical divergence generated by Ω [5] Eq. (3.44)).
Convex Smooth Surrogates with Linear Surrogate Regret Bounds
In this section, we first show our construction of surrogate losses and prediction links. After showing that this loss is convex and smooth with an appropriately chosen base negentropy (Theorem 11. we move on to the main result of this paper, linear surrogate regret bounds with convex smooth surrogate losses (Theorem 13). We further discuss the computational aspects and improve the regret bound constant. The missing proofs are deferred to Appendix
3.1 Construction
We design convex smooth surrogate loss built upon the framework of Senchel-Youngy losses. To make its surrogate regret bound linear, we craft negentropy by delicately leveraging the structure of target prediction problem. Denote by 7 the polyhedral convex function T(p) = min, (p, e (()).. Then, we have the following definition.
Definition 7 (Convolutional negentropy) Suppose (p, (P) decomposition for target loss f. For negentropy Ω: : Bd + IR, its convolutional negentropy is defined as follows:
QT(p) = 0(p) + T(p)
(8)
5

---

While commonly used negentropy in Fenchel-Yourd Young losses, such as the Shannon negentropy and norm negentropy [9] are unstructured toward target loss, the convolutional negentropy 22 encodes target loss explicitly into the base negentropy f via T. This polyhedral convex function T is an affinely transformed negative Bayes risk of a target loss when p E conv (p()))) Indeed, with the linear property p By-n ((v)], i.e., expectation of p(y) w.r.f. class probability
TΦp) = min (p. (()) min Ey E tE
(0(M) = Σ
nnc(u) - (n))
(9)
VE[K]
The base negentropy is up our choice. Before deriving the conjugate of Ωry, we make the following requirement on S2 throughout this work for well-behaved convolutional negentropy.
Condition 1 Ω is proper convex and lower-semicontinuons (l.sc.),, and satisfies conv(p())) S dom(S)) and dom)(?*) Rd.
a mild requirement. Indeed, proper convexity and lower-semicontinutty merely aim to avoid pathologies, and the domain assumptions are met by differentiable and finite S2 over the valid predic- tion space conv(p()))) The assumption on f2" is crucial for the induced loss have unconstrained domain gd Then we show explicit form of the conjugated convolutional negentropy.
Lemma (Conjugate of Q2)) Suppose Condition 7 hoolds, then Sr is proper convex and l.s.c. with dom(27)) Rdd and can be expressed as follows:
(7) = inf Ω- (0 + L*x) for any R #EAN
(10)
where Le E, B is the loss matrix with the t-th column being PP(t) E for t S. In addition. there always exists E A that achieves the infimum of (TO) for any O E Rd.
The conjugated form 10 owes to the infimal convolution between the base negentropy & and the target Bayes risk T. We coined the name the convolutional negentropy inspired by this structure. Intuitively, the conjugated convolutional negentropy 22 be viewed the conjugated base negentropy 52" toward the direction of the target loss matrix L This result facilitates
"perturhed" version of
concrete formulation of the Fenchel-Young loss generated by Urr, which refer to as the convolutional Younhg loss-the central focus of this work.
Definition 9 (Convolutional Fenchel-Young loss) dec decooppoosiin.nn. For a negentropy Ω IR > R. satisfying Condition / the convolutional Manchel-Young loss La, : R x y + R induced by the convolutional negentropy l2r defined as follows:
Suppose that discrete target loss E enjoys
Lor (0, v) = min 2 - (0, p(y)).
(11)
Note that Laz (0,-) is deliberately constrained to the class space instead of the general domain dom)) to align with the surrogate loss form introduced in Section 2.2
Given surrogate loss, we need to specify prediction link. For general discrete prediction problems where * Ve a prediction link yields discrete prediction in 5 from a score 0 E Rd obtained through minimizing the surrogate loss. Thus, a loss and link are the two sides of the same coin. Unlike the standard argmax link in multiclass classification prediction link based on the minimizer of (TO).
89 94
we create an alternative argmax-like
Definition 10 (I -rrgagmax link) Let II : Rd + 2A" be set-valued map defined as follows;
IT(0) = argmin {S2 (0 + LPT) E A for any O E TRd..
(12)
Let IRdd + AN be a selector of 11 such that π (0) E 11(0)) for all 0 d Then the π araagaax link yp : Rdd + 5) is defined as
(0) E argmax :t (e(( for any 0 Rdd.
where the tie can be broken arbitrarily.
*e slightly abuse the notation by using it for both vector and a valued mapping: in particular, the appearing in the argmax link refers to the selector function.

---

The existence of such links is guaranteed as long as II))) is non-empty for every O E R which is guaranteed by Lemma 8 While the standard argmax link returns prediction t E y with the maximum score f.. the --argmax link returns t with the maximum Tę. This probabilistic quantity (I)) defined via (IO) distorts the original score 0 by leveraging the target loss structure L
3.2 Convexity and Smoothness
Before discussing surrogate regret bounds, we verify that convolutional Fenchel-Young losses are indeed convex and smooth, implied by the conjugacy between smoothness and strong convexity 44
Corollary 11 (Convexity and smoothness of La,) Suppose that a discrete target loss & enjoys (p, decoopposiion For base negentropy S2 additionally suppose that Condition Dis satisfied. If is strictly convex dom(()), Lar (:, y) is convex and differentiable over IR for any y E V. If Q is additionally strongly convex on dom(s)), (. is smooth over I& for any E E..
There are several exemplar base negentropies fulfilling the conditions of Corollary I1 For example, the squared norm (p)) bll is strongly convex with the self-conjugate S!" (0) |0 1 In this
case, Ω is effective over the entire He and hence includes conv ((())) satisfying Condition | In light of the target-loss decomposition (3) we have conv(p()))
A In this case, the Shannon negentropy s2(p) (p. In Iax is strongly convex A with its conjugate (2*
(cxc f), 1) satisfying dom( = RK where In and cxp are element-wise. Hence, both base negentropy yield convex and smooth Laz.
Note that Loy is not locally strongly convex at every point. We can see this by noting that T is not differentiable and neither is P2y, which implies that S2 is not strictly convex (80) Theo-
rem 11.13J. This is important for establishing linear surrogate regret bounds (in Section 3.3) because the known square-root regret rate lower bound considers locally strongly convex surrogate losses [39 Theorem 2].
While the loss La, is now ensured to be convex and smooth, its gradient calculation, which is the basis for gradient- optimization [5], remains non-trivial. This is because the gradient of min S2" + ()Tr) contained in [ cannot be written analytically in general. We show that its gradient calculation reduces to computing (0) through the following variant of envelope theorems.
Lemma 12 (Envelope theorem) Suppose Condition 7 holds and Ω is strictly convex on dom
For any 0 E Idd and π E (I),,, we have
Vo min 02 + LTm) V2" LT)) HEAN
(13)
Deviating from the standard envelope theorems [3 we carefully addresses the non-uniqueness of the minimizers. Given this, the gradient of the convolutional Fenchel-Youe loss (II) is accessed
via VoLn, (0.y) VΩ2 ( ('T) π) p(y). At the core of its proof, the differentiability of 9
(indirectly obtained via Theorem is vital.
3.3 Linear Surrogate Regret Bounds
Now we exhibit linear surrogate regret bounds with the convolutional Fenchel-Young loss.
Theorem 13 (Linear surrogate regret bound) Consider a target loss with (p, RP) deccmdeccoooiiiiionnn
For a negentropy Ω : Rd + L, suppose Condition 1 holds. For any T--argmax link s,, (Lar, p) admits the following surrogate regret bound:
Regret, m) < NRegret (0, n7), for any (0. n7) Rd K
(14)
The regret bound in Theorem 13 indeed has the linear rate ((r) Nr in the form D.. while
Lap can be naturally made convex and smooth as discussed in Section 3.2 This is a remarkable consequence because many authors have previously implied the impossibility to overcome the barrier
of the square-root regret rate with convex smooth surrogate losses [50] 76 39 8). The crux this
success lies in the infimal convolution structure in (TO), which enables to additively decompose the conjugate 27 exploited below. The constant N' will be improved in Section 3.4
From now on sketch the regret bound proof. The following lemma is a cornerstone herein.
7

---

Lemma 14 (Lower bound of surrogate regret) Assume the same set of conditions as in Theo-
rem 13
For any 0 E R2 and π II( we have the following inequality:
N
m Reggret, n) s Regret La, (0, for any (0,n) E R E
(15)
Its proof, formally given in Appendix B hinges on the following additive regret decomposition:
Regret Lap (0. n) RL ( L2
EnEST T.Regret,(1,1) V(O. π
Rdd x IT(O),
Risk of Fenchel- Young loss La Convex combination of the target regret
which directly implies the lower bound (5) because the Fenchel- Young loss Lg is non-negative.
Note that this additive decomposition is indispensable for the linear lower bound (15). This becomes
possible just because we create the convolutional negentropy 2t based on the additive form in (8).
which yields the additive form + L the conjugate expression (TO). All these are thanks to the structure of the infimal convolution, and Theorem 13 immediately follows with rescaling.
Finally, we achieve the main result by combining Corollary [1 and Theorem 13
We constructively
prove the existence of convex smooth linear-regret surrogate losses, by noting that both strongly convex satisfying Condition T and -aaggax link do exist.
Theorem 15 (Main result) Consider a target loss l with (p, deccooooopoitnnnn For a negentropy Q Rd + I satisfying Condition 1 suppose that Q strongly convex on dom(S)). Then the convolutional Fenchel- Young loss (:.9) is convex, differentiable, and smooth over R for any E y. Moreover, with argmax link (p, (Lorr s) enjoys the linear surrogate regret bound
(1
3.4 Improving Constant of Linear Surrogate Regret Bounds
The constant N in the linear surrogate regret bound in (4 can be prohibitively large, leading to a vacuous bound. This issue is significant in structured prediction as studied in Osokin et al. [70]. For example, in multilabel classification with the Hamming loss, N =2 is the number of all the potential binary label predictions that increases exponentially with d, the number of binary labels. In top-k classification, N = (k) is the number of all possible size-k subsets of the class space. Thankfully, the geometry property of the problem (I0) provides a promising scheme for reducing the dependency on prediction number N, which induces the following improved link.
dd
Corollary 16 (Improved surrogate regret bound) Suppose Condition 7 holds. There exists से Rº A such that मं (0) E II(@) and || it (0))lo S affidim(CP) + for any O E Rd. Moreover, with the induced सt itargmax link (P# Rdd > N (Lar, (Px) admits the following surrogate regret bound:
(egret n) < Jaffdim( (CP) + 1] LagretLa, (0,00,)) for any (0, 1)) E RR x A (16)
where a affdim((P) is the dimension of the affine hull of the column vectors of LP.
Note that we have affdim(C* < mui((Nd)) d), which indicates that the dependency on N can be largely reduced when d & N. For example, in top-k classification, p(y) = Ey is used with d = K, which is much smaller than N = (k). In multilabel classification with Hamming loss, log, N is logarithmically smaller than N when binary encoding p(y) v(y) is used (see Section 2.1
3.5 Bonus: Fisher-consistent Probability Estimator
We discuss a benefit of convex smooth surrogate losses beyond discrete prediction problems. Often- times people are interested in a probability estimator over possible prediction outcomes, recovering from surrogate risk minimizers, as in classification with rejection [25] [1] 28
30 22 55, (3). Herein
non-smooth surrogate losses have been unfavored because of lacking reasonable probability esti- mators [60 24 Ramaswamy et al. (76) conjectures the incompatibility of probability estimation with linear regret bounds. By contrast, we give a Fisher-consisten estimator of the linear property [pl)] for convolutional Fenchel- Young losses without sacrificing the linear regret bound.
Theorem 17 (Fisher-consistent probability estimator) Suppose Condition 7 holds and Ω is strictly convex on do). For any 1 E velint(A*) (), the surrogate risk RLOg (., is minimized at 0" E I such that VΩ" (0* + x)) Eyon (yyn(p(y)) for any π E 11(0").
8

---

Algorithm 1 Exact Solution of (17 in ((Kln))
1: Sort 0 E _² such that (1) 2 ... 2 ((K)
2: max [k [K] (0()) -
3: r(0) - 0-
4: Mlg ( < max(0: - T0),
As a result, the empirical minimizers w.r.t. Lp, are Fisher-consistent estimators of the linear property (y--[((() According to the result above, can first solve IT(0) in [12 and select E IT(@). Then, ( + ( is a rational estimate of the linear property Ey-- ply)]. When we follow the trivial loss decomposition (3) with p(y) = Ey. the estimand is Eynn (vv) - E A For this reason, say V + TT) is a "probability" estimator.
For example, let us recap the encoding of multilahel classification in Section 2.1 where y E y is multilabel among all 2 possible combinations of d binary labels. A multilabel is encoded by ((y) E {0, 13. and the Hamming loss decomposed with p(y) = 1 (y) Here Ey-n (y)) reads v = (Prob((;()) = 1)}{=1 whose i-th element indicates the likelihood of the binary class being positíve. Through the relation 1- 122, the probability estimator V (0 + (Px) ) is capable of recovering by V0" //2
4 Example: Multiclass Classification
We demonstrate convolutional Fenchel-Youre losses for multiclass classification. and further exam- ples of prediction problems can found Appendices D and D including detailed computational complexity analyses and visualizations of the associated binary classification losses. In multiclass classification, the class space and the prediction space are the same: y 5 [K]. For input with class probability E A the goal to predict the most likely class E argmax,ey Tt- The target loss is the 0-1 loss f0 (t, y) = [t + y].
Firstly, we adopt the decomposition (3) for this task, that is, (t) = [Loi (t, 1). loi (t, K)] = 1 and p(y) Ey. which corresponds to the one-hot encoding commonly used in this task. In this case, N d = K, and C = =1 I.
Next, move on to the convolutional negentropy Dr. For the choice of Ω we use the Shannon negentropy, which induces the celebrated cross-entropy loss in the original Fenchel-Young loss framework [66] Table 1]. conjugate is the log-sum-exp function (²((0) In (exe (), 1). Then we can calculate the conjugate of Z2r based on Lemma [
(0) = min Ω (0 CPT)= min In (exp(0 + 1),
(17)
HEAK
#EAK
Since Ω is proper convex and l.s.c. with conv(p())) = A dom(S) (S2) and dom(S?") = R Ω satisfies Condition [ Furthermore, since Ω is strongly convex on A we can finally derive the convolutional Fenchel- Fenchel-Young loss (II) by nothing (r(p()) = for all E V, as follows:
Lap (0, y) ( 2r (0, p(U)) min In (exp( T
T), Oy. (18)
which is convex and smooth in thanks to Theorem II While shares the form of cross-entropy loss Ln(0, (0(0 y) In (exp((0), 1) 0y. it further incorporates additional bounded perturbation.
Solving the minimization problem 17 is important from the computational aspects, including the gradient calculation of for and accessing to the probability estimator given by Theorem 17 We provide Algorithm I to solve (17) with O(K In K) time.
Lemma 18 For any 0 E RK the problem 11 has unique minimizer Tlog (0) E I1(0), which can be obtained in OKK In K)) time by Algorithm
The proof is deferred to Appendix
C.I. following from the KKT conditions, Eventually we have
exp(8,) for E [K].
(0) = softmax (0 + Tog (0)). where softmax(0), = ΣK cxp(8:)

---

Algorithm comes with significant resemblance with the sparsemax [8 Algorithm 11, which is
determined by the similar structure shared by (I7) and Euclidean projection problem [58] (2)]. Since (T) is singleton, we have the unique Tlog-argmal link PPm (Definition 10 While we need to
solve problem (17) for every 0 to have access to V (0, y). the prediction by the Tlog-argmi link is much cheaper, without requiring Algorithm [] which indicates that we can simply use the class
label with the largest score [aX fy in test time. The proof can be found in Appendix C.2
Proposition 19 A prediction link y is the -lgg-ar link if and only if (0())= argmax,ey
cnrifficationcaalbrrattt which indicates that the surrogate risk minimization eventually leads to the Bayes-optimal classifier. In literature, Blondel [44) and Wang and Scott [94] have investigated sufficient conditions for Fenchel-Yone Young losses to be classfiiation-cclibrrtee of Legendre-type or twice differentiable. Our convolutional Fenchel-Young losses are interesting because we do not require these conditions to yield both the smoothness and a regret bound. Thus it remains open to relax these existing sufficient conditions for Fenchel Fenchel-Young losses further.
Remark 20 Under classification, a surrogate loss with a regret bound
Therein the base negentropy is assumed to be
Discussion
Convex non-smooth linear regret losses. Compared to existing convex non non-smooth surrogates with linear regret, e.g., polyhedral losses [7 our smooth convex surrogate has several advantages. First, smoothness enables more efficient optimization, as supported by results in both deterministic and stochastic optimization regimes [67 [83] while it is left open to exploit specific structures arising from polyhedral losses achieve faster optimization. In addition, the smoothness can lead to optimistic ERM rates of estimation error [87] offering better estimation in easier tasks. Another appealing aspect is that our loss admits consistent probability estimator (Theorem 17). which can be valuable for downstream tasks such as uncertainty quantification and calibration.
Efficient gradient calculation. In general discrete prediction problems, we need to solve the minimization (TO) to take a gradient of Lay. which is potentially demanding over a high-dimensional domain AN To have access to the gradient, we can alternatively solve
min Q* ( v), where V == conv {Ee (F)))N))))) DEV
(19)
To see this, let denote the minimizer of (9) by v" Then (99) is equivalent optimization
problem to (TO) because there exists π E IT(A) such that v LT. Eventually V + v*) serves as an alternative the gradient formula 13 Thus we can reduce the dimensionality of the
optimization problem. For example, in multilabel classification (Section 2.11). V = [0, 1já has
logarithmically smaller optimization dimensionality than N = 2d. We can solve (19) with this box
constraint efficiently by using the standard L-BFGS solver 47.
Randomized prediction link. Recall that the r-arrgax link o (Definition 10 deterministically outputs the probability simplex A Instead we can define a randomized link & such that Pr(p(0) = (0). This yields a better regret bound by Lemma 14 follows:
N
E5(() ())) Σ (0) Regret, n) Regret (0,n) (0,,))
V E E A
where the expectation is taken over the randomness of S. Although adopt the expected target regret differently from Theorem [3] the constant of regret bounds is strikingly improved from N to 1,
which is dimension-free free. Sakaue al. (82) observes similar regret improvement by randomized link for online structured prediction with Fenchel- Fenchel-Young losses.
6 Conclusion
In this work, we construct convex and smooth surrogate losses with linear surrogate regret bounds by leveraging Senchel-Young losses and infimal convolution. Our results demonstrate that convexity, smoothness, and linear surrogate regret are compatible for arbitrary discrete prediction problems. Moreover, our loss naturally admits consistent probability estimator, bridging the gap between linear regret and estimation. We illustrate the broad applicability of our approach through examples in multiclass classification, classification with rejection, and multilabel ranking. Overall, this study highlights the utility of convex analysis a principled tool for designing surrogate losses.
10

---

Acknowledgement
We thank Shinsaku Sakaue for his valuable insights on the target-loss decomposition and for his careful review, and also thank the anonymous reviewers for their attentive reading of the manuscript and their many thoughtful comments and suggestions. This research is supported by the Ministry of Education, Singapore, under its MOE AcRF Tier 2 Award MOE-T2HP20223-000 findings and conclusions or recommendations expressed in this material are those of the author(s) and do not reflect the views of the Ministry of Education, Singapore. YC is also supported by Google PhD Fellowship program. HB is supported by JST PRESTO (Grant No. JPMJPR24K6), Japan. Lei Feng is supported by the Big Data Computing Center of Southeast University.
Any opinions,

---

References
[1] Jacob D. Abernethy and Rafael Frongillo. A characterization of scoring rules for linear properties. In Conference Learning Theory, page 27.1, 2012. Cited on page: 5
[2] Alekh Agarwal, Sham Kakade, Nikos Karampatziakis, Le Song, and Gregory Valiant. Least squares revisited: Scalable approaches for multi-class prediction. In International Conference
on Machine Learning, pages 541-549, 2014. Cited on page: 5
[3] Shivani Agarwal. Surrogate regret bounds for bipartite ranking via strongly proper losses. Journal of Machine Learning Research, 15(1):15331674, 2014. Cited on page: 3
[4] Shun-ichi Amari. Information Geometry and Its Applications, volume 194, Springer, 2016. Cited p
[5] Shun-ichi Amari and Hiroshi Nagaoka. Methods of Information Geometry, volume 191. American Mathematical Soc., 2000. Cited on page: 5
[6] Pranjal Awasthi, Natalie Frank, Anqi Mao, Mehryar Mohri, and Yutao Zhong. Calibration and consistency of adversarial surrogate losses. Advances in Neural Information Processing Systems, 34:9804-9815, 2021. Cited on page: 25
[7] Pranjal Awasthi, Anqi Mao, Mehryar Mohri, and Yutao Zhong. Multi-class H --cooniittnccy bounds. Advances in Neural Information Processing Systems, 35:782-795, 2022. Cited on page: 3
[8] Han Bao. Proper losses, moduli of convexity, and surrogate regret bounds. In Conference on Learning Theory, pages 525-547, 2023, Cited on pages: 3, 7
[9] Han Bao and Asuka Takatsu. Proper losses regret at least 1/2-order. arXiv preprint
0rXiv2240.114477 2024. Cited on page: 3
[10] Han Bao, Clayton Scott, and Masashi Sugiyama. Calibrated surrogate losses for adversarially robust classification. In Conference on Learning Theory, pages 108-451, 2020. Cited on page: 25
[11] Peter L. Bartlett and Marten H. Wegkamp. Classification with a reject option using hinge loss. Journal of Machine Learning Research, 9(39):1823-1840, 2008. Cited on page: 8
[12] Peter L. Bartlett, Michael Jordan, and Jon McAuliffe. Convexity, classification, and risk bounds. Journal of the American Statistical Association, 101(473): 2006. Cited on pages: 2, 3, and
[13] Dimitri Bertsekas. Nonlinear Programming, volume 4. Athena Scientific, 2016. Cited on page: 7
[14] Mathieu Blondel. Structured prediction with projection oracles. Advances in Neural Informa- tion Processing Systems, 32:12145 12156, 2019. Cited on pages: 4, and 10
[15] Mathieu Blondel and Vincent Roulet. The elements of differentiable programming. arXiv preprint arXiv:2403. 14606, 2024. Cited on page: 7
[16] Mathieu Blondel, André F. T. Martins, and Vlad Niculae. Learning with Fenchel- Young losses. Journal of Muchine Learning Research, 21(35):1-63 2020. Cited on pages: 2, 5, and
[17] Mathieu Blondel, Quentin Berthet, Marco Cuturi, Roy Frostig, Stephan Hoyer, Felipe Llinares- López, Fabian Pedregosa, and Jean-Philippe Vert. Efficient and modular implicit differentiation. Advances in Neural Information Processing Systems, 35:5230-5242, 2022. Cited on page: 7
[18] Mathieu Blondel, Felipe Llinares-López, Robert Dadashi, Léonard Hussenot, and Matthieu Geist. Learning energy networks with generalized Fenchel-Young losses. Advances in Neural Information Processing Systems, 15:12516-122
2022. Cited on page: 5
[19] Dick Boekee and Jan C. van der Lubbe. The R-norm information measure, Information and Control, 45(2): 1980. Cited on page: 6
12

---

[20] Jonathan M. Borwein and Adrian S. Lewis. Convex Analysis and Nonlinear Optimization: Theory and Examples. CMS Books in Mathematics. Springer New York. 2005, Cited on page: 25
[21] Andreas Buja, Werner Stuetzle, and Yi Shen. Loss functions for binary class probability estimation and classification: Structure and applications. Technical report, University of Pennsylvania, 2005. Cited on page: 3
[22] Yuzhou Cao, Tianchi Cai, Lei Feng, Lihong Gu, Jinjie Gu, Bo An, Gang Niu, and Masashi Sugiyama. Generalizing consistent multi-class classification with rejection to be compatible with arbitrary losses. Advances in Neural Information Processing Systems, 35:521-5225 2022. Cited on page:
[23] Yuzhou Cao, Lei Feng, and Bo An. Consistent hierarchical classification with generalized metric. In International Conference on Artificial Intelligence and Statistics, pages 4825 4825-4833, 2024. Cited on page: 3
[24] Nontawat Charoenphakdee, Jongyeong Lee, and Masashi Sugiyama. On symmetric losses for learning from corrupted labels. In International Conference on Machine Learning, pages 961-970, 2019. Cited on pages: 2, 5, and 8
[25] Chao-Kong Chow. On optimum recognition error and reject tradeoff. IEEE Transactions on Information Theory, 16(1):41-44) 46, 1970. Cited on pages: 8, 30
[26] Carlo Ciliberto, Lorenzo Rosasco, and Alessandro Rudi. A consistent regularization approach for structured prediction. Advances in Neural Information Processing Systems, 29:4412-4422 2016. Cited on pages: 3, 4
[27] Carlo Ciliberto, Lorenzo Rosasco, and Alessandro Rudi. A general framework for consistent structured prediction with implicit loss embeddings. Journal of Machine Learning Research, 21 21(98)11667, 2020. Cited page:
[28] Corinna Cortes, Giulia DeSalvo, and Mehryar Mohri. Learning with rejection. In International Conference on Algorithmic Learning Theory, pages 67-82, 2016. Cited on page:
[29] Corinna Cortes, Vitaly Kuznetsov, Mehryar Mohri, and Scott Yang. Structured prediction theory based on factor graph complexity. Advances in Neural Information Processing Systems, 29:2514-2522 2016. Cited on page: 3
[30] Corinna Cortes, Giulia DeSalvo, and Mehryar Mohri. Theory and algorithms for learning with rejection in binary classification. Annals of Mathematics and Artificial Intelligence, 92(2):
277-315, 2023. Cited page:
[31] Koby Crammer and Yoram Singer. On the algorithmic implementation of multiclass kernel- based vector machines. Journal of Machine Learning Research, 2:265-292. 2001. Cited on page:
[32] Jia Deng, Wei Dong, Richard Socher, Li-Jia Li, Kai Li, and Li Fei-Fei. Imagenet: A large- scale hierarchical image database, In 2009 IEEE Conference on Computer Vision and Pattern Recognition, pages 248-255, 2009, Cited on page: 37
[33] John Duchi, Khashayar Khosravi, and Feng Ruan. Multiclass classification. information, divergence and surrogate risk. The Annals of Statisties, 46(66):3246-3275 2018. Cited on
page: 5
[34] Jessica Finocchiaro, Rafael Frongillo, and Bo Waggoner. An embedding framework for consistent polyhedral surrogates. Advances in Neural Information Processing systems, 32: 10781-10791, 2019. Cited on page: 3
[35] Jessie Finocchiaro, Rafael Frongillo, and Bo Waggoner. Embedding dimension of polyhedral losses. In Conference Learning Theory, pages 1558-1585. 2020. Cited on page: 3
[36] Jessie Finocchiaro, Rafael Frongillo, and Enrique Nueve. The structured abstain problem and the Lovász hinge. In Conference on Learning Theory, pages 877400,4,, 2022. Cited on page: 8
13

---

[37] Jessie Finocchiaro, Rafael Frongillo, and Bo Waggoner. An embedding framework for the design and analysis of consistent polyhedral surrogates. Journal of Machine Learning Research, 25(63):1-660 100 2024. Cited on pages: 3, 10
[38] Dean P. Foster and Rakesh V. Vohra. Asymptotic calibration. Biometrika, 85(2)379--39,
1998. Cited on page: 2
[39] Rafael Frongillo and Bo Waggoner. Surrogate regret bounds for polyhedral losses. Advances in Neural Information Processing Systems, 35:21569-21580, 2021. Cited on pages: 3, 7, 25,
and 37
[40] Wei Gao and Zui-Hua Zhou. On the consistency of multi-label learning. In Conference on Learning Theory, pages 341-358, 2011. Cited on page: 3
[41] Aritra Ghosh, Himanshu Kumar, and P. Shanti Sastry. Robust loss functions under label noise for deep neural networks. In Proceedings of the AAAI Conference on Artificial intelligence, volume 31, 2017. Cited on page: 25
[42] Tilmann Gneiting and Adrian E. Raftery. Strictly proper scoring rules, prediction, and estimation. Journal of the American Statistical Association, 102(477):359-378, 2007. Cited on page:
[43] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pages 770-778, 2016. Cited on page: 37
[44] Sham Kakade, Shai Chalev-Shwarta and Ambuj Tewari. On the duality of strong convexity and strong smoothness: Learning applications and matrix regularization. Technical report, Toyota Technological Institute at Chicago, 2009. Cited on page: 7
[45] Wojeiech Kotlowski and Krzysztof Dembezyúski. Surrogate regret bounds for generalized classification performance metrics. In Asian Conference on Machine Learning, pages 301-316, 2016. Cited on page: 3
[46] Alex Krizhevsky and Geoffrey Hinton. Learning multiple layers of features from tiny images. 2009, Cited on page: 38
[47] Dong C. Liu and Jorge Nocedal. On the limited memory BFGS method for large scale optimization. Mathematical Programming, 45(1):503-528, 1989. Cited on page: 10
[48] Phil Long and Rocco Servedio. Consistency versus realizable H-consistency for multiclass classification. In International Conference on Machine Learning, pages 801-809, 2013. Cited
on page:
[49] Michal Lukasik, Lin Chen, Harikrishna Narasimhan, Aditya Krishna Menon, Wittawat Jitkrit- tum, Felix X Yu, Sashank J Reddi, Gang Fu, Mohammadhossein Bateni, and Sanjiv Kumar. Bipartite ranking from multiple labels: On loss versus label aggregation. arXiv preprins arXiv:2504. 12244, 2025. Cited on page:
[50] Mchrdad Mahdavi, Lijun Zhang, and Rong Jin. Binary excess risk for smooth convex surro- gates. arXiv preprint Xrxiv 102. 2014. Cited on pages: 2,
[51] Angi Mao, Mehryar Mohri, and Yutao Zhong. H-consistency bounds: Characterization and extensions. Advances in Neural Information Processing Systems, 36:4470-4508, 2023. Cited
on page: 3
[52] Anqi Mao, Mehryar Mohri, and Yutao Zhong. Cross-entropp loss functions: Theoretical analysis and applications. In International Conference Machine Learning, pages 23803- 23828, 2023. Cited on pages: 3, 25
[53] Angi Mao, Mehryar Mohri, and Yutao Zhong Structured prediction with stronger consistency guarantees. Advances Neural Information Processing Systems, 06:46903-469577 2023. Cited pages: 3, 25
14

---

[54] Anqi Mao, Mehryar Mohri, and Yutao Zhong. Multi-label learning with stronger consisteney guarantees. Advances in neural information processing systems, 37:2378-2444 2024. Cited
on page:
[55] Anqi Mao, Mehryar Mohri, and Yutao Zhong. Predictor-rejector multi-class abstention: Theoretical analysis and algorithms. In International Conference on Algorithmic Learning
Theory, pages 822-867, 2024. Cited on pages: 3, 8
[56] Angi Mao, Mehryar Mohri, and Yutao Zhong. A universal growth rate for learning with smooth surrogate losses. Advances in Neural Information Processing Systems, 37:41670-41708, 2024. Cited page:
[57] Anqi Mao, Mehryar Mohri, and Yutao Zhong. Enhanced H-consistency bounds. In In- ternational Conference Algorithmic Learning Theory, pages 772-813, 2025. Cited on page:
[58] André F. T. Martins and Ramon Astudillo. From softmax to sparsemax: A sparse model of attention and multi-label classification. In International Conference on Machine Learning, pages 1614 1623, 2016. Cited on pages: 5, 10
[59] André F. T. Martins, Marcos Treviso, António Farinhas, Pedro M. Q. Aguiar, Mário A. Figueiredo, Mathieu Blondel, and Vlad Niculae. Sparse continuous distributions and Fenchel- Young losses. Journal of Machine Learning Research, 23(257):1-74, 2020. Cited on page:
[60] Hamed Aessadi-Shirazz and Nuno Vasconcelos. On the design of loss functions for classi- fication: Theory, robustness to outliers, and SavageBoost. Advances in Neural Information Processing Systems, 21:1049-1056 2008. Cited on page: 8
[61] Nishant A. Mehta and Robert C. Williamson. From stochastic mixability to fast rates. Advances in Neural Information Processing Systems, 27:1 197-1205, 2014. Cited on page: 25
[62] Shahar Mendelson. Lower bounds for the empirical minimization algorithm. IEEE Transac- tions on Information Theory, 547)333777,3803, 2008. Cited on page: 25
[63] Aditya Krishna Menon and Robert C. Williamson. Bayes-optimal scorers for bipartite ranking. In Conference on Learning Theory, pages 68-106, 2014. Cited on page:
[64] Aditya Krishna Menon, Harikrishna Narasimhan, Shivani Agarwal, and Sanjay Chawla. On the statistical consistency of algorithms for binary classification under class imbalance. In International Conference on Machine Learning, pages 603-611, 1, 2013. Cited on page: 3
[65] Aditya Krishna Menon, Ankit Singh Rawat, Sashank Reddi, and Sanjiv Kumar. Multilabel reductions: What is my loss optimising? Advances in Neural Information Processing Systems, 32:10600-10611, 2019. Cited on page:
[66] Harikrishna Narasimhan, Harish G. Ramaswamy, Shiv Kumar Tavker, Drona Khurana, Pra- neeth Netrapalli, and Shivani Agarwal. Consistent multiclass algorithms for complex metrics and constraints. Journal of Machine Learning Research, 25(367): 2024. Cited on page: 3
[67] Yurii Nesterov. A method for solving the convex programming problem with convergence rate O(1/k²). Dokl Akad Nauk SSSR, 269:543, 1983. Cited on pages: 2. 10
[68] Alex Nowak, Francis Bach, and Alessandro Rudi. Sharp analysis of learning with discrete losses. In International Conference on Artificial Intelligence and Statistics, pages 1929-1929, 2019. Cited on page: 3
[69] Alex Nowak, Francis Bach, and Alessandro Rudi. A general theory for structured prediction with smooth convex surrogates. arXiv preprint arXiv:1902. 190800198, 2019. Cited on pages: 2,
[70] Anton Osokin, Francis Bach, and Simon Lacoste-Julien. On structured prediction theory with calibrated convex surrogate losses. Advances Neural Information Processing Systems, 30: 302-313, 2017. Cited on pages: 8
15

---

[71] Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury. Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, Alban Desmaison, Andreas Köpf, Edward 7. Yang, Zachary Vito,, Martin Raison, Alykhan Tejani, Sasank Chilamkurthy, Benoit Steiner, Lu Fang, Junjie Bai, and Soumith Chintala. PyTorch: An imperative style, high-performance deep learning library. Advances in Neural Information Processing Systems, 52:8024-8035, 2019. Cited on page: 37
[72] Seta Rakotomandimby, Yean-Philippe Chancelier, Michel De Lara, and Mathieu Blondel. Learning with Fitzpatrick losses. Advances Neural Information Processing Systems, 37: 79381-79409, 2024. Cited on page: 5
[73] Harish G. Ramaswamy and Shivani Agarwal. Classification calibration dimension for general multiclass losses. Advances in Neural Information Processing Systems, 15:2078-2086 2012.
Cited pages: 3, 28
[74] Harish G. Ramaswamy, Shivani Agarwal, and Ambuj Tewari. Convex calibrated surrogates for low-rank loss matrices with applications to subset ranking losses. Advances in Neural Information Processing Systems, 26:1 26:1475-1483, 2013. Cited on page:
[75] Harish G. Ramaswamy, Balaji S. Babu, Shivani Agarwal, and Robert C. Williamson. On the consistency of output code based learning algorithms for multiclass learning problems. In Conference on Learning Theory, pages 885-902, 2014. Cited on page:
[76] Harish G. Ramaswamy, Ambuj Tewari, and Shivani Agarwal. Consistent algorithms for multiclass classification with an abstain option. Electronic Journal of Statistics, 12:530-554, 2018. Cited on pages: 2, 3, 7, and 8
[77] Mark D. Reid and Robert C. Williamson. Surrogate regret bounds for proper losses, In International Conference on Machine Learning, pages 897-904, 2009. Cited on page:
[78] Mark D. Reid and Robert C. Williamson. Composite binary losses. Journal of Machine Learning Research, 1 11:2387-2422, 2010. Cited on page: 3
[79] Ralph T. Rockafellar. Convex Analysis. Princeton University Press, 1997. Cited pages: 25, 26, and 28
[80] Ralph T. Rockafellar and Roger J.-B. R. Wets. Variational Analysis, volume 317. Springer Science & Business Media, 2009, Cited on pages: 7, 26, 27, and 28
[81] Vincent Roulet, Tianlin Liu, Nino Vieillard, Michael E. Sander, and Mathieu Blondel. Loss functions and operators generated by f-divergences. In International Conference Machine Learning, volume 267, pages 2210--2138, 2025. Cited on page: 3
[82] Shinsaku Sakaue, Han Bao, Taira Tsuchiya, and Taihei Oki. Online structured prediction with Fenchel-Young losses and improved surrogate regret for online multiclass classification with logistic loss. In Conference on Learning Theory, pages 4458-4486, 2024. Cited on page: 10
[83] Mark Schmidt, Nicolas Le Roux, and Francis Bach. Minimizing finite sums with the stochastic average gradient. Mathematical Programming, (62:83-112, 2017. Cited on pages: 2, 10
[84] Clayton Scott. Surrogate losses and regret bounds for cost-sensitive classification with example- dependent costs. International Conference on Machine Learning, pages 153-160, 201 Cited page:
[85] Clayton Scott. Calibrated asymmetric surrogate losses. Electronic Journal of Statistics, 958 992,9992222 2012. Cited on page: 3
[86] Sanket Shah, Milind Tambe, and Jessie Finocchiaro. Analyzing cost-sensitive surrogate losses via --calibration. arXiv preprint arXiv:2502. /9522, 2025. Cited on page:
[87] Nathan Srebro, Karthik Sridharan, and Ambuj Tewari. Smoothness, low noise and fast rates. Advances in Neural Information Processing Systems, 002119-2227,, 2010. Cited on pages: 5, 10, and 25
16

---

[88] Ingo Steinwart. How to compare different loss functions and their risks. Constructive Approximation, 26(2):225-28) 2007. Cited on page: 2
[89] Ambuj Tewari and Peter L. Bartlett. On the consistency multiclass classification methods. Journal of Machine Learning Research, 8036):1007-1025, 2007. Cited on pages: 3, 6
[90] Anish Thilagar, Rafael Frongillo, Jessica Finocchiaro, and Emma Goodwill. Consistent polyhedral surrogates for top-k classification and variants. In International Conference on Machine Learning, pages 21329 21359, 2022. Cited page:
[91] Tim van Erven, Peter D. Grünwald, Mark D. Reid, and Robert C. Williamson. Mixability in statistical learning. Advances in Neural Information Processing Systems, 26:1700-1770 2012. Cited on page: 25
[92] Tim van Erven, Peter D. Grünwald, Nishant Mehta, Mark D. Reid, and Robert C. Williamson. Fast rates in statistical and online learning. Journal of Machine Learning Research, 16:17911886, 2015. Cited on page: 25
[93] Yutong Wang and Clayton Scott. On clasification-caliiaatiie of gamma-phi losses. In Conference on Learning Theory, pages
2023. Cited page: 3
[94] Yutong Wang and Clayton Scott. Unified binary and multiclass margin-based classification. Journal of Machine Learning Research, 25(143):1-51, 2024. Cited on pages: 6, 10
[95] Forest Yang and Sanmi Koyejo. On the consistency of top-k surrogate losses. In International Conference on Machine Learning, volume 119, pages 10727-10735, 2020. Cited on page: 3
[96] Sergey Zagoruyko and Nikos Komodakis. Wide residual networks. In British Machine Vision Conference, 2016. Cited on page: 38
[97] Jingwei Zhang, Tongliang Liu, and Dacheng Tao. On the rates of convergence from surrogate risk minimizers to the Bayes optimal classifier. IEEE Transactions on Neural Networks and Learning Systems, 33(10):5766-577 577-4744 2021. Cited page: 2
[98] Lijun Zhang, Tianbao Yang, and Rong Jin. Empirical risk minimization for stochastic convex optimization: O(1 /n)- and ((1/n))-typ of risk bounds. In Conference on Learning Theory,
pages 1954-1979, 2017. Cited on page: 2
[99] Mingyuan Zhang and Shivani Agarwal. Bayes consistency vs. H H-consistency: The inter- play between surrogate loss functions and the scoring function class. Advances in Neural Information Processing Systems, 33:16927-16636. 2020. Cited on page: 3
[100] Mingyuan Zhang, Harish G. Ramaswamy, and Shivani Agarwal. Convex calibrated surrogates for the multi-label F-measure. In International Conference Machine Learning, pages 11246-11222 11255, 2020. Cited on page: 3
[101] Tong Zhang. Statistical analysis of some multi-category large margin classification methods. Journal of Machine Learning Research, 5:1225-1255 2004. Cited page:
17

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect paper's contributions and scope?
Answer: [Yes]
Justification: The abstract and Theorem 1 in the introduction (Section [ reflect our scope (surrogate regret bound of losses) and contribution (a family of convex smooth surrogates with linear surrogate regret bounds).
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation as long as it is clear that these goals are not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer:
[Yes]
Justification:
The limitation of this work is discussed in Appendix A
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-texx system might not be used reliably provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and faimess..
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community, Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
18

---

Answer: [Yes]
Justification: Assumptions are clearly stated in each theoretical claim. All theoretical claims are provided with proofs.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors encouraged provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [Yes]
Justification: The experimental setting, including the data augmentation, optimizer, model architecture, and associated computational cost.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, other means that appropriate to the research performed.
also be provided via detailed
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how to reproduce that algorithm.
(b) the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is a new model (e.g., a large language model), then there should either way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reprodueibility may be tricky in some cases, in which authors are welcome to describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers have some path reproducing or verifying the results.
5. Open access to data and code
19

---

reproducible, they Question: Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [No]
Justification: Our experiments use public datasets, the official PyTorch training script, and detailed formulations of both the loss and solver, making the work fully reproducible without releasing extra code or data.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips.. cc/
public/ guides /Cdde//uuuues/oe CodeSuumm
ss ssionsolicggyo for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" an acceptable answer. Papers cannot be rejected simply for including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https
//nips httpccccccccccccccc wwabbliccuuiiii ides/ CoodeS ubmi ss ssssssinn ciioooooiiii icy) for more details.
The authors should provide instructions on data access and preparation, including how access the raw data, preprocessed data, intermediate data, and generated data,
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permirted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification:
The experimental settings provided in Appendix
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment statistical significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Justification: For ImageNet experiments, we perform 5% t-test for comparison. For classification with rejection results, no comparison is involved, and report only the averaged performance.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by emor bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
20

---

The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative еπτог rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification:
The detailed information on computer resources is provided in Appendix
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported the paper (e.g., preliminary or failed experiments that didn't make it into the paper).
9. Code of ethics
Question: Does the research conducted the paper conform, in every respect, with the NeurlPS Code of Ethics http:///s...aaa.....c.////aataaa
Answer: [Yes]
Justification:
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make to preserve anonymity (e.g., if there is special consid- eration due to laws or regulations their jurisdiction..
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: This theoretical work aims to advance machine learning by informing the design and use of surrogate losses for discrete prediction. While it may influence downstream research and applications, we do not identify any specific risks that warrant emphasis.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
21

---

If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g.. code, data, models), used in the paper, properly credited and the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, possible, include URL
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
22

---

If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paaperswi paperswithoooes com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re- re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
If this information not available online, the authors are encouraged to reach out to the asset's s creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/moode as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsoureing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper doess not involve crowdsourcing nor research with human subjects.
Including this information the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According to the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based the requirements of your country institution) were obtained?
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
23

---

We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors adhere the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
16. Declaration of LLM usage
Does the paper describe the usage of LLMs if it is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, formatting purposes and does not impact the core methodology, scientific rigorousness, or originality of the research, declaration is not required.
Question:
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the method development in this research does not involve LLMs as any important, original, or non-standard components.
Please refer to our LLM policy (https: /tttps:/neeeee //nuurrrppsp www.eeee......onneeeeeeeee
cc /tc//ooffeeeene///2220 2025/
LLM) for what should should not be described.
24

---

A Additional Discussions on Related Losses
Fast rate losses. Let us briefly discuss the target risk estimation error rates induced by different surrogate losses. Suppose that surrogate risk can be estimated with the estimation error upper bound fest and the surrogate regret rate is vb. Then, the target risk estimation error is of order (b((ea)) Hence, we need to take care of both and East to discuss the target risk estimation.
On the one hand, loss functions entailing either strongly convex or exponentially concave are known to achieve fast estimation error rates with ERM (e.g., ((1/n)) in standard parametric setting, where the hypothesis class is of finite dimension 87 91 61 92]. However, Frongillo and Waggoner [3] Theorem 4] reveals that typical fast rate losses suffer at least from square-root regret rates, and thus their corresponding target risk estimation error bounds are (11/ (n) at least. On the other hand, convolutional Fenchel-Young losses (which is convex smooth but not strongly convex) yield the estimation error upper bounds of order (1/v/n) under the same setting, while the final target risk upper bounds are in order of O(1/vn) thanks to the linear regret rate function. As result, convolutional Fenchel-Young losses achieve target regret convergence rates that are comparable to those of existing fast-rate losses.
In more general nonparametric settings, where fast rates are often hard to achieve without additional assumptions (622, convolutional Fenchel- Young losses achieve target risk estimation error bound of order (1///n). In contrast, strongly convex surrogate losses typically achieve a slower target risk estimation error rate than (1//vn) because the general nonparametric estimation error is O(1/ but the regret rate are slower than (p(r) = (r)).
While we do not intend to argue that the convolutional Fenchel-Young loss is always better, we would like to highlight that may be a good alternative when the parametric conditions for fast rates cannot be readily justified. It also remains an open and worthwhile question whether fast rates can be obtained for our loss under additional assumptions, such as low-noise or margin conditions.
Smooth non-convex linear regret losses. While our focus is on convex surrogates due to their favorable optimization and statistical properties. we note that certain smooth but non-convex surro- gates, such as the mean absolute error (MAE) ETI [22] and structured comp-sum losses with MAE [53], also achieve linear regret. These methods, while typically non-convex and not equipped with probability estimator, offer valuable advantages in other aspects, such as robustness to label noise, H-consistency, and potential benefits under adversarial conditions [10 6), where non-convexity can play meaningful role.
B Deferred Proofs in Section 3
Recalling the definition of T(p) min, (p, (Pt)), which is the negative of the affinely transformed target Bayes risk in (9) can be inferred that is proper convex and l.s.c., and we have
Or 2 T.
B.1 Proof of Lemma g
Proof. Since Ω and T are proper convex and l.s.c., 2r and thus 22 Then we prove (10) using the infimal convolution. First, by noting that T is nothing else but the support function of the closed convex set conv( ((-PP(t)) we can express 7 as follows:
T (0) sup pERd
(0. p) max (p. (p (()) t
where the conjugacy relationship between support function and indicator function of closed convex set conv( (() (())) 779 Section 13). According to Condition and the definition
of T, we see that both Q and T are proper convex and T is continuous on dom( Then we use the infimal convolution 20 to derive the conjugate of Z7:
(7)0)- = inf
Ω2 (0 - 8') + II
(8))
d'ERd
inf 0'Econv( ((
s0' - 0')
25

---

inf (0 + LT)).
TEAN
Next we show that the infimum is indeed achieved by some E AN, Note that for any 0 E R since
the set θ {0 + L E A is compact and non-empty, and that Q² is l.s.c. dom((2") Rd. Then the infimum of S2" (0) is achieved by some l E O and there must exist π E A such that 0 + L = 0" by the definition of θ, which complete the proof of the existence of the minimizer.
Finally we see that for any 0 E Rd, there exists π E AN such that 27(0) = Q- + LPT), which smaller than +oo since dom((2*) Rd and 0 + L π E IRd. This indicates that dom (9t) Re because 0 is chosen arbitrarily.
B.2 Proof of Theorem
Proof. In the convolutional Tenchel-Young loss (TI. the term (tr(p())) (0, p(y)) is linear. Hence it suffices to prove the convexity and smoothness of the conjugate minzEaN 52" (0- CPT).
When Ω is strictly convex, S2 is also strictly convex since T is convex. Since the strict convexity holds ), S2y is further essentially strictly convex, that is, strictly convex every convex subset of dom(a [79] p253]. According to Rockafellar [79] Theorem 26.3]. 227 is essentially smooth, that is, differentiable throughout non-empty int (17(dom((27 )) with || VV2 diverging to +oo when 0 approaches a boundary point of inl (12))))))) which immediately indicates the differentiabilityy on Rdd
When Ω is further strongly convex, so is Pt. According to Condition T and Lemma 8 s2r is proper convex and l.s.c., and thus the biconjugate 27 matches 22 by the Fenchel-Moreal theorem. According to Rockafellar and Wets [80 Proposition 12.60J, O7 is smooth since its conjugate 07 = Ωr is strongly convex.
B.3 Proof of Lemma 12
Proof. According Condition 1. the strict convexity of Ω2 and the proof of Theorem II both Oz
and Ω* differentiable on Red. In addition, have dom( domm(Sr) according (8)
Note that 92" (0 + LTT) is convex in π. Then its first-order optimal condition for any π E II(0) reads
( (0 + LT)) CP -T) 2 0 any π E A
First, for any π II),), choose
t E argmin
then we have
( + LTT)
(0 + L (0- N(VS' C-T))
(000 -
000'0''''' (0000-0000"0000000000000000000'' 10 (0((TT)
0 00' min V2 (T)), l ((()) 20+72(0++''m
- (++Cx))
9 0 1U' (0 + ( - 2T
0 p 1T(PP)
sup
(7),
26

---

where (A) owes to the optimality of π E II(O), (B) holds by the definition of t, and (C) holds by the definition of the convolutional negentropy S2 (8) Since II(@), we have S2" (0 [
(0) according to Lemma 8 Thus the above inequality is indeed an identity. In particular, (D) becomes an identity, which implies that the supremum of ((Ppedom(((r)) 0 p Qp is achieved at VD + (.T)). Since the supremum is also achieved at (0) and the maximizer is unique according to Rockafellar and Wets 80 Proposition 1 11.3] and the differentiability of 22 we have
(0) VΩ (0 + L)T).
Since и E (0) and E I&d are chosen arbitrarily, this concludes the proof.
B.4 Proof of Theorem 13
Proof. Fix any A E Rd and choose any π E A N out of (I).. Then we have
Vn AK Regret Lay (0.
N
Ty R.geget,, (t, n)
(by 15
z (0) Regret, n) (because nT 2 0 for any t })
Regret,(v(O)),)) n)/N.
(by definition of şo Defintion T0
B.5
Proof of Lemma 14
Proof. First, we derive the Bayes risk of the convolutional Younhe loss La, as follows:
R Rtar
(n)
inf REng (0, ())
BERR
inf (0) -0, (F)nn(((())) + Fern((((((()))
DE
sup (00, (e,EEynn(l)))) - + +By-n(Dr((())
BERd
22 (En-nlp()))) + Ey-n(((r(p(x))
Eyyn U2r (p(v)) Dr (Fy-nl((v)))
where the Fenchel-Moreat theorem is applied to proper convex and l.s.c. 22 (by Lemma 8 the last identity. Then we can get the following regret lower bound for any π E I[(e):
Regret La, (0, RI.g (0, n) BLor (n)
-27 (0, (y.Enn(((()) 2r (Eynlo((s))
(0 (PT)
+ 2 [((Eynnl(())) T (Em-nl((vi)
( 22 (0 + (PT) (0 LT Ryynnl(())) + st F [p())))
20 due to the Fenchel Young incquality
[T n. Bplnnl((())) + (Ev-nlo(wil) ((E
N
(By-n(p(y)) (())))
-min
(iin(Bp-llll)))ee res
(l,
where (A) holds according the explicit form of 27 in 110 and the definition of II(0), (B) owes to Fenchel- Young inequality, and (C) holds according to the definition of (p, deccooosioooiiiiionnnn (4) This concludes the proof.
27

---

B.6 Proof of Corollary 16
Proof. Fix an arbitrary Rd. Since [I) is non-empty, we can select л from II) Note that
f ccnv (())))))))) According to Carathéodory's theorem, there exists म such that || lloo S affdim(( +1 and L L n is also in ()). Since 9 is chosen arbitrarily, we then construct single-valued function π. I + A such that म (0) [I(0) and (0)llo S affdim((e)) + 1. Noting that m (0) > 1/laffdim(CC9 + 1], we can complete the rest of the proof similarly to Theorem 13
Remark 21 Interestingl,, Ramaswamy and Agarwal [73] also used the affine dimension of the loss matrix to study the dimension of convex surrogates, suggesting that this concept plays important role in loss function design and deserves more attention.
B.7 Proof of Theorem 17
Proof. First of all, we prove that relint (c)(n)(con(pp()))) is in the image of VS2 by contradiction. According to Rockafellar [79 Theorem 23.4]. we have that 80r is non-empty for all p relint ((iin(d)m(({r)) )). Now suppose there exists p E relint(dom (Str)) such that p * V22 for any E Rdd Since 02r (p) is non-empty, there exists O' E Rd such that e' = (p) By Rockafellar and Wets [80] Proposition 11.3] (applied on proper Ls.cc lly), we have p V22 (0'), which contradicts the assumption * (0') Thus we have verified that (elint(dom(((rr)) is in the image of V This additionally implies that relin((conv(p(())) E relint relint(dom((Tr) )) is also in the image V22 because of Condition |
Now we fix r E relint(A A A)) and note that
Ri (0. (0) + (xr=((((((()))) (0, Ey-n
differentiable and convex in 0. If E Rd is the minimizer of Rr.,, (1, , its optimality condition indicates
VaRLa, (0" n) = (227-(0") - p(y)] 0.
When n E rclint(A K), we have ( E cclin((con(p(()))) and thus 0* satisfying the above optimality condition does exist. Finally, we conclude the proof by combining Lemmas and 2
C Deferred Proofs in Section
C.1 Proof of Lemma 18
Proof. Denote by VT(TT) Σ i= +0+1- Since In(-) is strictly increasing Rso. Vo(TT) shares the same minimizer as In (E t.) The Lagrangian F of the minimization problem Ve for
π E A is written as follows:
K
K Σ
F( a. B)
Σ c 0, 01+1=
+ 3
m -
where @1 aI.....C0 aK 2 0 and B are the Lagrangian multipliers. Since Vo(TT) tiable, and the feasible region A is convex, the KKT conditions are necessary and sufficient for the optimality of π E II)))) which requires that there exists (a*, satisfying
) is convex and differen-
- 1 o + + 0, 1 T
for any y I....,k K.
(20)
=1,
n 2 0, a 2 0,
(21)
a
for any y 1, K.
(22)
The conditions 21 and
22 indicates that o.j > 0 - ag = 0. Then according to
20 we have
T > 0 - Tty = 0 - (In 3 - 1).
(23)
28

---

Meanwhile, for m.y 0. indicates that yy 2 0, which further indicates
0u In( - any - In g
(24)
Then 23 and 24 can be rewritten as follows:
y = max (8, (In 3" 1). 0).
(25)
According to 21 and In g - E IR, the KKT conditions can be further simplified into the existence of E R such that the following conditions simultaneously hold:
max (0g -0, --, 00 =1
max
Denote by [(T) Σn max (0, r, 0}. Then f is continuous on R, and moreover, strictly decreasing on (-oc, (1) and equals for r 2 (1) because of the following expression:
Σ K (Oy 7) if ((K),
[(T)
1=1 (0(0-1) -)) if (0()), ((K-1)] for .,...,.. K.
i > (11)
Then n defined in line 2 of Algorithm| exists since [(0(1)) = < 1. We also have that [(0(n)) 1 (()) < 1. When < K, we have that f(0 ((0))) E (0 0(++1))
(0 - (m+1))) 2 by definition. Then we
E ( (0(x)1) (n))
and
Li=1
(10) 1
Σ Li=l
B(0)
(1)
11
i=1
n
(() Σ
(3) +1
1.
When = K, we have that Ein (() K0(K) 1, that is,
Σ 1=1 0())
< 8[K].
K
Then
>k
((0)
-1
K
D O(s)
f
(
K
K
i=1
K
K
0 ())
Σ
(3) +1
iml
im1
=
1.
Combining these two cases, we have
-= 010) 0
n
which is what line 3 of Algorithm returns. Since f(T) is strictly decreasing on (-00,01))) r* uniquely satisfies f(r*) = 1.
Since Σt (()) can be calculated cumulatively in O(K) time and the quick sort runs in O log K) time, Algorithm runs in O(K log K) time in total. Furthermore, since 7" is unique and T max(0, - T* 0), we ensure that 11(0) is a singleton, which concludes the proof.
29

---

C.2 Proof of Proposition 19
Proof. By Definition 10, the statement is equivalent to
argmax 02 argmax Tlog (0),- YE
tEy
According to Lemma 18 and Algorithm I there exists T E R such that Tlgg (0), = max - O..
We also have that max, 0, by contradiction: if max, dr 5, Tlog (0) 0 holds, which contradicts Tog (0) A
Denote the set argmax,ey by I. For any E I, we have Tlg (0); = (a T, 0. = max, 8 O. For any j & I,
* 0 > log 00) = max 0) =0 T max, 02
1f 2 T: log ( = max(0; - T, 0) = 0 max, 0₂ -T.
These imply that for any I, Flor (0); 2 Tox (0); and the equality holds and only if E I. which concludes the proof.
D Additional Examples
In this section, we further provide more examples of target losses to demonstrate that we can generate convex smooth surrogate losses for wide range of target prediction problems. The generated convolutional Fenchel- Young losses are automatically guaranteed to entail linear surrogate regret bounds thanks to Theorem
D.1 Multiclass Classification with Rejection
Problem setup. In multiclass classification with rejection [25), the class space is y = [K] and
the prediction space 5 = [K + 1). which is augmented by rejection option K + 1. We focus on the case that rejection cost e (0, 0.5) here. For input instance with class probability n E AK the goal is to predict the most likely class label E argmaxggy Ne if max ml predetermined cost c, and refrain from predicting otherwise. The standard target loss is the 0-1-c loss:
for the
[ + yl,
[K), t
lo v) [
that is, the prediction suffers from the ordinary classification error if it is wrong class label, and suffers from an intermediate error it chooses refrain from prediction.
We adopt the decomposition 33) for this task: (t) = (t, 1). lei (t, K)] = 1 - e, t + K + 1, and (t = cl if K 1. We choose the label encoding function p(y).. as in the
multiclass classification task. In this case, N = K + 1 and d = K, and L [11] - c,c), where
1 is K dimeenniional.
Loss formulation and calculation. In this case, we consider the Shannon negentropy 52 as in Section 4 Based on the discussion above and Lemma & the conjugated convolutional negentropy Oj can be written as follows
exp 02 +1 n. 1(1-0111- c)mkhH))
(0)
min (2 + LPT)= min In IEAR
(26)
#EAK
and we can then get the corresponding convolutional Fenchel-Young loss as follows, by noting Qr(p(v)
0 for all E y::
K exp(O. +1 -1-T; (1-c)Tx+t)) c)xx+1) 0y-
La (0,)) = min In
(27)
#EAKI1 11
To compute Loy, we need to know the minimizer in 26 We show its closed form below.
Lemma 22 For any 0 E K the problem 26 has unique minimizer π T²(() E =IT which can be obtained OKK) time. Denote by y" an arbitrary element in argmax, [( By Pthen the minimizer
We emphasize that the domain of conjugate is K-dimensional, despite the π is in K + 1-simplex. Though chosen arbitrarily, uniqueness guaranteed: argmax sets singleton in the first and third cases.
30

---

can be written as follows:
1f exp(0,,)
E
1 exp(0:+1]
>
(0) =
CK+1,
if ΣK exp(a))
exp((xe)
< <1 -c
2())ey- + (11-n())eex-
else,
1 exp(0:) exp(0,-)
-1) In (1-5)
where 7(0) In
Proof. First, the Lagrangian of the minimization problem (26) is written follows:
K+1
3) exp(0 +1 (1--(1)))mpp c)mK+1) a T π +
Σ
K+1
= in Σ exp(0; +1 5,)) - -1 -(1-c)TK+1- -
+
Σ
1
where 01,,.., aK+1 2 O and 3 E R are the Lagrangian multipliers. Since the log-sum-exp term is convex and differentiable and the feasible region A K+1 is convex, the KKT conditions are necessary and sufficient for the optimality of π E II(O), which requires that there exists (a", 333" satisfying
exp(0, + 1 - -TT)
for any y 1,... K,
(28)
Σ exp(0: +1 -mt)
1 c= 3-- -"-Ok-+
-kk+1: -0K=1
(29)
1 1T = 1, n" 2'0 a $220 0, ay = 0,
(30)
for any y = 1,... ..... K
(31)
continue the proof with the following four observations:
Observation By noting
- 0.5, we have
exp(8y-) ΣK 1 cxp(8.) 2 21-c- = argmax = }
d'E[K]
Observation 2.
From the KKT conditions, we have
exp(Oy.) exp(0,-)+ EE exp(0,
>1 1
n²" = By-
To see this, let us integrate the above left-hand side with
28 and 29
exp(Oy- + +1 - πÿr))
8 o.-- Σx exp(0, + - m.)
by 28
exp(fy.)
exp(Oy-) + Ik
2i=1, exp(8; + t 7z))
exp(0y-)
by TT- < 1 and क. 2 0
exp(00-)= + 21=1, exp(0: +1
c
by the assumption by
= 3" a'++1>
which indicates that a+41 > a 2 0. and thus x *+1 due to and 31
On the other hand,
for any y E [K] {v/") }. we have
8" ag = cxp + nT))
by 28
Σ exp(1; + - TT))
31

---

1 1 exp(Oy. + +1 -xz-)
Σ exp(0; + nT))
< 1 (1 (1-c)
by the same argument (+)
= 0
< 1
by [0, 0.5)
8 a-
by
and thus o > 0K+1 we verify π²" Cy'-
0, which indicates that ~ except for y y due to (30 and (3). Thus,
Observation 3.
From the KKT conditions, we have
exp(0g.)
π ek+1-
_ exp(0.)
To see this, we show the contraposition of Observation 3. Suppose there exists y E [K] such that Ty > 0. Then, we have 0y = 0 due to 31. and consequently
exp + m.)
g
by 28
and 0y
Σ exp : + mT)
(32)
8 ak+1
by 30
=1
by 29
Then, for any s/ E [K] \ {u). this inequality implies
exp(0y + 1 m.y))
8r oz.
by 28
Σ exp(0: 1 n.
K
$ 1 exp(fy + - mT,)
K Di=1 exp(0: + nT.)
< 1 (1 c)
by 332
c
< 1 - c,
by c E [0.0.5)
which indicates that ay and o... = 0 due to 30 and 31
Then, we have
exp(0, + - m nT))
exp(0, TT
K exp(0y +1 Di= exp(O: 1)
exp(0, - mT)) ΣK Li= exp(0.)
exp(0y)
exp(0y) + Ei=l, exp(0: + mT))
2 2-c
where we used 332 the last line. This inequality further implies
exp (0y-)
exp(8,)
21-6
Σ exp (.))
exp(0y) + Ei=Lit exp(O, + mT)
Thus, the contraposition of Observation 3 is shown.
Observation 4. From the KKT conditions again, have
exp
exp(0,-)
2 1 1 c
ΣK (xp(
exp(ey.) E exp(f; + +
n¹ = (0)e,, + (1-2(0))ekt),
E exp(0x) - 1) In (_=). ). To see this, we carefully examine क." First, exp(e,-)
where >(0) In
there exists different v/', y" [K] with TT,, " O. we have
8 exp(Oy/ + +1-
by 28 and o = 0 since T. >
Σ 1=1 ex + n;))
32

---

exp(Og" + 1 -mj²)
by 28 and 0g" = since Ty. > 0
Σ exp(0: + mi)
8" -ok+1
by ak41 2 0
by 29
0.5,
which is impossible since
exp(Oy m.y exp(0, + x;)
exp(Oy" +1 Tz.')
Ei=1 exp(0) 11mm,) S
This contradiction indicates that there exists at most one y E [K] such that n... >> O. Second, show y E [K] with 7 must be y y²" To see this, suppose there exists y [K] such that xy 0 but y + y", then y = 0 for any y E [K] \ {y} and we have
exp + n.))
exp(0, m.)
Σ 1= exp(0: + x;))
exp(8y Tz) + E exp(O:)
8 0y
by 28
8r
by Tyy > 0 and (3)
2 8r O.K+1
by a 2 0
2 -
by 29
0.5.
However, this contradicts the following inequality:
exp(Ay- + 1 Tz-)) D exp(0; + -
exp(0,y))
exp(0, - -T)) + Ei=1it
exp(Oy.) )
by n. 2 0
Σ exp(Oi)
2 1-c
by the assumption
> 0.5.
Thus, we have verified that Th is possible with y y" or y K only, From this, we have
π = -y. Cy- (1 ,..- eck+1
(33)
From now on, we show that
π = 700e, + (1 (1-)
a' =0 3==1-c
(34)
fulfill the KKT conditions under the assumption of Observation 4. By using (33) we have
exp(Oy- + nT.)) Σx exp(0; + 11 - m;)) exp(fy- Ty-) + 5K Li=1, exp(0.)
exp(0y. - Tÿ-)
by 33
= - agy
by 28
= -1-c ay ax+1
by 29
By elementary algebra and plugging in a* given by follows:
we can solve it with respect to TT- as
/ exp(O.) exp((0-)
1) In (1- =0()).
Tg. In
(35)
33

---

By rearranging the assumption of Observation 4, we have
_ exp(O.) 5 I-c² exp(Oy-)
c
from which we see 0 S " 7(0) I 1. All in all, (TT* ,", 3*) in 34 fulfill the KKT conditions, and thus Observation is verified.
By combining Observations 2, 3, and 4, we have shown the closed form of n (0)).. Furthermore, Observation guarantees the uniqueness of π (0)
Lastly, is easy to see that π T0) (0) can be computed in linear time because both of the following terms exp(0,-)
and exp(Og-)
cxp(f,-) + Ei 1iiy exp(0,+1 +)
Σ/11 iiml cxp(8.)
can be computed in linear time.
D.2 Multilabel Learning with Precision @
Problem setup. In multilabel learning, the target prediction space y [24] is the collection of indices of all possible combinations of d binary labels with | K 24, Precision @ k a common
performance metric for multilabel ranking. We consider that the prediction space y = [(]]] is the
collection of indices of all possible size-k subsets of multilabels with | = N ( In addition,
we encode the label E y into p(y) E {0, 1 and the prediction t E 5 into fu(t) E {0, 133, where (n(()) is the collection of all distinct permutations of el + eg. Then, the target loss of Precision @ l defined as follows:
((t, = 1 Ei p(y)
k
This is the portion of binary labels with value in the top-k list.
We adopt the decomposition 3 by using the aforementioned p(y). eP(1)
m(t) k and c(y) 1 for
all E y.
Loss formulation and calculation.
For Precision@k: k: we consider the base negentropy
a(p) Σ (pr Iup; + + (1- p.) In(1 -p.)).
Then, have
(0) = >
In(1 + exp(O:)),
1=
and
(0) min
In 1 exp 0: Σ man(t):)
(36)
We can simplify it into the following problem:
min Σ In (1 exp (0. 0, (0--
1 (--1() )
(7)
(37)
vEV
1=1
where == (v Rd o E [0, 1), ||a|| = k}. Then, the convolutional Monchel-Young loss can be
written follows:
Σ In (1+ exp exp (0. 1 (0:- ().
La (0 min DEV
To calculate the gradient of T. v) we only need the solution x² in the optimization problem 37 which can be obtained efficiently.
34

---

Algorithm 2 Exact Solution of 37 in (ddInd)
1: Set f(A) Σx i=1 m min X, X,1}}
2: Sort 0 = (0 1] E 2d such that (1)) 2 ... B120)
3: n + mn E [2d] (()(n)) < k:..
4: X* ((n) f( 1) ((0
A- (w)
(0 (0(m+1) 1())).
5: of max
(0,0(0mmnn)) min
X" 13}.
Lemma 23
For any 0 E Rd, the minimization problem 37 has unique minimizer v", which can be obtained in (dd log d) time with Algorithm
Proof.
The uniqueness can be seen by noting that the objective function strictly convex and its domain V is compact and convex.
Let us analyze the Lagrangian of the minimization problem 37 which can be written as follows:
a(v,a,,,7)
Σ exp 0, (.
1 ;, ) To 3 (v 1) +
Σ m - (38)
d
where a E 1 B E 200 and E IR are the Lagrangian multipliers. Then, we have the following
KKT conditions:
exp(0; vi)
= + 8 - a
for any 1....,d
(39)
I exp(0: - v0)
1 -T 0² = k; 0 5- 1, a 2 0, 3 0, 0/4 0, (1))))))
(40)
for any = 1,...,d d
(41)
where the inequalities in 40) are element-wist wise.
First, we show that the KKT conditions fulfilled by of max min(0; - 1>) for each i [d]. where X = Innnnn/((000 )))). Fixing i E [d]. we divide into cases. If o > 0 - X²,, we have
exp(O: - 0/))
1 + exp(O: - u, <7";
which implies Br of < by (39 Since 8 > 0 by 40 we have of > O, which implies of
due to If < 0 X", we can show oi = 1 similarly. Thus, we have
of 0 X1, then of = 0;
of 0, X² then of 1.
Moreover, let us divide into cases on 0 - X If X < 0, we must have of > 0, - X since 2 E [0, 1] (due to the feasibility (40)) which yields of 0. If - we have of similarly. If < 0; X < 1, we have x.r 0: - X otherwise it ends up with contradiction say, supposing of > 0, ^", then we have 0 o > 0 >; which contradicts the premise 0, X [0, 1].
Combining all above, we have verified that
= max(0, min (0, X*11} for E [d]
fulfills the KKT conditions.
Next, we show that Algorithm returns this n²_ By noting the constraint Σd oy = 1 in the feasibility conditions (40) we have
(S(A*)
Σ max - 1]] k.
Thus, we need to solve f(x*) = k to obtain v". Let us sort the elements of Ø == 10: 0 - 1] e
2d such that 0(1) 2 ap. The solution to f(x*) k uniquely exists since we have
35

---

5-
Conv FY Logistic
1.0
Sigmoid
Proposed
Probability Estimate
0.8
Loss value
3-
0.6
0.4
0.2
0.0
-4
-2
8
0
(a) Loss curves for +1.
(b) Probability estimators
Figure I: Visualization the convolutional Fenchel- Fenchel-Young loss, logistic loss, and probability estimators.
f(0a)) = = < k, 24) = d > k. and f is continuous and strictly decreasing on 18 (1)-- From the strict decreasing nature, can also be inferred that Step 3 of Algorithm 2 is the largest possible n E [2d] that (6)) < k and (1) 2 k, which indicates that the solution is in (0n+1, (w)) Furthermore, f is linear on each segment [0;+1]. (G] This indicates that for the point X (ett))0(m)) we have
5(0m))1()))))) f(((n+1)) f(0(m) f(X*) k.
f(O (1+1)) + + (())
8(n+1) (m)
which yields Step 4 in Algorithm
2
The time complexity of sorting θ is (dlogg) Note that the computation of f(2) is in O(d) and can be found using binary search due to monotonicity of in O(log d) steps, we can conclude that Step (dlogg).
E A Special Case: Visualization on Binary Classification
In this section, we visualize the graphs convolutional Fenchel- Young losses and the corresponding probability estimator (provided in Theorem 17p for binary classification get more intuition. For binary classification, we adopt the class space D f-1, +1), and the target loss loz (y, t) [y t]. We use the following decomposition of the target loss:
p(+1) = p(-1) -(-1)= e0 (0(+)) 1, (-(-1) 1, and c(+1) d-11 1
With this decomposition, surrogate losses can operate univariate prediction, which is convenient for the visualization purpose.
We compare convolutional Fenchel- Young losses with the standard Fenchel-Young losses generated by the binary Shannon negentropy:
[]
1
)r) + ( p) In
a(p)
+ In
2 pp)) p):
where 1/ + 7 the positive class probability and 1 - p =: 1- is the negative class probability. The corresponding convolutional negentropy is as follows:
Dr(p)- = +
In
2 + p
+
In -P) + mmx(p. -p},
2
2
where max(p. -p} = 1 min 11+1 7-1 is the negative Bayes 0-1 risk of class probability
2
(141,7-1) (1 + p, p). Then, the conjugate of convolutional negentropy be written
36

---

as follows:
In + exp(O (0 + 1)) 221 In(2),
if < -1
(7((0) =
f
In + exp - 1)) - i
Correspondingly, the convolutional Fenchel- Ceuchel-Young loss is
Im(1 + exp + 0)) #(1+y]+1
if < -1 if -1
L (0, We can explicitly write down the gradient of the conjugated entropy as follows:
In(2) 0y 2
In(1 + exp(0 - 1)) 8(1+)-11 if <
2
exp(1+00
2 < -1
(1+
(al2
expld
2. 0>1
exxp((011
0,
E [[1,1]
which is the estimator of 1+11(+11) + 17-1((11) 211-
1---+-11 17+1 2/2 by Theo-
rem 17 Finally, we can use the link function V Vol2; + the estimator of 1)+1.
We show the convolutional Fenchel-Young loss and logistic loss (which is the standard Fenchel- Young loss generated by the binary Shannon negentropy) in Figure T It can be seen that the convolutional Renchel-Young loss is linear in the shaded region E 1-1, while resembling the logistic loss outside of this region. Compared with the sigmoid function used for probability estimation with logistic loss, the link function induced by the convolutional Fenchel-Yoon -Youg loss also generates valid probability estimate in (0, 1] for any R, with 0 E [-1,1] generates constant
value 0.5 as the estimate.
Further discussion. In case of binary classification,, Figure (a) nicely illustrates that the con- volutional Mouchel-Younge loss linearly "extenns" the logistic loss
which the boundary point for binary classification. This illustration is possible because the above formulation for binary classification operates on the univariate score R. The linear extension the boundary point aligns with Frongillo and Waggoner (39), which shows the square-root regret lower bound by assuming that a surrogate loss is locally strongly convex around the boundary points, In general prediction tasks, it is not straightforward to overcome the square-root regret lower bound by such a linear extension because the boundary points for high- diledmmmiiionl prediction task can be infinitely many. By contrast, convolutional Fenchel-Young losses provide a general recipe to get linear surrogate regret bound via infimal convolution.
F Additional Empirical Results
F1 Multiclass Classification
To provide empirical validation of our proposed results, we use the loss introduced Section example and evaluate its performance on the ImageNet- 1k dataset 332 using the ResNet-50 architecture [43].
ImageNet training script. Specifically, we use stochastic gradient descent (SGD) with momentum of 0.9, training for 120 epochs with mini-batch size of 256. The initial learning rate is set to 0.1 and divided by 10 every 30 epochs. For comparison, also report results obtained using the standard cross-entropy loss under the same configuration. All experiments are conducted on 8 Gefforce RTX 3090 GPUs, and we report the average validation accuracy over independent runs.
Experimental Setup. We follow the default configuration of the PyTorch
Results and Discussion. dard cross-entropy loss in terms of validation accuracy under a 5% t-test,. This improvement is achieved without any additional hyperparameter tuning, demonstrating the potential of our approach. Meanwhile, the computation time per epoch remains comparable between the two methods, which indicates the efficiency of the proposed loss. These results confirm the compatibility of our loss with both mini- batch and distributed optimization settings.
shown in Table 1. our proposed loss slightly outperforms the stan-
37

---

Table Comparison between cross-entropy loss and the proposed loss ImageNet-Ik using ResNet-50.
Metric
Cross-Entronn Pross-Entropy Loss
Proposed Loss 18)
Accuracy (%)
76.40
76.81
Averaged Running Time / Epoch (s)
647.22
653.63
F.2
Classification with Rejection
We further evaluate the proposed loss 27 under the classification with rejection (CwR) setting, where the rejection cost fixed
0.05. The experiments are conducted on the CIFAR-10 and CIFAR- 100 datasets [46]. We adopt the WeseRes architecture [96] with widen factor of and hidden dimension of 50 as the backbone network for all experiments.
Experimental Setup. We train each model for 120 epochs on 8 GeForce RTX 3090 GPUs with per-GPU batch size of 128. The optimizer is SGD with momentum of 0.9, weight decay of 5e and an initial learning rate of 0.1. The learning rate is scheduled by cosine annealing.
For data augmentation, each image is first converted tensor, then padded by 4 pixcls each side using reflection padding. followed by random cropping to 32 x 32 and random horizontal flipping. The images are finally normalized using the datasct-specific mean and standard deviation. We report the average system accuracy (1 (1-averaged 0-1-c loss) and acceptance rate over 5 runs. Meanwhile, we also provide the result of ordinary classification using the similar loss (88) proposed.
Table 2: CwR/Classification performance of proposed losses CIFAR- 10/100 using WidcResNet-28.
Metric
CIFAR-10 CIFAR-100
CwR with (27
System Accuracy: c=0.05 (%)
96.79
91.90
Acceptance Rate (%)
92.84
65.94
Averaged Running Time / Epoch (s)
5.79
6.64
Classification with [8]
Accuracy (%)
93.87
74.36
Averaged Running Time / Epoch (s)
6.07
7.41
Results and Discussion. As shown in Table 2 both CIFAR-10 and CIFAR- 100 experiments demonstrate that our proposed loss successfully performs classification with rejection, achieving higher system accuracy while maintaining reasonable acceptance rate. This indicates that the model learns to reject uncertain samples effectively without sacrificing overall performance. In addition, the average computation time per epoch even lower than that of ordinary classification. which we attribute to the O(K) complexity of gradient computation for the proposed formulation. compared with the O(K log K) cost standard classification. These results confirm the efficiency and practicality of our loss for reliable decision-makin under uncertainty.
38


Reviews:
[{"review_id": "zqhLboG96z", "reviewer": "Reviewer_iy2f", "summary": "Previous work has shown that while convex and smooth surrogate losses are effective for estimation and optimization, they often face a trade-off between smoothness and achieving linear regret bounds. This paper overcomes that trade-off by introducing a novel surrogate loss that is both convex and smooth, yet still admits linear surrogate regret bounds. A convolutional negentropy is constructed by encoding the structure of the target loss into a chosen base negentropy, resulting in a convolutional Fenchel–Young loss that inherits both convexity and smoothness. Crucially, the derived prediction link, when paired with this loss, enables a linear surrogate regret bound and provides a consistent probability estimator.", "questions": "1. While the theoretical contributions are compelling, I believe the paper’s strengths would be significantly enhanced with empirical validation. For instance, the authors could evaluate the proposed surrogate loss on toy datasets or simple multiclass classification benchmarks with the algorithm presented in Section 4. This would help illustrate the practical impact of the loss and clarify its advantages over existing approaches.\n\n2. I found the definition and role of the term $T(p)$ in Equation (8) somewhat confusing. In line 69, the authors state: *“We encode the structure of a target loss $\\ell$ into the chosen base negentropy by adding the negative Bayes risk of $\\ell$”*, and in lines 210–211, they mention: *“This polyhedral convex function $T$ is an affinely transformed Bayes risk of a target loss $\\ell$”*. While Equation (9) shows that $T $ is an affinely transformed Bayes risk when $p = \\mathbb{E}_{y \\sim \\eta}[\\rho(y)] $, this does not seem to align with Equation (11), where $ p = \\rho(y) $. Could the authors clarify this discrepancy and more precisely define the conditions under which the interpretation of $ T(p) $ holds?\n\n3. Minor points:  \n   - Lines 256 and 297: The term *“Theorem”* should be replaced with *“Corollary”*.  \n   - Line 282: “The regret bound (13)” should be rewritten as “The regret bound in Theorem (13)” or “The regret bound in Eq. (14)”.  \n   - Equation (18): The notation $ \\theta_i $ should be corrected to $\\theta_y$.", "limitations": "Please see the above questions.", "rating": 4, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths:\n\n- Proposes a novel surrogate loss that is both convex and smooth while preserving linear surrogate regret bounds.\n\n- The writing and presentation are clear and well-structured.\n\nWeaknesses:\n\n- The paper would be stronger with the inclusion of empirical results to support the theoretical claims.", "was_revised": true, "final_justification": "Before the rebuttal, my main concerns were the lack of empirical results and the unclear definition and role of the term $T(p)$. During the rebuttal, the authors provided additional empirical results on ImageNet and clarified the interpretation of $T(p)$. While these responses addressed my concerns, I am not very familiar with this field and have not carefully reviewed their proof. Therefore, I maintain my score with low confidence.", "rebuttal": "Many thanks for your valuable suggestions! We will fix the typos in the revised manuscript, and the questions and corresponding answers are summarized below:\n\n**Q1. It is beneficial to evaluate the proposed surrogate loss on multiclass classification benchmarks.**\n  \n**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]. \nOur experimental setup follows the default configuration of the PyTorch ImageNet training script: \nwe use SGD with a momentum of 0.9, training for 120 epochs with a mini-batch size of 256. \nThe initial learning rate is set to 0.1 and divided by 10 every 30 epochs.\nFor comparison, we also report results using the standard cross-entropy loss under the same configuration.\nAll experiments are conducted using 8 GeForce RTX 4090 GPUs, and we report the average validation accuracy and running time per epoch over 5 runs.\n\n|| Cross-entropy Loss | Proposed Loss in Section 4 |\n| ------------------------------| ------------------------------ | -------------------------------------- |\n|Accuracy| 76.45%                         | 76.82%                             |\n|Averaged Running time/Epoch| 643.41 sec |  649.84 sec|\n\nInterestingly, our proposed loss slightly outperforms the standard cross-entropy loss in validation accuracy, as shown in the table above. \nThis improvement is observed without any additional tuning, indicating the potential of our approach. \n\n\n**Q2. The interpretation that $T(p)$ is an affinely transformed Bayes risk of the target loss should be defined more precisely.**\n\n**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}.$\n\n\n[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.\n\n[2]. He, K., Zhang, X., Ren, S. and Sun, J. Deep residual learning for image recognition. In CVPR, 2016."}, {"review_id": "hadjZJt8sc", "reviewer": "Reviewer_jSoZ", "summary": "This paper presents a theoretical contribution to machine learning by constructing convex smooth surrogate losses that achieve linear surrogate regret bounds for discrete prediction problems. This provides a theoretical contribution a long-standing belief in the community that there exists a fundamental trade-off between smoothness and linear regret bounds.", "questions": "Could you provide experimental evaluations? If not, could you explain why?\n\nWhat are reasonable values for the constants that imply computational complexity?\n\nCould you characterize problems where your approach would be inferior to existing methods? E.g., when $N$ is small or when computational resources are limited?\n\nHow do these losses behave under the stochastic setting of SGD with mini-batches?", "limitations": "The lack of empirical evaluation very much weakens the paper.", "rating": 5, "confidence": 1, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 2, "significance": 2, "originality": 2, "strengths_and_weaknesses": "The construction of convolutional Fenchel-Young losses through infimal convolution is elegant and seems per se theoretically sound. The key innovation lies in encoding the target loss structure into the base negentropy via the polyhedral function $T(\\mathbf{p})$, which enables the additive decomposition crucial for achieving linear regret bounds.\n\nWhile this is primarily a theoretical paper, the complete absence of experiments is notable. Even simple synthetic experiments comparing convergence rates of the proposed losses against existing smooth losses (logistic, squared) and non-smooth losses (hinge) would strengthen the practical relevance, and validate the results from an empirical point of view. \n\nThe computational complexity of the approach is not discussed, at least not in a way that would clarify how expensive the approach is. In particular, in relation to standard loss computations.", "was_revised": true, "final_justification": "Please note that this review does not give a judgement of the validity of the theoretical proofs.\n\nWhile the performance improvement in the experiment in the rebuttal lies much below the typical standard deviation for this type of experiment at that level of resulting accuracy, I appreciate the addition.", "rebuttal": "Thank you for your valuable suggestions! We summarized the questions and provide the responses below:\n\n**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.**\n\n**A1.** Thank you for your advice! \nTo 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]. \nOur experimental setup follows the default configuration of the PyTorch ImageNet training script: \nWe use SGD with a momentum of 0.9, training for 120 epochs with a mini-batch size of 256. \nThe initial learning rate is set to 0.1 and divided by 10 every 30 epochs.\nFor comparison, we also report results using the standard cross-entropy loss under the same configuration.\nAll experiments are conducted using 8 GeForce RTX 4090 GPUs, and we report the average validation accuracy over 5 runs.\n\n|| Cross-entropy Loss | Proposed Loss in Section 4 |\n| ------------------------------| ------------------------------ | -------------------------------------- |\n|Accuracy| 76.45%                         | 76.82%                             |\n|Averaged Running time/Epoch| 643.41 sec |  649.84 sec|\n\nInterestingly, our proposed loss slightly outperforms the standard cross-entropy loss in validation accuracy, as shown in the table above. \nThis improvement is observed without any additional tuning, indicating the potential of our approach. \nMeanwhile, we also observes that the computation time for standard method and our method per epoch are similar, demonstrating the efficiency of our proposed loss.\nThese results also confirm the compatibility of our loss with mini-batch and distributed optimization.\n\n**Q2. How do these losses behave under the stochastic setting of SGD with mini-batches?**\n\n**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. \n\n**Q3. The computational complexity of the approach should be discussed in relation to standard loss computations.**\n\n**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. \n\n- 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.\n\n- 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. \n\n- 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)$. \n\nWe appreciate your comment and will move the time complexity discussions from the Appendix to the main body in the revised version to improve clarity.\n\n**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?**\n\n**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. \n\nA 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.\n\n[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.\n\n[2]. He, K., Zhang, X., Ren, S., and Sun, J. Deep residual learning for image recognition. In CVPR, 2016.\n\n[3]. Martins, A. and Astudillo, R. From softmax to sparsemax: A sparse model of attention and multi-label classification. In ICML, 2016.\n\n[4]. Charoenphakdee, N., Cui, Z., Zhang, Y., and Sugiyama, M. Classification with rejection based on cost-sensitive classification. In ICML, 2021.\n\n[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.\n\n[6]. Menon, A. K., Rawat, A. S., Reddi, S., and Kumar, S. Multilabel reductions: what is my loss optimising? In NeurIPS, 2019.\n\n[7]. Gao, W., and Zhou, Z. H. On the consistency of multi-label learning. In COLT, 2011."}, {"review_id": "hb4DWG8UfN", "reviewer": "Reviewer_b4uG", "summary": "This paper demonstrates that the believed tradeoff between smoothness and linear regret rate of a surrogate loss is not true. This paper shows that for an arbitrary discrete target loss, there exists a smooth surrogate loss that facilitates linear regret. This result is presented constructively, allowing for its use. Beyond this core result, this paper presents an extended tightness result and demonstrates the proposed construction for multi-class classification.", "questions": "1. Could you comment on what inspired examining Convolutional Fenchel–Young Losses as a candidate loss which is smooth that satisfies linear regret rates?\n2. To help with the presentation, have you considered adding any plots which might give insight into the geometry?\n3. Section 3.6 talks about a Fisher-consistent estimator, could you add to the appendix a formal definition?", "limitations": "yes", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 4, "significance": 4, "originality": 4, "strengths_and_weaknesses": "Strengths\n1. Answers decisively that a belief that a tradeoff of linear regret and smoothness is not true for convex surrogates. This is a novel and insightful result in the convex surrogate literature.\n2. Furthers the established literature regarding Fenchal-young losses and their applications. \n3. The results are practically constructive (which is not always the case in the convex surrogate literature), allowing for the use of these novel insights. \n4. The paper is well-written, given the technical density behind many of the ideas being used.\n\nWeaknesses\n\nAlthough the results are clearly presented, rigorously proven, novel, and valuable, I find the underlying inspiration and intuition that facilitated said results to be opaque. From an educational standpoint, I would have found it intriguing to get insight into how this very, very specific approach was conceived while other researchers considered this tradeoff infeasible.", "was_revised": true, "final_justification": "This result is surprising and non-trivial to show within the convex surrogate literature. The work is clearly presented and is constructive allowing for not just theoretical insight but practical application as well. For that reason I recommend the score to be a 6.", "rebuttal": "Thank you for your constructive suggestions and acknowledgment! We summarize the answers to the questions below: \n\n**Q1. To help with the presentation, it is beneficial to add plots that give insight into the geometry.**\n\n**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.\n\n**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.**\n\n**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.\n\n**Q3. Section 3.6 talks about a Fisher-consistent estimator. Could you add to the appendix a formal definition?** \n\n**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$. \n\n[1]. Frongillo, R., and Waggoner, B. Surrogate regret bounds for polyhedral losses. In NeurIPS, 2021."}, {"review_id": "mHCz7j2MwP", "reviewer": "Reviewer_DQwU", "summary": "The paper studies *surrogate regret bounds* in the context of multiclass prediction problems. Given a *target loss* $\\ell: \\mathcal{Y} \\to R$, a *prediction link* $\\varphi: R^{\\varrho} \\to \\mathcal{Y}$ and a class distribution $\\eta \\in \\Delta_{N}$, the authors show that there is a surrogate loss $L$ satisfying the following regret bound:\n\n$$\\mathtt{Regret}(\\ell \\circ \\varphi; \\eta) \\lesssim \\mathtt{Regret}(L; \\eta).$$\n\nThe construction is via the framework of so-called *Fenchel-Young* losses. Given a CCP regularizer $\\Omega$,\n\n$$L_{\\Omega}(\\mu, \\theta) = \\Omega(\\mu) + \\Omega^*(\\theta) - \\langle \\mu, \\theta \\rangle \\geq 0$$\n\nis the associated Fenchel-Young loss. The paper shows how to adapt a given regularizer $\\Omega$ to a target loss $\\ell$ so that:\n- the induced Fenchel-Young loss satisfies a linear surrogate bound;\n- the induced Fenchel-Young loss is convex and differentiable (or even smooth when $\\Omega$ is strongly convex).\n\nIn particular, it is well-known in the literature that smooth losses achieve fast excess loss bounds for ERM (Srebro et al., NeurIPS 2010), but transferring these guarantees to the target loss was thought to suffer from square-root regret bounds.\n\nTo achieve this, the authors introduce a so-called *convolutional negentropy*, which is a sum of a base negentropy $\\Omega$ and an affinely-transformed version of the Bayes risk. Under this choice, the surrogate regret can be written as the sum of the Fenchel-Young loss risk and a convex combination of the *target* regret, which yields a linear upper bound on the surrogate loss after rearranging. The authors present a strengthened version of the upper bound, where the constant only depends on the affine dimension of the matrix of concatenated loss vectors.", "questions": "My main question was already posed in the \"strengths and weaknesses\" section. Other minor questions / suggestions:\n\n- My understanding is that $T$ is used to \"couple\" the target loss $\\ell$ with the base negentropy $\\Omega$. Are there other ways of systematically producing such couplings? If so, do some of these lead to less tractable losses?\n- p. 3, line 120: \"$\\mathbf{dom}(\\Omega)$\" should be $\\mathbf{dom}(f)$.\n- Definition 10: $\\pi$ simultaneously denotes a selector function and vector in the simplex. The authors may want to consider alternative notation for the selector to avoid confusion.\n- Similarly, $\\rho$ and $\\varrho$ are used with very different meanings (label encoding vs. dimension of the encoding).", "limitations": "See my comment under Strengths and Weaknesses.", "rating": 5, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 3, "strengths_and_weaknesses": "**Note**: The literature on surrogate regret bounds is far from my area of research. As such, I primarily reviewed this paper for correctness. \n\nStrengths:\n- The problem and proposed solution are clearly stated.\n- The contribution appears to be novel (based on my limited knowledge of the literature).\n\nWeaknesses:\n- Notation can be confusing at times.\n- 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).", "was_revised": true, "final_justification": "I have decided to raise my score after reading the authors' responses and other reviewers' comments, which helped me refine my understanding of the significance of this work.", "rebuttal": "Thank you for your helpful advice! The answers to the questions are summarized below, and we will integrate the discussions into the revised manuscript.\n\n**Q1. There exist typos, and the notations are confusing at times.**\n\n**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.\n\n**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?**\n\n**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.\n\n**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).**\n\n**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.\n\n[1]. Blondel, M.. Structured prediction with projection oracles. In NeurIPS, 2019."}]

Author rebuttal:

Meta-review: I have read the paper and really enjoyed it. In the camera-ready version of the paper, I strongly suggest the following:

1- naming. It is fine to use the terminology introduced by Blondel et al but those loss functions have a longstanding history in information geometry which says a lot more than the motivation behind the "Fenchel-Young" naming (which is the remainder of FY inequality). In particular, it is crucial to recognize Shun-ichi Amari's contribution: any FY loss is a Bregman divergence in disguise and the introductory notation is in Amari and Nagaoka's textbook (Methods of Information Geometry), Chapter 3 section 3.4, the canonical divergence (it is exactly eq. 3.44). This says exactly how each argument can be named. Then, there is Leonard J. Savage: FY losses encode the regret of a proper loss, see reference JMLR:v17:14-294 below (proposition 7 point 4). This gives the normative "why" for using such a FY loss (independently of the surrogate regret). I am confident that a nice inclusion of these points in the paper will address the "why such losses" asked by reviewers (e.g. b4uG, DQwU), perhaps by adding a section 2.4 to the paper.

2- notations. Please fix the suggestions of reviewers and make a long read of the paper -- probably by a non-author -- to spot and fix notations. The importance of this step should not be underestimated: it is painful to read a nice paper and to be stopped at times because of imprecise or confusing notations. Example: Algorithm 1 uses notation $[K]$ with two different meanings (index and set). This must be explained and fixed.

3- (no) experiments. I appreciate the effort made by the authors to deliver experiments but I think they are not necessary for the camera-ready (if the authors want, they can eventually push them to the appendix).

@article{JMLR:v17:14-294,
  author  = {Robert C. Williamson and Elodie Vernet and Mark D. Reid},
  title   = {Composite Multiclass Losses},
  journal = {Journal of Machine Learning Research},
  year    = {2016},
  volume  = {17},
  number  = {222},
  pages   = {1--52},
  url     = {http://jmlr.org/papers/v17/14-294.html}
}
Decision: Accept (spotlight)