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

<ol>
<li>Isomap (see tech report by Bernstein, de Silva, Langford and Tenenbaum)</li>
<li>Random linear projections (see paper by Ken Clarkson)</li>
<li>Nash-type embedding (see paper by Nakul Verma)</li>
<li>Maximum variance unfolding (see arXiv:1209.0016)</li>
</ol>

<p>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.</p>

CC BY-SA 3.0
2015-08-02T22:47:46.747Z
Welcome to cstheory, @Daniel!
Lev Reyzin
CC BY-SA 3.0
2015-08-02T18:36:03.440Z
2015-08-02T18:36:03.440Z
Daniel
<p>First of all, I want to make clear that my question is about <strong>algorithms</strong>. I'd like to know if there are <strong>any</strong> algorithms with <strong>provable guarantees</strong> in the context of manifold learning (or manifold regularization). </p>

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

<p>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.</p>

<hr>

<p>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.</p>

<p>Consider the non-negative matrix factorization problem where we have:</p>

<p>$$M =  AW$$</p>

<p>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 <a href="http://people.csail.mit.edu/moitra/docs/bookex.pdf" rel="nofollow">1</a>. However, under the separability condition on the topics, one can show that there exists a <strong>polynomial time algorithm to compute such a non-negative factorization</strong> (of minimum inner-dimension). So this scenario has two things that are interesting:</p>

<ol>
<li>We can learn the true model (the negative factorization) from the (samples) documents (with some probability conditions)</li>
<li>There a polynomial time algorithm for it.</li>
</ol>

<p>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 <a href="http://people.csail.mit.edu/moitra/docs/bookex.pdf" rel="nofollow">this monograph on algorithmic aspects of machine learning</a>.</p>

<p>This is exactly the type of thing I am interested in, on learning <strong>algorithms</strong> with some <strong>provable guarantees</strong> under some conditions. For more example, the following <a href="http://people.csail.mit.edu/moitra/docs/bookex.pdf" rel="nofollow">monograph</a> 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!</p>

<hr>

<p>References:</p>

<p><a href="http://people.csail.mit.edu/moitra/docs/bookex.pdf" rel="nofollow">1</a> S. Vavasis. On the complexity of nonnegative matrix factorization. SIAM
Journal on Optimization, pages 1364-1377, 2009.</p>

CC BY-SA 3.0
2015-05-04T23:45:18.120Z
check "Blind Source Separation" and "Information Geometry" for (approximation) algorithms of this kind and their theoretical analysis on efficiency and accuracy
Nikos M.
CC BY-SA 3.0
2015-08-02T23:38:27.387Z
I guess you can call it a monologue but you probably meant monograph.
Sasho Nikolov
CC BY-SA 3.0
2015-08-03T00:47:29.803Z
@SashoNikolov typo! Ooops! Corrected it. Thanks.
Charlie Parker
CC BY-SA 3.0
2015-08-03T15:42:02.447Z
@RickyDemer yes. Thanks. Don't know how these mistakes escaped me.
Charlie Parker
<ds.algorithms><approximation-algorithms><machine-learning>
Are there any learning algorithms with any provable guarantees for manifold learning or manifold regularization?
Charlie Parker
# Are there any learning algorithms with any provable guarantees for manifold learning or manifold regularization?

(Asked by: username_0 on 2015-05-04)

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](http://people.csail.mit.edu/moitra/docs/bookex.pdf). 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](http://people.csail.mit.edu/moitra/docs/bookex.pdf).

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](http://people.csail.mit.edu/moitra/docs/bookex.pdf) 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](http://people.csail.mit.edu/moitra/docs/bookex.pdf) S. Vavasis. On the complexity of nonnegative matrix factorization. SIAM
Journal on Optimization, pages 1364-1377, 2009.

**Tags:** ds.algorithms, approximation-algorithms, machine-learning
> **Comments:**
> **username_1**: check "Blind Source Separation" and "Information Geometry" for (approximation) algorithms of this kind and their theoretical analysis on efficiency and accuracy  
> **username_2**: I guess you can call it a monologue but you probably meant monograph.  
> **username_0**: @SashoNikolov typo! Ooops! Corrected it. Thanks.  
> **username_0**: @RickyDemer yes. Thanks. Don't know how these mistakes escaped me.  

---

## 1 answers

### Answer by username_3 on 2015-08-02. Score: 2

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.

> **Comments:**
> **username_4**: Welcome to cstheory, @Daniel!  

---

