Title: GRADIENT-BASED LEARNING FOR THE F -MEASURE AND OTHER PERFORMANCE METRICS

Abstract: Many important classification performance metrics, e.g. the F -measure, are nondifferentiable and non-decomposable, and are thus unfriendly to the gradient descent algorithm. Consequently, despite their popularity as evaluation metrics, these metrics are rarely optimized as training objectives in neural network community. In this paper, we propose an empirical utility maximization scheme with provable learning guarantees to address the non-differentiability of these metrics. We then derive a strongly consistent gradient estimator to handle nondecomposability. These innovations enable end-to-end optimization of these performance metrics with the same computational complexity as optimizing a decomposable and differentiable metric, e.g. the cross-entropy loss.

1. INTRODUCTION:

Different classification performance metrics are capable of revealing different aspects of a classifier's behavior. For example, the F -measure (Van Rijsbergen (1974) ), compared to performance metrics such as accuracy, is better at evaluating a classifier's performance when it encounters a sample belonging to a class that occurs with low frequency. Ideally, we can acquire a classifier with very tailored behavior by optimizing the classifier with respect to a carefully chosen performance metric. Unfortunately, many performance metrics, e.g. the F -measure, are non-differentiable and non-decomposable, which renders it very difficult to optimize neural network classifiers with these metrics as training objective.

In this paper, we propose a method that enables gradient-based learning for these performance metrics. Our contributions are the following:

• We propose a learning algorithm based on empirical utility maximization for a class of performance metrics and prove its generalization and consistency.

• We propose a strongly consistent gradient estimator that enables efficient gradient-based maximization of empirical utility.

• We demonstrate experimentally that the binary F 1 score of neural network classifiers can be efficiently optimized on datasets of decent scale and complexity.

We organize this paper as the following. In Section 2, we will sketch our method for the binary F 1 score to provide an overview. In Section 3, we will present our method in its general form. We review related work in Section 4 and provide experiment results in Section 5.

2 GRADIENT-BASED LEARNING FOR THE BINARY F 1 SCORE 2.1 PROBABILISTIC CLASSIFIER Given a feature vector x ∈ X ⊂ R N , a probabilistic classifier h first infers a posterior p(•|x) over a discrete output space Y and then samples its output from the posterior, i.e. h(x) ∼ p(•|x). In practice, p(•|x) is typically the output of a neural network with softmax layer on its top.When the posterior is parameterized, e.g. being implemented as a neural network, we denote it as p θ (•|x) and the corresponding probabilistic classifier as h θ .

Given a posterior p(•|x), a deterministic classifier can result from the inference rule h(x) = argmax y∈Y p(y|x).The difference between probabilistic and deterministic inference rules is negligible when the posterior is very concentrated. Although deterministic classifiers are more popular in the literature, in this paper we only consider probabilistic classifiers and leave it as future work to investigate the case where a probabilistic classifier is replaced by a deterministic one.

2.2. F -MEASURE:

Consider the case of binary classification, where Y = {0, 1} with 1 and 0 respectively corresponding to the positive and negative class. Given a dataset D = {(x 1 , y 1 ), ..., (x n , y n )} consisting of n i.i.d. pairs of feature vector and ground truth, let ŷi denote the label predicted by a classifier h given x i (not necessarily deterministically). Let ŷ = (ŷ 1 , ..., ŷn ) and y = (y 1 , ..., y n ). Then the truepositive, false-positive, false-negative and true-negative rate corresponding to ŷ and y are defined as

tp( ŷ, y) := 1 n n i=1 I (ŷ i = 1 ∧ y i = 1) fp( ŷ, y) := 1 n n i=1 I (ŷ i = 1 ∧ y i = 0) fn( ŷ, y) := 1 n n i=1 I (ŷ i = 0 ∧ y i = 1) tn( ŷ, y) := 1 n n i=1 I (ŷ i = 0 ∧ y i = 0)

where I denotes indicator function. The precision and recall are defined as

EQUATION

where p + D := 1 n n i=1 I(y i = 1) denotes the proportion of samples in D that belong to positive class. The binary F -measure is defined as (Van Rijsbergen (1974) ):

EQUATION

or equivalently,

F β ( ŷ, y) = (1 + β 2 ) • p + D -fn( ŷ, y) (1 + β 2 )p + D -fn( ŷ, y) + fp( ŷ, y) β > 0 (3)

which is more convenient for our purpose.

We will refer to F β ( ŷ, y) as the data-dependent binary F β -measure because it is evaluated on a specific set of data with pairs of ground truth and prediction vectors. F β is non-differentiable because it is a composition of indicator functions. Nor does it decompose over samples in D. More precisely, we are not aware of any function f β that only depends on per sample ground-truth and prediction such that

F β ( ŷ, y) = 1 n n i=1 f β (ŷ i , y i )

In the following we propose an empirical utility maximization scheme for optimizing the F βmeasure of probabilistic classifiers. For ease of exposition, in this section we focus on the binary F 1 -measure, a.k.a. the binary F 1 score. In Section 3, we will extend the method presented in this section to a family of non-decomposable and non-differentiable performance metrics, including F βmeasure for multi-class classification.

2.3. GRADIENT-BASED LEARNING FOR THE BINARY F 1 SCORE:

We consider a parameterized binary probabilistic classifier h θ . By linearity of expectation and the i.i.d. assumption, E ŷ,y [fp( ŷ, y)] = P(ŷ = 1 ∧ y = 0) where the expectation is taken over all datasets with a fixed size n and all possible predictions of h θ . Similarly, E ŷ,y [fn( ŷ, y)] = P(ŷ = 0 ∧ y = 1). With these approximate identities, we have the following approximation of F 1 ( ŷ, y):

EQUATION

which implies that the F 1 score of any predictions of h θ on any sufficiently large dataset is close to F1 (h θ ). We call F1 (h θ ) the expected utility of the F 1 score and will state the precise meaning of F 1 ( ŷ, y) ≈ F1 (h θ ) in Section 3. The key point is that we can optimize F1 (h θ ) instead of F 1 ( ŷ, y) if we are interested in the F 1 score of h θ on sufficiently large datasets. However, fn(h θ ) and fp(h θ ) are unknown because they are expectations taken over data distribution (and the classifier's posterior). Consequently, we have to estimate fn(h θ ) and fp(h θ ) by sampling from data distribution in order to estimate F1 (h θ ), as the following.

Let p + := P(y = 1) denote the probability that a positive sample occurs, which can be estimated by the frequency of positive samples in a training set D. Let n + := (x,y)∈D I(y = 1) denote the number of positive samples in the training set. Assume that the data distribution admits a density function (i.e. the data distribution is absolutely continuous w.r.t. the Lebesgue measure), and denote its density function by p. We have the following unbiased estimator of fn(h θ ):

EQUATION

where x + 1 , ..., x + n + are the feature vectors of samples belonging to the positive class in trainingset D. Similarly,

fp(h θ ) = P (ŷ = 1 ∧ y = 0) ≈ p - n - n - i=1 p θ (1|x - i ) := fp D (h θ )

where p -:= P(y = 0), n -:= (x,y)∈D I(y = 0), and x - 1 , ..., x - n are the feature vectors of samples in D belonging to the negative class. Thus F1 (h θ ) can be estimated as the following:

EQUATION

We will state the precise meaning of F1 (h θ ) ≈ FD (h θ ) in Section 3. Interestingly, although fn( ŷ, y) and fp( ŷ, y) are not differentiable, the estimators of their expectations, fn D (h θ ) and fp

D (h θ ), are differentiable w.r.t. θ if p θ is differentiable. Because FD (h θ ) is differentiable w.r.t. fn(h θ ) and fp(h θ ), ∇ θ FD (h θ

) can be computed by chain rule. Consequently, gradient descent can be applied to optimize FD (θ).

We call FD (θ) the empirical utility of the expected utility F1 (h θ ). They correspond to empirical and expected risk in the classical empirical risk minimization principle of statistical learning theory (Vapnik (1992) ). We use the term "empirical utility maximization" because we would like to maximize, instead of minimize these performance metrics. There are two fundamental questions for every empirical risk minimization style learning algorithm, as the number of samples increases:

• Generalization. Given h θ , does FD (h θ ) → F1 (h θ ) as |D| → ∞? • Consistency. Does argmax θ FD (h θ ) → argmax θ F1 (h θ ) as |D| → ∞?

We will address these two questions at the end of Section 3. For the moment let us consider a practical issue: how to maximize empirical utility FD (h θ ) efficiently with gradient descent?

2.4. GRADIENT ESTIMATOR:

In order for the approximation in Eq. 6 to be accurate, |D| has to be sufficiently large. In order to optimize FD (h θ ) efficiently via minibatch gradient descent, ∇ θ FD (h θ ) has to be estimated by

∇ θ FB (h θ ), where B ⊂ D is a mini-batch, such that E B [∇ θ FB (h θ )] = ∇ θ FD (h θ ). Sup- pose FD (h θ ) is decomposable, i.e. there is a per-sample loss function f such that FD (h θ ) = 1 |D| (x,y)∈D f (p θ (x), y)

, then it simply follows from linearity of differentiation and expectation that the requirement is satisfied. However, as FD (h θ ) is non-decomposable, it becomes unlikely that ∇ θ FB (h θ ) is an unbiased estimator of ∇ θ FD (h θ ). Fortunately, as a consequence of Theorem 1, ∇ θ FB (h θ ) is a strongly consistent estimator of ∇ θ FD (h θ ) when |D| is sufficiently large. More precisely,

P lim |B|→∞ ∇ θ FB (h θ ) = lim |D|→∞ ∇ θ FD (h θ ) = 1 (7)

Thus ∇ θ FB (h θ ) is almost as good as an unbiased estimator. More interestingly, the error incurred by estimating ∇ θ FD (h θ ) with ∇ θ FB (h θ ) can be further controlled. In the following we omit the dependence on h θ for brevity. Let 

φ D := ( fn D (h θ ), fp D (h θ )) ∈ R 2 and φ B := ( fn B (h θ ), fp B (h θ )) ∈ R 2 .

∇ θ FB = ∇ φ B FB J B = ∇ φ D FD + J D + E = ∇ φ D FD J D + ∇ φ D FD E + J D + E (8)

where

∇ φ D FD • J D is the true gradient and • E is negligible. The error E = J B (h θ ) -J D (h θ )

is intrinsic in the sense that it results immediately from estimating ∇ θ fn D (h θ ) and ∇ θ fp D (h θ ) with ∇ θ fn B (h θ ) and ∇ θ fp B (h θ ) and it is always present in mini-batch gradient descent because 

E[∇ θ fn B (h θ )] = ∇ θ fn D (h θ ) and E[∇ θ fp B (h θ )] = ∇ θ fp D (h θ ). However, we can control the error • J D because | • J | ≤ || J || • | |

p + ← 1 |D| (x,y)∈D I(y = 1) p -← 1 |D| (x,y)∈D I(y = 0) while terminating criterion not satisfied do Sample B + = {(x + 1 , 1), ..., (x + b , 1)} from D Sample B -= {(x - 1 , 0), ..., (x - b , 0)} from D fn ← p + b b i=1 p θ (0|x + 1 ) fp ← p - b b i=1 p θ (1|x - 1 ) δ ← ∇ θ F 1 (fn, fp) -λ • |θ| θ ← θ + α • δ end while

3. GRADIENT-BASED LEARNING FOR A CLASS OF PERFORMANCE METRICS:

The binary F -measure in fact belongs to a class of performance metrics that are well behaved functions of the confusion matrix. In this section, we propose a gradient-based learning algorithm that extends the approach illustrated in previous section to this class of performance metrics. We state theorems concerning the generalization and consistency of the proposed algorithm as well. We defer all proofs to appendix. We begin with a specification of this class of performance metrics, which relies on the definition of confusion matrix: Definition 1. Given a dataset D = {(x 1 , y 1 ), ..., (x n , y n )}, let y = (y 1 , ..., y n ) denote the vector of ground truth and ŷ = (ŷ 1 , ..., ŷn ) denote a vector of classifier predictions. Then the corresponding data-dependent confusion matrix C( ŷ, y) is defined as

C( ŷ, y) ij := 1 n n k=1 I (ŷ k = i ∧ y k = j) 0 ≤ i, j ≤ |Y| -1

In the case of binary classification,

C( ŷ, y) = tn( ŷ, y) fn( ŷ, y) fp( ŷ, y) tp( ŷ, y)

Let P be a probability measure induced by data distribution and a probabilistic classifier h θ over X × Y × Y, i.e. triples of feature vector, ground truth and classifier prediction. Let C(h θ ) be the entry-wise expectation of C( ŷ, y) over P, referred to as the expected confusion matrix. Formally,

C(h θ ) ij := E I(h θ (x) = i ∧ y = j) = P(h θ (x) = i ∧ y = j) 0 ≤ i, j ≤ |Y| -1

As in Section 2, given a training set D, we have the following unbiased estimator of C(h θ ), referred to as the empirical confusion matrix:

ĈD (h θ ) ij = p j n j nj k=1 p θ (i|x j k ) 0 ≤ i, j ≤ |Y| -1

where n j := (x,y)∈D I(y = j), p j := nj |D| , and x j 1 , ..., x j nj are the feature vectors of samples that belong to the j-th class. Almost sure convergence follows from the law of large number:

P lim |D|→∞ C( ŷ, y) ij = C(h θ ) ij = 1 P lim |D|→∞ ĈD (h θ ) ij = C(h θ ) ij = 1 (9)

The confusion matrix is well-defined for both single-label and multi-label classification (although these two settings impose different constraints on its entries). Many performance metrics are functions of the confusion matrix. For example, the accuracy of h θ is |Y| i=1 Cii (h θ ). The F β measure for multi-class classification can be defined in term of entries of the confusion matrix as the following. We first define for every class the data-dependent false positive and false negative rate as

fp i = j =i C ij fn i = j =i C ji i = 1, ..., |Y|

where we omit the dependence on ŷ and y for brevity. The data-dependent macro and micro Fmeasure (Parambath et al. ( 2014)) are defined in term of fp i and fn i as

F macro β = 1 + β 2 |Y| |Y| i=1 p i -fn i (1 + β 2 )p i -fn i + fp i β > 0 F micro β = (1 + β 2 ) • |Y| i=1 p i - |Y| i=1 fn i (1 + β 2 ) |Y| i=1 p i - |Y| i=1 fn i + |Y| i=1 fp i β > 0

Replacing C( ŷ, y) by C(h θ ) and Ĉ(h θ ) in these definitions will respectively result in the expected and empirical F -measure.

We now specify the class of performance metrics that we are interested in, namely the class of well-behaved performance metrics. In the following, we will consider C( ŷ, y), C(h θ ) and ĈD (h θ ) as vectors of dimension |Y| × |Y| and identify a performance metric with a function that maps |Y| × |Y|-dimensional vectors to real values. Definition 2. We say that a performance metric F : K → R, where K is a compact subset of R |Y|×|Y| , is well-behaved if F is continuously differentiable on K.

Please refer to appendix for a non-exhaustive list of well-behaved performance metrics. Importantly, the binary F 1 score and the macro and micro F -measure are well-behaved performance metrics (proof deferred to appendix).

Given a well behaved performance metric F , its corresponding data-dependent, expected and empirical utility are respectively defined as F (C( ŷ, y)), F ( C(h θ )) and F ( Ĉ(h θ )). The following theorem establishes asymptotic equivalence between these three kinds of utilities. Theorem 1. If F is a well-behaved performance metric and C D is a strongly consistent estimator of C, i.e.

P lim |D|→∞ (C D ) ij = C ij = 1 0 ≤ i, j ≤ |Y| -1 then F (C D ) is a strongly consistent estimator of F (C), i.e. P lim |D|→∞ F (C D ) = F (C) = 1

As a consequence of this theorem, it follows from Eq. 9 that

P lim |D|→∞ F C( ŷ, y) = F C(h θ ) = 1 P lim |D|→∞ F ĈD (h θ ) = F C(h θ ) = 1

i.e. both F (C( ŷ, y)) and F ( Ĉ(h θ )) are strongly consistent estimators of (converge w.p. 1 to) F ( C(h θ )). As a special case,

P lim |D|→∞ F 1 ( ŷ, y) = F1 (h θ ) = 1 P lim |D|→∞ F1 (h θ ) = F1 (h θ ) = 1

which justifies Eq. 4 and Eq. 6 when the dataset of interest is sufficiently large. Next we consider the issue of gradient estimation in this general setting.

Theorem 2. If F is a well behaved performance metric, then ∇ θ F ( ĈB (h θ )) is a strongly consistent estimator of ∇ θ F ( C(h θ )), where B ⊂ D is a mini-batch. More precisely,

P lim |B|→∞ ∇ θ F ĈB (h θ ) = ∇ θ F C(h θ ) = 1

As proved in Chen & Luss (2018), many convergence guarantees for stochastic gradient descent with unbiased gradient estimators holds for stochastic gradient descent with strongly consistent gradient estimators with probability 1. As illustrated in Eq. 8, batch normalization and weight decay can help control the noise of estimator. Please refer to Algorithm 2 for the resultant algorithm.

Finally, we state two theorems concerning the generalization and consistency of Algorithm 2. Rates of convergence are omitted for brevity. Theorem 3 (Generalization). For a well behaved performance metric F , for all > 0, lim

|D|→∞ P F ( ĈD (h θ )) -F ( C(h θ )) < = 1

Theorem 4 (Consistency). For a well behaved performance metric F , with appropriate constraints on the capacity of parametric model p θ (see the proof for details), we have that for all > 0, lim

|D|→∞ P arg max θ F ĈD (h θ ) -arg max θ F C(h θ ) < = 1

i.e. Algorithm 2 is consistent. 

B i = {(x i 1 , i), ..., (x i b , i)} from D Compute p θ (•|x i 1 ), ..., p θ (•|x i b ) end for for i = 1, ..., |Y| do for j = 1, ..., |Y| do C ij ← pj b b k=1 p θ (i|x j k ) end for end for δ ← ∇ θ F (C) -λ|θ| θ ← θ + α • δ end while

4. RELATED WORK:

The optimization of non-decomposable and non-differentiable performance metrics, especially Fhas been extensively studied. The heuristic algorithm considered in Jansche ( 2005) and Pastor-Pellicer et al. ( 2013) is essentially Algorithm 1 without techniques that stabilize gradient estimation. However, Jansche (2005) and Pastor-Pellicer et al. (2013) are not very well motivated theoretically and provide little mathematical insight into the heuristic. Also, as shown in Section 5, applying this heuristic algorithm without stabilization techniques can easily result in non-convergent models, even for a three-layer fully-connected network.

Another series of papers (Joachims (2005) , Kar et al. (2014) and Narasimhan et al. (2015) ) study optimizing differentiable lower bounds of various non-decomposable and non-differentiable binary classification metrics for linear classifiers. Despite proved learning guarantees for linear classifier, these lower bound methods are not very promising when applied to neural networks, as reported in Sanyal et al. (2018) .

Thresholding is a computationally economical method if we only consider binary classification. Koyejo et al. (2014) proves that the optimal classifier with respect to a family of binary classification metrics, including the F -measure, is appropriately thresholded Bayes classifier. Given an approximation of Bayes classifier, we can approach the optimal threshold via grid search. However, it remains unknown how to generalize thresholding to multi-class classification. More importantly, for binary classification, when training set is extremely imbalanced, it can be very difficult to train a classifier that approximates Bayes classifier very well.

The computational cost of aforementioned methods roughly equals that of training classifiers with standard classification losses such as cross-entropy. As proved in Parambath et al. (2014) and Koyejo et al. (2014) , optimization of many performance metrics, including F -measure, can be reduced to weighted classification. Unfortunately, the optimal weight is in general unknown and has to be approximated by an expensive grid search (see Section 5). Despite its computational cost, unlike thresholding, this method can perform reasonably well even when a training set is extremely balanced. Eban et al. (2016) proposes a similar method that performs well for neural networks coupled with the AUCPR metric.

Regarding theory, the equivalence between the data-dependent and expected utility of the F -measure was first proved in Nan et al. (2012) and later generalized in Dembczyński et al. (2017) to p-Lipschitz binary classification performance metrics. 

5. EXPERIMENTS:

We evaluate Algorithm 1 on the following datasets: Letter1 , Adult2 , Covertype3 , KDDCup084 , CI-FAR10 and CIFAR100 (Krizhevsky (2009) ). The performance metric to optimize is the binary F 1 score. The purpose of this experiment is to demonstrate that Algorithm 1 can match the performance of a provably optimal, yet considerably more expensive algorithm that optimizes the F 1 score. We use a three-layer fully-connected network in our experiments, with batch normalization enabled. The statistics of these datasets are summarized in Table 1 (number of features, number of samples, percentage of positive samples). For multi-class datasets (Letter, Covertype, CIFAR10 and CIFAR100), we designate one class as the positive class and leave the rest as the negative class. We compare Algorithm 1 with the following baseline (Parambath et al. (2014) and Koyejo et al. ( 2014)):

θ * ← arg max θ,λ∈(0,1) 1 |D| (x,y)∈D l(p θ (x), y) λI(y = 0) + (1 -λ)I(y = 1)

where l denotes the cross-entropy loss. We let λ = 0.1, 0.2, 0.3, ..., 0.9, and apply gradient descent to optimize θ for a fixed λ. As proved in Parambath et al. (2014) and Koyejo et al. (2014) , this baseline method should yield an approximately optimal F 1 score (although at a cost considerably higher than Algorithm 1 because we have to optimize θ for every λ). In our case, the baseline method is 8 times slower than Algorithm 1. To our knowledge, the baseline method is the state-ofthe-art method in term of resultant F 1 score (not in term of efficiency). We apply weight decay to both methods and find that in general weight decay improves the performance of Algorithm 1 while hurts the performance of baseline method. For the Covertype dataset, Algorithm 1 cannot converge without weight decay, which is an evidence that weight decay may improve gradient estimation. We report results in Table 1 , where "F 1 GS" refers to the F 1 score attained by the grid-search method and "F 1 EUM" refers to the F 1 score attained by Algorithm 1.

6. CONCLUSION:

We propose an empirical utility maximization scheme that enables efficient gradient-based learning for a class of non-decomposable and non-differentiable classification performance metrics. We inquire into the proposed scheme mathematically and present preliminary experiments that validate our approach. We leave it as future work to experiment on deeper neural networks, larger datasets, and more complex performance metrics.

PROOFS:

Theorem 1. If F is a well-behaved performance metric and C D is a strongly consistent estimator of C, i.e. 

P lim |D|→∞ (C D ) ij = C ij = 1 0 ≤ i, j ≤ |Y| -1 then F (C D ) is

D i = C i Let E be the event that lim |D|→∞ F (C D ) = F (C) By the continuity of F , ∀i = 1, ..., N, lim |D|→∞ C D i = C i ⇒ lim |D|→∞ F (C D ) = F (C) which implies that N i=1 E i ⊂ E

Taking complement on both sides, we have

E c ⊂   N i=1 E i   c = N i=1 E c i

By the monotonicity of probability measure and the union bound, 

P(E c ) ≤ P   N i=1 E c i   ≤ N i=1 P(E c i ) = N i=1 1 -P(E i ) = N i=1 1 -1 = 0 Consequently, P lim |D|→∞ F (C D ) = F (C) = P(E) = 1 -P(E c ) = 1 -0 = 1 Theorem 2. If F is a well behaved performance metric, then ∇ θ F ( ĈB (h θ )) is a strongly consistent estimator of ∇ θ F ( C(h θ )), where B ⊂ D is a mini-batch. More precisely, P lim |B|→∞ ∇ θ F ĈB (h θ ) = ∇ θ F C(h θ ) = 1 Proof. Let N = |Y| × |Y|.

∇ θ F ĈB = ∇ θ F C Because ∇ θ F ( ĈB i ) is an unbiased estimator of ∇ θ F ( Ci ), i.e. E[∇ θ F ( ĈB i )] = ∇ θ F ( Ci ), P (E i ) = P lim |B|→∞ ∇ θ F ĈB i = ∇ θ F Ci = 1

by the law of large number. Consequently, suppose

N i=1 E i ⊂ E which is equivalent to the proposition that ∀i = 1, ..., N, lim |B|→∞ ∇ θ ĈB i = ∇ θ Ci ⇒ lim |B|→∞ ∇ θ F ĈB = ∇ θ F C

then this theorem will follow from a union bound argument similar to that in the proof of theorem 1. We now prove this proposition. Let ĴB and J be the Jacobian of ĈB and C w.r.t. θ, i.e.

ĴB =    ∇ θ ĈB 1 ... ∇ θ ĈB N    J =   ∇ θ C1 ... ∇ θ CN   By the chain rule, ∇ θ F ĈB = ∇F ĈB ĴB

where ∇F ĈB is the gradient of F at ĈB . Because F is continuously differentiable, i.e. ∇F exists and is continuous, Proof. To prove consistency, it suffices to prove that (Vapnik (1992) ):

lim |D|→∞ P sup θ F ĈD (h θ ) -F C(h θ ) < = 1

Because F is well behaved, by the union bound argument in previous proofs, it suffices to show that 

:

https://archive.ics.uci.edu/ml/datasets/letter+recognition

https://archive.ics.uci.edu/ml/datasets/adult

https://archive.ics.uci.edu/ml/datasets/covertype

http://www.kdd.org/kdd-cup/view/kdd-cup-2008/

Figures and Tables:

a strongly consistent estimator of F (C), i.e. P lim |D|→∞ F (C D ) = F (C) = 1 Proof. Let N = |Y| × |Y|. Instead of treating C D and C as |Y| × |Y| matrices, we treat them as N -dimensional vectors (C D 1 , ..., C D N ) and (C 1 , ..., C N ). For i = 1, ..., N , let E i be the event that lim |D|→∞ C

∀i = 1, ..., N, lim|B|→∞ ĈB i = Ci ⇒ lim |B|→∞ ∇F ĈB = ∇F CThus for all δ > 0, there exists N F,δ such that when |B| > N F ,| | := ∇F ĈB -∇F C < δ 2|| J ||where || J || is the matrix norm of J , defined as|| J || = sup|x|≤1 is in the Frobenius norm. Because convergence in the Frobenius norm is equivalent to convergence in matrix norm, for all δ > 0, there exists N Ĵ such that when |D| > N Ĵ ,||E|| := J D (θ) -J (θ) < δ 2M where M := sup x∈K ∇F (x) < ∞ because K is compact and ∇F is continuous on K by definition.Thus for all B such that |B| > max N F , N Ĵ ,∇ θ F ĈB -∇ θ F C = ∇F ĈB ĴB -∇F C J = ∇F C + J + E -∇F C J = ∇F C J + ∇F C E + J + E -∇F C J = ∇F C E + J + E -∇F C J ≤ ∇F C E + J + | E| ≈ ∇F C E + J ≤ ∇F C |E| + | | J we ignore the high-order term | E|. Consequently, lim |D|→∞ ∇ θ F ĈB = ∇ θ F CTheorem 3 (Generalization). For a well behaved performance metric F , for all > 0, lim|D|→∞ P F ( ĈD (h θ )) -F ( C(h θ )) ( ĈD (h θ )) -F ( C(h θ )) < = 1 which implies that lim |D|→∞ P F ( ĈD (h θ )) -F ( C(h θ )) < = 1Theorem 4 (Consistency). For a well behaved performance metric F , with appropriate constraints on the capacity of parametric model p θ (see the proof for details), we have that for all > 0

Cij (h θ ) < = 1 1 ≤ i, j ≤ |Y|Under review as a conference paper at ICLR 2019 Because ( ĈD (h θ )) ij = which holds for p θ with finite VC-dimension by Lemma 29.1 in Devroye (

Let fn(h θ ) := E ŷ,y [fn( ŷ, y)] and fp(h θ ) := E ŷ,y [fp( ŷ, y)]. It follows from the law of large number that lim

Table content: <table><tr><td colspan="4">with probability 1, where |D| denotes the size of dataset D. Thus on sufficiently large datasets,</td></tr><tr><td/><td>fn( ŷ, y) ≈ fn(h θ )</td><td colspan="2">fp( ŷ, y) ≈ fp(h θ )</td></tr><tr><td>|D|→∞</td><td>fn( ŷ, y) = fn(h θ )</td><td>lim |D|→∞</td><td>fp( ŷ, y) = fp(h θ )</td></tr></table>

Algorithm 2 Gradient-based learning for well behaved performance metrics Require: batch size b, classifier h θ , dataset D, learning rate α, weight-decay strength λ, and wellbehaved metric F for i = 1, ..., |Y| do p i ← 1

Table content: <table><tr><td>|D|</td><td>(x,y)∈D I(y = i)</td></tr><tr><td>end for</td><td/></tr><tr><td colspan="2">while terminating criterion not satisfied do</td></tr><tr><td colspan="2">for i = 1, ..., |Y| do</td></tr><tr><td>Sample</td><td/></tr></table>

Dataset statistics and resultsDATASET # FEATS # SAMPS % POSF 1 GS F 1 EUM

Table content: <table><tr><td>Adult</td><td>108</td><td>48,842</td><td>23.93</td><td>0.701</td><td>0.689</td></tr><tr><td>CIFAR10</td><td>3072</td><td>60,000</td><td>10.00</td><td>0.630</td><td>0.635</td></tr><tr><td>Letter</td><td>16</td><td>20,000</td><td>3.92</td><td>0.990</td><td>0.975</td></tr><tr><td>Covtype</td><td>54</td><td>581,012</td><td>1.63</td><td>0.691</td><td>0.725</td></tr><tr><td>CIFAR100</td><td>3072</td><td>60,000</td><td>1.00</td><td>0.350</td><td>0.392</td></tr><tr><td colspan="2">KDDCup08 117</td><td>102,294</td><td>0.61</td><td>0.543</td><td>0.556</td></tr></table>

CN ), where we omit the dependence on h θ for brevity. For i = 1, ..., N , let E i be the event that lim

Table content: <table><tr><td>|B|→∞</td><td>∇ θ</td><td>ĈB i = ∇ θ Ci</td></tr><tr><td>and E denote the event that</td><td/><td/></tr><tr><td>lim</td><td/><td/></tr><tr><td>|B|→∞</td><td/><td/></tr></table>

Peer review (iclr2019):
 This paper studies the problem of optimizing non-decomposable metric in classification. This topic has been discussed in several recent works mainly under deterministic classifier context, the authors discuss the possibility of training a neural network and learn the model by gradient-based methods, which could result in randomized classifier; and conducted experiments to compare the performance with other existing methodologies. I have the following concerns after reading it. 1.The main idea of the paper has shown in other related works and the authors didn’t convince me why their work solves something that could not be solved in existing work. The related work section missed some relevant recent work including Ref[1], in which the method is also gradient-based and can be applied to neural networks. The well-behaved notion used in Definition 2 seems much weaker than the assumptions shown in Ref[1,2] to guarantee existence or uniqueness of the Bayes classifier, the authors could spend some effort to discuss why they require less assumptions. 2.For the theory part, all the convergence results are proved in an asymptotic way without further discussion in the sample complexity. This becomes problematic for this work because (as shown in eq (7)) mini batch size goes to infinity is an unrealistic assumption in neural network training. Also when the class is unbalanced, empirical mean converging to population also slows down significantly which is required in Eq (4) and other places. I would like to see more discussion on the sample complexity either theoretically or experimentally. 3.The experiments lack details for reproducing the results or generalizing the gain to other problems. For example, batch size, learning rate or how the size of the network influence the performance metrics. This information will be useful for others who want to apply the proposed method. There are some minor formatting issues like the leading space in .citep. Please fix those. Based on the above reasons, I’ll give this paper a 5. [Ref 1] Yan, B., Koyejo, S., Zhong, K. & Ravikumar, P.. (2018). Binary Classification with Karmic, Threshold-Quasi-Concave Metrics. Proceedings of the 35th International Conference on Machine Learning, in PMLR 80:5531-5540 [Ref 2] Narasimhan, H., Kar, P., & Jain, P. (2015, June). Optimizing non-decomposable performance measures: a tale of two classes. In International Conference on Machine Learning (pp. 199-208).