# Minimax-optimal semi-supervised regression on unknown manifolds

arXiv: https://arxiv.org/abs/1611.02221 · HTML: https://mlsanity.com/paper/1611.02221/

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 7 Nov 2016.

## Built on by (most cited first, 7 of 7)

- [Diffusion Models and the Manifold Hypothesis: Log-Domain Smoothing is Geometry Adaptive](https://mlsanity.com/paper/2510.02305/) (2025)
- [Fermat Distances: Metric Approximation, Spectral Convergence, and Clustering Algorithms](https://mlsanity.com/paper/2307.05750/) (2023)
- [Learning Distances from Data with Normalizing Flows and Score Matching](https://mlsanity.com/paper/2407.09297/) (2024)
- [Deep Clustering with a Constraint for Topological Invariance based on Symmetric InfoNCE](https://mlsanity.com/paper/2303.03036/) (2023)
- [Diffusion Maps for Group-Invariant Manifolds](https://mlsanity.com/paper/2303.16169/) (2023)
- [Built Year Prediction from Buddha Face with Heterogeneous Labels](https://mlsanity.com/paper/2109.00812/) (2021)
- [Semi-supervised Fr'echet Regression](https://mlsanity.com/paper/2404.10444/) (2024)

## Abstract (arXiv)

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.