Logistic Regression, AdaBoost and Bregman Distances

Michael Collins, Robert E. Schapire, Yoram Singer

Introduction

In the landscape of machine learning at the turn of the millennium, two algorithms stood as pillars of classification: AdaBoost and Logistic Regression. AdaBoost, a sequential "boosting" method, was celebrated for its ability to combine weak learners into a strong classifier by minimizing exponential loss. Logistic Regression, a statistical staple, was typically optimized via parallel updates to minimize log-loss. Despite their practical success, a rigorous mathematical bridge connecting these two approaches was missing.

In their seminal 2002 paper, Michael Collins, Robert Schapire, and Yoram Singer provided this missing link. They demonstrated that both algorithms are instances of a broader optimization problem: the minimization of a Bregman distance. This unification not only provided the first general proof of AdaBoost's convergence to a global minimum but also enabled the cross-pollination of optimization techniques between the two domains.

The Bregman Distance Framework

The core contribution of the paper is the identification of Bregman distances as the common language for these loss functions. A Bregman distance measures the discrepancy between two points based on a specific convex function.

The authors show a fundamental symmetry:

  1. Boosting (Exponential Loss): Minimizing exponential loss is mathematically equivalent to minimizing the unnormalized relative entropy (a specific Bregman distance) between the model's predictions and the target distribution.
  2. Logistic Regression (Log-Loss): Minimizing log-loss is equivalent to minimizing the binary relative entropy (another Bregman distance).

By framing both problems as the minimization of a Bregman distance associated with a convex function, the authors could derive a generalized family of algorithms applicable to both.

Algorithmic Innovations

Using this unified framework, the authors introduced two main classes of algorithms:

Parallel-Update Algorithms

Traditionally, boosting algorithms update one feature weight at a time. Drawing from the Maximum Entropy literature, the authors derived parallel versions that update all feature weights simultaneously. These are particularly effective in high-dimensional spaces where many features contribute to the final decision, allowing the model to "go right to the solution" early in training.

Sequential-Update Algorithms

Conversely, the authors developed a sequential version of Logistic Regression. A key practical advantage of this new algorithm is that it keeps example weights bounded within the range $[0, 1]$. In contrast, AdaBoost's weights can grow exponentially, which often makes it difficult to use for data filtering or subsampling in very large datasets.

Convergence Analysis

A significant theoretical hurdle addressed in this work is the proof of convergence. Prior to this paper, proofs for AdaBoost often relied on restrictive assumptions. The authors employed a sophisticated technique involving "auxiliary functions"—functions that upper-bound the loss and are easier to minimize. This allowed them to provide a rigorous, general proof that their iterative algorithms converge to the global minimum of the respective loss functions.

Experimental Validation

While primarily a theoretical work, the paper includes experiments on synthetic datasets to validate the new algorithms. The researchers used 100-dimensional data where labels were generated by a random hyperplane with added noise, testing both Gaussian and Boolean features.

Key results from these experiments include:

  • Speedup: Parallel-update variants converged much faster than sequential ones when many features were relevant.
  • Multiclass Versatility: The framework handled 10-class problems naturally without the complex "hacks" often required to extend binary classifiers.
  • Feature Selection: Sequential updates remained superior when only a few features were actually relevant, effectively performing feature selection during optimization.

Conclusion and Legacy

The unification of AdaBoost and Logistic Regression via Bregman distances remains a cornerstone of machine learning theory. It transformed our understanding of boosting from a heuristic-driven procedure into a principled optimization task. While the paper noted that weights can diverge to infinity in perfectly separable cases, its impact was profound, paving the way for modern gradient boosting machines and providing a template for analyzing a wide variety of loss functions under a single theoretical umbrella.

Summary updated

BibTeX
@article{collins2002logistic,
  author = {Michael Collins and Robert E. Schapire and Yoram Singer},
  title = {{Logistic Regression, AdaBoost and Bregman Distances}},
  journal = {Machine Learning},
  year = {2002},
  doi = {10.1023/a:1013912006537},
}
Figure