Local Minima Embedding

Minyoung Kim, Fernando De la TorreICML 2010 · OpenReview

TL;DR

Local Minima Embedding (LME) is a novel dimensionality reduction technique that compresses high-dimensional objective functions into low-dimensional spaces while strictly preserving their local minima structure. Unlike traditional methods that focus purely on data geometry, LME ensures that the "valleys" of an error surface remain valleys in the embedding. This enables better visualization, more efficient searches, and even the discovery of previously unobserved optimal points.

What Problem Does This Paper Address?

In fields like machine learning and computer vision, we spend a lot of time trying to minimize objective functions (like error or loss). These functions often exist in high-dimensional spaces, making them impossible to visualize and difficult to navigate. A major hurdle is the presence of local minima—points where the function value is lower than its immediate neighbors, but not necessarily the absolute lowest (global) value.

Concept of Local Minima Embedding

Standard dimensionality reduction (DR) tools like PCA or Isomap are designed to preserve the spatial structure of data points. However, they are "blind" to the function values associated with those points. If you use standard DR on an optimization landscape, you might accidentally "flatten" a local minimum or merge two distinct valleys into one, losing the very information needed to understand the optimization problem. The authors propose LME to bridge this gap, creating a low-dimensional "map" that respects the functional topology of the original space.

Methods

LME learns two things simultaneously: a low-dimensional embedding ($\mathbf{z}$) of the input space ($\mathbf{x}$) and a new target function $g(\mathbf{z})$ that approximates the original function $f(\mathbf{x})$.

The algorithm enforces three core conditions:

  1. Local Structure Preservation: Using a graph Laplacian approach (similar to Locality Preserving Projections), it ensures that points close to each other in the original high-dimensional space stay close in the embedded space.
  2. Local Minima Preservation: This is the "secret sauce." It enforces constraints so that if $\mathbf{x^*}$ was a local minimum in the original space, its counterpart $\mathbf{z^*}$ must be a local minimum in the embedded space. This includes enforcing a stationary point condition (the gradient must be zero).
  3. Function Approximation: The new function $g(\mathbf{z})$ must be a faithful approximation of the original function values $f(\mathbf{x})$ in a least-squares sense.

To handle complex, non-linear landscapes, the authors use the kernel trick (specifically RBF kernels) for both the embedding mapping and the target function. The resulting optimization problem is non-convex and is solved using constrained optimization techniques.

Datasets & Real-World Application

The authors evaluated LME on two primary setups:

  • Synthetic Data: The "Three-Hump Camel Function," a standard 2D optimization benchmark that contains three distinct local minima.
  • Real-World Application: An image alignment (template matching) task. The goal was to align a face template within a larger image. The search space was 4D, consisting of x-position, y-position, scale, and rotation.
Image alignment local minima

In the image alignment task, local minima represent incorrect but structurally "sticky" alignments—for instance, matching the template to a background texture or a misaligned facial feature. LME helps map these distinct error valleys into a manageable lower-dimensional space.

Key Insights and Results

  • Functional vs. Structural DR: The most significant insight is that for optimization, the value of the point is as important as its location. LME is one of the first methods to treat dimensionality reduction as a function-preserving task rather than just a point-cloud-preserving task.
  • Superior Topology Preservation: In the synthetic camel function test, LME successfully reduced the 2D space to 1D while maintaining all three minima in their correct relative order. Baseline methods like Kernel PCA and KLPP failed, often collapsing the minima or failing to represent the functional "valleys."
  • Discovery through Redundancy: The embedding can actually capture underlying dependencies between variables. In the image alignment task, LME revealed a "new" local minimum that wasn't in the original training samples. This "new" local minimum actually had a lower sum-of-squared-difference (SSD) error than the best local minimum found in the initial high-dimensional sampling, proving that the embedding can guide users to better solutions.
  • Analytic Gradients: Because the function in the embedded space ($g(\mathbf{z})$) takes an analytic form, gradients can be computed easily. This allows for efficient 1D or 2D line searches in the compressed space to find optimal parameters.

Limitations and Future Work

  • The Pre-image Problem: While LME finds a point $\mathbf{z}$ in the low-dimensional space, mapping that point back to the original high-dimensional $\mathbf{x}$ (the "pre-image") is difficult. There is often no one-to-one mapping, requiring additional optimization steps to retrieve the actual parameters (e.g., the specific rotation/scale of an image).
  • Requirement of Known Minima: The current formulation assumes we already know the locations of some local minima to use as training data. The authors acknowledge that an "unsupervised" version—where the locations of minima are unknown—is a necessary next step.
  • Computational Complexity: Solving the non-convex optimization problem with many constraints can be computationally expensive as the number of samples increases.

Summary updated

Abstract

Dimensionality reduction is a commonly used step in many algorithms for visualization, classification, clustering and modeling. Most dimensionality reduction algorithms find a low dimensional embedding that preserves the structure of high-dimensional data points. This paper proposes Local Minima Embedding (LME), a technique to find a low-dimensional embedding that preserves the local minima structure of a given objective function. LME provides an embedding that is useful for visualizing and understanding the relation between the original variables that create local minima. Additionally, the embedding can potentially be used to sample the original function to discover new local minima. The function in the embedded space takes an analytic form and hence the gradients can be computed analytically. We illustrate the benefits of LME in both synthetic data and real problems in the context of image alignment. To the best of our knowledge this is the first paper that addresses the problem of finding an embedding that preserves local minima properties of an objective function.
BibTeX
@inproceedings{kim2010local,
  author = {Minyoung Kim and Fernando De la Torre},
  title = {{Local Minima Embedding}},
  booktitle = {International Conference on Machine Learning},
  year = {2010},
  url = {https://openreview.net/forum?id=r1ZU1sZ_Zr},
}
Figure