Nonparametric Online Regression while Learning the Metric

Ilja Kuzborskij, Nicolò Cesa-Bianchi

Abstract

Online nonparametric regression often suffers from the "curse of dimensionality," where regret bounds scale poorly with the ambient dimension $d$. This paper introduces an adaptive algorithm that learns a Mahalanobis metric based on the Gradient Outer Product Matrix (GOPM) of the target function. By aligning search ellipsoids with directions of maximum variation, the algorithm achieves regret bounds determined by the "effective rank" $\rho_T$ of the data. This approach significantly improves performance when the target function is smooth in most directions, effectively bypassing the ambient dimensionality constraints.

Introduction

In online nonparametric regression, a learner predicts labels for a sequence of data points without assuming a specific functional form. The standard performance metric is regret: the difference between the learner's total loss and the loss of the best possible function in a large class of smooth functions.

Traditional algorithms face a fundamental challenge: the curse of dimensionality. Regret bounds typically grow as $T^{d/(1+d)}$, where $d$ is the number of features. However, in many real-world scenarios, the target function might be very smooth in most directions and only change rapidly along a few "important" directions. Standard methods using Euclidean distance treat all directions equally, missing the opportunity to simplify the problem by exploiting this directional smoothness.

Methods

The authors build upon the classic "sphere packing" approach by partitioning the input space using ellipsoids defined by a Mahalanobis metric. This allows the algorithm to be more sensitive in directions where the function changes quickly and more forgiving where it is smooth.

The proposed online regression algorithm using adaptive metric learning.

The algorithm, detailed in the pseudocode above, maintains a collection of centers $S$. For each new data point $x_t$, it identifies the nearest center $s$ in the Mahalanobis space, predicts using the historical average of labels in that region, and then decides whether to update the current ellipsoid or create a new one based on the radius $\epsilon_t$. A key innovation is the periodic estimation of the Gradient Outer Product Matrix (GOPM), which captures the directions of maximum variation to update the metric $M$.

Effective Rank and Theoretical Results

The paper introduces the concept of Effective Rank ($\rho_T$), a parameter that measures how many eigenvalues of the metric are significantly large. If the target function's gradient mostly lives in a low-dimensional subspace, $\rho_T$ will be much smaller than the ambient dimension $d$.

Evolution of eigenvalues and effective rank $\rho_t$ over time.

As shown in Figure 1, the algorithm automatically adapts to the spectrum of the gradient matrix. If the eigenvalues decay quickly, the effective rank remains low, leading to tighter regret bounds. The paper proves that when learning the metric on the fly in a stochastic setting, the algorithm achieves a high-probability regret bound of order: $$\tilde{O}\left( \text{poly}(d) \cdot T^{\frac{\rho_T}{1+\rho_T}} \right)$$ This result demonstrates that the learning rate is governed by the intrinsic dimensionality of the function's variation rather than the full feature space.

Key Insights

  • Directional Smoothness: Lipschitz continuity should not be treated as a single scalar. By aligning the axes of search ellipsoids with the function's gradient, the algorithm packs the space more efficiently.
  • Spectral Adaptivity: The algorithm does not require prior knowledge of the "true" rank. It adapts to the eigenvalues of the GOPM, improving regret automatically as it identifies the most relevant directions.

Limitations and Future Work

While the theoretical guarantees are robust, the current analysis assumes data instances are drawn i.i.d. to facilitate metric learning. Extending this to a fully adversarial setting remains an open challenge. Additionally, while the algorithm is theoretically efficient, the nearest-neighbor search in Mahalanobis space and periodic GOPM estimation could be computationally intensive for very high-dimensional streaming data. Future research may explore "local" metric learning, where the metric adapts differently across different regions of the input space.

Summary updated

Abstract

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.
BibTeX
@inproceedings{kuzborskij2017nonparametric,
  author = {Ilja Kuzborskij and Nicolò Cesa-Bianchi},
  title = {{Nonparametric Online Regression while Learning the Metric}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2017},
  url = {https://openreview.net/forum?id=B1bnPwZ_WB},
}
Figure