High probability upper bounds, online learning, and stability

In statistical learning, the guarantees for many learning algorithms are provided both in expectation and with high probability with respect to the learning sample. Usually, the concentration of measure inequalities provide sharp tails and reduce the problem to the analysis in expectation. But when considering some learning algorithms other than empirical risk minimization powerful concentration results are of no use and tight high probability bounds become an inaccessible dream. Simultaneously, tight results in expectation can be proven as a two line exercise via stability arguments. In this talk, we will discuss several successful approaches towards getting high probability bounds including the online to batch conversion and the analysis of monotonic learning rules.