Scalable Non-linear Learning with Adaptive Polynomial Expansions

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

Introduction

In the era of massive datasets, machine learning practitioners frequently face a frustrating dilemma: train a simple linear model on the entire dataset to save time, or train a complex nonlinear model (like Kernel SVMs) on a tiny fraction of the data to capture complex patterns. Standard nonlinear approaches, such as polynomial kernels, scale poorly—often quadratically or cubically with the number of examples. While manual feature engineering (like adding $n$-grams or quadratic interactions) can help, it often results in a massive, sparse, and unmanageable feature space.

This paper asks a critical question: Can we learn a nonlinear representation in time comparable to linear learning? To answer this, the authors introduce apple (Adaptive Polynomial Expansion), an algorithm that adaptively grows nonlinear features during training. By "breeding" new high-order interaction features from the most successful existing ones, apple bridges the gap between fast linear models and computationally expensive kernel methods.

The Apple Algorithm: Adaptive Feature Expansion

The apple algorithm builds upon standard Stochastic Gradient Descent (SGD) but introduces a staged feature expansion process designed for extreme computational efficiency:

  1. Base Learning: Training begins with a standard linear representation.
  2. Adaptive Expansion: At set intervals (epochs), the algorithm evaluates the existing features and identifies the "top" performers based on the largest learned weight magnitudes.
  3. Feature "Breeding": It dynamically creates new, higher-order interaction features by multiplying these successful "parent" features with the original base features.
  4. On-the-fly Computation: To avoid massive I/O bottlenecks—often the true limiting factor in large-scale learning—these features are generated dynamically during training using feature hashing (via the Vowpal Wabbit library). They are never stored on disk.

A significant theoretical contribution of the paper is a new regret bound for "shifting comparators." The authors prove that even as the feature set grows and the optimal model changes, apple achieves a $1/T$ convergence rate, significantly faster than previous theoretical benchmarks for this setting.

Key Insights and Performance Trade-offs

The researchers evaluated apple on a diverse suite of 30 publicly available datasets (including rcv1, nomao, 20news, and cup98) as well as a massive internal advertising dataset with approximately 690 million examples.

The results highlight several key insights:

  • The Weight Heuristic Works: The simple heuristic of using features with large weights to create higher-order interactions is highly effective and computationally cheaper than complex statistical alternatives.
  • Staged Growth is Essential: Adding features in stages allows the parameters of existing features to stabilize, providing a reliable guide for which nonlinearities to introduce next.
Relative error vs time tradeoff
  • Dominating the Trade-off: As illustrated above, apple occupies the "sweet spot" on the Pareto frontier of machine learning. It operates nearly as fast as linear models while achieving error rates comparable to (or better than) cubic models, which can take 10 to 100 times longer to train.

Comprehensive Results Across Datasets

On 26 out of the 30 evaluated datasets, the apple algorithm (using default settings) outperformed linear, quadratic, and cubic baselines in terms of the computation-to-prediction tradeoff.

Cumulative performance across datasets

On large, high-dimensional datasets where a full cubic expansion is computationally infeasible, apple provided similar accuracy gains while staying within a factor of 10 of the linear training time. Furthermore, on the massive 690M-example advertising dataset, apple improved the Area Under Curve (AUC) from 0.8166 (linear) to 0.8171, whereas a full quadratic model failed to even finish within a day.

Limitations and Future Work

While highly effective, the approach has a few limitations:

  • Hyperparameter Sensitivity: The expansion rate is controlled by a parameter $\alpha$. Although $\alpha=1$ serves as a reliable default, the optimal rate varies by dataset.
  • Stochastic vs. Adversarial Settings: The strong $1/T$ theoretical guarantees apply to the stochastic setting (data drawn from a distribution). Establishing these rates for harsher "adversarial" settings remains an open challenge.
  • Heuristic Guidance: The weight magnitude heuristic is practically successful but lacks formal theoretical guidance on exactly when to trigger an expansion epoch.

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 J. Telgarsky},
  title = {{Scalable Non-linear Learning with Adaptive Polynomial Expansions}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2014},
  url = {https://openreview.net/forum?id=rJ-8lOW_bH},
}
Figure