Venue: ICLR 2021 Conference

Reviews:

final_score: rating: 5: Marginally below acceptance threshold
review_content: A. Summary:
This paper approximates several nondecomposable functions (AUC and F1-score) as linear programmings and uses them as loss functions for network training. In the linear programmings, the constraints are indeterministic at each mini-batch, the number of constraints increases quadratically to the number of training samples, so some previous works are inapplicable here. So does the primal-dual based forward pass and the corresponding implicit differentiation for a backward pass.
Instead, the authors propose to select Newton's method for the forward pass and an adaptive online adjustment for the backward pass, where gradients are back-propagated through unrolled optimization before a proper accuracy is found, and then through complementary slackness afterward.
Finally, the experiments emphasize the condition when the positive/negative examples are imbalanced, and demonstrates the superiority of the proposed methods to cross-entropy loss and one previous AUC loss.

B. Strength:
1. This paper gives a clear discussion about the difference between the proposed method and previous works, which motivates the author to explore an alternative solution to integrate linear programming as a differentiable component for training.
2. It is a good choice to use Newton's method to tackle down the problem for training. For training, we care less about whether an optimization algorithm will achieve the global optimal solution, instead, we care more about whether the algorithm can achieve a local optimal rapidly, therefore the training will be feasible for larger-scale problems while the gradient can still be derived through complementary slackness.

C. Weakness:
1. Determining the accuracy \epsilon seems to be critical for the proposed algorithm. It would be good if the author could have some more explanation about this. Besides, is that possible to make it a learnable variable through back-propagation at the first stage? Since the gradient is backpropagated via unrolling at first, it should be doable and save some manual effort to decide how to increase it.
2.  In the experiments, the authors constructed an imbalanced dataset from the existing dataset, In addition, some other recent works, such as Lin, TY, Goyal, P, Girshick, R, He, K, Dollar, P, "Focal Loss for Dense Object Detection", ICCV'2017, also focus on deal with the class imbalance by other tricks. So it would be better to compare with these methods as well but not only vanilla cross-entropy. 
3.  The application of nonnegative matrix factorization should be further improved. As indicated in the paper, it only works when the number of channels is limited. The author may remove this application and focus on the AUC and F1-score. The contribution will be sufficient enough if these two widely used metrics can be discussed more solidly.
4.  What if we fine-tune a pre-trained model using the proposed losses and the dataset is not manually selected to make it imbalance? Will the performance achieve consistent improvements?

D. Justification of the score:
In general, this paper focus on an important problem, and the algorithm is discussed comprehensively. My major concern is about the experiments, where the experimenting settings are biased to the proposed algorithm. I will raise my score if these concerns can be addressed during rebuttal.

review_title: A good solution to tackle down large linear programming for training, but with some biased experiment settings.

final_score: rating: 5: Marginally below acceptance threshold
review_content: This paper addresses the classical topic of directly optimizing non-decomposable loss functions. Since these metrics can be computed via linear programs, it is sufficient to compute gradient through the LP solver. To that end, the authors propose to use a particular method for solving linear programs. In experiments, the resulting implementation outperforms the cross-entropy loss and mildly outperforms one recent baseline.

The topic of direct optimization of AUC, F1, and all the other related metrics is still of high practical interest and meaningful progress would be of high significance. However, the main reason why this topic is still open is that none (or a handful) of the dozens of top-tier publications addressing it, delivered a method that is reliable, stable, and scalable to practical setups (e.g. in computer vision). For this reason, I think, any new paper in this area needs to undergo a high level of scrutiny.

I believe this paper has merit and constitutes a perfectly reasonable submission. At the same time, in its current form, it does not indicate sufficiently why it should have a different fate than all the other papers that also outperformed cross-entropy and subsequently disappeared.

My objections to the paper fall into three categories

### Conceptual confusion 

In this section, I want to clarify that gradients to LPs are a mostly solved problem and there is no dire need to resort to a new type of an LP solver -- as the authors do. I will also contradict the claim "a simple closed-form gradient is not available for backpropagation" made on page 4

For clarity let's focus on three scenarios (in the notation of the paper):

1) Taking derivatives of the **optimal value of the objective function** w.r.t the LP parameters $c$, $b$, $A$

In all these cases, there is a simple closed-form gradient. E.g. if $x^*$ is optimal, the corresponding objective is $z = z(c) = c^T x^*(c)$ where the dependence of $x^*$ on $c$ is highlighted. This is a piecewise linear function ($x^*(c)$ is clearly piece-wise constant) with $dz/dc = x^*(c)$. This gradient $x^*(c)$ is simply the output of the LP and can be computed by any tailored method (not even necessarily by an LP e.g. by quicksort, Dijkstra, etc.) without requiring *any additional computation* on the backward pass.

The situation with $dz/db$ and $dz/dA$ is similar (via duality). This is all known for over 40 years ([M1, M2, M3, M4])

In the AUC LP formulation (eq 2), the resulting AUC score basically the negative optimal value of the objective, so **these classical results apply**.

2) Taking derivatives of the **optimal solution**  $x^*$ w.r.t the LP parameters $c$, $b$, $A$

In case of $dx^*/db$ and $dx^*/dA$ there are again simple closed-form gradients. One can either refer to eq (6) in (Amos, 2017) 
 where closed-form gradients of more general QPs computed, or to an argument the authors make themselves in Sec 3.2. $x^*$ is a solution to the linear system given by the set of active constraints, and gradients of matrix inversion are easy to compute. These are also the gradients given by CVXPy -- even though admittedly their LP solver is currently very slow.

Most interesting is the case of $dx^*/dc$ as the true gradient is zero (dependence is piecewise constant) but this zero gradient is useless for optimization. Constructing meaningful gradient proxies is precisely the point addressed by (Berthet, 2020) but also earlier by [M5, M6, M7]. This is an ongoing research direction with competing methods.

3) The LP solver is the last layer in the neural net and the ground truth solution $x^*_{\textrm{true}}$ is available for supervision.

In this special case, which is actually the most common one in practice -- and also occurs in this paper, the situation is a lot easier. In fact, most works have focused on this scenario [M8, M9, (Song 2016)]. Also (Berthet, 2020) addresses it with the YF loss. The takeaway is that there are good loss functions for which a) the gradient can be computed only from the forward pass information b) robustness of the solutions can be enforced (e.g. by noise in (Berthet, 2020) or by a margin in M8).

In summary, there are suitable existing methods for efficient and often blackbox (not tied to a specific solver) gradient computation can be achieved. I find it imperative that the authors acknowledge this and compare to some of them.

### Inaccurate claims and omissions in related work

Claims about (Berthet, 2020)
- "approximate gradient" - The gradient is approximate for good reason (see above)
- "necessary to solve ~n perturbed LPs" - This is not true for the YF loss that can be applied at the end of the network (see above). There, in fact, only forward pass information is enough to obtain a gradient. Also, in the more general case (middle of the network) there are methods [M6] that need only one additional call to LP solver. 
- "using off-the-shelf solvers ... can severely slow down" - a) SOTA LP solvers are extremely fast, b) if there is a faster "solver" for a concrete LP, such as quicksort for the LP formulation of ranking, (Berthet, 2020) allows using it. In summary, (Berthet, 2020 and M5) allow the usage of the fastest possible algorithm and by definition cannot slow down runtime.

Missing recent related work that also addresses nondecomposable metrics:
[M10, M11, M12, M13]

### Insufficient experimental evaluation

As far as I am concerned, the ideal experimental section for this paper would look like this:

a) more comparisons against recent literature on non-decomposable metrics (one recent baseline on one dataset is simply not enough)
b) Identifying that the source of the performance is the selected method for solving LPs -- by comparing to alternatives described above. In that case,  additionally producing qualitative explanation on why this is happening.
c) Find a fair way to report runtime and scaling with increasing instance sizes. Also comparing it to alternative approaches.

# Summary

My intention is not to dismiss the method, it seems to work reasonably well and has a formal backing, after all. But if this paper is to be of long-term value to the community, I have to insist on a major revision for the reasons described above.

### References

[M1] Gal, 1975, Rim Multiparametric Linear Programming

[M2] Freund, 1985, Postoptimal analysis of a linear program under simultaneous changes in matrix coefficients

[M3] De Wolf, 2000, Generalized derivatives of the optimal value of a linear program with respect to matrix coefficients

[M4] Gao, 2020, Differentiable Combinatorial Losses through Generalized Gradients of Linear Programs

[M5] Vlastelica, 2020, Differentiation of Blackbox Combinatorial Solvers

[M6] Ferber, 2020, MIPaaL: Mixed integer program as a layer

[M7] Wilder, 2019,  Melding the data-decisions pipeline: Decision-focused learning for combinatorial optimization

[M8] Tsochantaridis, 2005, Large Margin Methods for Structured and Interdependent Output Variables

[M9] Elmachtoub, 2017, Smart "predict then optimize"

[M10] Rolinek, 2020, Optimizing Rank-based Metrics with Blackbox Differentiation

[M11] Brown, 2020, Smooth-AP: Smoothing the Path Towards Large-Scale Image Retrieval

[M12] Fathony, 2020, AP-Perf: Incorporating Generic Performance Metrics in Differentiable Learning

[M13] Khim, 2020, Multiclass Classification via Class-Weighted Nearest Neighbors


review_title: The method has merit but doesn't indicate it will succeed where so many others failed

final_score: rating: 6: Marginally above acceptance threshold
review_content: This paper shows how some nondecomposable functions can be
interpreted as solving combinatorial optimization problems
that can be relaxed to linear programs.
As this paper brings some new insights and directions here
I recommend for a weak accept, although some of the experimental
settings and baselines feel incomplete (more details below).

# Strengths
Optimizing these performance metrics is useful for settings
where these are more important than optimizing for the accuracy,
and to the best of my knowledge these relaxations and ablations
meaningfully contribute to this direction.

The AUC experiments in Table 1 outperform [Liu 2019],
which also optimizes for the AUC.

The derivative computation can be computationally expensive
and ablating the impact of unrolling is interesting to
better-understand tradeoffs.

# Weaknesses
The biggest weakness I see is that the F-score experiment in
Table 3 has no baseline that also directly optimizes the F-score,
such as in [Fathony 2020] and other methods cited in the paper,
and the non-negative matrix factorization experiments are
lacking quantitative results.

This paper relies on relaxing the integer domain to be continuous
and it's not clear how much this approximation impacts the derivatives.

Some of the design choices seem arbitrary and unjustified, such as
focusing on the fast exterior penalty optimization at the start
of Section 3 and then doing the forward pass with Newton's algorithm
on the unconstrained problem from [Mangasarian 2004] in Section 3.1
to solve the LP.

# Other comments and questions
One recent related work is omitted: [Fathony 2020].

Is there any intuition behind why this approach sometimes outperforms
[Liu 2019] in Table 1, but sometimes doesn't? My interpretation without
this is that both of these approaches are approximations and it's hard
to know a-priori which will perform better.

Remark 2 says that in previous work, the LP constraints do not
depend on the data, but the formulations of [Amos 2017, Agrawal 2019]
allow constraints that depend on the data.

# References
Fathony, R. & Kolter, Z.. (2020). AP-Perf: Incorporating Generic
Performance Metrics in Differentiable Learning. Proceedings of the
Twenty Third International Conference on Artificial Intelligence
and Statistics, in PMLR 108:4130-4140
review_title: Interesting ideas, experiments seem incomplete

final_score: rating: 3: Clear rejection
review_content: Summary
-------

The paper makes the observation that various non-decomposable losses in machine learning can be rewritten as linear programs, whose constraints depends on the model output. This is the case for AUC, multi-class AUC, F-score, and to some extend NMF.

The authors review these losses, and recall how they may be rewritten as LPs. The LP formulation as known for AUC and NMF, but as far as the reviewer understand, they are new for multi-class AUC and F-score.

Then, the authors propose to directly backpropagate through the LP resolution to minimize non-decomposable losses, applied on top of deep architectures. For this, they propose to solve an approximate solution to the LP problem (a quadratic penalization of the constraint violations) using a modified Newton method. They propose either to backpropagate by unrolling the Newton steps, or by using the computed minimizer directly.

Review
------

The endeavor of writing non-decomposable losses as LPs, to see these losses as pluggable LP-layer in deep architecture is interesting, albeit not original.

Using a penalized approximation of the LP to be able to solve them efficiently using a Newton method is also interesting.

The experiment section shows that it is indeed beneficial to directly optimize over a certain decomposable loss when we measure performance in term of this loss: in particular, it outperform using a simple logistic loss. This was completely expected, but it is good to verify it experimentally.

On the other hand, the manuscript suffer from many unclear parts, and from a theoretical analysis that is not polished enough. In particular:

    - Phi is not introduced beforehand p. 4, and the F-score part is very hard to understand.

    - the NMF section is very unclear, in particular as the authors use vague terms in their construction, such as "zero padding ensures a sxs matrix". I do not understand the role of tilde p in (6).

    - Lemma 1 is not stated properly, as there is no f in equation (7). The authors state that "each y has a neighborhood in which the Hessian is quadratic", which does not mean anything. The proof sketch of Theorem 2 is very vague, in particular when the authors state that "the possible choice of Hessian is finite".

    - I do not understand whether rho is chosen at every iteration, and what is its importance.

I have trouble understanding why the authors went to such lengths in their
theoretical analysis. They modify a LP by making it a "smooth almost everywhere"
problem, which can then be solved using any methods, and backpropagated through
using either unrolling, or the computed minimizer (by virtue of Danskin
theorem), or the implicit function theorem. There is therefore not need to backpropagate throught tilde A^{-1} b.

The fact the the problem is only smooth almost everywhere may be a problem,
which is not addressed by using a Newton method. It implies that the gradient
becomes a subgradient, and may hinder optimization performance. Remark 4
dismisses this problem as unimportant, yet it is, as local convergence rates for
non-convex gradient descent requires smoothness.

Relating to experiments:

    - The reported performance does not show std errors across splits, which makes it impossible to compare in between similar methods (PPD-SG, PPD-AdaGrad and Ours). It appears that all three methods are within statistical variations.

    - NMF is a long studied problem, with many powerful methods to handle large inputs. I do not understand the choice of using the input of a deep learning network for the experiment. As it it, the experiment proposed in this manuscript is not polished enough to be valuable.
review_title: Interesting ideas but not polished enough

Meta-review: This paper shows that various discrete loss functions can be formulated as an LP. It proposes to relax the constraint Ax = b, x >= 0 using a soft constraint and following Mangasarian, proposes to solve the relaxed problem using Newton's method. Backpropagation through these iterations is further proposed. The main motivation is that this results in a GPU-friendly implementation.

I think the proposed approach is novel. However, as pointed out by reviewers, the current writing lacks clarity and the experiments are quite weak. There is now a wealth of methods for differentiating through an LP using implicit differentiation, smoothing (which the present paper is a form of, see below) and perturbations. It is important to compare to these methods. The paper also ignores a large literature on convex surrogates for ranking metrics.

I recommend the authors to strengthen the writing and experiments, and to resubmit to a top-conference.

Additional comments by the AC
-------------------------------------------

As the sentences "Hence, solving such LPs using off-the-shelf solvers may slow down the training process" or "Often, this would involve running the solver on the CPU, which introduces overhead" indicate, the authors seem to imply that LPs need to be solved in canonical LP form, min_x <c,x> s.t. Ax <= b, x >=0, using an off-the-shelf LP solver. This is not how many LPs are solved in practice. For every loss, there will always be an ad-hoc solver for the corresponding LP. For instance, the Hungarian algorithm for the Birkhoff polytope.

The paper is missing an important reference: SparseMAP (https://arxiv.org/abs/1802.04223). In this paper, the authors add regularization to the primal LP and use Frank-Wolfe or active set methods to solve the problem.

Equation (6) corresponds to relaxing the hard constraint Ax=b, x>=0 with a soft one. This approach is in a sense opposite to SparseMAP. Indeed, relaxing the constraints in the primal is equivalent to adding regularization in the dual LP (see, e.g., https://papers.nips.cc/paper/2012/hash/bad5f33780c42f2588878a9d07405083-Abstract.html).
Speaking of (6), the authors should clarify that it's a convex objective.

In section 2, the authors review a number of losses which can be written as an LP. It would be better to explicitly state what are A, b and c for each loss (or g, h, E, F, p, B, G, q).

The matrix A could potentially be huge, depending on the LP. Do you need to materialize it in memory in practice? This would limit the approach to relatively small LPs.
Decision: Reject