Active learning of self-concordant like multi-index functions

We study the problem of actively learning a multi-index function of the form f(x) = g₀(A₀x) from its point evaluations, where A₀ ∈ ℝ^k×d with k ≫ d. We build on the assumptions and techniques of an existing approach based on low-rank matrix recovery (Tyagi and Cevher, 2012). Specifically, by introducing an additional self- concordant like assumption on g0 and adapting the sampling scheme and its analysis accordingly, we provide a bound on the sampling complexity with a weaker dependence on d in the presence of additive Gaussian sampling noise. For example, under natural assumptions on certain other parameters, the dependence decreases from O(d^3/2) to O(d^¾).