Active Learning of Multi-Index Function Models

摘要

We consider the problem of actively learning multi-index functions of the form f(x) = g(Ax) = ∑_i~k=1 gi(a_i~Tx) fr°m Point evaluations of f. We assume that the function / is defined on an ℓ_2-ball in R~d, g is twice continuously differen-tiable almost everywhere, and A ∈ R~(k×d) is a rank k matrix, where k « d. We propose a randomized, active sampling scheme for estimating such functions with uniform approximation guarantees. Our theoretical developments leverage recent techniques from low rank matrix recovery, which enables us to derive an estimator of the function f along with sample complexity bounds. We also characterize the noise robustness of the scheme, and provide empirical evidence that the high-dimensional scaling of our sample complexity bounds are quite accurate.