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

The celebrated Vapnik-Chervonenkis dimension vc(F) of a binary-valued function class F and the scale-sensitive dimension vc(F, α) of a real-valued function class F are central notions in the study of empirical processes and convergence of statistical learning methods [VC71, BLW94, KS94]. Sequential analogues of these notions--the Littlestone dimension ldim(F) and the sequential scale-sensitive dimension sfat(F, α)-- have been shown to play an analogously central role in the study of uniform martingale laws and online prediction [Lit88, BDPSS09, RST10]. In this paper, we study "gapped" versions of vc(F,α) and sfat(F, α). The modification yields a dimension that is no larger than the original one, yet can still be shown to control covering numbers in both sequential and non-sequential cases. More importantly, the new notion gives us a more precise control on the functions involved in "shattering" and thus yields non-vacuous lower bounds for offset Rademacher complexities for any uniformly bounded class--both in the classical and sequential cases--and, as a consequence, tighter lower bounds for online prediction problems, such as online regression or transductive learning. Our definition in the non-sequential case can also be seen as a modification of the Natarajan dimension [NT88, Nat89], and was, in fact, introduced in [AB00]. We first motivate the development in this paper on the simpler case of non-sequential data. We start by recalling the definition of the Vapnik-Chervonenkis dimension and its scale-sensitive version.