Scalable Nonlinear Learning with Adaptive Polynomial Expansions

2014/10/02 by Alekh Agarwal, Agarwal, Alekh, Alina Beygelzimer +7 · 1 citation
Computer Science · Engineering · Physics and Astronomy · #FOS: Computer and information sciences #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Model Reduction and Neural Networks #Neural Networks and Applications #Sparse and Compressive Sensing Techniques

paper · pdf · doi:10.48550/arxiv.1410.0440

openalex publication_date 2014/10/02 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

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.

Citations

• Stochastic Gradient Descent for Non-smooth Optimization: Convergence\n Results and Optimal Averaging Schemes
• Signal Recovery From Random Measurements Via Orthogonal Matching Pursuit
• Polynomial Theory of Complex Systems

Cited by

• Sparse Quadratic Logistic Regression in Sub-quadratic Time

Related

• Learn Like The Pro: Norms from Theory to Size Neural Computation
• Iteratively reweighted kernel machines efficiently learn sparse functions
• Scalable Interpretability via Polynomials
• On the scaling of polynomial features for representation matching
• Hierarchical learning in polynomial Support Vector Machines