On divergences, surrogate loss functions, and decentralized detection

XuanLong Nguyen, Martin J. Wainwright, Michael I. Jordan

Abstract

The goal of binary classification is to estimate a discriminant function $\gamma$ 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 $f$-divergence functionals. Whereas this correspondence was established by Blackwell 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.

Introduction

In classical binary classification, the objective is to learn a decision rule that maps a feature vector $X$ to a label $Y \in \{-1, 1\}$. However, modern systems—ranging from decentralized sensor networks to complex feature selection pipelines—often operate under communication or computational constraints. In these settings, the full feature vector $X$ is not directly accessible to the classifier. Instead, $X$ is processed by a "quantizer" $Q$, which maps the high-dimensional input to a compressed representation $Z$.

The central challenge addressed in this research is the joint optimization of the classifier $\gamma$ and the quantizer $Q$. While the machine learning community has extensively studied "surrogate" loss functions (such as hinge, logistic, or exponential loss) for fixed data representations, their behavior in the context of simultaneous representation learning remains a critical theoretical gap. This paper bridges that gap by establishing a formal link between surrogate loss functions and the classical theory of $f$-divergences.

The Correspondence Between Loss and Divergence

A primary contribution of this work is the "Correspondence Theorem." The authors demonstrate that for any margin-based surrogate loss function $\phi$, the minimum achievable risk (the $\phi$-risk) is mathematically equivalent to the negative of an $f$-divergence between the class-conditional probability distributions.

An $f$-divergence is a functional that measures the "distance" or "dissimilarity" between two probability distributions. Common examples include the Kullback-Leibler (KL) divergence, Hellinger distance, and Total Variation distance. By providing a constructive mapping to relate a specific loss function to a specific divergence, the authors allow researchers to translate problems in statistical learning into the language of information theory.

Universal Equivalence and Bayes Consistency

The paper introduces the concept of "universal equivalence" to determine when two different loss functions will agree on the optimal quantizer. In standard classification with a fixed $Q$, many surrogate losses are "Bayes consistent," meaning that as the sample size grows, the learned classifier approaches the optimal Bayes decision rule.

However, when the quantizer $Q$ is also being optimized, the requirements for consistency become much stricter. For joint optimization to be Bayes consistent, the surrogate loss must induce the same ordering on the space of possible quantizers as the original 0-1 loss.

Key Findings on Specific Loss Functions:

  • 0-1 Loss and Hinge Loss: The authors show that both the 0-1 loss and the Hinge loss (commonly used in Support Vector Machines) correspond to the Total Variation distance. Because they share this underlying divergence, Hinge loss is "universally equivalent" to the 0-1 loss and remains Bayes consistent during joint optimization.
  • Logistic and Exponential Loss: Popular losses like the logistic loss (used in logistic regression) and the exponential loss (used in AdaBoost) correspond to different divergences—specifically, Capacitory Discrimination and the Hellinger distance, respectively.
  • The Joint Consistency Trap: The research reveals that these popular losses can fail in joint optimization settings. A quantizer that minimizes the Hellinger distance (optimal for exponential loss) might not minimize the Total Variation distance (optimal for 0-1 loss). Consequently, optimizing for these surrogates can lead to a sub-optimal "Bayes" decision when the data representation is part of the optimization loop.

Theoretical Results

The paper formalizes these insights through three primary theorems:

  1. Theorem 1: Establishes the one-to-one correspondence between optimal $\phi$-risk and $f$-divergences.
  2. Theorem 2: Defines the conditions for "Universal Consistency," proving that a loss function is consistent for joint estimation if and only if its induced divergence is a linear transformation of the Total Variation distance.
  3. Theorem 3: Provides a simple test for "Universal Equivalence," showing that two divergences are equivalent if one is a linear transformation of the other.

Conclusion

This research provides a rigorous framework for selecting loss functions in scenarios involving decentralized detection or learned dimensionality reduction. It highlights that the Hinge loss is a uniquely robust surrogate for joint optimization, whereas other common surrogates like logistic or least-squares loss may lead to inconsistent results. While the current framework is limited to binary labels, it sets the stage for future investigations into multiclass problems and the computational complexities of non-convex joint optimization.

Summary updated

Abstract

The goal of binary classification is to estimate a discriminant function $\gamma$ 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 $f$-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.
BibTeX
@misc{nguyen2005divergences,
  author = {XuanLong Nguyen and Martin J. Wainwright and Michael I. Jordan},
  title = {{On divergences, surrogate loss functions, and decentralized detection}},
  year = {2005},
  eprint = {math/0510521},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/math/0510521},
}

Loading related content...

Figure