A Gapped Scale-Sensitive Dimension and Lower Bounds for Offset Rademacher Complexity
This work addresses foundational problems in learning theory by providing new tools for analyzing convergence rates, though it is incremental as it builds on existing dimension concepts.
The paper introduces gapped scale-sensitive dimensions to control covering numbers for uniformly bounded function classes and uses them to derive lower bounds on offset Rademacher complexity, strengthening methods for proving convergence rate lower bounds in statistical and online learning.
We study gapped scale-sensitive dimensions of a function class in both sequential and non-sequential settings. We demonstrate that covering numbers for any uniformly bounded class are controlled above by these gapped dimensions, generalizing the results of \cite{anthony2000function,alon1997scale}. Moreover, we show that the gapped dimensions lead to lower bounds on offset Rademacher averages, thereby strengthening existing approaches for proving lower bounds on rates of convergence in statistical and online learning.