NeurIPS 2020

The Statistical Cost of Robust Kernel Hyperparameter Turning

Meta Review

This paper is concerned with active regression under adversarial noise, where the underlying function is assumed to live in a space induced by a parametric kernel with unknown hyperparameters (e.g., bandwidth of RBF kernel). Previous work shows that shows that if the kernel parameters are known exactly a priori, then efficient learning is possible. This work shows that if one does not know the kernel parameters a priori for a class of kernels, there exists an algorithm that learns these hyperparameters online and requires a sample complexity not much larger than if the kernel had been known for this adversarial active regression problem. However, while the statistical sample complexity is small, the computational complexity remains an issue and little guidance is given on how to overcome the exponential time naive algorithm. Moreover, reviewers also questioned the applicability of the approach—when is adversarial noise a good model? Where is this used? The authors addressed the applicability point in their rebuttal by simply restating a paper they had already cited, and not justified why adversarial noise was the right model here. The authors are strongly encouraged to make a case for how this work could potentially have impact in practice. Or on the other hand, acknowledge this is a theoretical result only and argue why it is fundamental.