Optimal Minimal Margin Maximization with Boosting

Alexander Mathiasen, Kasper Green Larsen, Allan Grønlund

Optimal Minimal Margin Maximization with Boosting

Boosting algorithms, such as AdaBoost and Gradient Boosting, are foundational machine learning techniques that combine many "weak" hypotheses into a single strong predictor. A curious property of boosting is that generalization often continues to improve even after training error reaches zero. This phenomenon is largely attributed to margins—the distance between data points and the decision boundary. Maximizing the minimal margin makes the classifier more robust.

However, there is a fundamental trade-off between the number of hypotheses ($T$) and the margin gap ($v$), which measures how close the ensemble is to the optimal margin. A long-standing 2013 conjecture posited a strict lower bound, suggesting that achieving a gap of $v$ required at least $\Omega(\log(n)/v^2)$ hypotheses. This paper challenges and refutes that conjecture by introducing SparsiBoost, an algorithm that optimally prunes large ensembles using techniques from combinatorial discrepancy theory.

The SparsiBoost Algorithm

SparsiBoost operates in two primary phases to achieve its optimal bounds:

  1. Initialization: It utilizes a standard margin-maximizing algorithm (like AdaBoostV) to generate a large, initial ensemble of hypotheses.
  2. Sparsification: Instead of relying on simple importance sampling or top-$k$ selection, SparsiBoost employs combinatorial discrepancy minimization. Specifically, it uses a constructive version of Joel Spencer’s famous "six standard deviations suffice" theorem.

This sparsification process intelligently adjusts the weights of the hypotheses, drastically reducing the total count while ensuring the margin of every single data point remains nearly unchanged. By doing so, it preserves the entire margin distribution rather than just optimizing the worst-case minimal margin.

Key Insights and Results

The authors prove theoretically that the previous lower bound was overly pessimistic. The true optimal number of hypotheses is actually $T = \Theta(\log(nv^2)/v^2)$. For small desired gaps $v$, SparsiBoost is significantly more efficient than previously thought possible, and the authors provide a matching lower bound to prove its mathematical optimality.

A major advantage of SparsiBoost is its ability to preserve the margin distribution. According to margin theory, this preservation is the key to why the pruned model generalizes so well.

Margin Distribution Comparison

As seen above, a model sparsified from 500 to 80 hypotheses maintains a cumulative margin distribution nearly identical to the original 500-hypothesis model. This vastly outperforms a model trained from scratch with only 80 hypotheses, which suffers from a significantly degraded margin distribution.

In empirical evaluations across standard benchmarks (like Flight Delay, Higgs, and Letter datasets), SparsiBoost consistently demonstrated superior generalization.

Performance vs. Number of Hypotheses

When compared to state-of-the-art implementations like LightGBM, SparsiBoost-pruned models achieve higher classification accuracy and AUC for the same number of hypotheses. By bridging theoretical computer science and practical machine learning, the authors show that abstract mathematical tools can effectively solve concrete optimization problems.

Limitations and Future Work

While SparsiBoost is theoretically optimal and empirically strong, it has a few limitations:

  • Algorithmic Complexity: The discrepancy minimization step is more complex to implement and tune than standard AdaBoost or simple importance sampling, running in roughly $\tilde{O}(nT + T^3)$ time.
  • Randomization: The sparsification process relies on randomization. Although it outperforms importance sampling on average, variance across different runs could be a consideration for production deployment.
  • Base Learner Assumptions: The current theoretical framework assumes base hypotheses return values in $[-1, +1]$. Extending this approach to handle complex, real-valued regressor outputs remains an open area for future exploration.

Summary updated

Abstract

Boosting algorithms iteratively produce linear combinations of more and more base hypotheses and it has been observed experimentally that the generalization error keeps improving even after achievi...
BibTeX
@inproceedings{mathiasen2019optimal,
  author = {Alexander Mathiasen and Kasper Green Larsen and Allan Grønlund},
  title = {{Optimal Minimal Margin Maximization with Boosting}},
  booktitle = {International Conference on Machine Learning},
  year = {2019},
  url = {https://openreview.net/forum?id=r144a9Zu-r},
}

Loading related content...

Figure