  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
$f$-divergence results.
