<p>Can someone give me typical/educative examples of how martingales can be used to prove convergence of an iterative algorithmS? </p>

<p>The examples I know of can only go so far as to show that there exists a ball of finite radius around the global minimum s.t the stochastic process is exponentially (in some parameter which scales with the radius of the ball) is suppressed to be outside this ball.  </p>

<p>Unless we can get lucky that this ball is of radius <span class="math-container">$\epsilon$</span> such <span class="math-container">``</span>escape time" arguments are weaker than convergence. Are there examples where this style of argument actually goes all the way? </p>

CC BY-SA 4.0
2020-02-12T02:25:25.210Z
See the Dubhashi-Panconesi book.
Aryeh
CC BY-SA 4.0
2020-02-12T18:34:31.403Z
Thanks! Seems like a very interesting book. Any specific example you might have in mind where such an argument was done?
gradstudent
CC BY-SA 4.0
2020-02-12T23:51:00.887Z
Not machine learning, so probably not what you are looking for, but super-martingales are often used as potential functions for randomized algorithms to prove performance guarantees and/or to bound running time (in expectation or with high-probability).  One example available online: https://algnotes.info/on/obliv/greedy/set-cover-grasp/
Neal Young
<machine-learning><randomized-algorithms><online-algorithms><stochastic-process>
Using martingale arguments to prove convergence of iterative algorithms
gradstudent
# Using martingale arguments to prove convergence of iterative algorithms

(Asked by: username_0 on 2020-02-11)

Can someone give me typical/educative examples of how martingales can be used to prove convergence of an iterative algorithmS?

The examples I know of can only go so far as to show that there exists a ball of finite radius around the global minimum s.t the stochastic process is exponentially (in some parameter which scales with the radius of the ball) is suppressed to be outside this ball.

Unless we can get lucky that this ball is of radius $\epsilon$ such ``escape time" arguments are weaker than convergence. Are there examples where this style of argument actually goes all the way?

**Tags:** machine-learning, randomized-algorithms, online-algorithms, stochastic-process

> **Comments:**
> **username_1**: See the Dubhashi-Panconesi book.  
> **username_0**: Thanks! Seems like a very interesting book. Any specific example you might have in mind where such an argument was done?  
> **username_2**: Not machine learning, so probably not what you are looking for, but super-martingales are often used as potential functions for randomized algorithms to prove performance guarantees and/or to bound running time (in expectation or with high-probability).  One example available online: https://algnotes.info/on/obliv/greedy/set-cover-grasp/  

---

## 0 answers

