Nonparametric Online Regression while Learning the Metric
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 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 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.
This paper describes a novel algorithm for online nonparametric regression problem. It employs Mahalanobis metric to obtain a better distance measurement in the traditional online nonparametric regression framework. In terms of theoretical analysis, the proposed algorithm improves the regret bound and achieves a competitive result to the state-of-the-art. The theoretical proof is well organized and correct to the reviewer.
However, the novelty of the proposed algorithm may be limited. The overall algorithm consists two separable components: online nonparametric regression with Mahalanobis metric, the estimation of gradient outer-product. 
The first component is a straightforward extension from [7], which proposed a general framework including all kinds of distance metric spaces. In Algorithm 1, it is obvious that the proposed work specializes the metric space as Mahalanobis distance and keep other steps unchanged. Therefore, the statement that the proposed algorithm is a generalized version of the algorithm from [7] in line 244 is improper. This extension is valuable only when the motivation of incorporating Mahalanobis distance is clearly introduced and convincing. Otherwise, this work mainly discusses a special case in the framework of [7]. On the other hand, the significance of the proposed method and the related regret bound should be discussed with more details. Because compared with the original method in [7], the improvement of regret bound depends on the specific problem.
The second component is an application from [14] to estimate the gradient outer-product. The authors should discuss the increased computational complexity brought by this phase.
Some minor issues:
1.	How does one compute the active center efficiently in line 8 of Algorithm 1
2.	$\tilde{\rho}$ in Theorem 2 is not defined. 
3.	What's the relationship between smoother f_0 and Mahalanobis metric?
4.	There is no experimental evaluation to demonstrate the improvement of the proposed method in comparison with the original framework in terms of accuracy or convergence rate.