Proofs on the convergence of optimization algorithms

Question

I was reading the following link (https://en.wikipedia.org/wiki/Scoring_algorithm) on the "Fisher Scoring Algorithm". As I understand, the Fisher Scoring Algorithm is similar to the Newton-Raphson Algorithm, but is used more to optimize Likelihood Functions of Statistical and Probabilistic Models.

Here is my understanding of this algorithm:

• Suppose we have observations: $$y_1, y_2, \dots$$

• And suppose these observations have a probability distribution function: $$f(y;\theta)$$

• If we consider the "Score Function" as the first derivative of the log-likelihood function, we can take the First Order Taylor Expansion of the Score Function and write it as follows: $$V(\theta) \approx V(\theta_0) - J(\theta_0)(\theta - \theta_0)$$

• Note that J(thetha) is the negative Hessian of the log-likelihood function : $$J(\theta_0) \approx -\sum_{i=1}^n \left(\triangledown_{\theta}^2 \log \left(f(y_i, \theta)\right)\right)$$

• We can then write the Fisher Scoring Algorithm as: $$\theta_{m+1} = \theta_m + J^{-1}(\theta_m)V(\theta_m)$$

In this article, the following two proofs are claimed about the Fisher Scoring Algorithm:

• Proof 1: As the number of iterations (i.e. "m") increases, the estimates from the Fisher Scoring Algorithm converges to the estimates that would have been obtained from Maximum Likelihood Estimation. As I understand, this is important for the following reason: Suppose you have some complicated Likelihood Function and have difficulty solving the resulting system of equations (e.g. multidimensional, non-linear, etc.) - then, the results of this proof would permit you to indirectly obtain estimates "close" to the estimates that you would have obtained via Maximum Likelihood Estimation (Note: Estimates obtained via MLE are "desirable" as these estimates have useful properties such as Unbiasedness, Consistency, Asymptotic Normality, etc.). In mathematical notation, this proof can be written like this:

$$\lim_{m\rightarrow\infty} \theta_m = \hat{\theta}_{MLE}$$

• Proof 2: To reduce the computational complexity of the Fisher Scoring Algorithm, we often replace J(thetha) with the "Expected Value" of J(thetha) - we call this I(thetha):

$$\theta_{m+1} = \theta_m + I^{-1}(\theta_m)V(\theta_m)$$

Given this information - the estimates produced from the Fisher Scoring Algorithm (after many iterations) are expected to have same asymptotic distribution properties as the true estimates under Maximum Likelihood Estimation. As I understand, this result is important because it allows for statistical inferences made using the results of the Fisher Scoring Algorithm to have similar properties as statistical inferences made using estimates from MLE. In mathematical notation, this proof can be written like this:

$$\sqrt{n}(\theta_{m+1} - \theta_{MLE}) \stackrel{d}{\rightarrow} N(0, I^{-1}(\theta_{MLE}))$$

My Question: I am trying to understand why the ideas captured within Proof 1 and Proof 2 are true.

When looking online, I found different references on these topics - but none of these references explicitly explained why these two proofs are true. Can someone please help me understand why these two proofs are true?

Thanks!

Answer 1

The Fisher Scoring Algorithm is, not merely "similar to the Newton–Raphson Algorithm", but just a particular case/application of the latter.

Proofs of convergence in the Newton–Raphson method are readily available -- see e.g. references to Kantorovich's generalization of the Newton–Raphson method to systems of nonlinear equations. In fact, Kantorovich's generalization applies even to vector equations of the form $f(x)=0$, where $f$ is a map from a Banach space $X$ to a Banach space $Y$ -- see e.g. Chapter XVIII of Kantorovich--Akilov.

Of course, to get a convergence to the root, some conditions on $f$ as well as on the closedness of the initial approximation to the root have to be imposed. However, the idea of the method is a simple linearization of the nonlinear equation.

Indeed, suppose we have a (possibly nonlinear) equation $f(x)=0$ with a root $x_*\in X$, where $f\colon X\to Y$, and $X$ and $Y$ are Banach spaces. Suppose also that the Fréchet derivative $f'(x_*)$ of $f$ at $x_*$ exists and is (an) invertible (linear operator from $X$ to $Y$). Suppose further that $f'$ is continuous at $x_*$, so that $f'(x)$ is invertible for all $x\in X$ close enough to $x_*$, and for some real $M>0$ and all such $x$ \begin{equation} \|f'(x)^{-1}\|\le M. \tag{0}\label{0} \end{equation} Suppose finally that for all $x\in X$ close enough to $x_*$ we have a Taylor-like expansion \begin{equation} f(x_*)=f(x)+f'(x)(x_*-x)+r_k(x) \tag{10}\label{10} \end{equation} such that \begin{equation} \|r_k(x)\|=O(\|x-x_*\|^2). \tag{15}\label{15} \end{equation}
Recalling that $f(x_*)=0$, rewrite \eqref{10} as \begin{equation} x_*=x-f'(x)^{-1}(f(x)+r_k(x)). \tag{20}\label{20} \end{equation} Accordingly, removing the remainder $r_k(x)$ and then replacing $x$ and $x_*$ in \eqref{20} respectively by $x_k$ and $x_{k+1}$, we get the recursion \begin{equation} x_{k+1}=x_k-f'(x_k)^{-1}(f(x_k)). \tag{30}\label{30} \end{equation} Subtracting now both sides of \eqref{20} with $x_k$ in place of $x$ from the respective sides of \eqref{30}, in view of \eqref{0} and \eqref{15} we get \begin{equation} \|x_{k+1}-x_*\|=\|f'(x_k)^{-1}(r_k(x_k))\| \\ \le M\|r_k(x_k)\|=O(\|x_k-x_*\|^2) \tag{40}\label{40} \end{equation} if $x_k$ is already close enough to $x_*$. So, we get a quadratic convergence (or better) of $x_k$ to the root $x_*$ of the $f(x)=0$, provided that the initial approximation (say $x_0$) to the root $x_*$ was already close enough to $x_*$.

---

It may be too expensive to compute $f'(x_k)^{-1}$ at each step $k$ of the just described procedure. Suppose then that we have a linear operator $L$ approximating $f'(x)^{-1}$ for all $x$ close to $x_*$ so that \begin{equation} \|f'(x)^{-1}-L\|\le t \tag{45}\label{45} \end{equation} for some $t\in(0,1)$ and all such $x$. Accordingly, modify recursion \eqref{30} as follows: \begin{equation} z_{k+1}=z_k-L(f(z_k)). \tag{50}\label{50} \end{equation} Subtracting now both sides of \eqref{20} with $z_k$ in place of $x$ from the respective sides of \eqref{50}, we get \begin{equation} z_{k+1}-x_*=(f'(z_k)^{-1}-L)(f(z_k))+f'(z_k)^{-1}(r_k(z_k)), \tag{60}\label{60} \end{equation} if $z_k$ is already close enough to $x_*$. Also, $\|f(z_k)\|=\|f(z_k)-f(x_*)\|\le C\|z_k-x_*\|$ for some real $C>0$ not depending on $k$, since $f'$ is continuous at $x_*$. So, by \eqref{60}, \eqref{45}, \eqref{0}, and \eqref{15}, \begin{equation} \|z_{k+1}-x_*\|\le tC\|z_k-x_*\|+M\|r_k(z_k)\| \\ =tC\|z_k-x_*\|+O(\|z_k-x_*\|^2) \le\tfrac12\,\|z_k-x_*\| \end{equation} if $tC<1/2$, provided that the initial approximation (say $z_0$) to the root $x_*$ was already close enough to $x_*$.

So, we get a geometric convergence (or better) of $z_k$ to the root $x_*$ of the $f(x)=0$. (Cf. Theorem 3 and formula (3) in mentioned Chapter XVIII of Kantorovich--Akilov.)