Year: 2019

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.

heading: 1 INTRODUCTION
text: In reality, a large set of loss functions cannot be directly minimized by gradient-based methods because they are either piece-wise continuous, non-differentiable, or 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), F1 measure (F1), Jaccard Similarity Index (JAC), Average Precision (AP), Equal Error Rate (EER), or the Mathew Correlation Coefficient (MCC). On the other hand, learning-to-rank models are measured through the Normalized Discounted Cumulative Gain (NDCG), or the Mean Average Precision (MAP). To illustrate the point, Figure 1 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. It is worth pointing out that non-gradient-based approaches, such as 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 a seamless manner. Researchers have so far focused on deriving smooth surrogate relaxations (approximations) to the true loss functions (Berman et al., 2018; Eban et al., 2017), in a way that first- and second-order 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-classification 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 a 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 a bilevel programming task (Colson et al., 2007; Franceschi et al., 2018) that is trained through a concurrent optimization algorithm. This paper shows that universal surrogates, which are trained without paying attention to a specific dataset, are sub-optimal compared to surrogates learned in a per-dataset manner. Results on nine datasets demonstrate that learning surrogates produces more accurate prediction models than state-of-the-art baselines with regard to diverse loss functions.

heading: 2 RELATED WORK
text: Due to the non-differential and non-continuous nature of most real-life losses, early works deployed the proxies of the miss-classification rate (e.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 a 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 F1 focused instead on the empirical utility maximization paradigm (Ye et al., 2012). Later on, researchers addressed F1 by optimizing the hyper-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 et al., 2018) 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 to 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., 2016). Unfortunately, per-instance dis-aggregations are not trivially feasible in other cases (e.g. F1), making the direct loss optimization technique an impractical 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 a confusion matrix (e.g. true positives, true negatives etc.) and combines the building block relaxations to create a 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 as a smooth approximation to the Jaccard index (Berman et 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 to enable a gradient-based learning of the teacher/controller (Wu et al., 2018). However, 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., 2017), which proposes to directly learn the amount of update values that are applied to the parameters of the prediction model. In the proposed framework a 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 applicability 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.
An alternative approach towards learning loss functions analyzes the usage of discriminative adversarial networks (dos Santos et al., 2017). The idea focuses on discriminating the probability of a given target variable value into either being an estimated target or the true one, therefore acting as a 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 state-of-the-art relaxations, with regards to minimizing popular binary classification losses, such as AUC, F1, Jaccard Index and the miss-classification rate.

heading: 3 SURROGATE LEARNING
text: Data mini-batches (x, y) := {(x1, y1), . . . , (xN , yN )} ofN instances each, with features x ∈ RN×M and ground-truth targets y ∈ YN , are drawn from a dataset D with a sampling distribution PD (x, y), where typically P is the uniform distribution. The target domain can be binary y ∈ {0, 1}N , or nominal among C categories y ∈ {1, . . . , C}N . Ultimately, the purpose of a prediction model is to estimate a target variable ŷ(x;α) : RN×M → RN , where the prediction model has parameters α. The estimations ŷ ∈ RN need to accurately match the given ground-truth target variable y ∈ YN with regards to a desired loss function ` (y, ŷ) : RN × YN → R. Therefore, supervised learning focuses on computing the optimal parameters α∗ that minimize the following objective.
α∗ = argmin α E(x,y)∼PD(x,y) ` (y, ŷ(x;α)) (1)
To minimize the aforementioned objective through first- or second-order optimization, it is necessary to define the gradients ∂`∂α . Unfortunately, in most real-world cases the loss represents step functions that are only piece-wise continuous (MCR, F1, AUC, etc.). Therefore, the derivatives are either zero, or undefined at the function steps, which prohibits a 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 a relaxation of the miss-classification rate. Yet, such non-parametric relaxation functions are not trivially derivable when the loss is nondecomposable 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 ˆ̀ for the surrogate of every loss function `, we propose a method that parameterizes and learns the surrogate for any demanded loss function 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-invariant set model, whose output must remain fixed given different orders of instances within a dataset mini-batch, i.e. ˆ̀(y1, . . . , yN , ŷ1, . . . , ŷN ) = ˆ̀ ( yπ(1), . . . , yπ(N), ŷπ(1), . . . , ŷπ(N) ) for any index permutation π. Our method uses the KolmogorovArnold representation theorem (Tikhomirov, 1991) and defines the surrogate loss of Equation 2 as a composition function h of per-instance functions g. This type of aggregation was recently applied to learning neural networks over sets of instances (Zaheer et al., 2017).
ˆ̀(y, ŷ) = h
( 1
N N∑ i=1 g (yi, ŷi)
) (2)
where g : R2 → RQ, and h : RQ → R are deep forward neural networks. The first function g extracts Q latent error components for the predictions on each instance (e.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.
It has been proven that with sufficient capacities for g and h, any permutation-invariant set function (hence any loss) can be approximated via the Kolmogorov-Arnold (KA) representation theorem (Za-
heer et al., 2017). In particular, it is worth mentioning that due to being an instance of the KA superposition, the proposed surrogate model of Equation 2 benefits from existing error bound guarantees of such a 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.

heading: 3.1 UNIVERSAL SURROGATES
text: The first intuition is to learn the weights β of surrogate network (a.k.a. the functions g and h) in a universal manner by solving the objective of Equation 3. In other words, we can attempt to make any surrogate loss ˆ̀behave as any true loss ` over the space of all possible batches of randomly-drawn true y and estimated ŷ targets. Focusing on binary classification losses, we sample the ground truth from a Bernoulli distribution, and respective estimated targets from a Gaussian distribution. Furthermore, the meta-loss L : R × R → R measures the distance between the true and surrogate losses and is practically implemented as an L1 norm.
βUniversal = argmin β
E y∼B(p)N×1, ŷ∼N (µ,σ2)N×1 L ( ` (y, ŷ) , ˆ̀(y, ŷ ; β) ) (3)
The challenge of learning a universal surrogate is in ensuring that the sampling hyper-parameters (p, µ, σ) would lead to drawing (y, ŷ) that match the specific target distribution of a concrete dataset. Therefore, we empirically found out that it is sub-optimal to universally relax the whole space of the true loss. Instead, as future sections will detail, it is more efficient to design a relaxation in a dataset-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.

heading: 3.2 SURROGATE LEARNING AS BILEVEL PROGRAMMING
text: A different approach from the universal surrogate is to associate a surrogate loss to each dataset. In that manner, the surrogate creates a smooth relaxation only around the dataset-relevant regions of the target (y, ŷ(x;α)) space. We propose to jointly optimize the prediction model parameters (α) and the surrogate loss parameters (β) through the following optimization:
α∗ = argmin α E(x,y)∼PD(x,y) ˆ̀(y, ŷ (x ; α) ; β) (4)
β∗ = argmin β
E(x,y)∼PD(x,y) L ( ` (y, ŷ (x;α)) , ˆ̀(y, ŷ (x;α) ; β) ) (5)
The rationale is that Equation 4 optimizes 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 can be addressed by treating both objectives of Equations 4 and 5 as a concurrent relationship, in a way that we can optimize them jointly and simultaneously. This dual objective is an instance of a bilevel programming problem (Colson et al., 2007; Franceschi et al., 2018). Algorithm 1 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 Kβ steps (lines 9 − 12). To illustrate the mechanism, Figure 2 provides a minimalistic example of optimizing jointly the bilevel programming objectives for training a single-parameter model on a single-feature binary dataset. The plots show the effect of minimizing the surrogate (magenta), as the parameter α is updated towards the minimum of the surrogate. At the same time, we observe that the surrogate is updated to match the true miss-classification-rate loss (cyan) at the current parameter value. The model converges close to the optimal true loss after applying the steps of Algorithm 1.

heading: 3.3 NOTE ON CONVERGENCE
text: It is possible to analyze the convergence of Algorithm 1 following existing proofs for bilevel programming (Revalski & Zhivkov, 1993; Franceschi et al., 2018), since Equations 4-5 can be rewritten
Algorithm 1: Surrogate Learning Input : Dataset D, Loss `, Training epochs T , Update steps Kα,Kβ , Learning rates ηα, ηβ .
1 Initialize α, β 2 for 1, . . . , T do 3 α(0) ← α 4 for k = 1, . . . ,Kα do 5 Sample batch (x, y) ∼ PD (x, y) 6 α(k) ← α(k−1) − ηα(k−1)∇α ˆ̀ ( y, ŷ ( x ; α(k−1) ) ; β ) 7 end 8 α← α(Kα), β(0) ← β 9 for k = 1, . . . ,Kβ do
10 Sample batch (x, y) ∼ PD (x, y) 11 β(k) ← β(k−1) − ηβ(k−1)∇βL ( ` (y, ŷ (x;α)) , ˆ̀ ( y, ŷ (x;α) ; β(k−1) )) 12 end 13 β ← β(Kβ) 14 end
Return : Prediction model ŷ (x; α)
in a standard bilevel programming form: minα∈A ˆ̀(α, β∗ (α)), β∗ (α) = argminβ(α) L (α, β (α)). However, the assumptions of the proofs offered by the related work are violated in the case where both considered models l̂,L are deep neural networks (Franceschi et al., 2018). For example, the assumption necessitating the optimal loss parameters argminβ(α) L (α, β (α)) to represent a singleton for every α ∈ A would not hold as there exist continuum many global minima. Nevertheless, we empirically observed that the proposed bilevel optimization problem of Equations 4-5 converges well in practice under the optimization regime of Algorithm 1, visually observable through the exemplifying convergence plots of Section 4.2.

heading: 4 EXPERIMENTS

heading: 4.1 PROTOCOL
text: The experiments are focused on a collection of publicly-available binary classification datasets, whose statistics are presented in Table 1. We split the data randomly into 80% training and 20% testing instances. The prediction model ŷ has an architecture of [100, 30, 10, 1] neurons with LeakyReLU activation, where batch normalization was applied at each layer. In addition, after each batch normalization we added a drop-out regularization layer with the drop rate set to 0.2. The surrogate network component g 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 ηα = ηβ = 10−5.
Furthermore, to improve the convergence stability we clipped the gradients by a 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 `. Data batches were drawn in a stratified random fashion (50% positive and 50% negative) with a mini-batch size N = 100. The update steps were chosen as Kα = 3 and Kβ = 10 and Algorithm 1 was run for 300000 iterations. We conducted experiments with 7 binary classification measures, namely AUC, Equal Error Rate (EER), Average Precision (AP), Miss-classification rate (MCR), F1, Mathew Correlation Coefficient (MCC), Jaccard Coefficient (JAC). All the measures are converted to a loss by a 1− x conversion, except for EER and MCR. For the losses that demand converting the predictions ŷ into binary values (e.g. MCR, F1, MCC), we used a thresholding ŷ ≥ γ, where γ was optimized for each dataset and loss. The following results of Sections 4.2-4.3 present the performance on the test sets.

heading: 4.2 ABLATION OF SURROGATE MODELS
text: This section addresses whether the surrogate should be trained in a universal manner (Section 3.1), or whether they should be optimized on a 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-U): Learn the surrogate ˆ̀using Equation 3 with hyperparameters p = 0.5 (due to stratified sampling), µ = 0, σ = 1, and then train only the prediction model f by minimizing ˆ̀ through Equation 4.
• Learned from Scratch (SL-S): Initialize the surrogate network ˆ̀from scratch (randomly), then optimize both Equations 4-5 using Algorithm 1.
• Refined Surrogate (SL-R): Initialize the surrogate with the universal solution of Equation 3, and then refine the surrogate by optimizing both Equations 4-5 using Algorithm 1.
Table 2 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 ones trained in a per-dataset manner (SL-R, SL-S), except for the AUC loss. In addition, the results indicate that there is not a major difference in terms of accuracy between SL-R and SL-U. The refined surrogate improves the convergence of the optimization procedure, as Figure 3 shows.

heading: 4.3 COMPARISON WITH THE STATE-OF-THE-ART
text: In order to demonstrate the usefulness of 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 of 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, 2015), and the cost-sensitive reduction (Puthiya Parambath et al., 2014) serves as the surrogate of F1. All the aforementioned baselines, except the cost-sensitive reduction, have no further hyper-parameters and were implemented based on the authors’ codes. For a ceteris paribus comparison, we used the same capacity prediction
model for the baselines, the same batch size, i.e. the same protocol as in Section 4.1. The hyperparameter of the cost-sensitive reduction, namely the positive weight coefficient was tuned among {0.3, 0.9, 2.7, 8.1, 24.3, 72.9} on a separate validation set. To ensure that the baselines converged, we trained them for 1M iterations with a learning rate of 10−4. Table 3 presents the results over the 9 datasets, where the refined surrogate learning SL-R is compared to the 5 state-of-the-art relaxation methods for 4 losses. The evidence suggests that surrogate learning yields more accurate prediction models than the state-of-the-art.

heading: 4.4 RUNTIME COMPLEXITY
text: Denoting the capacities as α ∈ RQα , β ∈ RQβ , the runtime complexity of Algorithm 1 is O (T × (Kα × (Qα +Qβ) +Kβ ×Qβ)), while that of gradient descent for minimizing the crossentropy (CE) is O (T ×Kα ×Qα). The additive complexity comes from ∂ ˆ̀∂ŷ ∂ŷ ∂α where O ( ∂ ˆ̀ ∂ŷ ) is O (Qβ) in 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.

heading: 5 CONCLUSION
text: The optimization of losses is a major challenge for the machine learning community. Unfortunately, most classification loss functions are only piece-wise continuous, non-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 a new paradigm to optimizing loss functions, by defining the loss itself as a parametric 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 as a bilevel programming objective and an alternating optimization algorithm is applied to learn the surrogates. The empirical results on multiple real-life datasets indicate that learning surrogates is more accurate than hand-crafted explicit relaxations in diverse popular loss functions, such as AUC, F1, or Jaccard Index.

Review summaries:
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. 

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