An Exponential Efron-Stein Inequality for Lq Stable Learning Rules

Understand

There is accumulating evidence in the literature that stability of learning algorithms is a key characteristic that permits a learning algorithm to generalize.

• Despite various insightful results in this direction, there seems to be an overlooked dichotomy in the type of stability-based generalization bounds we have in the literature.
• On one hand, the literature seems to suggest that exponential generalization bounds for the estimated risk, which are optimal, can be only obtained through stringent, distribution independent and computationally intractable notions of stability such as uniform stability.
• On the other hand, it seems that weaker notions of stability such as hypothesis stability, although it is distribution dependent and more amenable to computation, can only yield polynomial generalization bounds for the estimated risk, which are suboptimal.