The paper introduces local Rademacher complexities as a data-dependent measure of complexity for learning algorithms. These complexities are computed from a subset of functions with small empirical error, leading to tighter error bounds. The authors show that local Rademacher averages can provide optimal rates of convergence, which are more refined than global Rademacher averages. They apply these results to classification and prediction problems, particularly with convex function classes and kernel classes. The paper discusses the limitations of traditional complexity measures like Vapnik-Chervonenkis dimension and metric entropy, which are either too conservative or require knowledge of the underlying distribution. Local Rademacher averages, on the other hand, can be computed from the data and provide more accurate bounds. The authors present several results, including a theorem that shows how local Rademacher averages can be used to derive error bounds. They also discuss the relationship between local and global Rademacher averages and show that the fixed point of the local Rademacher average can be used to obtain data-dependent error bounds. The paper also addresses the issue of noise in prediction problems, where there may not be a perfect estimator. The authors show that local Rademacher averages can still provide useful bounds in such cases. The results are applied to various learning problems, including classification and regression with kernel classes. The authors show that local Rademacher averages can be used to approximate the complexity of these classes and provide data-dependent error bounds. The paper concludes with a discussion of the implications of these results for the theory of learning algorithms and the practical application of these bounds in machine learning. The authors argue that local Rademacher complexities provide a more accurate and useful measure of complexity than traditional methods, and that they can be used to derive tighter error bounds for learning algorithms.The paper introduces local Rademacher complexities as a data-dependent measure of complexity for learning algorithms. These complexities are computed from a subset of functions with small empirical error, leading to tighter error bounds. The authors show that local Rademacher averages can provide optimal rates of convergence, which are more refined than global Rademacher averages. They apply these results to classification and prediction problems, particularly with convex function classes and kernel classes. The paper discusses the limitations of traditional complexity measures like Vapnik-Chervonenkis dimension and metric entropy, which are either too conservative or require knowledge of the underlying distribution. Local Rademacher averages, on the other hand, can be computed from the data and provide more accurate bounds. The authors present several results, including a theorem that shows how local Rademacher averages can be used to derive error bounds. They also discuss the relationship between local and global Rademacher averages and show that the fixed point of the local Rademacher average can be used to obtain data-dependent error bounds. The paper also addresses the issue of noise in prediction problems, where there may not be a perfect estimator. The authors show that local Rademacher averages can still provide useful bounds in such cases. The results are applied to various learning problems, including classification and regression with kernel classes. The authors show that local Rademacher averages can be used to approximate the complexity of these classes and provide data-dependent error bounds. The paper concludes with a discussion of the implications of these results for the theory of learning algorithms and the practical application of these bounds in machine learning. The authors argue that local Rademacher complexities provide a more accurate and useful measure of complexity than traditional methods, and that they can be used to derive tighter error bounds for learning algorithms.