Learning Non-Parametric Basis Independent Models from Point Queries via Low-Rank Methods

Hemant Tyagi, V. Cevher

Research output: Contribution to journalArticlepeer-review


We consider the problem of learning multi-ridge functions of the form f(x)=g(Ax)f(x)=g(Ax) from point evaluations of f. We assume that the function f is defined on an ℓ2ℓ2-ball in RdRd, g is twice continuously differentiable almost everywhere, and A∈Rk×dA∈Rk×d is a rank k matrix, where k≪dk≪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: View the MathML sourcef(x)=∑i=1kgi(aiTx), 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.
Original languageEnglish
Pages (from-to)389-412
Number of pages24
JournalApplied and Computational Harmonic Analysis
Issue number3
Early online date15 Jan 2014
Publication statusPublished - 3 Nov 2014


Dive into the research topics of 'Learning Non-Parametric Basis Independent Models from Point Queries via Low-Rank Methods'. Together they form a unique fingerprint.

Cite this