On the Convergence of Bound Optimization Algorithms

Ruslan Salakhutdinov, Sam T. Roweis, Zoubin Ghahramani

TL;DR

This paper analyzes why common optimization algorithms like EM can be slow and provides a theoretical framework to predict and improve their convergence speed. The authors show that by understanding the "curvature" of the optimization problem, we can preprocess data to make these algorithms significantly faster, often achieving near-Newton-like convergence.

What Problem Does This Paper Address?

Many machine learning and pattern recognition tasks involve optimizing complex objective functions. While direct optimization methods like gradient descent exist, many practitioners opt for "bound optimization" (BO) algorithms (e.g., EM, Iterative Scaling, NMF, CCCP) because they can exploit the structure of these functions. However, these BO algorithms are often criticized for being slow to converge, especially in certain scenarios. This paper aims to answer: why are they sometimes slow, and what can be done to speed them up?

Methods

The core of the paper is a theoretical analysis of BO algorithms. The authors derive a general relationship between the updates performed by BO methods and those of gradient and second-order (Newton-like) methods. They introduce a "convergence rate matrix" (M') that characterizes how quickly a BO algorithm approaches a local optimum.

Key aspects of their method include:

  • General BO Framework: They define a general form for BO algorithms that iteratively optimize a lower bound of the objective function.
  • Convergence Rate Matrix (M'): They show that the eigenvalues of this matrix dictate the convergence behavior. Eigenvalues close to 1 imply slow, first-order convergence, while eigenvalues close to 0 suggest faster, quasi-Newton behavior.
  • Relationship to Hessian: They connect the M' matrix to the Hessian of the objective function, revealing how the "curvature" of the problem influences convergence.
  • Transformation Matrix (P): They analyze a transformation matrix that relates the BO step to the true gradient, showing it can resemble a Newton step under certain conditions.
  • Input Preprocessing: Based on their analysis, they propose modifying the input data (e.g., translating or whitening features) to improve the convergence properties of specific BO algorithms without changing the final result.

Datasets

The paper uses synthetic datasets for demonstrating the convergence behavior of various algorithms. Specific examples include:

  • Mixture of Gaussians (MoG): Used with both "well-separated" and "not-well-separated" one-dimensional data sets, as well as a dataset of 8x8 greyscale image patches.
  • Hidden Markov Models (HMMs): Two synthetic datasets were generated: "aliased" sequences and "structured" sequences.
  • Logistic Regression: A simple 2-class logistic regression model with synthetic 2-dimensional feature vectors.
  • NMF: Synthetic data vectors were generated from a standard normal distribution and then modified to be non-negative.
  • CCCP: A simple energy function E(x) = x⁴ - 3x² + 2x - 2 was used with different decompositions.

No new benchmarks were introduced; instead, existing models and synthetic data were used to illustrate theoretical points.

Key Insights and Ideas

  • BO as Linear Iteration: BO algorithms can be viewed as linear iterations in parameter space, with the convergence rate matrix M' acting as the "contraction mapping" operator.
  • Curvature is Key: The convergence speed of BO algorithms is fundamentally tied to the curvature of the objective function and its bounds. "Plateau" regions or areas with low curvature lead to slow convergence.
  • "Missing Information" as a Bottleneck: For EM, the "fraction of missing information" (related to the overlap of latent variable distributions) directly impacts convergence speed. High missing information means slow convergence.
  • Feature Correlation Matters for GIS/NMF: For algorithms like Generalized Iterative Scaling (GIS) and Non-Negative Matrix Factorization (NMF), highly correlated or dependent feature vectors lead to slow convergence.
  • Decomposition Choice for CCCP: The way an energy function is decomposed into convex and concave parts significantly affects CCCP's convergence rate. Minimizing the ratio of curvatures is crucial.
  • Preprocessing as a Powerful Tool: Simple data transformations (translation, whitening) can dramatically improve convergence speed for GIS, NMF, and CCCP without altering the final solution. This is a practical and effective way to overcome slow convergence.

Key Results

  • EM: Exhibits quasi-Newton behavior on "well-separated" MoG data and "structured" HMM data, converging in 10-15 iterations. On "overlapping" or "aliased" data, it shows poor, first-order convergence, taking orders of magnitude longer.
  • GIS: Naive GIS on unpreprocessed 2D logistic regression data took over 2500 iterations. Translating features reduced this to ~230 iterations (a factor of 12 speedup). Translating and whitening features achieved convergence in ~100 iterations (a factor of 20 speedup).
  • NMF: Naive NMF on unpreprocessed data took over 1300 iterations. After translating data vectors, convergence was achieved in ~230 iterations (a factor of 5 speedup).
  • CCCP: Different decompositions of the energy function led to vastly different convergence speeds, with decompositions that minimized the ratio of concave-convex curvature converging much faster.

Limitations and Future Work

  • Approximations: The analysis often relies on approximations, particularly in the neighborhood of a local optimum.
  • Generalization to Other BO: While the framework is general, applying it to all BO algorithms requires deriving specific forms of the convergence rate matrix.
  • Future Work: The authors mention ongoing work to derive analytic conditions for CCCP's convergence on Bethe and Kikuchi free energies. They also suggest that similar analysis can be applied to other BO algorithms, such as multiplicative updates for SVMs. The paper also hints at exploring "hybrid" approaches that switch to direct optimization when BO is predicted to be slow.

Summary updated

Abstract

Many practitioners who use the EM algorithm complain that it is sometimes slow. When does this happen, and what can be done about it? In this paper, we study the general class of bound optimization algorithms - including Expectation-Maximization, Iterative Scaling and CCCP - and their relationship to direct optimization algorithms such as gradient-based methods for parameter learning. We derive a general relationship between the updates performed by bound optimization methods and those of gradient and second-order methods and identify analytic conditions under which bound optimization algorithms exhibit quasi-Newton behavior, and conditions under which they possess poor, first-order convergence. Based on this analysis, we consider several specific algorithms, interpret and analyze their convergence properties and provide some recipes for preprocessing input to these algorithms to yield faster convergence behavior. We report empirical results supporting our analysis and showing that simple data preprocessing can result in dramatically improved performance of bound optimizers in practice.
BibTeX
@inproceedings{salakhutdinov2003convergence,
  author = {Ruslan Salakhutdinov and Sam T. Roweis and Zoubin Ghahramani},
  title = {{On the Convergence of Bound Optimization Algorithms}},
  booktitle = {Conference on Uncertainty in Artificial Intelligence},
  year = {2003},
}
Figure