A new boosting algorithm based on dual averaging scheme

Nan WangarXiv 2015 · OpenReview

Abstract

The fields of machine learning and mathematical optimization are increasingly intertwined. The training part of most supervised learning algorithms can usually be reduced to an optimization problem that minimizes a loss between model predictions and training data. While most optimization techniques focus on accuracy and speed of convergence, the qualities of a good optimization algorithm from the machine learning perspective can be quite different, as machine learning is more than fitting the data. Better optimization algorithms that minimize training loss can possibly give very poor generalization performance. In this paper, we examine boosting, whose training process can be viewed as functional coordinate descent on the exponential loss. We study the relation between optimization techniques and machine learning by implementing a new boosting algorithm, DABoost, based on a dual-averaging scheme. We show that DABoost, although slower in reducing training error, generally enjoys better generalization error than AdaBoost.

Introduction

In mathematical optimization, the primary objective is typically to reach the minimum of a loss function as efficiently as possible. However, in machine learning, aggressive optimization can lead to overfitting—where a model fits the training data perfectly but fails to generalize to unseen data. Standard boosting algorithms like AdaBoost are essentially performing functional gradient descent, moving greedily to minimize exponential loss. This paper explores an alternative optimization philosophy: using Nesterov’s dual averaging method to create a more robust boosting algorithm, DABoost.

Methodology: DABoost vs. AdaBoost

The fundamental difference between AdaBoost and the proposed DABoost lies in their optimization strategies:

  • AdaBoost: Operates like gradient descent. At each iteration, it selects a "weak learner" to address the most recent errors. This approach is aggressive and greedy, focusing on the current gradient.
  • DABoost: Utilizes a dual averaging scheme. Instead of relying solely on the current iteration's gradient, it maintains a "dual variable" that accumulates gradients from all previous iterations.

By basing instance weight updates on the average performance of all previous weak learners, DABoost ensures that the weight distribution changes more slowly and smoothly. This "intentional slowness" acts as an implicit form of regularization.

Key Results and Empirical Analysis

The algorithm was evaluated on several benchmarks, including Heart Disease, Ionosphere, and Web Spam datasets.

Generalization and the "Slow and Steady" Advantage

On the Heart Disease and Ionosphere datasets, DABoost demonstrated a clear advantage in generalization. While it was slower to reduce training error compared to AdaBoost, it achieved a lower test error.

Comparison of training and test error on HeartDisease (a) and Ionosphere (b) datasets. Note how DABoost (green) maintains better test performance despite slower training convergence.

In the Heart Disease dataset specifically, AdaBoost's training error plummeted toward zero, but its test error began to climb, indicating overfitting. In contrast, DABoost’s test error remained stable and lower, effectively trading off training bias for lower variance.

The Noise Penalty

The "averaging" nature of DABoost is not without drawbacks. On the Web Spam dataset, DABoost performed worse than AdaBoost.

Comparison of training and test error on the WebSpam dataset. In this high-noise environment, AdaBoost (blue) outperforms the more sluggish DABoost (green).

The authors attribute this to the high level of noise and biased labels in the Web Spam corpus. The sluggish nature of the dual averaging update prevented the algorithm from quickly identifying the true signal amidst the noise.

Discussion: Optimization as Regularization

The core insight of this work is that the choice of optimization algorithm itself can serve as a powerful implicit regularizer. By being less "flexible" and changing instance weights more slowly, DABoost avoids chasing noise in the training set. This demonstrates that slower convergence can be a deliberate and beneficial design choice for improving machine learning performance.

Limitations and Future Work

DABoost's sensitivity to noisy labels suggests that its current form may struggle in highly biased environments. Future research could explore time-varying importance parameters or incorporating explicit $L_1$ or $L_2$ regularization directly into the dual averaging sub-problem to further enhance robustness.

Summary updated

Abstract

The fields of machine learning and mathematical optimization increasingly intertwined. The special topic on supervised learning and convex optimization examines this interplay. The training part of most supervised learning algorithms can usually be reduced to an optimization problem that minimizes a loss between model predictions and training data. While most optimization techniques focus on accuracy and speed of convergence, the qualities of good optimization algorithm from the machine learning perspective can be quite different since machine learning is more than fitting the data. Better optimization algorithms that minimize the training loss can possibly give very poor generalization performance. In this paper, we examine a particular kind of machine learning algorithm, boosting, whose training process can be viewed as functional coordinate descent on the exponential loss. We study the relation between optimization techniques and machine learning by implementing a new boosting algorithm. DABoost, based on dual-averaging scheme and study its generalization performance. We show that DABoost, although slower in reducing the training error, in general enjoys a better generalization error than AdaBoost.
BibTeX
@misc{wang2015new,
  author = {Nan Wang},
  title = {{A new boosting algorithm based on dual averaging scheme}},
  year = {2015},
  eprint = {1507.03125},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1507.03125},
}
Figure