Scalable Nonlinear Learning with Adaptive Polynomial Expansions

When faced with large datasets, it is commonly observed that using all the data with a simpler algorithm is superior to using a small fraction of the data with a more computationally intense but possibly more effective algorithm. The question becomes: What is the most sophisticated algorithm that can be executed given a computational constraint? At the largest scales, Naïve Bayes approaches offer a simple, easily distributed single-pass algorithm. A more computationally difficult, but commonly better-performing approach is large scale linear regression, which has been effectively parallelized in several ways on real-world large scale datasets [1, 19]. Is there a modestly more computationally difficult approach that allows us to commonly achieve superior statistical performance?