Minimax-optimal semi-supervised regression on unknown manifolds

Abstract

We consider semi-supervised regression when the predictor variables are drawn from an unknown manifold. A simple two step approach to this problem is to: (i) estimate the manifold geodesic distance between any pair of points using both the labeled and unlabeled instances; and (ii) apply a k nearest neighbor regressor based on these distance estimates. We prove that given sufficiently many unlabeled points, this simple method of geodesic kNN regression achieves the optimal finite-sample minimax bound on the mean squared error, as if the manifold were known. Furthermore, we show how this approach can be efficiently implemented, requiring only O(k N log N) operations to estimate the regression function at all N labeled and unlabeled points. We illustrate this approach on two datasets with a manifold structure: indoor localization using WiFi fingerprints and facial pose estimation. In both cases, geodesic kNN is more accurate and much faster than the popular Laplacian eigenvector regressor.

References in corpus (1)

• Local polynomial regression on unknown manifolds

Cited by in corpus (7)

• Manifold learning with arbitrary norms
• Approximation of Functions over Manifolds: A Moving Least-Squares Approach
• Manifold regularization with GANs for semi-supervised learning
• High-dimensional semi-supervised learning: in search for optimal inference of the mean
• Built Year Prediction from Buddha Face with Heterogeneous Labels
• Approximating the Riemannian Metric from Point Clouds via Manifold Moving Least Squares
• Achieving the time of $1$-NN, but the accuracy of $k$-NN