{"ID":2866828,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2509.20618","arxiv_id":"2509.20618","title":"A Gapped Scale-Sensitive Dimension and Lower Bounds for Offset Rademacher Complexity","abstract":"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.","short_abstract":"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 tha...","url_abs":"https://arxiv.org/abs/2509.20618","url_pdf":"https://arxiv.org/pdf/2509.20618v1","authors":"[\"Zeyu Jia\",\"Yury Polyanskiy\",\"Alexander Rakhlin\"]","published":"2025-09-24T23:49:53Z","proceeding":"stat.ML","tasks":"[\"stat.ML\",\"cs.LG\",\"math.ST\"]","methods":"[]","has_code":false}