Timezone: »

 
Poster
Nonparametric Online Regression while Learning the Metric
Ilja Kuzborskij · Nicolò Cesa-Bianchi

Wed Dec 06 06:30 PM -- 10:30 PM (PST) @ Pacific Ballroom #52
in Posters Wed »
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.
Keywords: Online Learning
[ Paper] 

Author Information

Ilja Kuzborskij (University of Milan)
Nicolò Cesa-Bianchi (Università degli Studi di Milano, Italy)

More from the Same Authors