Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: summary: This paper present a novel approach to perform direct optimization of non-decomposable objective functions (such as AUC or F-measure) in the context of Deep Learning.
They propose a general LP-based framework describing these objective functions and provide a general algorithm to solve this problem (and get the corresponding gradients).
Finally, this new approach is compared to other methods trying to optimize these objectives directly and surrogate loss functions that are commonly used in practice.
main_review: I think the paper is well written and strike a good balance of technical details and high level intuition. And clearly states which results are included or left in the supplementary materials.

From a high level:
- While stochastic training is omnipresent and explicitly mentioned l33 and l177, there is no discussion in this paper that discuss the impact of the impossibility of computing the exact objective function on the whole dataset. A lot of these more principled methods usually struggle to reconcile this idea that the objective itself cannot be computed to begin with (let alone quickly or be optimized). Could you clarify how the method presented here is positioned with respect to that? In particular for the LP formulations in Section 2.
- l41 mentions that the LP that is being solved is a relaxation in  these cases, it would be nice to have some details on how good this relaxation is? And if it could be interesting to get a more tight one?
- The limited number of iteration used for this algorithm also remind me of other "optimization as layer" work done on CRFs. Where a limited numbers of optimization steps are done and provide most of the benefit. Maybe citation of such work would give a nice backing for this choice here.
- l205-207 such hyperparameter can have a big impact in practice on the result and cross validating them is a significant endeavor (especially when different part of your network have such parameters). Do you have any experimental result on this sensitivity? And how crucial is the lambda tuning?
- l214 do you have any result on data-driven SDR?
- The absence of baseline trying to optimize the multiclass AUC is surprising. Could you detail why?

Smaller details:
- Thanks for including a notations section!
- l165 "exterior penalty in (3)" is not defined
- l168-169: I am not sure what this sentence is showing? In particular, you need to be able to evaluate your function efficiently to be able to use it. I don't see why AD is used as an argument here.
- l189 the value given in parenthesis is a pair of values?
- l225 the sentence is not english. More generally, a few sentence in the paper would gain at being shorter.
- l234, why do you redifine Q = H tilde ? Why not just keep using H tilde?
- l252 using -> during
- l257 the discussion around Danskin's theorem is surprising here as it is not mentioned anywhere else in the paper.
- Fig 2 is never linked from the text, same for Fig 3a as far as I can see
- l316 formatting is weight. It could be better aligned to avoid the single dangling line
- l324 which results?
- Table 3: "N" should be defined in the caption.


limitations_and_societal_impact: The authors clearly address the limitations of the method in a clear paragraph.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This work proposes to relax some commonly used discrete metrics into a Linear Program (LP). By using the Newton LP method, the algorithm is able to backpropagate through the LP and thus to train a neural network end-to-end while directly optimizing for the metric. In particular, this submission describes how the AUC, multi-class AUC and F-score can be casted as LPs, and how the resulting problems can be solved with a Newton LP method that can be differentiated through. Experiments are presented on Cat&Dog, CIFAR-10, CIFAR-100 and STL.
main_review: ### Strengths
1. The problem is well motivated: end-to-end training for metrics such as AUC would be of practical interest to the machine learning community.
2. The formulation seems sound and amenable to efficient (and differentiable) optimization methods.
3. The submission is evidently the result of a solid amount of work to scale the method for deep learning, including implementations of sparse operations for a common deep learning framework.
4. The experiments (which are "medium-scale" by deep learning standards) show consistent improvements over the baselines.

### Weaknesses
1. This work is difficult to follow and sometimes unclear, and would benefit from extra work on clarity before sharing with the community, hence why I am not giving a higher rating (more details in Questions and Minor comments).
2. The experimental evaluation does not seem to provide a timing comparison with the baselines (e.g. Cross-Entropy): the improved performance should also be put in perspective with the amount of time that each method takes.

### Questions
1. Why is it stated that the number of constraints $m$ is much larger than the number of variables? It seems to me that in e.g. 2.2 there are about as many variables as constraints.
2. Why is epsilon needed in the formulation of 2.2? If the computation of the AUC outputs only binary values, then could not one just use the indicator function $z_{ij} > 1$ (and "backpropagate" through this operation with 0/1 according to whether the value is 0/1)?
3. Is it correct to say that at each iteration, the metrics are only computed on the current mini-batch? (this should be made clearer in the paper). If so, how does the batch-size affect the performance of the algorithm, since the metrics are not decomposable over the samples?
4. L.177 the paragraph title is "Why is Newton’s method applicable for minibatches?" but the content does not seem to address this question, can this be clarified?
5. In Lemma 1, it is stated that g can be approximated by a constant function. It seems more logical that it should be approximated by a quadratic function, is this a typo?
6. Can the authors discuss how the proposed method compares with existing work on direct loss optimization such as [1]?

### Minor comments:
1. To improve clarity, it would be beneficial to summarize the overall computational graph at the beginning: the model "backbone" yields a classifier score, which is used to construct the parameters of the LP, which itself is then solved to compute the metric in a differentiable way. This organization is not clear at the first read.
2. L.104 the second sum for $X_-$ should be over $j$
3. Results on nonnegative matrix factorization are announced in the experiments section, but turn out to be available in the supplementary material only.
4. It is confusing to use he notation $\epsilon$ for both the Linear Program Newton method and the relaxation, since they have different meanings in these two contexts.

### Reference

[1] Song, Yang, Alexander Schwing, and Raquel Urtasun. "Training deep neural networks via direct loss minimization." International Conference on Machine Learning. PMLR, 2016.

----

### Updated Review

Thanks to the authors for their detailed and informative response which addresses all my questions. I am updating my rating from 6 to 7, counting on the authors to update the manuscript so that it has (1) a clearer exposition of the method and (2) a more thorough related work section (including references suggested here and in other reviews).
limitations_and_societal_impact: Sufficiently discussed.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper proposes a new method for training neural networks using LP-based loss functions that involves adapting Mangasarian’s Exterior-point Newton Method. The authors prove new theoretical properties for the Exterior-point Newton method, propose a backward pass technique, and perform experiments on several image data sets to validate their method.

main_review: **After rebuttal**

I thank the authors for their detailed rebuttal. The authors have clarified my main questions regarding the correctness of the Lemma and using PPD in multi-class AUC. I am happy to recommend acceptance.


However, I strongly urge the authors to revise the clarity of the paper with (i) a proper related works section and (ii) clear and correct statements of the theorems and their proofs. The work has a lot of moving parts and can be difficult to read. As another reviewer mentioned, the paper would benefit greatly with some extra work on improving the clarity.


**Original review**

The experiments in this paper seem convincing that the authors have built a Pytorch library that allows for efficiently maximizing AUC and other LP-type objectives. However, I found overall this paper very difficult to read. It uses ideas from and compares with various works but there is no structure to guide an unfamiliar reader. Trivial topics are explained in detail but core prerequisites are missing. Furthermore the math is difficult to follow: (i) the notation frequently changes and terms are not properly defined, (ii) statements are vague with hidden assumptions. All of this makes it difficult to understand the originality and quality of the contributions of this work.


Related literature: this is presented sporadically in Section 1 and then Section 3.0. In both cases, a reader cannot appreciate this related works because the proposed methods of the paper have not been introduced. I would recommend for clarity that the authors produce a separate Related literature section where they can properly compare the weaknesses of existing methods.

Lines 84-96: The notation and LP setup are useless because the authors do not ever use most of this afterwards in the paper (e.g., target label $Y$ and non-linear function $\phi$). The breakdown of the LP from $c^T x$ to $g^T u + h^T v$ is never used afterwards. This makes the paper even more confusing because notation $x$, $y$, $g$, $u$, etc. are all recycled in Section 3.
- Please try to maintain some consistent notation throughout the paper. In Section 2.1, $x$ is first a row of the data matrix (line 87), then a variable of an optimization problem (line 95). Then in Section 2.2, the variable is now $z$. Then in Section 3, the variable is $y$. 

Line 174: Please unpack this math. $\tilde{H}$ is implicitly defined and only here but it is needed later below. Please also define $\rho$. 

The statement of Lemma 1 is vague.
- Under what distributional assumptions is $A$ is a random matrix? The answer is hidden in the supplement at the end of the proof, where the authors state their assumption that the rows of $A$ are uniformly distributed over a sphere.  
- Typo: “constant” -> “quadratic” ?

The randomness assumption in Lemma 1 leads to the follow up question: is this assumption satisfied in practice? From my understanding of S2.2, the constraint matrices in the LPs contain rows which are just random identity vectors, which is not a continuous uniform distribution over the sphere.

Similarly, the statement of Theorem 2 in the paper is vague. The statement in the supplement is different from the one in the paper but actually includes the core assumptions needed to make the statement meaningful.

The experiments are overall satisfactory although I would have liked to see some more baselines. For example, Multiclass AUC in Table 2 compares only against Cross-Entropy, which is obviously going to be a poor baseline. 
- Why can’t you apply PPD to multi-class AUC? If this is a limitation of existing methods then it would have been nice to clarify and make your method more appealing.

It seems to me that the data sets used in numerical evaluation are customized to appear as long-tail distributions. As a future direction, I would be interested to see whether the method in this work could be applied directly to long-tail data sets (e.g., CIFAR10-LT, CIFAR100-LT).
limitations_and_societal_impact: This paper discusses the limitations of the work in detail.
review_title: null

Meta-review: Thank you for your submission to NeurIPS.  The reviewers and I are in agreement that the proposed work presents some substantial advances to the topic of optimizing non-decomposable metrics, in this case using a nice application of unrolled smoothed LP solving.  The reviewers provided several comments, and in some cases have already improved their scores after rebuttal.  I would only suggest that the authors be sure to make these modifications, but I have no concerns, as these are largely easy to make.  I'm happy to recommend the paper for acceptance.
Decision: Accept (Poster)