Learning Surrogate Losses
Authors: Josif Grabocka
Randolf Scholz
Lars Schmidt-Thieme
Venue:  (2020)
Keywords: Surrogate losses
Non-differentiable losses

Abstract: The minimization of loss functions is the heart and soul of Machine Learning. In this paper, we propose an off-the-shelf optimization approach that can seamlessly minimize virtually any non-differentiable and non-decomposable loss function (e.g. Miss-classification Rate, AUC, F1, Jaccard Index, Mathew Correlation Coefficient, etc.). Our strategy learns smooth relaxation versions of the true losses by approximating them through a surrogate neural network. The proposed loss networks are set-wise models which are invariant to the order of mini-batch instances. Ultimately, the surrogate losses are learned jointly with the prediction model via bilevel optimization. Empirical results on multiple datasets with diverse real-life loss functions compared with state-of-the-art baselines demonstrate the efficiency of learning surrogate losses.

Under review as a conference paper at ICLR 2020
LEARNING SURROGATE LOSSES
Anonymous authors Paper under double-blind review
ABSTRACT
The minimization of loss functions is the heart and soul of Machine Learning. In this paper, we propose off-the-shelff optimization approach that can seamlessly minimize virtually any non-differentiable and non-decomposable loss function (e.g. Missclaasification Rate, AUC, FI, Jaccard Index, Mathew Correlation Coef- ficient, etc.). Our strategy learns smooth relaxation versions of the true losses by approximating them through a surrogate neural network. The proposed loss net- works are set-wise models which are invariant to the order of mini-batch instances. Ultimately, the surrogate losses are learned jointly with the prediction model via bilevel optimization. Empirical results multiple datasets with diverse real-life loss functions compared with state-of-the-art baselines demonstrate the efficiency of learning surrogate losses.
INTRODUCTION
In reality, a large set of loss functions cannot be directly minimized by gradient- based methods because they either piece-wise continuous, non-differentiable, non-decomposable (Zhang et al. 2018). For example, binary classification models are often evaluated using the miss-classification rate (MCR), Area under the ROC curve (AUC), Fl measure (FI), Jaccard Similarity Index (JAC), Average Precision (AP), Equal Error Rate (EER), or the Mathew Correlation Coefficient (MCC). On the other hand, learning-to-rrn to-rnk models are measured through the Normalized Discounted Cumulative Gain (NDCG), or the Mean Average Precision (MAP). To illustrate the point, Figure [ shows the challenging surfaces of common binary classification losses. Unfortunately, there exists no tractable omni-solver so far, i.e. no off-the-shelf optimization strategy to train prediction models for the aforementioned category of loss functions. worth pointing out that con-gradientt-assee approaches, such evolutionary computing. are intractable from a runtime perspective.
While there exists a plethora of methods that tackle various aspects of particular losses, there is no single gradient-based method that can optimize any loss in seamless manner. Researchers have so far focused on deriving smooth surrogate relaxations (approximations) to the true loss functions (Berman et al. 2018 Ebaa et al.) 2017). in way that first- and second-orde optimization techniques can benefit from the derivative of the surrogates with respect to the parameters of prediction models. For instance, the widely-applied cross-entropy loss is a surrogate relaxation of the miss-classificatinn rate. However, these explicit relaxations are hand-crafted individually for each loss and do not generalize to other losses.
In this paper, we present the first off-the-shelf optimizer for arbitrary loss functions. In contrast to the related work, this work proposes a new perspective on minimizing loss functions, by defining surrogate losses as meta-level neural networks that approximate the desired true non-differentiable losses. Our method does not need the gradient information of the true loss with respect to the parameters of the prediction model and treats the loss as black-box function. In addition, we introduce a set-based surrogate network that computes the loss over the training set, being invariant to the order of instances, in order to accurately handle non-decomposable losses.
The surrogate learning problem is formalized as bilevel programming task (Colson et al. 2007 Franceschi et al.] 2018) that is trained through concurrent optimization algorithm. This paper shows that universal surrogates, which are trained without paying attention to a specific dataset, sub-o sub-optimal compared to surrogates learned in dar-dataset manner. Results on nine datasets demonstrate that learning surrogates produces more accurate prediction models than state-of-the. the-art baselines with regard to diverse loss functions.

---

Under review as a conference paper at ICLR 2020
MCR.
AUC
EER
AP
F1
0
0
1
0
0
1;
Y;
9,
Y.
Figure 1: The surfaces of five binary classification losses derived by perturbing the predictions Y. Y, of two instances inside a random mini-batch Ý E RT Y E {0,1)"M with true targets Y, = 0, = 1. AUC, AP and Fl are converted to losses via 1 x, while the positive class for MCR, EER is estimated as y 2 0.
2 RELATED WORK
Due to the non-differential and non-continuous nature of most real-life losses, early works deployed the proxies of the classilassiiinntoonn rate (c.g. cross-entropy) as universal proxy losses, despite their sub-optimal performance (Cortes& & Mohri 2004). Subsequent approaches relied on designing smooth relaxations of the losses. As an example, the pairwise ranking loss is common surrogate of the AUC measure (Gao & Zhou 2015 Chen et al. 2009). On the other, hand, the F-measure is another typical loss that cannot be optimized directly due to its non-decomposable nature over instances. The initial papers tackling Fl focused instead on the empirical utility maximization paradigm (Ye et al. 2012). Later on, researchers addressed F1 by optimizing the hyper-parameee parameters of standard binary classifiers, either the cost-sensitive weights of the classification loss (Puthiya Parambath et al. 2014 or the threshold of the estimated target values (Lipton et al. 2014 Koyejo et al. (2014). Nevertheless, the non-decomposable trait of F1 remains unresolved (Zhang al.. (0118) and recent works have explored directions to improve hyper-parameter tuning with tighter bounds (Bascol et al. 2019).
Instead of relying on explicit surrogates, another research direction handles non-convex losses by means of the direct loss method (Hazan et al., 2010)), which minimizes a surrogate loss by embedding the true loss as a correction term. This method was recently extended optimize neural networks (Song et al. 2016). It assumes the loss can be decomposed into per-instance sub-losses and the authors derived an explicit decomposition of the average precision (Song et al. (016)) Unfortunately, per-instance dis-aggregations are not trivially feasible in other cases (e.g. F1), making the direct loss optimization technique an impractical off off-the-shelf option.
Two more recent papers have offered relaxation surrogates for non-decomposable losses, concretely the AUC and the Jaccard Index (known as Intersection over Union in the computer vision community). The first method defines relaxation forms for the building blocks of confusion matrix (e.g. true positives, true negatives etc.) and combines the building block relaxations to create final surrogate for losses like the AUC (Eban et al. 2017). However, this model does not handle cases where the loss is not expressible into confusion matrix blocks, for instance the Jaccard index. On the other hand, the second paper proposes the Lovasz soft-max smooth approximation the Jaccard index (Berman let al. 2018), which is based on a generic decomposition of sub-modular (decomposable) losses for sets Yu & Blaschko 2015)).
Besides that, a stream of recent papers has focused on meta-learning for loss functions. The "Learning to Teach" paradigm (Fan et al.) 2018) proposes a meta-level teacher/controller that continuously updates the loss function for a prediction model based on its progress. The work has been recently extended enable gradient-basee this approach does not extend to non-decomposable loss functions which are defined over the full set of instances. A parallel stream of research has elaborated the concept of "Learning to Learn" (Li & Malik 2017), or "Learning to Optimize" (Chen et al.) (017). which proposes to directly learn the amount of update values that are applied to the parameters proposed framework controller uses per-parameter learning curves comprised of the loss values and derivatives of the loss with respect to each parameters (Chen et al. 2017). This method suffers from two drawbacks that prohibit its direct upplicability to arbitrary losses: i) for large prediction models it is computationally infeasible to store the learning curve of every parameter, and ii) there is no gradient information for non-differentiable losses.
learning of the teacher/controller (Wu et al.) 2018). However,
the prediction model. In the
2

---

Under review as a conference paper at ICLR 2020
An alternative approach towards learning loss functions analyzes the usage of discriminative adver- sarial networks (dos Santos et al. 2017). ). The idea focuses on discriminating the probability of a given target variable value into either being estimated target the true one, therefore acting form of surrogate loss (dos Santos et al.) 2017). Last, but not least, our method shares similarities with the concept of error-critic model for function approximation (Pang & Werbos 1998). In contrast to the prior work, we propose the first off-the-shelf optimization method that seamlessly minimizes any loss function. In Section 4.3 we empirically compare the proposed method against multiple satte-of-the-aee relaxations, with regards to minimizing popular binary classification losses, such as AUC, F1, Jaceard Index and the ciss-slaasiiiiatiin rate.
SURROGATE LEARNING
Data mini-batches (ar, v) :- {(x) :I...... (ZN. of N instances each, with features æ E RN and ground-truth targets y E )dN, are drawn from a dataset D with sampling distribution PD (r, v). where typically P is the uniform distribution. The target domain can be binary y E {0, I or nominal among C' categories E {I..... CY. Ultimately, the purpose of a prediction model is to estimate target variable ÿ(z; a): R RNXM + RN,, where the prediction model has parameters The estimations ÿ E TR- need to accurately match the given ground-truth target variable E y with regards to desired loss function E (v. ú) IRN x )' + R. Therefore, supervised learning focuses on computing the optimal parameters a² that minimize the following objective.
a- = arg min ((a.w))P(mma)) e (v. ((;)))
(1)
To minimize the aforementioned objective through first- or second-order optimization, is necessary dt Unfortunately, in most real-world cases the loss represents step functions
to define the gradients Be that are only piece-wise continuous (MCR, F1, AUC, etc.). Therefore, the derivatives are either zero, or undefined at the function steps, which prohibits direct optimization of these losses. For this reason, a smooth surrogate relaxations of the loss functions is used instead of the true loss. Arguably the most popular surrogate is cross-entropy, which is relaxation of the miss-classification rate. Yet, such non-parametric relaxation functions are not trivially derivable when the loss is non- decomposable into per-instance components (e.g. F1, AUC), because such losses are defined as performance measures over an entire set of instances.
Instead of deriving one explicit hand-crafted function i for the surrogate of every loss function we propose method that parameterizes and learns the surrogate for any demanded loss func- tion through an off-the-shelve procedure. Neural networks are a good choice for parametrizing the surrogate loss given their universal approximation capability (Hornik 1991). However, the surrogate loss network must be a permutation-invanl
set model, whose output must remain fixed given different orders instances within a dataset mini-batch, i.c. (1),.... yN .1...., UN) =
(V+(I)::.. ... (N) (r(1)..... (=(N)) for any index permutation т. Our method uses the Kol- mogorov Arnold representation theorem (Tikhomirov) 1991) and defines the surrogate loss of Equa- tion 2 as a composition function h of per-instance functions This type of aggregation was recently applied to learning neural networks over sets of instances (Zaheer et al. 2017).
( 1) h
N E Eg(un))
where g: 2 -> RR,, and h: RR_ + R are deep forward neural networks. The first function g extracts Q latent error components for the predictions each instance (c.g. latent representations of false positive, false negative, etc.), while the aggregation produces set-wise performance indicators (e.g. potentially latent representation of the count of true positives, false positives, error rate, etc.). The function h creates nonlinear combinations of set-wise performance indicators to produce complex latent error metrics such as precision, recall, F1, etc.
has been proven that with sufficient capacities for and h, any cemmutation-invariann set function (hence any loss) can be approximated via the Kolmogorov-Amold (KA) representation theorem (Za
3

---

Under review as a conference paper at ICLR 2020
heer al. 2017). In particular, it is worth mentioning that due to being instance of the KA superposition, the proposed surrogate model of Equation[]oa benefits from existing error bound guar- antees of such representation when the functions g and h are deep neural networks (Montanelli & Yang, 2019). The remaining sections of this paper detail a novel method for optimizing surrogate losses.
3.1 UNIVERSAL SURROGATES
The first intuition is to learn the weights 3 of surrogate network (a.k.a. the functions and h) in universal manner by solving the objective Equation In other words, we can attempt to make any surrogate loss ? behave as any true loss over the space all possible batches of randomly-drawn true y and estimated ý targets. Focusing on binary classification losses, we sample the ground truth from a Bernoulli distribution, and respective estimated targets from Gaussian distribution. Furthermore, the meta-loss L R x I- + I measures the distance between the true and surrogate losses and is practically implemented as an L1 norm.
gUniversal arg min E Byr-Bl))xnn S~N(m.03 (((v.0).(...b.1)
The challenge of learning universal surrogate is in ensuring that the sampling hyper-parameters (p, μr, σ)) would lead to drawing (y. ú) that match the specific target distribution of a concrete dataset. Therefore, we empirically found out that it is sub-optimal the true loss. Instead, as future sections will detail, it is more efficient to design a relaxation in sataset-specific manner, which smoothens only the specific regions of the true loss which belong to the respective dataset-specific distributions of true and estimated target batches.
universally relax the whole space of
3.2 SURROGATE LEARNING AS BILEVEL PROGRAMMING
different approach from the universal surrogate associate a surrogate loss to each dataset. In that manner, the surrogate creates smooth relaxation only around the dataset-relevant regions of the target (y, [(;; a)) space. We propose to jointly optimize the prediction model parameters (a) and the surrogate loss parameters (3) through the following optimization:
a² arg min ((z.)))P((..)
(v.ū a): 8)
(4)
3r arg min E ((z.))))((..)) C (e(y.((z;))) (v,,0)))) 3)
(5)
The rationale is that Equation 4 optimiizes the prediction model in order to minimize the surrogate loss. However, the surrogate loss should approximate the true loss, which is ensured by Equation 5
Such interdependence concurrent relationship, in way that we can optimize them jointly and simultaneously. This dual objective is an instance bilevel programming problem (Colson et al. 2007 Franceschi al.) 2018). Algorithm I sketches the minimization procedure of the proposed surrogate learning. In an alternating fashion, the surrogate minimization is carried out for K. steps (lines 4 7), while the surrogate loss is updated for Kg steps (lines 9 12). To illustrate the mechanism. Figure 2 provides minimalistic example of optimizing jointly the bilevel programming objectives for training single-paramete model on single-feature binary dataset. The plots show the effect of minimizing the surrogate (magenta), as the parameter a is updated towards the minimum of the surrogate. At the same time, observe that the surrogate is updated to match the true cassssssssiiittinnnntt loss (cyan) at the current parameter value. The model converges close to the optimal true loss after applying the steps of Algorithm
be addressed by treating both objectives of Equations 4 and
3.3 NOTE ON CONVERGENCE
is possible to analyze the convergence of Algorithm following existing proofs for bilevel pro- gramming (Revalski & Zhivkov 1993. Franceschi al. 2018), since Equations 4 can be rewritten
4

---

Under review as a conference paper at ICLR 2020
Binary Data
Batch: 1000
Batch: 3000
Batch: 10000
MCR
0.4
MCR
0.4
MCR
0.4
0,25
0.0
2
1
0.2
0.1
0.2
0.4
0.2
0.1
X
CK
==0
Current &
Figure 2:
A single-pane parameter prediction model ((2 a)
1 classifies single- feature binary dataset
(leftmost plot), i.e. a E R, E R N where initially a = 0.3. In the three rightmost plots, the x-axis shows the variation in true (cyan) and surrogate (magenta) losses for the whole space of a. The plots indicate that Equation forces the surrogate approximate the loss the regions around the current (dashed vertical line), while the parameter a updated towards the minimum the surrogate by Equation
Algorithm 1: Surrogate Learning
Input Dataset D, Loss f, Training epochs T, Update steps Ka, Ks, Learning rates Ta 7/8
Initialize a, B
for 1.....,77 7 do
( +a
for k = 1,.... Ko do
Sample batch (z, v) ~ PD (x,
(e) f (M-1) 11 V V. (1; (k-1)) ( 3)
end
a t (Ka), , 300) 3 for k 1,... . Kg do
Sample batch (x, y) ~ PD (x, y)
10
g(k) + ((k-1) 1g of
3(1-11))
11
12
end
B + g(Ka)
13
14
end
Return: Prediction model ý (x;
in standard bilevel programming form: mingE É(a, 8" (a)), 8 (a) = arg ming(a) ((,, B (a)). However, the assumptions of the proofs offered by the related work are violated in the case where both considered models C are deep neural networks (Franceschi et al. 2018). For example, the assumption necessitating the optimal loss parameters arg ming(a) L (a, 3 (a)) represent single- for every AA would not hold as there exist continuum many global minima. Nevertheless, we empirically observed that the proposed bilevel optimization problem of Equations converges well in practice under the optimization regime of Algorithm visually observable through the exemplifying convergence plots of Section
4
EXPERIMENTS
4.1
PROTOCOL.
The experiments are focused on collection of publicly-available binary classification datasets, whose statistics are presented Table [ We split the data randomly into 80% training and 20% testing instances. The prediction model has an architecture of [100, 30, 10, 1] neurons with Leaky- ReLU activation, where batch normalization was applied at each layer. In addition, after each batch normalization added drop-out regularization layer with the drop rate
0.2. The surrogate network component has [30, 30) neurons, while h has [10, 10, 1] neurons. We employed the Adam optimizer for training the network, with initial learning rates being 1/a n/ 10-3
5

---

Under review as a conference paper at ICLR 2020
Table 1: Dataset Statistics.
Dataset
Classes
Train
Test
Features
Pos. Frac.
A9A
2
39073
9769
123
0.2379
CC-Fraud
2
227845
56962
29
0.0015
Cod-RNA
2
390852
97713
0.3346 8
CoverType
2
464809
116203
54
0.4867
IJCNN
2
125344
31337
22
0.0954
Porto-Seguro
2
476169
119043
57
0.0368
Santander
2
160000
40000
200
0.1004
Skin
2
196045
49012
3
0.7919
Susy 2
4000000
1000000
0.4577
Furthermore, to improve the convergence stability clipped the gradients by norm of 10-5, which is necessary due to the steep curvature of the surrogate losses é, caused by approximating the step-wise true loss surfaces f. Data batches were drawn a stratified random fashion (50% positive and 50% negative) with mini-batch size N 100. The update steps were chosen Ka and K3 = 10 and Algorithm [ was run for 300000 iterations. We conducted experiments with 7 binary classification measures, namely AUC, Equal Error Rate (EER), Average Precision (AP), ciss-classification rate (MCR), FI, Mathew Correlation Coefficient (MCC), Jaccard Coefficient (JAC). All the measures are converted a loss by a 1 x conversion, except for EER and MCR. For the losses that demand converting the predictions ý into binary values (e.g. MCR, FI, MCC), we used a thresholding 1 2 Y where y was optimized for each dataset and loss. The following results of Sections present the performance on the test sets.
4.2 ABLATION OF SURROGATE MODELS
This section addresses whether the surrogate should be trained in universal manner (Section) 3.1) or whether they should be optimized on per-dataset basis following the bilevel programming of Section 3.2 For this reason, we designed three different modalities for surrogate learning:
Universal Surrogate (SL-UU): Learn the surrogate i using Equation with hyperparameters = 0.5 (due to stratified sampling), = 0, a = 1, and then train only the prediction model f by minimizing é through Equation
Learned from Scratch (SL-S): Initialize the surrogate network from scratch (randomly), using Algorithm
then optimize both Equations 4
Refined Surrogate (SL-R): Initialize the surrogate with the universal solution of Equation and then refine the surrogate by optimizing both Equations 4 Jusingg Algorithm
Table shows the results of the ablation study with the 3 variations of surrogate learning on 7 losses and 9 datasets. We notice that the universal surrogates (SL-U) are overall sub-optimal with respect to the trained in der-dataset manner (SL-R, SL-S), except for the AUC loss. In addition, the results indicate that there is not a major difference terms of accuracy between SL.RR and SL-U. The refined surrogate improves the convergence of the optimization procedure, Figure 3
4.3 COMPARISON WITH THE OFATE-OF-THE-ART
In order to demonstrate the usefulness learning surrogates, we will compare our method against the state-of-the art baselines of four popular loss functions: MCR, AUC, F1 and JAC. Concretely, cross-entropy is the relaxation MCR, while Pairwise Ranking (Gao & Zhou 2015 Chen et al. 2009) and Global Objective (Eban et al. 2017) are the relaxations of AUC. Furthermore, the Lovasz Soft-Max is the relaxation of JAC (Berman et al., 2018 Yu & Blaschko 2013). and the cost-sensitive reduction (Puthiya Parambath et al. 2014) serves as the surrogate of FI. All the aforementioned baselines, except the cost-sensitive reduction, have no further paper--rramtters and were implemented based on the authors' codes. For ceteris paribus comparison, used the same capacity prediction

---

Under review as a conference paper at ICLR 2020
Table Comparing universal surrogates (SL-U) against dataset-specific surrogates (SL-S and SL-R), which either initialized randomly (SL-S) or with the universal surrogate (SL-R). The lowest loss values are highlighted.
Loss Measures
Dataset
Model
AUC
EER
AP
MCR
F1
MCC
JAC
SL-U
0.0968
0.1897
0.2629
0.2165
0.4557
0.2164
0.1819
A9A
SL--R
0.0983
0.1807
0.2584
0.1502
0.3134
0.2085
0.1512
SL-S
0.0969
0.1782
0.2585
0. 0.1508
0.3115
0.2069
0.1529
SL-U
0.0245
0.1512
0.2530
0.0093
0.7774
0.3975
0.0099
CC-Fraud
SL-R
0.0284
0.0914
0.1650
0.0088
0.7693
0.3293
0.0088
SL-S
0.0209
0.0814
0.1902
0.0088
0.9970
0.3293
0.0089
SL-U 0.0107
0.0513
0.0293
0.0510
0.1430
0.0514
0.1272
Cod-RNA
SL-R
0.0110
0.0422
0.0273
0.0430
0.0632
0.0476
0.0426
SL-S
0.0101
0.0428
0.0275
0.0418
0.0619
0.0474
0.0422
SL-U 0.1450
0.3019
0.1730
0.3466
0.2699
0.2349
0.2886
Covtype
SL-R
0.1463
0.2220
0.1663
0.2198
0.2102
0,2165
0.2192
SL-S
0.1468
0.2233
0.1635
0.2207
0.2109
0.2203
0.2219
SL-U 0.0048
0.0378
0.0537
0.1045
0.5486
0,1923
0.0609
IJCNN
SL-R
0.0030
0.0268
0.0224
0.0161
0.0806
0.0422
0.0152
SL-S
0.0028
0.0260
0.0219
0.0153
0.0777
0.0427
0.0161
SL-U 0.3745
0.4348
0.9376
0.0461
0.8990
0.4901
0.0459
Perto-Seguro
SL-R
0.3737
0.4110
0.9361
0.0449
0.8867
0.4606
0.0448
SL-S
0.3744
0.4127
0.9367
0.0446
0.8939
0,4614
0.0446
SL-U 0.1453
0.2349
0.5027
0. 0012
0.5800
0.3012
0.0951
Santander
SL-R
0.1465
0.2300
0.4996
0.0864
0.5166
0.2863
0.0863
SL-S
0.1470
0.2314
0.4945
0.0871
0.5083
0.2857
0.0861
SL-U 0.0001
0.0648
0.0001
0.0075
0.0036
0.0836
0,0889
Skin
SL-R
0.0006
0.0044
0.0003
0.0073
0.0085
0.0031
0.0115
SL-S
0.0009
0.0143
0.0001
0.0047
0.0017
0.0035
0.0031
SL-U 0.1316
0.2269
0.1312
0.4596
0.2507
0.2133
0.2461
Susy
SL-R
0.1334
0.2156
0.1288
0.2046
0.2289
0.2050
0.2031
SL-S
0.1324
0.2140
0.1291
0.2043
0.2294
0.2062
0.2050
SI-U
1.78
2.89
2.67
2.78
2.67
2.89
2.78
Ranks
SL-R
2.22
1.67
1.67
1.78
1.78
1.44
1.56
SL-S
1.89
1.44
1.67
1.22
1.67
1.67
1.67
AUC
BER
MCC
MCR
0.6
The
The
0.6
Thee
The
5000
5000 Egech
5000
5000
5000
5000
Epoch
Epoch
Egoch
Epoch
Figure 3: Illustrating the convergence for different loss functions the UCNN dataset, using two types of surrogates, SL-S: randomly from scratch, SL-R: refined from the universal surrogate. and L represent the surrogate optimization performance on the training set, while glest the true loss the tesing set.
7

---

Under review as a conference paper at ICLR 2020
The hyper- parameter of the cost-sensitive reduction, namely the positive weight coefficient was tuned among separate validation set. To ensure that the baselines converged, we trained them for 1M iterations with a learning rate of 10-1. Table presents the results over the 9 datasets, where the refined surrogate learning SL-R is compared to the 5 state-of-the-ar relaxation methods for losses. The evidence suggests that surrogate learning yields more accurate prediction models than the state-of-the-art.
model for the baselines, the same batch size, i.e the same protocol in Section 4.1
{0.3, 0.9, 2.7, 8.1, 24.3, 72.9)
Table 3: Surrogate learning SL-R vs state-of-the-arr, MCR: CE Crross-Entropy): AUC: PR (Pairwise Rank-
ing (Gao Zhou 2015 Chen et al. 2009)), GO (Global Objectives (Eban et al. 2017)); JAC: 1.O (Lo-
vasz Soft-Max for Jaccard (Berman et al. [0188] Yu & Blaschko 2015 FI: CS (Cost-sensitive Fl reduc-
tion Puthiya Parambath el. 2014)). Lowest values in bold.
MCR
AUC
JAC
F1
Data
CE
SL-R
PR
GO
SL-R
LO
SL-R
CS
SL-R
A9A
0.1520
0.1502
0.1019
0.1028
0.0983
0.1539
0.1512
0.3177
0.3134
CCF
0.0088
0.0088
0.0437
0.0369
0.0284
0.0088
0.0088
0.7652
0.7693
COD
0.0462
0.0430
0.0122
0.0129
0.0110
0.0438
0.0426
0.0652
0.0632
COV
0.2149
0.2198
0.1786
0.1504
0.1463
0.2594
0.2192
0.2305
0.2102
IJC
0.0364
0.0161
0.0168
0.0258
0,0030
0.0322
0.0152
0.1959
0.0806
POR
0.0446
0.0449
0.3814
0.3815
0.3737
0.0445
0.0448
0.8851
0.8867
SAN
0.0842
0.0864
0.1406
0.1427
0.1465
0.0850
0.0863
0.4990
0.5166
SKI
0.0482
0.0073
0.0364
0.0473
0.0006
0.0432
0.0115
0.0278
0.0085
SUS
0.2146
0.2046
0.1524
0.1508
0.1334
0.2022
0.2031
0.2420
0.2289
Wins
3.5
5.5
1.0
0.0
8.0
3.5
5.5
3.0
6.0
4.4 RUNTIME COMPLEXITY
RQ.,8 E Rdo, the runtime complexity of Algorithm I is O (T x (Ka x (Qa Q8) + K3 Qa)), while that of gradient descent for minimizing the cross- entropy (CE) is O (T x Ka x Qa). The additive complexity comes from 0g O (Q²) the case of surrogate learning. When deploying on an Intel Xeon E5-2670 server with 40 cores, it took SL-R circa 26 hours and 38 minutes to train the prediction model of Section 4.1 with the MCR loss on the Susy dataset for 1M batches. Under an identical setup, the cross-entropy baseline completed in circa 6 hours and 17 minutes.
Denoting the capacities
Øg 8a where O oe is
By
CONCLUSION
The optimization of losses is major challenge for the machine learning community. Unfortu- nately, most classification loss functions are only piece-wise continuous, con-differentiable and non-decomposable. So far, researchers have addressed this bottleneck by designing (hand-crafting) smooth approximative surrogate functions to those losses. In contrast to the existing work, we propose new paradigm optimizing loss functions, by defining the loss itself model that is jointly optimized with a prediction model, in a way that the smooth surrogate loss matches the non-differentiable true loss. The task is formalized and an alternating optimization algorithm is applied to learn the surrogates. The empirical results on multiple real-life datasets indicate that learning surrogates more accurate than hand-crafted explicit relaxations in diverse popular loss functions, such as AUC, FI, or Jaccard Index.
parametric
bilevel programming objective
8

---

Under review as a conference paper at ICLR 2020
REFERENCES
Kevin Bascol, Rémi Emonet, Elisa Fromont, Amaury Habrard, Guillaume Metzler, and Marc Sebban. From cost-sensitive tight f-measure bounds. In Kamalika Chaudhuri and Masashi Sugiyama (eds.), Proceedings of Machine Learning Research, volume 89 of Proceedings of Machine Learning Research, pp. 1245-1253. PMLR, 16-18 Apr 2019.
Maxim Berman, Amal Rannen Triki, and Matthew B Blaschko. The lovász-softmax loss: A tractable surrogate for the optimization of the intersection-over-uiioon measure in neural networks. In Proceedings of the IEEE Conference Computer Vision and Pattern Recognition, pp. 4413-4421, 2018.
Wei Chen, Tie yan Liu, Yanyan Lan, Zhi ming Ma, and Hang Li. Ranking measures and loss functions in learning to rank. Y. Bengio, D. Schuurmans, J. D. Lafferty, C. K. Williams, and A. Culotta (eds.), Advances in Neural Information Processing Systems 22, pp. 315-323. Curran Associates, Inc., 2009.
Yutian Chen, Matthew W. Hoffman, Sergio Gómez Colmenarejo, Misha Denil, Timothy P. Lillicrap, Matt Botvinick, and Nando de Freitas. Learning to learn without gradient descent by gradient descent. In Doina Precup and Yee Whye Teh (eds.). Proceedings of the 34th International Conference on Machine Learning, volume 70 of Proceedings of Machine Learning Research, pp- 748-756, International Convention Centre, Sydney, Australia, 06-11 Aug 2017. PMLR.
Benoît Colson, Patrice Marcotte, and Gilles Savard. An overview of bilevel optimization. Annals of Operations Research, 153(1 (:111)):33255555 2007.
Corinna Cortes and Mehryar Mohri. Auc optimization vs. error rate minimization. In Advances in Neural Information Processing Systems, pp. 313-320, 2004.
Cícero Nogueira dos Santos, Kahini Wadhawan, and Bowen Zhou. Learning loss functions for semi-supervised learning via discriminative adversarial networks. CoRR, abs/1707 07777002198, 2017.
URL httt:://aaaiiii org/ wwwpaaa./..1o///
Elad Eban, Mariano Schain, Alan Mackey, Ariel Gordon, Ryan Rifkin, and Gal Elidan. Scalable Learning of Non- Deno-oopppssbl Objectives. In Aarti Singh and Jerry Zhu (eds.), Proceedings of the 20th International Conference on Artificial Intelligence and Statistics, volume 54 of Proceedings of Machine Learning Research, pp.
Fort Lauderdale, FL, USA, 20-22 Apr 2017. PMLR.
Yang Fan, Fei Tian, Tao Qin, Xiang- Yang Li, and Tie- Yan Liu. Learning to teach. In International Conference on Learning Representations (ICLR), 2018.
Luca Franceschi, Paolo Frasconi, Saverio Salzo, Riccardo Grazzi, and Massimiliano Pontil. Bilevel programming for byperparameter optimization and meta-learning In Jennifer Dy and Andreas Krause (eds.), Proceedings of the 35th International Conference Machine Learning, volume 80 of Proceedings of Machine Learning Research, pp. 1568-1577, Stockholmsmssan, Stockholm Sweden, 10-15 Jul 2018. PMLR.
Wei Gao and Zhi-Hua Zhou. On the consistency of auc pairwise optimization. In Twenty-Fourth International Joint Conference Artificial Intelligence, 2015.
Tamir Hazan, Joseph Keshet, and David A. McAllester. Direct loss minimization for structured prediction. In D. Lafferty. C. K. Williams, J. Shawe-Taylon R. S. Zemel, and A. Culotta (eds.), Advances in Neural Information Processing Systems 23, pp. 1594-1602. Curran Associates, Inc., 2010.
Kurt Hornik. Approximation capabilities of multilayer feedforward networks. Neural Networks, 4(2): 251 257, 1991. ISSN 0893-6080.
Oluwasanmi Koyejo, Nagarajan Natarajan, Pradeep K Ravikumar, and Inderjit S Dhillon. Consis- tent binary classification with generalized performance metrics. In Z. Ghahramani, M. Welling, C. Cortes, N. D. Lawrence, and K. Q. Weinberger (eds.), Advances Neural Information Process- ing Systems 27, pp.
Curran Associates, Inc., 2014.

---

Under review as a conference paper at ICLR 2020
Ke Li and Jitendra Malik. Learning to optimize. In International Conference Learning Represen- tations (ICLR), 2017.
Zachary C. Lipton, Charles Elkan, and Balakrishnan Naryanaswamy. Optimal thresholding of classifiers maximize fl measure. In Toon Calders, Floriana Esposito, Eyke Hüllermeier, and Rosa Meo (eds.), Machine Learning and Knowledge Discovery in Databases, pp. 225-239, Berlin, Heidelberg, 2014. Springer Berlin Heidelberg. ISBN 978-3-662-44851--
Hadrien Montanelli and Haizhao Yang. Error bounds for deep relu networks using the kolmogorov- arnold superposition theorem, 2019.
Xiaozhong Pang and P Werbos. Neural network design for j function approximation in dynamic programming. arXiv preprint adap-org9986000,, 1998.
Shameem Puthiya Parambath, Nicolas Usunier, and Yves Grandvalet. Optimizing f-measures by cost-sensitive classification. In Z. Ghahramani, M. Welling, C. Cortes, N. D. Lawrence, and K. Q. Weinberger (eds.). Advances in Neural Information Processing Systems 27, pp. 2123-2131. Curran Associates, Inc., 2014.
Revalski and N. Zhivkov. Well-posed constrained optimization problems in metric spaces. Journal of Optimization Theory and Applicaations. 10. 10.1007/BF00955226. URL http://////....oo0//0000000////0
1661) Jan 1993. ISSN 1573-2878. doi:
/
Yang Song, Alexander Schwing, Richard, and Raquel Urtasun. Training deep neural networks via direct loss minimization. In Maria Florina Balcan and Kilian Q Weinherger (eds.). Proceedings of The 33rd International Conference on Machine Learning, volume 48 of Proceedings of Machine Learning Research, pp. 2169-2177, New York, New York, USA, 20-22 Jun 2016. PMLR.
VM Tikhomirov. On the representation of continuous functions of several variables as superpositions of continuous functions of one variable and addition. In Selected Works of AN Kolmogorov, pp. 383-387. Springer, 1991.
Lijun Wu, Fei Tian, Yingce Xia, Yang Fan, Tao Qin, Lai Jian-Huang, and Tie- Yan Liu. Learning to teach with dynamic loss functions. In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa-BBinnhh,, and R. Garnett (eds.), Advances in Neural Information Processing Systems 31, pp. 6466-6477. Curran Associates, Inc., 2018.
Nan Ye, Kian Ming A. Chai, Wee Sun Lee, and Hai Leong Chieu. Optimizing f-measures: tale of two approaches. In Proceedings of the 29th International Coference on International Conference on Machine Learning, ICML'12, pp. 1555-1562, USA, 2012. Omnipress. ISBN 978-1-4503-1225-11
Jiaqian Yu and Matthew Blaschko. Learning submodular losses with the lovasz hinge. In Francis Bach and David Blei (eds.), Proceedings of the 32nd International Conference on Machine Learning, volume 37 of Proceedings of Machine Learning Research, pp. 1623-1631, Lille, France, 07-09 Jul 2015. PMLR.
Manzil Zaheer, Satwik Kottur, Siamak Ravanbakhsh, Barnabas Poczos, Ruslan R Salakhutdinov, and Alexander J Smola. Deep sets. In Guyon, U. V. Luxburg, S. Bengio, H. Wallach, Fergus. S. Vishwanathan, and R. Garnett (eds.), Advances in Neural Information Processing Systems 30, Curran Associates, Inc., 2017.
pp. 3391-3401.
Xiaoxuan Zhang, Mingrui Liu, Xun Zhou, and Tianbao Yang. Faster online learning of optimal threshold for consistent f-measure optimization. In Samy Bengio, Hanna M. Wallach, Hugo Larochelle, Kristen Grauman, Nicolò Cesa-Bianchi, and Roman Garnett (eds.), Advances in Neural Information Processing Systems 31: Annual Conference Neural Information Processing Systems 2018, NewrlPS 2018, 3-8 December 2018, Montréal, Canada., pp. 3893-3903, 2018.
10


Reviews:
[{"review_id": "rJlDGZYRKH", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "In this paper, the authors propose to learn surrogate loss functions for non-differentiable and non-decomposable loss. An alternative minimization method is used for training the surrogate network and prediction model. Learning surrogate loss functions for different tasks is somewhat novel, although there are some prior works on learning the loss, e.g., [1]. \n\nPros.\n1.\tThe paper is well written and easy to follow.\n2.\tLearning a unified loss for different tasks is interesting. It has the potential to reduce human efforts to design losses.\n\nCons.\n1.\tSome important details of learning the surrogate loss are missing. The function g for extracting the latent error component is not clear. The composition function h is not provided either.\n2.\tThe details of the experiments are not clear. Are the results on the test set? How many independent runs are performed?\n3.\tLearning surrogate loss incurs additional approximation error, time complexity, and model complexity. The benefit of the trade-off is not systematically evaluated.\n\nQuestions\n1.\tThe function g for extracting the latent error component is not clear. Is it required to design for different tasks by an expert specifically? Or, does it have the same differentiable form for different tasks? Please provide the details of the function g for the different losses in the experiments.\n\n2.\tCan the proposed loss work well for multi-class classification tasks? In the experiments, only binary classification is evaluated. Multi-class classification will increase the number of classes, thus increasing the difficulty of approximation. It is better to provide MCR compared with CE on the CIFAR100 dataset for evaluation. Also, please provide the running time of CE and SL-R in the same running environment.\n\n3.\tIs the results in Table 3 on the test set? CE has fewer parameters compared with the proposed loss, why does SL-R have better generalization performance compared with CE? How many independent runs performed in experiments?\n\n4.\t CE does not need training the loss compared with SL-R. Please provide the running time of CE in the same environment for a fair comparison. \n\n5.\tThe time complexity analysis treats extracting function g as a black-box function. However, the complexity of function g depends on the tasks. Please provide a detailed discussion about time complexity for different tasks (e.g., AUC, F1, MCR for multi-class classification, and ranking tasks). \n\n\n[1] Learning Loss Functions for Semi-supervised Learning via Discriminative Adversarial Network, 2017\n\n", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I did not assess the derivations or theory."}, "extra_text": {}}, {"review_id": "S1xPxXH3tr", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper proposes a method of learning loss functions in addition to the learning of predictors. Since it's not easy to optimize loss functions that evaluate the accuracy, surrogate loss functions have been widely employed. The design of the surrogate loss is problem-dependent, and handcraft is required. This paper tries to tackle this problem from the viewpoint of meta-learning, i.e., the surrogate loss learning. Typically, deep neural networks (DNN) are used to design a surrogate loss that approximates the original loss while maintaining the tractability of the optimization. Some convergence properties of the proposed method are analyzed. Some empirical studies showed the efficiency of the proposed method to the state-of-the-art baselines. \n\nThe design of the surrogate loss is important for machine learning problems. However, the proposed method in this paper seems an ad-hoc approach rather. For example, the 0-1 loss is often replaced with convex loss functions such as the hinge loss or logistic loss. Using these surrogate loss functions, the statistical properties of the predictors obtained from 0-1 loss are maintained. See the following paper for details.\nP. L. Bartlett, et al., (2006), Convexity, Classification, and Risk Bounds, Journal of the American Statistical Association March , Vol. 101, No. 473. \n\nOn the other hand, the current approach does not have such a theoretical guarantee for each learning problems. Though certainly, the proposed method is widely applicable to many problems, there is no theoretical guarantee. Theorem 1 in page 5 shows the convergence property. However, the number of iterations, K_beta, should tend to infinity. This is not a practical operation in the learning algorithm", "extra_scores": {"experience_assessment": "I have published in this field for several years.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I did not assess the derivations or theory.", "review_assessment:_checking_correctness_of_experiments": "I did not assess the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I made a quick assessment of this paper."}, "extra_text": {}}, {"review_id": "HkgIEkppFH", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": null, "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "In this paper authors propose to jointly optimize a critic, that estimates some non-differentiable objective (or an objective with intractable derivatives and/or derivatives that are 0 almost everywhere). Authors conduct numerous experiments, and show improvements over some sota methods, and maybe more importantly - provide a unified way of achieving these across multiple metrics. Paper is well written, very easy to understand and in reviewers opinion, a nice, simple story worth sharing.\n\n\nMajor concerns:\n\nThe theoretical result provided is just a citation of an existing proof, rather than a new contribution. More importantly however, the setup considered strongly violates the assumptions of the theorem, for example assumption (b) does not hold for the neural networks, as there are continuum many global minima (imagine having a unit in a neural net, that has a huge negative bias, which causes it to always be \"turned off\" by relu, then any weight on top of it will have the same final loss value; or simply notice that relu(a*x)=a*relu(x) if x>0, and so you can always \"push\" the norm of weights from one layer to the next one without affecting the outcome etc.), and so argmin is not a singleton, but the set of exactly same power as the whole parameter space (since for each k there exists a bijection from R^k to R, and R is of continuum power). This property is not a mild assumption, but rather a critical element guaranteeing convergence of such systems, with powerful universal approximators, one cannot hope for such strong convergence results without actually analysing the approximators family. Reviewer strongly believes this should be either removed completely, or just briefly mentioned, rather than made a strong statement in the paper. It is an empirical work, and stands strong on its own rights, there is no need to add theorems with assumptions that are never satisfied in the proposed scenario.\n\nResults provided use somewhat non-standard datasets for deep learning, and as such it is hard to asses statistical significance of the differences reported; while the test datasets sizes are big enough to trust error to 1e-3 level, they are heavily imbalanced and relatively low dimensional problems, which have proven to be hard for neural network many times in the past, consequently I would expect to see confidence intervals or stds of each result, at least for Table 3. The problem becomes even more severe for metrics such as F1 which do not decompose additively and so can be very sensitive to the (false) positive rates values - reported improvements might disappear once these are introduced, but even if one does not outperform hand-crafted proxies for specific objectives, having a unified method that is on-part with those in black-box scenario is a good result (I would argue that even if all the results are slightly worse, it is still worth publishing).\n\nI find it a bit disappointing, that authors did not try to analyse trained models, it would be invaluable to see what kind of aggregation g and h came up with, that is well aligned with losses such as F1 or JAC.\n\n\nMinor concerns:\n\nThe work resembles closely methods of error critic learning - where one uses an update direction coming from a model, that regresses towards the loss itself, or the gradient of the loss (is available), see:\n- Neural Network Design for J Function Approximation in Dynamic Programming (Pang and Werbos paper from '98)\n- Sobolev Training of Neural Networks (from NIPS; more precisely \"Critic\" baseline, which has the same functional form as the loss presented in the paper, if applied at the very top of the network only)\nIt might be worth discussing in the paper.\n\n\nOverall I recommend weak acceptance, and encourage authors to address some of the concerns raised above.\n\n**Update**\n\nBased on discussion, corrections and new additions, I recommend acceptance of the above work.", "extra_scores": {"experience_assessment": "I have published in this field for several years.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I carefully checked the derivations and theory."}, "extra_text": {}}]

Author rebuttal:

Meta-review: Unfortunately, this was a borderline paper that generated disagreement among the reviewers.  After high level round of additional deliberation it was decided that this paper does not yet meet the standard for acceptance.  The paper proposes a potentially interesting approach to learning surrogates for non-differentiable and non-decomposable loss functions.  However, the work is a bit shallow technically, as any supporting theoretical justification is supplied by pointing to other work.  The paper would be stronger with a more serious and comprehensive analysis.  The reviewers criticized the lack of clarity in the technical exposition, which the authors attempted to mitigate in the rebuttal/revision process.  The paper would benefit from additional clarity and systematic presentation of complete details to allow reproduction.
Decision: Reject