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:
- Base Learning: Training begins with a standard linear representation.
- Adaptive Expansion: At set intervals (epochs), the algorithm evaluates the existing features and identifies the "top" performers based on the largest learned weight magnitudes.
- Feature "Breeding": It dynamically creates new, higher-order interaction features by multiplying these successful "parent" features with the original base features.
- 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.
- Dominating the Trade-off: As illustrated above,
appleoccupies 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.
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