Are there any learning algorithms with any provable guarantees for manifold learning or manifold regularization?

Question

First of all, I want to make clear that my question is about algorithms. I'd like to know if there are any algorithms with provable guarantees in the context of manifold learning (or manifold regularization).

I do not necessarily require that guarantees are with respect to generalization. However, those are always nice though but I just want to emphasize that the main focus of the question is about algorithms (with guarantees), not necessarily about generalization.

What I do want is that given a finite sample of data (maybe mixed with labeled and unlabeled data) if we can provably learn. For example, are there algorithms that guarantee that we learn the manifold or its structure? Or maybe, are there algorithms that theoretically guarantee better prediction with the manifold assumption? Any algorithm with provable guarantees is good.

---

To be clear of what I mean with provable guarantees I will give a couple of examples of scenarios/problems (and algorithms) where there are provable guarantees for (learning) algorithms.

Consider the non-negative matrix factorization problem where we have:

$$M = AW$$

s.t. A and W are $m \times k$ and $k \times n$ and are required to be entry-wise nonnegative. In fact, lets suppose that the columns of M each sum to one. One can interpret this problem as follows. Each column is a document from our model. Its generated as a convex combination from topics (i.e. the columns of A). The combination is specified by the columns of W. Can we recover the best non-negative factorization of the model? It turns out that Vavasis proved its NP-hard 1. However, under the separability condition on the topics, one can show that there exists a polynomial time algorithm to compute such a non-negative factorization (of minimum inner-dimension). So this scenario has two things that are interesting:

1. We can learn the true model (the negative factorization) from the (samples) documents (with some probability conditions)
2. There a polynomial time algorithm for it.

The algorithm for this is based on finding the "Anchor words" (i.e. the highly technical words for each document) and then taking advantage of that to find the factorization. The some of the details for this can be found on this monograph on algorithmic aspects of machine learning.

This is exactly the type of thing I am interested in, on learning algorithms with some provable guarantees under some conditions. For more example, the following monograph has many that are appropriate examples. To name the monograph explains tensor methods, ICA, alternating minimization, mixtures of gaussians, matrix completion, phylogenetic trees, noisy parity and more!

---

References:

1 S. Vavasis. On the complexity of nonnegative matrix factorization. SIAM Journal on Optimization, pages 1364-1377, 2009.

Answer 1

It depends what you mean by "learn[ing] the manifold", but here are a few papers that present some algorithms and a theoretical analysis:

1. Isomap (see tech report by Bernstein, de Silva, Langford and Tenenbaum)
2. Random linear projections (see paper by Ken Clarkson)
3. Nash-type embedding (see paper by Nakul Verma)
4. Maximum variance unfolding (see arXiv:1209.0016)

In terms of using/exploiting manifold structure to help learning or estimation, there are many such results. For example, many of the papers by Misha Belkin and Samory Kpotufe explore this direction.