Optimization transfer algorithms in statistics.
David R. Hunter, Kenneth Lange, Chunping Wu · Deep Blue (University of Michigan) · 1999
The technique of optimization transfer has surfaced from time to time in the statistical literature under the name of majorization, or iterative majorization; the best-known example of it is the EM algorithm. Although the EM algorithm relies on some concept of missing data, the optimization engine which drives it may be extracted from the missing data framework. The dissertation explores the use of this technique of optimization for solving problems in statistics. In essence, optimization transfer replaces a difficult optimization problem by a sequence of easier optimization problems. In most cases, the solutions of the substitute problems converge to a solution of the original problem. More specifically, minimization (or maximization) of an objective function is accomplished iteratively by the construction, for a given iterate, of a majorizing (minorizing) function lying entirely above (below) the objective function but tangent to it at the given iterate. It is easy to prove the descent (ascent) property---namely, that minimizing (maximizing) the surrogate function drives the value of the objective function downhill (uphill)---and thus the optimization problem is transferred from the objective function to the surrogate. It is a challenge and an art to construct a good surrogate function. This is exactly what is accomplished by the E step of a well-conceived EM algorithm. More general optimization transfer algorithms dispense with missing data and rely on surrogate functions constructed from convexity arguments. After defining optimization transfer algorithms and laying the groundwork for their development, the dissertation discusses convergence properties of the algorithms and outlines methods for accelerating this convergence. Subsequent sections and chapters present specific examples of optimization transfer in detail, including results of numerical tests. The concluding chapter summarizes some of the properties of optimization transfer and points to several problems in statistics which may benefit from future work in this area.