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?

  • $\begingroup$ See the Dubhashi-Panconesi book. $\endgroup$ – Aryeh Feb 12 at 2:25
  • $\begingroup$ Thanks! Seems like a very interesting book. Any specific example you might have in mind where such an argument was done? $\endgroup$ – gradstudent Feb 12 at 18:34
  • 1
    $\begingroup$ 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: algnotes.info/on/obliv/greedy/set-cover-grasp $\endgroup$ – Neal Young Feb 12 at 23:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.