Skip to main content
Notice removed Authoritative reference needed by CommunityBot
Bounty Ended with Iosif Pinelis's answer chosen by CommunityBot
removed capitals from title
Link
YCor
  • 63.9k
  • 5
  • 187
  • 286

Proofs on the Convergenceconvergence of Optimization Algorithmsoptimization algorithms

Notice added Authoritative reference needed by stats_noob
Bounty Started worth 50 reputation by stats_noob
Source Link

Proofs on the Convergence of Optimization Algorithms

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!