Abstract

We consider the problem of actively learning multi-index functions of the form Pk from point evaluations of f . We assume that the function f is defined on an -ball in g is twice continuously differentiable almost everywhere, and is a rank k matrix, where 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 highdimensional scaling of our sample complexity bounds are quite accurate.