Learning ridge functions with randomized sampling in high dimensions

We study the problem of learning ridge functions of the form f(x) = g(a^T x), x ∈ ℝ^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 de facto compressibility assumption on the parameter a 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 O(log d) to O(d) or from equation to O(d^2+q/2-q) to O(d⁴), depending on the behaviour of g\´ and g" at the origin, with 0 <; q <; 1 characterizing the sparsity of a.