Active Learning of Self-concordant like Multi-index Functions

Abstract

We study the problem of actively learning a multi-index function of the form $f(x) = g_0(A_0x)$ from its point evaluations, where $A_0 \in \mathbb{R}^{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 $g_0$ 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.