Bregman Divergence Bounds and Universality Properties of the Logarithmic Loss
arXiv:1810.07014
Abstract
A loss function measures the discrepancy between the true values and their estimated fits, for a given instance of data. In classification problems, a loss function is said to be proper if a minimizer of the expected loss is the true underlying probability. We show that for binary classification, the divergence associated with smooth, proper, and convex loss functions is upper bounded by the Kullback-Leibler (KL) divergence, to within a normalization constant. This implies that by minimizing the logarithmic loss associated with the KL divergence, we minimize an upper bound to any choice of loss from this set. As such the logarithmic loss is universal in the sense of providing performance guarantees with respect to a broad class of accuracy measures. Importantly, this notion of universality is not problem-specific, enabling its use in diverse applications, including predictive modeling, data clustering and sample complexity analysis. Generalizations to arbitrary finite alphabets are also developed. The derived inequalities extend several well-known -divergence results.
arXiv commentarXiv admin note: substantial text overlap with arXiv:1805.03804
References in corpus (11)
- The information bottleneck method
- Opening the Black Box of Deep Neural Networks via Information
- -divergence Inequalities
- Information based clustering
- Composite Binary Losses
- Multivariate Information Bottleneck
- Theory and Applications of Proper Scoring Rules
- A Note on the PAC Bayesian Theorem
- A PAC-Bayesian Tutorial with A Dropout Bound
- Information Measures: the Curious Case of the Binary Alphabet
- Linear Independent Component Analysis over Finite Fields: Algorithms and Bounds