Learning with Fitzpatrick Losses

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.

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

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? 2. 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. 3. Regarding lines 164-165, is there a canonical class of convex functions $\Omega$ such that $D\_\Omega$ is convex in the second argument? 4. 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$)? #### **Minor comments** - 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. - Eq. (4). Enclosing the terms after "argmax" in parentheses will make it easier to read. - l. 174. that that. - 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.

Rating

7

Confidence

3

Soundness

3

Presentation

3

Contribution

3

Limitations

The authors have discussed the limitation regarding computation costs.

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.

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... Until 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. Minor comments: - Citations appear to be out of numerical order when they are cited - Line 30: In what sense is "proper" meant? All losses I'm aware of are proper functions (using the convex analysis definition). - Line 56: Is R_+ numbers which are strictly positive, or just positive? - Line 59: The set must be nonempty for the projection to be defined. - 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. - Line 66: Please provide a citation. - Line 68: Does this function need to be Legendre? - Line 101: Monotone is defined here, but mentioned earlier in the article; would be nice to have the definition at the beginning. - 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. - Line 132: "Above expression" referring to "\nabla^2 Omega" is ambiguously defined, since in the constrained case Omega is not differentiable.

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

Rating

9

Confidence

4

Soundness

4

Presentation

4

Contribution

4

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?) The 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.

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.

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. 2. 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. 3. 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. My 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.

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? 2. 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. - 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. - 2.2 Is it safe to say that Fitzpatrick loss is a special case of Fenchel-Young loss? Perhaps not? - 2.3 Can we also say that any Fenchel-young loss can be rewritten in a form of Fitzpatrick loss generated by different $\Omega$? 3. 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. Minor comment 1. Typo: Line 99: also know as -> also known as 2. I feel it is a bit strange to say One loss is tighter than another loss since it is closer to zero everywhere.

Rating

7

Confidence

3

Soundness

3

Presentation

3

Contribution

3

Limitations

The discussion was sufficient. The authors noted the challenge of computational problem and appropriately discussed the experimental results of the proposed method.

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.

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

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.

Rating

6

Confidence

3

Soundness

3

Presentation

3

Contribution

2

Limitations

The paper does not have negative societal impact.

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

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

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

Rating

5

Confidence

3

Soundness

4

Presentation

3

Contribution

2

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.

Post Rebuttal Update

Thank you for the response. I understand that the point of the paper is not to introduce "better" losses than FY, and appreciate the paper for the results it presents. Therefore I will keep my recommendation to accept the paper.

Thank you for the author feedback

I have read other reviews as well as the author rebuttal. Thank you very much for the detailed feedback. Thank you for clarifying my concerns and my potential misunderstanding. I agree with other reviewers and the paper that this paper provides a theoretical foundation for the Fitzpatrick loss which is novel to the best of my knowledge. Even though experimental results are not very strong and thus more investigation of empirical performance is needed, it can be studied in the future for some specific applications of interest. In this current form, I think the paper is worth an acceptance. As a result, I raised the score to 7 (Accept).