Minimax-optimal semi-supervised regression on unknown manifolds

Applied Mathematics
Event time: 
Tuesday, October 2, 2018 - 4:00pm
LOM 215
Amit Moscovich
Speaker affiliation: 
Event description: 
n recent years, many semi-supervised regression and classification methods have been proposed. These methods demonstrated empirical success on some data sets, whereas on others the unlabeled data did not appear to help.
To analyze semi-supervised learning theoretically, it is often assumed that the data points lie on a low-dimensional manifold. Under this assumption [1] and [2] have shown that classical nonparametric regression methods, using only the labeled data, can achieve optimal rates of convergence. This implies that asymptotically, as the number of labeled points tends to infinity, unlabeled data does not help. However, typical semi-supervised scenarios involve few labeled points, and plenty of unlabeled ones.
In this work ([3]) we clarify the potential benefits of unlabeled data under the manifold assumption, given a fixed amount of labeled points. Specifically, we prove that for a Lipschitz function on a manifold, a simple semi-supervised regression method based on geodesic k-nearest-neighbors achieves the finite-sample minimax bound on the mean squared error, provided that sufficiently many unlabeled points are available. Furthermore, we show that this approach is computationally efficient, requiring only O(k N log N) operations to estimate the regression function for 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, the proposed method is more accurate and much faster than the popular Laplacian eigenvector regressor [4].
The talk should be accessible to anyone with a general background in statistics and machine learning. Specifically, no knowledge of manifold geometry or minimax theory is assumed.
Joint work with Ariel Jaffe (Yale) and Boaz Nadler (Weizmann Institute).
Amit Moscovich (Princeton PACM)
[1] Bickel, P. J. and Li, B. “Local polynomial regression on unknown manifolds”. Tomography, Networks and Beyond (2007).
[2] Lafferty, J. and Wasserman, L. “Statistical analysis of semi-supervised regression”. NIPS (2007).
[3] Moscovich, A. Jaffe, A. and Nadler, B. “Minimax-optimal semi-supervised regression on unknown manifolds”. AISTATS (2017).
[4] Belkin, M. and Niyogi, P. “Semi-supervised learning on riemannian manifolds”. Machine learning (2004).