Learning non-parametric basis independent models from point queries via low-rank methods

摘要

We consider the problem of learning multi-ridge functions of the form f(x) = g( Ax) from point evaluations of f. We assume that the function f is defined on an ℓ_2-ball in R~d, g is twice continuously differentiable almost everywhere, and A ∈ R~(k×d) is a rank k matrix, where k (＜＜) d. We propose a randomized, polynomial-complexity sampling scheme for estimating such functions. Our theoretical developments leverage recent techniques from low rank matrix recovery, which enables us to derive a polynomial time estimator of the function f along with uniform approximation guarantees. We prove that our scheme can also be applied for learning functions of the form: f(x) = ∑_(i=1)~k g_i(a_i~Tx), provided f satisfies certain smoothness conditions in a neighborhood around the origin. We also characterize the noise robustness of the scheme. Finally, we present numerical examples to illustrate the theoretical bounds in action.