text: Recently, a parametrized class of loss functions called @math -loss, @math , has been introduced for classification. This family, which includes the log-loss and the 0-1 loss as special cases, comes with compelling properties including an equivalent margin-based form which is classification-calibrated for all @math . We introduce a generalization of this family to the entire range of @math and establish how the parameter @math enables the practitioner to choose among a host of operating conditions that are important in modern machine learning tasks. We prove that smaller @math values are more conducive to faster optimization; in fact, @math -loss is convex for @math and quasi-convex for @math . Moreover, we establish bounds to quantify the degradation of the local-quasi-convexity of the optimization landscape as @math increases; we show that this directly translates to a computational slow down. On the other hand, our theoretical results also suggest that larger @math values lead to better generalization performance. This is a consequence of the ability of the @math -loss to limit the effect of less likely data as @math increases from 1, thereby facilitating robustness to outliers and noise in the training data. We provide strong evidence supporting this assertion with several experiments on benchmark datasets that establish the efficacy of @math -loss for @math in robustness to errors in the training data. Of equal interest is the fact that, for @math , our experiments show that the decreased robustness seems to counteract class imbalances in training data.
  @cite_13: In this letter, we investigate the impact of choosing different loss functions from the viewpoint of statistical learning theory. We introduce a convexity assumption, which is met by all loss functions commonly used in the literature, and study how the bound on the estimation error changes with the loss. We also derive a general result on the minimizer of the expected risk for a convex loss function in the case of classification. The main outcome of our analysis is that for classification, the hinge loss appears to be the loss of choice. Other things being equal, the hinge loss leads to a convergence rate practically indistinguishable from the logistic loss rate and much better than the square loss rate. Furthermore, if the hypothesis space is sufficiently rich, the bounds obtained for the hinge loss are not loosened by the thresholding stage.
  @cite_18: Many of the classification algorithms developed in the machine learning literature, including the support vector machine and boosting, can be viewed as minimum contrast methods that minimize a convex surrogate of the 0–1 loss function. The convexity makes these algorithms computationally efficient. The use of a surrogate, however, has statistical consequences that must be balanced against the computational virtues of convexity. To study these issues, we provide a general quantitative relationship between the risk as assessed using the 0–1 loss and the risk as assessed using any nonnegative surrogate loss function. We show that this relationship gives nontrivial upper bounds on excess risk under the weakest possible condition on the loss function—that it satisfies a pointwise form of Fisher consistency for classification. The relationship is based on a simple variational transformation of the loss function that is easy to compute in many applications. We also present a refined version of this result in the...
  @cite_14: We present a margin-based loss function for classification, inspired by the recently proposed similarity measure called correntropy. We show that correntropy induces a nonconvex loss function that is a closer approximation to the misclassification loss (ideal 0–1 loss). We show that the discriminant function obtained by optimizing the proposed loss function using a neural network is insensitive to outliers and has better generalization performance as compared to using the squared loss function which is common in neural network classifiers. The proposed method of training classifiers is a practical way of obtaining better results on real world classification problems, that uses a simple gradient based online training procedure for minimizing the empirical risk.
  @cite_7: Stochastic convex optimization is a basic and well studied primitive in machine learning. It is well known that convex and Lipschitz functions can be minimized efficiently using Stochastic Gradient Descent (SGD). The Normalized Gradient Descent (NGD) algorithm, is an adaptation of Gradient Descent, which updates according to the direction of the gradients, rather than the gradients themselves. In this paper we analyze a stochastic version of NGD and prove its convergence to a global minimum for a wider class of functions: we require the functions to be quasi-convex and locally-Lipschitz. Quasi-convexity broadens the concept of unimodality to multidimensions and allows for certain types of saddle points, which are a known hurdle for first-order optimization methods such as gradient descent. Locally-Lipschitz functions are only required to be Lipschitz in a small region around the optimum. This assumption circumvents gradient explosion, which is another known hurdle for gradient descent variants. Interestingly, unlike the vanilla SGD algorithm, the stochastic normalized gradient descent algorithm provably requires a minimal minibatch size.
  @cite_9: We present @math -loss, @math , a tunable loss function for binary classification that bridges log-loss ( @math ) and @math - @math loss ( @math ). We prove that @math -loss has an equivalent margin-based form and is classification-calibrated, two desirable properties for a good surrogate loss function for the ideal yet intractable @math - @math loss. For logistic regression-based classification, we provide an upper bound on the difference between the empirical and expected risk for @math -loss by exploiting its Lipschitzianity along with recent results on the landscape features of empirical risk functions. Finally, we show that @math -loss with @math performs better than log-loss on MNIST for logistic regression.
  @cite_3: While convex losses for binary classification are attractive due to the existence of numerous (provably) efficient methods for finding their global optima, they are sensitive to outliers. On the other hand, while the nonconvex 0-1 loss is robust to outliers, it is NP-hard to optimize and thus rarely directly optimized in practice. In this paper, however, we do just that: we explore a variety of practical methods for direct (approximate) optimization of the 0-1 loss based on branch and bound search, combinatorial search, and coordinate descent on smooth, differentiable relaxations of 0-1 loss. Empirically, we compare our proposed algorithms to logistic regression, SVM, and the Bayes point machine showing that the proposed 0-1 loss optimization algorithms perform at least as well and offer a clear advantage in the presence of outliers. To this end, we believe this work reiterates the importance of 0-1 loss and its robustness properties while challenging the notion that it is difficult to directly optimize.
  @cite_6: 
  @cite_0: In many classification procedures, the classification function is obtained by minimizing a certain empirical risk on the training sample. The classification is then based on the sign of the classification function. In recent years, there have been a host of classification methods proposed that use different margin-based loss functions. The margin-based loss functions are often motivated as upper bounds of the misclassification loss, but this cannot explain the statistical properties of the classification procedures. We show that a large family of margin-based loss functions are Fisher consistent for classification. That is, the population minimizer of the loss function leads to the Bayes optimal rule of classification. Our result covers almost all margin-based loss functions that have been proposed in the literature. We give an inequality that links the Fisher consistency of margin-based loss functions with the consistency of methods based on these loss functions. We use this inequality to obtain the rate of convergence for the method of sieves based on a class of margin-based loss functions.
  @cite_23: Problems of data classification can be studied in the framework of regularization theory as ill-posed problems. In this framework, loss functions play an important role in the application of regularization theory to classification. In this paper, we review some important convex loss functions, including hinge loss, square loss, modified square loss, exponential loss, logistic regression loss, as well as some non-convex loss functions, such as sigmoid loss, @math -loss, ramp loss, normalized sigmoid loss, and the loss function of 2 layer neural network. Based on the analysis of these loss functions, we propose a new differentiable non-convex loss function, called smoothed 0-1 loss function, which is a natural approximation of the 0-1 loss function. To compare the performance of different loss functions, we propose two binary classification algorithms for binary classification, one for convex loss functions, the other for non-convex loss functions. A set of experiments are launched on several binary data sets from the UCI repository. The results show that the proposed smoothed 0-1 loss function is robust, especially for those noisy data sets with many outliers.
  @cite_2: The machine learning problem of classifier design is studied from the perspective of probability elicitation, in statistics. This shows that the standard approach of proceeding from the specification of a loss, to the minimization of conditional risk is overly restrictive. It is shown that a better alternative is to start from the specification of a functional form for the minimum conditional risk, and derive the loss function. This has various consequences of practical interest, such as showing that 1) the widely adopted practice of relying on convex loss functions is unnecessary, and 2) many new losses can be derived for classification problems. These points are illustrated by the derivation of a new loss which is not convex, but does not compromise the computational tractability of classifier design, and is robust to the contamination of data with outliers. A new boosting algorithm, SavageBoost, is derived for the minimization of this loss. Experimental results show that it is indeed less sensitive to outliers than conventional methods, such as Ada, Real, or LogitBoost, and converges in fewer iterations.
  @cite_5: A tunable measure for information leakage called maximal a-leakage is introduced. This measure quantifies the maximal gain of an adversary in refining a tilted version of its prior belief of any (potentially random) function of a dataset conditioning on a disclosed dataset. The choice of @math determines the specific adversarial action ranging from refining a belief for @math to guessing the best posterior for @math , and for these extremal values this measure simplifies to mutual information (MI) and maximal leakage (MaxL), respectively. For all other @math this measure is shown to be the Arimoto channel capacity. Several properties of this measure are proven including: (i) quasi-convexity in the mapping between the original and disclosed datasets; (ii) data processing inequalities; and (iii) a composition property. A full version of this paper is in [1].
  @cite_10: The goal of binary classification is to estimate a discriminant function y from observations of covariate vectors and corresponding binary labels. We consider an elaboration of this problem in which the covariates are not available directly but are transformed by a dimensionality-reducing quantizer Q. We present conditions on loss functions such that empirical risk minimization yields Bayes consistency when both the discriminant function and the quantizer are estimated. These conditions are stated in terms of a general correspondence between loss functions and a class of functionals known as Ali-Silvey or -divergence functionals. Whereas this correspondence was established by Blackwell [Proc. 2nd Berkeley Symp. Probab. Statist. 1 (1951) 93-102. Univ. California Press, Berkeley] for the 0-1 loss, we extend the correspondence to the broader class of surrogate loss functions that play a key role in the general theory of Bayes consistency for binary classification. Our result makes it possible to pick out the (strict) subset of surrogate loss functions that yield Bayes consistency for joint estimation of the discriminant function and the quantizer.
  @cite_20: Binary classification is a well studied special case of the classification problem. Statistical properties of binary classifiers, such as consistency, have been investigated in a variety of settings. Binary classification methods can be generalized in many ways to handle multiple classes. It turns out that one can lose consistency in generalizing a binary classification method to deal with multiple classes. We study a rich family of multiclass methods and provide a necessary and sufficient condition for their consistency. We illustrate our approach by applying it to some multiclass methods proposed in the literature.
  @cite_17: 
summary: Surrogate loss functions for the @math - @math loss have been widely of interest to the machine learning and statistics communities @cite_18 @cite_2 @cite_0 @cite_10 @cite_13 @cite_17 @cite_3 @cite_14 @cite_20 @cite_23 . Recently, there has been renewed interest in alternative losses for classification @cite_6 @cite_3 @cite_23 @cite_17 @cite_5 other than the oft-used log-loss. During the inception of the field, convex losses were widely considered optimal @cite_18 @cite_13 @cite_10 @cite_0 . However, more recent works propose the use of non-convex losses as a means to moderate the behavior of an algorithm @cite_17 @cite_9 @cite_3 @cite_2 . In particular, motivated by superior robustness and classification accuracy of non-convex losses, Mei @cite_17 studied the empirical landscape of such functions. Along these lines, Hazan @cite_7 introduce SLQC as a means to study the unimodality of quasi-convex functions and their optimization characteristics. For SLQC functions, they introduce Normalized Gradient Descent algorithm and prove its convergence guarantees. Using their methodology, we consider @math -loss under logistic regression for binary classification and derive intuition about the operating characteristics of @math -loss.