On the Convergence of Bound Optimization Algorithms

Ruslan R Salakhutdinov, Sam T Roweis, Zoubin Ghahramani

TL;DR

Bound Optimization (BO) algorithms like Expectation-Maximization (EM) are workhorses of machine learning, but they are notorious for being slow. This paper provides a unified theoretical framework showing that these algorithms are essentially "locally reshaped" gradient methods, and their speed depends on how well the bound matches the objective's curvature. By simply preprocessing data—such as translating or whitening features—you can turn a sluggish first-order optimizer into a fast, quasi-Newton-like machine.

What Problem Does This Paper Address?

Many core machine learning tasks involve optimizing a scalar function, like maximizing likelihood or minimizing energy. Bound Optimization algorithms (including EM, Iterative Scaling, and NMF) are popular because they are easy to implement and come with a "never-worsen" guarantee: every step is guaranteed to improve the objective.

However, practitioners often complain that these methods are painfully slow to converge. Until this paper, there wasn't a general, analytical way to predict when they would be slow or a systematic method to fix it. The authors set out to bridge the gap between these "bound-based" updates and standard optimization theory (like gradient descent and Newton's method).

Methods

The authors analyze BO algorithms by treating them as a mapping from one parameter state to the next. They derive a general relationship showing that a BO step is equivalent to taking a gradient step transformed by a matrix $P(\theta)$: $$\theta^{(t+1)} - \theta^{(t)} = P(\theta^{(t)}) \nabla L(\theta^{(t)})$$

Key technical contributions include: * The Transformation Matrix: They prove that under mild conditions, $P(\theta)$ is positive definite, meaning BO always moves in an "uphill" direction relative to the gradient. * Convergence Rate Analysis: By Taylor-expanding the mapping near a local optimum, they show that the convergence speed is governed by a "convergence rate matrix" $M'$. * Unified View: They apply this analysis to four major algorithm classes: 1. Expectation-Maximization (EM): Where speed is tied to the "fraction of missing information." 2. Generalized Iterative Scaling (GIS): Used in maximum entropy models. 3. Non-negative Matrix Factorization (NMF): A popular dimensionality reduction technique. 4. Concave-Convex Procedure (CCCP): Used in approximate inference.

Datasets

The authors validated their theory using several synthetic and real-world benchmarks:

  • Mixture of Gaussians (MoG): Tested on synthetic 1D data (well-separated vs. overlapping) and the imlog dataset (50,000 $8 \times 8$ grayscale image patches).
  • Hidden Markov Models (HMM): Synthetic data generated with "structured" (sparse transition) vs. "aliased" (uniform/noisy) parameters.
  • Logistic Regression: Synthetic 2D feature vectors.
  • NMF: Synthetic data generated from standard normal distributions and shifted to be non-negative.
  • Energy Minimization: A simple polynomial energy function to test CCCP decompositions.

Key Insights and Ideas

  • Quasi-Newton Behavior: When the "bound" is a good fit for the objective function (e.g., when there is little "missing information" in EM), the algorithm automatically behaves like a second-order Newton method, rescaling the gradient by the inverse Hessian for lightning-fast convergence.
  • The Geometry of Slowness: Conversely, if the bound is "loose"—meaning the eigenvalues of the convergence matrix $M'$ approach unity—the algorithm takes tiny steps and exhibits poor first-order convergence.
  • Preprocessing as Acceleration: The most practical insight is that we can change the convergence properties without changing the final answer. For algorithms like GIS and NMF, the correlation and scale of input features dictate the curvature of the bound.
Figure I: Contour plots of the likelihood function L( 8) for MoG examples using well-separated (upper panels) and not-well-separated (lower panels) one-dimensional data sets. Axes correspond to the two means. The dashdot line shows the direction of the true gradient V' £(8), the solid line shows the direction of P(8)V' £(8) and the dashed line shows the direction of ( -s)-1\7 £(8). Right panels are blowups of dashed regions on the left. The numbers indicate the log of the l2 norm of V'£(8). For the "well-separated" case, in the vicinity of 8', vectors P(8)V' £(8) and ( -s)-'Y' L(8) become identical.

As seen in Figure 1 above, in "well-separated" cases, the EM step aligns almost perfectly with the ideal Newton direction. In "not-well-separated" cases, the directions diverge, leading to the dreaded slow convergence.

Key Results

  • EM for MoG: On image patches, EM converged quickly with few components (distinct clusters). As the number of components increased and clusters overlapped, convergence slowed by several orders of magnitude.
  • Iterative Scaling (GIS): Simply translating feature vectors closer to the origin sped up convergence by a factor of 12. Adding "whitening" (decorrelating the features) resulted in a 20x total speedup.
  • NMF: Translating data vectors to be closer to the origin (while remaining non-negative) outperformed the naive algorithm by a factor of over 5.
  • CCCP: The authors showed that by choosing a specific mathematical decomposition of the energy function (minimizing the ratio of concave-to-convex curvature), they could drastically accelerate convergence.

Limitations and Future Work

  • Parameter Dependency: The "optimal" preprocessing (like whitening) technically depends on knowing the optimal parameters $\theta^*$ beforehand. In practice, researchers must rely on approximations using sample statistics from the training data.
  • Local Analysis: The theoretical results primarily describe behavior near a local optimum (asymptotic convergence). While empirical results show benefits throughout the learning process, the global dynamics are more complex.
  • Future Directions: The authors suggest applying this curvature-ratio analysis to more complex inference problems, such as minimizing Bethe and Kikuchi free energies.

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 R 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