Theoretical and Empirical Analysis of a Parallel Boosting Algorithm
  Many real-world problems involve massive amounts of data. Under these
circumstances learning algorithms often become prohibitively expensive, making
scalability a pressing issue to be addressed. A common approach is to perform
sampling to reduce the size of the dataset and enable efficient learning.
Alternatively, one customizes learning algorithms to achieve scalability. In
either case, the key challenge is to obtain algorithmic efficiency without
compromising the quality of the results. In this paper we discuss a
meta-learning algorithm (PSBML) which combines features of parallel algorithms
with concepts from ensemble and boosting methodologies to achieve the desired
scalability property. We present both theoretical and empirical analyses which
show that PSBML preserves a critical property of boosting, specifically,
convergence to a distribution centered around the margin. We then present
additional empirical analyses showing that this meta-level algorithm provides a
general and effective framework that can be used in combination with a variety
of learning classifiers. We perform extensive experiments to investigate the
tradeoff achieved between scalability and accuracy, and robustness to noise, on
both synthetic and real-world data. These empirical results corroborate our
theoretical analysis, and demonstrate the potential of PSBML in achieving
scalability without sacrificing accuracy.
