A Fast, Universal Algorithm to Learn Parametric Nonlinear Embeddings
Nonlinear embedding algorithms such as stochastic neighbor embedding do dimensionality reduction by optimizing an objective function involving similarities between pairs of input patterns. The result is a low-dimensional projection of each input pattern. A common way to define an out-of-sample mapping is to optimize the objective directly over a parametric mapping of the inputs, such as a neural net. This can be done using the chain rule and a nonlinear optimizer, but is very slow, because the objective involves a quadratic number of terms each dependent on the entire mapping's parameters. Using the method of auxiliary coordinates, we derive a training algorithm that works by alternating steps that train an auxiliary embedding with steps that train the mapping. This has two advantages: 1) The algorithm is universal in that a specific learning algorithm for any choice of embedding and mapping can be constructed by simply reusing existing algorithms for the embedding and for the mapping. A user can then try possible mappings and embeddings with less effort. 2) The algorithm is fast, and it can reuse N -body methods developed for nonlinear embeddings, yielding linear-time iterations.
Note 1 - this is a 'light review'. Note 2 - I was not able to open the supplementary file, the provided archive .gz did not contain any readable file type. The paper presents an optimization approach for parametric out-of-sample extension of nonlinear dimensionality reduction algorithms.Solutions are constrained a desired parametric family whose parameters are optimized based on an auxiliary coordinate approach, alternatively optimizing a regularized loss with respect to auxiliary coordinates and then the mapping as a regression to the coordinates.Experiments on three data sets show that the method achieves solutions about equal in quality to direct optimization of parametric embeddings but is faster. Another advantage is that it does not require separate derivation of optimization equations for each loss + parametric family combination.  Evaluation:The idea is good and out of sample extension is a common problem in nonlinear dimensionality reduction. The experiments are somewhat brief as they are only on COIL, swissroll and MNIST data; the supplementary file was said to contain more experiments but I was unable to open it.It is hard to evaluate the contribution. On one hand the method answers a clear need. On the other hand, the method seems mostly an adaptation of the principle in ref. 6 from the multilayer network case in that paper to a general loss function setting.  Details:* It is stated "Directly fitting F to (Y,X) is inelegant, since F is unrelated to the embedding, and may not work well if the mapping cannot model well the data" but then state "Alternating optimization ... trains an auxiliary embedding with a 'regularization' term, and ... trains the mapping by solving a regression". Both approaches use a regressor, the difference is in the use of regularization during the alternating optimization; it would be useful to clarify this.* "if manually simplified and coded, the gradient can actually be computed in O(N2L + N |F|)": this would seem to require some proof to show this holds in a general case; the elastic embedding is only a special case.* "Deriving, debugging and coding the gradient of P for a nonlinear F is cumbersome.": how cumbersome is this? If I understand correctly, many nonlinear dimensionality reduction methods are optimized by gradient algorithms anyway, so the gradient with respect to data points is likely known, all that remains is the right-hand term in the chain rule (gradient of coordinates with respect to the mapping). Do you mean that simplification is the cumbersome part?* "each term depends only on 2 projections (zn and zm", what are zn and zm?* "it is even possible to use something like a regression tree for F, which is not differentiable, and so the PE objective function is not differentiable either": does such a non-differentiable F still satisfy the convergence conditions mentioned below eq. (5)?