A Gapped Scale-Sensitive Dimension and Lower Bounds for Offset Rademacher Complexity

Zeyu Jia, Yury Polyanskiy, Alexander Rakhlin

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…