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
imlogdataset (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.
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