Scalable Nonlinear Learning with Adaptive Polynomial Expansions

Alekh Agarwal, Alina Beygelzimer, Daniel J. Hsu, John Langford, Matus Telgarsky

This paper, presented by researchers from Microsoft, Yahoo!, Columbia, and Rutgers, tackles a fundamental trade-off in machine learning: the choice between the speed of linear models and the predictive power of nonlinear ones. When dealing with massive datasets, practitioners often default to linear models because they are computationally cheap and easy to parallelize. The authors introduce apple (Adaptive Polynomial Expansion), an algorithm that bridges this gap by starting with a linear model and "growing" into a nonlinear one on the fly.

TL;DR

The apple algorithm adaptively expands a linear model's feature space by adding higher-order polynomial interactions based on the most influential features learned during training. It achieves the predictive accuracy of complex nonlinear models while maintaining the extreme computational efficiency required for web-scale datasets.

What Problem Does This Paper Address?

In the world of big data, there is a "folklore" observation: it is often better to use all your data with a simple algorithm (like linear regression) than a small fraction of your data with a complex one (like a Kernel SVM). The bottleneck isn't just CPU cycles; it's often I/O—the time it takes to read data from disk.

The challenge is that linear models can't capture interactions between features (e.g., in text data, the words "not" and "good" have a very different meaning when they appear together). While you could pre-calculate every possible interaction (quadratic or cubic expansions), the number of features explodes exponentially, making training impossibly slow. The authors ask: Can we learn these nonlinearities adaptively, only adding the interactions that actually matter, in a time comparable to linear learning?

Methods

The authors propose a staged, online learning approach implemented within the Vowpal Wabbit framework.

  1. Stochastic Gradient Descent (SGD): The algorithm processes data one example at a time, updating weights for the current feature set.
  2. Adaptive Expansion: At set intervals (epochs), the algorithm identifies the "top" features—those with the largest weight magnitudes. It assumes that if a feature is important linearly, its interactions with other features are likely important nonlinearly.
  3. Feature Growth: It creates new features by multiplying these top "parent" features with the base features. For example, if the word "excellent" has a high weight, the algorithm might start looking for interactions like "excellent" $\times$ "service."
  4. Hashing: To handle the dynamic creation of millions of features without a massive memory overhead, the algorithm uses a "hashing trick," mapping feature strings to a fixed-size bit index.
  5. Theoretical Regret Bound: The authors provide a new proof showing that even though the feature space is changing (a "shifting comparator"), the algorithm converges at a fast $O(1/T)$ rate in a stochastic setting, which is surprisingly robust.

Datasets

The algorithm was evaluated on a diverse testbed of 30 publicly available datasets from sources like the UCI repository and KDDCup (e.g., 20news, rcv1, adult, covtype, kdda). These ranged from small-scale to massive datasets with millions of examples and features.

Additionally, they tested a parallelized version on an internal advertising dataset containing 690 million training examples, specifically looking at click-through rate prediction.

Key Insights and Ideas

  • The Weight Heuristic: The most powerful idea here is using weight magnitude as a proxy for feature utility. Instead of an exhaustive search for interactions, apple uses the model's own current state to decide where to invest more computational effort.
  • Amortized Complexity: By only expanding the feature set a few times (e.g., 5 rounds over 6 epochs), the "expensive" operation of adding features is spread out, preventing it from becoming a bottleneck.
  • I/O Efficiency: Because features are generated on-the-fly at runtime, the algorithm avoids the massive I/O cost of reading pre-expanded nonlinear features from disk.

Key Results

The primary success of apple is its superior computation/prediction tradeoff, as illustrated in the Pareto frontier below:

Figure 1: Computation/prediction tradeoffpoints using non-adaptive polynomial expansions and adaptive polynomial expansions (apple). The markers are positioned at the coordinate-wise median of (relative error, relative time) over 30 datasets, with bars extending to 25th and 75th percentiles. See Section 3 for definition of relative error and relative time used here.
  • Dominance over Baselines: On 12 of the 30 datasets, apple achieved a lower error than linear, quadratic, and cubic baselines.
  • Efficiency: On large, sparse datasets, apple was often 10 to 100 times faster than a full cubic expansion while providing similar or better accuracy.
  • Scalability: In the 690M example advertising experiment, apple significantly improved AUC (Area Under the Curve) compared to linear and bigram models. Crucially, full quadratic and cubic models were computationally "prohibitive" and could not even finish training on this dataset.

Limitations and Future Work

  • Heuristic Nature: While the weight magnitude heuristic works well in practice, the authors admit it isn't "rigorously analyzed" for all possible data distributions. They suggest a "fall-back" rule to ensure risk consistency in worst-case scenarios.
  • High-Probability Bounds: The current theoretical guarantees are in expectation. The authors note that proving these fast convergence rates with high probability remains an open challenge.
  • Parallelization Tuning: While the parallel version worked, the authors suggest that the process of synchronizing "parent" features across nodes could be further optimized to reduce communication overhead.

For those interested in implementation, the authors integrated this logic into Vowpal Wabbit via the --stage_poly flag.

Summary updated

Abstract

Can we effectively learn a nonlinear representation in time comparable to linear learning? We describe a new algorithm that explicitly and adaptively expands higher-order interaction features over base linear representations. The algorithm is designed for extreme computational efficiency, and an extensive experimental study shows that its computation/prediction tradeoff ability compares very favorably against strong baselines.
BibTeX
@inproceedings{agarwal2014scalable,
  author = {Alekh Agarwal and Alina Beygelzimer and Daniel J. Hsu and John Langford and Matus Telgarsky},
  title = {{Scalable Nonlinear Learning with Adaptive Polynomial Expansions}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2014},
  url = {https://openreview.net/forum?id=rJ-8lOW_bH},
}
Figure