The paper introduces new bounds on the error of learning algorithms using a data-dependent notion of complexity, specifically local Rademacher complexities. These bounds are optimal and are based on empirical Rademacher averages computed from a subset of functions with small empirical error. The authors present applications to classification and prediction with convex function classes and kernel classes. The key contributions include: 1. **Local Rademacher Complexities**: The authors propose using local Rademacher averages, which are computed from a subset of functions with small empirical error, as a more efficient and accurate measure of complexity compared to global averages. 2. **Error Bounds**: They establish error bounds that are optimal in terms of the complexity of the function class, providing sharper rates of convergence than previous methods. These bounds are applicable to both classification and regression problems. 3. **Data-Dependent Bounds**: The bounds are data-dependent, meaning they can be computed directly from the sample, which is crucial for practical applications. The authors also show that the empirical bounds are close to the distribution-dependent bounds with high probability. 4. **Applications**: The results are applied to various scenarios, including nonnegative functions, binary-valued functions, and kernel classes, demonstrating their broad applicability. 5. **Proof Techniques**: The proofs combine classical empirical processes theory with concentration inequalities, leveraging the peeling and weighting techniques to control the variance of functions in the class. The paper provides a comprehensive framework for understanding and improving the performance of learning algorithms, particularly in the context of finite sample sizes and noisy data.The paper introduces new bounds on the error of learning algorithms using a data-dependent notion of complexity, specifically local Rademacher complexities. These bounds are optimal and are based on empirical Rademacher averages computed from a subset of functions with small empirical error. The authors present applications to classification and prediction with convex function classes and kernel classes. The key contributions include: 1. **Local Rademacher Complexities**: The authors propose using local Rademacher averages, which are computed from a subset of functions with small empirical error, as a more efficient and accurate measure of complexity compared to global averages. 2. **Error Bounds**: They establish error bounds that are optimal in terms of the complexity of the function class, providing sharper rates of convergence than previous methods. These bounds are applicable to both classification and regression problems. 3. **Data-Dependent Bounds**: The bounds are data-dependent, meaning they can be computed directly from the sample, which is crucial for practical applications. The authors also show that the empirical bounds are close to the distribution-dependent bounds with high probability. 4. **Applications**: The results are applied to various scenarios, including nonnegative functions, binary-valued functions, and kernel classes, demonstrating their broad applicability. 5. **Proof Techniques**: The proofs combine classical empirical processes theory with concentration inequalities, leveraging the peeling and weighting techniques to control the variance of functions in the class. The paper provides a comprehensive framework for understanding and improving the performance of learning algorithms, particularly in the context of finite sample sizes and noisy data.