Learning with Fitzpatrick Losses
Authors: Seta Rakotomandimby
Jean-Philippe Chancelier
Michel De Lara
Mathieu Blondel
Venue: NeurIPS 2024 poster (2024)
Keywords: loss functions
convex analysis
monotone operators
Primary area: optimization
TL;DR: A new family of loss functions based on monotone operator theory that lower bound Fenchel-Young losses, such as the the logistic loss.

Abstract: Fenchel-Young losses are a family of loss functions, encompassing the squared,
logistic and sparsemax losses, among others. They are convex w.r.t. the model
output and the target, separately. Each Fenchel-Young loss is implicitly associated
with a link function, that maps model outputs to predictions. For instance, the
logistic loss is associated with the soft argmax link function. Can we build new
loss functions associated with the same link function as Fenchel-Young losses?
In this paper, we introduce Fitzpatrick losses, a new family of separately convex
loss functions based on the Fitzpatrick function. A well-known theoretical tool in
maximal monotone operator theory, the Fitzpatrick function naturally leads to a
refined Fenchel-Young inequality, making Fitzpatrick losses tighter than Fenchel-
Young losses, while maintaining the same link function for prediction. As an
example, we introduce the Fitzpatrick logistic loss and the Fitzpatrick sparsemax
loss, counterparts of the logistic and the sparsemax losses. This yields two new
tighter losses associated with the soft argmax and the sparse argmax, two of the
most ubiquitous output layers used in machine learning. We study in details the
properties of Fitzpatrick losses and, in particular, we show that they can be seen as
Fenchel-Young losses using a modified, target-dependent generating function. We
demonstrate the effectiveness of Fitzpatrick losses for label proportion estimation.

Learning with Fitzpatrick Losses
Seta Rakotomandimby
Jean-Philippe Chancelier Ecole des Ponts
Ecole des Ponts
seta. rrttarrkootommndnnyyyee......
Dean-philipee
Michel De Lara
Mathieu Blondel
Ecole des Ponts
Google DeepMind mbl mblondel@google com
mi chil. dew.aa@enpe......
Abstract
Fenchel- Young losses family of loss functions, encompassing the squared, logistic and sparsemax losses, among others. They are convex w.r.t. the model output and the target, separately. Each Tenchel-Yound loss is implicitly associated with a link function, that maps model outputs to predictions. For instance, the logistic loss is associated with the soft argmax link function. Can build new loss functions associated with the same link function as Fenchel- Young losses? In this paper, we introduce Fitzpatrick losses, a new family of separately convex loss functions based on the Fitzpatrick function. A well-known theoretical tool in maximal monotone operator theory, the Fitzpatrick function naturally leads a refined Fenchel- Young inequality. making Fitzpatrick losses tighter than Fenchel- Young losses, while maintaining the same link function for prediction. As an example, we introduce the Fitzpatrick logistic loss and the Fitzpatrick sparsemax loss, counterparts of the logistic and the sparsemax losses. This yields two new tighter losses associated with the soft argmax and the sparse argmax, two of the most ubiquitous output layers used in machine learning. We study in details the properties of Fitzpatrick losses and, in particular, we show that they can be seen Fenchel- Young losses using a modified, target-dependent generating function. We demonstrate the effectiveness of Fitzpatrick losses for label proportion estimation.
Introduction
Loss functions are a cornerstone of statistics and machine learning: they measure the difference, or "loss," between a ground-truth target and model prediction. As such, they have attracted a wealth of research. Proper losses (a.k.a. proper scoring rules) [17, 16) measure the discrepancy between a target distribution and a probability forecast. They are essentially primal-primal Bregman divergences, with both the target and the prediction belonging to the same primal space. They are typically explicitly composed with link function [26. 30], in order to map the model output prediction. A disadvantage of this explicit composition is that it often makes the resulting composite loss function non-convex. A related family of loss functions are Fenchel- Fenchel-Young losses [7, 8], which encompass many commonly-used loss functions machine learning including the squared, logistic, sparsemax and perceptron losses. Fenchel- Young losses can be seen as primal-dual Bregman divergences [1], Fenchel-Young with the target belonging to the primal space and the model output belonging to the dual space. In contrast proper losses, each Tenchel-Young mapping the dual-space model output to a primal-space prediction (for instance, the soft argmax is the link function associated with the logistic loss). This erucial difference makes Fenchel- Young losses always convex w.r.t. the model output and w.r.t. the target, separately. Can we build new (separately) convex losses associated with the same link function as Fenchel-Yee -oung losses?
Young loss implicitly associated with given link function,
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

Logistic loss
30
Sparsemax loss
Fitzpatrick logistic loss
Fitzpatrick sparsemax loss
25-
2.0
15-
05-
05-
00
Figure We introduce Fitzpatrick losses, a new family of loss functions Lyy 0) generated by convex regularization function S2, that are lower-bounds of the Fenchel- Young losses generated by the same function Q, while maintaining the same link function in VΩ" In particular, we use our framework instantiate the counterparts of the logistic and sparsemax losses, two instances of Fenchel-Yourd losses, associated with the soft argmax and the sparse argmax. In figures above, plot Lyy, 8), where y e1. 0 = (s, 0) and L E [Lojon) Logn-) ), confirming the lower-bound property.
In this paper, we introduce Fitzpatrick losses, a new family of primal-dual (separately) convex loss functions. Our proposal builds upon the Fitzpatrick function, well-known theoretical object in maximal monotone operator theory [15, 11, 2]. So far, the Fitzpatrick function had been used as theoretical tool represent maximal monotone operators [28] and construct Bregman-like grimal-primat divergences [10], but it had not been used to construct primal-dual loss functions for machine learning. as we do. Crucially, the Fitzpatrick function naturally leads refined Fenchel- Young inequality, making Fitzpatrick losses tighter than Fenchel- Fenchel-Young losses. Yet, their predictions are produced using the same link function, suggesting that can use Fitzpatrick losses as a tighter replacement for the corresponding Fenchel- Young losses (Figure 1). We make the following contributions.
After reviewing some background, we introduce Fitzpatrick losses. They can be thought as tighter version of Fenchel- Fenchel-Young losses, that the same link function.
We instantiate two new loss functions in this family: the Fitzpatrick logistic loss and the Fitzpatrick sparsemax loss. They the counterparts of the logistic and sparsemax losses, two instances of Fenchel- Young losses. We therefore obtain two new tighter losses for the soft argmax and the sparse argmax, two of the most popular output layers machine learning.
We study in detail the properties of Fitzpatrick losses. We show that Fitzpatrick losses are equivalent Fenchel-Young losses with modified, target-dependent generating function.
We demonstrate the effectiveness of Fitzpatrick losses for probabilistic classification on 11 datasets.
2 Background
2.1 Convex analysis
We denote the non-negative real numbers by R4 [0, +0o), the positive real numbers by R,+ (0, +o0), and the extended real numbers by R natural number k. We denote the probability simplex by A = {p E IR. Σ P: = 1]. We denote the indicator function of a set C R by <c(y) = 0 if E C, +oo otherwise. We denote the effective domain of a function Ω: T + k by dom = {y E R 22v) < +00}. A function
(-x,, +oo}. We suppose given nonzero
Ω: R + RR is said to be proper if it never takes the value ~c and if dom Ω * 0. We denote the Fuclidean projection onto nonempty closed convex set C c & by Pe()), the unique solution y' E C of the minimization problem miny'ec |/y/ 0113.

---

For function Ωi R2 + R. its subdifferential an c R R is defined by (v' E an = O' E aQ(y') = p(y) 2 Mly') + 0',0',, vy R
When Ω is convex and differentiable, the subdifferential is singleton and we have a0(yy)
(VD())). The normal cone to nonempty closed convex set C. C R at is defined by
0' E Ne(y') + (y- < O, Vy ECC C if y and Nc(1)) 0 yf C. The Fenchel conjugate 52" R is defined by
R of function Ω R R
1 sup (w' 0) Oty) y E'
From standard results in convex analysis [27, Proposition 1 11.3), when Ω R + R is proper convex I.s.c. (lower semicontinuous) function.
a2" (0) argmax(y' .) M(y') y'ER"
When the argmax is unique, it is equal to (0). We define the generalized Bregman diver- gence [18] Da by
It x R + R+ generated by proper convex l.s.c. function Q
R R.
Daly, v/) = 2(y) 12('))()))))))()))))
sup wy v'''''0''
(I)
('Ea((y))
with the convention +00 + (-00)- = +oo (we comment on this convention in Appendix C). When Ω is differentiable, Equation (1) gives the classical Bregman divergence
Dn 3/) = 2(v) R(v') (u y-- Vl(3)))
Both and y belong to the primal space.
2.2 Fenchel- Fenchel-Young losses
Definition and properties
The Sanchel-Young loss [8] Loen-
R R + R generated by proper convex l.s.c. function Ω
Loen- (v.0) 0) = (2 @ Q (v. 0) - (y. 0) = f1y) + (0) (y. 0).
As its name indicates, is grounded in the Fenchel Young inequality
(y. S fly) (#) Vy, E R
The Penchel-Young loss enjoys many desirable properties, notably it is non-negative and it is separately convex in y and 0. The Fenchel- Young loss can be seen as a primal-dual Bregman divergence [1, 8), where y belongs to the primal space and 0 belongs to the dual space.
Link functions
To map an element 0 of a dual space to an element y of a primal space, we define the link function (potentially set-valued) associated with the loss I. by
0 - {y E &R* T(y, 0) 0}.
Given proper convex function Ω the associated Fenchel- Tenchel-Young loss Looor produces the canonical link function 0N", since
Logn- (y, 0) =
= - y E (0)
In particular when Ω is strictly convex, and thus !2" is differentiable according to [27, Theorem 11.13], the Young loss satisfies the identity of indiscernibles
Ln (y. 0)
VΩ" (8).
In the remainder of this paper, will use the notation (0) for the canonical link function (0). When the function Ω2 is diffcrentiable, (+) will denote V!² (9). Since Q is convex, io is monotone (see $2.3). As shown in [8], the monotonicity implies that 0 and (c) sorted the same way, i.c., 0g > 0, = (0),), 2 (0) Link functions also play an important role in the loss subgradients (and in the loss gradient when it is differentiable). as we have
Og (y, 0) ta (0) y.
(2)
3

---

Examples of Fenchel-Young loss instances and their associated link function
We give few examples of Fenchel- Young losses. With the squared 2-norm, 92(y)) 221lo'11 112. we obtain the squared loss
Laeer (v.0) = Laquared (v, 0) = 2 012
and the identity link
(0) = 6.
With the indicator of a nonempty closed convex set C, (1(''))()))) = (c(3)) ) we obtain the perceptron loss
Loan- (y: 0) = /pprrcpproon (y: 0) = max (w', 0) (y.0)
y'EC
and the argmax link
(f) argmax (y. 0).
yЕC
With the squared 2-norm restricted to some nonempty closed convex set C, R(v') +110 (c(()) we obtain the sparseMAP loss [24]
1
Lnen (y, EsparseMAr (y, 2 l1
012 1 -11
PP
and the link the Euclidean projection onto C.
Un (0) Pc(0).
When the is C A we obtain the sparsemax loss [21] and the sparse argmax link (0) Pat (6) (also known as sparsemax), which is known to produce sparse probability distributions.
With the Shannon negentropy restricted to the probability simplex, Styy') (g/, "lggo'g') + c (y))
we obtain the logistic loss
Lags- (v, 0) = Liogistio 0) = log exp(8:) + (v. log - (v. 0).
and the soft argmax link (also known as softmax)
(n) (0) softargmax(() cxp(O)) Σ exp(O.).
2.3 Maximal monotone operators and the Fitzpatrick function
An operator A, that is, subset A C R x IR is called monotone if for all (y, 0) A and all (v/ 8') E A, we have
(v' y, 0' 0.
We overload the notation to denote A(y) (0 R (y.0) E A}. monotone operator A is said to be maximal if there does not exist (y, 0) & A such that AU {(y, 0)} is still monotone. is well-known that the subdifferential 02 of a proper convex ls..c function Ω is maximal monotone. For more details on monotone operators, see [3, 28].
well-known object in monotone operator theory, the Fitzpatrick function associated with maximal monotone operator A [15, 11, 2), denoted F F[A] R R + R. is defined by
F[A] (y. 0) sup (v'
(y -u-vv. v'.0') + (v/ 0).
In particular, with A = a2, we have
F(a sup (g' 8')n
(u ,',0' + (M'00)
sup e'mmm a
(v.0) + sup
(v '',00) ercan()))

---

The Fitzpatrick function was studied in depth in [2]. In particular, it is (jointly convex and satisfies
(v. 0) & (y, 0) = (2 @ 22*) (y, 0) = 2(v) + (0) Vy. E R
(3)
We introduce the operator Varan C (R+ R x IR", associated to the Fitzpatrick function F[ōn]:
VF [a0a] (v, 0)
argmax E'Eomm St
(w'0) sup (y ww-v',00 v',03
(4)
('
As proven for Item 4 in Proposition 1, we have Vira (v. 8) C OgF( 6). For the rest of the paper, in case that the argmax in (4) is singleton {v"), we will write Virooy (v.0) 0) = y²- The Fitzpatrick function (y, 8) and (v. 8) = [2() + (0) play a similar role but the latter function is separable in y and 6, while the former is not. In particular this makes the subdifferential 0, Flao (v. 0) depend on both and 0, while O5 <D 22 (v. 0) = as" (0) depends only on 0.
The Fitzpatrick function was used in [10] to theoretically study primal-primal Bregman- diver- gences. As discussed in more detail in Section 3.4, using these divergences for machine learning would require to compose them with an explicit link function, which would typically break convexity, the next section, we introduce new primal-dual losses based on the Fitzpatrick function.
Fitzpatrick losses
3.1 Definition and properties
Inspired by the inequality in (3), which we can view as refined Cenchel-Young inequality, we introduce Fitzpatrick losses, new family of loss functions generated by convex l.s.c. function Ω.
Definition 1 Fitzpatrick loss
Let Q R&* - TR. be a proper convex Ls.c. function. When y E dom Ω and O E TR. we define the Fitzpatrick loss [F(00]] T2.k Rot -> generated by ft as
[V) 0) = Flas (y. 0) - (y. 8)
sup (y) V 8") + (3/ (u. 8)
(v/ 88
sup ( y, 0¹) (vi6))00
When & dom P. Lapa (v. 0) +o0.
Fitzpatrick losses enjoy similar properties as Fenchel- Young losses, while being tighter than Fenchel- Young losses.
Proposition Properties of Fitzpatrick losses
1. Non-negativity: for all (y. 0) E R x R L La (v, 2 0.
2. Same link function: Lagar (y, 0) LF (v. = y (0))
Separable convexity: LF (y. 8) is separately convex.
(Sub-)Gradient: 0g Ta (y, 0) C Vrion (v, 0) where ui (mg) (v, 0) is given by (4).
5. Tighter inequality: for all (y, 0) E R L Lajay (v. 0) S Lo (v.
proof is given in Appendix B.2. Because the Fitzpatrick loss and the Fenchel- Fenchel-Young loss generated by the same Ω have the same link function yn. they share the same minimizers w.r.t. 0 for y fixed. However, the Fitzpatrick loss is always a lower bound of the corresponding Fenchel-Yonne Moreover, they have different gradients w.r.t. 6: dgLoen (y, 9) Dn(()) y dg Da (y. 0) O Vijoo (v. 0) y. It is worth noticing that vi V (v. 0) depends on both y and 0, contrary to in (0).
loss.
5

---

When S2 is twice differentiable function on its domain (which is for instance the case of the squared 2-norm or the negentropy). we next show that Fitzpatrick losses enjoy particularly simple expression and become squared Mahalanobis-like distance.
Proposition 2 Expressions of (y, 0) and Lejon (y, 0) when Q twice difserentiable
Let St I + R be convex function such that dom St is an open set. Let us assume that Q is twice differentiable. Then, for any E dom Q and for any y" E Vyjony (v, 0), as defined in (4), we have that
Fl0n] (v. 0) = (y. v(((y)) + (0"00) (v,, v2(("))
I. F. (v. (y" y, (l(('))
(y' - y, v2 (2² 3))
and
v²n("")("* - - VD(x))
A proof is given in B.3. When Ω is constrained (i.e., when it contains an indicator function), we show $3.5 that the above expression becomes a lower bound.
3.2 Examples
We now present the Fitzpatrick loss counterparts of various Fenchel- Young losses. Squared loss.
Proposition 3 Squared loss as a Fitzpatrick loss
When 2(y/) = I1s'1lg, we have for all y E IR. and R
Lyjon (y. 0) 1 01 Lequared (y) 0).
A proof is given in Appendix B.4. Therefore, the Fenchel- Young and Fitzpatrick losses generated by Ω coincide, but up to a factor 1 2-
Perceptron loss.
Proposition 4 Perceptron loss Fitzpatrick loss
When 21y)) = ic(y)) where C is a nonempty closed convex set, we have for all y E C and g
Lipan (y, 0) pperceptron (y, 0) max y EC (v/, 0) (v,
A proof is given in Appendix B.5. Therefore, the Fenchel-Young and Fitzpatrick losses generated by exactly coincide this case.
Fitzpatrick sparseMAP and Fitzpatrick sparsemax losses. As our first example where Fenchel- Young and Fitzpatrick losses substantially differ, introduce the Fitzpatrick sparseMAP loss, which is the Fitzpatrick counterpart of the sparseMAP loss [24].
Proposition 5 Fitzpatrick sparseMAP loss
When M(y') lv'1l tcl''), where C is nonempty closed convex set, we have for all E C
and 0 E IR=
Lyan (v. 0) 20" (1++0)/2) (v.0) (2- yy 0 )²)
where we used y" as a shorthand for
Viioo (y. 0) =
= Pc((y ( + 00/2).

---

A proof is given in Appendix B.6. As special case, when C = A we call the obtained loss the Fitzpatrick sparsemax loss, is the counterpart the sparsemax loss [21]. Like the sparseMAP and sparsemax losses, these new losses rely on the Euclidean projection as core building block. The Fuclidean projection onto the probability simplex A can be computed exactly in ( expected time and O log k)) worst-case time (9, 22, 14, 12].
Fitzpatrick logistic loss. We now derive the Fitzpatrick counterpart of the logistic loss. Before stating the next proposition, we recall the definition of the Lambert function [13] W IR., - R+. The function W is the inverse the function f I - R. where [(w) wexp(w) for all
I.
Proposition 6 Fitzpatrick logistic loss
When f(y') ,log v/) + (==(1')) have for all y A and 0 E R
Fa (v. 0) = (v" y, log - 1) where used y" as shorthand for yr (y. 0) defined by
Vajan (v, 0): {
e if yi 0, W Wyne" 44) if
vi
> 0.
A proof and the value of X- = (v, 0) R are given in Appendix B.7. To obtain (y, 0), we need to solve a one-dimensional root equation, which can be done using, for instance, a bisection.
3.3 Relation with Fenchel-Young losses
On first sight, Fitzpatrick losses and Fenchel- Penchel-Young losses appear quite different. In the next proposition, we show that the Fitzpatrick loss generated by 12 is in fact equal to the Fenchel-Yone Young loss generated by the modified, degeeddee function
(1)( = 2(y') + Pnly.y'),
where Dq is the generalized Bregman divergence defined in (1). In particular, Lemma in the appendix shows that if Ω V + lc, where C is nonempty closed convex set, then (,y V (w') + (v'), where (y(w') = (sy)) + ('),,y)).
Proposition 7 Characterization of F[On], Lyjan and daacy using Sly
Let Q R* + E be a proper convex l.s.c. function. Then, for all y dom Q and all 0 R*
Flan]yy, 0) (v) (7)
Lraa () La,en; (v. 0)
Viron (u, 0) Ve, (0).
This characterization of the Fitzpatrick function F[00 is also new to knowledge. A proof is given in Appendix B.8. Proposition 7 is very useful, as it means that Fitzpatrick losses inherit from all the known properties of Fenchel- Fenchel-Young losses, analyzed in prior works [8, 6]. In particular, Fenchel- strongly convex. We therefore
Young losses are smooth (i.e., with Lipschitz gradients) when immediately obtain that Fitzpatrick losses smooth in their second argument Ø if Ω is strongly convex and Da is convex in its second argument, which is the case when M(y') Z |/ I| and 0(y')= = (v/, logg"). Therefore, the Fitzpatrick sparsemax and logistic losses are smooth. However in the general case, this does not hold, as Dg is usually not convex in its second argument. Proposition 7 also provides a mean to compute Fitzpatrick losses and their gradient. Finally, it suggests a very natural geometric interpretation of Fitzpatrick losses, as presented in Figure 2.
3.4 Relation with generalized Bregman divergences
As we stated before, the generalized Bregman divergence Da(y, y²) in (1) primal-primal di- vergence, both y and y' belong to the same primal space. In contrast. Senchel-Youny losses
7

---

Lejony(v. 0)
Ln (v.
Laoar (v. 0)
(1()) (v)
(v. 0) (0)
(y. (0)
-0
(0)
Figure 2: Geometric interpretation, with 22y/))
11.//1 The Fenchel- Young loss Loga (y. is
the gap (depicted with a headee arrow) between (2y) and (y. 0) - 52" (0), the value at the tangent with slope 9 and intercept -S2" As per Proposition 7, the Fitzpatrick loss L F|an| (y. 0) is
equal to La (y, 0) and is therefore equal to the gap between (v) = (2()) and (v. 0) (0). the value at of the tangent with slope 0 and intercept - (0). Since Sy (v') M(y') + Dnlu, v'), y'. We therefore have (7) s (0),
we have that S2 (v/) 2 M(y'), with equality when implying that the Fitzpatrick loss is lower bound of the Fenchel- Fenchel-Young loss.
Laen- (y, 0) are primal-dual, since y belongs to the primal space and belongs to the dual space. Both can however be related for any proper l.s.c. convex function Ω since, for any y such that 052(y') * 0, we have
inf #E80(v))
Loan (v. )') = inf (2y) + 12" (0) (u, 8') ('E0R(r))
Ω2 (6)) - (v,8") (2()) + inf
(2()) e'ean(v')
Q2' (8") + (v.
22w)) - 12ll))
sup ('aA(())
(y - v'.0')
Da(y. v/)
where, in the penultimate line, we have used that 52" (8') (y/, 00 22//), as 2g(g') This equality remains true when 02(2)) = 0, by convention inf 0 = +oo and by definition of Dy (y. y') in (1). This identity suggests that we can create Bregman- primal-primal divergences by replacing Ω e Ω with F(as]).
inf Lryan (v, ('Ean(y))
Fl (v, e'e8n(y))
inf
This recovers one of the two Bregman-like divergences proposed in [10], the other one replacing the inf above by sup. As stated in [10], F[A?] and Ω @ O are representations of an.
In order to function, such as (0) = VΩ2" (0). Unfortunately, Dy (y. (f)) or DD Dijaa (v. Do (o) are typically non convex functions of 6, while Fenchel-Yourg and Fitzpatrick losses always convex in A. In addition, differentiating through (f) typically requires implicit differentiation [19, 5], while Tenchel-Young and Fitzpatrick losses enjoy easy-to-compute gradients, thanks to Danskin's 's theorem.
primal-primal divergence loss, need to explicitly compose it with link
3.5 Lower bound on Fitzpatrick losses
If Q = + (cs where R -> Th. is proper convex Legendre-type function and C C dom v is nonempty closed convex then it shown in [8, Proposition 3] that Fenchel- Fenchel-Young losses

---

satisfy the lower bound
Du (v)( S Lnga-(y-
with equality if C dom V. We now show that similar result holds for Fitzpatrick losses. Similarly as before, we define Vr vv(v = wey)
D& (g.v).
Proposition 8 Lower bound Fitzpatrick losses
Let f2 V + tc, where V RR& _> Th a proper convex Legendre-type function, as defined in {8, Definition 3), and C S dom V is nonempty closed convex set. We remind that (1/) = 22(y') + Daly. 11). Let us assume that Sy is differentiable. Then,
Dæ, (.. y²) (y- ('ne 1lly-yy) y²) s L Lrjon 0),
with equality dom V C. where we used y² as a shorthand for (0)
proof is given in Appendix B.9, If Vy is p-strongly convex, we obtain Elly v012 S Dv, (v,
4 Experiments
Experimental setup. We follow exactly the same experimental setup as in [7, 8]. We consider a dataset of n pairs (Ii,3t) Ur) of feature vectors x; E TRd and label proportions yi E A where is the number of features and k is the number of classes. At inference time, given unknown input vector & E Rd, our goal is to estimate a vector of label proportions ÿ A A model is specified by a matrix W E Rxd and convex Ls.cc function Ω R + E. Predictions are then produced by the generalized linear model + Va (ow)) v). At training time, estimate the matrix W I by minimizing the convex objective
À
RLA(WW) = Σ L(n,
I 12. 2
(5)
where L E { Luwar Luja }. We focus on the (Fitzpatrick) sparsemax and the (Fitzpatrick) logistic losses. We optimize (5) using the L-BFGS algorithm [20]. The gradient of the Fenchel- given in (2), while the gradient of the Fitzpatrick loss is given in Proposition 1, Item 4. Experiments were conducted on a Intel Xeon E5-2667 clocked at 3.30GHz with 192 GB of RAM running on Linux. Our implementation relies on the SciPy [29] and scikit-learn [25] libraries.
loss
We ran experiments on 11 standard multi-label benchmark datasets (see Table in Appendix for statistics on the datasets). For all datasets, we removed samples with no label, normalized samples to have zero mean unit variance, and normalized labels to lie the probability simplex. In (5), we chose the hyperparameter À E {10-4, 10 mean squared error (also known as Brier score in a probabilistic forecasting context) in Table
104) against the validation set. We report test set
We found that the logistic loss and the Fitzpatrick logistic loss are comparable on most datasets, with the logistic loss significantly winning on 2 datasets and the Fitzpatrick logistic loss significantly winning on 2 datasets, out of 11. Since the Fitzpatrick logistic loss is slightly more computationally demanding, requiring to solve a root equation while the logistic loss does not, we believe that the logistic loss remains the best choice when we wish to use the softargmax as link function In-
Results.
Similarly, we found that the sparsemax loss and the Fitzpatrick sparsemax loss are comparable on most datasets, with the sparsemax loss significantly winning only dataset out of 11 and the Fitzpatrick loss significantly winning on 2 datasets out of 11. Since the two losses both use the Euclidean projection onto the simplex Pa as their link function Do, we conclude that the Fitzpatrick sparsemax loss is a serious contender to the sparsemax loss, especially when predicting sparse label proportions is important.
'The datasets can be downloaded from https://wwwe htops://www... csie ntu, edu. http://jjhn/lllttooo/aaaaaaaaaaa
nlml and

---

Dataset
Sparsemax
Filzpatrick-sparsemax
Logistic
Fitzpatrick-logistic
Birds
0.531
0.513
0.519
0.322
Cal500
0.035
0.035
0.034
0.034
Delicious
0.051
0.052
0.056
0.055
Ecthr A
0,514
0.514
0.431
0.423
Emotions
0.317
0.318
0.327
0.320
Flags
0,186
0.188
0.184
0.187
Mediamill
0.191
0.203
0.207
0,220
Scene
0.363
0.355
0.344
0.368
Tme 0.151
0.152
0.161
0.160
Unfair 0.149
0.148
0.157
0.158
Yeast 0.186
0.187
0.183
0.185
Table I: Test performance comparison between the sparsemax loss, the logistic loss and their Fitzpatrick counterparts on the task of label proportion estimation, with regularization parameter in (5) tuned against the validation set. For each dataset, label proportion errors are measured using the mean squared error (MSE). We use bold if the error least 0.005 lower than its counterpart.
5 Conclusion
We proposed leverage the Fitzpatrick function, theoretical tool from monotone operator theory, to build new family of primal-dual separately convex loss functions for machine learning. We reinterpreted Fitzpatrick losses as lower bounds of Fenchel- Fenchel-Young losses that maintains the same link function. Our paper therefore challenges the idea that there can only be one loss function, convex in each argument, associated with a certain link function. For instance, we created the Fitzpatrick logistic and spansemax losses, that are associated with the soft argmax and sparse argmax links, traditionally associated with the logistic and sparsemax losses, respectively. We believe that even more loss functions with the same link can be created, which calls for systematic study of their properties and respective benefits. to test new link functions from maximal monotone operator theory and to implement more efficient training for the Fitzpatrick logistic loss.
future work, we intend to study calibration guarantees for Fitzpatrick losses,
References
[1] S.-i. Amari. Information geometry and its applications, volume 194. Springer, 2016.
[2] H. Bauschke, D. McLaren, and H. Sendov. Fitzpatrick functions: Inequalities, examples, and remarks on a problem by S. Fitzpatrick. Journal of Convex Analysis, 13, 07 2005.
[3] H. H. Bauschke and P. L. Combettes. Convex analysis and monotone operator theory in Hilbert spaces. CMS Books in Mathematics/Ouurrgee de Mathématiques de la SMC. Springer-Verlag, New York, second edition, 2017.
[4] D. P. Bertsekas. Nonlinear programming. Journal of the Operational Research Society, 48(3):334-333 334, 1997.
[5] M. Blondel, Q. Berthet, M. Cuturi, R. Frostig, S. Hoyer, F. Llinares-Lopez, F. Pedregosa, and J.-P. Vert. Efficient and modular implicit differentiation. In S. Koyejo, S. Mohamed, A. Agarwal, D. Belgrave, K. Cho, and A. Oh, editors, Advances in Neural Information Processing Systems, volume 35, pages 5230-5242. Curran Associates, Inc., 2022.
[6] M. Blondel, F. Llinares-López, R. Dadashi, L. Hussenot, and M. Geist. Learning energy networks with generalized Fenchel- Young losses. Advances in Neural Information Processing Systems, 35:12516-1221 12528, 2022.
[7] M. Blondel, A. Martins, and V. Niculae. Learning classifiers with Fenchel- Fenchel-Young losses: Generalized entropies, margins, and algorithms. In The 22nd International Conference Artificial Intelligence and Statistics, pages 606-615. PMLR, 2019.
[8] M. Blondel, F. Martins, and V. Niculae. Learning with Fenchel- Youell-Yongg losses. Journal of Machine Learning Research, 21(35): 2020.
10

---

[9] P. Brucker. An (nn) algorithm for quadratic knapsack problems. Operations Research Letters, 3()):163-16, 1984.
[10] R. S. Burachik and J. E. Martinez-Legaz. On Bregman-type distances for convex functions and maximally monotone operators. Set-Valued and Variational Analysis, 26:369-384, 2018.
[11] R. S. Burachik and B. F. Svaiter. Maximal monotone operators, convex functions and a special family of enlargements. Sel-Valued Analysis, 10:297-316, 2002.
[12] L. Condat. Fast projection onto the simplex and the & ball. Mathematical Programming. 158(1-2)5555-58, 2016.
[13] R. M. Corless, G. H. Gonnet, D. E. G. Hare, J. Jeffrey, and D. E. Knuth. On the Lambert W function. Advances in Computational Mathematics, 5(1):329-359, Dec 1996.
[14] J. C. Duchi, S. Shalev-Shwartz, Y. Singer, and T. Chandra. Efficient projections onto the 1aall for learning in high dimensions. In Proc. of ICML., 2008.
[15] S. Fitzpatrick. Representing monotone operators by convex functions. In Work- shop/Mimiconference on Functional Analysis and Optimization, volume 20, pages 59-66. Australian National University, Mathematical Sciences Institute, 1988.
[16] Gneiting and E. Raftery. Strictly proper scoring rules, prediction, and estimation. Journal of the American statistical Association, 102(477):359 2007.
[17] D. Grünwald and A. Dawid. Game theory, maximum entropy, minimum discrepancy and robust Bayesian decision theory. The Annals of Statisties, 32(4): 2004.
[18] K. C. Kiwiel. Proximal minimization methods with generalized Bregman functions. SIAM journal on control and optimization, 35(4): 10 142-1168, 1997.
[19] S. G. Krantz and H. R. Parks. The implicit function theorem: history, theory, and applications. Springer Science Business Media, 2002.
[20] D. C. Liu and J. Nocedal. On the limited memory BFGS method for large scale optimization. Mathematical programming, 45(1):503-528, 1989.
[21] A. Martins and R. Astudillo. From softmax to sparsemax: A sparse model of attention and multi-label classification. In International conference on machine learning, pages 1614-1623. PMLR, 2016.
[22] C. Michelot. A finite algorithm for finding the projection of a point onto the canonical simplex of g". Journal of Optimization Theory and Applications, 50(1):195-200, 1986.
[23] J. J. Moreau. Inf-convolution, sous-additivité, convexité des fonctions numériques. J. Math. Pures Appl. (9), 49: 109-154, 1970.
[24] V. Niculae, A. Martins, M. Blondel, and C. Cardie. Sparsemap: Differentiable sparse structured inference. In International Conference on Machine Learning, pages 3799-3808. PMLR, 2018
[25] Pedregosa, G. Varoquaux, A. Gramfort, V. Michel, B. Thirion, O. Grisel, M. Blondel, P. Prettenhofer, R. Weiss, V. Dubourg, et al. Seikit-learn: Machine learning in Python. the Journal of machine Learning research, 12:2825-2830, 2011.
[26) M. D. Reid and R. C. Williamson. Composite binary losses. The Journal of Machine Learning Research, 11 11:23772422,, 2010.
[27] R. T. Rockafellar and R. J.-B. Wets. Variational Analysis. sv, Berlin, 1998.
[28] E. K. Ryu and W. Yin. Large-scale convex optimization: algorithms & analyses via monotone operators. Cambridge University Press, 2022.
[29] P. Virtanen, R. Gommers, T. E. Oliphant, M. Haberland, T. Reddy, D. Cournapeau, E. Burovski, Peterson, W. Weckesser, Bright, et al. Scipy 1.0: fundamental algorithms for scientific computing in Python. Nature methods, (7(3):261-223 2020.
[30] R. Williamson, F. Vernet, and D. Reid. Composite multiclass losses. Journal of Machine Learning Research, 17(222):1552, 2016.

---

A Datasets statistics
Dataset
Type
Train
Dev
Test
Features
Classes
Avg.labels
Birds
Audio
134
45
172
260
19
2
Cal500
Music
376
126
101
68
174
26
Delicious
Text
9682
3228
3181
500
983
19
Ecthr A
Text
6683
228
847
92401
10
Emotions
Music
293
98
202
72
6
2
Flags
Images
96
33
65
19
Mediamill
Video
22353
7451
12373
120
101
5
Scene
Images
908
303
1196
294
Tmc
Text
16139
5380
7077
48099
896
6
Unfair
Text
645
215
172
6290
Yeast
Micro-array
1125
375
917
103
14
4
Table 2: Datasets statistics
B Proofs
B.1 Lemmas
Lemma 1 Generalized Bregman divergence for constrained Q
Let Q V tc, where R&d Th. proper convex l.s.c. and S dom nonempty closed convex set such that riC O dom v + D, where riC is the relative interior of Then, for all y.y y R
Dalu,v') (v, + (ucly'))
Proof.
As C. dom v C R and riC O ri dom Vi + 0, we can apply [3, Proposition 6.19] and [3, Theorem 16.47] write a0(y') (V/) + dic(s').
Thus, we have
Da(u, = (yy) - M2%
sup ('EA((s))
(y y 3/ '0)
(v)) + <c()) V(y') - 1c(1')
@' (y v/,0')
sup
(v) (1v) sup ('EaV(y))
(y V 0²) + (c()) (c(1/)
sup (2) - 1 07 v'ancty))
(v. s/) + Dio (y.
Lemma 2 Generalized Bregman divergence of function of some nonempty closed convex set set C C R
(1(()) ify' EC ic(v) cc()).
(y.v''
00 ify EC
Proof. Using (1) and the fact that die- = Ne [3, Example 16.13], we obtain that
(v.( = (e()) rc((")
sup (y - y 8'). N'NNe('")
When y' E C and y E C.
(y - -'''00 MeNo((')
sup
sup
(y- - v.,6') = 0.
0'
,0' 20'5000 <0
WEEC
When s/ E C and y & C, Dao (y) +00, +00 (-00) +00 the definition of the Bregman
divergence. Therefore, when 3 E C, we get that Drc (v. y/) ic(y).
12

---

When of & C. Ne(vv) = 0. Again, in the definition of the Bregman divergence, too + (-00) too and we use the convention sup, -00
Lemma 3 Bregman divergence of y
Let V TR + R. be proper, convex and twice differentiable on the interior of its domain. For all y RR let Vy v/- Dv -). Then, for all y, 3' 3f" E int dom V,,
De, (vd", .// = Dv (y. v²) Dv 1/) D (y" 3/) (2d" v/. 42 (g')(y s/)) = ww" y, VV (v")) (5' v. VV(O')) + -w, V2 - v/))
and, in particular, for all y, int dom
-y (1
Proof. For all y, y E int dom Mr as y is convex and differentiable on int dom v we have that
Vy(w') = (1/) Do (v.v'))
(V/')) (v() ((1') - - (w)'""))
(v) - (y - VV))))
and therefore, Ve is twice differentiable int dom V we get that
v4a(1/) v 4) Vy/))
Therefore, for all y. V.8"" E dom V
De, (v,(v" = (v")) - V v,(1') - (0" - v
~v('") (v, - V((')) Do (w" - VVV/V('' - 1))
-W"-v'
-V. vVV((()))
Dv v") - D-(y,v))++ DD 3²) W/" - VV v/)) (w" v, (V()")) (y" - y, Vvyy')) ww" - V', V' (2 y/))
and in particular using the just last established equality with the triplet (y/, y, y²), we have for all y, v/ E dom V
Dv, (v. 1)) (y y. VV())) (v- v. vV(()) (w(2 v')) (y v. v'v(''(v v'))
Lemma 4 Generalized Bregman divergence of negentropy
Let a E R. Let (3y) Σt log vl
Ei v be defined for 3 E Rt. Then, for
y. E R
h
D'(. Σ
yi log
y1 y/
Σ 1=1
(ys v/t) + LRt. (v/),
which does not depend on Oz.
Proof. First, if y' R8t,, is differentiable at s/ and (v(()') log yi + 1 a. Thus, 04
(V and
Dv(v.v)- ((v) - v(4))
sup
( v.00 0'),
('EaV(y)
= (v)) - ((4')
(y v.' V
k
Σ y/s log
yA
Σ (y: v.).
1m1
im1
13

---

Second, if we prove that 0v (v') = & when there exists component such that y/ = 0, we can conclude the proof, as supy -o by convention. Indeed, Let assume that y Suppose that 0' E (v)). Then, by definition of subgradients.
w',-v',0) + v(y) & ((V"), Vy" R
We consider = > 0 and choose y" y' + EEG, where e, is the i-th canonical base vector. Thus, obtain
50, (gy' + +eee) (z))),
k Σ v/ log + logg - a ΣV² 1/3 as (2 U/ log > v/)). j=1
k
j=1
1=1
5
logg QEE,
as yı and Olog 0 by convention. By noticing that lim-- (e (olog a contradiction, which concludes the proof.
as) / = -0, we get
Lemma 5 Subdifferential inclusion for sup function
Let Y R& be some set. Let UyyneY be a family of finite functions fy R + R. We define
the function IR by g(0) = supper f. any E IR. Then, we have
0fg(0) c 0g(0),
for all 0 E R& and for all ÿ E argmax (0).
Proof. Left an exercise.
Lemma 6 Value and gradient of Vi
Let V : R* + R be proper strictly corvex function. Let assume that Du (y(u.v') v') is conver w.r.t y for all y E dom V. We remind that V Vy(y)) = (1y) + Dy (y.3)) Then, for all A e R
and for all ÿ E argmax,'edom v (y', + (y v', (y)))
(0) = (g. 0) - (z)) + (y y. VV) V (0) y.
Furthermore, if the function T is twice differentiable, have
argmax ()' + (y D' vV((')) < {v' E dom v V/W(// v) v) = - v(()).
g' E'dom V
Proof. As V & y. have dom V y C dom V. Thus, get
V E'mmm w
sup (v', 0) Vy(e/)
sup (y', 0) (V'(')) + v()) w(y") -M- v.
E'edom
(y' 0) (vy) + (v v. (V(()))
sup y'Edom
As V is strictly convex and Dv (y. y²) is convex w.r.t. y'. we have that V is strictly convex. Thus, according to [27, Theorem 11.13), M is differentiable. Thus,
(V N
5 argmax (v' (()) + (v V. VV v Edom V
argmax (v', 0) (u V. (V())), e'edom
using Lemma for the inclusion.
In the case that & is twice differentiable, setting the gradient of the inner function to zero concludes the proof.
14

---

Lemma 7 Gradien of V squared norm case
Let (v)) LeI = --111/ 2111'l8 and Vy defined as in Lemma 6. Then, the gradient of Vy is given by
y +
Proof. Let notice that
sup (w' 0) (y V. (V())) = sup (.'0 3²) + - 111111 y'Edom V
y'Edom V
and that V is strictly convex function. By strong convexity of y/ + 1ly' deduce that argmaxy' Edom Edomm w (3/' 0) + (y - y', (V(('') * 0. Furthermore, as V/ is twice differentiable and (1') = I and dom v = R we have that {s' E dom V (1)) y) 0 - v V (y') is a singleton. Thus, we use Lemma 6 with (vy)) y' and (1"( = I, we obtain that V V (0) is the solution w.r.t y of the equation y' 0 - y'. Rearranging the terms concludes the proof.
15

---

Before stating the next lemma, we recall the definition of the Lambert function [13] W : R__ + R+.
The function W is the inverse the function f IR - R+ where f(w) exp(w) for all E IR,.
Lemma 8 Gradient of V negentropy case
Let (()) = Ei= 1 V/ log y - a Ei= V be defined for yf E R Then,
--22+a
if ys 0 if y, >
(0)(
21 W Wgge (4, -++1)
Proof. Following the same arguments in the proof of Lemma 7, we use Lemma 6. We know that is the solution of V (ū - y) = - (ÿ) Using ( = log ÿ + 1 (where logarithm and division are performed clement-wise), obtain for all i E {I..... k}
a and V ( 1/y
(is y/) 9. 8, log U,
a + y 9 8 log yJ 1+
When Vi = O, we immediately have ÿJ = cxp(0; - + a). When y; > 0, after rearranging, we obtain
exp
Vi Tx
yi expl - 2 aa))
=
W(n exp( 2 -2 a))),
hence the result.
Lemma 9 Gradient of
Let v IR F be proper strictly convex ls..c function and assume that, for all y E R the function (y, is convex. Let Qty = +
+ ie with My defined as in Lemma 6 and assume that C is nonempty compact convex set included in dom V. Then V (0) is the unique element of the set
argmax ()' w V (V)))) y'EC
Proof. The result follows from Danskin's theorem [4, Proposition B.25].
Lemma 10 Dual of simplex-come constrained conjugate
Let V R + -R be proper strictly convex finction. Then,
( (2+) min + ( + 1Rt (6 r1). -ER
and for any 7² E argmin, 7
'R" )r (0- -1), we gel
V(V + ) =
V(V 1 711)
Proof. We have by the definition of the Fenchel conjugate that (IT ((++2)""(0 = max ((y 0)
(v')). As the unit simplex A is compact set and as (VI + is differentiable (by [27, Theorem
11.13] given that V/ is strictly convex and 2 is convex we apply Danskin's theorem [4, Proposition
B.25] and get (V(V + + )* (0)) = argmax (Ky/, 0) - (yy)))
Furthermore, we rewrite (V 1 in the following dual minimization problem
(VV + +*)
max (w',0) (v))
E'E
max min(y/. 0) ((y') -(W' 1)
V'ERR
min + max (1/ r1) (3y')
TER
E'
min + ( + ) r1).
Again, Ti is strictly convex, (V + (R:) ) is differentiable [27, Theorem 11.13]. After some elementary calculus on subdifferentials, we conclude by applying primal and dual forms of Fermat's rule [27, Theorem 11.39, Item (d)]: for any 7* E argmin,,RR + (I) + lst )0 71), we have
V( + tat (0 - r"1) E argmax ((0',0 - (2/)))
16

---

Lemma 11 Gradient of by negentropy, constrained to the simplex
Let (yy) = "l''log'' logy',, y' E R2, to0 otherwise. Then, for all y E R4, the gradient of
Gy = v, + Lax (as defined in Lemma 9) is given by
if yi = 0, y: O.
W(y
2)
where X is the unique solution of the equation
1/1 W (ybee((e (0: -2))
1.
E:y 0
Proof. From Lemma 9 and Lemma 10, since dom My = RR we have
= VQ2 (0
for any solution x" of
min + ( - -1) TER
As r H ( - r1) is a convex function, Setting the gradient the inner function to zero, we get
+* E argmin + ( -1) =
(VV -" -"1), 11
TER
Using Lemma 8, we obtain that satisfies
Σ =0==0
Σ #y
1.
W (0--r'-1 2))
By monotonicity in 7*, conclude that 7* exists and is unique. Using the change of variable
X" + 2 concludes the proof.
B.2 Proof of Proposition (Properties of Fitzpatrick losses)
Apart from differentiability, the proofs follow from the study of Fitzpatrick functions found in [15, 2, 28]. We include the proofs for completeness.
Link function and non-negativity. We recall that
Lrqa (v, 0)
sup
( - 1, 0¹)
(o' e0)
inf (y/ y, 0' - 0) (o',)')0
From the monotonicity of 82, we have that if (y. 0) E an and (y', 0") E an, then (y/ 0y' 2 0.
Therefore, for all (y, a2,
inf (,)
W - v,O 0' - -) 0,
with the infimum being attained at (v',0) 0') = (y. 0). This proves the link function.
From the maximality of 02, if (v. 0) & an, there exists (v', 0') E 02 such that (y/ y. 0. 8) 0. Therefore, for all (y, 0) & 002
inf (a))))
( y, 0' 0) 0.
This proves the non-negativity.
17

---

Separable convexity.
We recall that
Lijao (v,0) F'00]](, (y. 0)
where
[ya sup (y ,' (v',0) .) sup (u', + (2. .0)
(w'00')00
(v' (w'88))nn
The function (y, 0) - (w', 0) (y 0² (y', ) is (jointly) convex in (y. 0) for (v/: 0¹) Since the supremum preserves convexity. [y 0) is (jointly) convex in (y. 0). The function (y. 0) is convex in y and 0 but not (jointly) convex in (y, 0). Therefore, Lyjan (y, 0) is separately convex in and 0.
Subgradient We going prove that, for any y, IR* and for any y² Vironn (v, 0) as defined in (4), we have y* - E 0g L (y. 0). Indeed, by Definition 1, we have that
L. F.1 (U: 0)
sup e'edom f
( 0)
sup
wリ 0'
Furthermore, (f) f vt. where fv. = (v/0) + supo (u 0', Thus, by
applying Lemma 5, we get
y y E 1.g. (y,
for any v² E argmax,y'domm st (0) argmax,, (V/ y, + supe 1/ 8' ( which yields the result by definition of y Vijona (v. 0) in (4).
Differentiability. Since the function Ω is strietly convex and y/ + Daly, v/) is convex, then (,)) = Q(y) + Dr(y, y²) is strictly convex in y'. From the duality between striet convexity and differentiability, (0) is differentiable in 0.
Tighter inequality.
Using
M (1/ 0') E IR* x Rd ((v) M27) + (y - 0',0') Vy}
and
22 (2) sup
( - 2(3'),
ER
we get for any (v 0') E an,
v. 00) W 0) s M(y) 0(v') + (/
I (1 + (0).
Therefore
[1 0)
sup (y' (1.8))aas)
(y - v' 0') + w 0) S
B.3 Proof of Proposition 2 (Expression of Fitzpatrick loss when Ω is twice differentiable)
We recall that F[0R](y, 0)
sup 0' (v' ()',0)- ( (ren Since differentiable, we have 0( (V(((')) and therefore 0' = vD()), which gives FlAM)y, 0) = sup
sup (3 0) + sup (y, 0" (v.0', of Edom a
('aa()))
(v, v(((')) )) + (s'00 W VD(V)).
y' g'edom R
Setting the gradient of the inner function w.r.t. y' to zero, we get, for any 3² Vironn (v. 0) as defined in (4),
V22(x") yy + - v2(2') - v'D("")'' = 0. Using the y' = and 0' vi(x*) Definition 1, we then obtain
Faaaao (v. 0) = (y' - y. 0¹)
= (g) - 0- vl(x*))
(y* y. (22(1)) -v))
18

---

B.4
Proof of Proposition (squared loss)
Using Proposition with vD(y)) y' and (yy( I, we obtain
y/ + 2
y + 0 2y
- y'
We therefore obtain
1 ++0
y + A
Laaa (y.0)
V, 0
2
y
0
2
2
bly 012
B.5 Proof of Proposition (perceptron loss)
proof of the Fitzpatrick function for this case was given in [2, Example 3.1J. We include a proof for completeness. Since f2 lc, we have dom ft C. Therefore, for all y E C and 0 R
Flan)(y,. 8)
sup (w' 8)
sup (y v'.6" ('aan(v")
y'Edom
sup ( 0) (c(1) -c((') sup (y ju-v/a 0' d'Eārc(o')
N'EC
sup (v/ 0) - (V.2') y'EC
sup (),
y'Ee
where in the third line used that (c(v) to()') and where in the last line used Lemma 2. Therefore, for all y E & and 0 E R
[V 0) sup (y' 0) + <c(v) (e()) +2)
y'EC
B.6 Proof of Proposition (Fitzpatrick sparseMAP loss)
A proof of the Fitzpatrick function for this case was given in [2, Example 3.13]. We provide an alternative proof.
From Proposition 7, we know that for any y E dom Q(= C here)
F[aN](y, 0) (v) + (2) = 2(y) + (0),
where
(y('') 1 1l/'112
1 - 2'112 + cc('')
VI 11 = Ellll - (. + (c()))
20(v') + D(v) (v.1).
Using conjugate calculus, obtain
y + 0
(7( = 202
2 12
Therefore,
y +
Flan](y,0) 0) 2Ω'
From Proposition 7, the supremum w.r.t. 1f is achieved at y VΩ ((v + 00/2) Pe((u + 0)/2).
We therefore obtain
Ly 0) (y* 0. y*).
19

---

B.7 Proof of Proposition 6 (Fitzpatrick logistic loss)
Differentiability w.r.t. and formula of gradient. According to Proposition 7, we have
Lejor 0) - (g)(v) + (2) (y. 0).
Thus the differentiability w.r.t. 0 of [ (v. 0) follows from the differentiabillty of 0 (0). Lemma 11 yields the differentiability of S2, (0) and formula for its gradient Virooa (v, = (0)
c-x'c o if Vi = 0, o2)
Vejon (v, (), {{
W( =2) if y/ 0. follows that VoLrran (y. 0) = VF (y. y.
Formula of the Fitzpatrick logistic loss. We use y² as shorthand for yiron (v. 0). As we know that (0) (y", 0) Pay (v²",, we use again Proposition 7 to get
I F (y. 0) = (v)()) + (v",) - 22y(v)) (v. 8)
[yy - (1((y) + Dny,. 8²)) + fy - v.
as 2 ((v)+ y/) and in particular s2, (8) Dyy). Furthermore, as 1/¹ E ^ .i differentiable at y" and (n v²) = (2(v) - -2((") (y y" vi((")), where V12("") log y" +1. Thus
L (v, 0) = (y - y¹, Vl )} + (3) - y. = (y y, 0 log y² - 1).
Bisection formula for and bounds. which is shorthand for F0o0 (v.
We also get from Lemma 11 bisection formula for X1,
Σ
Σ
V1 =
((ye-(0-xx1)
09:30
We focus here on a lower bound and an upper bound for x E R. Let us prove that
log
X log 2 + max { log Σ
"t log lol))= max 0, 220(2)81
:=
where lo(y) Card(j 8/ # 0). For the lower bound, we use the concavity [13] of the Lambert function W, which implies (()) 2 -10 Thus,
12 12
c
y: Bie---00
Eggy
Bag 20
which in turn implies
1:y=00
1:3i >0
and yields the lower bound.
For the upper bound, the function 9())= - -1 e: Σ Eiyoo W(y is continuous and
decreasing (as it is positive combination of decreasing functions) and g( -(x:)) = +oc Thus if we
find a such that (\) < 1, we know that x* 1 X.
We deal with each term of g(A) separately. If A E R satisfies
Σ
<
2
:::: 0
y/
W (y,eA-0:) 0:)
20a(y)
20

---

then
9(A)
= -1
Σ
0 +
S 1.
W Wysor 91)
=
Nigs
(20(((()))
11/
Thus, all À satisfying the following inequalities are upper bounds of X
2
Σ a S e
=:==0
2lo(y) S W Wwyee~00 9 :>:0 O.
As W is monotone and (1) = le", we get
log 2 + log Σ c. <>
=w:=D
26 ( 200(a)
S exx - Vi: y; 0.
* - e maxiy,30 log 2 + log (o(v) + +0 +2.+26(v))) yields Thus taking À = max log 2 + log an upper bound of X
B.8 Proof of Proposition (characterization of F(a?] using De)
Let (y, 0) E dom f2 R We have
sup (y 0 + ())
(y #'jeon
(1'0)+ sup (EDR(V)
(y - v/ S.
sup E2mmm
(v'0) - -2(1) + 221'') + sup
(y - 1 v0.00
sup E'Edom
MEaA(()))
() - (9(5/) + 2(v) 2200)
-(y) + sup
sup ('
(2) - .7)
y'Edom 9
((y) + sup
(w'0) (2(s/) + De(u.3'))
y' y'Edom
(2)) + ( + Da(u, ))" (0)
(v) (0).
The supremum above is achieved at some y' (0)
When Q V + ic, where C C dom Vi is nonempty closed convex set, using Lemmas and 2, have for all E C
2,(('') ((y') + Du(u.v) + ec(v').
B.9 Proof of Proposition 8 (lower bound)
was shown in [8, Proposition 3] that if f f= g + te, where the function g Legendre-type with C C dom V nonempty closed convex set, then for all E C and f E IR*,
0 (3. v (0)) < Ljer (v, with equality if - dom g. Using V f = 22 V + ic, D* (02 = 1r' jaay (v. 0), and Lemma 3, we therefore obtain
Dv, () = (y - v", V 2 (2 v²)) < Ln (v, 0) = L (v, 0).
If V is j-sttrongly convex and Da is convex in its second argument, then V, is j-strongly convex as well. Therefore, we also have
yl y 11 Dv, (g. )))
21

---

C Comment on the inf-addition convention too + (-oc) = +.00
The question of adding conflicting infinities has been thoroughly studied by Moreau in [23]. this paper, Moreau introduced two additions for IR U (-x,, +o0}. One of Moreau's two conventions for summing infinities can be found under the name of inf-addition in [27, Chapter 1]. The other convention is named sup-addition.
Using the inf-addition IR U {-o0, + allows, for instance, the equivalence of min (x) and millzER (xx) + (2)). The same goes for the sup-addition but for maxinization problems.
We used the inf-addition convention for the definition of the generalized Bregman divergence in (1). As the generalized Bregman divergence is to be thought of as a generalization of a distance, it is generally quantity that will be minimized. Therefore, the inf-addition is a good fit for the definition of the generalized Bregman divergence.
In the proof of Proposition 7 in B.8, the choice of inf-addition is corroborated by the fact that we want to calculate, for some fixed y IR. (S(() (y ()) sup, (y) 8) (S2(')
Da(y, v') )), Vy E TR.
The minus sign transforms the inf-addition into the sup-addition when distributed. If we had chosen the sup-addition the definition of the Bregman divergence Da, we would here calculate supremum of an inf-addition, thus entering unknown territory.
22

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: As stated in the abstract and in the introduction, have defined Fitzpatrick losses in Definition and studied their properties in Proposition 1. We instantiated the Fitzpatrick sparseMAP and the Fitzpatrick logistic loss in Proposition 5 and Proposition 6; we have studied the properties of Fitzpatrick losses in Proposition and Proposition 7; we have gathered the results of the label proportion estimation in Table 1.
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 in the paper and important assumptions and limitations. A No or NA answer to this question will not perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results
be expected to generalize other settings.
is fine to include aspirational goals as motivation as long 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]
We discuss the computational limitations of the Fitzpatrick logistic loss. As stated in Proposition and in Section 4, the computation the loss value and gradient involves solving root equation.
Justification:
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are 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 vell-specificattin, 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 with few runs. In general, empirical results often depend on implicit assumptions, which should be 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 is low or images are taken in low lighting. Or speech-to-text system might not be used reliably to 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, worse outcome might be that reviewers discover limitations that aren't acknowledged 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.
23

---

3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?
Answer: [Yes]
Justification: All results in the paper are proved in the appendix. We strived to make the proofs self-contained.
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 any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are 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 properly referenced.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions the paper (regardless of whether the code and data are provided or not)?
Answer: [Yes]
Justification: In Section 4, we describe the training setup, the linear model we use for predictions and give a link to access the datasets we use. We also indicate that we use the L-BFGS algorithm for training. Furthermore, Proposition and Proposition 6 yield formulae for the gradients of the new losses we introduce.
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 a novel architecture, describing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how replicate the results, access hosted model (e.g., in the of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how reproduce that algorithm. (b) If the contribution is primarily the architecture clearly and fully.
model architecture, the paper should describe
(c) the contribution a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).

---

(d)
We recognize that reproducibility may be tricky in some cases, in which case authors are welcome 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 to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification: We provided link for the used datasets in the experiments. The code will be opened upon release. For now, we provide instructions to reproduce the main experi- mental results. These instructions involved basic supervised learning tools such as L-BFGS algorithm, linear prediction model and standard cross- vrass-valiiation for the hyperparameter.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (httpa://nips. cc/ public/guie Stape//guieee//oeeeeeeeee Ceaee/ooeSSubbbeeccc SonoeeeSbmissiooooo. asionPolicy/ for more details.
While encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https: / /nnips cc/ppbcccccccccccccccccccccccccc httgguudee/eeee (CodeSubiissi www.rbmiissiooooeerro.. for more details.
The authors should provide instructions data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they 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 much information possible in supplemental material (appended the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (c.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: The selection of hyperparameter are discussed in section 4. We use predeter- mined train-test splits that come with the datasets.
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, or 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]
25

---

The split between training sets and test sets are fixed in advance so there is no variability when conducting the label proportion estimation tests. Furthermore, as minimize convex losses, the convergence of the minimization algorithm is independent of the starting point.
Justification:
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
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
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.
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 of range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
The characteristics of the computer we used to conduct the tests. On the largest dataset, our experiment only takes couple of hours to run.
Justification:
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (c.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 https:
Answer: [Yes]
Justification: The research conducted does not involve human subjects. We did not create new datasets and used standard open access datasets for multiclassification. After reviewing the "societal impact and potential harmful consequences" from the Code of Ethics, we conclude that the research conduct in the paper does not pose a risk of harmful consequences.
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
26

---

The authors should make sure 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:
The research conducted in this paper is theoretical and has societal impact.
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative socictal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deploymeetm 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 a direct path to any negative applications, the authors should point it out. For example, it is legitimate point out that an 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 a 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 a system learns from feedback over time, improving the efficiency and accessibility of MI.).
11. Safeguards
Question:
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)?
Answer: [NA]
Justification: The datasets used in the tests are publicly available. No new prediction model has been released in this paper.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-ust 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 is challenging, and many papers do not require this, but encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Question: Are the creators original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes]
27

---

Justification: In Section 4, the libraries used for the implementation of the numerical experiments are credited and cited.
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 or dataset.
The authors should state which version of the asset used and, possible, include a 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 (c.g.. website). the copyright and terms of service of that source should be provided.
assets are released, the license, copyright information, and terms use in the package should be provided. For popular datasets, paper swi chcode. com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's ss 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: The paper does not release new assets.
Guidelines:
The answer NA means that the paper does release new assets.
Researchers should communicate the details the dataset/code/moodl as part their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was 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. Crowdsourcing 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 as details about compensation (if any)?
Answer: [NA]
Justification:
The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing 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 much detail as possible should be included the main paper.
According to the NeurlPS Code of Ethics, workers involved in data collection, curation, 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 an equivalent approval/review based on the requirements of your country or institution) were obtained?
28

---

Answer:
[NA]
Justification:
The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does involve crowdsourcing nor research with
human subjects.
Depending on 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.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such the institution conducting the review.
29


Reviews:
[{"review_id": "P5ZXApjYDQ", "reviewer": "Reviewer_xpBU", "summary": "The paper proposes a family of losses based on the notion of a Fitzpatrick function, which takes the role of composable subdifferentials in Fenchel-Young losses. The resulting family of losses is parallel to Fenchel-Young losses in the sense that each Fenchel-Young loss has a shared link function with a certain Fitzpatrick loss, but the losses themselves differ. It is shown that these losses posses some desirable properties such as convexity, and that they are based on a type of duality that yields a smaller duality gap than the one based on the Fenchel-Young inequality. Representative Fitzpatrick losses, such as logistic and sparsemax losses are developed as examples of useful members of the family. \n\nExperiments show that the losses are mostly comparable in performance to their Fenchel-Young parallels, with the exception of the sparsemax loss that might be slightly improved in its Fitzpatrick version.", "questions": "No significant questions arise from reading the paper. It might be nice if the authors could comment on what potential they see for future research on this topic, and how", "limitations": "The authors mention some limitations such as somewhat increased computation time, and acknowledge the mixed empirical results. I find this to be an adequate treatment of limitations.", "rating": 5, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 2, "strengths": "The approach is original and imports ideas from operator theory into ML. Theory is laid out neatly and in an easy to understand manner. Loss functions are clearly an important part of training any ML model, hence improvements in them can be very significant even if they are small, and I assume that further progress beyond this paper can be significant in practice as well.", "weaknesses": "The empirical utility of the developed losses in not entirely clear, since they do not offer a significant advantage over standard losses, and in some cases (e.g. Fitzpatrick sigmoid) may be more computationally demanding.\nIn other losses such as the squared loss and hinge loss, the parallel Fitzpatrick losses are practically the same. Hence, the contribution here is mainly in exploring further definitions of losses that are associated with familiar link functions, but attach to them a loss function that is not the standard one that stems from the Fenchel-Young family.\n\nI am not an expert on this topic, so while I'm unsure whether the paper is interesting for its sub-community within ML, or for the wider NeurIPS audience (mainly because readers put a lot of emphasis on empirical results), I found it interesting enough to read hence I will give a borderline acceptance rating.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for taking the time to review our paper and for the feedback.\n\n> The empirical utility of the developed losses in not entirely clear, since they do not offer a significant advantage over standard losses, and in some cases (e.g. Fitzpatrick sigmoid) may be more computationally demanding.\n\nIndeed, as we clearly acknowledged in the experiment section, FP-logistic does not bring much benefit compared to FY-logistic. However, FP-sparsemax brings benefits compared to FY-sparsemax: FP-sparsemax performs better than FY-sparsemax for some datasets and comparably for the others. Therefore, FP-sparsemax should be considered as a viable alternative to FY-sparsemax, as it is not more computationally demanding. Indeed, as explained in Proposition 5 and in the text below it, FP-sparsemax is based on the projection on the simplex, just like FY-sparsemax.\n\nFurthermore, the FP-sparsemax loss can also be trained by dual coordinate ascent, similarly to the FY-sparsemax loss (see Section 8.2, Blondel et al. 2020). Indeed, for $\\Omega(y) = \\frac{1}{2}\\lVert y \\rVert^2 + \\iota_{\\triangle^k}(y)$,  dual coordinate ascent consists of computing these proximal operators for each subproblem associated with the sample $i$:\n- for FY-sparsemax: $\\mathrm{prox}_{\\frac{1}{\\sigma_i} \\Omega}(v_i)$;\n- for FP-sparsemax: $\\mathrm{prox}_{\\frac{2}{\\sigma_i} \\Omega}(\\frac{v_i - y_i}{\\sigma_i})$.\n\nBoth $\\mathrm{prox}$ have a similar computational cost, as they are both computed using formulas for $\\mathrm{prox}_{\\tau \\Omega}(\\eta)$, where $\\tau \\in \\mathbb{R}$ and $\\eta \\in \\mathbb{R}^k$, (see Section 8.4, Blondel et al. 2020).\n\nTherefore, FP-sparsemax and FY-sparsemax are equivalent in terms of computational cost, whether we use primal or dual training.\n\n> It might be nice if the authors could comment on what potential they see for future research on this topic\n\nFuture directions include calibration guarantees, new link functions and more efficient training for the FP-logistic loss.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "NiNmiiwxRr", "reviewer": "Reviewer_26BT", "summary": "The paper describes an alternative approach to constructing loss functions. The authors propose a Fitzpatrick loss and compare it to Fenchel-Young loss and Bregman divergence. The work enumerates the basic properties of the introduced loss and compares it to existing loss functions by numerical simulations.", "questions": "The paper claims that the Fitzpatrick losses are tighter than Fenchel-Young. Can something be said from the statistical point of view? Does using new loss lead to better generalization, for example.", "limitations": "The paper does not have negative societal impact.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "The overview of Fitzpatrick loss is nice. For the reader not acknowledged with the topic it is easy to get the main concepts. The authors also give examples and compare Fitzpatrick loss with Fenchel-Young loss.", "weaknesses": "I think the paper needs more thorough numerical evaluation due to the format of the conference. Although the properties of Fitzpatrick loss are given, the logical question is, why to use it instead of known loss functions for machine learning? At the moment, the authors presented comparison for classification problem over several datasets. Without broader experimental study, the manuscript seems more like a mathematical note. Therefore, I think that additional experiments will strengthen the paper.\n\nMoreover, the datasets are for classification, but the results are compared in terms of mean squared error. It seems more logical to compare using some metric for classification, i.e. accuracy, f1-score etc.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for taking the time to review our paper and for the feedback.\n\n> I think the paper needs more thorough numerical evaluation due to the format of the conference. \n\nOur paper is first and foremost a theoretical contribution: \n- it introduces a new family of losses that lower-bound Fenchel-Young losses;\n- it is the first practical application of the Fitzpatrick function;\n- it advances the Fitzpatrick function literature, e.g., Proposition 7 is a novel result.\n\nThat said, based on our empirical comparison on **11 datasets**, our main claim is that FP-sparsemax is a viable alternative to FY-sparsemax, as it performs better or comparably, and is not more computationally demanding.\n\n> Moreover, the datasets are for classification, but the results are compared in terms of mean squared error. It seems more logical to compare using some metric for classification, i.e. accuracy, f1-score etc.\n\nFollowing Blondel et al (2020), we are doing label proportion estimation experiments. Since the model outputs are probability distributions over the classes, the mean squared error is an appropriate measure for estimating the quality of prediction. It is known as the **Brier score**, in a probabilistic forecasting context.\n\n> Can something be said from the statistical point of view? Does using new loss lead to better generalization\n\nWe leave additional theoretical guarantees such as calibration or generalization to future work, as we believe the paper is already quite packed with results (8 propositions in the main text).", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "MSMGmiyo7U", "reviewer": "Reviewer_E7nS", "summary": "This paper proposes a class of loss functions called Fitzpatrick loss, based on the Fitzpatrick function known in maximal monotone operator theory. It can be shown that building a loss function with the proposed method, can give a convex loss function that lower bounds the Fenchel-Young loss under the same choice of link function for prediction. Extensive analysis provides in the paper also shows the relationship between Fitzpatrick loss and Fenchel-Young loss. Finally, experiments were provided to validate the usefulness of Fitzpatrick loss.", "questions": "1. Since Fitzpatrick loss lower bounds the Fenchel-young loss for the same link function, is it possible to find some use-cases that the proposed loss (e.g., Fitzpatrick-sparsemax) is preferable? For example, could it be more useful when we want to have sparse probability output and we have to learn under the case where there are outliers/noisy data?\n2. It is said that we can provide a relationship between Fitzpatrick loss and Fenchel-young loss by using \"target-dependent function\" in Section 3.3 (Prop. 7). I think the result is very interesting and I have two questions regarding this finding. \n- 2.1 Since we need target-dependent function for $\\Omega_y$ to make the relationship holds, does the original Fenchel-Young loss supports target-dependent function case? If so, then this should be no problem and we can state that all properties of Fenchel-young loss inherits to Fitzpatrick loss.\n- 2.2 Is it safe to say that Fitzpatrick loss is a special case of Fenchel-Young loss? Perhaps not?\n- 2.3 Can we also say that any Fenchel-young loss can be rewritten in a form of Fitzpatrick loss generated by different $\\Omega$?\n3. In the conclusion section, there was a discussion about \"there can only be one loss function associated with a certain link function\". I am not sure about this statement for the definition of loss function here. Is it about a \"proper composite\" loss function, a \"classification-calibrated\" loss function, or a convex + (proper composite/classification-calibrated) loss function? Maybe we can be more explicit here otherwise one might think about any function or small ad-hoc modification using the same link and use it as a loss function with not much problems. \n\n\nMinor comment\n1. Typo: Line 99: also know as -> also known as\n2. I feel it is a bit strange to say One loss is tighter than another loss since it is closer to zero everywhere.", "limitations": "The discussion was sufficient. The authors noted the challenge of computational problem and appropriately discussed the experimental results of the proposed method.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The proposed method is theoretically sound and novel to the best of my knowledge. This give rises to a way to construct a convex loss function systematically that lower bounds the family of Fenchel-young loss under the same link function for prediction.\n2. Not only the new class of loss function is proposed, but the characterization of the relationship between the proposed class of loss functions and existing loss was also provided to understand the research in this direction better.\n3. The paper is well-written overall and is friendly for also new people in the field who is not familiar with Fenchel-young loss function.", "weaknesses": "Although it is nice to also provide the experiments in the paper, I found that the experiment failed to motivate the usefulness of Fitzpatrick loss family in the sense that the performance is not preferable overall. I think no so many insights were provided when Fitzpatrick loss is more useful than existing losses in the literature. The proposed loss is also more computationally demanding. Perhaps different kinds of experiments would give more values to the paper. From the current experiments, I think we still need lots of work to study when to use Fitzpatrick loss in practice.\n\nMy current score is Weak accept (6) as I put importance to the theory to advance the understanding of Fenchel-young loss and Fitspatrick loss function quite high and believe these are the main contributions of this paper, rather than the experimental result.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for taking the time to review our paper and for the feedback.\n\n> Although it is nice to also provide the experiments in the paper, I found that the experiment failed to motivate the usefulness of Fitzpatrick loss family in the sense that the performance is not preferable overall.\n\nWe believe it is important to provide empirical results, even if they are partially positive and partially negative. What is important is that our conclusions are backed up by observations. Based on our experiments on 11 datasets, our conclusions are: \n- FY-logistic performs better or comparably compared to FP-logistic and is computationally cheaper. Therefore, FY-logistic remains the solution of choice when we want to use the soft-argmax link.\n- FP-sparsemax performs better or comparably compared to FY-sparsemax and is computationally equivalent. Therefore, FP-sparsemax is a viable alternative to FY-sparsemax when we want to use the sparse-argmax link.\n\n> The proposed loss is also more computationally demanding.\n\nIt is true that it is more computationally demanding to use the FP-logistic loss than its FY counterpart, as the former requires solving a root-finding problem (e.g., by bisection), while the latter enjoys a closed form (using the log-sum-exp).\n\nHowever, for FP-sparsemax, the situation is different. Indeed, computing the loss (and its gradient) is as computationally demanding as its FY counterpart (Proposition 5). Both only involve a projection on the simplex.\n\n> Since Fitzpatrick loss lower bounds the Fenchel-young loss for the same link function, is it possible to find some use-cases that the proposed loss (e.g., Fitzpatrick-sparsemax) is preferable? For example, could it be more useful when we want to have sparse probability output and we have to learn under the case where there are outliers/noisy data?\n\nBased on our experiments on 11 datasets, we found that FP-sparsemax is slightly better than FY-sparsemax. We also tried to add artificially various degrees of noise to labels but we did not observe any major change in our conclusions.\n\n> 2.1 Since we need target-dependent function for \n to make the relationship holds, does the original Fenchel-Young loss supports target-dependent function case? If so, then this should be no problem and we can state that all properties of Fenchel-young loss inherits to Fitzpatrick loss.\n\nIn principle, Fenchel-Young losses do not support target-dependent regularization functions $\\Omega_y$. The problem comes at prediction time, as we cannot compute $\\nabla \\Omega_y^*$, since $y$ is unknown. However, viewing Fitzpatrick losses as Fenchel-Young losses with target-dependent $\\Omega_y$ is useful because, as you point out and as we write in line 162, properties can be inherited easily from Fenchel-Young losses. For example, if $\\Omega_y$ is strongly convex, then the Fitzpatrick loss associated with $\\Omega$ is smooth.\n\n> 2.2 Is it safe to say that Fitzpatrick loss is a special case of Fenchel-Young loss? Perhaps not?\n\nThe answer is no by the theory of representations of maximal monotone operators (Burachik et al., 2002).\nHowever, in the paper we introduce the notion of target dependent Fenchel-Young losses (which are not strictly speaking Fenchel-Young losses). Indeed, one of the contributions of our paper is to rewrite Fitzpatrick losses as Fenchel-Young losses with a target-dependent $\\Omega_y$ (Proposition 7), while keeping the same target-independent link function $\\nabla \\Omega^*$. \n\n> 2.3 Can we also say that any Fenchel-young loss can be rewritten in a form of Fitzpatrick loss generated by different  $\\Omega$?\n\nAs both Fenchel-Young and Fitzpatrick losses only depend on the subdifferential of the generating function, the question boils down to ask if a Fenchel-Young loss generated by some subdifferential can be rewritten in the form of a Fitzpatrick loss for a different subdifferential.\nThe answer is no by Theorem 6.1 in (Burachik et al., 2002).\n\n> In the conclusion section, there was a discussion about \"there can only be one loss function associated with a certain link function\". I am not sure about this statement for the definition of loss function here. Is it about a \"proper composite\" loss function, a \"classification-calibrated\" loss function, or a convex + (proper composite/classification-calibrated) loss function? Maybe we can be more explicit here otherwise one might think about any function or small ad-hoc modification using the same link and use it as a loss function with not much problems.\n\nThank you for catching. We indeed meant convex loss function. Otherwise, it’s indeed possible to compose the link with some other loss function but the resulting composite loss function would be nonconvex in general. We also omit trivial loss modifications such as multiplying the loss by a non-negative scalar.\n\nWe fixed the typos reported by the reviewer.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "ABydlSEyUI", "reviewer": "Reviewer_C9fT", "summary": "This article presents a refreshing take on losses used in ML, with solid motivational examples and a several of interesting and beautiful results in pure convex analysis.", "questions": "- Line 69: As far as I've seen in most convex analysis books and papers, this convention is a bit nonstandard; typically, \"+infinity +  (-infinity)\" is *undefined*. Please comment on which results in this article break if the quantity \"+infinity + (-infinity)\" is undefined. I.e., if this is \"not a valid move\", which of your results still hold? It is very important to clarify which results hold under varying algebraic models of convex analysis.\n\n- Line 157 / Prop. 7: the relationship between the claim in the equation following Line 157 and Proposition 7 is unclear. How does the claim in line 157 follow from Proposition 7?", "limitations": "The mathematically precise statements (propositions, lemmas, theorems/etc.) should state **all** of their assumptions. In particular, the authors do not repeat that a compact domain of the objective function is required for several of their results. (Unless I'm missing something and compactness is not actually required?)\n\nThe authors do a great job of explaining the results of their experiments. More numerics is always a plus, but since the article has so many strong theoretical contributions, I am quite happy with this as-is.", "rating": 9, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "The Fitzpatrick function is a well-known tool for achieving very pure-theoretical results like Minty's theorem in convex analysis. However, before reading this article, I was under the impression that the Fitzpatrick function was just a theoretical tool with limited applications in-practice...\n\nUntil now! This paper takes a beautiful tool from pure convex analysis, spruces up some very interesting and new results, and presents it as a new application in ML with some very solid justification concerning sharper inequalities in comparison to the classical class of Fenchel-Young inequalities.", "weaknesses": "My main regret is that, due to the reviewing load, I was not able to fully check all of the proofs presented in the appendix. The claims *in the article* are reasonable, interesting, well-presented, and thorough; however, I am quite concerned that there may be some (unintentionally) omitted hypothesis, or holes in the proofs in the appendix (e.g., please also see my statement about Compactness of the domain in \"limitations\" section), because this often happens in ML conference articles. I wish that an appendix counted as the \"reviewed\" part of the article, but alas I simply do not have the time to check every detail. I am going to suggest that this paper is accepted, but I suggest that the authors please take care to revise based on the following minor points.\n\n\nMinor comments:\n- Citations appear to be out of numerical order when they are cited\n- Line 30: In what sense is \"proper\" meant? All losses I'm aware of\n  are proper functions (using the convex analysis definition).\n- Line 56: Is R_+ numbers which are strictly positive, or just\n  positive?\n- Line 59: The set must be nonempty for the projection to be defined.\n- Line 62: This identity only holds when \\Omega is differentiable  *and convex*! Otherwise, this definition of the subdifferential produces the emptyset in areas of concavity.\n- Line 66: Please provide a citation.\n- Line 68: Does this function need to be Legendre?\n- Line 101: Monotone is defined here, but mentioned earlier in the\n  article; would be nice to have the definition at the beginning.\n- Definition 1: Within the text of the definition, \"dom Omega\"  appears before Omega is introduced.\n- A bit more discussion would be nice on specifically which problems (4) can be calculated.\n- Line 132: \"Above expression\" referring to \"\\nabla^2 Omega\" is ambiguously defined, since in the constrained case Omega is not differentiable.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the very positive and detailed constructive feedback.\n\n> Citations appear to be out of numerical order when they are cited\n\nThis is because the references are sorted alphabetically by author name.\n\n> Line 30: In what sense is \"proper\" meant? All losses I'm aware of are proper functions (using the convex analysis definition).\n\nIn line 30, “proper” refers to “proper losses” or “proper scoring rules”, which we also mentioned in line 21 with citations (Gneiting et al. 2007) and (Grünwald et al. 2004). This notion of “proper” is not related to “proper functions” in convex analysis.\n\n> Line 56: Is R_+ numbers which are strictly positive, or just positive?\n\nWe added $\\mathbb{R}_+ := [0,+\\infty)$ to the notation section. \n\n> Line 59: The set must be nonempty for the projection to be defined.\n\nFixed.\n\n> Line 62: This identity only holds when \\Omega is differentiable and convex! Otherwise, this definition of the subdifferential produces the emptyset in areas of concavity.\n\nFixed.\n\n> Line 66: Please provide a citation.\n\nWe added Proposition 11.3 from \nR. T. Rockafellar and R. J-B. Wets. Variational Analysis. Springer-Verlag, Berlin, 1998.\n\n> Line 68: Does this function need to be Legendre?\n\nHere, $\\Omega$ needs not to be Legendre, as in Equation (1), \n $\\sup_{\\theta’ \\in \\partial \\Omega(y’)} \\langle y-y’, \\theta’ \\rangle$ is always well defined, although it can take the value $-\\infty$ or $\\infty$. This is why we use the convention\n$+\\infty +(-\\infty) = +\\infty$ in this definition.\n\n> Line 101: Monotone is defined here, but mentioned earlier in the article; would be nice to have the definition at the beginning.\n\nOn line 84, we added a reference to section 2.3.\n\n> Definition 1: Within the text of the definition, \"dom Omega\" appears before Omega is introduced. A bit more discussion would be nice on specifically which problems (4) can be calculated.\n\nFixed.\n\n> Line 132: \"Above expression\" referring to \"\\nabla^2 Omega\" is ambiguously defined, since in the constrained case Omega is not differentiable.\n\nThe reviewer is right, we have neglected to mention that the function is twice differentiable on the interior of its domain. This is now fixed.\n\n> Line 69: As far as I've seen in most convex analysis books and papers, this convention is a bit nonstandard; typically, \"+infinity + (-infinity)\" is undefined. Please comment on which results in this article break if the quantity \"+infinity + (-infinity)\" is undefined. I.e., if this is \"not a valid move\", which of your results still hold? It is very important to clarify which results hold under varying algebraic models of convex analysis.\n\nThis question of adding conflicting infinites has been thoroughly studied by Moreau in:\n\nInf-convolution, sous-additivité, convexité des fonctions numériques.\nJ. Math. Pures Appl. (9), 49:109–154, 1970.\n\nIn this paper, Moreau introduced two additions for $\\mathbb{R} \\cup \\{-\\infty,+\\infty}$.\nOne of the two Moreau’s conventions for summing the infinites can be found under the name of inf-addition in Chapter 1 Section E. in R. T. Rockafellar and R. J-B. Wets. Variational Analysis. Springer-Verlag, Berlin, 1998.\n\nTo make a long story short, one of them is used for minimization and the other for maximization.\nUsing the inf-addition on $\\mathbb{R} \\cup \\{-\\infty,+\\infty}$ allows for things like $\\min_C f$ coinciding with $\\min_{\\mathbb{R}^n} f(x) + \\iota_C(x)$, where $C \\subset \\mathbb{R}^n$, and $f : \\mathbb{R}^n \\to \\mathbb{R} \\cup \\{-\\infty,+\\infty}$.\n\nAs the generalized Bregman divergence $D_\\Omega$ is to be thought of as a generalization of a distance, it is generally a quantity that will be minimized. So, the inf-addition fits the definition of the generalized Bregman divergence in line 69.\n\nIn the proof of Proposition 7, the choice of inf-addition is corroborated by the fact that we want to calculate, for some fixed $y\\in \\mathbb{R}^n$, \n$\\big( \\Omega(\\cdot)+ D_\\Omega(y,\\cdot) \\big)(\\theta)\n = \\sup_{y’} \\langle y’, \\theta \\rangle - \\big( \\Omega(y’)+ D_\\Omega(y,y’) \\big), \\forall y’ \\in \\mathbb{R}^k$.\nThe minus sign transforms the inf-addition into the sup-addition when distributed.\nIf we had chosen the sup-addition in the definition of the Bregman divergence $D_\\Omega$, we would here calculate a supremum of an inf-addition, thus entering unknown territory.\n\nTo conclude, the natural choice for addition in the definition of the generalized Bregman divergence is the $+\\infty + (-\\infty) = + \\infty$.\n\n> Line 157 / Prop. 7: the relationship between the claim in the equation following Line 157 and Proposition 7 is unclear. How does the claim in line 157 follow from Proposition 7?\n\nWe are not sure if we understand the question correctly. Line 157 is a definition, not a claim. It is what we call the target-dependent regularization $\\Omega_y$. With the definition in line 157, Proposition 7 shows that $F[\\partial \\Omega](y, \\theta)$ coincides with $\\Omega_y(y) + \\Omega_y^*(\\theta)$. And therefore the Fitzpatrick loss generated by $\\Omega$ coincides with the Fenchel-Young loss generated by $\\Omega_y$.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "qvxqgS0iwH", "reviewer": "Reviewer_3f1M", "summary": "The paper proposes the Fitzpatrick loss, a tighter version of the Fenchel-Young loss. Fitzpatrick losses are defined based on the monotone operator theory. In particular, the Fitzpatrick function satisfies a tighter inequality than the Fenchel-Young inequality, leading to the tighter loss function. The authors elucidate the fundamental properties of the Fitzpatrick loss and present concrete examples, demonstrating that Fitzpatrick sparsemax/logistic losses indeed differ from the Fenchel-Young counterparts. The authors also show that the Fitzpatrick loss can be seen as the Fenchel-Young loss generated by target-dependent regularizes and that it is connected to generalized Bregman divergences, while the primal-dual nature of the Fitzpatrick loss crucially makes it convex. A lower bound on the Fitzpatrick loss is also presented, which is analogous to the Fenchel-Young counterpart. Finally, experiments compare Fitzpatrick and Fenchel-Young losses on classification tasks.", "questions": "1. A special form of target-dependent regularizers is used for constructing the cost-sensitive Fenchel-Young loss ([Blondel et al. 2020, Section 3.4](https://jmlr.csail.mit.edu/papers/v21/19-021.html)). Does the Fitzpatrick loss have any relation with the cost-sensitive Fenchel-Young loss?\n2. Is it possible to establish calibration of target and Fitzpatrick excess risks, as in [Blondel (2019, Proposition 5)](https://proceedings.neurips.cc/paper_files/paper/2019/hash/7990ec44fcf3d7a0e5a2add28362213c-Abstract.html)? The lower bound in Proposition 8 seems useful for this. \n3. Regarding lines 164-165, is there a canonical class of convex functions $\\Omega$ such that $D\\_\\Omega$ is convex in the second argument?\n4. In the experiments, predictions are produced by $\\hat y\\_\\Omega(Wx)$, and I can understand this since the Fitzpatrick loss has $\\hat y_\\Omega$ as the link function as in Proposition 1. On the other hand, given the discussion in Section 3.3, $y^*\\_{F[\\partial\\Omega]}(y, \\theta)$ also appears to be a Fitzpatrick counterpart of $\\hat y\\_\\Omega(\\theta)$, which, however, cannot be used in the test phase since ground truth $y$ is not available. So, when $W$ is learned with the Fitzpatrick loss, aren't there other possible methods for converting $Wx$ to a prediction other than $\\hat y\\_\\Omega(Wx)$ (without knowing $y$)?\n\n#### **Minor comments**\n- l. 84. \"$\\hat y\\_\\Omega$ is monotone...\" Does this \"monotone\" refer to the one in Section 2.3? If so, it is not yet defined there.\n- Eq. (4). Enclosing the terms after \"argmax\" in parentheses will make it easier to read.\n- l. 174. that that.\n- Proposition 8. Reminding that $\\Psi_y$ is defined as with $\\Omega_y$ in Section 3.3 is helpful; alternatively, it may be better to define $\\Omega_y$ as a general notation in Section 3.3 or earlier.", "limitations": "The authors have discussed the limitation regarding computation costs.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The paper presents a novel framework for designing loss functions from link functions. Prior to the work, the Fenchel-Young loss is the only such framework. The current work opens a new direction for designing various other loss functions with rigorous foundations of monotone operator theory. I believe this is of great benefit to the machine-learning community. \n2. The paper discusses the properties of the Fitzpatrick loss and its connection to other notions (Fenchel-Young losses and generalized Bregman divergences) in detail. This is helpful for readers who are familiar with either of the existing notions.", "weaknesses": "A weakness (not so serious) is that the experimental results are not very compelling. Still, I find the slight superiority of Fitzpatrick-sparsemax to Sparsemax noteworthy as their computation costs are almost the same.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the very positive and constructive feedback.\n\n> A special form of target-dependent regularizers is used for constructing the cost-sensitive Fenchel-Young loss (Blondel et al. 2020, Section 3.4). Does the Fitzpatrick loss have any relation with the cost-sensitive Fenchel-Young loss?\n\nThere is similarity but the additional target-dependent term is linear in their case, while it is a general Bregman divergence in our case. We also tried to write the multiclass hinge loss as a Fitzpatrick loss, but we believe this is not possible.\n\n> Is it possible to establish calibration of target and Fitzpatrick excess risks, as in Blondel (2019, Proposition 5)? The lower bound in Proposition 8 seems useful for this.\n\nThis is an interesting question but we leave the study of calibration guarantees to future work. \n\n> Regarding lines 164-165, is there a canonical class of convex functions \n such that is convex in the second argument?\n\nWe do not know a class of convex functions $\\Omega$ such that the generated generalized Bregman distance $D_\\Omega$ is convex in the second variable.\nWe can see the difficulty of finding such convex functions by considering the case of differentiable $\\Omega$ on the interior of its domain. In this case, we recover the classical Bregman divergence,\n$D_\\Omega(y,y’) = \\Omega(y) - \\Omega(y’) - \\langle y-y’,\\nabla\\Omega(y’) \\rangle $.\nWhen $\\Omega$ is the Shannon negentropy or the squared 2-norm, $D_\\Omega(y,\\cdot)$ is convex for all $y \\in \\mathrm{dom}~\\Omega$ because \n$y’ \\mapsto \\langle y’, \\nabla \\Omega(y’) \\rangle - \\Omega(y’) $ is convex, which is usually\nnot the case.\n\n> when is learned with the Fitzpatrick loss, aren't there other possible methods for converting $Wx$ to a prediction?\n\nIt is indeed possible that other methods exist. For example, as an heuristic, we could try to replace the unknown $y$ with the average of the label proportions in the dataset. The calibration study could further suggest new principled methods.\n\n> l. 84. \"is monotone...\" Does this \"monotone\" refer to the one in Section 2.3? If so, it is not yet defined there.\n\nThank you, we added a reference to section 2.3.\n\n > Eq. (4). Enclosing the terms after \"argmax\" in parentheses will make it easier to read.\n\nDone, thanks.\n\n> Proposition 8. Reminding that  $\\Psi_y$\n is defined as with $\\Omega_y$ in Section 3.3 is helpful; alternatively, it may be better to define \n as a general notation in Section 3.3 or earlier.\n\nDone, thanks.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
We thank the reviewers for the very positive and constructive feedback, as well as the ACs for their editorial work. We summarize below our main replies to the reviewers (see reply to each reviewer for more details).

* All comments have been addressed (minor typos, some assumptions that were in the text have been moved explicitly in the propositions).
* Our paper is first and foremost a theoretical contribution (**8 propositions** in the main text), advancing both the literature on loss functions and the literature on Fitzpatrick functions. It is the first practical application of the Fitzpatrick function.
* Following Blondel et al (2020), we are doing label proportion estimation experiments and we use MSE (also known as **Brier score**) for evaluation.
* Based on our experiments on **11 datasets**, our conclusions are: 
  - FY-logistic performs better or comparably compared to FP-logistic and is computationally cheaper. Therefore, FY-logistic remains the solution of choice when we want to use the soft-argmax link (a.k.a. softmax).
  - FP-sparsemax performs better or comparably compared to FY-sparsemax and is computationally equivalent. Therefore, FP-sparsemax is a viable alternative to FY-sparsemax when we want to use the sparse-argmax link (a.k.a. sparsemax).

Meta-review: Overall, all reviewers found the main theoretical contribution of this paper (the introduction of the convex Fitzpatrick loss functions) to be compelling and well explained. It is thus an easy accept. Most reviewers found empirical motivation a bit lacking, since the new loss functions do not seem to lead to any especially large performance gains in common settings. However, this was mitigated by the strong theoretical contributions of the work. Hopefully the paper will spur further investigation on the empirical side of things.
Decision: Accept (poster)