Differentiable Optimization of Generalized Nondecomposable Functions using Linear Programs
Authors: Zihang Meng
Lopamudra Mukherjee
Yichao Wu
Vikas Singh
Sathya N. Ravi
Venue: NeurIPS 2021 Poster (2021)
Keywords: differentiable
non-decomposable objectives
linear programming
Newton's method

Abstract: We propose a framework which makes it feasible to directly train deep neural networks with respect to popular families of task-specific non-decomposable performance measures such as AUC, multi-class AUC, $F$-measure and others. A common feature of the optimization model that emerges from these tasks is that it involves solving a Linear Programs (LP) during training where representations learned by upstream layers characterize the constraints or the feasible set. The constraint matrix is not only large but the constraints are also modified at each iteration. We show how adopting a set of ingenious ideas proposed by Mangasarian for 1-norm SVMs -- which advocates for solving LPs with a generalized Newton method -- provides a simple and effective solution that can be run on the GPU. In particular, this strategy needs little unrolling, which makes it more efficient during backward pass. Further, even when the constraint matrix is too large to fit on the GPU memory (say large minibatch settings), we show that running the Newton method in a lower dimensional space yields accurate gradients for training, by utilizing a statistical concept called {\em sufficient}  dimension reduction. While a number of specialized algorithms have been proposed for the models that we describe here, our module turns out to be applicable without any  specific adjustments or relaxations. We describe each use case, study its properties and demonstrate the efficacy of the approach over alternatives which use surrogate lower bounds and often, specialized optimization schemes. Frequently, we achieve superior computational behavior and performance improvements on common datasets used in the literature. 

Differentiable Optimization of Generalized Nondecomposable Functions using Linear Programs
Zihang Meng', Lopamudra Mukherjee', Yichao Wu', Vikas Singh', Sathya N. Ravi
'University of Wisconsin-Madison
University of Wisconsin-Whinn Whitewater
Uniivesiity of Illinois at Chicago
zihangm&cs wisc. edu, mukherjl@uee edu, yichaowu@uic. edu vsingh@biostat. wisc. edu, sathyaQuic.ed
Abstract
We propose a framework which makes it feasible to directly train deep neural networks with respect popular families of task-specific non-decomposable per- formance measures such as AUC, multi-class AUC, F F-measure and others. A feature of the optimization model that emerges from these tasks is that involves solving a Linear Programs (LP) during training where representations learned by upstream layers characterize the constraints or the feasible set. The constraint ma- trix is not only large but the constraints are also modified at each iteration. We show how adopting set of ingenious ideas proposed by Mangasarian for 1-norm SVMs - which advocates for solving LPs with a generalized Newton method provides a simple and effective solution that can be run on the GPU. In partieu- lar, this strategy needs little unrolling, which makes it more efficient during the backward pass. Further, even when the constraint matrix too large to on the GPU memory (say large minibatch settings), we show that running the Newton method in a lower dimensional space yields accurate gradients for training, by utilizing statistical concept called sufficient dimension reduction. While num- ber of specialized algorithms have been proposed for the models that we describe here, module turns out be applicable without any specific adjustments relaxations. We describe each use case, study its properties and demonstrate the efficacy of the approach often, specialized optimization schemes. Frequently, we achieve superior compu- tational behavior and performance improvements common datasets used in the literature.
alternatives which surrogate lower bounds and
Introduction
Commonly used losses such as cross-entropy used in deep neural network (DNN) models can be expressed
the per-sample losses incurred by the current estimate of the model. This allows the direct use of mature optimization routines, and is sufficient for many use cases. But in applications ranging from ranking/retrieval class imbalanced learning. the most suitable losses for the task do not admit a "decompose over samples" form. Examples include Area under the ROC curve (AUC), multi-class variants of AUC, F-score, Precision fixed recall (P@R) and others. Optimizing such measures in scalable manner can pose challenges even in the shallow setting.
For AUC maximization, Lu all [2018], Natole al all [20I]] the so-called ERM framework. These ideas have been incor- porated within deep neural network models and solved using SGD type schemes in Liu et all [ Such results on stochastic and online data models have also been explored in Ataman et all [200]]
know that convex surrogate losses can be used in linear model
Cortes and Mohri [20K2]], Gao all 203 There also available strategies for measures other
35th Conference on Neural Information Processing Systems (NcurIPS 2021), virtual.

---

than the AUC: Nan et all 2012 Dembezynski et al. |0000|| give exact algorithms for optimizing F-score and Eban et all 2017 Raviet all |000|] proposes scalable methods for non-decomposable
objectives which utilizes Lagrange multipliers to construct the proxy objectives. The authors in Moe hapatra et al. [20]] discuss using a function that upper bounds (structured) hinge-loss to optimize average precision. Recently, Fathony and Kofter [2020] presented an adversarial prediction formula- tion for such nondecomposable measures, and showed that it is indeed possible to incorporate such
measures within differentiable pipelines.
Our work utilizes the simple observation that a number of these denoopoooeseblee objectives can be expressed in the form of an integer program that can be relaxed to linear program (LP). Our approach based on the premise that tackling the LP form of the non-decomposable objective as a module within the DNN, one which permits forward and reverse mode differentiation and can utilize in-built support for specialized GPU hardware in modern libraries such as PyTorch, is desirable. First, as long as suitable IP formulation for an objective is available, the module may be directly used. Second, based on which scheme used to solve the L.,, one may be able to provide guarantees for the non-decomposable objective based on simple calculations (e.g., number of constraints, primal-dual gap). The current tools do not entirely address all these requirements.
A characteristic of the LPs that arise from the nondecomposable losses mentioned above is that the constraints (including the mini- of samples themselves) are modified at each iteration as a function of the updates to the representations of the data in the upstream layers. In Section E, we provide LP formulations of widely used nondecomposable terms. which fall squarely within the ca- pabilities of our solver. In Section EL we show that the modified Newton's is algorithm in Mangasarian [2(н4]] can be used for deep neural network (DNN) training in an end-to-end manner without requir- ing external solvers, where support for GPUs currently remains limited. Specifically, by exploiting self-concordance of the objective, we show that the algorithm can converge globally without line search. We then analyze the gradient properties of our approach, and some modifications to improve stability during backpropagation. Our experiments in Section 5 show that this scheme based on Mangasarian's parametric exterior penalty formulation of the primal LP is a computationally effec- tive and scalable strategy to solve LPs with a large number of constraints. On the practical side, we provide two ways to deal with the scaling issue when the constraint matrix is large. On the one hand, we show that sufficient dimension reduction can be used in our solver to solve the problem in a lower dimension space. On the other hand, when the matrix is sparse, with our new sparse implementa- tion, we show that we can train Resnet- 18 with 10x mini-batch size (memory savings) on a 2080TI Nvidia GPU. Our code is available, see Fig II for overview of our solver for differentiating many popular nondecomposable objectives.
2 Related Works
Differentiable optimization of nondecomposable objectives. One closely related result to ours is au [20]]]] which explored optimizing a surrogate loss of AUC using SGD type methods that made the stochastic AUC optimization more practical for deep neural networks. Compared with Lt [201%] our work enables optimizing many more types of nondecomposable objectives for deep neural networks, and relies on the LP reformulation instead of a surrogate loss. In Fathony and Kolted [200]]] (the expected values of) such metrics are approximated by LPs defined by pre- dictor and adversary marginal distributions (represented as square matrices). The ADMM solver in Fathony and Kolter [2020], we will see, inherits some drawbacks of ADMMs including higher memory footprint and slower convergence. Another body of work the one involving the use of blackbox solvers Pogančíć et al. [2019], Berthet et all [2020]] which can be adapted to solve the nondccomposable objectives (c.g., reformulating as LPs). For example, one idea is to use appropri- ate (infimal or gaussian) convolution to construct approximations of the gradients through the LP. Song et al. [2016]] proposes a using a task loss to perturb the loss and is similar in spirit to blackbox solvers - they both solve sequence of perturbed argmax/argmin problems first, and then use care- fully designed procedures for the backward gradient that often require at least one more solve of the optimization problem. We will discuss these properties later in the paper, and in our experiments.
Differentiable LP solver. In principle, of course, backpropagating through convex optimization model (and in particular, LPs) is quite possible. For LPss, we can take derivatives of the optimal value (or the optimal solution) of the model with respect to the LP parameters, and this can be ac- complished by calling powerful external solver. Often, this would involve the overhead of running
2

---

Non-decomposable metric
Input: c, A, for the primal LP initialize the starting point
z
(optional) Construct random projection matrix S.bmm((A
for ( K do
Linear Program
* diag-torch.diagg emmee(A.bmm(j)))) bmmeet)..uueeeee(2-bb)
minc' s. b,
* P A. 1tt.sppossse222..m.mmm.m (aiia).bmm((A) rho" Identity
Q (aaasppooe(122..mmmeeeuuuuu (Amm/)))mm))) b.unsqueeze(2]]
+ epsilon c.unsqueeze(2)
* 7.
d Morch.iiverss()).bmmm()
Our Newton solver
8.
2=2+0
= 1/epsillon (emm(() b.umsqueeze(22)
10. v_gr__rr 3r_0- 0 sooee../
11. AJ Af: v_er O, b_j b(s, v_er_o]
*
12. z torch.solve(b A_j
Differentiable estimate of the metric
13. Output: z
* We provide sparse support for these operations in Pytorch
Figure I: Overview how to compute differentiable non-decomposable metric and code example of our LP solver. We provide sparse support for operations which are not supported in official Pytorch library (colored operations in the figure).
the solver on the CPU. Solvers within CVXPY, are effective but due to their general- nature, rely on interior point methods. OptNet Amos and Koltei [2M] is quite efficient but designed for quadratic programs (QP): the theoretical results and its efficiency depends on factorizing a matrix in the quadratic term in the objective (which is zero/non-invertibl for LPs). The primal-dual properties and implicit differentiation for QPs do not easily translate to LPs due to the polyhedral geometry in LPs. The ideas in Meng et all [M00]] only applicable when the number of constraints is ap- proximately equal to the number of variables an invalid assumption for the models that we study here.
3 Nondecomposable Functions and corresponding LP models
We first present standard LP form and then reparameterize several generalized nondecomposable objectives in this way, summarized in a table in the appendix. We start with the binary AUC, extend to multi-class AUC, and then later, discuss ratio objective, F-score. The appendix also includes a discussion of other objectives that are amenable to our method.
3.1 Notations and Generalized LP formulation
Notations. We use the following notations:
(i) re number of samples used training.
(ii) X E R. xdix. the explanatory features fed to classifier (e.g., parameterized by w);
(iii) f(x;) (or f())): a score function for the classifier where x; E XX;
(iv) Y E [0,1): 1]: target label and Ý E {0, 1}: predicted label for binary classification, both in R";
(v) A B: Kronecker product of matrices A and B.
(vi) I,: Identity matrix of size and is the indicator function. (vii) B (and B )x) gives the k-th row (and k kt) column of B.
LP formulation. We consider a general linear program (LP) that contains nonnegative variables as
well as inequality and equality constraints. The form of the IP is given as
max 9² u h subject to Eü + Fi S P.
Bü Gi =
ú. T 0
We write it more succinetly
E B -B 7" F
Variable = [ū ū]
Coefficient = [-9 - h]; Constraints A =
Constants b = Ip - =
G
-G
The corresponding primal LP can be written as, min, cT subject Az < b, 0.
3.2
Maximizing AUC
The Area under the ROC Curve (AUC) calculates the probability that classifier f(-) will rank randomly chosen positive sample higher than randomly chosen negative sample. AUC varies

---

between 0 and 1, where represents all positives being ranked above the negatives. AUC may be estimated using the Wilcoxon- Manun- Whinney (WMW) Statistic Hanley and McNe1 [182]. as
Definition 3.1 (AUC). Let n be the number of samples. Let X+ (and X_ resp.) be the set of positive (and negative resp.) samples such that [+1 X where | is the cardinality of the set. Then, AUC is given as [ |X
El {(=))>((;))) (IX+I for x; : : (1,-.", ,n).
Here, we follow Ataman al 2006 to calculate the AUC based on the WMW statistic as follows.
1+11X-1
min Σ Σ 2j s.t. f(x) 6- 2ig where x, E X,, E X_: Bg 20 2 0, (1)
where is given constant. Problem (lI) computes AUC indirectly by minimizing the number of pairs (one each from the positive and negative classes) where the positive sample is not ranked higher than the negative sample: so, the number of zero entries in 2 equals the number of pairs where this condition is not true. For a given 2, we have that,
AUC (n - 1= (1x+ (x-1) (n ΣΣ reluu( -ii + +)) (1X+) (X++|
If Ziy is O, then E relu(O, -zij - <) equals 1. Otherwise 2ij > 0, it follows from the first constraint in (L), that Zij 2 e, so (0 - -ij + e) equals O. Observe that in (I), the number of constraints is X-| which is O (n²).
3.3 Maximizing Multi-class AUC
extension of AUC to the multi-class setting, AUC,, is defined Kleiman and Page [2014]] The , objective optimizes an indicator matrix calculated on the orientation function, Oz,j defined as,
Definition 3.2 (Orientation Function; Kleiman and Page (2019]). Assume we have K classes {yr.... , yk }- Let [3ri -) E RK (extension of /()) to the multi-class setting) indicate the model's prediction on 2; for each of the K classes (class-specific probability). Let xt provide the index of x;'s true class label. Let P E Rlxk be a partition matrix where PI,K is the cost of classifying a sample class l when it should be V. Define,
Vak Pk.- PK.- and V Vxtz; E RRK OLd -V=;; Vz;) -)) ( f( -)))
The LP formulation of AUC,, fully characterized by P. We can set P(k, k) 0 Vk and 1 for all other entries. We can also define a P with arbitrary entries or formulate AUC in a one-vs-all setting (denoted AUC Here, for presentation, use the simplified 0/1 partition matrix P. Let f(i,j) = f(z,, x(z),x;) + 2(z), f(x,, xf). Then the LP formulation is given by,
AUchin
min Ziy
s.t. f 2e- - Zags Vi,ji < x3 Zij
24
(2)
i=
j
where dip V2g Vag- Problem can seen as an extension of our binary AUC model, where Zij is the ranking between pair of points defined for multiple classes.
3.4 Maximizing F-score
The F-score (or F-measure) representative of objectives expressed ratios of some combi- nation of True positives (TP), False positives (FP), True negatives (TN) and False negatives (FN). We the result in Dembezynski al] [ express the F-score in the ratio form and further relax it into the LP form. The detailed LP formulation of F-score and other ratio functions is in the appendix.

---

4 Backpropagation via Fast Exterior Penalty Optimization
Unlike traditional feedforward networks, where the output of each layer is a relatively simple (albeit non-linear) function of the previous layer, a LP layer must solve constrained problem, therefore implementing scalable/efficient backpropagation schemes that minimizes overhead requires more care and is active topic of research. This problem is, of course, not unique LPs and manifests in differentiable sorting Mena et aD [2018] and formulating quadratic or cone programs Amos et all
[2017] One may unroll gradient descent steps Amos et all [2017], Goodfellow all [2013]] Metzi
all
2 or use projections Zeng et al. [2019]] Recently Agrawal et al. [2019]] introduced a
package for differentiable constrained convex programming. which includes LPs as a special case.
For LPs, Meng et al. [2020] presents an unrolled scheme and [Blondel cf all [2020] shows that we can differentiate through LP formulations of sorting/ranking exactly by using smooth approximations of projection steps. Berthet et all [202]] describes an interesting approach where one computes approximate gradients through ranking/shortest path problems by stochastic perturbation techniques.
Remark 1. Some previous works Zeng et al [2079] have considered LPs where the constraints are deterministic (for fixed input dimension), i.e., do not depend on the data X, which is different from the LPs in Sections 1.4
Note that perturbation techniques in Berther et all Fenchel Young losses in Berther et all [2020] is attractive because there is no need to compute the Jacobian. Implemeenationn-iin and output of the forward pass. But the gradient expressions of the losses involves an expectation and hence may require multiple calls LP solver order approximate the expectation. Paral- lelization and warm starts were shown to alleviate this dependency to some extent by sampling in parallel.
2020 are applicable our LPs well. The
one could think of the backward pass as a function given the input
Rationale for our approach. Consider a LP with a large m number of constraints in fixed dimen- sions (n < m). This assumption holds in all formulations in Section B. This is because assume that the architecture is fixed whereas minibatch size depends on the complexity of the task (stable gradient or when noise in gradient is high). Hence, solving such LPs using off-the-shelf solvers in Berther et all [2020]] in the general case, could slow down training. The strategy in [Agrawal el al.
[2019]] does offer benefits over Amos and Koftei [201]] for sparse QPs. Our strategy is to run Man- gasarian's 's Newton's 's method on an exterior penalty function of the LP. There are two advantages: (i) during forward pass, quadratic local convergence of Newton's 's method indicates that unrolling the method may be reasonable; and further (ii) based on the relationship between dual and primal variables, and the exactness of the exterior penalty we can show that backward pass is independent of m. We will discuss both results and some modifications to deal with discontinuous Hessian (and its inverse) that is required for Newton's 's method, A similar approach adopted in Amos and Kolter [007]] where Primal-Dual Interior Point methods with implicit differentiation is used for differen- tiation purposes. But the exterior penalty in (B) satisfies a nice property: primal and dual solutions are related by closed form expression which can be exploited for efficient backpropagation.
4.1 Forward Pass using Newton's Algorithm on a Sufficiently Reduced Space
Fast automatic (forward or reverse mode) differentiation requires performing the forward pass effi- ciently. In our setting, we seek to solve and backpropagate through an LP. We will focus on reverse mode differentiation since it is the most suitable for DNN training.
Given primal LP, for a fixed accuracy > 0. Mangasarian [2004]] solves an unconstrained problem,
min g(v) = IIa b)]l + +eoTy. 9
where (-)) max(- 0) represents the elementwise relu function. modified Newton's 's method can be used to solve (E) that performs the following iterations:
y= y + Ad
(4)
where
d= d= = (Vig + pl) -V))
(5)
5

---

In large scale settings of A, b, such Newton methods are known to perform empirically better than gradient descent Mangasaraa [2006), Keerth all [2007]] We will evaluate if this holds for our purposes shortly.
Why is Newton's method applicable for minibatches? In general, the convergence of Newton's method depends strongly on initialization (even for convex problems), i... we can only provide local convergence results. However, this is not the case for our problems since in our examples, either the level sets are bounded from below; or the feasible set is compact, as noted in Mangasarian [2004]] There are two reasons why the above result, by itself, is insufficient for our purposes: (i) it assumes that we can perform line search to satisfy Armijo condition; (ii) even with line search, the result does not provide a rate of convergence. In DNN training, such line search based convergence results can be very expensive. The key difficulty is handling the discontinuity in the Hessian. As a remedy, we use self concordance of (G) to guarantee global convergence of (EI iterations for the exterior penalty formulation in (E)) To do so, we first show result (proof in appendix) that characterizes the discrepancy between the actual Hessian of (G) and the modified one in (eI when the (feature) matrix A is randomly distributed.
Lemma 1, Assume that A is a random matrix, and fix arbitrary E RR. Then with probability one, g in (E) can be approximated by a quadratic function (given by H, Vg(y)) over a sufficiently small neighborhood of y.
Lemma I states that with probability one, each y has a neighborhood in which the Hes- sian is constant. In addition, the modified Hessian is nonsingular all points (in particular the optimal y²) )) and so we can then show the following global convergence result.
Intuitively,
Theorem 2. Assume that the primal LP has unique optimal solution, and that the level set {2 A= < b, c² z S a} is bounded for all a (for dual feasibility). Then short step (no line search) Newton's method converges globally at a linear rate with local quadratic convergence.
Proof. First, note that the objective function is piecewise quadratic since it is a sum of piecewise quadratic functions defined by coordinatewise relu function o. In particular, g is self concordant since its third derivative is zero almost everywhere. Now setting p < we see that approxi- mate solution of the problem with the modified Hessian is also an approximate solution to equation 3. Morcover, since the possible values of A is finite, the local norm (also known as Newton's decrement) Vg(y)" ( is finite. Hence, we can choose p > 0 so that there is a descent direction d, that is, there exists a step size À > 0 such that > Vgx()) d < O. Finally, we use Theorem 4.1.12 in Nesterov
M to claim the desired result.
The assumptions in Theorem D are standard: 1. unigueness easily be satisfied by randomly perturbing the cost vector; 2. in most of our formulations, we explicitly have bound constraints on the decision variables, hence level sets are bounded.
Remark 2. Convergence in Thm. 2 is guaranteed under standard constraint qualification assump- tions. Linear Independent Constraint Qualification (LICQ) is satisfied for AUC, and Multi-class AUC formulations in $E But the F-score formulation does not satisfy LICQ, hence we need safe- guarding principles in the initial iterations (until iterates get close to the optimal solution).
Our analysis of the Newton's 's method for LP so far indicate that we may be able to use constant step size X (avoid linesearch) to obtain fast convergence provided that we are able to choose p sufficiently small. For our purposes, we assume À to be a hyperparameter and can be tuned by cross validation.
Sketching d using Sufficient Dimension Reduction (SDR), For training the backbone network, we have to compute d in (g) using A (and b) which could be very large within each training iteration. But each minibatch corresponds to an LP instantiation in (B), so it may suffice to compute an approximate d in each Newton's 's iteration. To approximate d, we use sufficient dimension reduction in which a lower dimensional LP obtained by projecting A solved /hang et al. [2020]] Kim et all [2020]. That is, instead of the inverse of H, we will compute a lower dimensional sketch of H by using SA (and
Sb) instead of A (and b) for some sampling matrix S and solve problem (E). During each iteration,
the metries are computed on the current minibatch as is done in Fathony and Kolter [2020]. Thus (without SDR) the memory cost is directly proportional to minibatch size viz., number of samples and feature dimensions. The advantage of using SDR (as opposed to naive sketching) is that the lower dimensional space can also be chosen using data driven cross validation or other techniques

---

Kim et al [2016]] making it ideal for training purposes. In essence, the size of minibatch does not matter- as long as the minibatch can be sufficiently reduced, our solver is directly applicable. especially for low resource, memory constrained settings. For a fixed (low) dimension parameter, our sketched is,
a (IIrelu( Ay b)1)) ~ (SA)*S relu(sign ( b)), d H & where & δy
(6)
H ~ (diag(S relu(sign(Au) b)) S relu(sign b])) SS)). SAA
(7)
It is easy to see that the approximate update can be seen as equivalent to Iterative Hessian Sketch algorithm which has geometric convergence rate Pilanci and Wannwnght [2016].
4.2 Backward Pass using Optimal Dual Variables Aided by Unrolling
The advantage of optimizing the exterior penalty in (G) is that given iterate yt, accuracy E, can get the optimal dual solution ot by simple thresholding, i.e., 1/- = o - 6)). By complementarity slackness, nonzero coordinates of o2 specify the set of active constraints in A= S b. So, given approximate Ye such that ( ( VV((v) S E, to get the primal solution s*, solve the "active" linear system given by Ab, where A denotes the active rows of A and the corresponding subvector b. So, backpropagation through the layer reduces to computing derivatives of 8 (simple via automatic differentiation).. The appendix gives systematic way of choosing
How to backpropagate through unrolled iterations? We assume that the chain rule is applicable up to this LP layer and is ØL 0z öz 04 (for one of the parameters A), and note that is possible to find 0= AL (either directly or using a chain rule). Therefore we focus our attention on 84: which involves it the LP layer. Indeed, unrolling each iteration in (eI) is equivalent
"sublayer". So, in order to backpropagate we have to show the partial derivatives of each operation or step wrt to the LP parameters A, b, and c.
Our goal is to calculate ad 0д where d QQ Q H and w Vg(y). We can use the product rule to arrive at: Od - (w TeeTQ-1 @ (Q-1)aQ + Q-1 To see this, note that we have used the chain rule to differentiate through the inverse in the first term. The second term is easy to compute aQ similar to the computation of Hessian. For each of these terms we eventually have to compute Svar or the Ziar where var E fc, b} which can also be done by another application of chain rule. Please see appendix for empirical verification of unrolled gradient and the one provided by Á
Before proceeding, we should note an issue that comes up when differentiating each step of the unrolled algorithm because the Hessian is piecewise linear (constant) as function of the input to that particular layer. Here, some possible numerical approximations are needed, as we describe below.
aQ is nondifferentiable due to the presence of Remark 3. Note that the diagonal matrix term in 9 the step function. However, the step function is a piecewise constant function, and hence has zero derivative almost surely, that is, in any bounded set S, E S, if a ball (of radius >> 0,) Br(z) C S, then the Lebesgue measure of the set of nondifferentiable points on S is zero. Please see appendix for a formal justification where we show this by approximating the step function using a sequence of logistic functions with increasing slope parameter at the origin.
Therefore, in this setting, Remark & provides a way to compute an approximate sub sub-gradies gradient when using Newtons method based LP layers. The function is a piece-wise quadratic function and differ- entiable everywhere, and the inverse of the Hessian acts as a preconditioner.
Summary. Our forward pass involved three steps: (1) finite steps of Newton's method using which we (2) computed the dual variable by thresholding operation, and (3) finally, get the primal solution, these dual variables are first used to identify the active constraints followed by solving a linear system. To backpropagate through these three steps, we must differentiate through each layer of our procedure including 11:6: this is independent of whether we use unrolling or Danskin's theorem. For instance, using Danskin's 's theorem here would involve differentiating through the fixed point of the Newton's 's iterations similar to (regularized) gradient descent iterations iMAML Rajeswaran et all [201%].
7

---

Experiments
In this section, we conduct experiments on commonly used benchmarks to show that our frame- work can be used to optimize multiple different objectives within deep neural networks and lead to performance gain. We start with binary AUC optimization, and then extend to multi class AUC opti- mization and F-score optimization. Nonnegative matrix factorization discussed in the appendix.
Optimizing Binary AUC
We follow the Lm et all [2019 to conduct experiments on optimizing AUC score directly with deep neural networks. The baseline algorithms we compare with for binary AUC are cross-entropy loss and two algorithms (PPD-SG and PPD-AdaGrad) from al [2019].
Datasets: Cat&Dog. CIFARIO, CIFARI00, and STL10 (See appendix for dataset details). We follow Lu all [201] to use 19k/Ik, 45k/5k, 45k/5k, 4k/lk training/validatonn split on Cat&Dog. CIFARIO, CIFAR STL10 respectively.
Experimental setting. We
Table 1: Binary AUC optimization results on four benchmark datasets.
follow Liu et all [2019]
construct an imbalanced bi-
AUC(%)
Cat&Dog
CIFAR10
nary classification task by
Positive Ratio
91%
83%
71%
50%
91%
83%
71%
50%
using half of the classes
Cross-Entropy
67.6
74.6
85.1
87.4
65.2
73.3
78.1
83.7
PPD-SG
79.1
81.5
85.5
87.1
69.8
73.9
79.1
82.6
positive class and an- other half as negative class, and dropping samples from negative class by a certain ratio, which is reflected by the positive ratio (ratio of majority class the minor- ity class) in Table M. Con- structing imbalanced datasets by dropping samples was also used in Cui all [2019]] to construct long tailed CIFAR-LT. We use the same random seed, learning rate and total number of iterations in all of our experiments including multi class AUC and F-score experiments. See appendix for model architecture, learning rate, etc.
PPD-AdaGrad
77.3
80.6
83.7
86.3
69.7
74.1
78.4
83.1
Ours
78.6
81.3
85.6
87.8
72.5
74.4
78.3
82.7
AUC(%)
CIFAR100
STL10
Positive Ratio
91%
83%
71%
50%
91%
83%
71%
50%
Cross-Entrope
57.8
58.4
62.2
66.3
63.5
67.1
72.7
80.8
PPD-SG
56.5
58.9
61.6
65.2
70.7
71.6
75.1
77.4
PPD-AdaGrad
56.2
59.0
62.6
67.6 6
68.5
72.4
76.7
78,5
Ours
58.2
60.5
64.5
69.0
68.4
71.1
76.7
81.6
Results. The results are shown in Table We can see that our method slightly outperforms Lu arall [001]] and outperforms cross-entropy loss by a large margin, especially on imbalanced datasets, where the AUC objective shows superiority over cross-entropy loss.
Per-iteration complexity. The wall clock run time per iteration of cross-entropy, our solver, PPD- SG and PPD-AdaGrad are 0.018, 0.069, 0.122 and 0. 130 respectively (in terms of seconds). Our method and PPD cost more than directly optimizing cross-entropy because of the additional cost of solving AUC and our method is more time efficient compared with PPD.
Influence of e in our formulation II We test the influence of e using Cat&Dog as an example. Results (see appendix for the table) show that = 0.1 gets slightly worse performance than 0.01, while e = 0.001 performs much worse. To choose c, we follow the approach in Mangasarian [2004]] If for two successive values of c1 c2, the value of the perturbed quadratic function is the same, then it is the least 2-norm solution of the dual. Therefore, we simply choose an e that satisfies this property, which is chosen to be 0.01 in our experiments.
Optimizing Multiclass AUC
Table 2: Multiclass AUC results on STL10 and CIFARI00. Drop rate is the proportion used when dropping samples from 2 (of 3) classes.
We also evaluate our method for multiclass AUC. Similar to binary AUC, we construct imbal- anced multiclass datasets by dividing datasets into 3 classes and drop samples from of them and report one-versus-all AUC (as
(%)
CIFARIO0
STLI0
Drop rate
90%
80%
60%
90%
80%
60%
0%
Cross-Entropy
54.3
59,4
62.7
63.5
66.9
68.0
74.8
81.0
Ours
58.4
59.2
64.1
65.7
72.9
72.5
75.7
82.7
(S6)
CIFAR100
STL10
Drop rate
90%
80%
60%
90%
80%
60%
0%
Cross-Fatroppy
60.6
65.0
64.0
68.9
69.6
75.8
82.2
AUÇova) and AUCbin score
Ours
60.1
61.2
66.0
67.2
76.1
74.4
77.7
84.5
For STL10,, we group class 0 2, 3
5. 6 9 into the three classes, and drop samples from the

---

first two classes. For CIFRIO0, we group class 0 - 32, 33 65, 66 99 into three classes, and also drop samples from the first two classes.
Results. Results are in Table M In addition to one-versus-all AUC metric, we also report the per- formance in terms of AUC,, Kleiman and Page [0019] which is specifically designed for measuring multiclass AUC and preserves nice properties of binary AUC such as being insensitive to class skew. Our method outperforms cross-entropy loss all four datasets and under all different skewed ratios.
Cross-Erde Entrady Curs
Cross-Ertrgg Ertrap
Cross Entrasy
Ou/S
Curs
Thue Peattvve Rate
0.3
Tour Postbve PaP
0.5
6--
0.0
0.1
000
0.7
0.6
U.S.
0.0
1.0
00
0.2
U...
0.5
0.5
1.0
000
0.2
12.5
0.5
0.5
1.0
(a) Positive class:
(b) Positive class:
(c) Positive class:
Figure 2: ROC curve of multiclass AUC optimization on STLI0 with 90% drop rate. We divide
STLI0 into 3 classes and use one positive class and other two negative class plot the ROC.
0.40
comparioon
0.39
Dute-tiza
0:30
Becohee oucowerrd time
0.25
72
0.10
0.00
0.45 9.5
635
3.50
0.55
D.70
5/5 3.50 0.55
10
20
Redocodito 508e
(a) Evaluation of the quality of F1- (b) Runtime score predicted by our solver and our solver and blackbox solver Ap-Perf.
comparison of The relationship between re- duced size accuracy when us- ing SDR on constraint matrix A.
Pogančić et all [2M]]]
Figure 3: Three numerical experiments to show the properties of our solver.
Optimizing Fi-score
We show that by directly optimizing Fl-score, we can achieve a better performance than when using cross entropy loss. In addition to cross entropy loss, perform evaluations with two other methods that can also directly optimize the F1-score. First, we replace our solver with CVXPY-SCS Agrawal aL [ which refers the SCS solver used within CVXPY package: second, we perform comparisons with AP-Perf Fathony and Kolter [2022]] which offers differentiable optimization of f'I-score using an adversarial prediction framework. The datasets and our setup to group them into two classes remain the same as in binary AUC section. The results show that our method yields consistent improvement over cross-entropy loss in terms of Fi-score. The accuracy of cross-entropy loss on Cog, CIFAR10. CIFARIOK and STL10 is 76.0%, 70.3%, 60.4%. 71.8%, respectively. while our method gives 77.8%. 72.6%. %, 63.4% % 72.7% When we optimize F1-score directly, there exists local optimal point where assigning all examples to the positive class leads to F1-score of 66.7%. Both CVXPY-SCS and AP-Perf fall into this local optimal on four datasets (except that CVXPY-SCS gets out of the local optimal point on Cat& and gives 70.1% % accuracy). Note that although our solver, CVXPY-SCS and AP-Perf seek to solve the same objective, the backward gradient will be different due to different approximations used by the methods.
Comparing with blackbox solvers. Recently, several results Pogančré et al. [201)] Berthet et all [202 use blackbox solvers for solving combinatorial problems, which can also be used as a LP solver for problems where we need dz" /dc (c is the cost vector in standard form LP). These methods can utilize existing LP solvers and compute backward gradient by calling the LP solvers on perturbed LP problems. our knowledge, the current state-of-the-ard LP solvers are often CPU based, which means that one needs to transfer the LP parameters from GPU to CPU, then solve the IP on the CPU before getting the solution back. These CPU-based solvers will usually be slower than our GPU based solver, especially when the batch size is large. To evaluate this property, we randomly

---

Table 3: Properties of different methods. C, A, are the parameters describing a linear programming: min c² 2, s.t.Az < b. 2n denotes the optimal solution. The extra cost for computing backward gradient for Berthct ct all [2020], depending on implementation. can either be N times time cost,
or N times memory cost plus some time cost brought by increased batch size (see appendix for explanation).
Ours de
CVXPY-SCS
Perturbed solver Berthet al. [2020]
Gradients support
de de
de 25
d5
d2
dz de
2b
GPU support
depends on solver
Sparsity support
depends on solver N (# perturbations)
Extra cost for computing hackward gradient (denote forward time cost
Nearly zero
around
construct LP problems using AUC as an example and make the cost vector the parameter to optimize. In Fig. GR we compare the runtime of our solver and the blackbox solver in Poganćić et all [2019] (with the LP solver from scipy package). We can see that our GPU based solver is not sensitive to the increase in the batch size, while the CPU based solver is, due to the lack of support for operations. Our solver has more clear advantage in backward pass because the matrix needed for computing gradient is already computed during forward pass thus the backward pass is nearly free, while the blackbox solver Pogančić et al. [2019] needs at least the same time forward pass to compute backward gradient. We also compare our solver with Berthet et all [20010] in Table E!
Dealing with large scale LPs. In practice we often encounter large scale LPs whose constraint matrix may be too large to fit into the GPU memory. We first show that we can utilize sufficient dimension reduction in Fig. Bd which demonstrates reasonable tradeoff between reduced size and accuracy. Then we show that when the constraint matrix is sparse, we can readily utilize sparse operations to save memory. We have incorporated functionality to use sparsity within our solver [aaport] [202U], rusty Is el all [202)]. Consider AUC maximization in which the constraint matrix is extremely sparse. With our sparse implementation, we are able to run SGD on Resnet-18 18 with minibatch size of up to 200 on 2080Ti GPU with just 1GB memory whereas the same problem can take upto I IIBB using dense operations (<s 10x memory savings) with some overhead.
Limitations. Scaling is still key limitation for differentiable LP solvers. We present two ways to mitigate these problems but there is an associated cost. Our proposed SDR sacrifices some accuracy. Partly due to support within available libraries sparse operations can sometimes be slow when the size of the matrices is large which should improve with better sparsity support in existing libraries.
6 Conclusions
We demonstrated that various non-decomposable objectives can be optimized within deep neural net- works in a differentiable way under the same general framework of LPs using modified Newton's algorithm proposed by Mangasarian. A number of recent papers have studied the general problem of backpropagating through convex optimization modules, and this literature provides several effective approaches although scalability remains topic of active research. Our work complements these results and shows that the operations needed can be implemented to utilize the capabilities of mod- deep learning libraries. While our experimental results suggest that promising results on binary AUC, multi- class-class AUC and F-score optimization within DNNs is achievable, we believe that the module may have other applications where the number of constraints are large and data-dependent. Our code is available at https://gtthu..com
Potential negative societal impacts. Optimizing non-decomposable measures such as AUC is a fundamental task in statistics/machine learning and not tied to specific applications, so we do not see negative societal impact of the technical development described here. It is possible, however, that modules such as these can be used within general applications that are detrimental to society.
7 Acknowledgments
This work was supported by NIH RF1 AG059312 and RFI AG062336, and NSF CCF #1918211. We thank Sameer Agarwal for Twitter discussions regarding implicit differentiation in deep networks, and later pointing to Olvi's paper over email correspondence. Sathya Ravi was supported by UIC start-up funds. Yichao Wu was supported by NSF grant DMS-1821171
10

---

References
A. Agrawal, B. Amos, S. Barratt, S. Boyd, S. Diamond, and J. Z. Kolter. Differentiable convex optimization layers. In Advances in neural information processing systems, pages 9562-9574, 2019.
B. Amos and J. Z. Kolter. Optnet: Differentiable optimization as layer neural networks. ICMI,, 2017.
B. Amos, L. Xu, and J. Z. Kolter. Input convex neural networks. In International Conference on Machine Learning, pages 146-155, 2017.
K. Ataman, W. N. Street, and Y. Zhang. Learning to rank by maximizing auc with linear program- ming. In The 2006 IEEE International Joint Conference on Neural Network Proceedings, pages 123-129. IEEE, 2006.
Q. Berthet, M. Blondel, O. Teboul, M. Cuturi, J.-P. Vert, and F. Bach. Learning with differentiable perturbed optimizers. ICLR, 2020.
M. Blondel, O. Teboul, Q Berthet, and J. Djolonga. Fast differentiable sorting and ranking. In International Conference Machine Learning, 2020.
C. Cortes and M. Mohri. Auc optimization vs. error rate minimization. In Advances in neural information processing systems, pages 313-320, 2004.
Y. Cui, M. Jia, T.-Y. Lin, Y. Song, and S. Belongie. (lass-balanced loss based on effective number of samples. In Proceedings of the IEEE/CVF conference computer vision and pattern recognition, pages
2019.
K. Dembezynski, W. Waegeman, W. Cheng, and E. Hüllermeier. An exact algorithm for f-measure maximization. In J. Shawe-Taylor, R. S. Zemel, P. L. Bartlett, F. Pereira, and K. Q. Weinberger, editors, Advances in Neural Information Processing Systems 24, pages 1404-1412. Curran Asso- ciates, Inc., 2011.
E. Eban, M. Schain, A. Mackey, A. Gordon, R. Rifkin, and G. Elidan. Scalable learning of non- decomposable objectives. In Artificial Intelligence and Statistics, pages 832-840, 2017.
R. Fathony and Z. Kolter. Ap-perf: Incorporating generic performance metrics in diffcrentiable learning. In International Conference on Artificial Intelligence and Statistics, pages 41 4130-4140. PMLR, 2020.
flaport. torch-sparse-solve.
thub. wwt.:occmmffffooe http sparse solve, 2020.
W. Gao, R. Jin, S. Zhu, and Z.-H. Zhou. One-pass auc optimization. In International conference machine learning, pages 906-914, 2013.
I. Goodfellow, M. Mirza, A. Courville, and Y. Bengio. Multi-prediction deep boltzmann machines. In Advances in Neural Information Processing Systems, pages 548-556, 2013.
J. A. Hanley and B. J. McNeil. The meaning and use of the area under receiver operating charac- teristic (roc) curve. Radiology, 143(1):29-36, 1982.
S. S. Keerthi, V. Sindhwani, and O. Chapelle. An efficient method for gradient-based adaptation of hyperparameters in models. In Advances neural information processing systems, pages 673-680, 2007.
H. J. Kim, B. M. Smith, N. Adluru, C. R. Dyer, S. C. Johnson, and V. Singh. Abundant inverse regression using sufficient reduction and its applications. In European Conference on Computer Vision, 2016.
K. Kim, B. Li, Z. Yu, L. Li, et al. On post dimension reduction statistical inference. Annals of Statistics, 4863):1567-192 2020.
R. Kleiman and D. Page. Aucp: A performance metric for multi-class machine learning models, In International Conference Machine Learning, pages 3439-3447, 2019.

---

M. Liu, X. Zhang, Z. Chen, X. Wang, and T. Yang. Fast stochastic auc maximization with o(1 (n/ convergence rate. International Conference on Machine Learning, pages 3189-3197, 2018.
M. Liu, Z. Yuan, Y. Ying, and T. Yang. Stochastic auc maximization with deep neural networks. ICLR, 2019.
O. Mangasarian. A newton method for linear programming. Journal of Optimization Theory and Applications, 1-)1,,, 2004.
O. I.. Mangasarian, Exact 1-norm support vector machines via unconstrained convex differentiable minimization. Journal of Machine Learning Research, 1111531517-11530 2006.
G. Mena, D. Belanger, S. Linderman, and J. Snoek. Learning latent permutations with gumbel- sinkhorn networks. ICLR, 2018
Z. Meng, S. N. Ravi, and V. Singh. Physarum powered differentiable linear programming layers and applications. arXiv preprint arXiv:2004.14539, 2020.
L. Metz, B. Poole, D. Pfau, and J. Sohl-Dickstein. Unrolled generative adversarial networks. ICLR, 2017.
P. Mohapatra, M. Rolinek, C. Jawahar, V. Kolmogorov, and M. Pawan Kumar. Efficient optimization for rank-based loss functions. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pages 3693-3701, 2018.
Y. Nan, K. M. Chai, W. S. Lee, and H. L. Chieu. Optimizing f-measure: A tale of two approaches. arXiv preprint arXiv: 1206. 4625, 2012.
M. Natole, Y. Ying, and S. Lyu. Stochastic proximal algorithms for auc maximization. In Interna- lional Conference on Machine Learning, pages 3710-3719, 2018.
Y. Nesterov. Introductory lectures convex optimization: A basic course, volume 87. Springer Science & Business Media, 2013.
M. Pilanci and M. J. Wainwright. Iterative hessian sketch: Fast and accurate solution approximation for constrained least-squares. Journal of Machine Learming Research, 17(53):1-38, 2016. URL http://jml= wttp:///pppppp////////////// hmml.
M. V. Pogančić, A. Paulus, V. Musil, G. Martius, and M. Rolinck. Differentiation of blackbox combinatorial solvers. In International Conference on Learning Representations, 2019.
A. Rajeswaran, C. Finn, S. M. Kakade, and S. Levine. Meta-learning with implicit gradients. In Advances in Neural Information Processing Systems, pages 11-1244, 2019.
N. Ravi, A. Venkatesh, G. M. Fung, and V. Singh. Optimizing nondecomposable data dependent regularizers via lagrangian reparameterization offers significant performance and efficiency gains. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 34, pages 5487-5494 2020.
rusty Is el al.
https: http:://gttaab.cco/uststssssyyys
sparse, 2020.
Y. Song, A. Schwing, Urtasun, et al. Training deep neural networks via direct loss minimization. In International Conference on Machine Learning, pages 2169-2177. PMLR, 2016.
X. Zeng, R. Liao, L. Gu, Y. Xiong, S. Fidler, and Urtasun. Dmm-net: Differentiable mask- matching network for video object segmentation. In Proceedings of the IEEE International Con- ference on Computer Vision, pages 3929-3938, 2019.
X. Zhang, Q. Mai, and H. Zou. The maximum separation subspace in sufficient dimension reduction with categorical response. Journal of Machine Learning Research, 21(29):1-36 2020. URL prgppapers/v2///t.. html.
12

---

Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes] See experiment section and the
limitation section (before Conclusions).
(c) Did you discuss any potential negative societal impacts your work? [Yes] See conclusions.
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes] See section
(b) Did you include complete proofs of all theoretical results? [Yes] See section and supplement.
3. If you ran experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or URL)? [Yes] See supplement
(b) Did you specify all the training details (c.g., data splits, hyperparameters, how they were chosen)? [Yes] See experiment section and supplement.
(c) Did you report error bars (e.g.. with respect to the random seed after running experi- ments multiple times)? [Yes] We include error bars Fig BR.
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, cloud provider)? [Yes] See experiment section.
4. If you using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [Yes]
(b) Did you mention the license of the assets? [N/A] The license can be found in cited paper/website.
(c) Did you include any new assets either in the supplemental material or as URL? (Yes] In supplement
(d) Did you discuss whether and how consent was obtained from people whose data you're re using/curating? [N/A] These can be found in cited paper/website from the creators.
(e) Did you discuss whether the data you are using/curating contains personally identifi- able information offensive content? [N/A] These be found in cited paper/web- site from the creators.
5. If you used crowdsoureing or conducted research with human subjects...
(a) Did you include the full text of instructions given participants and screenshots, applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent participant compensation? [N/A]
13


Reviews:
[{"review_id": "sPrQJ2S9Eh", "reviewer": "Reviewer_Gi3P", "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.\n", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "main_review": "**After rebuttal**\n\nI 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.\n\n\nHowever, 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.\n\n\n**Original review**\n\nThe 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.\n\n\nRelated 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.\n\nLines 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.\n- 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$. \n\nLine 174: Please unpack this math. $\\tilde{H}$ is implicitly defined and only here but it is needed later below. Please also define $\\rho$. \n\nThe statement of Lemma 1 is vague.\n- 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.  \n- Typo: “constant” -> “quadratic” ?\n\nThe 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.\n\nSimilarly, 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.\n\nThe 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. \n- 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.\n\nIt 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).", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "This paper discusses the limitations of the work in detail.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}, {"review_id": "dTe6XLunteD", "reviewer": "Reviewer_TyHW", "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.\nThey propose a general LP-based framework describing these objective functions and provide a general algorithm to solve this problem (and get the corresponding gradients).\nFinally, this new approach is compared to other methods trying to optimize these objectives directly and surrogate loss functions that are commonly used in practice.", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "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.\n\nFrom a high level:\n- 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.\n- 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?\n- 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.\n- 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?\n- l214 do you have any result on data-driven SDR?\n- The absence of baseline trying to optimize the multiclass AUC is surprising. Could you detail why?\n\nSmaller details:\n- Thanks for including a notations section!\n- l165 \"exterior penalty in (3)\" is not defined\n- 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.\n- l189 the value given in parenthesis is a pair of values?\n- l225 the sentence is not english. More generally, a few sentence in the paper would gain at being shorter.\n- l234, why do you redifine Q = H tilde ? Why not just keep using H tilde?\n- l252 using -> during\n- l257 the discussion around Danskin's theorem is surprising here as it is not mentioned anywhere else in the paper.\n- Fig 2 is never linked from the text, same for Fig 3a as far as I can see\n- l316 formatting is weight. It could be better aligned to avoid the single dangling line\n- l324 which results?\n- Table 3: \"N\" should be defined in the caption.\n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors clearly address the limitations of the method in a clear paragraph.\n", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2"}, "extra_text": {}}, {"review_id": "ar0wAnPgXi4", "reviewer": "Reviewer_mCRV", "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.", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "main_review": "### Strengths\n1. The problem is well motivated: end-to-end training for metrics such as AUC would be of practical interest to the machine learning community.\n2. The formulation seems sound and amenable to efficient (and differentiable) optimization methods.\n3. 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.\n4. The experiments (which are \"medium-scale\" by deep learning standards) show consistent improvements over the baselines.\n\n### Weaknesses\n1. 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).\n2. 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.\n\n### Questions\n1. 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.\n2. 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)?\n3. 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?\n4. 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?\n5. 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?\n6. Can the authors discuss how the proposed method compares with existing work on direct loss optimization such as [1]?\n\n### Minor comments:\n1. 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.\n2. L.104 the second sum for $X_-$ should be over $j$\n3. Results on nonnegative matrix factorization are announced in the experiments section, but turn out to be available in the supplementary material only.\n4. 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.\n\n### Reference\n\n[1] Song, Yang, Alexander Schwing, and Raquel Urtasun. \"Training deep neural networks via direct loss minimization.\" International Conference on Machine Learning. PMLR, 2016.\n\n----\n\n### Updated Review\n\nThanks 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).", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Sufficiently discussed.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6"}, "extra_text": {}}]

Author rebuttal:

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)