Learning Ridge Functions with Randomized Sampling in High Dimensions

• Publication date: 2011

We study the problem of learning \textit{ridge} functions of the form f(\vecx) = g(\veca^T\vecx), \vecx \in \Real^d, from random samples. Assuming g to be a twice continuously differentiable function, we leverage techniques from low rank matrix recovery literature to derive a uniform approximation guarantee for estimation of the ridge function f. Our new analysis removes the {\em de facto} compressibility assumption on the parameter \veca for learning in the existing literature. Interestingly the price to pay in high dimensional settings is not major. For example, when g is thrice continuously differentiable in an open neighbourhood of the origin, the sampling complexity changes from \mathcal{O}(\log d) to \mathcal{O}(d) or from \mathcal{O}(d^{2+\frac{q}{2-q}}) to \mathcal{O}(d^4), depending on the behaviour of g^{\prime} and g^{\prime\prime} at the origin, with 0 < q < 1 characterizing the sparsity of \veca.

Keywords: Ridge functions, high dimensional function approximation, low rank recovery

Reference

• EPFL-REPORT-169199

Record created on 2011-10-03, modified on 2012-03-21