Theories in Statistical learning theory

In my view, two main important questions regarding learning algorithms are generalization ability and stability analysis. When I have started working on learning algorithms, I asked myself this question: "Why can a learning algorithm predict future samples only by finding a classifier which minimizes the empirical error on training samples?". I have encountered a lot of theories and concepts looking for a answer to this question and I wanna deep my understanding of them. Please note that all of following concepts are not exactly related to answering the mentioned question but somehow related to it.

1) No free launch theorem
2) PAC learning (realizable and agnostic)
3) Occam learning
4) VC dimension
5) Covering numbers
6) Growth functions
7) Rademacher complexity

Wait for my future post for a survey of these concepts.

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-specific 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.

Prediction, Learning and games

When I started working on online learning algorithms, my adviser Dr. Jin introduced me the excellent book Prediction, learning and games and I have started to read it. At the first glance, it seems easy but when I went deeper in the concepts I found it very challenging. I will talk about the chapters in future posts.