Important asymptotic theorems

Last updated on Jul 31, 2022 4 min read Statistics

Machine learning algorithms are very populuar. However, machine learing algorithms are not stable/consistant on the performance because lots of them are not using statistical inference. Thus, statistical theory for estimating function which has established hundreds of years ago becomes a more and more interesting research direction.

In this blog, I will introduce a few important asymptotic theorems that are fundamental to prove some machine learning algorithms, such as SVM and Markov Chain.

Fatou-Lebesgue Lemma: if the random variable $X_{n} \overset{a . s}{\to} X$ and if for all n $X_{n} \geq Y$ with $E | Y | < \infty$ , then $E (\underset{n \to \infty}{lim inf} X_{n}) \leq \underset{n \to \infty}{lim inf} E (X_{n})$ It holds if $X_{n} \geq 0$ for all n.

By using Fatou-Lebesgue Lemma, we can prove the (a) Monotone convergence Theorem, and the (b) Lebesgue Dominated Convergence Theorem.

(a) Monotone convergence Theorem: If $X_{n}$ is a sequence of nonnegative measurable functions denoted by $0 \leq x_{1} \leq x_{2} \dots \leq x_{n} \leq x_{n + 1}$ and $X_{n} \overset{a . s}{\to} X$ , then $lim_{0 \to \infty} E (X_{n}) = E (lim_{0 \to \infty} X_{n}) = E X$
(b) Lebesgue Dominated Convergence Theorem：If the random variables $X_{n} \to X$ , then we have $| X_{n} | \leq Y$ , almost surely for all n. Then $X_{n} \in L^{1}$ , $X \in L^{1}$ , and $lim_{0 \to \infty} E (X_{n}) = E (X)$ .

Partical converge relation： $X_{n} \overset{P}{\to} X$ if and only if every subsequence $n_{1}, N_{2}, \dots ϵ {1, 2, \dots}$ has a sub-sequence $m_{1}, m_{2}, \dots ϵ {n_{1}, n_{2}, \dots}$ such that $X_{m_{j}} \overset{a . s}{\to} X$ as $j \to \infty$ .

Borel-Cantelli Lemma: for { $A_{n} : n \geq 1$ } a sequence of events in a probability space if $\sum_{n = 1}^{\infty} P (A_{n}) < \infty$ then $P (A_{n} i . o .) = 0$ ; only a finite number of the events occur, with probability 1. Conversely, if the $A_{n}$ are independent and $\sum_{n = 1}^{\infty} P (A_{n}) = \infty$ , then $P (A_{n} i . o .) = 1$ ; an infinite number of the events occur, with probability 1.

Borel-Cantelli Lemma is useful in problems related to the a.s. convergence. It could be written as $P (| X_{n} - X | > ϵ i . o .) = 0, \forall ϵ > 0$ .

Laws of Large Numbers: When the convergence is in probability or law, this is known as weak law of large numbers (WLLN). if $E | X | < \infty$ , then $\bar{X_{n}} \overset{P}{\to} μ = E X$ . When the convergence is almost surely, it is the strong laws of large nubmers (SLLN). $\bar{X_{n}} \overset{a . s .}{\to} μ \Leftrightarrow E X < \infty$ and $μ = E X$

Central Limit Theorems: Let $X_{1}, X_{2}, \dots$ be i.i.d. random vectors with mean $μ$ and finite covariance matrix, $Σ$ . Then $\sqrt{n} (\bar{X_{n}} - μ) \overset{L}{\to} N (0, Σ)$ .

Slutsky’s Theorem: Let ${X_{n}}, {Y_{n}}$ be sequences of scalar/vector/matrix random elements. If $X_{n}$ converges in distribution to a random element X; and $Y_{n}$ converges in probability to a constant c, then $X_{n} + Y_{n} \overset{d}{\to} X + c$ , $X_{n} Y_{n} \overset{d}{\to} c X$ , $\frac{X_{n}}{Y_{n}} \overset{d}{\to} \frac{X_{n}}{c}$ .

SVM¹could be an application of Lebesgue Dominated Convergence Theorem and Central Limit Theorem. We can use the theorem and Partical converge relation to prove the hinge loss function, when the data is not linearly separable. By limiting on Hilbert space, a weakly convergent subsequence. We can apply asymptotic normality property on the regularization parameter $λ_{i} \to 0$ and thus to solve the miminization problem on the hyperplane $ω_{n}$ , where the solution $\tilde{ω} = ω_{*}$ because $ω_{*} (λ_{i}) \overset{a . s .}{\to} ω_{*}$ .

The Markov chain² can be proved by using Borel-Cantelli Lemma. The probability of having state from $i$ and eventually return to $i$ is 1. If this probability is strictly less than 1, $i$ is called transient.

SVM is supervised learning model with associated learning algorithm that analyzes data used for classification and regression analysis.↩
A Markov chain is a stochastic model describing a sequence of possible events in which the probability of each event depends only on the state attained in the previous event. In probability theory and related fields, a Markov process, named after the Russian mathematician Andrey Markov, is a stochastic process that satisfies the Markov property. The defining characteristic of a Markov chain is that no matter how the process arrived at its present state, the possible future states are fixed. In other words, the probability of transitioning to any particular state is dependent solely on the current state and time elapsed. The state space, or set of all possible states, can be anything: letters, numbers, weather conditions, sales volume，etc.↩

Asymptotic Theory Theorem MCMC SVM

Important asymptotic theorems

Yuan Du

Senior Data Scientist