Active learning of self-concordant like multi-index functions
Ilija Bogunovic, Volkan Cevher, Jarvis D. Haupt, Jonathan Scarlett
Abstract
We study the problem of actively learning a multi-index function of the form f(x) = g <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">0</sub> (A <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">0</sub> x) from its point evaluations, where A <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">0</sub> ∈ ℝ <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">k×d</sup> 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 <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">3/2</sup> ) to O(d <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">¾</sup> ).
BibTeX
@inproceedings{icassp2015_activelearningof,
title = {Active learning of self-concordant like multi-index functions},
author = {Ilija Bogunovic and Volkan Cevher and Jarvis D. Haupt and Jonathan Scarlett},
booktitle = {ICASSP 2015},
year = {2015}
}