Local Rademacher Complexity Bounds based on Covering Numbers
This work addresses a theoretical bottleneck in machine learning by offering a convenient tool for deriving generalization bounds, but it appears incremental as it builds on existing complexity theory without introducing a new paradigm.
The paper tackles the problem of controlling local Rademacher complexities by providing a general result that relates complexities with constraints on expected and empirical norms, which is applied to derive refined generalization error bounds for function classes under general entropy conditions.
This paper provides a general result on controlling local Rademacher complexities, which captures in an elegant form to relate the complexities with constraint on the expected norm to the corresponding ones with constraint on the empirical norm. This result is convenient to apply in real applications and could yield refined local Rademacher complexity bounds for function classes satisfying general entropy conditions. We demonstrate the power of our complexity bounds by applying them to derive effective generalization error bounds.