  Cross-validation (CV) is one of the main tools for performance estimation and
parameter tuning in machine learning. The general recipe for computing CV
estimate is to run a learning algorithm separately for each CV fold, a
computationally expensive process. In this paper, we propose a new approach to
reduce the computational burden of CV-based performance estimation. As opposed
to all previous attempts, which are specific to a particular learning model or
problem domain, we propose a general method applicable to a large class of
incremental learning algorithms, which are uniquely fitted to big data
problems. In particular, our method applies to a wide range of supervised and
unsupervised learning tasks with different performance criteria, as long as the
base learning algorithm is incremental. We show that the running time of the
algorithm scales logarithmically, rather than linearly, in the number of CV
folds. Furthermore, the algorithm has favorable properties for parallel and
distributed implementation. Experiments with state-of-the-art incremental
learning algorithms confirm the practicality of the proposed method.
