  Single Index Models (SIMs) are simple yet flexible semi-parametric models for
classification and regression. Response variables are modeled as a nonlinear,
monotonic function of a linear combination of features. Estimation in this
context requires learning both the feature weights, and the nonlinear function.
While methods have been described to learn SIMs in the low dimensional regime,
a method that can efficiently learn SIMs in high dimensions has not been
forthcoming. We propose three variants of a computationally and statistically
efficient algorithm for SIM inference in high dimensions. We establish excess
risk bounds for the proposed algorithms and experimentally validate the
advantages that our SIM learning methods provide relative to Generalized Linear
Model (GLM) and low dimensional SIM based learning methods.
