Abstract
This paper introduces a general framework for iterative optimization algorithms and establishes under general assumptions that their convergence is asymptotically geometric. We prove that under appropriate assumptions, the rate of convergence can be lower bounded, providing the exact asymptotic convergence rate. This framework encompasses the Expectation Maximization (EM) algorithm, mirror descent, alpha-EM, and Mirror Prox. Furthermore, we establish sufficient conditions for the convergence of Mirror Prox, ensuring systematic convergence to the unique minimizer of a convex function on a convex compact set.
Introduction
In the fields of mathematical optimization and machine learning, iterative algorithms are the workhorses for finding parameter estimates. However, the theoretical analysis of these algorithms has historically been fragmented. For instance, the Expectation-Maximization (EM) algorithm, widely used for latent variable models, is typically analyzed through the "ratio of missing information." In contrast, Mirror Descent, a staple of constrained convex optimization, is analyzed using Bregman divergences and gradient steps.
This paper addresses this fragmentation by proposing a "unified field theory" for iterative optimization. By defining a general framework based on a bivariate surrogate function, the authors demonstrate that these seemingly disparate algorithms are instances of a single underlying mechanism, all sharing an asymptotically geometric convergence rate.
The Bivariate Surrogate Framework
The core of the proposed framework is the definition of an iterative scheme using a bivariate function $Q(\theta, \theta')$. At each step $n$, the algorithm updates the current estimate $\theta_n$ to a new estimate $\theta_{n+1}$ by minimizing this function with respect to the second variable: $$\theta_{n+1} \in \text{argmin}_{\theta' \in \Theta} Q_{\theta_n}(\theta')$$
This structure is remarkably versatile. The authors show that several prominent algorithms fit this mold:
- EM Algorithm: Here, $Q$ corresponds to the negative expected complete-data log-likelihood.
- Mirror Descent: $Q$ is constructed from a linear approximation of the objective function combined with a Bregman divergence.
- Mirror Prox: This involves a more complex update involving an intermediate "extragradient" step, yet it still maps to the bivariate framework.
Asymptotic Convergence Rates
The primary contribution of this work is the characterization of the convergence rate near the optimal point $\theta_\star$. By examining the second-order derivatives (curvature) of the surrogate function $Q$, the authors derive the asymptotic behavior. Specifically, they define $A_\star$ as the curvature with respect to the new estimate (the second variable) and $B_\star$ as the interaction between the current estimate and the new estimate.
Theorem 1: Geometric Convergence
The authors prove that for a broad class of "well-behaved" (smooth and locally convex) problems, the sequence of estimates $\theta_n$ satisfies: $$\|\theta_n - \theta_\star\| = o(\rho^n)$$ for any $\rho$ greater than a specific spectral radius $\hat{\rho}_\star$. This establishes that geometric convergence—where the error is reduced by a constant factor at each iteration—is the standard behavior for these algorithms.
Theorem 3: Exact Rates and Invariance
Under stricter conditions, the paper provides the exact asymptotic convergence rate, determined by the eigenvalues of the matrices derived from $Q$. A significant finding is that these rates are invariant to $C^2$-reparameterization. This means the fundamental efficiency of the algorithm is a property of the optimization landscape and the choice of $Q$, rather than how the parameters are labeled.
Robustness of Mirror Prox
While much of the paper focuses on local asymptotic behavior, the authors also provide global convergence results for the Mirror Prox algorithm. Theorem 7 establishes sufficient conditions under which Mirror Prox converges systematically to the unique minimizer of a convex function on a convex compact set, regardless of the initial starting point. This fills a critical gap in the literature regarding the initialization requirements for proximal methods.
Discussion and Limitations
The framework also extends to $\alpha$-EM and Newton's method. In the case of Newton's method, the framework correctly predicts quadratic convergence, which can be viewed as a special case where the geometric rate $\rho = 0$.
However, there are notable limitations to the current study:
- Asymptotic Focus: The results describe behavior as the algorithm nears the solution. They do not provide non-asymptotic "worst-case" bounds for the initial stages of optimization.
- Smoothness Requirements: The most precise results require the functions to be twice continuously differentiable ($C^2$). Analyzing algorithms on non-smooth landscapes would require different mathematical techniques.
Conclusion
By unifying EM, Mirror Descent, and their variants under a single bivariate surrogate framework, this research provides a deeper understanding of why iterative optimization algorithms succeed. The proof of universal geometric convergence and the invariance of convergence rates offer a robust theoretical foundation for future algorithmic development and analysis.
Summary updated