Robust Nonparametric Regression with Metric-Space Valued Output

Matthias HeinNeurIPS 2009 · OpenReview

Introduction

Standard regression techniques typically assume that output variables exist in a standard Euclidean space ($\mathbb{R}^n$). However, many modern machine learning applications involve "structured" outputs that do not fit this assumption. This paper introduces a unified framework for nonparametric regression where outputs live in complex metric spaces, such as Riemannian manifolds or structured discrete sets. By incorporating robust loss functions into kernel-smoothing estimators, the author provides a principled way to handle outliers in non-Euclidean data while mathematically guaranteeing that these estimators converge to the optimal solution.

The Challenge of Manifold-Valued Data

Real-world problems frequently constrain data to non-Euclidean geometries:

  • Computer Vision: Estimating the 3D rotation of an object means outputs live on the manifold $SO(3)$.
  • Medical Imaging: Analyzing organ shapes or diffusion tensors requires specialized geometric representations.
  • Robotics: Predicting joint configurations must respect physical, non-linear constraints.

When outputs are constrained to a manifold, standard averaging techniques—like the Nadaraya-Watson estimator—fail. For instance, the Euclidean "average" of two points on the surface of a sphere might fall inside the sphere, rather than on its surface. While previous work has addressed manifold-valued regression using squared distances (known as the "Fréchet mean"), these methods are notoriously sensitive to outliers. This paper tackles the challenge of making manifold regression robust while providing a rigorous proof of its consistency (ensuring the model converges to the true function as data increases).

A Robust Nonparametric Framework

The author proposes a family of kernel-smoothing estimators $\phi_l(x)$ defined as the minimizer of a weighted objective function:

$$\phi_l(x) = \arg \min_{q \in N} \frac{1}{l} \sum_{i=1}^l \Gamma(d_N(q, Y_i)) k_h(d_M(x, X_i))$$

Key Components: * Metric Spaces ($M, N$): The input $X$ and output $Y$ live in metric spaces with distance functions $d_M$ and $d_N$, respectively. * Robust Loss Functions ($\Gamma$): Instead of relying solely on squared distance ($L_2$), the paper introduces $(\alpha, s)$-bounded convex losses. This allows the use of $L_1$-type loss (for generalized medians), Huber loss (a hybrid that is robust yet smooth), and $\epsilon$-insensitive loss. * Optimization: For outputs on Riemannian manifolds, the paper utilizes a gradient descent algorithm that leverages the exponential map to ensure the estimated points always remain strictly on the manifold. * Theoretical Proof: The core theoretical contribution is a proof of Bayes consistency. The author demonstrates that as the sample size $l \to \infty$, the estimator converges to the best possible mapping, even when using non-smooth loss functions like $L_1$.

Experimental Validation

The approach is evaluated using a synthetic toy experiment designed to test robustness. The task involves estimating a curve on a 1D sphere ($S^1$) embedded in $\mathbb{R}^2$, with inputs in the interval $[0, 1]$. The data is disturbed by van-Mises noise (the circular equivalent of Gaussian noise), and to test robustness, 20% of the training points are replaced with random outliers.

Quantitative comparison of estimators with and without outliers.

As shown in the quantitative results above, the $L_1$ and Huber loss estimators significantly outperform the standard $L_2$ (mean-based) estimator when outliers are introduced. The Huber loss emerges as a "sweet spot," handling outliers effectively while remaining more stable than the $L_1$ loss in outlier-free scenarios.

Visual comparison of L1, L2, and Huber loss estimators on a synthetic dataset with outliers.

Qualitative visual results further reinforce these findings. While the $L_2$ estimate is visibly "pulled" away from the true underlying curve by the presence of outliers, the $L_1$ and Huber estimates remain almost perfectly aligned with the ground truth.

Key Theoretical Insights

Beyond the empirical results, the paper offers several important theoretical takeaways:

  • Unification of Fields: The framework demonstrates that manifold-valued regression and "structured output learning" (commonly used in NLP or bioinformatics) are essentially two sides of the same coin—both represent regression in metric spaces.
  • The "Difficulty" Myth: A major insight is that regression on manifolds is not fundamentally "harder" to learn than standard regression. The author proves that the convergence rate ($l h^m / \log l \to \infty$) is identical to the classic Euclidean Nadaraya-Watson estimator.
  • Functional Convergence: Unlike typical proofs that track the movement of the minimizer, this proof analyzes the convergence of the entire objective functional. This novel approach allows the author to handle robust losses that might not have a unique or smooth minimizer.

Limitations and Future Directions

While powerful, the proposed framework has limitations. Because the estimator requires solving an optimization problem for every single test point, it is computationally much more expensive than a simple weighted average. Furthermore, the kernel estimator is inherently a "local" method; "global" methods that regularize the entire mapping at once might perform better, though they are significantly more complex to implement and analyze. Finally, the current implementation assumes the output space is a Riemannian manifold where gradients and exponential maps can be computed. Extending this to more "exotic" metric spaces, such as graphs or strings, will require the development of new optimization strategies.

Summary updated

Abstract

Motivated by recent developments in manifold-valued regression we propose a family of nonparametric kernel-smoothing estimators with metric-space valued output including a robust median type estimator and the classical Frechet mean. Depending on the choice of the output space and the chosen metric the estimator reduces to partially well-known procedures for multi-class classification, multivariate regression in Euclidean space, regression with manifold-valued output and even some cases of structured output learning. In this paper we focus on the case of regression with manifold-valued input and output. We show pointwise and Bayes consistency for all estimators in the family for the case of manifold-valued output and illustrate the robustness properties of the estimator with experiments.
BibTeX
@inproceedings{hein2009robust,
  author = {Matthias Hein},
  title = {{Robust Nonparametric Regression with Metric-Space Valued Output}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2009},
  url = {https://openreview.net/forum?id=S17c0UbOWB},
}
Figure