Single Index Models (SIMs) are simple yet flexible semi-parametric models for classification and regression, where 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 that relates features to observations. While methods have been described to learn SIMs in the low dimensional regime, a method that can efficiently learn SIMs in high dimensions, and under general structural assumptions, has not been forthcoming. In this paper, we propose computationally efficient algorithms for SIM inference in high dimensions using atomic norm regularization. This general approach to imposing structure in high-dimensional modeling specializes to sparsity, group sparsity, and low-rank assumptions among others. We also provide a scalable, stochastic version of the method. Experiments show that the method we propose enjoys superior predictive performance when compared to generalized linear models such as logistic regression, on several real-world datasets.
@cite_14: Consider measuring an n-dimensional vector x through the inner product with several measurement vectors, a_1, a_2, ..., a_m. It is common in both signal processing and statistics to assume the linear response model y_i = + e_i, where e_i is a noise term. However, in practice the precise relationship between the signal x and the observations y_i may not follow the linear model, and in some cases it may not even be known. To address this challenge, in this paper we propose a general model where it is only assumed that each observation y_i may depend on a_i only through . We do not assume that the dependence is known. This is a form of the semiparametric single index model, and it includes the linear model as well as many forms of the generalized linear model as special cases. We further assume that the signal x has some structure, and we formulate this as a general assumption that x belongs to some known (but arbitrary) feasible set K. We carefully detail the benefit of using the signal structure to improve estimation. The theory is based on the mean width of K, a geometric parameter which can be used to understand its effective dimension in estimation problems. We determine a simple, efficient two-step procedure for estimating the signal based on this model -- a linear estimation followed by metric projection onto K. We give general conditions under which the estimator is minimax optimal up to a constant. This leads to the intriguing conclusion that in the high noise regime, an unknown non-linearity in the observations does not significantly reduce one's ability to determine the signal, even when the non-linearity may be non-invertible. Our results may be specialized to understand the effect of non-linearities in compressed sensing.
@cite_26: Most recent results in matrix completion assume that the matrix under consideration is low-rank or that the columns are in a union of low-rank subspaces. In real-world settings, however, the linear structure underlying these models is distorted by a (typically unknown) nonlinear transformation. This paper addresses the challenge of matrix completion in the face of such nonlinearities. Given a few observations of a matrix that are obtained by applying a Lipschitz, monotonic function to a low rank matrix, our task is to estimate the remaining unobserved entries. We propose a novel matrix completion method that alternates between low-rank matrix estimation and monotonic function estimation to estimate the missing matrix elements. Mean squared error bounds provide insight into how well the matrix can be estimated based on the size, rank of the matrix and properties of the nonlinear transformation. Empirical results on synthetic and real-world datasets demonstrate the competitiveness of the proposed approach.
@cite_29: This paper addresses the problem of fitting nonlinear regression models in high-dimensional situations, where the number of predictors, p , is large relative to the number of observations, n . Most of the research in this area has been conducted under the assumption that the regression function has a simple additive structure. This paper focuses instead on single index models, which are becoming increasingly popular in many scientific fields including biostatistics, economics and financial econometrics. Novel methodology is presented for estimating high-dimensional single index models and simultaneously performing variable selection. A computationally efficient algorithm is provided for constructing a solution path. Asymptotic theory is developed for the proposed estimates of the regression function and the index coefficients in the high-dimensional setting. An investigation of the empirical performance on both simulated and real data demonstrates strong performance of the proposed approach.
@cite_21: 
@cite_9: 
@cite_19: Constructing a good approximation to a function of many variables suffers from the “curse of dimensionality”. Namely, functions on ℝN with smoothness of order s can in general be captured with accuracy at most O(n−s N) using linear spaces or nonlinear manifolds of dimension n. If N is large and s is not, then n has to be chosen inordinately large for good accuracy. The large value of N often precludes reasonable numerical procedures. On the other hand, there is the common belief that real world problems in high dimensions have as their solution, functions which are more amenable to numerical recovery. This has led to the introduction of models for these functions that do not depend on smoothness alone but also involve some form of variable reduction. In these models it is assumed that, although the function depends on N variables, only a small number of them are significant. Another variant of this principle is that the function lives on a low dimensional manifold. Since the dominant variables (respectively the manifold) are unknown, this leads to new problems of how to organize point queries to capture such functions. The present paper studies where to query the values of a ridge function f(x)=g(a⋅x) when both a∈ℝN and g∈C[0,1] are unknown. We establish estimates on how well f can be approximated using these point queries under the assumptions that g∈Cs[0,1]. We also study the role of sparsity or compressibility of a in such query problems.
Alquier and Biau @cite_21 consider learning high dimensional single index models. They provide estimators of @math using PAC-Bayesian analysis, which relies on reversible jump MCMC, and is slow to converge even for moderately sized problems. @cite_29 learns high dimensional single index models with simple sparsity assumptions on the weight vectors, while @cite_26 provide methods to learn SIM's in the matrix factorization setting. While these are first steps towards learning high dimensional SIM's, our method can handle several types of structural assumptions, generalizing these approaches to several other structures in an elegant manner. Restricted versions of the SIM estimation problem with (structured) sparsity constraints have been considered in @cite_14 @cite_9 , where the authors are only interested in accurate parameter estimation and not prediction. Hence, in these works the proposed algorithms do not learn the transfer function. We finally comment that there is also related literature focused on how to query points in order to learn the SIM, such as @cite_19 .