Learning with Fitzpatrick Losses

We thank the reviewer for the very positive and constructive feedback.

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?

There 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.

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.

This is an interesting question but we leave the study of calibration guarantees to future work.

Regarding lines 164-165, is there a canonical class of convex functions such that is convex in the second argument?

We do not know a class of convex functions $\Omega$ such that the generated generalized Bregman distance $D_\Omega$ is convex in the second variable. We 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, $D_\Omega(y,y’) = \Omega(y) - \Omega(y’) - \langle y-y’,\nabla\Omega(y’) \rangle$. When $\Omega$ is the Shannon negentropy or the squared 2-norm, $D_\Omega(y,\cdot)$ is convex for all $y \in \mathrm{dom}~\Omega$ because $y’ \mapsto \langle y’, \nabla \Omega(y’) \rangle - \Omega(y’)$ is convex, which is usually not the case.

when is learned with the Fitzpatrick loss, aren't there other possible methods for converting $Wx$ to a prediction?

It 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.

l. 84. "is monotone..." Does this "monotone" refer to the one in Section 2.3? If so, it is not yet defined there.

Thank you, we added a reference to section 2.3.

Eq. (4). Enclosing the terms after "argmax" in parentheses will make it easier to read.

Done, thanks.

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 as a general notation in Section 3.3 or earlier.

Done, thanks.

We thank the reviewer for the very positive and detailed constructive feedback.

Citations appear to be out of numerical order when they are cited

This is because the references are sorted alphabetically by author name.

Line 30: In what sense is "proper" meant? All losses I'm aware of are proper functions (using the convex analysis definition).

In 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.

Line 56: Is R_+ numbers which are strictly positive, or just positive?

We added $\mathbb{R}_+ := [0,+\infty)$ to the notation section.

Line 59: The set must be nonempty for the projection to be defined.

Fixed.

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.

Fixed.

Line 66: Please provide a citation.

We added Proposition 11.3 from R. T. Rockafellar and R. J-B. Wets. Variational Analysis. Springer-Verlag, Berlin, 1998.

Line 68: Does this function need to be Legendre?

Here, $\Omega$ needs not to be Legendre, as in Equation (1), $\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 $+\infty +(-\infty) = +\infty$ in this definition.

Line 101: Monotone is defined here, but mentioned earlier in the article; would be nice to have the definition at the beginning.

On line 84, we added a reference to section 2.3.

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.

Fixed.

Line 132: "Above expression" referring to "\nabla^2 Omega" is ambiguously defined, since in the constrained case Omega is not differentiable.

The reviewer is right, we have neglected to mention that the function is twice differentiable on the interior of its domain. This is now fixed.

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.

This question of adding conflicting infinites has been thoroughly studied by Moreau in:

Inf-convolution, sous-additivité, convexité des fonctions numériques. J. Math. Pures Appl. (9), 49:109–154, 1970.

In this paper, Moreau introduced two additions for \mathbb{R} \cup \{-\infty,+\infty}. One 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.

To make a long story short, one of them is used for minimization and the other for maximization. Using 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}.

As 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.

In 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$, $\big( \Omega(\cdot)+ D_\Omega(y,\cdot) \big)(\theta) = \sup_{y’} \langle y’, \theta \rangle - \big( \Omega(y’)+ D_\Omega(y,y’) \big), \forall y’ \in \mathbb{R}^k$. The minus sign transforms the inf-addition into the sup-addition when distributed. If 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.

To conclude, the natural choice for addition in the definition of the generalized Bregman divergence is the $+\infty + (-\infty) = + \infty$.

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?

We 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$.

We thank the reviewer for taking the time to review our paper and for the feedback.

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.

We 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:

• 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.
• 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.

The proposed loss is also more computationally demanding.

It 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).

However, 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.

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?

Based 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.

2.1 Since we need target-dependent function for 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.

In 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.

2.2 Is it safe to say that Fitzpatrick loss is a special case of Fenchel-Young loss? Perhaps not?

The answer is no by the theory of representations of maximal monotone operators (Burachik et al., 2002). However, 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^*$.

2.3 Can we also say that any Fenchel-young loss can be rewritten in a form of Fitzpatrick loss generated by different $\Omega$?

As 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. The answer is no by Theorem 6.1 in (Burachik et al., 2002).

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.

Thank 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.

We fixed the typos reported by the reviewer.

We thank the reviewer for taking the time to review our paper and for the feedback.

I think the paper needs more thorough numerical evaluation due to the format of the conference.

Our paper is first and foremost a theoretical contribution:

• it introduces a new family of losses that lower-bound Fenchel-Young losses;
• it is the first practical application of the Fitzpatrick function;
• it advances the Fitzpatrick function literature, e.g., Proposition 7 is a novel result.

That 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.

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.

Following 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.

Can something be said from the statistical point of view? Does using new loss lead to better generalization

We 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).

We thank the reviewer for taking the time to review our paper and for the feedback.

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.

Indeed, 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.

Furthermore, 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$:

• for FY-sparsemax: $\mathrm{prox}_{\frac{1}{\sigma_i} \Omega}(v_i)$;
• for FP-sparsemax: $\mathrm{prox}_{\frac{2}{\sigma_i} \Omega}(\frac{v_i - y_i}{\sigma_i})$.

Both $\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).

Therefore, FP-sparsemax and FY-sparsemax are equivalent in terms of computational cost, whether we use primal or dual training.

It might be nice if the authors could comment on what potential they see for future research on this topic

Future directions include calibration guarantees, new link functions and more efficient training for the FP-logistic loss.