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 l(2)-ball in R-d, g is twice continuously differentiable almost everywhere, and A is an element of R-kxd 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) = Sigma(k)(i=1) g(i)(a(i)(T)x), 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. (C) 2014 Elsevier Inc. All rights reserved.


Published in:
Applied And Computational Harmonic Analysis, 37, 3, 389-412
Year:
2014
Publisher:
San Diego, Elsevier
ISSN:
1063-5203
Keywords:
Laboratories:




 Record created 2014-10-23, last modified 2018-03-17


Rate this document:

Rate this document:
1
2
3
 
(Not yet reviewed)