Nonparametric Online Regression while Learning the Metric
This work addresses online learning challenges in nonparametric settings by adapting metrics, offering incremental improvements in algorithm design.
The paper tackles the problem of online nonparametric regression by developing an algorithm that learns a Mahalanobis metric based on the gradient outer product matrix to adapt to the smoothness directions of the regression function, achieving regret bounds in terms of the spectrum of this matrix.
We study algorithms for online nonparametric regression that learn the directions along which the regression function is smoother. Our algorithm learns the Mahalanobis metric based on the gradient outer product matrix $\boldsymbol{G}$ of the regression function (automatically adapting to the effective rank of this matrix), while simultaneously bounding the regret ---on the same data sequence--- in terms of the spectrum of $\boldsymbol{G}$. As a preliminary step in our analysis, we extend a nonparametric online learning algorithm by Hazan and Megiddo enabling it to compete against functions whose Lipschitzness is measured with respect to an arbitrary Mahalanobis metric.