Friday, February 19, 2010

Concenteration inequalities

Proving generalization bounds for most of learning algorithms requires a good knowledge of concentration inequalities beside rich knowledge of probability theory and sometimes advanced topics such as Martingale, etc.

Concentration inequalities bound tail probabilities of general functions of independent random variables. Several methods have been known to prove such inequalities, including:

1)Martingale methods
2)Information-theoretic methods
3)Talagrand’s induction method
4)Some problem-speciļ¬c methods

Many inequalities have been proposed such as Hoeffding, Berstein, Azuma, McDiarmid , so on. I have started to rich my knowledge in this area. In future posts I will talk more about them or maybe provide a survey document of what I will learn.

No comments:

Post a Comment