A fast, universal algorithm to learn parametric nonlinear embeddings

Miguel Á. Carreira-Perpiñán, Max VladymyrovNeurIPS 2015 · OpenReview

This paper, presented by Miguel Á. Carreira-Perpiñán and Max Vladymyrov, introduces a flexible and efficient framework for training parametric nonlinear embeddings—a crucial task for data visualization and dimensionality reduction.

TL;DR

The authors propose a "universal" framework that decouples the choice of embedding (like t-SNE or Elastic Embedding) from the choice of mapping (like neural networks or linear maps). By using the Method of Auxiliary Coordinates (MAC), they transform a complex, slow optimization problem into a fast, alternating process that scales linearly with the number of data points.

What Problem Does This Paper Address?

Nonlinear embeddings (NLEs) are powerful tools for visualizing high-dimensional data by projecting it into 2D or 3D space. However, standard NLEs like t-SNE only provide coordinates for the training data; they don't define a "map" to handle new, unseen data (known as the "out-of-sample" problem).

To fix this, researchers use Parametric Embeddings (PE), where a function (like a neural network) is trained to perform the projection. The traditional way to train these is via the chain rule and gradient descent. This approach comes with three major headaches:

  1. Complexity: You have to derive and code new gradients for every specific combination of embedding and mapping.
  2. Speed: The objective functions involve $O(N^2)$ pairs of points, making them incredibly slow to compute as datasets grow.
  3. Differentiability: The mapping must be differentiable, ruling out useful tools like regression trees.

Methods

The authors solve these issues using the Method of Auxiliary Coordinates (MAC). Instead of optimizing the mapping parameters directly through the complex embedding objective, they break the problem into two simpler, alternating steps:

  1. The Z-step (Regularized Embedding): The low-dimensional projections ($Z$) are treated as free variables. The embedding objective is optimized while adding a penalty that keeps these coordinates close to the current mapping's output. Because this step looks like a standard embedding problem, existing "N-body" acceleration methods (like Barnes-Hut) can be reused to make it run in $O(N \log N)$ or $O(N)$ time.
  2. The F-step (Mapping/Regression): The coordinates $Z$ are treated as fixed targets, and the mapping (e.g., a neural net or linear model) is trained to predict them. This is a standard least-squares regression problem, which is well-understood and easy to solve with existing libraries.

By alternating these steps and gradually increasing the penalty parameter ($\mu$), the mapping and the embedding eventually converge to a unified, optimal solution.

Key Insights and Ideas

  • Decoupling is King: By separating the "embedding logic" from the "mapping logic," the algorithm becomes "universal." You can plug in a new neural net architecture or a different embedding objective without rewriting the entire optimization loop.
  • Reusing Fast Solvers: Because the Z-step mimics a standard free embedding, highly optimized N-body methods developed for t-SNE can be borrowed. This allows the algorithm to scale to millions of points.
  • Direct Fit vs. PE: The paper clarifies that simply fitting a map to a pre-computed "free" embedding (a "direct fit") is usually suboptimal. The MAC approach allows the embedding to "bend" slightly to accommodate the limitations of the mapping family, leading to better overall performance.
Comparison of Free Embedding, Direct Fit, and Parametric Embedding (PE)

Key Results

The authors evaluated their algorithm on standard benchmarks including COIL-20, a synthetic Swissroll, and MNIST.

  • Massive Speedups: For a neural-net-based t-SNE on the Swissroll dataset, the MAC approach was significantly faster than traditional chain-rule optimization. On MNIST, MAC was 5x faster than minibatch gradient descent and 20x faster than exact batch mode.
  • Scalability: While traditional parametric embedding gradients often run out of memory or become prohibitively slow at large $N$, the MAC iterations remain linear in time complexity.
  • Quality Preservation: MAC reaches the same (or better) local optima as traditional methods, meaning there is no "accuracy penalty" for the increased speed and flexibility.
Runtime and Objective Function comparisons between MAC and traditional PE

Limitations and Future Work

  • Penalty Schedule: Like many penalty-based methods, the performance of MAC depends on the "schedule" used to increase the penalty parameter $\mu$. If increased too quickly, the algorithm might get stuck in poor local optima; if too slowly, it takes longer to converge.
  • Non-Differentiable Maps: While MAC could allow for non-differentiable mappings like regression trees, the primary experiments focused on linear maps and neural networks. Empirical validation of tree-based parametric embeddings is a natural next step.
  • Hyperparameter Tuning: The Z-step and F-step each have their own optimization parameters (learning rates, iterations), adding a layer of hyperparameter tuning to the training process.

Summary updated

Abstract

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.
BibTeX
@inproceedings{carreiraperpinan2015fast,
  author = {Miguel Á. Carreira-Perpiñán and Max Vladymyrov},
  title = {{A fast, universal algorithm to learn parametric nonlinear embeddings}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2015},
  url = {https://openreview.net/forum?id=Skb0zv-_Zr},
}

Loading related content...

Figure